Loading...
Please wait, while we are loading the content...
Similar Documents
Nearest Neighbor Retrieval Using Distance-Based Hashing
| Content Provider | CiteSeerX |
|---|---|
| Author | Athitsos, Vassilis Kollios, George Potamias, Michalis Papapetrou, Panagiotis |
| Abstract | Abstract — A method is proposed for indexing spaces with arbitrary distance measures, so as to achieve efficient approximate nearest neighbor retrieval. Hashing methods, such as Locality Sensitive Hashing (LSH), have been successfully applied for similarity indexing in vector spaces and string spaces under the Hamming distance. The key novelty of the hashing technique proposed here is that it can be applied to spaces with arbitrary distance measures, including non-metric distance measures. First, we describe a domain-independent method for constructing a family of binary hash functions. Then, we use these functions to construct multiple multibit hash tables. We show that the LSH formalism is not applicable for analyzing the behavior of these tables as index structures. We present a novel formulation, that uses statistical observations from sample data to analyze retrieval accuracy and efficiency for the proposed indexing method. Experiments on several real-world data sets demonstrate that our method produces good trade-offs between accuracy and efficiency, and significantly outperforms VP-trees, which are a well-known method for distance-based indexing. I. |
| File Format | |
| Access Restriction | Open |
| Subject Keyword | Hashing Technique Statistical Observation Lsh Formalism Non-metric Distance Measure Several Real-world Data Set Neighbor Retrieval Retrieval Accuracy Similarity Indexing Neighbor Retrieval Using Distance-based Hashing Domain-independent Method Distance-based Indexing Binary Hash Function Key Novelty Locality Sensitive Hashing Indexing Method Arbitrary Distance Measure Good Trade-off Multiple Multibit Hash Table |
| Content Type | Text |
