Distributed high-dimensional index creation using Hadoop, HDFS and C++

Gylfi Þór Gudmundsson, Laurent Amsaleg, Björn Þór Jónsson

TL;DR

This paper explores using Hadoop and HDFS to accelerate the creation of high-dimensional indices, a critical but computationally expensive step in large-scale multimedia retrieval. By connecting existing C++ indexing code to Hadoop, they demonstrate significant speedups, highlighting the challenges and benefits of distributed computing for this task.

What Problem Does This Paper Address?

Modern Content-Based Image Retrieval Systems (CBIRS) are capable of handling massive datasets, often millions or even billions of descriptors. While searching these datasets has become remarkably fast, the process of creating the high-dimensional index itself remains a significant bottleneck. This index construction phase is computationally intensive, requiring extensive I/O operations and CPU cycles for distance calculations. For datasets on the order of terabytes, indexing can take days or weeks. This paper addresses this challenge by investigating how to parallelize and distribute this index creation process using the Hadoop framework.

Methods

The authors leverage the Hadoop MapReduce framework and its distributed file system, HDFS, to parallelize the index creation process. Their approach involves connecting their existing C++ implementation of the "extended Cluster Pruning" (eCP) algorithm to Hadoop, rather than a full reimplementation in Java. This decision was driven by the desire to evaluate Hadoop's viability for their specific use case and to gain practical experience with the framework without a complete rewrite.

The eCP algorithm's index creation is broken down into three phases:

  1. Phase #1: Creation of the index tree: Cluster representatives are picked and organized into a tree. This phase is kept centralized to ensure consistency across distributed nodes.
  2. Phase #2: Vector assignment: Vectors are assigned to clusters in rounds, creating temporary sorted files. This phase is identified as the prime candidate for parallelization due to its high CPU and I/O demands.
  3. Phase #3: Merging sorted files: Temporary files are merged into a single final index file. This phase is primarily I/O intensive.

The authors focus on distributing Phase #2, while Phase #3 is handled as a separate post-processing step outside of Hadoop. They also discuss several practical challenges encountered when integrating C++ code with Hadoop, including reading binary data, handling HDFS block sizes, and the implications of not having implicit sorting within the MapReduce pipeline.

Datasets

The paper uses a custom dataset consisting of 100,000 random images downloaded from Flickr. These images were resized to 512 pixels on their longest edge, and SIFT local descriptors were computed. This resulted in over 110 million 128-dimensional vectors, totaling approximately 13.6 GB of data.

Key Insights and Ideas

  • Bridging the C++/Java Divide: Connecting existing, highly optimized C++ code to Hadoop, rather than a full Java reimplementation, can offer significant performance gains while mitigating development effort. However, this approach introduces practical challenges.
  • Hadoop's Suitability for I/O-Intensive Tasks: While MapReduce is often associated with CPU-bound tasks, this paper demonstrates its effectiveness in accelerating I/O-bound index creation by distributing the workload.
  • Networking as a Bottleneck: As CPU and I/O bottlenecks are addressed by distributed computing, network topology and usage become critical factors. Inefficient network communication can negate the benefits of parallelization.
  • Task Granularity Matters: For tasks involving a fixed overhead (like building an in-memory index tree), larger Map tasks can be more efficient than many small ones to amortize this overhead.
  • Replication Trade-offs: Increasing HDFS replication can reduce disk competition and improve read performance, but gains plateau when the network becomes saturated.

Key Results

  • Substantial Speedups: The most striking result is the dramatic reduction in index creation time. A baseline run on a single machine took approximately 8 hours. When distributed across 40 CPUs using Hadoop, this time was reduced to about 20 minutes (a 4.1% ratio of the baseline). Further optimization with 118 CPUs on 62 machines achieved an index creation time of less than 8 minutes (1.6% of the baseline).
  • Effect of Replication: Increasing the HDFS replication factor from 1 to 10 reduced the index creation time from 25 minutes to about 10 minutes, demonstrating the benefit of reduced disk contention.
  • Optimal Task Completion: By forcing all indexing tasks to complete around the same time, they achieved an index build time of 27 minutes on 13 machines (5.7% of the baseline), close to the theoretical optimum.

Limitations and Future Work

  • C++ Integration Challenges: The paper highlights several practical issues with integrating C++ code into Hadoop, including the lack of a direct interface for reading binary data, which necessitates workarounds that can impact performance (e.g., by limiting HDFS's ability to schedule tasks locally).
  • Suboptimal Parallelism: In some experiments, uneven task distribution across machines led to suboptimal speedups, indicating that careful resource management and task scheduling are crucial.
  • Future Work - Java Reimplementation: The authors strongly suggest that a full reimplementation of the index creation algorithm in Java would likely yield even better performance gains by fully leveraging Hadoop's features.
  • Future Work - Networking Optimization: Further investigation into optimizing network topology and minimizing message exchanges is recommended to overcome the network bottleneck.

Summary updated

Abstract

This paper describes an initial study where the open-source Hadoop parallel and distributed run-time environment is used to speedup the construction phase of a large high-dimensional index. This paper first discusses the typical practical problems developers may run into when porting their code to Hadoop. It then presents early experimental results showing that the performance gains are substantial when indexing large data sets.
BibTeX
@inproceedings{gudmundsson2012distributed,
  author = {Gylfi Þór Gudmundsson and Laurent Amsaleg and Björn Þór Jónsson},
  title = {{Distributed high-dimensional index creation using Hadoop, HDFS and C++}},
  booktitle = {CBMI},
  year = {2012},
  url = {https://openreview.net/forum?id=doh_yzdxwcW},
}
Figure