Pith. sign in

REVIEW 3 major objections 5 minor 68 references

On Simplifying Large-Scale Spatial Vectors: Fast, Memory-Efficient, and Cost-Predictable k-means

T0 review · 3 major / 5 minor · reviewed 2026-08-11 · deepseek-v4-flash

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

Pith's one-line read Dask-means claims exact k-means on million-scale spatial vectors can run 168x faster than the classic algorithm in under 30MB, with memory and runtime predicted by a lightweight estimator.

desk verdict The accelerator is the real contribution and it holds up; the cost estimator is the weak half, with a dimension-blind memory formula and an invalid GP kernel, but those are fixable and the paper deserves a serious referee. read the letter →

arxiv 2412.02244 v1 pith:3YDB5AEM submitted 2024-12-03 cs.LG

Yushuai Ji , Zepeng Liu , Sheng Wang , Yuan Sun , Zhiyong Peng This is my paper · ORCID
classification cs.LG
keywords k-meansspatialvectorsball-treeindexkNNsearchmemory-efficientclusteringruntimepredictionresource-constraineddevicespointcloudsimplification
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 proposes Dask-means, a k-means variant that returns the same clusters as the classic alternating-assignment algorithm while aiming to fit resource-constrained devices. Its central claim is that exact k-means can be accelerated by assigning spatial vectors to clusters in batches: a ball-tree over the data is built once, a ball-tree over the current centroids is rebuilt each iteration, and a three-pronged kNN search prunes whole nodes and vectors instead of scanning all k centroids. On million-scale 2D and 3D datasets, the paper reports up to 168x speedup over the classic algorithm while using under 30MB of memory, and it reports a lightweight cost estimator that predicts memory with a difference of less than 3% and runtime with an MSE up to 33.3% lower than several state-of-the-art predictors. The significance, if the claims hold, is that exact k-means becomes practical on mobile devices and other low-memory hardware for simplifying large spatial datasets.

What carries the argument

The load-bearing object is a pair of ball-trees joined by a bound-armed kNN search. A ball-tree node $N$ is defined by a pivot $p^*$, radius $r$, and, for the data tree, the number of vectors it covers; the centroid tree is rebuilt each iteration because centroids move. Three uses of kNN drive the acceleration: kNN with $k=2$ computes each centroid's inter bound $cb[j]=\min_{j'\neq j}\|c_j-c_{j'}\|$, kNN with $k=2$ finds the two nearest centroids of a data node $N$ and assigns the whole node when $d_2-d_1>2N.r$, and kNN with $k=1$ assigns individual leaf vectors. Pruning is tightened by an upper bound $ub=cb[j]+\Delta[j]+\max(\Delta)$ that uses centroid drift, and by parent-inherited bounds $ub_1(N'.p^*)=d_1(N.p^*)+N.r$ and $ub_2(N'.p^*)=d_2(N.p^*)+N.r$ for child nodes. The cost estimator's mapping $m\approx(2+28/f)(n+k)-32+n$ lets the algorithm invert the formula to pick $f$ from available memory.

What would settle it

Build the spatial-vector ball-tree on a deliberately skewed million-point dataset, such as points lying on a low-dimensional manifold with heavy density variation, set $f=30$, and compare the actual allocated memory against $M(n,f)=2n+28n/f-16$. If the ratio of estimated to actual memory deviates by more than a few percent, or fewer than half the leaves are about half full, the balanced-tree assumption behind the memory-tunable guarantee is broken.

Watch

Extended reading notes

Core claim

Dask-means' central discovery is that the assignment phase can be batched without storing per-point bounds. A spatial-vector ball-tree stores for each node its pivot, radius, count, and previous cluster id; the centroid ball-tree lets the algorithm find the one or two nearest centroids of a node or point in $O(\log_2 k)$ average time. If the distance gap between the two nearest centroids of a node's pivot exceeds twice the node radius, the entire node is assigned to the nearer centroid, and if an upper bound on a node's distance to its previous centroid is below half the inter-centroid bound, the node stays put. A memory formula $M(n,f)=2n+28n/f-16$ maps leaf capacity $f$ to index size, so $f$ can be chosen to fit a memory limit. The paper reports exact-k-means speedups of up to 168x over the classic algorithm on million-scale spatial data, under 30MB memory use, and memory predictions within 3%.

Load-bearing premise

The memory formula assumes the data ball-tree is balanced, with height $\lceil\log_2(2n/f)\rceil$ and each leaf holding about $f/2$ vectors; on skewed real-world data those assumptions may fail and the predicted memory and the chosen leaf capacity would be off.

Editorial extensions

If this is right

  • Exact k-means with large k (up to $10^4$) becomes executable in under 30MB, because no $n\times k$ lower-bound matrix is stored.
  • Because the output is identical to the classic algorithm, Dask-means can be substituted into existing pipelines without changing the resulting clusters.
  • A device can turn a memory budget into a concrete index configuration, making memory behavior predictable before the run starts.
  • The runtime model can be trained cheaply and adjusted during execution, so resource-constrained devices can reserve CPU time.
  • Speedup is strongest on 2D and 3D spatial data; on high-dimensional embeddings performance degrades to roughly 15x over the classic algorithm due to the curse of dimensionality.

Reading between the lines

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

  • The same dual-index, batch-assignment pattern could accelerate other Lloyd-style iterative algorithms for spatial data, such as k-medians or EM clustering, since the pruning rules rely only on triangle inequality bounds.
  • The memory formula implies a non-monotone runtime landscape: more memory improves pruning but adds index build time, so the estimator could be used not just to satisfy a constraint but to search for the memory level that minimizes runtime.
  • The balanced-tree assumption is testable on real trajectory and point-cloud distributions; if skewed data produce unbalanced trees, an adaptive height bound or a different space-partitioning structure would be needed to preserve the 3% memory prediction claim.
  • The asymmetric Gaussian-process correction is a general scheme for any iterative algorithm's runtime prediction, provided one can observe per-iteration runtimes.
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

3 major / 5 minor

Summary. The paper proposes Dask-means, an accelerated variant of Lloyd's k-means for large-scale spatial vectors on resource-constrained devices. The accelerator builds a ball-tree over data points and a per-iteration ball-tree over centroids, then assigns points to clusters in batches using a three-pronged kNN search with triangle-inequality bounds (Eqs. 4-8). A lightweight cost estimator predicts memory via a closed-form formula M(n,f) (Eq. 10) and runtime via a polynomial regressor plus a Gaussian-process adjustment. Experiments on 2D/3D trajectory and point-cloud datasets report speedups up to 168x over Lloyd's, memory under 30MB, and runtime prediction error below SOTA methods. The paper also evaluates high-dimensional embedded trajectories (d=128, 256) and a smartphone deployment.

Significance. If the claims hold, the paper makes an exact (Lloyd-equivalent) k-means practical on low-memory devices and introduces a cost model that can tune index size to a memory budget. The pruning inequalities are correct triangle-inequality applications, and the experimental speedups on low-dimensional data are substantial. The paper ships public code and includes extensive comparisons against standard accelerators, which is a strength. The main weakness is that the memory model and the associated memory-tunable index configuration are not valid for high-dimensional data, and the reported memory-accuracy numbers do not fully support the abstract's '<3%' claim.

major comments (3)
  1. [Section V-A, Eqs. (10)-(12)] The memory formula assumes each stored node pivot costs exactly 3 floats, but the paper's own high-dimensional datasets (Apoll-TD d=128, Argo-ETD d=256 in Table V) have pivots costing d floats. Consequently M(n,f) under-predicts index memory by roughly a factor of d/3 for these datasets, and Eq. (12) computes a leaf capacity f that would exceed a given memory budget. Since the 'memory-tunable index' and the resource-constrained guarantee rest on this mapping, the cost-predictability claim is not established for high-dimensional spatial vectors; the paper either needs a dimension-aware memory model or must restrict the memory-tunable claim to d<=3 and state that limitation explicitly.
  2. [Table VI and Abstract] Table VI reports accuracy as estimated/actual memory, with all k-values showing 0.963. This corresponds to a 3.7% error, not 'a difference of less than 3%' as stated in the abstract and introduction. The metric should be defined precisely (e.g., |estimated-actual|/actual), and the claimed <3% accuracy should be corrected or supported by measurements that actually satisfy that bound.
  3. [Section V-A and Appendix VIII-A] The closed-form memory estimate relies on the assumptions that the spatial-vector ball-tree is balanced with height ceil(log2(2n/f)) and that leaves are half full on average. Appendix VIII-A itself acknowledges that a degenerate ball-tree can have height n-f and construction cost O(dn^2). The paper does not report memory-estimation accuracy on skewed distributions or on data that produce unbalanced trees, yet Eqs. (10)-(12) are presented as general mapping functions. At minimum, the scope of the balanced-tree assumption should be stated as a validity condition, and experiments should show whether real datasets satisfy it.
minor comments (5)
  1. [Abstract and Table VI] The '<3%' memory-accuracy claim should be reconciled with the 0.963 ratio reported in Table VI; a ratio of 0.963 is 3.7% away from 1.
  2. [Section V-A] The text says 'ball-true structure'; this should be 'ball-tree structure'.
  3. [Appendix VIII-C, Fig. 13] Figure 13's caption refers to 'the impact of α', but the text and equations use σ for the GP kernel hyperparameter; the notation should be unified.
  4. [Introduction] There are typographical errors such as 'Inaccruate Memory & Runtime Estimation' and 'da taset simplification'; these should be corrected before publication.
  5. [References] Reference [50] appears to have a malformed author entry ('C. R. R. A Dual-Tree Algorithm For Fast k-means Clustering With Large k'); the authors and title need to be fixed.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the acceleration and cost-estimator claims are evaluated against external baselines and held-out data, and the only self-citation is a non-load-bearing survey pointer.

full rationale

The claimed derivation chain is self-contained. The accelerator's pruning rules are justified by the triangle inequality and exact kNN search, and its speedups are measured against external implementations (Lloyd, Hamerly, Elkan, NoBound, Dual-tree, Yinyang, Drake), so the central speedup claim is not forced by any fitted parameter. The memory estimator (Eqs. 10-12) is an analytic node-accounting model with explicitly stated assumptions (balanced tree, half-full leaves, 3-float pivots); its accuracy is then checked against measured memory in Table VI, making it an empirical prediction rather than a tautology. The runtime estimator is trained on an 80/10/10 split of 2000 generated k-means tasks and compared with XGBoost, DisNet, and AutoML; the fitted regression coefficients and the validation-chosen hyperparameters beta=4 and sigma=50 do not by construction equal the predicted runtimes. The only self-citation ([61]) is used solely as a survey pointer in Section II-C and carries no load in the derivation. The balanced-tree and low-dimensional-pivot assumptions are genuine robustness/extrapolation risks for skewed or high-dimensional data, but that is a correctness limitation, not circularity.

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

The central accelerator rests on standard triangle-inequality pruning, but the cost-predictability claims rest on several hand-tuned or dimension-blind assumptions: the tree balance and leaf occupancy assumptions behind Eq (10), the unit-counting of leaf vectors, and the validity of the asymmetric GP kernel. The free parameters f, beta, sigma are chosen by hand or validation.

free parameters (5)
  • leaf node capacity f = f=30 default; 30-200 in experiments
    Controls the memory/runtime tradeoff of the dual ball-tree indexes (Section IV-A, Eq 10-12).
  • polynomial degree beta = beta=4
    Degree of the polynomial runtime regressor, selected on a validation split (Section VIII-C).
  • GP kernel scale sigma = sigma=50
    Controls correlation in the runtime-adjustment GP, selected on validation (Section VIII-C).
  • leaf fullness factor = 2
    The memory estimate doubles the number of leaf nodes assuming each is half full (Section V-A, Eq 10).
  • initial GP mean = 1
    Assumes the initial runtime prediction is exact before any posterior information (Section V-B2).
assumptions (6)
  • standard math Triangle inequality holds for Euclidean distance and is used for all pruning bounds.
    Invoked throughout Section IV in Eqs 2, 4-9.
  • ad hoc to paper The spatial-vector Ball-tree is balanced with height ceil(log_2(2n/f)) and each leaf holds about f/2 vectors.
    Used in Eq (10) to derive the memory formula and in the complexity analysis (Appendix VIII-A).
  • ad hoc to paper Memory per leaf-stored spatial vector is one unit, independent of dimensionality d.
    The formula 3+3+f in Eq (10) treats each vector in a leaf as one float; no d term appears.
  • ad hoc to paper The asymmetric function in Eq (20) is a valid GP covariance kernel.
    The kernel is not symmetric, so it is not a valid covariance function; the GP adjustment relies on this assumption.
  • domain assumption Runtime and memory estimates trained on Dask-means runs generalize to unseen k-means tasks in the tested range (n=1e5-1e8, k=1e2-1e4).
    Standard supervised modeling assumption for the cost estimator (Section VI-C).
  • domain assumption k-means can be stopped at 20 iterations for fair speedup comparisons.
    Experiments cap maximum iterations to 20 (Section VI-B); the resulting clusters may not be fully converged.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On Simplifying Large-Scale Spatial Vectors: Fast, Memory-Efficient, and Cost-Predictable k-means." pith.science (2026). https://pith.science/paper/3YDB5AEM

@misc{pith2026241202244,
  author       = {Pith},
  title        = {Pith review of: On Simplifying Large-Scale Spatial Vectors: Fast, Memory-Efficient, and Cost-Predictable k-means},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/3YDB5AEM}},
  note         = {Machine review of arXiv:2412.02244}
}
abstract

The k-means algorithm can simplify large-scale spatial vectors, such as 2D geo-locations and 3D point clouds, to support fast analytics and learning. However, when processing large-scale datasets, existing k-means algorithms have been developed to achieve high performance with significant computational resources, such as memory and CPU usage time. These algorithms, though effective, are not well-suited for resource-constrained devices. In this paper, we propose a fast, memory-efficient, and cost-predictable k-means called Dask-means. We first accelerate k-means by designing a memory-efficient accelerator, which utilizes an optimized nearest neighbor search over a memory-tunable index to assign spatial vectors to clusters in batches. We then design a lightweight cost estimator to predict the memory cost and runtime of the k-means task, allowing it to request appropriate memory from devices or adjust the accelerator's required space to meet memory constraints, and ensure sufficient CPU time for running k-means. Experiments show that when simplifying datasets with scale such as $10^6$, Dask-means uses less than $30$MB of memory, achieves over $168$ times speedup compared to the widely-used Lloyd's algorithm. We also validate Dask-means on mobile devices, where it demonstrates significant speedup and low memory cost compared to other state-of-the-art (SOTA) k-means algorithms. Our cost estimator estimates the memory cost with a difference of less than $3\%$ from the actual ones and predicts runtime with an MSE up to $33.3\%$ lower than SOTA methods.

Figures

Figures reproduced from arXiv: 2412.02244 by the authors.

Figure 1
Figure 1. The simplified point clouds by random sampling (left) and our [PITH_FULL_IMAGE:figures/full_fig_p001_1.png] view at source ↗
Figure 2
Figure 2. Pruning using ball node and inter bound. [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. Framework of Dask-means. IV. MEMORY-EFFICIENT ACCELERATOR A. Pruning Mechanisms We design pruning mechanisms that apply a three-pronged optimized kNN over the centroid index to batch prune nodes and spatial vectors, thus accelerating k-means without the need to store bounds for spatial vectors. We first prune distance computations between centroids and a set of spatial vectors by applying kNN to find the nearest cen… view at source ↗
Figures from the paper (10 more)
Figure 4
Figure 4. Figure 4: Pruning with a single indexing tree, where a spatial vector node [PITH_FULL_IMAGE:figures/full_fig_p005_4.png]
Figure 5
Figure 5. Figure 5: Overview of our lightweight cost estimator, where [PITH_FULL_IMAGE:figures/full_fig_p006_5.png]
Figure 6
Figure 6. Figure 6: The performance of kNN and inter bound in acceleration on both a server and a smartphone: 1) The server, equipped with an i9-14900KF CPU and 128 GB RAM, allows us to simulate the k-means task on resource-limited devices and easily implement our lightweight estimator to…
Figure 7
Figure 7. Figure 7: The per-iteration runtime of the k-means algorithm under different data scales. k = 10 2 , k = 10 3 , k = 10 4 10 1 10 2 Runtime (s) T-drive k = 10 2 , k = 10 3 , k = 10 4 10 1 10 2 Runtime (s) Porto k = 10 2 , k = 10 3 , k = 10 4 10 1 10 2 Runtime (s) Argo-AVL k = 10 …
Figure 10
Figure 10. Figure 10: The performance of Dask-means in the smartphone. • The value of k has only a slight effect on efficiency. This is consistent with the observation that log2 k and the dataset scale n have a linear relation with the running time. • For high-dimensional datasets, Dask-me…
Figure 11
Figure 11. Figure 11: The performance of our cost estimator in terms of predicting runtime. [PITH_FULL_IMAGE:figures/full_fig_p012_11.png]
Figure 12
Figure 12. Figure 12: The runtime performance of k-means algorithms in each iteration. TABLE VIII THE IMPACT OF THE INTERACTION FEATURES AND β. Degree Basic Feature Interaction Feature MSE MAE WMAPE sMAPE MSE MAE WMAPE sMAPE β = 1 600.48 18.44 0.41 62.15 525.33 17.39 0.39 59.06 β = 2 245.6…
Figure 13
Figure 13. Figure 13: The impact of α in adjusting the runtime. 2 4 6 8 10 Iterations (a) MSE of Each Method 10 1 10 0 Running Time (S) 2 4 6 8 10 Iterations (b) MAE of Each Method 10 1 10 0 Running Time (S) 2 4 6 8 10 Iterations (c) WMAPE of Each Method 10 1 Running Time (S) 2 4 6 8 10 It…
Figure 14
Figure 14. Figure 14: The performance of our cost estimator in adjusting predicted runtime. [PITH_FULL_IMAGE:figures/full_fig_p016_14.png]
Figure 15
Figure 15. Figure 15: Running k-means algorithms on the smartphone [PITH_FULL_IMAGE:figures/full_fig_p016_15.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

68 extracted references · 66 canonical work pages

  1. [1]

    https://networkrepository

    3d road network (north jutland, denmark). https://networkrepository. com/3D-spatial-network.php

    work page

  2. [2]

    https://shapenet.org/

    Shapenet. https://shapenet.org/

    work page

  3. [3]

    https://figshare.com/ articles/dataset/Porto taxi trajectories/12302165

    Taxi service trajectory prediction challenge 2015. https://figshare.com/ articles/dataset/Porto taxi trajectories/12302165

    work page arXiv 2015

  4. [4]

    https://www.hackster.io/flyingfox/flyingfox-821a16, 2021

    FlyingFox. https://www.hackster.io/flyingfox/flyingfox-821a16, 2021

    work page 2021

  5. [5]

    https://www.oppo.com/en/smartphones/ series-reno/reno11/

    Oppo reno11 5g, 2024. https://www.oppo.com/en/smartphones/ series-reno/reno11/

    work page 2024

  6. [6]

    https://github.com/notNNORTH/ Dask-means-cpp, 2024

    Repository of Dask-means. https://github.com/notNNORTH/ Dask-means-cpp, 2024

    work page 2024

  7. [7]

    https://malmaud.github.io/tfdocs/shape inference/, 2024

    TensorFlow Shape Infer . https://malmaud.github.io/tfdocs/shape inference/, 2024

    work page 2024

  8. [8]

    T. S. Abdelrahman. Cooperative software-hardware acceleration of k- means on a tightly coupled CPU-FPGA system. ACM Trans. Archit. Code Optim., 17(3):20:1–20:24, 2020

    work page 2020

Show all 68 references
  1. [9]

    M. Ahmed. Data summarization: a survey. Knowl Inf Syst, 58:249–273, 2019

    2019

  2. [10]

    Albert, S

    E. Albert, S. Genaim, and M. G ´omez-Zamalloa. Parametric inference of memory requirements for garbage collected languages. In ISMM, pages 121–130, 2010

    2010

  3. [11]

    M. A. Bender, J. Berry, S. D. Hammond, B. Moore, B. Moseley, and C. A. Phillips. k-Means Clustering on Two-Level Memory Systems. In MEMSYS, pages 197–205, 2015

    2015

  4. [12]

    Brand, J

    I. Brand, J. Roy, A. Ray, J. Oberlin, and S. Oberlix. PiDrone: An Autonomous Educational Drone Using Raspberry Pi and Python. In IROS, pages 5697–5703, 2018

    2018

  5. [13]

    Canziani, A

    A. Canziani, A. Paszke, and E. Culurciello. An analysis of deep neural network models for practical applications. arXiv preprint arXiv:1605.07678, 2016

    2016 arXiv

  6. [14]

    Castelo, F

    S. Castelo, F. Chirigati, R. Rampin, A. Santos, A. Bessa, and J. Freire. Auctus: A Dataset Search Engine for Data Augmentation. PVLDB, 14(12):2791 – 2794, 2021

    2021

  7. [15]

    Chang, J

    M.-F. Chang, J. Lambert, P. Sangkloy, J. Singh, S. Bak, A. Hartnett, D. Wang, P. Carr, S. Lucey, D. Ramanan, and J. Hays. Argoverse: 3D Tracking and Forecasting with Rich Maps. In CVPR, pages 8748–8757, 2019

    2019

  8. [16]

    Chicco, M

    D. Chicco, M. J. Warrens, and G. Jurman. The coefficient of determi- nation r-squared is more informative than smape, mae, mape, MSE and RMSE in regression analysis evaluation. PeerJ Comput. Sci. , 7:e623, 2021

    2021

  9. [17]

    Y . Ding, Y . Zhao, X. Shen, M. Musuvathi, and T. Mytkowicz. Yinyang K-means: A drop-in replacement of the classic K-means with consistent speedup. In ICML, pages 579–587, 2015

    2015

  10. [18]

    Doan and J

    T. Doan and J. Kalita. Predicting run time of classification algorithms using meta-learning. Int. J. Mach. Learn. Cybern. , 8(6):1929–1943, 2017

    1929

  11. [19]

    J. Drake. Faster k-means Clustering. In MS Thesis, 2013

    2013

  12. [20]

    Eggensperger, M

    K. Eggensperger, M. Lindauer, and F. Hutter. Neural networks for predicting algorithm runtime distributions. In IJCAI, pages 1442–1448, 2018

    2018

  13. [21]

    C. Elkan. Using the triangle inequality to accelerate k-means. In ICML, page 147–153, 2003

    2003

  14. [22]

    Y . Fan, P. Rich, W. E. Allcock, M. E. Papka, and Z. Lan. Trade-off between prediction accuracy and underestimation rate in job runtime estimates. In CLUSTER, pages 530–540, 2017

    2017

  15. [23]

    Y . Gao, Y . Liu, H. Zhang, Z. Li, Y . Zhu, H. Lin, and M. Yang. Estimating GPU memory consumption of deep learning models. In FSE, pages 1342–1352, 2020

    2020

  16. [24]

    B. R. Gunnarsson, S. vanden Broucke, and J. D. Weerdt. A direct data aware LSTM neural network architecture for complete remaining trace and runtime prediction. IEEE Trans. Serv. Comput. , 16(4):2330–2342, 2023

    2023

  17. [25]

    Y . Guo, H. Wang, Q. Hu, H. Liu, L. Liu, and M. Bennamoun. Deep Learning for 3D Point Clouds: A Survey. IEEE Transactions on Pattern Analysis and Machine Intelligence , pages 1–1, 6 2020

    2020

  18. [26]

    G. Hamerly. Making k-means even faster. In SDM, pages 130–140, 2010

    2010

  19. [27]

    Hamerly and J

    G. Hamerly and J. Drake. Accelerating Lloyd’s Algorithm for k-Means Clustering. 2015

    2015

  20. [28]

    W. He, Z. Jiang, M. Kriby, Y . Xie, X. Jia, D. Yan, and Y . Zhou. Quantifying and reducing registration uncertainty of spatial vector labels on earth imagery. In KDD, pages 554–564, 2022

    2022

  21. [29]

    K. Heo, H. Oh, and H. Yang. Resource-aware program analysis via online abstraction coarsening. In ICSE, pages 94–104, 2019

    2019

  22. [30]

    Q. Hu, B. Yang, L. Xie, S. Rosa, Y . Guo, Z. Wang, N. Trigoni, and A. Markham. RandLA-Net: Efficient Semantic Segmentation of Large- Scale Point Clouds. In CVPR, pages 11105–11114, 2020

    2020

  23. [31]

    Hutter, L

    F. Hutter, L. Xu, H. H. Hoos, and K. Leyton-Brown. Algorithm runtime prediction: Methods and evaluation (extended abstract). In Q. Yang and M. J. Wooldridge, editors, IJCAI, pages 4197–4201, 2015

    2015

  24. [32]

    Jayasumana, R

    S. Jayasumana, R. I. Hartley, M. Salzmann, H. Li, and M. T. Harandi. Kernel methods on riemannian manifolds with gaussian RBF kernels. IEEE Trans. Pattern Anal. Mach. Intell. , 37(12):2464–2477, 2015

    2015

  25. [33]

    Kapus and C

    T. Kapus and C. Cadar. A segmented memory model for symbolic execution. In FSE, pages 774–784, 2019

    2019

  26. [34]

    Kleindessner, P

    M. Kleindessner, P. Awasthi, and J. Morgenstern. Fair k-Center Clus- tering for Data Summarization. In ICML, 2019

    2019

  27. [35]

    Krulis and M

    M. Krulis and M. Kratochv ´ıl. Detailed analysis and optimization of CUDA k-means algorithm. In ICPP, pages 69:1–69:11, 2020

    2020

  28. [36]

    I. Lang, A. Manor, and S. Avidan. SampleNet: Differentiable point cloud sampling. In CVPR, pages 7578–7588, 2020

    2020

  29. [37]

    Leyton-Brown, E

    K. Leyton-Brown, E. Nudelman, and Y . Shoham. Empirical hardness models: Methodology and a case study on combinatorial auctions. J. ACM, 56(4):22:1–22:52, 2009

    2009

  30. [38]

    Y . Li, K. Zhao, X. Chu, and J. Liu. Speeding up k-Means algorithm by GPUs. Journal of Computer and System Sciences , 79:216–229, 2013

    2013

  31. [39]

    S. P. Lloyd. Least squares quantization in PCM. IEEE Transactions on Information Theory, 28(2):129–137, 1982

    1982

  32. [40]

    C. Lv, W. Lin, and B. Zhao. Approximate intrinsic voxel structure for point cloud simplification. IEEE Trans. Image Process., 30:7241–7255, 2021

    2021

  33. [41]

    Mariam, A

    S. Mariam, A. Chew, and C. Meng. Density Based Clustering for 3D Object Detection in Point Clouds. In CVPR, pages 10608–10617, 2020

    2020

  34. [42]

    Maulud and A

    D. Maulud and A. M. Abdulazeez. A review on linear regression comprehensive in machine learning. Journal of Applied Science and Technology Trends, 1(2):140–147, 2020

    2020

  35. [43]

    F. Mohr, M. Wever, A. Tornede, and E. H ¨ullermeier. Predicting machine learning pipeline runtimes in the context of automated machine learning. IEEE Trans. Pattern Anal. Mach. Intell. , 43(9):3055–3066, 2021

    2021

  36. [44]

    A. W. Moore. The Anchors Hierarchy: Using the Triangle Inequality to Survive High Dimensional Data. In UAI, pages 397–405, 2000

    2000

  37. [45]

    Newling and F

    J. Newling and F. Fleuret. Fast k-means with accurate bounds. In ICML, pages 936–944, 2016

    2016

  38. [46]

    Newling and F

    J. Newling and F. Fleuret. K-Medoids For K-Means Seeding. In NIPS, pages 5201–5209, 2017

    2017

  39. [47]

    S. M. Omohundro. Five Balltree Construction Algorithms. Technical report, 1989

    1989

  40. [48]

    Pedregosa, G

    F. Pedregosa, G. Varoquaux, A. Gramfort, V . Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V . Dubourg, J. Vander- Plas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duch- esnay. Scikit-learn: Machine learning in python. J. Mach. Learn. Res. ...

    2011

  41. [49]

    C. R. Qi, H. Su, K. Mo, and L. J. Guibas. PointNet: Deep Learning on Point Sets for 3D Classification and Segmentation. In CVPR, pages 652–660, 2017

    2017

  42. [50]

    C. R. R. A Dual-Tree Algorithm for Fast k-means Clustering With Large k. In SDM, pages 300–308, 2017

    2017

  43. [51]

    Roynard, J

    X. Roynard, J. E. Deschaud, and F. Goulette. Paris-Lille-3D: A large and high-quality ground-truth urban point cloud dataset for automatic segmentation and classification. International Journal of Robotics Research, 37(6):545–557, 2018

    2018

  44. [52]

    Ry ˇsav´y and G

    P. Ry ˇsav´y and G. Hamerly. Geometric methods to accelerate k -means algorithms. In SDM, pages 324–332, 2016

    2016

  45. [53]

    J. Shao, H. Zhang, Y . Mao, and J. Zhang. Branchy-GNN: a Device-Edge Co-Inference Framework for Efficient Point Cloud Processing. Technical report, 2020

    2020

  46. [54]

    X. Su, X. Yan, and C.-L. Tsai. Linear regression. Wiley Interdisciplinary Reviews: Computational Statistics , 4(3):275–294, 2012

    2012

  47. [55]

    X. Sun, H. Ma, Y . Sun, and M. Liu. A Novel Point Cloud Compression Algorithm Based on Clustering. IEEE Robotics and Automation Letters, 4(2):2132–2139, 2019

    2019

  48. [56]

    W. Tang, N. Desai, D. Buettner, and Z. Lan. Analyzing and adjusting user runtime estimates to improve job scheduling on the blue gene/p. In IPDPS, pages 1–11, 2010

    2010

  49. [57]

    Tuero and M

    J. Tuero and M. Buro. Bayes distnet - A robust neural network for algorithm runtime distribution predictions. In AAAI, pages 12418– 12426, 2021

    2021

  50. [58]

    Verbauwhede, C

    I. Verbauwhede, C. J. Scheers, and J. M. Rabaey. Memory estimation for high level synthesis. In DAC, pages 143–148, 1994

    1994

  51. [59]

    C. Wang, L. Gong, F. Jia, and X. Zhou. An FPGA based accelerator for clustering algorithms with custom instructions. IEEE Trans. Computers, 70(5):725–732, 2021

    2021

  52. [60]

    S. Wang, Z. Bao, J. S. Culpepper, and G. Cong. A survey on trajectory data management, analytics, and learning. ACM Comput. Surv., 54(2):39:1–39:36, 2022

    2022

  53. [61]

    S. Wang, Y . Sun, and Z. Bao. On the Efficiency of K-Means Clustering: Evaluation, Optimization, and Algorithm Selection. PVLDB, 14(2):163– 176, 2021

    2021

  54. [62]

    Wilson, W

    B. Wilson, W. Qi, T. Agarwal, J. Lambert, J. Singh, S. Khandelwal, B. Pan, R. Kumar, A. Hartnett, J. K. Pontes, D. Ramanan, P. Carr, and J. Hays. Argoverse 2: Next generation datasets for self-driving perception and forecasting. CoRR, abs/2301.00493, 2023

    2023 arXiv

  55. [63]

    Wortsman, G

    M. Wortsman, G. Ilharco, S. Y . Gadre, R. Roelofs, R. G. Lopes, A. S. Morcos, H. Namkoong, A. Farhadi, Y . Carmon, S. Kornblith, and L. Schmidt. Model soups: averaging weights of multiple fine-tuned models improves accuracy without increasing inference time. In ICML, volume 16...

    2022

  56. [64]

    S. Xia, D. Peng, D. Meng, C. Zhang, G. Wang, E. Giem, W. Wei, and Z. Chen. A Fast Adaptive k-means with No Bounds. IEEE Transactions on Pattern Analysis and Machine Intelligence , pages 1–1, 2020

    2020

  57. [65]

    Xu and G

    X. Xu and G. Hee Lee. Weakly Supervised Semantic Point Cloud Segmentation: Towards 10x Fewer Labels. In CVPR, pages 13706– 13715, 2020

    2020

  58. [66]

    X. Yin, Y . Sasaki, W. Wang, and K. Shimizu. 3D Object Detection Method Based on YOLO and K-Means for Image and Point Clouds. Technical report, 2020

    2020

  59. [67]

    T. Yu, W. Zhao, P. Liu, V . Janjic, X. Yan, S. Wang, H. Fu, G. Yang, and J. Thomson. Large-scale automatic k-means clustering for heterogeneous many-core supercomputer. IEEE Trans. Parallel Distributed Syst. , 31(5):997–1008, 2020

    2020

  60. [68]

    J. Yuan, Y . Zheng, C. Zhang, W. Xie, X. Xie, G. Sun, and Y . Huang. T-drive: Driving directions based on taxi trajectories. In GIS, pages 99–108, 2010. VIII. A PPENDIX A. Complexity Analysis We analyze the time complexity of the proposed pruning mechanism. We first analyze th...

    2010

Pith tools

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