Approximate Similarity Search for Online Multimedia Services on Distributed CPU-GPU Platforms

George Teodoro, Eduardo Valle, Nathan Mariano, Ricardo da Silva Torres, Wagner Meira Jr., Joel H. Saltz

In the era of massive image and video databases, finding similar objects within a query is akin to locating a needle in a high-dimensional haystack that grows by the second. Traditional indexing methods often fail as dimensionality increases, leading to the "curse of dimensionality." To address this, George Teodoro and colleagues introduced Hypercurves, a distributed framework designed to make high-dimensional similarity search fast and responsive by balancing workloads across hybrid CPU-GPU clusters.

Similarity search—finding objects in a database closest to a query—is fundamental to services like image recognition and copyright detection. However, two primary hurdles exist:

  1. Computational Complexity: As feature vectors increase in dimensions, traditional indexing becomes prohibitively expensive.
  2. Latency vs. Throughput: Online services face "bursty" traffic. While GPUs excel at high-throughput batch processing, they can increase latency for individual queries if the system waits too long to form a batch.

Hypercurves addresses these by utilizing the parallel power of GPUs without sacrificing the quick response times required for real-time online services.

The Hypercurves Framework

Hypercurves is built upon the Multicurves sequential indexing method and the Anthill distributed runtime. The core of the strategy involves mapping high-dimensional data onto a one-dimensional line using fractal space-filling curves.

A Hilbert space-filling curve mapping 2D points to a 1D sequence, preserving spatial locality.

By using curves like the Hilbert or Z-order curve, the system can employ standard, fast 1D indexing structures while largely preserving the "neighborhood" relationships of the original data. The search is split into a hybrid pipeline: the CPU handles initial candidate retrieval from the index, while the GPU performs the heavy Euclidean distance calculations for the k-nearest neighbor (kNN) search.

Evolution of Hilbert (left) and Z-order (right) curves through increasing fractal orders.

To maximize efficiency, the system employs a double-buffering scheme, allowing the CPU to prepare the next batch of queries while the GPU processes the current one.

Dynamic Scheduling with DTAHE

The "secret sauce" of Hypercurves is the Dynamic Task Assigner (DTAHE). This greedy scheduling algorithm monitors the system in real-time. If the GPU is saturated or the query load is low, DTAHE intelligently routes kNN tasks back to idle CPU cores. This allows the system to pivot dynamically: under low load, it behaves like a low-latency CPU system; under high load, it transforms into a high-throughput GPU powerhouse.

Performance and Scalability

The researchers evaluated Hypercurves using a massive dataset of over 130 million SIFT feature vectors (128 dimensions each). Key findings include:

  • Significant Speedup: The hybrid CPU-GPU implementation achieved up to a 30x performance improvement over a single-core CPU version.
  • Latency Reduction: DTAHE reduced average query response times by 52% to 81% compared to the best possible static configurations.
  • Superlinear Scalability: In distributed tests, the system showed superlinear speedups. As the database is partitioned across more nodes, local indices become small enough to fit into faster CPU cache levels, boosting performance beyond simple linear scaling.
  • High Capacity: An 8-node cluster was capable of processing roughly 646 million queries per day, demonstrating the framework's ability to support world-scale multimedia services at a relatively low hardware cost.

Conclusion

Hypercurves demonstrates that approximate similarity search can be both highly accurate and extremely fast on distributed heterogeneous platforms. While the original research utilized older GPU architectures, the underlying principles of dynamic task assignment and space-filling curve indexing remain highly relevant for modern multimedia retrieval systems. Future work may explore integrating newer indexing strategies like HNSW or leveraging specialized hardware like Tensor Cores to further push the boundaries of real-time search.

Summary updated

BibTeX
@article{teodoro2014approximate,
  author = {George Teodoro and Eduardo Valle and Nathan Mariano and Ricardo da Silva Torres and Wagner Meira Jr. and Joel H. Saltz},
  title = {{Approximate Similarity Search for Online Multimedia Services on Distributed CPU-GPU Platforms}},
  journal = {VLDB J.},
  year = {2014},
  doi = {10.1007/s00778-013-0329-7},
}
Figure