  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.
