Similarity Search in the Blink of an Eye with Compressed Indices
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.
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}
}
EUVIMED