作者
Yufei Tao, Ke Yi, Cheng Sheng, Panos Kalnis
发表日期
2010/7/1
期刊
ACM Transactions on Database Systems (TODS)
卷号
35
期号
3
页码范围
20
出版商
ACM
简介
Nearest Neighbor (NN) search in high-dimensional space is an important problem in many applications. From the database perspective, a good solution needs to have two properties: (i) it can be easily incorporated in a relational database, and (ii) its query cost should increase sublinearly with the dataset size, regardless of the data and query distributions. Locality-Sensitive Hashing (LSH) is a well-known methodology fulfilling both requirements, but its current implementations either incur expensive space and query cost, or abandon its theoretical guarantee on the quality of query results.
Motivated by this, we improve LSH by proposing an access method called the Locality-Sensitive B-tree (LSB-tree) to enable fast, accurate, high-dimensional NN search in relational databases. The combination of several LSB-trees forms a LSB-forest that has strong quality guarantees, but improves dramatically the efficiency of the …
学术搜索中的文章
Y Tao, K Yi, C Sheng, P Kalnis - ACM Transactions on Database Systems (TODS), 2010