Publication Type
Journal Article
Version
acceptedVersion
Publication Date
6-2024
Abstract
Similarity search, the task of identifying objects most similar to a given query object under a specific metric, has gathered significant attention due to its practical applications. However, the absence of coordinate information to accelerate similarity search and the high computational cost of measuring object similarity hinder the efficiency of existing CPU-based methods. Additionally, these methods struggle to meet the demand for high throughput data management. To address these challenges, we propose GTS, a GPU-based tree index designed for the parallel processing of similarity search in general metric spaces, where only the distance metric for measuring object similarity is known. The GTS index utilizes a pivot-based tree structure to efficiently prune objects and employs list tables to facilitate GPU computing. To efficiently manage concurrent similarity queries with limited GPU memory, we have developed a two-stage search method that combines batch processing and sequential strategies to optimize memory usage. The paper also introduces an effective update strategy for the proposed GPU-based index, encompassing streaming data updates and batch data updates. Additionally, we present a cost model to evaluate search performance. Extensive experiments on five real-life datasets demonstrate that GTS achieves efficiency gains of up to two orders of magnitude over existing CPU baselines and up to 20x efficiency improvements compared to state-of-the-art GPU-based methods.
Keywords
Metric Space, Concurrent Similarity Search, GPU-based Index
Discipline
Databases and Information Systems | Numerical Analysis and Scientific Computing
Research Areas
Data Science and Engineering
Areas of Excellence
Digital transformation
Publication
Proceedings of the ACM on Management of Data
Volume
2
Issue
3
First Page
1
Last Page
27
ISSN
2836-6573
Identifier
10.1145/3654945
Publisher
Association for Computing Machinery (ACM)
Citation
ZHU, Yifan; MA, Ruiyao; ZHENG, Baihua; KE, Xiangyu; CHEN, Lu; and GAO, Yunjun.
GTS: GPU-based Tree Index for Fast Similarity Search. (2024). Proceedings of the ACM on Management of Data. 2, (3), 1-27.
Available at: https://ink.library.smu.edu.sg/sis_research/9041
Copyright Owner and License
Authors CC-BY
Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.
Additional URL
https://doi.org/10.1145/3654945
Included in
Databases and Information Systems Commons, Numerical Analysis and Scientific Computing Commons
Comments
Accepted by SIGMOD 2024