File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Bi-level locality sensitive hashing for k-nearest neighbor computation

TitleBi-level locality sensitive hashing for k-nearest neighbor computation
Authors
Issue Date2012
Citation
Proceedings - International Conference on Data Engineering, 2012, p. 378-389 How to Cite?
AbstractWe 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 Identifierhttp://hdl.handle.net/10722/206203
ISSN
ISI Accession Number ID

 

DC FieldValueLanguage
dc.contributor.authorPan, Jia-
dc.contributor.authorManocha, Dinesh-
dc.date.accessioned2014-10-22T01:25:26Z-
dc.date.available2014-10-22T01:25:26Z-
dc.date.issued2012-
dc.identifier.citationProceedings - International Conference on Data Engineering, 2012, p. 378-389-
dc.identifier.issn1084-4627-
dc.identifier.urihttp://hdl.handle.net/10722/206203-
dc.description.abstractWe 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.languageeng-
dc.relation.ispartofProceedings - International Conference on Data Engineering-
dc.titleBi-level locality sensitive hashing for k-nearest neighbor computation-
dc.typeConference_Paper-
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1109/ICDE.2012.40-
dc.identifier.scopuseid_2-s2.0-84864265150-
dc.identifier.spage378-
dc.identifier.epage389-
dc.identifier.isiWOS:000309122100036-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats