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: 6394
Venue: SIGMOD
Year: 2022
Pagerank: 5.3717005e-05
Overall Rank: 8,791 | 39.69%
DOI: 10.1145/3514221.3517880

Incoming Non-self Citations Over Time

Authors

1. Qiyu Liu (Hong Kong University of Science and Technology)
2. Yanyan Shen (Shanghai Jiao Tong University)
3. Lei Chen (Hong Kong University of Science and Technology)

BibTeX Citation

@inproceedings{liu_sigmod22,
        title = {{HAP: An Efficient Hamming Space Index Based on Augmented Pigeonhole Principle}},
        author = {Liu, Qiyu and Shen, Yanyan and Chen, Lei},
        series = {{SIGMOD} '22},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3514221.3517880},
        url = {https://dl.acm.org/doi/10.1145/3514221.3517880},
        year = {2022}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,709	Why Are Learned Indexes So Effective but Sometimes Ineffective?	2025	VLDB	5.3789739e-05
10,261	LICO: An SIMD-Aware High-Performance Learned Inverted Index Compression Framework	2026	SIGMOD	5.093636e-05
10,944	Not Small Enough? SegPQ: A Learned Approach to Compress Product Quantization Codebooks	2025	VLDB	5.093636e-05
11,059	Cardinality Estimation for Similarity Search on High-Dimensional Data Objects: The Impact of Reference Objects	2025	VLDB	5.093636e-05
11,447	A Two-Level Signature Scheme for Stable Set Similarity Joins	2023	VLDB	5.093636e-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.0020210012
43	The Case for Learned Index Structures	2018	SIGMOD	0.00046060254
84	Learned Cardinalities: Estimating Correlated Joins with Deep Learning	2019	CIDR	0.00035838391
323	DeepDB: Learn from Data, not from Queries!	2020	VLDB	0.00021264788
401	Deep Unsupervised Cardinality Estimation	2020	VLDB	0.00019092557
477	The PGM-index: a fully-dynamic compressed learned index with provable worst-case bounds	2020	VLDB	0.00017851226
873	Learning Multi-dimensional Indexes	2020	SIGMOD	0.00013481915
1,061	Are We Ready For Learned Cardinality Estimation?	2021	VLDB	0.00012369764
1,108	Approximate Query Processing: No Silver Bullet	2017	SIGMOD	0.00012145154
1,174	Tsunami: A Learned Multi-dimensional Index for Correlated Data and Skewed Workloads	2021	VLDB	0.00011817414
3,474	An Efficient Partition Based Method for Exact Set Similarity Joins	2016	VLDB	7.3859271e-05
3,865	The Case for a Learned Sorting Algorithm	2020	SIGMOD	7.0621718e-05
4,073	Stable Learned Bloom Filters for Data Streams	2020	VLDB	6.9242783e-05
4,617	Learned Cardinality Estimation for Similarity Queries	2021	SIGMOD	6.604437e-05
5,011	Monotonic Cardinality Estimation of Similarity Selection: A Deep Learning Approach	2020	SIGMOD	6.4020848e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,011	Monotonic Cardinality Estimation of Similarity Selection: A Deep Learning Approach	2020	SIGMOD
2	3,310	Similarity Query Processing for High-Dimensional Data	2020	VLDB
3	9,918	HAKES: Scalable Vector Database for Embedding Search Service	2025	VLDB
4	705	HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces	2018	VLDB
5	10,233	Enhancing Graph-based Approximate Maximum Inner Product Search via Norm-Adaptive Partitioning	2026	SIGMOD
6	1,934	Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces	2023	VLDB
7	21	Similarity Search in High Dimensions via Hashing	1999	VLDB
8	9,052	Fast Approximate Similarity Join in Vector Databases	2025	SIGMOD
9	7,942	Efficient and Tunable Similar Set Retrieval	2001	SIGMOD
10	3,858	A General and Efficient Querying Method for Learning to Hash	2018	SIGMOD