Pith. sign in

REVIEW 2 major objections 5 minor 1 cited by

Parallel $k$d-tree with Batch Updates

T0 review · 2 major / 5 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper claims that a single kd-tree can be built, batch-updated, and queried in parallel with near-optimal cache behavior and polylogarithmic span, using sampled splitters and local rebuilds to stay weight-balanced.

desk verdict Strong practical and algorithmic contribution, but the theoretical guarantees need an extra assumption for duplicate-heavy inputs. read the letter →

arxiv 2411.09275 v2 pith:AZT5MCJR submitted 2024-11-14 cs.DS cs.DBcs.DCcs.PF

Ziyang Men , Zheqi Shen , Yan Gu , Yihan Sun This is my paper · ORCID
classification cs.DScs.DBcs.DCcs.PF MSC 68P0568W1068W40
keywords kd-treeparallelalgorithmsbatchupdatescachecomplexityweight-balancedtreerandomsamplingnearestneighborsearchrangequeries
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper sets out to show that the kd-tree's three traditional weaknesses—slow construction, expensive updates, and weak parallelism—can be solved in one structure rather than traded against each other. It proposes the Pkd-tree, a parallel in-memory kd-tree built from randomly sampled splitters and cache-efficient sieving, kept dynamic by tolerating a tunable amount of subtree imbalance and rebuilding only the subtrees that drift out of bounds. The paper proves that construction runs in optimal $O(n \log n)$ work and sorting-level cache complexity with polylogarithmic span, and that batch insertions and deletions of up to $O(n)$ points cost $O(\log^2 n)$ amortized work per element with $O(\log^2 n)$ span, and calls the result the first kd-tree that is highly performant, parallel, and dynamic. It also reports that on billion-point synthetic and real-world datasets, the Pkd-tree is consistently faster than existing parallel kd-tree implementations at construction and updates, with competitive or better query times. If the claims hold, applications can keep one dynamic kd-tree instead of paying the query penalty of the logarithmic method's multiple trees.

What carries the argument

The load-bearing object is the skeleton-and-sieving construction. A skeleton is the first $\lambda$ levels of the tree, built on $2^\lambda \sigma$ samples small enough to fit in cache; its $2^\lambda$ external nodes are buckets. The sieving step divides the input into chunks of size $2^\lambda$, counts how many points of each chunk fall in each bucket, takes a column-major prefix sum to obtain offsets, and writes every point directly to its bucket's slot—one round of data movement per $\lambda$ levels. Updates reuse the same sieve to drop batch points into the relevant buckets; any subtree that would leave the weight-balance window $[0.5-\alpha, 0.5+\alpha]$ of its parent is rebuilt with the construction routine. The parameter $\alpha$ is the dial between update frequency and tree quality.

What would settle it

Construct an initially empty Pkd-tree and apply a thousand batches drawn from a single dense cluster, or from points sharing one coordinate, recording the cumulative size of rebuilt subtrees and the final tree height. If the cumulative rebuild size is superlinear in the final tree size, or the height exceeds the predicted $O(\log n)$ bound, the sampling-balance guarantee behind the amortized update bounds has failed.

Watch

Extended reading notes

Core claim

The central claim is that a kd-tree can be made simultaneously parallel, cache-efficient, and dynamic by replacing exact median splits with sample-based approximate splits and by replacing global rebalancing with lazy local rebuilds. The Pkd-tree fixes $\lambda$ levels of splitters at a time from $2^\lambda \sigma$ random samples, sieves all points into the resulting $2^\lambda$ buckets in one round of data movement, and recurses; updates sieve the batch through the existing skeleton and rebuild exactly the subtrees whose child sizes leave $(1/2 \pm \alpha)$ of the parent. Theorem 3.3 states construction of $n$ points has $O(n \log n)$ work and $O((n/B)\log_M n)$ cache complexity with $O(M^\epsilon \log_M n)$ span, all with high probability; Theorem 4.1 states batch updates of size $m = O(n)$ have $O(\log^2 n)$ span with high probability and amortized $O(\log^2 n)$ work and $O(\log(n/m) + (\log n \log_M n)/B)$ cache per element. The reported experiments on up to $1.3 \times 10^9$ points show construction and updates orders of magnitude faster than the tested parallel kd-tree implementations, with queries at parity or better, and the paper's stated conclusion is that the Pkd-tree is the first kd-tree that is highly performant, parallel, and dynamic.

Load-bearing premise

The load-bearing premise is that the random samples used to pick splitters are representative enough that every rebuilt subtree lands inside $(1/2 \pm \alpha/4)$ of its parent with high probability, so a constant fraction $\Theta(\alpha)$ of its points must change before another rebuild is triggered; this representativeness is asserted rather than proven for adversarial or duplicate-heavy batch inputs.

Editorial extensions

If this is right

  • A single kd-tree can be dynamic without paying the query overhead of the logarithmic method's $O(\log n)$ trees.
  • Construction matches the sorting lower bound in work and cache, so no comparison-based multidimensional index built by splitting can be asymptotically faster.
  • Standard static kd-tree query algorithms (k-NN, range report, range count) work unchanged, so existing query optimizations transfer directly.
  • Batch updates of up to $O(n)$ points remain highly parallel, with amortized polylogarithmic work per element and near-sorting cache cost.
  • Relaxing balance to a constant $\alpha$ buys large constant-factor speedups in practice; choosing $\alpha = O(1/\log n)$ recovers the classical $\log n + O(1)$ height bound when theory demands it.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the sampling guarantee is robust in practice, the same skeleton-and-sieve construction could be ported to external memory or GPU by tuning $\lambda$ to the device's memory hierarchy; the paper's $\lambda = 6$ choice suggests the technique is not tied to one cache size.
  • The amortized analysis assumes updates spread across subtrees; a batch sequence that repeatedly refills one dense region could trigger rebuilds before enough amortized work accumulates. That case deserves stress-testing beyond the printed skewed-data experiments.
  • The no-bounding-box design trades query pruning for memory and build speed, and the paper's own measurements show the trade reverses in high dimensions, so a hybrid that stores boxes above some dimension is a natural extension.
  • Range count, which only the Pkd-tree supports among the tested implementations, makes the structure useful for aggregate analytics where reporting points is unnecessary.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 5 minor

Summary. The paper proposes the Pkd-tree, a parallel in-memory kd-tree with sampling-based multi-level construction, a sieving step for cache-efficient data movement, and lazy weight-balanced partial rebuilds for batch insertions and deletions. The authors claim optimal O(n log n) work and O(Sort(n)) cache complexity for construction with polylogarithmic span (Theorems 3.3 and 3.4), and amortized O(log^2 n) work per updated element with O(log(n/m) + (log n log_M n)/B) cache cost for batch updates (Theorem 4.1). They support these claims with a C++ implementation, extensive experiments on synthetic and real-world datasets up to 1.3 billion points, and comparisons against CGAL, ParGeo's Log-tree and BHL-tree, Boost R-tree, and Zd-tree.

Significance. If the theoretical bounds hold, the paper is a substantial contribution: it would be the first parallel dynamic kd-tree with simultaneously optimal work and cache complexity for construction and polylogarithmic span, and the engineering results are convincing on their face. The paper deserves credit for releasing its code, for the breadth of experiments (including real-world datasets, out-of-distribution queries, cache-miss profiling, and an ablation of the two construction techniques), and for the concrete algorithmic ideas of sampling-based skeleton construction and sieving. The main concern is that a central lemma used to justify both the height bound and the update amortization does not account for tied coordinates, so the universal form of the theoretical claims is not established. That issue is fixable by adding an explicit general-position assumption or a tie-robust analysis, but it must be addressed before the theorems can be accepted as stated.

major comments (2)
  1. [§3.2 (Lemma 3.1) and §4.3 / Appendix B] Lemma 3.1's proof silently assumes a strict ordering in the splitting dimension. The set Λ is defined as the smallest (1/2 − ε/4)n′ points, and the bad event is 'more than s/2 samples fall in Λ.' With ties, this event does not track the actual left child: in the sieving step all points with coordinate equal to the splitter are sent to the right. For an input where 90% of the points share coordinate c in the chosen splitting dimension and the remaining 10% are strictly larger, the sample median is c with probability 1 − o(1), so the left child has size 0 (or, with a splitter chosen between c and the next coordinate, size about 0.9n). Either outcome violates the promised (1/2 ± ε/4)n′ balance range for every ε used in the paper. The heavy-leaf mechanism in Appendix C covers only nodes whose points are all duplicates, so it does not repair the balance guarantee for a large-but-not-total tie. Since Lemma 3.1 is used both for the O(log n) height claim (Lemma 3.2) and for the amortized Θ(α n′) rebuild interval in Theorem 4.1 / Appendix B, the claimed bounds are not universal for inputs with tied splitter coordinates. Please either state an explicit distinct-coordinates / general-position assumption and apply it wherever the theorems are invoked, or give a tie-robust version of the sampling argument. As written, the theorems overclaim.
  2. [§4.3 / Appendix B] There is an algebraic inconsistency in the update analysis. Theorem 4.1 sets σ = (6c log n)/α², but Appendix B writes that a rebuilt subtree contains (1/2 ± sqrt((12c log n)/σ)/4)n′ = (1/2 ± α/4)n′ points whp. Under the stated σ, sqrt((12c log n)/σ) = sqrt(2) α, not α, so the displayed equality is wrong. This does not change the asymptotic amortized bound when α is a constant, but the derivation should be corrected or the parameter σ should be adjusted to match the displayed expression.
minor comments (5)
  1. [§2] The paragraph on the ideal-cache model says 'we do not control the cache, so the optimal eviction strategy is guaranteed,' which contradicts the immediately following sentence stating that real eviction strategies are more complicated. The intended wording appears to be 'not guaranteed.'
  2. [§3.2, proof of Lemma 3.1] In the proof, 'Let X = ΣXᵢ for i = 1..|Λ|' should read 'for i = 1..s', since the indicators are over the s sampled points, not over the points of Λ. The subsequent Chernoff calculation is otherwise clear.
  3. [§4.2] Batch deletion is described only in prose. Since deletion differs from insertion by requiring a first round to identify absent points and then a second round to find unbalanced subtrees, the paper would benefit from either a pseudocode listing or a more detailed formal description of the two rounds and their cost accounting.
  4. [§5] The text refers to a 'leaf warp size' when describing the leaf wrap threshold φ; this appears to be a typo for 'leaf wrap size.'
  5. [§6] Reported timings are described as the average of three runs after a warm-up, but no variance, standard deviation, or min/max values are given. Given that some claimed speedups are close to 1.0× or 1.3×, adding error bars or per-run values would make the comparisons more informative.

Circularity Check

0 steps flagged · score 0.0 of 10

No load-bearing circularity: the theoretical results are derived from in-paper sampling and amortization arguments, and the experimental benchmarks are external.

full rationale

The paper's central derivation chain is self-contained rather than circular. Lemma 3.1, which provides the whp balance guarantee used for construction height and update amortization, is proved in the paper via a Chernoff-bound argument on uniformly sampled points; the citation to similar sampling results is for context only and does not carry the proof. Theorem 3.3's work, span, and cache bounds follow directly from the algorithm's parameters (lambda, sigma, chunk size) and from the recurrence on recursive levels, and the optimality argument rests on the standard sorting lower bound. Theorem 4.1 and Appendix B use an amortization argument over the weight-balance trigger, with the rebuild cost charged to the updates that must occur before the next rebuild; no fitted parameter is renamed as a prediction. The experimental section compares against external libraries (CGAL, Boost R-tree, Zd-tree, ParGeo), and while ParGeo shares a co-author, the comparison is to an independent implementation and is not used to justify the theoretical claims. The skeptical concern about duplicate-heavy inputs and ties at the splitter coordinate identifies a possible gap in the proof of Lemma 3.1's applicability, but that is a correctness/robustness issue, not circularity: the proof does not assume its conclusion. Self-citations in the paper (e.g., to prior sampling results and to a tree-traversal lemma) are either proved in the text or are independently established facts, so they do not reduce the central claim to its own inputs.

Assumptions & free parameters 4 free parameters · 5 assumptions · 0 invented entities

The central claims rest on standard computational models plus a randomized sampling assumption. The only hand-set numbers are engineering parameters (lambda, sigma, alpha, phi) whose values are chosen by experiment. No new physical or conceptual entities are postulated.

free parameters (4)
  • lambda (skeleton height) = 6
    Controls how many kd-tree levels are built per round from samples. Theory requires lambda = epsilon log M; experiments use 6.
  • sigma (oversampling rate) = 32
    Sample count multiplier for splitter selection. Theory requires Theta(log n); experiments use 32.
  • alpha (balancing parameter) = 0.3
    Allowed weight imbalance between siblings. Chosen via parameter study in Sec 6.5 as a trade-off between update cost and query performance.
  • phi (leaf wrap threshold) = 32
    Maximum points stored in a leaf. Set to 32 in implementation.
assumptions (5)
  • standard math Binary-forking work-span model with a randomized work-stealing scheduler
    Used for all work and span claims (Sec 2).
  • standard math Ideal-cache model with optimal offline replacement, with LRU assumed equivalent
    Used for cache complexity bounds (Sec 2).
  • domain assumption Input points are sampled uniformly with replacement for splitter selection
    Needed for Lemma 3.1, the Chernoff bound on subtree balance.
  • domain assumption Cache size M is Omega(polylog n) and lambda = epsilon log M with epsilon < 1/2
    Assumed in Theorem 3.3 so sample set and per-chunk matrices fit in cache (Sec 3.2).
  • domain assumption Median-based splitters give standard balanced kd-tree query bounds
    Used to inherit O(n^{(D-1)/D}) orthogonal range-query bounds (Sec 5).

how reviews work

0 comments
Cite this review

Pith. "Pith review of Parallel $k$d-tree with Batch Updates." pith.science (2026). https://pith.science/paper/AZT5MCJR

@misc{pith2026241109275,
  author       = {Pith},
  title        = {Pith review of: Parallel $k$d-tree with Batch Updates},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/AZT5MCJR}},
  note         = {Machine review of arXiv:2411.09275}
}
abstract

The $k$d-tree is one of the most widely used data structures to manage multi-dimensional data. Due to the ever-growing data volume, it is imperative to consider parallelism in $k$d-trees. However, we observed challenges in existing parallel kd-tree implementations, for both constructions and updates. The goal of this paper is to develop efficient in-memory $k$d-trees by supporting high parallelism and cache-efficiency. We propose the Pkd-tree (Parallel $k$d-tree), a parallel $k$d-tree that is efficient both in theory and in practice. The Pkd-tree supports parallel tree construction, batch update (insertion and deletion), and various queries including k-nearest neighbor search, range query, and range count. We proved that our algorithms have strong theoretical bounds in work (sequential time complexity), span (parallelism), and cache complexity. Our key techniques include 1) an efficient construction algorithm that optimizes work, span, and cache complexity simultaneously, and 2) reconstruction-based update algorithms that guarantee the tree to be weight-balanced. With the new algorithmic insights and careful engineering effort, we achieved a highly optimized implementation of the Pkd-tree. We tested Pkd-tree with various synthetic and real-world datasets, including both uniform and highly skewed data. We compare the Pkd-tree with state-of-the-art parallel $k$d-tree implementations. In all tests, with better or competitive query performance, Pkd-tree is much faster in construction and updates consistently than all baselines. We released our code.

Figures

Figures reproduced from arXiv: 2411.09275 by the authors.

Figure 1
Figure 1. An illustration of our 𝑘d-tree construction algorithm, with a detailed overview on the sieving step. In this example, we first sample seven points and construct the tree skeleton using the samples, dividing the plane into four regions (buckets). Next, we sieve all points into the corresponding bucket. Concretely, we divide the points 𝑃 into chunks of size 𝑙 = 3. All chunks are processed in parallel. For each chunk, … view at source ↗
Figure 2
Figure 2. Illustation of our batch insertion to a 𝑘d-tree. Our algorithm first fetches the tree skeleton from the 𝑘d-tree, sieves the points into the corresponding bucket as in Alg. 1, then processes each buckets in parallel, and finally rebuilds the subtrees that become imbalance after insertion. Algorithm 2: Batch insertion Input: A sequence of points 𝑃 and a 𝑘d-tree 𝑇 . Output: A 𝑘d-tree with 𝑃 inserted. Parameter :𝜆: the … view at source ↗
Figure 4
Figure 4. Running time (in seconds) of 𝑘-NN queries for 𝑘 ∈ {1, 10, 100}. Lower is better. The dataset contains 1000M points in 3 di￾mensions. The test contains 𝑘-NN queries from 107 points in the input. Plots are in log-log scale [PITH_FULL_IMAGE:figures/full_fig_p009_4.png] view at source ↗
Figures from the paper (4 more)
Figure 6
Figure 6. Figure 6: Batch update using a sliding window spanning five years and 10-NN queries on [PITH_FULL_IMAGE:figures/full_fig_p011_6.png]
Figure 8
Figure 8. Figure 8: Time, cache misses, and memory usage needed during the [PITH_FULL_IMAGE:figures/full_fig_p011_8.png]
Figure 9
Figure 9. Figure 9: Normalized rebuild size, update and query times with vary [PITH_FULL_IMAGE:figures/full_fig_p012_9.png]
Figure 10
Figure 10. Figure 10: Normalized parallel speedup of operations on [PITH_FULL_IMAGE:figures/full_fig_p012_10.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

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

  1. Monitoring Robustness and Individual Fairness

    cs.AI 2025-05 conditional novelty 6.0 of 10

    Runtime monitoring of input-output robustness, covering adversarial robustness, semantic robustness, and individual fairness, is implemented as online fixed-radius nearest-neighbor search in the tool Clemont.

Reference graph

Works this paper leans on

93 extracted references · 60 canonical work pages · cited by 1 Pith paper

  1. [1]

    Pankaj Agarwal, Kyle Fox, Kamesh Munagala, and Abhinandan Nath. 2016. Par- allel algorithms for constructing range and nearest-neighbor searching data structures. In Principles of Database Systems (PODS) . 429–440

    2016

  2. [2]

    Pankaj K Agarwal, Lars Arge, Andrew Danner, and Bryan Holland-Minkley. 2003. Cache-oblivious data structures for orthogonal range searching. In Proceedings of the nineteenth annual symposium on Computational geometry . 237–245

    2003

  3. [3]

    Alok Aggarwal and S Vitter, Jeffrey. 1988. The input/output complexity of sorting and related problems. Commun. ACM 31, 9 (1988), 1116–1127

    1988

  4. [4]

    I Al-Furajh, Srinivas Aluru, Sanjay Goil, and Sanjay Ranka. 2000. Parallel con- struction of multidimensional binary search trees. IEEE Transactions on Parallel and Distributed Systems 11, 2 (2000), 136–148

    2000

  5. [5]

    Daniel Anderson, Guy E Blelloch, Laxman Dhulipala, Magdalen Dobson, and Yihan Sun. 2022. The problem-based benchmark suite (PBBS), V2. In ACM Symposium on Principles and Practice of Parallel Programming (PPOPP) . 445–447

    2022

  6. [6]

    Arne Andersson. 1989. Improving partial rebuilding by using simple balance criteria. In Workshop on Algorithms and Data Structures (W ADS). Springer, 393– 402

    1989

  7. [7]

    Lars Arge, Gerth Stølting Brodal, and Rolf Fagerberg. 2004. Cache-Oblivious Data Structures. Handbook of Data Structures and Applications 27 (2004)

    2004

  8. [8]

    Lars Arge, Klaus H Hinrichs, Jan Vahrenhold, and Jeffrey Scott Vitter. 2002. Efficient bulk operations on dynamic R-trees. Algorithmica 33 (2002), 104–128

    2002

Show all 93 references
  1. [9]

    Nimar S Arora, Robert D Blumofe, and C Greg Plaxton. 2001. Thread scheduling for multiprogrammed multiprocessors. Theory of Computing Systems (TOCS) 34, 2 (2001), 115–144

    2001

  2. [10]

    Michael A Bender, Erik D Demaine, and Martin Farach-Colton. 2000. Cache- oblivious B-trees. In focs. IEEE, 399–409

    2000

  3. [11]

    Jon Louis Bentley. 1975. Multidimensional binary search trees used for associative searching. Commun. ACM 18, 9 (1975), 509–517

    1975

  4. [12]

    Jon Louis Bentley. 1979. Decomposable searching problems. Inform. Process. Lett. 8, 5 (1979), 244–251

    1979

  5. [13]

    Blelloch

    Guy E. Blelloch. 1989. Scans as Primitive Parallel Operations. IEEE Trans. on Comput. 38, 11 (1989)

    1989

  6. [14]

    Blelloch, Daniel Anderson, and Laxman Dhulipala

    Guy E. Blelloch, Daniel Anderson, and Laxman Dhulipala. 2020. ParlayLib — a toolkit for parallel algorithms on shared-memory multicore machines. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) . 507–509

    2020

  7. [15]

    Guy E Blelloch and Magdalen Dobson. 2022. Parallel Nearest Neighbors in Low Dimensions with Batch Updates. In Algorithm Engineering and Experiments (ALENEX). SIAM, 195–208

    2022

  8. [16]

    Blelloch, Daniel Ferizovic, and Yihan Sun

    Guy E. Blelloch, Daniel Ferizovic, and Yihan Sun. 2016. Just Join for Parallel Ordered Sets. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)

    2016

  9. [17]

    Blelloch, Jeremy T

    Guy E. Blelloch, Jeremy T. Fineman, Yan Gu, and Yihan Sun. 2020. Optimal parallel algorithms in the binary-forking model. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 89–102

    2020

  10. [18]

    Blelloch, Phillip B

    Guy E. Blelloch, Phillip B. Gibbons, and Harsha Vardhan Simhadri. 2010. Low depth cache-oblivious algorithms. In ACM Symposium on Parallelism in Algo- rithms and Architectures (SPAA)

    2010

  11. [19]

    Blelloch and Yan Gu

    Guy E. Blelloch and Yan Gu. 2020. Improved Parallel Cache-Oblivious Algorithms for Dynamic Programming. In SIAM Symposium on Algorithmic Principles of Computer Systems (APOCS)

    2020

  12. [20]

    Blelloch, Yan Gu, Julian Shun, and Yihan Sun

    Guy E. Blelloch, Yan Gu, Julian Shun, and Yihan Sun. 2018. Parallel Write- Efficient Algorithms and Data Structures for Computational Geometry. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)

    2018

  13. [21]

    Benjamin Blonder, Cecina Babich Morrow, Brian Maitner, David J Harris, Chris- tine Lamanna, Cyrille Violle, Brian J Enquist, and Andrew J Kerkhoff. 2018. New approaches for delineating n-dimensional hypervolumes. Methods in Ecology and Evolution 9, 2 (2018), 305–319

    2018

  14. [22]

    Blumofe and Charles E

    Robert D. Blumofe and Charles E. Leiserson. 1998. Space-Efficient Scheduling of Multithreaded Computations. SIAM J. on Computing 27, 1 (1998)

    1998

  15. [23]

    Christian Böhm, Stefan Berchtold, and Daniel A Keim. 2001. Searching in high- dimensional spaces: Index structures for improving the performance of multime- dia databases. ACM Computing Surveys (CSUR) 33, 3 (2001), 322–373

    2001

  16. [24]

    Russell A Brown. 2014. Building a balanced kd tree in o (kn log n) time. arXiv preprint arXiv:1410.5420 (2014)

    2014

  17. [25]

    Yixi Cai, Wei Xu, and Fu Zhang. 2021. ikd-tree: An incremental kd tree for robotic applications. arXiv preprint arXiv:2102.10808 (2021)

    2021 arXiv

  18. [26]

    Yu Cao, Xiaojiang Zhang, Boheng Duan, Wenjing Zhao, and Huizan Wang

  19. [27]

    Bapi Chatterjee, Ivan Walulya, and Philippas Tsigas. 2018. Concurrent lineariz- able nearest neighbour search in lock free-kd-tree. In Proceedings of the 19th International Conference on Distributed Computing and Networking . 1–10

    2018

  20. [28]

    Yifei Chen, Yi Li, Rajiv Narayan, Aravind Subramanian, and Xiaohui Xie. 2016. Gene expression inference with deep learning. Bioinformatics 32, 12 (2016), 1832–1839

    2016

  21. [29]

    Byn Choi, Rakesh Komuravelli, Victor Lu, Hyojin Sung, Robert L Bocchino Jr, Sarita V Adve, and John C Hart. 2010. Parallel SAH kD tree construction. In High performance graphics. Citeseer, 77–86

    2010

  22. [30]

    Zhenyun Deng, Xiaoshu Zhu, Debo Cheng, Ming Zong, and Shichao Zhang. 2016. Efficient kNN classification algorithm for big data. Neurocomputing 195 (2016), 143–148

    2016

  23. [31]

    Blelloch, Yan Gu, and Yihan Sun

    Laxman Dhulipala, Guy E. Blelloch, Yan Gu, and Yihan Sun. 2022. PaC-trees: Supporting Parallel and Compressed Purely-Functional Collections. In ACM Conference on Programming Language Design and Implementation (PLDI)

    2022

  24. [32]

    Xiaojun Dong, Laxman Dhulipala, Yan Gu, and Yihan Sun. 2024. Parallel Integer Sort: Theory and Practice. InACM Symposium on Principles and Practice of Parallel Programming (PPOPP)

    2024

  25. [33]

    Xiaojun Dong, Yunshu Wu, Zhongqi Wang, Laxman Dhulipala, Yan Gu, and Yihan Sun. 2023. High-Performance and Flexible Parallel Algorithms for Semisort and Related Problems. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)

    2023

  26. [34]

    Jordi Fonollosa, Sadique Sheik, Ramón Huerta, and Santiago Marco. 2015. Reser- voir computing compensates slow response of chemosensor arrays exposed to fast varying gas concentrations in continuous monitoring. Sensors and Actuators B: Chemical 215 (2015), 618–629

    2015

  27. [35]

    Jerome H Friedman, Jon Louis Bentley, and Raphael Ari Finkel. 1977. An algorithm for finding best matches in logarithmic expected time. ACM Transactions on Mathematical Software (TOMS) 3, 3 (1977), 209–226

    1977

  28. [36]

    Leiserson, Harald Prokop, and Sridhar Ramachandran

    Matteo Frigo, Charles E. Leiserson, Harald Prokop, and Sridhar Ramachandran

  29. [37]

    Igal Galperin and Ronald Rivest. 1993. Scapegoat Trees.. InACM-SIAM Symposium on Discrete Algorithms (SODA), Vol. 93. 165–174

    1993

  30. [38]

    Junhao Gan and Yufei Tao. 2017. On the hardness and approximation of Euclidean DBSCAN. ACM Transactions on Database Systems (TODS) 42, 3 (2017), 1–45

    2017

  31. [39]

    Kirill Garanzha, Simon Premože, Alexander Bely, and Vladimir Galaktionov. 2011. Grid-based SAH BVH construction on a GPU. The Visual Computer 27 (2011), 697–706

    2011

  32. [40]

    Goetz Graefe. 1993. Query Evaluation Techniques for Large Databases. ACM Comput. Surv. 25, 2 (1993), 73–170

    1993

  33. [41]

    Yan Gu, Ziyang Men, Zheqi Shen, Yihan Sun, and Zijin Wan. 2023. Parallel Longest Increasing Subsequence and van Emde Boas Trees. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)

    2023

  34. [42]

    Yan Gu, Zachary Napier, and Yihan Sun. 2022. Analysis of Work-Stealing and Parallel Cache Complexity. In SIAM Symposium on Algorithmic Principles of Computer Systems (APOCS). SIAM, 46–60

    2022

  35. [43]

    Yulan Guo, Ferdous Sohel, Mohammed Bennamoun, Min Lu, and Jianwei Wan

  36. [44]

    Ralf Hartmut Güting. 1994. An introduction to spatial database systems. the VLDB Journal 3 (1994), 357–399

    1994

  37. [45]

    Antonin Guttman. 1984. R-trees: A dynamic index structure for spatial searching. In ACM SIGMOD International Conference on Management of Data (SIGMOD) . 47–57. 14

    1984

  38. [46]

    Mordechai Haklay and Patrick Weber. 2008. Openstreetmap: User-generated street maps. IEEE Pervasive computing 7, 4 (2008), 12–18

    2008

  39. [47]

    Georges Hebrail and Alice Berard. 2012. Individual household elec- tric power consumption. UCI Machine Learning Repository. DOI: https://doi.org/10.24432/C58K54

    2012 doi

  40. [48]

    Ramon Huerta, Thiago Mosqueiro, Jordi Fonollosa, Nikolai F Rulkov, and Irene Rodriguez-Lujan. 2016. Online decorrelation of humidity and temperature in chemical sensors for continuous monitoring. Chemometrics and Intelligent Labo- ratory Systems 157 (2016), 169–176

    2016

  41. [49]

    Warren Hunt, William R Mark, and Gordon Stoll. 2006. Fast kd-tree construction with an adaptive error-bounded heuristic. In IEEE Symposium on Interactive Ray Tracing. IEEE, 81–88

    2006

  42. [50]

    Jeffrey Ichnowski and Ron Alterovitz. 2020. Concurrent nearest-neighbor search- ing for parallel sampling-based motion planning in SO (3), SE (3), and euclidean spaces. In Algorithmic Foundations of Robotics XIII: Proceedings of the 13th Work- shop on the Algorithmic Foundatio...

    2020

  43. [51]

    Intel Corporation. 2024. VTune Profiler. https://www.intel.com/content/www/ us/en/developer/tools/oneapi/vtune-profiler.html

    2024

  44. [52]

    Intel Threading Building Blocks [n. d.]. Intel Threading Building Blocks (TBB). https://www.threadingbuildingblocks.org

  45. [53]

    Jaemin Jo, Jinwook Seo, and Jean-Daniel Fekete. 2017. A progressive kd tree for approximate k-nearest neighbors. In 2017 IEEE Workshop on Data Systems for Interactive Analysis (DSIA). IEEE, 1–5

    2017

  46. [54]

    Ibrahim Kamel and Christos Faloutsos. 1992. Parallel R-trees. ACM SIGMOD International Conference on Management of Data (SIGMOD) 21, 2 (1992), 195–204

    1992

  47. [55]

    Tapas Kanungo, David M Mount, Nathan S Netanyahu, Christine D Piatko, Ruth Silverman, and Angela Y Wu. 2002. An efficient k-means clustering algorithm: Analysis and implementation. IEEE transactions on pattern analysis and machine intelligence 24, 7 (2002), 881–892

    2002

  48. [56]

    Jiaxin Li, Ben M Chen, and Gim Hee Lee. 2018. So-net: Self-organizing network for point cloud analysis. In Proceedings of the IEEE conference on computer vision and pattern recognition. 9397–9406

    2018

  49. [57]

    Yujia Li, Chenjie Gu, Thomas Dullien, Oriol Vinyals, and Pushmeet Kohli. 2019. Graph matching networks for learning the similarity of graph structured objects. In International conference on machine learning . PMLR, 3835–3845

    2019

  50. [58]

    Aristidis Likas, Nikos Vlassis, and Jakob J Verbeek. 2003. The global k-means clustering algorithm. Pattern recognition 36, 2 (2003), 451–461

    2003

  51. [59]

    Lin Ma, Dana Van Aken, Ahmed Hefny, Gustavo Mezerhane, Andrew Pavlo, and Geoffrey J Gordon. 2018. Query-based workload forecasting for self-driving database management systems. InProceedings of the 2018 International Conference on Management of Data . 631–645

    2018

  52. [60]

    Yu A Malkov and Dmitry A Yashunin. 2018. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE transactions on pattern analysis and machine intelligence 42, 4 (2018), 824–836

    2018

  53. [61]

    Leland McInnes and John Healy. 2017. Accelerated hierarchical density based clustering. In 2017 IEEE International Conference on Data Mining Workshops (ICDMW). IEEE, 33–42

    2017

  54. [62]

    Ziyang Men, Zheqi Shen, Yan Gu, and Yihan Sun. 2024. Parallel 𝑘d-tree with Batch Updates. https://github.com/ucrparlay/Pkd-tree

    2024

  55. [63]

    Marius Muja and David G Lowe. 2014. Scalable nearest neighbor algorithms for high dimensional data. IEEE transactions on pattern analysis and machine intelligence 36, 11 (2014), 2227–2240

    2014

  56. [64]

    Mark H Overmars. 1983. The design of dynamic data structures . Vol. 156. Springer Science & Business Media

    1983

  57. [65]

    Mark H Overmars and Jan Van Leeuwen. 1981. Maintenance of configurations in the plane. Journal of computer and System Sciences 23, 2 (1981), 166–204

    1981

  58. [66]

    Sushil K Prasad, Michael McDermott, Xi He, and Satish Puri. 2015. GPU-based Parallel R-tree Construction and Querying. In 2015 IEEE International Parallel and Distributed Processing Symposium Workshop . IEEE, 618–627

    2015

  59. [67]

    Octavian Procopiuc, Pankaj K Agarwal, Lars Arge, and Jeffrey Scott Vitter. 2003. Bkd-tree: A dynamic scalable kd-tree. In International Symposium on Spatial and Temporal Databases (SSTD). Springer, 46–65

    2003

  60. [68]

    Sanguthevar Rajasekaran and John H. Reif. 1989. Optimal and sublogarithmic time randomized parallel sorting algorithms. SIAM J. on Computing 18, 3 (1989), 594–607

    1989

  61. [69]

    Maximilian Reif and Thomas Neumann. 2022. A scalable and generic approach to range joins. Proceedings of the VLDB Endowment 15, 11 (2022), 3018–3030

    2022

  62. [70]

    John T Robinson. 1981. The KDB-tree: a search structure for large multidimen- sional dynamic indexes. InACM SIGMOD International Conference on Management of Data (SIGMOD). 10–18

    1981

  63. [71]

    Boris Schäling. 2011. The boost C++ libraries . Boris Schäling

    2011

  64. [72]

    Erich Schubert, Jörg Sander, Martin Ester, Hans Peter Kriegel, and Xiaowei Xu

  65. [73]

    Nick Scoville, H Aussel, Marcella Brusa, Peter Capak, C Marcella Carollo, M Elvis, M Giavalisco, L Guzzo, G Hasinger, C Impey, et al. 2007. The cosmic evolution survey (COSMOS): overview. The Astrophysical Journal Supplement Series 172, 1 (2007), 1

    2007

  66. [74]

    Gregory Shakhnarovich, Trevor Darrell, and Piotr Indyk. 2005. Nearest-neighbor methods in learning and vision: theory and practice . Vol. 3. MIT press Cambridge, MA, USA:

    2005

  67. [75]

    Maxim Shevtsov, Alexei Soupikov, and Alexander Kapustin. 2007. Highly par- allel fast KD-tree construction for interactive ray tracing of dynamic scenes. In Computer Graphics Forum, Vol. 26. Wiley Online Library, 395–404

    2007

  68. [76]

    Jonathan A Silva, Elaine R Faria, Rodrigo C Barros, Eduardo R Hruschka, André CPLF de Carvalho, and Joã o Gama. 2013. Data stream clustering: A survey.ACM Computing Surveys (CSUR) 46, 1 (2013), 1–31

    2013

  69. [77]

    Sleator and Robert E

    Daniel D. Sleator and Robert E. Tarjan. 1985. Amortized Efficiency of List Update and Paging Rules. Commun. ACM 28, 2 (1985), 7 pages. https://doi.org/10.1145/ 2786.2793

    1985

  70. [78]

    Mark William Smith, Jonathan L Carrivick, and Duncan J Quincey. 2016. Struc- ture from motion photogrammetry in physical geography. Progress in physical geography 40, 2 (2016), 247–275

    2016

  71. [79]

    Yihan Sun, Daniel Ferizovic, and Guy E Blelloch. 2018. PAM: Parallel Augmented Maps. In ACM Symposium on Principles and Practice of Parallel Programming (PPOPP)

    2018

  72. [80]

    Jian Tang, Jingzhou Liu, Ming Zhang, and Qiaozhu Mei. 2016. Visualizing large- scale and high-dimensional data. InProceedings of the 25th international conference on world wide web . 287–297

    2016

  73. [81]

    The CGAL Project. 2020. CGAL User and Reference Manual (5.1 ed.). CGAL Editorial Board. https://doc.cgal.org/5.1/Manual/packages.html

    2020

  74. [82]

    Marc J van Kreveld and Mark H Overmars. 1991. Divided kd trees. Algorithmica 6 (1991), 840–858

    1991

  75. [83]

    Yiqiu Wang, Shangdi Yu, Laxman Dhulipala, Yan Gu, and Julian Shun. 2022. ParGeo: a library for parallel computational geometry. In European Symposium on Algorithms (ESA)

    2022

  76. [84]

    Yiqiu Wang, Shangdi Yu, Yan Gu, and Julian Shun. 2021. Fast parallel algorithms for euclidean minimum spanning tree and hierarchical spatial clustering. InACM SIGMOD International Conference on Management of Data (SIGMOD) . 1982–1995

    2021

  77. [85]

    Hiroki Yamasaki, Atsushi Nunome, and Hiroaki Hirata. 2018. Parallelizing the Construction of a k-Dimensional Tree. In 2018 IEEE International Conference on Big Data, Cloud Computing, Data Science & Engineering (BCD) . IEEE, 23–30

    2018

  78. [86]

    Simin You, Jianting Zhang, and Le Gruenwald. 2013. Parallel spatial query processing on gpus using r-trees. In Proceedings of the 2Nd ACM SIGSPATIAL international workshop on analytics for big geospatial data . 23–31

    2013

  79. [87]

    Xiao Yue, Huiju Wang, Dawei Jin, Mingqiang Li, and Wei Jiang. 2016. Healthcare data gateways: found healthcare intelligence on blockchain with novel privacy risk control. Journal of medical systems 40 (2016), 1–8

    2016

  80. [88]

    R-tree (seq.)

    Yu Zheng, Like Liu, Longhao Wang, and Xing Xie. 2008. Learning transportation mode from raw gps data for geographic applications on the web. In International World Wide Web Conference (WWW). 247–256. 15 A Proof for Tree Height Lemma A.1. Function𝑓(𝑛) =− log𝑛/log(1/2+ 1/log𝑛)− ...

    2008

  81. [106]

    CC”: Cycles, “Inst

    Different queries are performed in parallel, and each query searches the tree in serial. “CC”: Cycles, “Inst”: Instructions, “IPC”: Instructions per cycle, “CR”: Cache reference, “CMs”: Cache misses, “BR”: Branches, “BMs”: Branch misses. Tree Time (sec.) Average # of nodes pro...

  82. [1999]

    In IEEE Symposium on Foundations of Com- puter Science (FOCS)

    Cache-Oblivious Algorithms. In IEEE Symposium on Foundations of Com- puter Science (FOCS)

  83. [2013]

    International journal of computer vision 105 (2013), 63–86

    Rotational projection statistics for 3D local surface description and object recognition. International journal of computer vision 105 (2013), 63–86

    2013

  84. [2017]

    ACM Transactions on Database Systems (TODS) 42, 3 (2017), 1–21

    DBSCAN revisited, revisited: why and how you should (still) use DBSCAN. ACM Transactions on Database Systems (TODS) 42, 3 (2017), 1–21

    2017

  85. [2020]

    In International Conference on Software Engineering and Service Science (ICSESS)

    An improved method to build the KD tree based on presorted results. In International Conference on Software Engineering and Service Science (ICSESS) . IEEE, 71–75

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.