Source-linked AI summary
Density Sensitive Hashing
Yue Lin, Deng Cai, Cheng Li
TL;DR
High-dimensional nearest-neighbor search is difficult for conventional indexes and random-projection hashing, which requires many projections and incurs storage and computational costs. Density Sensitive Hashing (DSH) uses data geometry to select informative projections, and experiments on three large datasets show improved retrieval accuracy and scalability over state-of-the-art hashing methods.
Problem
High-dimensional nearest-neighbor search challenges conventional index structures, while random-projection hashing requires many projections, increasing storage space and computational cost.
Method
DSH extends LSH by using k-means-partitioned data geometry and maximum entropy to select projections that separate adjacent groups and provide informative bits.
Results
DSH significantly outperforms state-of-the-art hashing methods in retrieval accuracy and scales well to data size on three large datasets.
Takeaways & Limitations
DSH generates hashing codes with more discriminating power by guiding projection selection with the geometric structure of the data.
Takeaways & Limitations
Random-projection hashing methods require O(ln n/ǫ2) projective vectors to preserve pairwise distances, leading to long codewords, large storage space, and high computational cost.
Abstract
from arXiv · showhide
Nearest neighbors search is a fundamental problem in various research fields like machine learning, data mining and pattern recognition. Recently, hashing-based approaches, e.g., Locality Sensitive Hashing (LSH), are proved to be effective for scalable high dimensional nearest neighbors search. Many hashing algorithms found their theoretic root in random projection. Since these algorithms generate the hash tables (projections) randomly, a large number of hash tables (i.e., long codewords) are required in order to achieve both high precision and recall. To address this limitation, we propose a novel hashing algorithm called {\em Density Sensitive Hashing} (DSH) in this paper. DSH can be regarded as an extension of LSH. By exploring the geometric structure of the data, DSH avoids the purely random projections selection and uses those projective functions which best agree with the distribution of the data. Extensive experimental results on real-world data sets have shown that the proposed method achieves better performance compared to the state-of-the-art hashing approaches.
1 INTRODUCTION
High-dimensional nearest-neighbor search makes traditional index structures ineffective, motivating hashing methods that trade exactness for scalable approximate retrieval. DSH addresses limitations of random and learning-based hashing by selecting projections using data geometry.
- Traditional KD-tree and R-tree indexes can perform worse than linear scan as dimensionality increases.
- Approximate hashing methods generate binary codes that preserve similarity between high-dimensional data points.
- LSH requires O(ln n/ε2) random projections, producing long codewords with large storage and computational costs.
- Learning-based hashing exploits data affinity structure but often fails to improve substantially as code length increases.
- DSH guides projection selection with data geometry, using adjacent cluster pairs and maximum entropy to choose informative hash bits.
- Experiments compare DSH with state-of-the-art hashing methods on three large real-world data sets.
2 BACKGROUND AND RELATED WORK
Hashing maps high-dimensional points to binary codes through projection-based functions, with LSH using random hyperplanes and probabilistic retrieval guarantees. Random projection methods require many vectors, while learning-based alternatives address this cost with their own structural and computational trade-offs.
- The generic hashing task maps n data points in R^d to L-bit binary codes using L hash functions.
- A linear projection hash function uses a projection vector and intercept within a general transformation F.
- LSH uses randomly generated projection vectors, an identity F, and zero intercept for mean thresholding.
- Each LSH projection vector is sampled from a zero-mean multivariate Gaussian with identity covariance, defining a separating hyperplane.
- LSH offers probabilistic retrieval within (1 + ε) times optimal similarity with sub-linear query time in n.
- The hashing discussion assumes, without loss of generality, that all data points are centralized to zero mean.
- Random projection hashing requires O(ln n/ε2) vectors, leading to long codewords, large storage, and high computational cost.
- Learning-based methods exploit data-affinity spectral properties, but spectral analysis is usually time consuming.
3 DENSITY SENSITIVE HASHING
Density Sensitive Hashing (DSH) extends LSH by selecting projections according to data geometry rather than randomly. It quantizes data into groups, generates projections between adjacent groups, ranks them by entropy, and uses the top L projections for hashing.
- Core idea: DSH guides projection selection with the data’s geometric structure instead of generating projections randomly.It is presented as an extension of LSH intended to address limitations of both random-projection and learning-based hashing.
- Minimum Distortion Quantization: DSH first uses k-means to partition the data into k groups represented by their center points.The approach may stop k-means after a parameterized number of iterations, usually five, and the group count controls the maximum code length.
- Density Sensitive Projections Generation: For each pair of r-adjacent groups, DSH constructs a separating projection using the median plane between their centers.Groups are r-adjacent when either group belongs to the other’s r nearest-center neighbors.
- Entropy Based Projections Selection: DSH generates around 2αrL candidate projections and selects the top L by entropy to form the L-bit codes.The entropy criterion favors projections that split the data as equally as possible, maximizing the information supplied by each bit.
- Entropy Based Projections Selection: Entropy estimation uses weighted group centers rather than the entire database, significantly reducing the calculation time.Each group center receives a weight based on its group size, and the two center partitions determine the estimated probabilities.
- Computational Complexity Analysis: DSH training scales linearly with the number of database samples, while query compression requires O(Ld), matching LSH’s testing complexity.Under αLr ≪ n, k-means dominates training with complexity O(αLpnd).
4 EXPERIMENT
Experiments on three million-scale datasets compare DSH with random-projection and learning-based hashing methods, assessing retrieval accuracy, efficiency, and parameter sensitivity. DSH generally performs strongly across code lengths, is efficient at testing, and exhibits useful accuracy–efficiency trade-offs in its parameters.
- Compared Algorithms: The evaluation uses GIST1M, Flickr1M, and SIFT1M, each with one million feature vectors, comparing DSH against six state-of-the-art hashing algorithms.Queries are evaluated using Hamming-distance rankings, with true neighbors defined by the closest 2 percentile in the original Euclidean space.
- Retrieval Accuracy: Random-projection methods improve as code length increases, whereas learning-based methods perform well with short codes but often fail to improve substantially with longer codes.PCAH is specifically reported to decrease in performance as code length increases, attributed to later low-variance principal projections producing poorly discriminative codes.
- Retrieval Accuracy: DSH almost outperforms its competitors across code lengths and shows larger improvements on the higher-dimensional GIST1M and Flickr1M datasets.The reported datasets have dimensions 960, 512, and 128 respectively, with the largest gains occurring on the two higher-dimensional datasets.
- Efficiency: DSH is slower to train than random-projection methods but faster than SpH and AGH, while its testing time is among the most efficient.DSH, LSH, and PCAH obtain binary codes through matrix multiplication and thresholding during testing.
- Parameter Selection: 3 k-means iterations are sufficient for reasonably good MAP, while increasing iterations raises both DSH's MAP and learning time.The experiments learn 64-bit codes when studying parameter effects.
- Parameter Selection: α = 1.5 balances accuracy and efficiency, whereas increasing α raises both MAP and learning time; performance remains stable for r < 5 but declines at larger r.Larger r adds projections separating far-away groups, which are described as less critical and redundant.
5 CONCLUSION
The paper concludes that DSH uses data geometry to guide projection selection for high-dimensional nearest-neighbor search. On three large datasets, it scales well with data size and significantly outperforms state-of-the-art hashing methods in retrieval accuracy.
- Conclusion: DSH guides projection selection using the geometric structure of data rather than relying on random projections alone.The authors describe this design as producing hashing codes with more discriminating power.
- Conclusion: Experiments on three large datasets show that DSH scales well to data size and significantly outperforms state-of-the-art hashing methods in retrieval accuracy.