TRIM: Accelerating High-Dimensional Vector Similarity Search with Enhanced Triangle-Inequality-Based Pruning

Summary: TRIM enhances triangle‑inequality lower‑bound pruning for high‑dimensional vector search via optimized landmark selection and tunable bound relaxation to combat distance concentration. Pluggable into graph/quantization/disk indexes (HNSW, IVFPQ, DiskANN), yields massive reductions in distance/I/O (up to 99% pruning, 90–200% speedups, up to 58% I/O cut) while maintaining accuracy. (summarized by gpt-5-mini on Feb 11 2026)

Paper ID: 7624
Venue: SIGMOD
Year: 2026
Pagerank: 5.093636e-05
Overall Rank: 10,412 | 28.57%
DOI: 10.1145/3769838

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Yitong Song (Hong Kong Baptist University; Shanghai Jiao Tong University)
2. Pengcheng Zhang (Shanghai Jiao Tong University)
3. Chao Gao (Zilliz)
4. Bin Yao (Shanghai Jiao Tong University)
5. Kai Wang (Shanghai Jiao Tong University)
6. Zongyuan Wu (Alibaba)
7. Lin Qu (Taobao)

BibTeX Citation

@inproceedings{song_sigmod26,
        title = {{TRIM: Accelerating High-Dimensional Vector Similarity Search with Enhanced Triangle-Inequality-Based Pruning}},
        author = {Song, Yitong and Zhang, Pengcheng and Gao, Chao and Yao, Bin and Wang, Kai and Wu, Zongyuan and Qu, Lin},
        series = {{SIGMOD} '26},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3769838},
        url = {https://dl.acm.org/doi/10.1145/3769838},
        year = {2026}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,201	Balancing Global and Local: Representative Sampling for Large-Scale Vector Data	2026	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 22 of 22 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
56	M-tree: An Efficient Access Method for Similarity Search in Metric Spaces	1997	VLDB	0.00040719947
93	Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph	2019	VLDB	0.00034701237
286	Milvus: A Purpose-Built Vector Data Management System	2021	SIGMOD	0.00022357911
332	Query-Aware Locality-Sensitive Hashing for Approximate Nearest Neighbor Search	2016	VLDB	0.00020920444
406	AnalyticDB-V: A Hybrid Analytical Engine Towards Query Fusion for Structured and Unstructured Data	2020	VLDB	0.00019054532
580	SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index	2015	VLDB	0.00016157635
805	Cache locality is not enough: High-Performance Nearest Neighbor Search with Product Quantization Fast Scan	2016	VLDB	0.00013891999
926	Improving Approximate Nearest Neighbor Search through Learned Adaptive Early Termination	2020	SIGMOD	0.00013181732
1,244	Efficient Approximate Nearest Neighbor Search in Multi-dimensional Databases	2023	SIGMOD	0.00011508159
1,357	RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search	2024	SIGMOD	0.00011043994
1,735	High-Dimensional Approximate Nearest Neighbor Search: with Reliable and Efficient Distance Comparison Operations	2023	SIGMOD	9.9004924e-05
1,760	Starling: An I/O-Efficient Disk-Resident Graph Index Framework for High-Dimensional Vector Similarity Search on Data Segment	2024	SIGMOD	9.8157819e-05
1,802	HVS: Hierarchical Graph Structure Based on Voronoi Diagrams for Solving Approximate Nearest Neighbor Search	2022	VLDB	9.7284341e-05
1,934	Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces	2023	VLDB	9.4561907e-05
2,010	iDEC: Indexable Distance Estimating Codes for Approximate Nearest Neighbor Search	2020	VLDB	9.3085202e-05
2,137	Efficient Processing of k Nearest Neighbor Joins using MapReduce	2012	VLDB	9.110238e-05
2,303	SeRF: Segment Graph for Range-Filtering Approximate Nearest Neighbor Search	2024	SIGMOD	8.7783079e-05
2,519	Similarity search in the blink of an eye with compressed indices	2023	VLDB	8.4741476e-05
3,108	Practical and Asymptotically Optimal Quantization of High-Dimensional Vectors in Euclidean Space for Approximate Nearest Neighbor Search	2025	SIGMOD	7.7499741e-05
3,858	A General and Efficient Querying Method for Learning to Hash	2018	SIGMOD	7.067591e-05
6,133	Efficient Data-aware Distance Comparison Operations for High-Dimensional Approximate Nearest Neighbor Search	2025	VLDB	5.9654376e-05
6,650	Tribase: A Vector Data Query Engine for Reliable and Lossless Pruning Compression using Triangle Inequalities	2025	SIGMOD	5.8146324e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,851	Maximum Inner Product is Query-Scaled Nearest Neighbor	2025	VLDB
2	2,519	Similarity search in the blink of an eye with compressed indices	2023	VLDB
3	3,265	New Trends in High-D Vector Similarity Search: AI-driven, Progressive, and Distributed	2021	VLDB
4	3,108	Practical and Asymptotically Optimal Quantization of High-Dimensional Vectors in Euclidean Space for Approximate Nearest Neighbor Search	2025	SIGMOD
5	8,655	A Non-Linear Dimensionality-Reduction Technique for Fast Similarity Search in Large Databases	2006	SIGMOD
6	46	A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces	1998	VLDB
7	13,294	TRIM: An Efficient Framework for Exact Eccentricity Computation on Large-Scale Graphs	2026	VLDB
8	10,336	Accelerating High-Dimensional ANN Search via Skipping Redundant Distance Computations	2026	SIGMOD
9	10,227	Efficient Index Layout and Search Strategy for Large-scale High-dimensional Vector Similarity Search	2026	SIGMOD
10	6,650	Tribase: A Vector Data Query Engine for Reliable and Lossless Pruning Compression using Triangle Inequalities	2025	SIGMOD