Efficient Image Similarity Search with Quadtrees (Student Abstract)

Yifan Zhang, Jeff HeflinAAAI 2025 · DOI

TL;DR

This paper introduces a novel quadtree-based approach for efficient image similarity search, significantly speeding up retrieval times by organizing high-dimensional image data into a spatial structure. By integrating this quadtree indexing with traditional information retrieval systems, the method offers a scalable solution that balances retrieval speed with reasonable accuracy.

What Problem Does This Paper Address?

Finding similar images within large datasets is a computationally intensive task. Traditional methods like pairwise comparisons or K-Nearest Neighbors (KNN) become impractical as datasets grow due to their high computational cost. While recent advancements have focused on dimensionality reduction and Approximate Nearest Neighbor (ANN) techniques to improve speed, these often come with trade-offs in accuracy and storage, and critically, they lack seamless integration with existing information retrieval (IR) systems that handle both image and metadata searches. This paper aims to bridge this gap by proposing a method that is both scalable and integrates well with IR systems.

Methods

The core of the proposed method involves representing images as 2D vectors and then organizing these vectors using a quadtree data structure.

  1. Image Representation: Images are first converted into meaningful vectors using pre-trained embedding models (like those trained on ImageNet). These high-dimensional vectors are then projected into a 2D space using dimensionality reduction techniques, with UMAP being found to be particularly effective for minimizing information loss.
  2. Quadtree Construction: The 2D image representations are organized into a quadtree. This spatial data structure recursively subdivides the 2D space. Each node in the quadtree represents a region, and as more images are added, nodes split into four child nodes to accommodate them, effectively grouping similar images together in leaf nodes.
  3. IR Integration with Quadtree Paths: A novel "tag scheme" is introduced where each image is assigned a quadtree path. This path acts as an additional field in an IR system's inverted index, recording the route from the quadtree root to the leaf node containing the image. This allows for indexing and searching based on image location within the quadtree structure.
  4. Querying Strategies: Two strategies are proposed for finding the n most similar images:
  5. Window-based search: Dynamically adjusts a search window around the query point in the 2D space, expanding it if necessary to find enough relevant images.
  6. Distance-based search: Recursively explores the quadtree, prioritizing nodes closer to the query image and balancing accuracy with retrieval speed.

Datasets

The experiments were conducted on datasets of varying sizes: 30K, 50K, and 70K images. These images were sourced from the Materials Project database. The paper does not mention introducing any new benchmarks.

Key Insights and Ideas

  • Quadtrees for Scalability: The hierarchical and recursive nature of quadtrees is a natural fit for organizing spatial data, making it highly effective for reducing the search space in large image datasets.
  • IR Integration is Crucial: The ability to integrate image search with existing IR systems (handling metadata) is a significant advantage, offering a more unified search experience. The quadtree path indexing is the key enabler here.
  • Speed vs. Accuracy Trade-off: While the quadtree methods achieve dramatic speedups, there is a noticeable, though acceptable, reduction in ranking accuracy compared to methods operating in the full embedding space. This highlights the practical engineering challenge of balancing performance metrics.
  • UMAP's Effectiveness: The choice of UMAP for dimensionality reduction is highlighted as crucial for preserving meaningful relationships between image embeddings in the 2D space, which is essential for the quadtree's effectiveness.

Key Results

The proposed quadtree-based methods (QT Distance and QT Window) demonstrated remarkable improvements in retrieval speed. For a dataset of 70K images, queries consistently took only 8-10 seconds, a significant reduction compared to traditional methods.

  • Speedup: Achieved a 24.67x speed improvement over Pairwise 2D and a 147x improvement over Pairwise Full.
  • Accuracy: While accuracy was reduced, the quadtree models performed reasonably well. QT Distance achieved NDCG scores between 0.61 and 0.64, and QT Window ranged from 0.56 to 0.58. The accuracy reduction compared to Pairwise 2D was approximately 20.78%.
  • Scalability: The retrieval time remained nearly constant regardless of dataset size, a key advantage over methods whose performance degrades linearly with data volume.

Limitations and Future Work

Limitations: * The paper acknowledges a reduction in accuracy (around 20%) compared to methods operating in the full embedding space. * The quadtree path generation assumes a maximum tree depth, which might require adjustments for extremely large or dense datasets.

Future Work: * The authors plan to further improve retrieval performance while maintaining speed. * A promising direction is exploring the use of octrees (3D quadtrees) to map images to 3D space, potentially mitigating some of the information loss incurred during 2D dimension reduction.

Summary updated

BibTeX
@inproceedings{zhang2025efficient,
  author = {Yifan Zhang and Jeff Heflin},
  title = {{Efficient Image Similarity Search with Quadtrees (Student Abstract)}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.1609/aaai.v39i28.35324},
}
Figure