New paradigms for approximate nearest-neighbor search

Similarity search;Nearest-neighbor search;Computational geometry;Algorithms and analysis

Ram, Parikshit ; Balcan, Maria-Florina Gray, Alexander G. Computational Science and Engineering Lebanon, Guy Clarkson, Kenneth L. Vempala, Santosh S. ; Balcan, Maria-Florina

University:Georgia Institute of Technology

Department:Computational Science and Engineering

关键词: Similarity search;    Nearest-neighbor search;    Computational geometry;    Algorithms and analysis;   

Others  :  https://smartech.gatech.edu/bitstream/1853/49112/1/RAM-DISSERTATION-2013.pdf

美国|英语

来源: SMARTech Repository

【 摘 要 】

Nearest-neighbor search is a very natural and universal problem in computer science. Often times, the problem size necessitates approximation. In this thesis, I present new paradigms for nearest-neighbor search (along with new algorithms and theory in these paradigms) that make nearest-neighbor search more usable and accurate. First, I consider a new notion of search error, the rank error, for an approximate neighbor candidate. Rank error corresponds to the number of possible candidates which are better than the approximate neighbor candidate. I motivate this notion of error and present new efficient algorithms that return approximate neighbors with rank error no more than a user specified amount. Then I focus on approximate search in a scenario where the user does not specify the tolerable search error (error constraint); instead the user specifies the amount of time available for search (time constraint). After differentiating between these two scenarios, I present some simple algorithms for time constrained search with provable performance guarantees. I use this theory to motivate a new space-partitioning data structure, the max-margin tree, for improved search performance in the time constrained setting. Finally, I consider the scenario where we do not require our objects to have an explicit fixed-length representation (vector data). This allows us to search with a large class of objects which include images, documents, graphs, strings, time series and natural language. For nearest-neighbor search in this general setting, I present a provably fast novel exact search algorithm. I also discuss the empirical performance of all the presented algorithms on real data.