Search research articles

Search research articles

Related Experiment Videos

K-nearest neighbor finding using MaxNearestDist.

¹Computer Science Department, Center for Automation Research, University of Maryland, College Park, MD 20742-3275, USA. hjs@cs.umd.edu

IEEE Transactions on Pattern Analysis and Machine Intelligence

|December 18, 2007

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

Visualizing multilayer spatiotemporal epidemiological data with animated geocircles.

Journal of the American Medical Informatics Association : JAMIA·2024

Same author

An efficient region expansion algorithm for regular triangulated meshes.

Pattern recognition letters·2023

Same author

Archimedes, an archive of medical images.

AMIA ... Annual Symposium proceedings. AMIA Symposium·2007

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

ABOUT JoVE

Overview Leadership Blog JoVE Help Center

AUTHORS

Publishing Process Editorial Board Scope & Policies Peer Review FAQ Submit

LIBRARIANS

Testimonials Subscriptions Access Resources Library Advisory Board FAQ

RESEARCH

JoVE Journal Methods Collections JoVE Encyclopedia of Experiments Archive

EDUCATION

JoVE Core JoVE Business JoVE Science Education JoVE Lab Manual Faculty Resource Center Faculty Site

Terms & Conditions of Use

This study introduces MaxNearestDist, an upper bound pruning technique for k-nearest neighbor search. It enhances both depth-first and best-first algorithms, potentially reducing execution time and storage needs in hierarchical clustering.

Area of Science:

Computer Science
Data Mining
Machine Learning

Background:

Similarity searching is crucial for data analysis, often involving finding k-nearest neighbors.
Existing k-nearest neighbor algorithms use hierarchical clustering and a MinDist lower bound for pruning.
MinDist pruning can be inefficient, leading to suboptimal search performance.

Purpose of the Study:

To introduce and adapt the MaxNearestDist upper bound for k-nearest neighbor search.
To enhance the efficiency of depth-first and best-first k-nearest neighbor algorithms.
To overcome the limitations of traditional MinDist pruning techniques.

Main Methods:

Developed an adaptation of the MaxNearestDist upper bound for k-nearest neighbor (k>1) search.
Modified both depth-first and best-first k-nearest neighbor algorithms to incorporate MaxNearestDist.

Related Experiment Videos

Evaluated the impact of MaxNearestDist on cluster examination and priority queue storage.

Main Results:

MaxNearestDist enhances both depth-first and best-first k-nearest neighbor algorithms.
For depth-first search, MaxNearestDist does not increase the number of examined clusters, potentially reducing execution time.
For best-first search, MaxNearestDist does not increase priority queue size, potentially reducing storage requirements.

Conclusions:

The MaxNearestDist upper bound offers a significant improvement for k-nearest neighbor search in hierarchical clustering.
This technique provides a valuable alternative to MinDist pruning, enhancing algorithm efficiency.
The adapted MaxNearestDist is effective in optimizing both time and space complexity for nearest neighbor queries.