Research map / Architectures and efficiency / Neural architecture search
Efficient Image Similarity Search with Quadtrees (Student Abstract)
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a quadtree-based image similarity search method over UMAP-projected 2D embeddings, integrated with an IR inverted index via quadtree path tags, and reports large speedups over pairwise and KNN search on 70K materials microscopy images.
Problem
Image similarity search over large datasets is computationally expensive with pairwise or KNN methods, and existing ANN approaches are hard to integrate with traditional IR systems that support combined image and metadata search.
Approach
Organize UMAP-projected 2D image embeddings in a quadtree, tag each image with its quadtree path as an indexable IR field, and retrieve top-n similar images by searching candidate quadtree regions via either a window-based or a distance-based strategy.
Key results
- QT Distance achieves NDCG 0.61-0.64 and QT Window 0.56-0.58 against Pairwise Full reference, with query times of about 8-10 s for 1000 queries.
- Pairwise Full takes 528-1247 s for 1000 queries across 30K-70K images, versus about 8.5 s for quadtree methods, a 147x speedup over Pairwise Full.
- Quadtree methods give a 24.67x speedup over Pairwise 2D with roughly 20% lower ranking accuracy (NDCG).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use QT Distance instead of Pairwise Full | Image similarity search · 70K images | Time (seconds): 1246.77 -> 8.46 | Helped |
| Use QT Distance instead of Pairwise Full | Image similarity search · 70K images | Mean NDCG: 1 -> 0.62 | Hurt |
| Use QT Window instead of Pairwise Full | Image similarity search · 70K images | Time (seconds): 1246.77 -> 10.35 | Helped |
| Use QT Window instead of Pairwise Full | Image similarity search · 70K images | Mean NDCG: 1 -> 0.57 | Hurt |
| Use QT Distance instead of Pairwise 2D | Image similarity search · 30K images | Time (seconds): 89.58 -> 8.44 | Helped |
| Use QT Distance instead of Pairwise 2D | Image similarity search · 30K images | Mean NDCG: 0.76 -> 0.65 | Hurt |
| Use QT Distance rather than QT Window | Quadtree image search · 30K images | Mean NDCG: 0.56 -> 0.65 | Helped |
| Use QT Distance rather than QT Window | Quadtree image search · 30K images | Time (seconds): 8.44 -> 8.44 | No clear effect |
Surprising findings
- KNN Full achieves NDCG 0.92 (median) yet quadtree methods score much lower (0.56-0.64), indicating a notable accuracy trade-off.
Limitations
- Accuracy drops relative to Pairwise 2D and KNN Full (NDCG roughly 0.56-0.64 vs 0.92 for KNN Full).
- Evaluated on a single materials microscopy dataset with one embedding model.
- Dimensionality reduction to 2D loses information, which the authors note as a source of error.
Experimental setup
Datasets: Materials Project images (30K, 50K, 70K subsets)
Benchmarks: Materials Project image subsets (30K, 50K, 70K)
Metrics: NDCG (median and mean) total query time in seconds
Baselines: Pairwise Full Pairwise 2D KNN Full
Builds on: UMAP NDCG
Closest papers by meaning
- Instance-Level Composed Image Retrieval (NeurIPS 2025 · similarity 0.82)
- D3still: Decoupled Differential Distillation for Asymmetric Image Retrieval (CVPR 2024 · similarity 0.80)
- MagicLens: Self-Supervised Image Retrieval with Open-Ended Instructions (ICML 2024 · similarity 0.80)
- ILIAS: Instance-Level Image retrieval At Scale (CVPR 2025 · similarity 0.80)
- QuRe: Query-Relevant Retrieval through Hard Negative Sampling in Composed Image Retrieval (ICML 2025 · similarity 0.80)
- Learning with Noisy Triplet Correspondence for Composed Image Retrieval (CVPR 2025 · similarity 0.80)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.