Distance-Sensitive Hashing

Summary: Introduces distance-sensitive hashing (DSH), generalizing LSH to prescribed collision-probability functions; asymmetric hash pairs enable increasing or unimodal CPFs for annulus and output-sensitive queries. Adds privacy-preserving distance estimation and near-tight angular-distance lower bounds. (summarized by gpt-5.6-luna on Jul 26 2026)

Paper ID: 1755
Venue: PODS
Year: 2018
Pagerank: 5.8359922e-05
Overall Rank: 6,583 | 54.84%
DOI: 10.1145/3196959.3196976

Incoming Non-self Citations Over Time

Authors

1. Martin Aumüller (IT University of Copenhagen)
2. Tobias Christiani (IT University of Copenhagen)
3. Rasmus Pagh (IT University of Copenhagen)
4. Francesco Silvestri (University of Padova)

BibTeX Citation

@inproceedings{aumuller_pods18,
        address = {New York, NY, USA},
        series = {{PODS} '18},
        title = {{Distance-Sensitive Hashing}},
        url = {https://dl.acm.org/doi/10.1145/3196959.3196976},
        doi = {10.1145/3196959.3196976},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Aumüller, Martin and Christiani, Tobias and Pagh, Rasmus and Silvestri, Francesco},
        year = {2018}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,623	Fair Near Neighbor Search: Independent Range Sampling in High Dimensions	2020	PODS	7.2463734e-05
5,121	Point-to-Hyperplane Nearest Neighbor Search Beyond the Unit Hypersphere	2021	SIGMOD	6.3577317e-05
10,645	On the Adversarial Robustness of Locality-Sensitive Hashing in Hamming Space	2025	PODS	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 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
244	On the Design and Quantification of Privacy Preserving Data Mining Algorithms	2001	PODS	0.00023476901
2,462	Output-optimal Parallel Algorithms for Similarity Joins	2017	PODS	8.5487602e-05
3,806	On the Complexity of Inner Product Similarity Join	2016	PODS	7.108802e-05
5,666	Smooth Tradeoffs between Insert and Query Complexity in Nearest Neighbor Search	2015	PODS	6.1285141e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,546	PM-LSH: A Fast and Accurate LSH Framework for High-Dimensional Approximate NN Search	2020	VLDB
2	3,389	Intelligent Probing for Locality Sensitive Hashing: Multi-Probe LSH and Beyond	2017	VLDB
3	4,927	Neighbor-Sensitive Hashing	2016	VLDB
4	5,666	Smooth Tradeoffs between Insert and Query Complexity in Nearest Neighbor Search	2015	PODS
5	5,800	DET-LSH: A Locality-Sensitive Hashing Scheme with Dynamic Encoding Tree for Approximate Nearest Neighbor Search	2024	VLDB
6	3,279	Locality-Sensitive Hashing Scheme based on Longest Circular Co-Substring	2020	SIGMOD
7	21	Similarity Search in High Dimensions via Hashing	1999	VLDB
8	332	Query-Aware Locality-Sensitive Hashing for Approximate Nearest Neighbor Search	2016	VLDB
9	369	Locality-Sensitive Hashing Scheme Based on Dynamic Collision Counting	2012	SIGMOD
10	2,673	DSH: Data Sensitive Hashing for High-Dimensional k-NN Search	2014	SIGMOD