Analysis of approximate nearest neighbor searching with clustered point sets

Abstract

We present an empirical analysis of data structures for approximate nearest neighbor searching. We compare the well-known optimized kd-tree splitting method against two alternative splitting methods. The first, called the sliding-midpoint method, which attempts to balance the goals of producing subdivision cells of bounded aspect ratio, while not producing any empty cells. The second, called the minimum-ambiguity method is a query-based approach. In addition to the data points, it is also given a training set of query points for preprocessing. It employs a simple greedy algorithm to select the splitting plane that minimizes the average amount of ambiguity in the choice of the nearest neighbor for the training points. We provide an empirical analysis comparing these two methods against the optimized kd-tree construction for a number of synthetically generated data and query sets. We demonstrate that for clustered data and query sets, these algorithms can provide significant improvements over the standard kd-tree construction for approximate nearest neighbor searching.

20 pages, 8 figures. Presented at ALENEX '99, Baltimore, MD, Jan 15-16, 1999

Cited by in corpus (10)

• The effect of AGN feedback on the halo mass function
• The Origin of Faint Tidal Features Around Galaxies in the RESOLVE Survey
• Lessons from the curious case of the `fastest' star in Gaia DR2
• An accelerated hybrid data-driven/model-based approach for poroelasticity problems with multi-fidelity multi-physics data
• A Generic and Efficient E-field Parallel Imaging Correlator for Next-Generation Radio Telescopes
• Spectral Energy Distributions of Candidate Periodically-Variable Quasars: Testing the Binary Black Hole Hypothesis
• NanoNET: an extendable Python framework for semi-empirical tight-binding models
• PowerBin: Fast Adaptive Data Binning with Centroidal Power Diagrams
• 3D Human Texture Estimation from a Single Image with Transformers
• Efficient Spatial Nearest Neighbor Queries Based on Multi-layer Voronoi Diagrams