DSH: Data Sensitive Hashing for High-Dimensional k-NN Search

Summary: DSH: Data Sensitive Hashing for high-dimensional k-NN search leverages data distributions to balance buckets and preserve NN relations. The method offers guarantees and remains orthogonal to indexing strategies, with practical efficiency on non-uniform data. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h8d4333ecbe26e837
Venue: SIGMOD
Year: 2014
Pagerank: 8.3779738e-05
Overall Rank: 2,505 | 83.16%
DOI: 10.1145/2588555.2588565

Incoming Non-self Citations Over Time

Authors

1. Jinyang Gao (National University of Singapore)
2. H. V. Jagadish (University of Michigan)
3. Wei Lu (National University of Singapore)
4. Beng Chin Ooi (National University of Singapore)

BibTeX Citation

@inproceedings{gao_sigmod14,
        title = {{DSH: Data Sensitive Hashing for High-Dimensional k-NN Search}},
        author = {Gao, Jinyang and Jagadish, H. V. and Lu, Wei and Ooi, Beng Chin},
        series = {{SIGMOD} '14},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/2588555.2588565},
        url = {https://dl.acm.org/doi/10.1145/2588555.2588565},
        year = {2014}
}

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
74	Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph	2019	VLDB	0.00037091678
839	Improving Approximate Nearest Neighbor Search through Learned Adaptive Early Termination	2020	SIGMOD	0.00013547412
1,328	VHP: Approximate Nearest Neighbor Search via Virtual Hypersphere Partitioning	2020	VLDB	0.00011003106
1,530	LazyLSH: Approximate Nearest Neighbor Search for Multiple Distance Functions with a Single Index	2016	SIGMOD	0.00010344205
4,856	Neighbor-Sensitive Hashing	2016	VLDB	6.3798143e-05
8,998	ANN Softmax: Acceleration of Extreme Classification Training	2022	VLDB	5.2400492e-05
10,745	Balancing the Blend: An Experimental Analysis of Trade-offs in Hybrid Search	2026	VLDB	4.9793485e-05
10,868	CONDA: A Connectivity-Aware Dynamic Index for Approximate Nearest Neighbor Search over Evolving Data	2026	VLDB	4.9793485e-05
12,150	Top-k Queries over Digital Traces	2019	SIGMOD	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
20	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00057568153
45	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB	0.0004503446
280	Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search	2007	VLDB	0.0002230467
338	Locality-Sensitive Hashing Scheme Based on Dynamic Collision Counting	2012	SIGMOD	0.00020585187
576	Quality and Efficiency in High Dimensional Nearest Neighbor Search	2009	SIGMOD	0.00016121388
992	Bayesian Locality Sensitive Hashing for Fast Similarity Search	2012	VLDB	0.00012646771
3,016	Indexing the Distance: An Efficient Method to KNN Processing	2001	VLDB	7.7483267e-05
5,982	Query-Sensitive Embeddings	2005	SIGMOD	5.9276742e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,796	Smooth Tradeoffs between Insert and Query Complexity in Nearest Neighbor Search	2015	PODS
2	2,969	Locality-Sensitive Hashing Scheme based on Longest Circular Co-Substring	2020	SIGMOD
3	298	Query-Aware Locality-Sensitive Hashing for Approximate Nearest Neighbor Search	2016	VLDB
4	1,485	PM-LSH: A Fast and Accurate LSH Framework for High-Dimensional Approximate NN Search	2020	VLDB
5	20	Similarity Search in High Dimensions via Hashing	1999	VLDB
6	9,674	MQH: Locality Sensitive Hashing on Multi-level Quantization Errors for Point-to-Hyperplane Distances	2023	VLDB
7	338	Locality-Sensitive Hashing Scheme Based on Dynamic Collision Counting	2012	SIGMOD
8	5,527	DET-LSH: A Locality-Sensitive Hashing Scheme with Dynamic Encoding Tree for Approximate Nearest Neighbor Search	2024	VLDB
9	4,856	Neighbor-Sensitive Hashing	2016	VLDB
10	6,704	Distance-Sensitive Hashing	2018	PODS