File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1109/ICDE.2012.40
- Scopus: eid_2-s2.0-84864265150
- WOS: WOS:000309122100036
- Find via
Supplementary
- Citations:
- Appears in Collections:
Conference Paper: Bi-level locality sensitive hashing for k-nearest neighbor computation
Title | Bi-level locality sensitive hashing for k-nearest neighbor computation |
---|---|
Authors | |
Issue Date | 2012 |
Citation | Proceedings - International Conference on Data Engineering, 2012, p. 378-389 How to Cite? |
Abstract | We present a new Bi-level LSH algorithm to perform approximate k-nearest neighbor search in high dimensional spaces. Our formulation is based on a two-level scheme. In the first level, we use a RP-tree that divides the dataset into sub-groups with bounded aspect ratios and is used to distinguish well-separated clusters. During the second level, we compute a single LSH hash table for each sub-group along with a hierarchical structure based on space-filling curves. Given a query, we first determine the sub-group that it belongs to and perform k-nearest neighbor search within the suitable buckets in the LSH hash table corresponding to the sub-group. Our algorithm also maps well to current GPU architectures and can improve the quality of approximate KNN queries as compared to prior LSH-based algorithms. We highlight its performance on two large, high-dimensional image datasets. Given a runtime budget, Bi-level LSH can provide better accuracy in terms of recall or error ration. Moreover, our formulation reduces the variation in runtime cost or the quality of results. © 2012 IEEE. |
Persistent Identifier | http://hdl.handle.net/10722/206203 |
ISSN | 2023 SCImago Journal Rankings: 1.306 |
ISI Accession Number ID |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Pan, Jia | - |
dc.contributor.author | Manocha, Dinesh | - |
dc.date.accessioned | 2014-10-22T01:25:26Z | - |
dc.date.available | 2014-10-22T01:25:26Z | - |
dc.date.issued | 2012 | - |
dc.identifier.citation | Proceedings - International Conference on Data Engineering, 2012, p. 378-389 | - |
dc.identifier.issn | 1084-4627 | - |
dc.identifier.uri | http://hdl.handle.net/10722/206203 | - |
dc.description.abstract | We present a new Bi-level LSH algorithm to perform approximate k-nearest neighbor search in high dimensional spaces. Our formulation is based on a two-level scheme. In the first level, we use a RP-tree that divides the dataset into sub-groups with bounded aspect ratios and is used to distinguish well-separated clusters. During the second level, we compute a single LSH hash table for each sub-group along with a hierarchical structure based on space-filling curves. Given a query, we first determine the sub-group that it belongs to and perform k-nearest neighbor search within the suitable buckets in the LSH hash table corresponding to the sub-group. Our algorithm also maps well to current GPU architectures and can improve the quality of approximate KNN queries as compared to prior LSH-based algorithms. We highlight its performance on two large, high-dimensional image datasets. Given a runtime budget, Bi-level LSH can provide better accuracy in terms of recall or error ration. Moreover, our formulation reduces the variation in runtime cost or the quality of results. © 2012 IEEE. | - |
dc.language | eng | - |
dc.relation.ispartof | Proceedings - International Conference on Data Engineering | - |
dc.title | Bi-level locality sensitive hashing for k-nearest neighbor computation | - |
dc.type | Conference_Paper | - |
dc.description.nature | link_to_subscribed_fulltext | - |
dc.identifier.doi | 10.1109/ICDE.2012.40 | - |
dc.identifier.scopus | eid_2-s2.0-84864265150 | - |
dc.identifier.spage | 378 | - |
dc.identifier.epage | 389 | - |
dc.identifier.isi | WOS:000309122100036 | - |
dc.identifier.issnl | 1084-4627 | - |