Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Experiment Videos

BoostMap: an embedding method for efficient nearest neighbor retrieval.

Vassilis Athitsos1, Jonathan Alon, Stan Sclaroff

  • 1Computer Science and Engineering Department, University of Texas, Arlingtton, TX 76019, USA. athitsos@uta.edu

IEEE Transactions on Pattern Analysis and Machine Intelligence
|November 15, 2007
PubMed
Summary
This summary is machine-generated.

Related Concept Videos

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

Video Frame Interpolation With Many-to-Many Splatting and Spatial Selective Refinement.

IEEE transactions on pattern analysis and machine intelligence·2023
Same author

Leveraging Geometric Structure for Label-Efficient Semi-Supervised Scene Segmentation.

IEEE transactions on image processing : a publication of the IEEE Signal Processing Society·2022
Same author

Guided Zoom: Zooming into Network Evidence to Refine Fine-Grained Model Decisions.

IEEE transactions on pattern analysis and machine intelligence·2021
Same author

Revisiting Image-Language Networks for Open-Ended Phrase Detection.

IEEE transactions on pattern analysis and machine intelligence·2020
Same author

Hashing with Mutual Information.

IEEE transactions on pattern analysis and machine intelligence·2019
Same author

Scale and Rotation Invariant Matching Using Linearly Augmented Trees.

IEEE transactions on pattern analysis and machine intelligence·2015
Same journal

Relation DETR+: Exploring Explicit Position Relation Prior for Dense Prediction.

IEEE transactions on pattern analysis and machine intelligence·2026
Same journal

RBF++: Quantifying and Optimizing Reasoning Boundaries across Measurable and Unmeasurable Capabilities for Chain-of-Thought Reasoning.

IEEE transactions on pattern analysis and machine intelligence·2026
Same journal

CAFE: Cross-View Adaptive Fusion and Cluster Center Enhancement for Robust Multi-View Clustering.

IEEE transactions on pattern analysis and machine intelligence·2026
Same journal

DIVER: Reinforced Diffusion Breaks Imitation Bottlenecks in End-to-End Autonomous Driving.

IEEE transactions on pattern analysis and machine intelligence·2026
Same journal

Ethics-Aware Safe Reinforcement Learning for Rare-Event Risk Control in Interactive Urban Driving.

IEEE transactions on pattern analysis and machine intelligence·2026
Same journal

Learning Shape Anchors for Holistic Indoor Scene Understanding.

IEEE transactions on pattern analysis and machine intelligence·2026
See all related articles

BoostMap efficiently retrieves nearest neighbors using computationally expensive distance measures by embedding data into a vector space. This method significantly outperforms existing techniques, improving retrieval efficiency with minimal accuracy loss.

Area of Science:

  • Computer Science
  • Machine Learning
  • Data Mining

Background:

  • Nearest neighbor retrieval is crucial for many data analysis tasks.
  • Computationally expensive distance measures pose significant challenges for efficient retrieval.
  • Existing methods like Lipschitz embeddings, FastMap, and VP-trees have limitations.

Purpose of the Study:

  • To introduce BoostMap, a novel method for efficient nearest neighbor retrieval.
  • To address the challenge of computationally expensive distance measures.
  • To improve retrieval efficiency while maintaining high accuracy.

Main Methods:

  • Objects are embedded into a vector space for efficient distance calculation.
  • Embeddings act as classifiers predicting relative distances between objects.

Related Experiment Videos

  • BoostMap frames embedding construction as a boosting problem, combining weak classifiers into a strong one.

    • Main Results:

    • BoostMap significantly enhances retrieval efficiency across diverse datasets (hand images, digits, time series).
    • The method demonstrates small accuracy losses compared to brute-force search.
    • BoostMap outperforms established nearest neighbor retrieval techniques.

    Conclusions:

    • BoostMap offers an effective solution for efficient nearest neighbor search with complex distance metrics.
    • The method's optimization criterion is applicable in both metric and non-metric spaces.
    • BoostMap represents a significant advancement in nearest neighbor retrieval technology.