Bidirectionally Densifying LSH Sketches with Empty Bins
Summary: BiDens: bidirectional densification for LSH sketches, filling empty bins from non-empty bins forward/backward while preserving the LSH property. Theory and experiments report up to 10^6× faster runs with equal or better accuracy for similarity estimation, fast search, and kernel linearization on real data. (summarized by gpt-5-nano on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Peng Jia (Xi'an Jiaotong University)
- 2. Pinghui Wang (Shenzhen University; Xi'an Jiaotong University)
- 3. Junzhou Zhao (Xi'an Jiaotong University)
- 4. Shuo Zhang (Xi'an Jiaotong University)
- 5. Yiyan Qi (Xi'an Jiaotong University)
- 6. Min Hu (China Mobile)
- 7. Chao Deng (China Mobile)
- 8. Xiaohong Guan (Shenzhen University; Tsinghua University; Xi'an Jiaotong University)
BibTeX Citation
@inproceedings{jia_sigmod21,
title = {{Bidirectionally Densifying LSH Sketches with Empty Bins}},
author = {Jia, Peng and Wang, Pinghui and Zhao, Junzhou and Zhang, Shuo and Qi, Yiyan and Hu, Min and Deng, Chao and Guan, Xiaohong},
series = {{SIGMOD} '21},
booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
publisher = {Association for Computing Machinery},
doi = {10.1145/3448016.3452833},
url = {https://dl.acm.org/doi/10.1145/3448016.3452833},
year = {2021}
}Incoming Citations (Sorted by Pagerank)
Showing 2 of 2 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 7,498 | Stingy Sketch: A Sketch Framework for Accurate and Fast Frequency Estimation | 2022 | VLDB | 5.6031077e-05 |
| 7,716 | Double-Anonymous Sketch: Achieving Top-K-fairness for Finding Global Top-K Frequent Items | 2023 | SIGMOD | 5.5605526e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 2 of 2 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 21 | Similarity Search in High Dimensions via Hashing | 1999 | VLDB | 0.00056760516 |
| 2,010 | iDEC: Indexable Distance Estimating Codes for Approximate Nearest Neighbor Search | 2020 | VLDB | 9.3085202e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 3,389 | Intelligent Probing for Locality Sensitive Hashing: Multi-Probe LSH and Beyond | 2017 | VLDB |
| 2 | 5,666 | Smooth Tradeoffs between Insert and Query Complexity in Nearest Neighbor Search | 2015 | PODS |
| 3 | 4,857 | Similarity Join Size Estimation using Locality Sensitive Hashing | 2011 | VLDB |
| 4 | 4,927 | Neighbor-Sensitive Hashing | 2016 | VLDB |
| 5 | 5,800 | DET-LSH: A Locality-Sensitive Hashing Scheme with Dynamic Encoding Tree for Approximate Nearest Neighbor Search | 2024 | VLDB |
| 6 | 287 | Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search | 2007 | VLDB |
| 7 | 2,673 | DSH: Data Sensitive Hashing for High-Dimensional k-NN Search | 2014 | SIGMOD |
| 8 | 369 | Locality-Sensitive Hashing Scheme Based on Dynamic Collision Counting | 2012 | SIGMOD |
| 9 | 2,390 | Streaming Similarity Search over one Billion Tweets using Parallel Locality-Sensitive Hashing | 2013 | VLDB |
| 10 | 991 | Bayesian Locality Sensitive Hashing for Fast Similarity Search | 2012 | VLDB |