GTS

Type: Research paper / GPU-based index structure
Category: Research Papers & Surveys
Tags: similarity-search, ANN, gpu-acceleration

GTS is a GPU-based tree index for fast similarity search in general metric spaces, aimed at high-dimensional vector and other complex data types. It is designed to support high-throughput, concurrent similarity queries where only a distance function is available, and to be integrated into high-performance (approximate) nearest-neighbor and vector database systems.

Key Concepts

• Domain: Similarity search in general metric spaces (not limited to Euclidean/coordinate data).
• Goal: Accelerate similarity search where distance computation is expensive and coordinate-based acceleration is not available.
• Hardware focus: GPU-based parallel index and query processing.
• Use cases: Multimedia retrieval, decision-making systems, visualization recommendation, bioinformatics and omics data, text and sequence data, social media / online commercial databases.

Features

Index Structure

• GPU-based tree index (GTS):
  • Designed specifically for similarity search in general metric spaces.
  • Operates only on a distance metric; does not require explicit coordinates.
• Pivot-based tree structure:
  • Uses pivots (reference objects) to organize data.
  • Enables effective pruning of candidate objects during search.
• List-table organization:
  • Employs list tables to structure data and index information for GPU-friendly access patterns.
  • Optimizes memory coalescing and parallel computation on GPUs.

Query Processing & Parallelism

• Concurrent similarity search:
  • Supports many similarity queries executing in parallel on GPU.
  • Tailored to meet high-throughput data management requirements.
• Two-stage search method:
  • Batch processing stage: Groups multiple queries to exploit GPU parallelism and amortize computation.
  • Sequential (or follow-up) stage: Handles remaining work to better utilize limited GPU memory and handle large query loads.
  • Combined strategy balances throughput and memory constraints.
• General metric support:
  • Works with arbitrary distance functions (e.g., cosine distance, edit distance, domain-specific metrics) as long as metric properties hold.

Update & Maintenance

• Streaming data updates:
  • Supports incremental updates to the index as new data arrives in a streaming fashion.
• Batch data updates:
  • Provides efficient mechanisms for bulk updates or reorganization when large sets of data change.
• Cost-effective updates for dynamic datasets:
  • Targets use cases like social media and online commercial databases where data changes frequently.

Performance Modeling

• Cost model for search performance:
  • The paper presents a cost model to estimate or analyze the performance of similarity search using GTS.
  • Helps guide parameter tuning and system design/integration.

Experimental Results (as reported)

• Datasets: Evaluated on five real-world datasets.
• Efficiency vs CPU baselines:
  • Reported speedups up to two orders of magnitude over existing CPU-based methods.
• Efficiency vs GPU baselines:
  • Reported up to 20× efficiency improvement over state-of-the-art GPU-based similarity search methods.

Applications

• High-dimensional vector search and ANN index within vector databases.
• General-purpose similarity search in metric spaces for:
  • Multimedia and image retrieval.
  • Text and document similarity (e.g., cosine distance).
  • Biological sequence comparison (e.g., edit distance for DNA strings).
  • Heterogeneous cancer omics and other scientific data.
  • Dynamic, large-scale social and commercial datasets needing frequent updates.

Pricing

• Not applicable (research paper / algorithm; no pricing information provided).

Source

• Paper: "GTS" – GPU-based tree index for similarity search in metric spaces
• URL: https://arxiv.org/html/2404.00966v1