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


全文

引用次數

其它資訊
摘要Nearest 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.
著者Tao YF, Yi K, Sheng C, Kalnis P
會議名稱35th ACM SIGMOD Conference
會議開始日29.06.2009
會議完結日02.07.2009
會議地點Providence
會議國家/地區美國
詳細描述ACM
出版年份2009
月份1
日期1
出版社ASSOC COMPUTING MACHINERY
頁次563 - 575
國際標準書號978-1-60558-554-3
語言英式英語
關鍵詞Locality Sensitive Hashing; Nearest Neighbor Search
Web of Science 學科類別Computer Science; Computer Science, Information Systems

上次更新時間 2021-21-10 於 00:53