2016/02/21 by Ping Li, Michael Mitzenmacher, Li, Ping +3 · 1 citation
Computer Science · Mathematics · #Advanced Image and Video Retrieval Techniques #Algorithm #Algorithms and Data Compression #Computer science #Data Structures and Algorithms (cs.DS) #Data mining #Estimator #FOS: Computer and information sciences #Hash function #Hash table #Image Retrieval and Classification Techniques #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Mathematics #Nearest neighbor search #Random projection #Statistics #Theoretical computer science #cs.DS #cs.LG #stat.ML
paper · pdf · doi:10.48550/arxiv.1602.06577
published in arXiv (Cornell University) (Cornell University) · arXiv admin note: text overlap with arXiv:1403.8144
arxiv created 2016/02/21 · openalex publication_date 2016/02/21 · arxiv updated 2016/02/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/06
The method of random projections has become a standard tool for machine learning, data mining, and search with massive data at Web scale. The effective use of random projections requires efficient coding schemes for quantizing (real-valued) projected data into integers. In this paper, we focus on a simple 2-bit coding scheme. In particular, we develop accurate nonlinear estimators of data similarity based on the 2-bit strategy. This work will have important practical applications. For example, in the task of near neighbor search, a crucial step (often called re-ranking) is to compute or estimate data similarities once a set of candidate data points have been identified by hash table techniques. This re-ranking step can take advantage of the proposed coding scheme and estimator. As a related task, in this paper, we also study a simple uniform quantization scheme for the purpose of building hash tables with projected data. Our analysis shows that typically only a small number of bits are needed. For example, when the target similarity level is high, 2 or 3 bits might be sufficient. When the target similarity level is not so high, it is preferable to use only 1 or 2 bits. Therefore, a 2-bit scheme appears to be overall a good choice for the task of sublinear time approximate near neighbor search via hash tables. Combining these results, we conclude that 2-bit random projections should be recommended for approximate near neighbor search and similarity estimation. Extensive experimental results are provided.