Point-to-Hyperplane Nearest Neighbor Search Beyond the Unit Hypersphere

Summary: Introduces an asymmetric transformation enabling provable hyperplane hashing for Point-to-Hyperplane NNS beyond the unit hypersphere. NH and FH deliver sublinear queries; FH adds a data-dependent multi-partition boost, with NH favoring speed and 3–100× gains on real data. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h4fff0c829cd18054
Venue: SIGMOD
Year: 2021
Pagerank: 6.2205593e-05
Overall Rank: 5,222 | 64.91%
DOI: 10.1145/3448016.3457240

Incoming Non-self Citations Over Time

Authors

1. Qiang Huang (National University of Singapore)
2. Yifan Lei (National University of Singapore)
3. Anthony K. H. Tung (National University of Singapore)

BibTeX Citation

@inproceedings{huang_sigmod21,
        title = {{Point-to-Hyperplane Nearest Neighbor Search Beyond the Unit Hypersphere}},
        author = {Huang, Qiang and Lei, Yifan and Tung, Anthony K. H.},
        series = {{SIGMOD} '21},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3448016.3457240},
        url = {https://dl.acm.org/doi/10.1145/3448016.3457240},
        year = {2021}
}

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,230	Chameleon: a Heterogeneous and Disaggregated Accelerator System for Retrieval-Augmented Language Models	2025	VLDB	5.842393e-05
7,098	A New Sparse Data Clustering Method Based On Frequent Items	2023	SIGMOD	5.5991152e-05
8,350	Fast Graph Vector Search via Hardware Acceleration and Delayed-Synchronization Traversal	2025	VLDB	5.3481387e-05
9,681	MQH: Locality Sensitive Hashing on Multi-level Quantization Errors for Point-to-Hyperplane Distances	2023	VLDB	5.1416711e-05
11,658	LARGE: A Length-Aggregation-based Grid Structure for Line Density Visualization	2024	VLDB	4.9769913e-05
11,924	ONe Index for All Kernels (ONIAK): A Zero Re-Indexing LSH Solution to ANNS-ALT (After Linear Transformation)	2022	VLDB	4.9769913e-05
13,679	From Zero to Hero: Detecting Leaked Data through Synthetic Data Injection and Model Querying	2024	VLDB	-

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
45	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB	0.00045027197
297	Query-Aware Locality-Sensitive Hashing for Approximate Nearest Neighbor Search	2016	VLDB	0.00021849337
338	Locality-Sensitive Hashing Scheme Based on Dynamic Collision Counting	2012	SIGMOD	0.00020600264
562	SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index	2015	VLDB	0.00016350316
576	Quality and Efficiency in High Dimensional Nearest Neighbor Search	2009	SIGMOD	0.00016118297
1,325	VHP: Approximate Nearest Neighbor Search via Virtual Hypersphere Partitioning	2020	VLDB	0.00011016872
1,481	PM-LSH: A Fast and Accurate LSH Framework for High-Dimensional Approximate NN Search	2020	VLDB	0.00010535847
1,527	LazyLSH: Approximate Nearest Neighbor Search for Multiple Distance Functions with a Single Index	2016	SIGMOD	0.00010350688
2,444	DeltaPQ: Lossless Product Quantization Code Compression for High Dimensional Similarity Search	2020	VLDB	8.4556406e-05
2,955	Locality-Sensitive Hashing Scheme based on Longest Circular Co-Substring	2020	SIGMOD	7.8111585e-05
6,708	Distance-Sensitive Hashing	2018	PODS	5.7027685e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	20	Similarity Search in High Dimensions via Hashing	1999	VLDB
2	10,574	Efficient Approximate Nearest Neighbor Search via Hemi-Sphere Centroids Graph	2026	SIGMOD
3	1,481	PM-LSH: A Fast and Accurate LSH Framework for High-Dimensional Approximate NN Search	2020	VLDB
4	3,692	Fair Near Neighbor Search: Independent Range Sampling in High Dimensions	2020	PODS
5	4,852	Neighbor-Sensitive Hashing	2016	VLDB
6	2,501	DSH: Data Sensitive Hashing for High-Dimensional k-NN Search	2014	SIGMOD
7	3,546	A General and Efficient Querying Method for Learning to Hash	2018	SIGMOD
8	297	Query-Aware Locality-Sensitive Hashing for Approximate Nearest Neighbor Search	2016	VLDB
9	1,325	VHP: Approximate Nearest Neighbor Search via Virtual Hypersphere Partitioning	2020	VLDB
10	9,681	MQH: Locality Sensitive Hashing on Multi-level Quantization Errors for Point-to-Hyperplane Distances	2023	VLDB