Quality and Efficiency in High Dimensional Nearest Neighbor Search
Refereed conference paper presented and published in conference proceedings


Full Text

Times Cited
Web of Science69WOS source URL (as at 27/05/2020) Click here for the latest count

Other information
AbstractNearest neighbor (NN) search in high dimensional space is an important problem in many applications. Ideally, a practical solution (i) should be implementable in a relational database, and (ii) its query cost should grow sub-linearly with the dataset size, regardless of the data and query distributions. Despite the bulk of NN literature, no solution fulfills both requirements, except locality sensitive hashing (LSH). The existing LSH implementations are either rigorous or adhoc. Rigorous-LSH ensures good quality of query results, but requires expensive space and query cost. Although adhoc-LSH is more efficient, it abandons quality control, i.e., the neighbor it outputs can be arbitrarily bad. As a result, currently no method is able to ensure both quality and efficiency simultaneously in practice.
All Author(s) ListTao YF, Yi K, Sheng C, Kalnis P
Name of Conference35th ACM SIGMOD Conference
Start Date of Conference29/06/2009
End Date of Conference02/07/2009
Place of ConferenceProvidence
Country/Region of ConferenceUnited States of America
Detailed descriptionACM
Year2009
Month1
Day1
PublisherASSOC COMPUTING MACHINERY
Pages563 - 575
ISBN978-1-60558-554-3
LanguagesEnglish-United Kingdom
KeywordsLocality Sensitive Hashing; Nearest Neighbor Search
Web of Science Subject CategoriesComputer Science; Computer Science, Information Systems

Last updated on 2020-28-05 at 02:46