Pith. sign in

REVIEW 11 cited by

Analysis of approximate nearest neighbor searching with clustered point sets

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv cs/9901013 v1 pith:QBT7Q3M4 submitted 1999-01-26 cs.CG

Songrit Maneewongvatana , David M. Mount This is my paper · ORCID
classification cs.CG
keywords datanearestneighboranalysisapproximatekd-treemethodpoints
verification ladder T0 review T1 audit T2 compute T3 formal

Signed reviews

No signed human review yet.

0 comments
read the original 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.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 11 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Excitons in Large Disordered Boron-Nitride Layer using Linear-Scaling Bethe-Salpeter Simulations

    cond-mat.mtrl-sci 2026-06 unverdicted novelty 7.0 of 10

    A new real-space linear-scaling Bethe-Salpeter framework with sublattice-resolved decoupling and Kernel Polynomial Method enables O(N) excitonic absorption spectra for Anderson-disordered hBN, showing asymmetric broad...

  2. Stellar flare morphology with TESS across the main sequence

    astro-ph.SR 2024-12 conditional novelty 7.0 of 10

    Stellar flare shapes vary systematically with spectral type, with hotter stars showing broader peaks and faster late decay, visible only when averaging thousands of flares.

  3. TACTIC: Tactile and Vision Conditioned Contact-Centric Control for Whole-Arm Manipulation

    cs.RO 2026-07 conditional novelty 6.5 of 10

    A hybrid contact-centric MPC with tactile-vision latents and Jacobian-biased sampling outperforms pure learned and pure kinematic baselines on multi-contact whole-arm tasks in sim and on a manikin/maze robot.

  4. Tomographer: End-to-end Redshift Distribution Estimation for Source Catalogs and Intensity Maps

    astro-ph.CO 2026-08 conditional novelty 6.0 of 10

    Tomographer recovers bias-weighted redshift distributions b(z)dN/dz or b(z)dI/dz from source catalogs or intensity maps in minutes, using precomputed activation maps instead of user-side pair counting.

  5. Automated Erythrocyte Detection and Tracking for Retinal Blood Flow Quantification in Erythrocyte-Mediated Angiography

    cs.CV 2026-05 unverdicted novelty 6.0 of 10

    EMTrack framework with flow-context detection and topology-aware tracking outperforms baselines on the new RBF-EMA dataset for erythrocyte detection, tracking, and retinal blood flow quantification.

  6. An Orbital House of Cards: Frequent Satellite Close Conjunctions

    astro-ph.EP 2025-12 conditional novelty 6.0 of 10

    The CRASH Clock, the expected time between potentially catastrophic close approaches if satellite maneuvers stop, is 5.5 days as of June 2025 versus 164 days in 2018.

  7. TensorTouch: Calibration of Tactile Sensors for High Resolution Stress Tensor and Deformation for Dexterous Manipulation

    cs.RO 2025-06 conditional novelty 6.0 of 10

    TensorTouch converts optical tactile sensor images into dense stress tensor, deformation, and contact force fields using finite-element simulation and a hierarchical vision transformer, and uses these fields for selec...

  8. Parametric Matrix Models for Emulation in Nuclear and Many-Body Physics

    nucl-th 2026-08 conditional novelty 5.0 of 10

    Parametric matrix models learn small matrix representations of expensive parametric physics models from data, preserving the algebraic form of the equations while avoiding explicit projection bases.

  9. Measuring Distortion in the Empty Regions of Dimensionality Reduction Scatterplots with the Gap Index

    cs.LG 2026-07 conditional novelty 5.0 of 10

    The Gap Index quantifies visual distortion in empty regions of DR scatterplots via Delaunay triangle area deformation and is more sensitive to salient gap artifacts than stress or trustworthiness.

  10. A Pan-STARRS Search for Distant Planets: Part 1

    astro-ph.EP 2025-06 conditional novelty 5.0 of 10

    A catalog-level injection calibration of Pan-STARRS1 recovers 692 Kuiper Belt objects and constrains Planet Nine's remaining sky area to the galactic plane.

  11. SciPy 1.0--Fundamental Algorithms for Scientific Computing in Python

    cs.MS 2019-07 accept novelty 2.0 of 10

    SciPy 1.0 documents a mature open-source library that has become the de facto standard for scientific algorithms in Python with broad adoption across research projects.

Pith tools