EUVIMEDEUVIMED entdecken
Crossref

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

Yitong Song, Pengcheng Zhang, Chao Gao, Bin Yao, Kai Wang, Zongyuan Wu, Lin Qu

Proceedings of the ACM on Management of Data · 04.12.2025 · 3 (6) · 1-26

DOI: 10.1145/3769838 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 05.12.2025. Verfasst von Yitong Song und 6 weiteren Autor:innen. Die Arbeit wurde bisher 3-mal zitiert (Crossref) und nennt 66 Literaturangaben. Gefördert von: Oceanic Interdisciplinary Program of Shanghai Jiao Tong University, Alibaba Innovative Research (AIR) Program.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

High-dimensional vector similarity search (HVSS) is critical for many data processing and AI applications. However, traditional HVSS methods often require extensive data access for distance calculations, leading to inefficiencies. Triangle-inequality-based lower bound pruning is a widely used technique to reduce the number of data access in low-dimensional spaces but becomes less effective in high-dimensional settings. This is attributed to the ''distance concentration'' phenomenon, where the lower bounds derived from the triangle inequality become too small to be useful. To address this, we propose TRIM, which enhances the effectiveness of traditional triangle-inequality-based pruning in high-dimensional vector similarity search using two key ways: (1) optimizing landmark vectors used to form the triangles, and (2) relaxing the lower bounds derived from the triangle inequality, with the relaxation degree adjustable according to user's needs. TRIM is a versatile operation that can be seamlessly integrated into both memory-based (e.g., HNSW, IVFPQ) and disk-based (e.g., DiskANN) HVSS methods, reducing distance calculations and disk access. Extensive experiments show that TRIM enhances memory-based methods, improving graph-based search by up to 90% and quantization-based search by up to 200%, while achieving a pruning ratio of up to 99%. It also reduces I/O costs by up to 58% and improves efficiency by 102% for disk-based methods, while preserving high query accuracy. Our source code is available at https://github.com/petrizhang/TRIM.

Förderung

  • Oceanic Interdisciplinary Program of Shanghai Jiao Tong University
  • Alibaba Innovative Research (AIR) Program

Zitieren

APA

Song, Y., Zhang, P., Gao, C., Yao, B., Wang, K., Wu, Z., & Qu, L. (2025). TRIM: Accelerating High-Dimensional Vector Similarity Search with Enhanced Triangle-Inequality-Based Pruning. Proceedings of the ACM on Management of Data, 3(6), 1-26. https://doi.org/10.1145/3769838

Vancouver

Song Y, Zhang P, Gao C, Yao B, Wang K, Wu Z, et al. TRIM: Accelerating High-Dimensional Vector Similarity Search with Enhanced Triangle-Inequality-Based Pruning. Proceedings of the ACM on Management of Data. 2025;3(6):1-26. doi:10.1145/3769838

BibTeX
@article{Song2025,
  author = {Song, Yitong and Zhang, Pengcheng and Gao, Chao and Yao, Bin and Wang, Kai and Wu, Zongyuan and Qu, Lin},
  title = {TRIM: Accelerating High-Dimensional Vector Similarity Search with Enhanced Triangle-Inequality-Based Pruning},
  journal = {Proceedings of the ACM on Management of Data},
  year = {2025},
  volume = {3},
  number = {6},
  pages = {1--26},
  doi = {10.1145/3769838}
}
Kostenlos starten →