EUVIMEDEUVIMED entdecken
Crossref

Similarity Search in the Blink of an Eye with Compressed Indices

Cecilia Aguerrebere, Ishwar Singh Bhati, Mark Hildebrand, Mariano Tepper, Theodore Willke

Proceedings of the VLDB Endowment · 2023-07 · 16 (11) · 3433-3446

DOI: 10.14778/3611479.3611537 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the VLDB Endowment, online erschienen am 24.08.2023. Verfasst von Cecilia Aguerrebere und 4 weiteren Autor:innen. Die Arbeit wurde bisher 49-mal zitiert (Crossref) und nennt 60 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Nowadays, data is represented by vectors. Retrieving those vectors, among millions and billions, that are similar to a given query is a ubiquitous problem, known as similarity search, of relevance for a wide range of applications. Graph-based indices are currently the best performing techniques for billion-scale similarity search. However, their random-access memory pattern presents challenges to realize their full potential. In this work, we present new techniques and systems for creating faster and smaller graph-based indices. To this end, we introduce a novel vector compression method, Locally-adaptive Vector Quantization (LVQ), that uses per-vector scaling and scalar quantization to improve search performance with fast similarity computations and a reduced effective bandwidth, while decreasing memory footprint and barely impacting accuracy. LVQ, when combined with a new high-performance computing system for graph-based similarity search, establishes the new state of the art in terms of performance and memory footprint. For billions of vectors, LVQ outcompetes the second-best alternatives: (1) in the low-memory regime, by up to 20.7x in throughput with up to a 3x memory footprint reduction, and (2) in the high-throughput regime by 5.8x with 1.4x less memory.

Zitieren

APA

Aguerrebere, C., Bhati, I. S., Hildebrand, M., Tepper, M., & Willke, T. (2023). Similarity Search in the Blink of an Eye with Compressed Indices. Proceedings of the VLDB Endowment, 16(11), 3433-3446. https://doi.org/10.14778/3611479.3611537

Vancouver

Aguerrebere C, Bhati IS, Hildebrand M, Tepper M, Willke T. Similarity Search in the Blink of an Eye with Compressed Indices. Proceedings of the VLDB Endowment. 2023;16(11):3433-3446. doi:10.14778/3611479.3611537

BibTeX
@article{Aguerrebere2023,
  author = {Aguerrebere, Cecilia and Bhati, Ishwar Singh and Hildebrand, Mark and Tepper, Mariano and Willke, Theodore},
  title = {Similarity Search in the Blink of an Eye with Compressed Indices},
  journal = {Proceedings of the VLDB Endowment},
  year = {2023},
  volume = {16},
  number = {11},
  pages = {3433--3446},
  doi = {10.14778/3611479.3611537}
}
Kostenlos starten →