Parallel Metric Skip Lists and Nearest Neighbor Search Conference: 38th ACM Symposium on Parallelism in Algorithms and Architectures; July 6–10, 2026; London, United Kingdom 38th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA ’26), July 6–10, 2026, London, United Kingdom DOI: 10.1145/3816782.3819182 ISBN: 979-8-4007-2761-0/26/07 CCS: Theory of computation Parallel algorithms CCS: Theory of computation Data structures design and analysis CCS: Theory of computation Nearest neighbor algorithms

Xiangyun Ding, Rohin Garg, Yan Gu, Yihan Sun · 2026

Read Parallel Metric Skip Lists and Nearest Neighbor Search Conference: 38th ACM Symposium on Parallelism in Algorithms and Architectures; July 6–10, 2026; London, United Kingdom 38th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA ’26), July 6–10, 2026, London, United Kingdom DOI: 10.1145/3816782.3819182 ISBN: 979-8-4007-2761-0/26/07 CCS: Theory of computation Parallel algorithms CCS: Theory of computation Data structures design and analysis CCS: Theory of computation Nearest neighbor algorithms by Xiangyun Ding, Rohin Garg, Yan Gu, Yihan Sun (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-03129.txt.

Introduction

Ding, Garg, Gu, and Sun give fast parallel algorithms to build metric skip lists. A metric skip list supports nearest neighbor search in metric spaces. For data with a fixed expansion rate, it builds in near-linear time and answers queries fast. It needs no bound on aspect ratio, which makes it more flexible than rivals.

The catch is that its standard build is a step-by-step chain, so no parallel version was known. The team finds new insights that improve the sequential build itself. Those insights open a divide-and-conquer route to parallelism. Under the same expansion rate premise, their build has expected work near n log n. Its span is polylogarithmic with high chance. These include closest pair search, density-based clustering, and k-nearest-neighbor graph building. The authors say many of these are first results with both work efficiency and low span.

Catalog record

CREATORXiangyun Ding, Rohin Garg, Yan Gu, Yihan Sun
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE95 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.03129

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Parallel Metric Skip Lists and Nearest Neighbor Search Conference: 38th ACM Symposium on Parallelism in Algorithms and Architectures; July 6–10, 2026; London, United Kingdom 38th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA ’26), July 6–10, 2026, London, United Kingdom DOI: 10.1145/3816782.3819182 ISBN: 979-8-4007-2761-0/26/07 CCS: Theory of computation Parallel algorithms CCS: Theory of computation Data structures design and analysis CCS: Theory of computation Nearest neighbor algorithms Xiangyun Ding, Rohin Garg, Yan Gu, Yihan Sun Abstract . The metric skip list is a data structure designed for efficient nearest and k k -nearest neighbor search in metric spaces. For many real-world datasets with reasonable distributions—specifically, those with a constant expansion rate —it supports O ~ ​ ( n ) \tilde{O}(n) construction time and O ⁡ ( k ​ log ⁡ n ) O(k\log n) query time, where n n is the input size and k k is the number of nearest neighbors in queries. Notably, unlike alternative approaches, it does not require a bounded aspect ratio, making it more flexible for input data distributions. However, the inherently sequential nature of its original construction has, to our knowledge, precluded any existing parallel algorithm. In this paper, we present highly parallel and work-efficient algorithms for constructing metric skip lists. Under the assumption of a constant expansion rate, our approach achieves an expected work of O ⁡ ( n ​ log ⁡ n ) O(n\log n) and a polylogarithmic span with high probability. Our design is based on novel algorithmic insights that improves the sequential procedure, enabling a divide-and-conquer strategy that facilitates parallelism while maintaining efficiency. With our algorithms, we can also support improved bounds for relevant applications using nearest neighbor as building blocks, including bichromatic closest pair (BCP), density-based clustering, and k k -NN graph construction, among others. To our knowledge, many of these results represent the first solutions to achieve both work efficiency and polylogarithmic span, relying solely on the assumption of a constant expansion rate. † † cc-license: by Original Cover Tree and Its Parallel Version Metric Skip Lists Proposed in Beygelzimer et al. ( 8 ) ; analysis later corrected by Curtin ( 20 ) and Elkin and Kurlin ( 22 ) Karger and Ruhl ( 42 ) Assumptions for the stated bounds Constant expansion rate, and bounded aspect ratio Only constant expansion rate Sequential Construction Time O(n\log n) O(n\log n\log\log n) whp ( 42 ) . Improved to O(n\log n) expected [this paper] Nearest Neighbor Search Time O(\log n) O(\log n\log\log n) whp ( 42 ) . Improved to O(\log n) expected [this paper] Parallel Construction Work O(n\log n) expected ( 31 ) O(n\log n) expected [this paper] Parallel Construction Span O(\log^{3}n\log\log n) whp ( 31 ) O(\log^{3}n) whp [this paper] Table 1. Comparison between cover trees and metric skip lists for exact NNS in metric spaces. The stated bounds assume a constant expansion rate; the cover-tree bounds additionally use a bounded aspect ratio. For both data structures, the assumptions are needed for the displayed asymptotic bounds, not for correctness: without them, both still find exact nearest neighbors, but the expansion rate and the aspect ratio (for cover trees) appear in the cost bounds. 1. Introduction Nearest neighbor search (NNS) is a fundamental algorithmic primitive with extensive applications in computational geometry, computer graphics, machine learning, computer vision, and various other fields within artificial intelligence. In many practical scenarios, the distance between two points is defined using measures other than the standard Euclidean metric and L_{p} norm. Commonly employed alternatives include cosine similarity (related to angular distance), Jaccard distance ( 40 ) (set-based similarity), tree/graph distances, Mahalanobis distance ( 47 ) , and Earth Mover’s Distance ( 57 ) . All these distance measures satisfy specific properties (defined in section 2 ) and can be generalized to metric spaces . Many efficient data structures ( 42 ; 58 ; 44 ; 15 ; 8 ; 39 ; 22 ; 31 ) have been developed specifically for NNS in metric spaces. Unfortunately, finding (or even approximating) nearest neighbors in general metrics requires linear time ( 6 ; 8 ) . Therefore, most of these data structures rely on assumptions regarding a “good” data distribution to achieve high efficiency. Two widely-studied properties include low expansion rate, which indicates that the density of points in the metric space changes smoothly, and bounded aspect ratio, which indicates that the scale of the dataset (maximum vs. minimum distance) is bounded. We define these two concepts formally in section 2 . Under certain assumptions, the two canonical theoretical data structures for exact NNS in metric spaces are the metric skip list introduced by Karger and Ruhl in 2002 ( 42 ) and the cover tree proposed by Beygelzimer et al. in 2006 ( 8 ) . Their best-known bounds are shown in table 1 . The cover tree was long regarded as the standard theoretical solution for NNS in metric spaces since 1) its construction and query bounds are better by a factor of O(\log\log n) where n is the input size, and 2) it has a work-efficient parallel version with polylogarithmic span ( 31 ) . However, in addition to a low expansion rate, the cover tree also assumes a bounded aspect ratio 1 1 1 A recent work ( 23 ) showed a sequential cover tree variant without this assumption; to our knowledge, no parallel version of this variant or easy fix of ( 31 ) is known. for both the original cover tree ( 8 ) and its parallel version ( 31 ) . This assumption can be strong: in L_{p} metrics, even a simple quad/octree can achieve the same construction and query bounds assuming a bounded aspect ratio ( 9 ) . By contrast, metric skip lists only assume a constant expansion rate to achieve their theoretical guarantees. Therefore, this gap motivates a natural question for NNS: for metric skip lists, can we achieve the same construction time (work) as cover trees, as well as high parallelism (polylogarithmic span), while maintaining their flexibility of solely relying on the basic low expansion rate assumption? This would make metric skip list a theoretically powerful building block for NNS queries, enabling downstream applications to achieve strong bounds under minimal assumptions. However, designing such an efficient and parallel solution remained open. In this paper, we answer this question affirmatively. In particular, we present new algorithms for metric skip lists that achieve the same O(n\log n) work as cover trees (modulo randomization) for construction with polylogarithmic span, as well as the same asymptotic query bounds, under weaker assumptions. We note that achieving the strong cost bounds, both in work (overcoming the O(\log\log n) overhead) and span (achieving parallelism), is highly non-trivial. Several factors contribute to this difficulty. The first reason is that the original sequential algorithm itself is substantially complicated. The algorithm given in the original paper ( 42 ; 58 ) requires O(n\log n\log\log n) work, which incurs an O(\log\log n) factor overhead as compared to cover trees. While that paper shared some high-level ideas regarding the possibility of achieving an efficient construction with O(n\log n) work, no algorithmic details or formal analysis were provided. Hence, the first major contribution of this paper is to

Read the complete text