HAP: An Efficient Hamming Space Index Based on Augmented Pigeonhole Principle

Summary: Relax disjoint partitioning of binary vectors by allowing dimension redundancy to form Augmented Pigeonhole Principle (APP) for tighter Hamming pruning. HAP combines APP, SimCardNet, PLA-Elias-Fano compression, and batch optimization to support Hamming range and k-NN with improved space/time efficiency on large binary DBs. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 6332
Venue: SIGMOD
Year: 2022
Pagerank: 4.4761716e-05
Overall Rank: 8,650 | 39.83%
DOI: 10.1145/3514221.3517880

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
9,746	Why Are Learned Indexes So Effective but Sometimes Ineffective?	2025	VLDB	4.2897489e-05
10,698	Not Small Enough? SegPQ: A Learned Approach to Compress Product Quantization Codebooks	2025	VLDB	4.1945683e-05
10,833	Cardinality Estimation for Similarity Search on High-Dimensional Data Objects: The Impact of Reference Objects	2025	VLDB	4.1945683e-05
11,247	A Two-Level Signature Scheme for Stable Set Similarity Joins	2023	VLDB	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 15 of 15 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
2	R-Trees: A Dynamic Index Structure For Spatial Searching	1984	SIGMOD	0.0032169493
102	The Case for Learned Index Structures	2018	SIGMOD	0.00049545203
204	Learned Cardinalities: Estimating Correlated Joins with Deep Learning	2019	CIDR	0.00034784455
608	DeepDB: Learn from Data, not from Queries!	2020	VLDB	0.00019235898
758	Deep Unsupervised Cardinality Estimation	2020	VLDB	0.0001706608
857	The PGM-index: a fully-dynamic compressed learned index with provable worst-case bounds	2020	VLDB	0.00015882892
1,478	Learning Multi-dimensional Indexes	2020	SIGMOD	0.00011762542
1,574	Approximate Query Processing: No Silver Bullet	2017	SIGMOD	0.00011287495
1,703	Are We Ready For Learned Cardinality Estimation?	2021	VLDB	0.00010836769
1,889	Tsunami: A Learned Multi-dimensional Index for Correlated Data and Skewed Workloads	2021	VLDB	0.00010200865
4,050	An Efficient Partition Based Method for Exact Set Similarity Joins	2016	VLDB	6.4953612e-05
4,097	The Case for a Learned Sorting Algorithm	2020	SIGMOD	6.4551616e-05
4,446	Stable Learned Bloom Filters for Data Streams	2020	VLDB	6.1800659e-05
5,469	Learned Cardinality Estimation for Similarity Queries	2021	SIGMOD	5.4898192e-05
5,622	Monotonic Cardinality Estimation of Similarity Selection: A Deep Learning Approach	2020	SIGMOD	5.4060403e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
3,609	Similarity search in the blink of an eye with compressed indices	2023	VLDB	6.9215236e-05
5,622	Monotonic Cardinality Estimation of Similarity Selection: A Deep Learning Approach	2020	SIGMOD	5.4060403e-05
4,278	Similarity Query Processing for High-Dimensional Data	2020	VLDB	6.2953764e-05
10,654	HAKES: Scalable Vector Database for Embedding Search Service	2025	VLDB	4.1945683e-05
1,010	HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces	2018	VLDB	0.00014652858
2,971	Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces	2023	VLDB	7.7970531e-05
34	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00076637636
8,899	Fast Approximate Similarity Join in Vector Databases	2025	SIGMOD	4.427232e-05
7,522	Efficient and Tunable Similar Set Retrieval	2001	SIGMOD	4.7180617e-05
4,609	A General and Efficient Querying Method for Learning to Hash	2018	SIGMOD	6.0528541e-05