AI Paper Atlas

Research map / Learning theory and algorithms / Prediction and decision losses

Efficient Nearest Neighbor Search Using Dynamic Programming

Pengfei Wang, Jiantao Song, Shiqing Xin, Shuangmin Chen, Changhe Tu, Wenping Wang, Jiaye Wang

TPAMI 2025 · Learning theory and algorithms › Prediction and decision losses · approach: Approximate nearest neighbor indexing · 13 citations (OpenAlex)

Read the paperCheck your idea against 137,217 papers

AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Measured effects reported in the paper

What was changedWhereMeasuredEffect
use farthest point sorting instead of spatial sort as insertion order (ablation)Query Table NNS · Dragon (3D model)comparisons per query: 240.15 -> 162.68Improved
use farthest point sorting insertion order (ablation)Query Table NNS · Dragon (3D model)average query list length: 16.371 -> 14.197Improved
use farthest point sorting insertion order (ablation)Query Table NNS · Dragon (3D model)average query time (us): 0.343 -> 0.213Improved
use farthest point sorting insertion order (ablation)Query Table NNS · Dragon (3D model)preprocessing time (s): 0.249 -> 0.466Hurt
replace KD-tree with Query Table NNS inside P2MP2M point-to-mesh · Dragon meshquery time (us): 0.854 -> 0.342Improved
replace Ex-DPC++ delta computation with Query Table NNSdensity peak clustering · syn-2d (serial)clustering time (s): 4.974 -> 0.715Improved
replace Ex-DPC++ delta computation with Query Table NNS (OpenMP)density peak clustering · syn-2d (omp)clustering time (s): 0.927 -> 0.559Improved
replace nanoflann KD-tree with Query Table NNS in PCL ICPICP registration · 3DMatch (8 scenes)registration time: faster in 82.4% of casesImproved
use Query Table NNS instead of KD-tree on uniform data with queries in same boundsQuery Table NNS · uniform point cloudsquery timeNo clear effect
enlarge query region beyond target bounding box for uniform dataQuery Table NNS vs KD-tree · uniform point clouds (1M)query timeImproved
use Query Table NNS instead of KD-tree for far queriesQuery Table NNS · Dragon (1M, 2x bounding box)query time: 1.585 -> 0.213Improved
use Query Table NNS instead of farthest point sampling specialist QuickFPSfarthest point sampling · Dragon 25% samplingsampling time (s): 0.087 -> 0.142Hurt

Closest papers by meaning

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.

Open scime draft

Get the next scime Dispatch and a monthly field update

Free. We send a confirmation link first; every email has a one-click unsubscribe. Privacy