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
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 changed | Where | Measured | Effect |
|---|---|---|---|
| use farthest point sorting instead of spatial sort as insertion order (ablation) | Query Table NNS · Dragon (3D model) | comparisons per query: 240.15 -> 162.68 | Improved |
| use farthest point sorting insertion order (ablation) | Query Table NNS · Dragon (3D model) | average query list length: 16.371 -> 14.197 | Improved |
| use farthest point sorting insertion order (ablation) | Query Table NNS · Dragon (3D model) | average query time (us): 0.343 -> 0.213 | Improved |
| use farthest point sorting insertion order (ablation) | Query Table NNS · Dragon (3D model) | preprocessing time (s): 0.249 -> 0.466 | Hurt |
| replace KD-tree with Query Table NNS inside P2M | P2M point-to-mesh · Dragon mesh | query time (us): 0.854 -> 0.342 | Improved |
| replace Ex-DPC++ delta computation with Query Table NNS | density peak clustering · syn-2d (serial) | clustering time (s): 4.974 -> 0.715 | Improved |
| replace Ex-DPC++ delta computation with Query Table NNS (OpenMP) | density peak clustering · syn-2d (omp) | clustering time (s): 0.927 -> 0.559 | Improved |
| replace nanoflann KD-tree with Query Table NNS in PCL ICP | ICP registration · 3DMatch (8 scenes) | registration time: faster in 82.4% of cases | Improved |
| use Query Table NNS instead of KD-tree on uniform data with queries in same bounds | Query Table NNS · uniform point clouds | query time | No clear effect |
| enlarge query region beyond target bounding box for uniform data | Query Table NNS vs KD-tree · uniform point clouds (1M) | query time | Improved |
| use Query Table NNS instead of KD-tree for far queries | Query Table NNS · Dragon (1M, 2x bounding box) | query time: 1.585 -> 0.213 | Improved |
| use Query Table NNS instead of farthest point sampling specialist QuickFPS | farthest point sampling · Dragon 25% sampling | sampling time (s): 0.087 -> 0.142 | Hurt |
Closest papers by meaning
- Graph-Based Algorithms for Diverse Similarity Search (ICML 2025 · similarity 0.90)
- Navigable Graphs for High-Dimensional Nearest Neighbor Search: Constructions and Limits (NeurIPS 2024 · similarity 0.87)
- Distance Adaptive Beam Search for Provably Accurate Graph-Based Nearest Neighbor Search (NeurIPS 2025 · similarity 0.87)
- Discovering Data Structures: Nearest Neighbor Search and Beyond (NeurIPS 2025 · similarity 0.87)
- MCGI: Manifold-Consistent Graph Indexing for Billion-Scale Disk-Resident Vector Search (NeurIPS 2026 · similarity 0.86)
- CSPG: Crossing Sparse Proximity Graphs for Approximate Nearest Neighbor Search (NeurIPS 2024 · similarity 0.86)
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.
