Conceptio › Archive › arXiv CS

arXiv CSopen access

In-memory Multidimensional Indexing Using the skd-tree

2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

data-management databases storage

databases, sql, data management, storage

In-memory Multidimensional Indexing Using the skd-tree Achilleas Michalopoulos

Dept. of Comp. Sci. and Engineering Ioannina, Greece [email protected]

Dimitrios Tsitsigkos

arXiv:2605.03640v1 [cs.DB] 5 May 2026

Abstract In this paper, we revisit the problem of indexing multi-dimensional data in memory for the efficient support of multi-dimensional range queries and nearest neighbor queries. This is a classic problem in main-memory databases, where there is a need for indexing multiple columns simultaneously. Established data structures include the R-tree, kd-tree, quad-tree, and grid-based partitioning. More recently, multi-dimensional learned indexes have also been proposed to address this problem. We propose slicing kd-tree (skd-tree), a variant of the kd-tree, where each node partitions the space of its subtree into multiple slices across a single splitting dimension. By compressing the splitters of the partitions and with the help of data-parallelism, we (i) radically reduce the number of levels of the tree and (ii) limit the number of computations required for multi-dimensional range and proximity queries. The nodes of the skd-tree resemble the nodes of a main-memory B+ -tree, however, a different dimension is used at each level. Our novel range and 𝑘NN algorithms on the skd-tree apply only a small constant number of SIMD instructions at each node during tree traversal. Our contributions also include a novel top-down construction algorithm, different types of inner and leaf nodes that warrant tree balancing, and a novel update algorithm. Our skd-tree achieves strong performance compared to existing methods, according to our experimental evaluation on real and synthetic datasets.

Code Available at: https://github.com/achmichalop/skd-tree_2027

Nikos Mamoulis

Archimedes, Athena RC Dept. of Comp. Sci. and Engineering 48 Athens, GreeceOur Greece Ourmkd-tree mkd-treewith withIoannina, 48points points [email protected] [email protected] Traditional mkd-tree with 48 points

Introduction

Multi-dimensional range filtering is a core operation in analytical database engines. The goal is to retrieve the tuples from a table that simultaneously satisfy range predicates in multiple attributes. Typically, the filtering attributes are not many, so multi-dimensional indices for low-dimensional spaces (e.g., kd-trees, quadtrees, Rtrees) are considered the standard way to index and search across multiple attributes. In spatial databases, proximity queries, such as 𝑘 nearest neighbor (𝑘NN) search are also prominent; besides, 𝑘NN queries are used for similarity search and as a module of data mining algorithms (clustering, classification). Given the growth in memory sizes of commodity machines and the capacity of modern processors for data parallelism, modern database systems offer in-memory indexing solutions. Besides adapting B-trees or tries for one-dimensional indexing in memory [17, 45, 62, 68, 77, 87, 88], there have also been efforts in modernizing multi-dimensional index structures such as R-trees and kd-trees for data-parallel and/or multi-core processing in memory [51, 64]. There is also work on workload-aware multi-dimensional indexing

y y

y y 85 85 80 80

y 20 40 2052 40 52

55 55 50 50 45 45

80 50 80

32 32 30 30 26 26 22 22 13 13

45 45 30 30

20 20

40 4052 52

(a) 2-d points

x x

85 85 50 50

32 40

80 80 55 55

32 32 26 26 13 13 20 20 52 52 20 20 40 40 40 52 40 52 40 22 22

x x

40 50

(b) skd-tree (ours)

30 30

Figure 1: Multiway kd-trees [55, 75], where index partitions are determined considering the distribution of the expected query workload. Our proposal. Existing memory-based multi-dimensional data structures suffer from pointer chasing and branch mispredictions. In this paper, we propose a slicing kd-tree, briefly skd-tree, which achieves branchless search per accessed node and balanced partitioning. The structure of skd-tree is illustrated in Figure 1(b) for a set of 2-d points shown in Figure 1(a). We divide the space recursively by alternating dimensions (as in the kd-tree), but we perform 𝑚-way partitioning in a single splitting dimension at each node (𝑚=4 in the figure). In addition, we do not use points to define boundaries; all data are stored at the leaves of the tree (in this example, we assume that each leaf gets 3 points). Each node divides the data in its subtree to multiple partitions that get (almost) the same number of points. This can be done after computing quantiles along the split dimension for the space to be partitioned and using these quantiles to define separators. For example, in Figure 1(b), the 0.25, 0.50, 0.75 quantiles of the 𝑥-values are used to divide the space into four partitions corresponding to the children of our skd-tree’s root; for each partition, the 0.25, 0.50, 0.75 quantiles of the 𝑦-values that fall in them are used to recursively split the partition. Novelty and contributions. 1 Each node of our skd-tree splits its subspace across a single dimension. This facilitates search within a single node by a small constant number of SIMD operations. In previous multi-way kd-trees [8, 58, 66], each node is split in multiple dimensions, as illustrated in Figure 1(c), which limits data-parallelism. 2 We propose novel data-parallel algorithms for multidimensional search and 𝑘NN queries, which exploit the skd-tree structure. 3 We apply an adaptive quantization scheme to compress the splitters within each skd-tree node, effectively increasing node fanout and, in turn, reducing storage requirements, tree height, and search cost. Inner tree nodes can be of variable capacities, even at the same level. The novelty of our node compression is that it does not only adapt to the data (unique prefixes of splitters), but it also decides the level of compression based on a target number of splits, aiming at a balanced tree. 4 To cope with ties and data skew, we introduce three types of leaf nodes (light, heavy, and outlier) that help to maintain balance and improve the robustness of the structure. 5 We present a novel top-down construction algorithm, which

Achilleas Michalopoulos, Dimitrios Tsitsigkos, and Nikos Mamoulis

adaptively determines the number of splits at each node, to achieve a balanced, high-performance skd-tree. 6 We propose a novel update algorithm, which postpones restructuring and reconstruction by exploiting heavy and outlier leaves. To the best of our knowledge, this is the first work that integrates all these functionalities in a high-performance cache-conscious multidimensional index for main memory data. We conduct an experimental evaluation with real and synthetic datasets, varying distribution and dimensionality, where we compare skd-tree against state-of-the-art conventional and learned multidimensional indices, including the boost.org R-tree implementation, which was shown to be the most robust in-memory multi-dimensional index in a recent experimental study [49]. The result show that skd-tree consistently outperforms the runner up by 1.5x-2x in range and 𝑘NN queries, while being several times faster in updates. We also show that its search performance remains robust even after a large number of updates, as opposed to bulk-loaded R-trees and compressed multi-dimensional indices [85]. Outline Section 2 presents related work. Section 3 presents the structure of our skd-tree, query processing algorithms, and the skdtree construction algorithm. Updates on the skd-tree are discussed in Section 4. Section 5 presents our experimental evaluation and Section 6 concludes the paper.

2 2.1

Related Work Conventional multidimensional indices

The R-tree family. The popular multidimensional access method is the R-tree [32, 35], a height-balanced structure similar to a B+ tree where each node stores a set of minimum bounding rectangles (MBRs) that cover either actual objects in leaf nodes or in the corresponding child subtrees in internal nodes. Over the years, many variants, such as the R+-Tree [69], the R*-Tree [13], and the Priority R-Tree [11], bulk-loading methods [39, 46, 53, 60], and optimizations [14, 41] have been proposed to improve its performance. Recently, Rayhan and Aref [64] accelerate R-tree queries using SIMD instructions to vectorize intersection tests and traversal operations. kd-trees. Kd-trees represent another major class of multidimensional indices. Classic kd-trees [15, 16] recursively split space along alternating axes. The K-D-B-tree [66] combines kd-tree space partitioning with the disk-based B+ -tree structure, storing bounding rectangles in region pages and data points in point pages. The BKD-tree [58] improves the K-D-B-tree by maintaining multiple static trees and incrementally rebuilding selected trees to efficiently handle large datasets. Cache-oblivious kd-trees [8] use recursive layouts to preserve spatial locality and reduce memory transfers. The iKD-tree [20] extends kd-trees to support incremental updates without full reconstruction. Parallel implementations of kd-trees have also been explored. ParGeo [81] provides scalable parallel kd-tree construction and spatial partitioning. The BDL-tree [84] is a parallel batchdynamic kd-tree that combines ideas from BKD-trees and cacheoblivious kd-trees, maintaining multiple static trees of exponentially increasing sizes and rebuilding only the necessary trees for highthroughput batch updates. Reif and Neumann [65] propose scalable multi-dimensional range joins using kd-trees with parallel space

partitioning. The CGAL C++ library (www.cgal.org) implements kdtrees for fast nearest-neighbor and range searches with support for parallel construction, though dynamic updates require full rebuilds. The Pkd-tree [51] further improves cache efficiency and parallelism by supporting parallel construction, batch updates, and queries such as 𝑘 nearest neighbor, range, and range-count. Parallel kd-tree construction algorithms typically fall into two categories: one class [19, 21, 82] sorts all points in every dimension before construction and splits using medians, while the other group [9, 22, 36, 65, 71] computes medians on the fly during each recursive split. Other multi-dimensional indices. Grid-based indexing is popular for highly-dynamic low-dimensional points, such as moving objects [52, 63, 72]. On the other hand, grids cannot guarantee balanced partitioning and low worst-case cost. Quadtrees [28] are 2-d hierarchical space-partitioning structures that recursively subdivide space into quadrants for fast insertion and range queries, while octrees [50, 67] extend this principle to three dimensions by subdividing nodes into eight regions. Unlike R-trees and kd-trees, quadtrees are not balanced, so searching in dense regions can be expensive. Grids and quadtree-based structures do not scale well beyond 3 dimensions. More recently, the UB-tree [12, 61] generalizes B-trees for multidimensional indexing by mapping objects to a single ordered domain. The PH-tree [85] combines bitwise partitioning with Patricia-trie compression to provide predictable performance, low memory usage, and efficient access patterns. Sprenger et al. [73] show that hardware-conscious designs—such as cache-friendly layouts and SIMD-aware traversal—significantly outperform traditional indexes, and they propose the BB-tree [74], a space-efficient main-memory index that combines a m-way search tree with a linearized, cache-optimized layout and bubble-bucket leaf architecture to buffer updates and reduce expensive reorganizations. Comparison to our skd-tree. The SIMD R-tree [64] compares entire boxes at each node, limiting the level of parallelism. On the other hand, our skd-tree splits using only one dimension per node and compares one dimension per level, allowing larger fanout and considering more children per SIMD instruction. Besides, the SIMD R-tree was implemented and tested only for 2-d data, while skdtree supports points of arbitrary dimensionality. Finally, as opposed to the skd-tree, the SIMD R-tree it does not support 𝑘NN queries and adaptive node compression. Previous kd-tree variants that use multiple splitters per node [8, 58, 66] do not split across the same dimension at each node; hence, the number of branches that could be examined by a single SIMD instruction is limited. The Pkd-tree [51] focuses on milti-threaded processing of batches of queries and not on data-parallelism in the evaluation of a single query.

2.2

Multi-Dimensional Learned Indexing

An early multidimensional learned index is the ZM-Index [78], which simply maps multidimensional points to a Z-order curve and employs 1-d learned indexing [42, 43]. ML-Index [24] is a multidimensional learned index that extends iDistance [38]. The Learned KD-tree [57] extends replaces classic kd-tree splitting with learned models. Wang and Xu proposed the Hilbert Model (HM) index [80], which maps multidimensional data to one dimension using the Hilbert curve. RSMI (Recursive Spatial Model Index) [59] recursively partitions multidimensional space and trains models at each

In-memory Multidimensional Indexing Using the skd-tree

partition. LISA [48] partitions space into grid cells and uses models to map multidimensional points into a linear order, ensuring monotonicity between cells. Flood [55] partitions multidimensional data by a grid which uses 𝐷-1 dimensions, where 𝐷 is the data dimensionality; it then trains a 1-d model on the left-out dimension in each grid cell. Tsunami [25] extends Flood to optimize the index structure for a known query workload. SPRIG [86] uses adaptive grids and spatial (two-dimensional) interpolation functions as learned models to directly predict the position of a spatial search key. The IF-Index (IFI) [34] replaces leaf-node search in a standard R-tree by a model to predict the locations of points which are included in a query range. RW-Tree [26] and AI+R-Tree [10] are learned, workload-aware R-trees. LMSFC [29] leverages learned monotonic space-filling curves to enhance query efficiency, while Wazi [56] introduces workload-aware z-indexing that dynamically adapts to access patterns. SLBRIN [79] combines historical and current ranges, using learned models to support fast spatial queries and efficient updates. The RLR-Tree [31] incorporates reinforcement learning to optimize R-tree construction and query performance, and COAX [33] emphasizes correlation-aware indexing by learning inter-dimensional relationships, achieving high efficiency on complex, correlated datasets. Refs. [47, 49] provide comprehensive evaluations of multidimensional learned indices vs. traditional indices. Based on these studies, the most robust non-learned multidimensional indices are the boost R-tree implementation and the kd-tree, which we also include in our evaluation (Section 5), together with the best performing learned indices (IFI, Flood). Learned indices perform well in range queries, but they lose to the kd-tree in 𝑘NN search; in addition, they have high construction cost and limited support of updates.

2.3

Data-parallel, main-memory indexing

There are several data-parallel implementations of B-trees [30]. The first work in this direction was a SIMD-ified m-way search algorithm (find which out of m partitions contains a search key) [68]. FAST [40] optimizes m-way tree search by leveraging cache locality, SIMD parallelism on CPUs, and GPU-parallelism. B+ -trees for GPU and SIMD architectures were proposed in [44, 70, 83]. Finally, the recently proposed B𝑆 -tree [77] aligns each node to a small number of cache lines that can be processed in parallel. Branching at each node is performed by a small number of SIMD operations (one operation per cache line). Unused slots at the end of nodes have as key a maximum value MAXVAL, while gaps in the middle take the next used key in the node, to facilitate fast search and updates. Comparison to skd-tree. Although both the B𝑆 -tree [77] and our skd-tree use SIMD instructions in search, there are significant differences between them. The B𝑆 -tree supports equality and range queries on a single attribute, whereas skd-tree supports multidimensional range queries and 𝑘NN queries. The B𝑆 -tree splits the same single dimension hierarchically (many times), but the skd-tree splits a different dimension per level. The search algorithms are essentially different, as queries on the skd-tree traverse multiple paths and the pending accesses are organized in a (priority) queue. Two operations are needed per accessed node in the mkd-tree (for the upper and lower query bounds in that dimension), but only one is used in the B𝑆 -tree. The B𝑆 -tree applies frame-of-reference (FOR)

compression at the leaves, which requires reconstruction of keys during search. On the other hand, the mkd-tree uses a prefix compression technique at inner nodes that requires no reconstruction of key values during search. The construction algorithms of the two structures are different, since skd-tree is constructed in a top-down manner and compression is not only based on unique prefixes but also on balancing demands. Updates are simple in the 1-d B𝑆 -tree, however, in skd-tree, splits do not propagate upwards, so we apply reconstruction of subtrees. The skd-tree uses three different types of leaf nodes that store uncompressed points, while the leaf nodes of the B𝑆 -tree have the same structure as its inner nodes. Finally, The B𝑆 -tree only supports unique keys, but the skd-tree handles points, which may have ties in one or more dimensions.

skd-tree

This section presents skd-tree, a multi-dimensional index designed to efficiently handle 𝐷-dimensional data. We first describe the basic structure of the skd-tree, which adapts to modern memory hierarchies, focusing on cache-aware node layouts and data-parallel query processing using SIMD intrinsics. We show how to reduce the precision of splitters to increase node fanout, producing more compact trees with shorter traversal paths. Search algorithms for range and 𝑘NN queries are then presented. Finally, we present a novel top-down bulk-loading algorithm for the skd-tree which achieves a balanced structure. For the ease of presentation, we assume that all dimensions take as values 64-bit unsigned integers; however, our approach can be generalized for other attribute types (e.g., doubles).

3.1

The skd-tree structure

The skd-tree generalizes the binary kd-tree by allowing each internal node to hold multiple splitters in the same dimension instead of a single splitter. An internal node 𝑣 with maximum fanout 𝑓 stores up to 𝑓 − 1 splitters that partition the data space of the subtree rooted at 𝑣 into 𝑓 partitions across a dimension. The splitting dimension alternates across consecutive tree levels, as in the classical kd-tree. The leaves of the tree store up to 𝐶 data points, where 𝐶 is a predefined maximum leaf capacity. Figure 2 shows the structure of the skd-tree for the data plotted in Figure 1(a) (𝐶 = 3). The root splits the x dimension into 𝑓 = 4, using 𝑓 − 1 = 3 splitter values in the x domain, based on the 0.25, 0.5, and 0.75 quantiles of the total order of the points in the x dimension. Then, each child of the root, which spans a vertical stripe is split recursively based on the 0.25, 0.5, and 0.75 quantiles of the y-order of the points in the stripe. Finally, each leaf includes the points in the corresponding partition and their minimum bounding box (MBB). For example, the first leaf includes all the points in the partition at the lower-left part of the space in Figure 1(b). Note that non-leaf nodes store splitters across a single dimension, whereas each leaf node stores the complete set of points in the corresponding partition. The skd-tree built from a set of 𝑁 D-dimensional points has a height 𝑂 (log 𝑓 (𝑁 /𝐶)), as opposed to a binary kd-tree (with 𝐶 points at each leaf) that would have a 𝑂 (log2 (𝑁 /𝐶)) height; hence, a reduced number of nodes are visited along a search path. Each node stores its 𝑓 − 1 splitters in a contiguous memory block (e.g., an array), and memory is fetched in cache lines (e.g., of 64 bytes). The choice of maximum fanout 𝑓 has a direct impact on performance: if

Mkd-tree Achilleas Michalopoulos, Dimitrios Tsitsigkos, and Nikos Mamoulis

Splitting Dimension (SP) = x

SP = y

e a

h g

22 50 85 ∞

30 45 80 ∞

l k

…

∞

3.2

30 55 80 ∞

…

13 26 32 ∞

…

Figure 2: The skd-tree structure for the data in Figure 1(d) type (e.g., N64)

SP = y 𝐁 !"# 𝐁 !$% 𝐵%!"# 𝐵%!$% 𝐵&!"# 𝐵&!$%

ax bx cx

ay by cy

30 45 80 ∞

a.rid b.rid c.rid

...

Figure 3: skd-tree node layout 𝑓 is relatively small, all splitters fit within a single cache line, maximizing memory efficiency, but the tree becomes taller, requiring more node visits. If 𝑓 is larger, the tree height is reduced, but nodes may span multiple cache lines, increasing memory accesses and resulting in more cache misses. Layout of inner nodes Our implementation of the skd-tree uses a cache-friendly inner node layout; node capacity (i.e., maximum fanout 𝑓 ) is set such that all splitters fit within a single cache line. On 64-bit systems, if each coordinate of a data point is represented as 8 bytes (e.g., a double or 64-bit integer), a 64-byte cache line can store up to 8 elements. To fully utilize this space, each internal node stores an array of up to seven splitters. Unused slots at the end of the array are filled with an upper bound of the domain in the splitting dimension, denoted as MAXVAL (and shown as ∞ in Figure 2). We also store an array of 8 pointers, each holding the address of the corresponding child node, aligned to the splitters. This way, we can achieve a maximum node fanout 𝑓 = 8. Layout of leaf nodes Each leaf node stores 𝐷 coordinate vectors in a structure-of-arrays (SoA) layout (columnar representation). That is, for each dimension 𝑑 there is a vector holding the values of all points in that dimension. There is also a vector with the record ids of all points in the leaf, to potentially access other attributes of query results. All these vectors are aligned; hence, values in the same position correspond to the same point (data object). Two more vectors B𝑚𝑖𝑛 and B𝑚𝑎𝑥 hold the bounding box of the points in the leaf. Node occupancy meta-data are kept in both inner and leaf nodes. Figure 3 exemplifies the skd-tree node layout for an excerpt of the tree shown in Figure 2, which includes the leftmost inner node above the leaves and the first leaf node, containing points 𝑎, 𝑏, and 𝑐. The inner node includes two vectors holding the splitters (upper array) and node pointers (lower array). It also includes a variable indicating the type of the node (N64, N32, or N16), to be explained in Section 3.2. The leaf node includes two vectors with the coordinates of the points in the 𝑥 and 𝑦 coordinate (dimension 0 and 1, respectively), a record ids vector, and the two bounding box vectors B𝑚𝑖𝑛 and B𝑚𝑎𝑥 .

Compressed splitters and increased fanout

The fanout of our skd-tree is limited by the requirement that all splitters of an internal node must fit within a single cache line of 64 bytes. We suggest the use of compressed splitters, which trade numerical precision for a higher fanout while still fitting within a single cache line. The key idea is to store the most significant bits of each splitter, up to the bit position where the set of kept prefixes of all splitters does not contain duplicates. This way, we can increase the number of splitters per node without increasing memory usage. We support two additional node layouts based on this idea. In the single-precision layout (N32), each splitter becomes a 32-bit (unsigned) integer having the 32 most significant bits of the original splitter, considering only the bit positions from the first one where the largest original splitter in the node has a 1. With this layout, an internal node can store up to 15 splitters plus one MAXVAL entry in a single cache line, which doubles the maximum fanout compared to N64 (𝑓 becomes 16). In the half-precision layout (N16), only the 16 most significant bits of each splitter are kept, supporting maximum fanout 𝑓 up to 32. The N32 and N16 layouts reduce tree height and traversal depth, while all layouts have the same search cost per node, since the SIMD operations that we use (to be discussed in the next section) support 64-bit, 32-bit, and 16-bit data types. On the other hand, the use of compressed splitters does not guarantee even partitioning of the data, as when using uncompressed 64-bit splitters, because padding 0’s at their end does not result in the original 64-bit splitter. This potential issue of imbalance and how to address it is discussed in Section 3.4, where we choose between the N64, N32, and N16 layouts during skd-tree construction.

3.3

Query processing

The skd-tree supports range queries and 𝑘 nearest neighbor (𝑘NN) searches. We now present efficient processing algorithms for these queries, which exploit the cache-friendly node layout of the skd-tree and data-level parallelism enabled by SIMD-based query evaluation. 3.3.1 Range Query Let P ⊂ R𝐷 be a set of data points in a 𝐷dimensional space. Each point p ∈ P is represented as p = (𝑝 0, 𝑝 1, . . . , 𝑝 𝐷 −1 ). A range query is an axis-aligned hyper-rectangle, whose lower and upper bounds are defined by the following vectors: 𝑚𝑖𝑛 𝑚𝑖𝑛 q𝑚𝑖𝑛 = [𝑞𝑚𝑖𝑛 0 , 𝑞 1 , . . . , 𝑞 𝐷 −1 ],

q𝑚𝑎𝑥 = [𝑞𝑚𝑎𝑥 , 𝑞𝑚𝑎𝑥 , . . . , 𝑞𝑚𝑎𝑥 0 1 𝐷 −1 ]

The result of range query 𝑅𝑄 (q𝑚𝑖𝑛 , q𝑚𝑎𝑥 ) is defined as follows: 𝑅𝑄 (q𝑚𝑖𝑛 , q𝑚𝑎𝑥 ) = {p ∈ P |q𝑚𝑖𝑛 ≤ p ≤ q𝑚𝑎𝑥 }, where q ≤ p is vector-wise inequality, i.e., 𝑞𝑖 ≤ 𝑝𝑖 , ∀𝑖 ∈ [0, 𝐷). Traversal is performed in breadth-first order (BFS) using a queue 𝑄 to store nodes to be examined. For each internal node, evaluation is accelerated using SIMD intrinsics, as summarized in Algorithm 1. Initially, the node’s splitters are loaded into a SIMD register (splitters_vec, line 1), and the bounds of the query along the current splitting dimension 𝑑 are broadcast to SIMD registers (qmin_vec and qmax_vec, lines 2–3). Data parallel comparisons (lines 4–5) find which splitters lie below or above the query bounds, producing masks (mask_min and mask_max). The popcount of these masks (lines 6–7) identifies the indices of the first and last child whose subtree may contain points in the query range (startPos and endPos,

In-memory Multidimensional Indexing Using the skd-tree

ALGORITHM 1: SIMD-based range search (inner nodes)

ALGORITHM 2: SIMD-based range search (leaf nodes)

: Internal node 𝑣 , query bounds [𝑞𝑚𝑖𝑛 , 𝑞𝑚𝑎𝑥 ] in 𝑣 ’s splitting 𝑑 𝑑 dimension 𝑑 , queue 𝑄 Output : Queue 𝑄 updated with child nodes intersecting the query 1 𝑠𝑝𝑙𝑖𝑡𝑡𝑒𝑟𝑠 _𝑣𝑒𝑐 ← load (𝑣.𝑠𝑝𝑙𝑖𝑡𝑡𝑒𝑟𝑠 ) ; 𝑚𝑖𝑛 ) ; 2 𝑞𝑚𝑖𝑛 _𝑣𝑒𝑐 ← broadcast (𝑞 𝑑 𝑚𝑎𝑥 ) ; 3 𝑞𝑚𝑎𝑥 _𝑣𝑒𝑐 ← broadcast (𝑞 𝑑 4 𝑚𝑎𝑠𝑘 _𝑚𝑖𝑛 ← compare_ge (𝑞𝑚𝑖𝑛 _𝑣𝑒𝑐, 𝑠𝑝𝑙𝑖𝑡𝑡𝑒𝑟𝑠 _𝑣𝑒𝑐 ) ; 5 𝑚𝑎𝑠𝑘 _𝑚𝑎𝑥 ← compare_ge (𝑞𝑚𝑎𝑥 _𝑣𝑒𝑐, 𝑠𝑝𝑙𝑖𝑡𝑡𝑒𝑟𝑠 _𝑣𝑒𝑐 ) ; 6 𝑠𝑡𝑎𝑟𝑡𝑃𝑜𝑠 ← popcount (𝑚𝑎𝑠𝑘 _𝑚𝑖𝑛) ; 7 𝑒𝑛𝑑𝑃𝑜𝑠 ← popcount (𝑚𝑎𝑠𝑘 _𝑚𝑎𝑥 ) ; 8 for 𝑖 = 𝑠𝑡𝑎𝑟𝑡𝑃𝑜𝑠 to 𝑒𝑛𝑑𝑃𝑜𝑠 do 9 𝑄.add (𝑣.𝑐ℎ𝑖𝑙𝑑𝑃𝑡𝑟 [𝑖 ] ) ;

: Leaf node 𝑣 with 𝐷 coordinate vectors 𝑋 0 , ..., 𝑋𝐷 −1 , range query 𝑅𝑄 (q𝑚𝑖𝑛 , q𝑚𝑎𝑥 ) , result set 𝑆 Output : Result set 𝑆 updated with all points in the leaf satisfying the query 1 𝑙𝑒𝑎𝑓 𝐶𝑎𝑝𝑎𝑐𝑖𝑡 𝑦 ← 𝑣.𝑠𝑙𝑜𝑡𝑢𝑠𝑒 ; 2 𝑛𝑢𝑚𝐵𝑙𝑜𝑐𝑘𝑠 ← 𝑙𝑒𝑎𝑓 𝐶𝑎𝑝𝑎𝑐𝑖𝑡 𝑦/𝑆𝐼 𝑀𝐷𝑊 𝑖𝑑𝑡ℎ ; 3 Initialize 𝑚𝑎𝑠𝑘𝑠 [0..𝑛𝑢𝑚𝐵𝑙𝑜𝑐𝑘𝑠 − 1] ← all bits set; 4 for 𝑑 = 0 to 𝐷 − 1 do 5 if 𝑞𝑚𝑖𝑛 ≤ 𝑣.𝐵𝑑𝑚𝑖𝑛 and 𝑞𝑚𝑎𝑥 ≥ 𝑣.𝐵𝑑𝑚𝑎𝑥 then 𝑑 𝑑 6 continue ⊲ 𝑣.B contained in q in dimension 𝑑 ;

Input

7 8 9

respectively). Finally, lines 8–9 add the corresponding child nodes to queue 𝑄, to schedule visiting the relevant subtrees. Leaf nodes are similarly evaluated using SIMD-based columnar operations (Algorithm 2). The points in a leaf 𝑣 are processed in SIMD-sized blocks. We first initialize an array 𝑚𝑎𝑠𝑘𝑠 with one bitvector per block to signify that each point is a result (all bits are set to 1). Then, for each dimension 𝑑, we find which points are included in the projected query range to 𝑑. If 𝑣’s bounding box projection to dimension 𝑑, i.e., [𝑣.𝐵𝑑𝑚𝑖𝑛 , 𝑣.𝐵𝑑𝑚𝑎𝑥 ], is included in the query range, then we know that all points are results with respect to that dimension, so dimension 𝑑 is skipped (Lines 5-6). Otherwise, the query bounds in 𝑑 are broadcast into SIMD registers (qmin_vec and qmax_vec, Lines 7-8), and each block of coordinates is loaded into a SIMD vector (x_vec, line 11). Data parallel comparisons (Lines 12–13) produce masks identifying which points in the block lie within the query interval along that dimension. These masks are combined across dimensions using bitwise AND operations (line 14) to produce a final mask per block, marking points that are fully contained in the hyper-rectangle. Finally, lines 15-21 iterate over the set bits in each mask. The global index of each point is computed as offset + idx, where 𝑜 𝑓 𝑓 𝑠𝑒𝑡 = 𝑏 · SIMDWidth and idx is the position of the bit in the mask. Each point is reconstructed from the columnar vectors using getPoint(offset + idx) and added to the result set 𝑆. SIMD operations maximize throughput by processing multiple coordinates within the same block in parallel. 3.3.2 𝑘NN search Let P ⊂ R𝐷 be a set of data points in a 𝐷dimensional space, and let q ∈ R𝐷 be a query point. A 𝑘 nearest neighbor (𝑘NN) query retrieves the subset of 𝑘 points in P that minimize the squared Euclidean distance to q: ∑︁ 𝑘𝑁 𝑁 (q, 𝑘) = arg min ∥p − q∥ 2, 𝑆 ⊂ P, |𝑆 |=𝑘

p∈𝑆

where the squared Euclidean distance between points p and q is ∥p − q∥ 2 =

𝐷 −1 ∑︁

(𝑝𝑖 − 𝑞𝑖 ) 2 .

𝑖=0

Search Strategy The 𝑘NN search follows a best-first traversal (Best-Bin-First), guided by lower-bound distance estimates [54]. Two auxiliary heaps are used during the process: (i) a min-heap 𝐿 enabling access to tree entries by their minimum distance to the query and (ii) a fixed-size max-heap 𝐻 that stores the current 𝑘 nearest neighbors. The maximum distance in 𝐻 (i.e., the distance of the top element in 𝐻 ) is used as a global pruning threshold

10 11 12 13 14

𝑞𝑚𝑖𝑛 _𝑣𝑒𝑐 ← broadcast (𝑞𝑚𝑖𝑛 ); 𝑑 𝑞𝑚𝑎𝑥 _𝑣𝑒𝑐 ← broadcast (𝑞𝑚𝑎𝑥 ); 𝑑 for 𝑏 = 0 to 𝑛𝑢𝑚𝐵𝑙𝑜𝑐𝑘𝑠 − 1 do 𝑜 𝑓 𝑓 𝑠𝑒𝑡 ← 𝑏 · 𝑆𝐼 𝑀𝐷𝑊 𝑖𝑑𝑡ℎ ; 𝑥 _𝑣𝑒𝑐 ← load (𝑋𝑑 , 𝑜 𝑓 𝑓 𝑠𝑒𝑡 ) ; 𝑚𝑎𝑠𝑘 _𝑙𝑒 ← compare_ge (𝑥 _𝑣𝑒𝑐, 𝑞𝑚𝑖𝑛 _𝑣𝑒𝑐 ) ; 𝑚𝑎𝑠𝑘 _𝑔𝑒 ← compare_le (𝑥 _𝑣𝑒𝑐, 𝑞𝑚𝑎𝑥 _𝑣𝑒𝑐 ) ; 𝑚𝑎𝑠𝑘𝑠 [𝑏 ] ← 𝑚𝑎𝑠𝑘𝑠 [𝑏 ] AND (𝑚𝑎𝑠𝑘 _𝑙𝑒 AND 𝑚𝑎𝑠𝑘 _𝑔𝑒 ) ;

for 𝑏 = 0 to 𝑛𝑢𝑚𝐵𝑙𝑜𝑐𝑘𝑠 − 1 do 𝑚𝑎𝑠𝑘 ← 𝑚𝑎𝑠𝑘𝑠 [𝑏 ] ; 17 𝑜 𝑓 𝑓 𝑠𝑒𝑡 ← 𝑏 · 𝑆𝐼 𝑀𝐷𝑊 𝑖𝑑𝑡ℎ ; 18 while 𝑚𝑎𝑠𝑘 ≠ 0 do 19 𝑖𝑑𝑥 ← index of least-significant set bit in 𝑚𝑎𝑠𝑘 ; 20 𝑆.add ( getPoint (𝑜 𝑓 𝑓 𝑠𝑒𝑡 + 𝑖𝑑𝑥 ) ) ; 21 Clear least-significant set bit in 𝑚𝑎𝑠𝑘 ;

𝑏𝑜𝑢𝑛𝑑. Initially, 𝑏𝑜𝑢𝑛𝑑 is set to infinity until 𝑘 points have been found. Any entry in 𝐿 whose distance exceeds 𝑏𝑜𝑢𝑛𝑑 is skipped, effectively pruning regions that cannot contain closer neighbors. Heap Entries Each entry in the min-heap 𝐿 is represented as a tuple ⟨𝑣, 𝑖𝑑𝑥, 𝑡𝑦𝑝𝑒, 𝑑𝑖𝑠𝑡, 𝛿⟩, where 𝑣 is a pointer to a tree node, 𝑖𝑑𝑥 is a child or splitter index, 𝑡𝑦𝑝𝑒 ∈ {NODE, GROUP} denotes whether the entry represents a single child or a group of children. The value 𝑑𝑖𝑠𝑡 is the accumulated squared Euclidean distance and 𝛿 is a vector of per-dimension projection distances used to update distance bounds efficiently. Both 𝑑𝑖𝑠𝑡 and 𝛿 are computed incrementally during the query process. For the max-heap 𝐻 , entries are represented as tuples ⟨𝑝𝑜𝑖𝑛𝑡, 𝑑𝑖𝑠𝑡⟩, where 𝑑𝑖𝑠𝑡 is the squared Euclidean distance from the query q for a point located inside a leaf node of the skd-tree. Internal Node Processing & Grouping When examining an internal node, search is guided by its splitting dimension 𝑑, and a point query is performed between the node’s splitters and 𝑞𝑑 using SIMD intrinsics to identify the child containing the query coordinate. This child has zero projection distance along dimension 𝑑 (i.e., 𝛿𝑑 = 0) and is immediately pushed to heap 𝐿 as a NODE entry. The remaining subspaces, which lie on either side of coordinate 𝑞𝑑 , are summarized into at most two GROUP entries: one representing the subspaces to the left of 𝑞𝑑 and one for the subspaces to the right. Each group stores the minimum projection distance needed to reach that region, postponing unnecessary distance computations and heap operations. This approach ensures that only potentially relevant subspaces are explored, improving efficiency while maintaining correctness. When a GROUP entry is extracted from heap 𝐿, the closest child in that group is enheaped first as a NODE entry. Any remaining children are reinserted into 𝐿 forming a new GROUP entry with updated 𝛿 and 𝑑𝑖𝑠𝑡 respectively. Leaf Node Processing When a leaf node is reached during the 𝑘NN search, the squared Euclidean distances between the query

Achilleas Michalopoulos, Dimitrios Tsitsigkos, and Nikos Mamoulis

ALGORITHM 3: SIMD-based 𝑘NN search Input : Tree root, query point q, number of neighbors 𝑘 Output : Set of 𝑘 nearest neighbors 1 Initialize empty min-heap 𝐿 ; 2 Initialize empty max-heap 𝐻 with capacity 𝑘 ; 3 𝑏𝑜𝑢𝑛𝑑 ← ∞; 4 Initialize projection vector 𝛿 ← 0; 5 𝐿.push ( ⟨𝑟𝑜𝑜𝑡, 0, NODE, 0, 𝛿 ⟩ ) ; 6 while 𝐿 is not empty do 7 ⟨𝑣, 𝑖𝑑𝑥, 𝑡 𝑦𝑝𝑒, 𝑑𝑖𝑠𝑡, 𝛿 ⟩ ← 𝐿.pop ( ) ; 8 if 𝐻 is full AND 𝑑𝑖𝑠𝑡 ≥ 𝑏𝑜𝑢𝑛𝑑 then 9 break; if 𝑣 is a leaf then ∀ point ∈ 𝑣 compute sq. distance to q using SIMD; Insert candidate points into 𝐻 ; if 𝐻 is full then 𝑏𝑜𝑢𝑛𝑑 ← 𝐻 .top.𝑑𝑖𝑠𝑡 ;

10 11 12 13 14

continue;

if 𝑡 𝑦𝑝𝑒 = NODE then Let 𝑑 be the splitting dimension of 𝑣 ; Use SIMD to locate the child subspace containing 𝑞𝑑 ; Push this child as a NODE entry with 𝛿𝑑 = 0; Create up to two GROUP entries for subspaces left and right of 𝑞𝑑 ; Compute their minimum projection distances and push them to 𝐿 ;

else

16 17 18 19 20

23 24 25

Select the closest child within the group; Push it as a NODE entry into 𝐿 ; Reinsert remaining children as a reduced GROUP entry with updated (𝑑𝑖𝑠𝑡, 𝛿 ) ;

return 𝐻 ;

point q and all points in the leaf are computed. Since leaf contents are organized in a structure-of-arrays (SoA) layout, distances are computed in a dimension-wise manner using SIMD intrinsics. Specifically, each query coordinate is broadcast into a SIMD register, while blocks of point coordinates are loaded from the corresponding columnar arrays. For each block, squared differences are accumulated using combined multiply-add operations, producing a SIMD vector of squared distances. This process continues until distances for all points in the leaf have been computed. Each point is then considered for insertion into the max-heap 𝐻 , which maintains the current set of 𝑘 nearest neighbors. Algorithm 3 summarizes 𝑘NN search. For simplicity, we present the high-level 𝑘NN traversal logic and omit the explicit SIMD intrinsics in this pseudocode. These operations either reuse the same SIMD comparison patterns illustrated in Algorithms 1 and 2 or are replaced by analogous SIMD arithmetic primitives (e.g., vectorized subtraction, multiplication, and accumulation).

3.4

skd-tree construction

We propose a top-down construction algorithm for the skd-tree which is both effective and efficient. Recall that, as in the kd-tree, a different dimension is used to split each level of the skd-tree. However, nodes are multiway and may have different fanouts (i.e., N64, N32, and N16 nodes). This allows the mkd-tree to adapt and keep balanced: if a split results in imbalanced partitions (due to ties in values in the splitting dimension or imprecision of the compressed splitters), the partitions can use different node types. Partitions that contain more data can use nodes with larger fanout (e.g., N16), while partitions with less data can use nodes with smaller fanout (e.g., N64). For leaf nodes, we empirically set the capacity

𝐶=128, a value that reduces number of tree levels while facilitating processing of multiple points in parallel. We first have to determine the order in which the dimensions are split. More uniform dimensions with more unique values should be selected first, to facilitate compression of splitters and balanced subtrees . Hence, we rank the dimensions according to their degree of uniformity (or spread) and based on the number of unique values in the data per dimension. Once the dimension order is established, we proceed with the construction. Our goal is to form leaf nodes whose bounding boxes are hypercubes, as this is well suited for queryagnostic workloads [13, 46]. To this end, we determine the number of splits to apply along each dimension. Let 𝑁 be the total number of data points in the 𝐷-dimensional space, and let 𝐶 be the leaf capacity threshold. We first estimate the number of leaf nodes as 𝑃 = ⌈𝑁 /𝐶⌉. The target number of splits for the first dimension is then estimated as 𝑆 = 𝑃 1/𝐷 . This value represents the desired number of partitions along that dimension and serves as an upper bound on the fanout of nodes that split on it. The estimated value 𝑆 guides the selection of the node type. If 𝑆 ≤ 8, we exclusively use N64 nodes for this dimension, as their maximum fanout is 8. If 𝑆 > 8, we consider the possible options of N64, N32, and N16 nodes, and select the option whose fanout most closely matches the desired number of partitions. However, if 𝑆 > 8 and it is not possible to achieve unique splitters by a N16 or N32 compression scheme, we split into 𝑆/2 child nodes and keep the dimension for a possible new split at a level below. Determining the Splitters To construct the splitters for a node, we generate candidate split boundaries using a recursive median selection approach. Specifically, we first compute the median 𝑚 of the points along the chosen dimension (this can be done fast using the median-of-medians algorithm or by computing the median of a small data sample). Then, we quantize 𝑚 (if we aim for a N32 or N16 node), by right bit-shifting. Finally, we apply one step of quicksort to crack [37] the subarray containing the points into two parts using 𝑚 (after padding it with an appropriate number of zeros in the end if 𝑚 is compressed). After partitioning, we apply the same procedure recursively to the largest piece of the cracked points array, until the target number of splitters has been reached. This procedure is applied iteratively to construct inner nodes. During the median selection and cracking process, it is possible that we compute a new (quantized) splitter, which is identical to its next or previous splitter, especially when points have duplicate values in the splitting dimension. In this case, we skip the split of the corresponding cracked array segment and turn to the next largest segment. This may create imbalance to the child subtrees. Another reason why we may have imbalance in the resulting partitions is that when we quantize a splitter, we essentially move the value of the original (uncompressed) splitter to the left. For example, suppose that we quantize value 156 (binary 10011100) by rightshifting it by 4 to become 9 (1001). The quantized splitter (9) will be used as 9 << 4 = 144 in partitioning (and during search), which is much smaller than the original median value (156). To deal with the possible imbalance of partitions at the next level, we adapt the number of splitters per node. Recall that target number of splits at each node is originally 𝑆. We adjust the target number of splits to 𝑆 ′ based how much the number 𝑀 of points to be partitioned at the node deviates from the expected number

In-memory Multidimensional Indexing Using the skd-tree

𝑀𝑒𝑥𝑝 of points that the subtree rooted at that node would get if the data were uniform and exact splitters (as in N64 nodes) were used. Hence, 𝑆 ′ is set to 𝑆 · (𝑀/𝑀𝑒𝑥𝑝 ). If, after applying splitting we end up having fewer than 𝑆 ′ splits (due to splitter ties), the imbalance propagates to (some of) the children and eventually addressed by either an additional round of splits for that dimension, or (in the case of numerous ties in that dimension) by creating outlier (i.e., overflown) leaf nodes, as we will explain now. Leaf types Due to the distribution of the data and the presence of duplicate values in the splitting dimensions, it may not be possible to produce leaves with exactly the same number of points. To accommodate this, we allow leaf nodes to store between 𝐶/2 = 64 and 𝐶 = 128 points. However, a larger than 𝐶 number of duplicates at the splitting dimension above the leaf level may result in larger leaves. Due to this, we relax the basic structure of the skd-tree to include three types of leaf nodes: light, heavy and outlier. We define two thresholds to classify leaves. The heavy threshold, 𝑇h , determines whether a leaf is subject to splitting and is defined as ¯ 𝐶), where 𝐶¯ is the mean capacity of all leaves. 𝑇h = 1.2 · 𝑚𝑎𝑥 (𝐶, The outlier threshold is defined as 𝑇o = 2 · 𝑇h . Leaves which contain between 𝐶/2 and 𝑇h points are characterized as light. Leaves having between 𝑇h and 𝑇o points are characterized as heavy. Finally, leaves with more points than 𝑇o are characterized as outliers. Outlier leaves represent regions with a large number of points with duplicate values in the splitting dimension at the level above. These nodes cannot be further subdivided, because all remaining points share identical coordinates along the splitting dimensions, resulting in zero-width partitions. Consequently, they are treated as terminal nodes in the skd-tree.

4 4.1

Updates Insertion

To insert a new point 𝑝, we traverse the internal levels of the skdtree as if we were searching for 𝑝 to locate the leaf node where 𝑝 should be inserted. The traversal algorithm is similar SIMD-based range search described in Section 3.3.1, however, only one pointer per accessed node is selected (as in a point query) and we end up accessing just one path of the skd-tree. Once the target leaf node is identified, the insertion procedure depends on the leaf type. Light leaf If the leaf is light, the point is simply inserted to the end of the leaf node; that is, for each dimension 𝑑, the value of 𝑝 in that dimension is appended at the end of the corresponding vector and the identifier of 𝑝 is also appended at the end of the id’s vector, such that the vectors are fully aligned to each other. The bounding box (MBB) vector B of the node is also updated. After the insertion the leaf may become heavy. Heavy leaf If 𝑝 is inserted to a heavy leaf, we also append the new point at the end of the corresponding vectors. However, we monitor whether multiple insertions cause the leaf size to exceed the threshold 𝑇o . When this happens, we attempt a split operation to the leaf. For leaf node splitting, we follow two different strategies. If the parent node of the leaf is not full, we perform the split as in a B+ -tree; we find the median value 𝑚 in the leaf based on the parent’s splitting dimension 𝑖, keep points smaller than 𝑚 in dimension 𝑖 the current leaf, create a new leaf with the points greater than or

equal to 𝑚 in dimension 𝑖, and insert the splitter 𝑚 to the parent. If the parent node is of N32 or N16 type, we quantize the splitter before partitioning. Finally, the MBBs of the new leaf nodes are computed. If the parent node does not have an empty slot for an immediate split, we backtrack along the tree path to identify the closest ancestor node 𝑣 that has an empty slot. Once the node is found, we collect all the data in the subtree pointed by the entry of 𝑣 that leads to the split leaf and construct two new subtrees that replace the original one, following the recursive construction algorithm described in Section 3.4. A new splitter is created at node 𝑣 to separate the two new subtrees that replace the old one. There are two cases when a heavy leaf node 𝑙 becomes an outlier node after an attempted split. The first case is when we fail to generate a new unique (quantized) splitter at the parent node 𝑝𝑎𝑟𝑒𝑛𝑡 (𝑙) of the leaf 𝑙 that we attempt to split. This may happen if the parent node is N32 or N16 and there is heavy skew, or when there are many duplicate values in the splitting dimension of 𝑝𝑎𝑟𝑒𝑛𝑡 (𝑙). Then, the new splitter may be identical to the next or the previous splitter in 𝑝𝑎𝑟𝑒𝑛𝑡 (𝑙). The second case is when we fail to generate a new splitter at the closest ancestor node 𝑣 of 𝑙 that has an empty slot, for the same reason. Outlier leaf If the leaf node, where 𝑝 is to be inserted, is characterized as outlier, we do not attempt to split it. As discussed in Section 3.4, further splitting of such nodes is challenging due to the high replication of values in one or more dimensions. Only when the size of an outlier node becomes 21 · 𝑇𝑜 , we attempt a split; if the split fails, the leaf remains an outlier and we attempt again when its size becomes 22 · 𝑇𝑜 , and so on.

4.2

Deletion

Like insertions, deletions first perform point search to locate the leaf node that contains the point 𝑝 to be deleted, using at each accessed node 𝑣 the value of 𝑝 in 𝑣’s splitting dimension. During traversal, SIMD-based comparisons are employed to efficiently find the corresponding tree path, as discussed in Section 3.3.1. Data parallelism enabled by SIMD intrinsics is exploited at the leaf node 𝑙 to perform equality search for 𝑝.𝑖𝑑 in 𝑙’s vector which contains the identifiers of the points there. Assuming that the point 𝑝 to be removed exists, this search finds its position within the leaf. Then, in all vectors (coordinate vectors, id vector), the last values are copied into the position of the deleted point, the node’s occupancy is reduced by one, and its MBB is updated if necessary. After the deletion, an outlier leaf may become heavy, a heavy leaf may become light, and a light leaf may underflow. We do not handle underflows, relaxing the lower bound constraint of light leaves, following previous work (e.g., [62]). The reason is that deletions are expected to be rare compared to insertions, so when a leaf underflows, we expect that it will accept new points in the future and that would address the occupancy requirement. In addition, for in-memory indices, underflows have a much lower impact compared to disk-based access methods. In the edge case where a leaf node becomes completely empty, we delete it and backtrack along the tree path and update the contents of the involved internal nodes.

Achilleas Michalopoulos, Dimitrios Tsitsigkos, and Nikos Mamoulis

Experiments

We experimentally compare skd-tree to alternative main-memory multi-dimensional indices. All methods are implemented in C++ and compiled with gcc (v13) using the flags -O3 and -march=native. The experiments are conducted on a system with an 11th Gen Intel® Core™ i7-11700K processor running at 3.60 GHz, 128 GB of RAM, with AVX-512 support. The operating system used is Ubuntu 22.04. We extend the codebase of Learnedbench [49] to include skd-tree.

5.1

Setup

Datasets We conduct our experiments on standard benchmark datasets of varying dimensionality that have been widely used in previous studies [25, 49, 55]. We consider only numerical dimensions, as in prior work [25, 49, 55, 85], and normalize each dimension to the range [0,1]. The second and third columns of Table 1 summarize the cardinality and dimensionality of the points in each dataset. EDGES [7] is a 2-d dataset containing polygon data from the continental United States; we use polygon centroids to obtain points. TORONTO [76] is a large-scale urban outdoor point cloud dataset with 3-d points collected in Toronto, Canada, using a mobile laser scanning (MLS) system. OOKLA [4] is a 5-d dataset that includes global fixed broadband and mobile network performance metrics. GAIA [2, 23, 27] is a 6-d dataset of nearly two billion Milky Way objects, providing precise astrometric and photometric measurements, along with spectroscopy and derived stellar properties. NYT [3] is an 8-d dataset containing trip records from the New York City Taxi and Limousine Commission. TPC-H [6] is a decision-support benchmark for evaluating database systems on complex analytical workloads. We use it to generate an 8-d dataset by joining the Lineitem, Orders, Partsupp, Customer, and Part tables using their standard foreign-key relationships and selecting numerical attributes from the result. Workloads. For range queries, we execute 1000 hypercube queries on each dataset, retrieving 0.001%, 0.01%, and 0.1% of the indexed points. Query centers are randomly sampled from the data and each dimension is then symmetrically expanded around the selected point until the desired selectivity is achieved. We exclude queries with selectivity of 1% or higher, as they return hundreds of thousands of results in our datasets, which is not representative of a realistic search scenario. For 𝑘NN queries, we randomly select 1000 points from each dataset and use them as query points. We then perform 𝑘NN searches while varying the number 𝑘 of nearest neighbors in {1, 5, 10, 50, 100}. Competitors. We compare our proposed skd-tree with seven conventional and learned multi-dimensional index structures, most of which are implemented in the Learnedbench codebase [49], a benchmarking suite based on the Boost C++ Libraries [1]. We exclude methods shown to perform poorly or inconsistently in prior work [49], as well as those with unavailable or proprietary implementations. Regarding learned indices, we excluded those without publicly available code (e.g., SLBRIN [79], LMSFC [29], WAZI [56], HMI [80]) and those which support only approximate queries (e.g., RSMI [59]) or exhibit poor performance (e.g., ZMI [78], LISA [48]). The first competitor is the strongest performing R-tree (with STR bulk-loading), taken from the Boost C++ Libraries [1], using a

Table 1: skd-tree construction statistics across datasets (rows) and reported structural characteristics (columns) Datasets

Card. (𝑁 )

Dim. (𝐷)

Inner Node Layouts

Avg. Leaf Capacity

Light Leaves [%]

Heavy Leaves [%]

Outlier Leaves [%]

EDGES TORONTO OOKLA GAIA NYT TPC-H

51M 78M 123M 216M 44M 240M

2 3 5 6 8 8

N16 N16/32/64 N16/32/64 N32/64 N64 N64

128.6 123.6 125.5 133.9 128.4 122.5

98.43 ∼99.53 ∼100 100 ∼100 100

1.56 ∼0.47 <0.01 0 <0.01 0

0.01 <0.01 <0.01 0 0 0

fanout of 128 (i.e., the same as the leaf capacity 𝐶 threshold of skdtree). It supports 𝑘NN and range queries and also allows updates. The kd-tree is based on the nanoflann library [18] and natively supports only 𝑘NN queries; we extend it to support range queries using the provided nanoflann interfaces. Adaptive Grid (AG) and Uniform Grid (UG) use the same cell size (128 points per cell) and support only range queries. For AG, we apply the partitioning method described in our skd-tree (Section 3.4) to determine the boundaries of the partitions in each dimension using a sample of the dataset. During range queries, we perform binary search in each dimension to identify the relevant partitions and, ultimately, the grid cells covered by the query. The PH-tree implementation is taken from [5] and integrated into Learnedbench; it supports 𝑘NN and range queries, as well as updates. Finally, we compare against Flood and IF-Index (IFI), two learned indices already included in Learnedbench. We use the default parameter settings of Learnedbench, and both support only range queries. For Flood, each cell contains 2000 points, while for IFI the fanout of inner nodes is 32 and that of leaf nodes is 2000.

5.2

Effectiveness of the skd-tree construction

In the first experiment, we evaluate the effectiveness of the skdtree construction algorithm described in Section 3.4. For this, we collected structural statistics of the skd-tree across each dataset. In particular, we record which of the different internal node layouts (N16, N32, N64) are used during construction. We also measure the average leaf capacity of the produced leaf nodes, along with their categorization into the three leaf types (light, heavy, outlier). All statistics are summarized in Table 1. As shown in the table, EDGES, which is low-dimensional and duplicate values in each dimension are rare, fully exploits compression and includes exclusively N16 nodes. TORONTO and OOKLA use all three node types, effectively compressing some regions with N16 and N32 nodes, while GAIA does not require N16 compression due to its higher dimensionality. The 8-d datasets (NYT and TPC-H) require no compression at all, so they just use N64 nodes. For all datasets, the skd-tree achieves average leaf occupancy consistently close to the target value of 128. In addition, the number of leaf nodes classified as heavy or outliers is negligible across all datasets, indicating that the tree achieves a well-balanced partitioning in practice.

5.3

Impact of compression and data-parallelism

Next, we test the impact of node compression and SIMD-based search in the performance of the skd-tree. Figure 4 presents, for two different datasets, the throughput in queries per second (QPS) of the skd-tree, after turning off compression (NoComp), i.e., enforcing all nodes to be N64, and when using traditional for-loop search at each node (NoSIMD) instead of SIMD intrinsics. Observe that using compression and SIMD improves the throughput of skd-tree in range queries, but SIMD brings insignificant benefit to 𝑘NN search.

In-memory Multidimensional Indexing Using the skd-tree

2 0 Queries Sel.: 0.01%

60 40 20 0

NoComp + SIMD Throughput (QPS) (×104 )

Throughput (QPS) (×102 )

Comp + NoSIMD Throughput (QPS) (×104 )

Throughput (QPS) (×104 )

NoComp + NoSIMD 6

15 10 5 0

Comp + SIMD 4 3 2 1 0

Queries Sel.: 0.01%

10NN

(a) EDGES (𝐷 = 2) (b) EDGES (𝐷 = 2) (c) GAIA (𝐷 = 6) (d) GAIA (𝐷 = 6)

Figure 4: Impact of node layouts and SIMD in skd-tree Table 2: Construction cost (seconds) across all datasets Datasets

skd-tree

kd-tree

R-tree

PH-tree

Flood

IFI

EDGES TORONTO OOKLA GAIA NYT TPC-H

5.07 10.52 23.76 50.07 11.55 71.05

12.54 44.3 356.21 444.26 138.8 1059.66

5.46 10.99 28.04 46.6 10.02 67.84

8.28 23.33 116.5 68.15 31.74 272.08

2.36 3.69 18.65 22.41 6.06 61.52

0.64 1.33 4.15 8.17 2.7 28.27

11.24 20.59 65.35 189.59 33.12 217.01

7.47 14.67 38.94 63.63 14.79 101.52

This is because for 𝑘NN queries much fewer nodes are accessed and the computational bottleneck is mainly due to the management of heaps which is not parallelizable. For the rest of the experiments, we use the default version of our skd-tree, which employs both compression and SIMD-based search, as they are always beneficial.

5.4

Construction Time and Memory Footprint

We compare all tested methods in terms of construction time and memory footprint, when bulk-loaded with each of the real datasets. As shown in Table 2, UG and AG have the lowest construction costs. This is expected, as grids only require simple and fast arithmetic operations to locate the cell to insert a given point. After the grid-based indices, the best methods are skd-tree and the Rtree. skd-tree is marginally faster than the R-tree on half of the datasets, and marginally slower on GAIA, NYT, and TPC-H, which are the datasets with higher dimensionality. This demonstrates the efficiency of skd-tree’s construction algorithm, having comparable cost to an optimized R-tree bulk-loading method, despite being top-down and more complex. Table 3 reports the memory footprint of skd-tree compared with competing index structures across all datasets. As expected, the lowest memory consumption is achieved by grid-based indices (UG and AG), as grids are simple data structures and require memory close to that of the raw data. Flood is a learned index that is built on top of a grid structure and also exhibits low memory consumption. Compared to UG, AG, and Flood, skd-tree uses up to 30% more memory. When compared to the kd-tree, skd-tree incurs a moderate memory overhead ranging from 17.3% on EDGES to 27% on TPC-H. This overhead is mainly due to the additional storage required to maintain a bounding box for each leaf and metadata for the whole nodes of skd-tree. Finally, skd-tree consistently outperforms the R-tree and the PH-tree in terms of memory usage, reducing memory consumption by 36–39% compared to the R-tree and by 73–92% compared to the PH-tree across all datasets.

5.5

Range queries

In this section, we compare all tested methods with respect to their range query throughput. As shown in Figure 5, skd-tree exhibits remarkable robustness in range query performance, which is not affected by the data dimensionality and the query selectivity.

Table 3: Memory footprint (GB) across all datasets Datasets

skd-tree

kd-tree

R-tree

PH-tree

Flood

IFI

EDGES TORONTO OOKLA GAIA NYT TPC-H

0.95 2.30 5.81 11.93 3.27 18.54

0.81 1.86 4.75 9.90 2.71 14.60

1.55 3.58 9.39 19.69 5.40 29.22

11.84 26.14 33.29 58.54 13.45 68.67

0.77 1.76 4.62 9.68 2.65 14.35

2.65 4.68 9.21 17.71 4.30 23.30

The best relative performance is observed on EDGES (Fig. 5a), where the skd-tree best exploits compression, using only N16 inner nodes. In most of the experiments, the runner up method is the optimized boost R-tree, which is 1.6x-3x times slower than the skd-tree. Across all datasets, the performance of competing indexes varies notably with dimensionality and selectivity. UG exhibits acceptable throughput only on very low-dimensional data (EDGES) but its performance degrades sharply as dimensionality increases, making it unsuitable for higher-dimensional datasets. AG has better relative performance than UG, which drops with the data dimensionality. Flood, kd-tree, and IFI have stable performance across all datasets with small fluctuations. PH-tree shows limited throughput on lowdimensional datasets, with performance improving slightly as the number of dimensions increases. In TORONTO and OOKLA, for less selective queries (0.1%), the learned indices (Flood and IFI) outperform the R-tree; this is due to the fact that their predictions at the leaf nodes are more accurate compared to explicit search. However, in most cases, learned indices underperform; adding this to the facts that (i) to update them requires expensive model re-training, (ii) they are not appropriate for 𝑘NN search, and (iii) they outperform the R-tree only when the queries compute tens of thousands of results or more, hints against using multidimensional learned indices. Table 4 presents hardware performance counters for range queries. skd-tree achieves the lowest values in Instructions, Cycles, and Branch Misses, highlighting its superior performance and the effectiveness of the SIMD-based search strategy. Additionally, skd-tree exhibits the lowest number of L1 cache misses, demonstrating the efficiency of its memory access patterns and overall structure. Table 4: Hardware performance counters per range query EDGES (𝐷 = 2) - Queries Selectivity: 0.01% Events Instr. Cycles L1 Misses Br. Misses

skd-tree

kd-tree

R-tree

PH-tree

Flood

IFI

110K 95K 6.8K 614

361K 390K 11.9K 1.1K

257K 200K 7.4K 1.12K

756K 1.38M 28K 6.4K

233K 170K 7.1K 1.4K

308K 233K 7.5K 1.5K

378K 382K 11K 1K

360K 237K 7.7K 2.5K

GAIA (𝐷 = 6) - Queries Selectivity: 0.01% Events

skd-tree

kd-tree

R-tree

PH-tree

Flood

IFI

Instr. Cycles L1 Misses Br. Misses

2.57M 3.08M 152K 21K

4.15M 14.9M 362K 49K

7.31M 7.74M 225K 75K

7.94M 17M 337K 66.6K

9.04M 6.99M 343K 43.8K

71.5M 46.3M 2.77M 206K

6.69M 8.84M 302K 141K

11.5M 10.4M 298K 132K

5.6 𝑘NN queries This section compares skd-tree against kd-tree, R-tree, and PH-tree, with respect to their 𝑘NN query throughput. These are the only competitors in our analysis that support NN search. As shown in Figure 6, skd-tree consistently outperforms all competitors, except for a few cases in the NYT dataset, where it marginally loses to the R-tree. For the great majority of queries, the R-tree is the runner up;

Achilleas Michalopoulos, Dimitrios Tsitsigkos, and Nikos Mamoulis

skd-tree

kd-tree

R-tree

PH-tree

Flood

IFI

104 102

0.001

0.01

Queries Selectivity (%)

100

0.1

103 102 101 0.001

0.001

0.01

Queries Selectivity (%)

102 101 100

0.1

0.001

102 101 0.001

(d) GAIA (𝐷 = 6)

0.01

0.1

Queries Selectivity (%) (c) OOKLA (𝐷 = 5)

103

100

0.1

0.01

Queries Selectivity (%)

103

(b) TORONTO (𝐷 = 3)

104

Throughput (QPS)

(a) EDGES (𝐷 = 2)

100

102

Throughput (QPS)

100

104

Throughput (QPS)

104

0.01

102 101 100

0.1

Queries Selectivity (%)

103

0.001

(e) NYT (𝐷 = 8)

0.01

0.1

Queries Selectivity (%) (f) TPC-H (𝐷 = 8)

Figure 5: Throughput in queries per second (QPS) of skd-tree vs. competitor indices

skd-tree

kd-tree

R-tree

PH-tree

104 102 100

Nearest Neighbors

104 102 100

100

Throughput (QPS)

106

102 1

Nearest Neighbors

(d) GAIA (𝐷 = 6)

Nearest Neighbors

100

104 102 100

Nearest Neighbors

100

Nearest Neighbors

Throughput (QPS)

104

100

102

(b) TORONTO (𝐷 = 3)

Throughput (QPS)

(a) EDGES (𝐷 = 2)

104

100

104 102 100

(e) NYT (𝐷 = 8)

Nearest Neighbors

(f) TPC-H (𝐷 = 8)

Figure 6: Performance comparison of skd-tree with kd-tree, R-tree, and PH-tree for 𝑘NN queries however, the kd-tree outperforms the R-tree on datasets of low dimensionality and when 𝑘 = 1. As we already saw from the previous experiment, the kd-tree is not competitive in range queries, being a few times slower than our skd-tree. The PH-tree is the worst performing method in almost all cases. Overall, skd-tree consistently excels for a variety of data distributions and dimensionalities and across all values of 𝑘. In Table 5, we present the hardware performance counters for 𝑘NN queries. Overall, we observe a similar trend to that of range queries. However, the number of branch misses for skd-tree is slightly higher than for the kd-tree. This is expected, as skd-tree requires additional conditions to determine whether a popped heap

entry corresponds to a leaf, an internal node, or a group of nodes during the 𝑘NN search (see Algorithm 3, lines 10, 16, and 22). Despite this, skd-tree maintains competitive performance across the remaining metrics, indicating that the additional comparisons introduce only a minor overhead and do not offset the benefits of its overall design. Table 5: Hardware performance counters per 𝑘NN query EDGES (𝐷 = 2) - 10NN Events Instr. Cycles L1 Misses Br. Misses

GAIA (𝐷 = 6) - 10NN

skd-tree

kd-tree

R-tree

PH-tree

skd-tree

kd-tree

R-tree

PH-tree

30.5K 22.1K 171 130

26.6K 27.5K 302 106

73.4K 48.1K 698 451

41.7K 40.5K 265 239

139.8K 126.4K 3.42K 375

94.5K 278.7K 5.67K 255

218.5K 194.6K 4.86K 2.71K

273.9K 238.7K 3.55K 1.59K

In-memory Multidimensional Indexing Using the skd-tree

5.7

Updates

We evaluate the behavior of skd-tree under mixed workloads that combine insertions, deletions, and queries, comparing it with Rtree and PH-tree, the only indices in our set supporting dynamic updates; the remaining indices are omitted due to lack of plug-andplay update support. Workload setup. Insertions and deletions are applied to a fraction of the initial dataset, varying from 5% to 30% for insertions and 1% to 6% for deletions. Queries consist of 1000 hypercube queries and 1000 query points, with a selectivity of 0.01% and 𝑘 = 10 for 𝑘NN searches. Updates are split into five equal-sized batches, and queries are executed after each batch. For each scenario, we measure the total execution time and break it down into three components: insertion, deletion, and query time. This approach allows us to observe not only the overall performance but also the contribution of each operation to total cost. Performance comparison. Figure 7 shows the performance of all tested methods across all datasets and mixed workload scenarios. skd-tree consistently achieves the lowest total execution time across all configurations. Its performance remains stable as update intensity increases and continues to scale favorably with higher dimensionality. Remarkably, the skd-tree is several times to one order of magnitude faster than the R-tree on data with dimensionality 5 or higher. This illustrates the deterioration of the optimized boost R-tree index in workloads that include updates. The PH-tree is more robust to updates on datasets of higher dimensionality, but performs poorly when 𝐷 is 2 or 3. skd-tree structure under updates. To interpret skd-tree’s robustness, we collect structural statistics, including the average leaf capacity, number of leaf nodes, and leaf-type categorization (light, heavy, outlier) before and after an update scenario. Table 6 summarizes these statistics for the EDGES and GAIA datasets under low-intensity (10% insertions - 2% deletions) and high-intensity (30% insertions - 6% deletions) scenarios. Overall, the skd-tree exhibits a stable and controlled structural adaptation, with only gradual changes in its organization as update intensity increases. In the low-intensity scenario, the structure remains largely unchanged. The number of leaf nodes is preserved, as a result of the strategies we analyzed in Section 4. The average leaf capacity increases slightly, showing that new insertions are accommodated within existing leaves rather than causing extensive splitting or redistribution (a small shift from light to heavy leaves, while outlier leaves remain negligible). In the high-intensity scenario, structural changes are more visible but remain controlled. GAIA maintains a nearly constant number of leaves, while EDGES shows a moderate increase, indicating additional splits. The average leaf capacity increases more noticeably in both datasets; observe a clear shift from light to heavy leaves. Despite this reorganization, outlier leaves remain rare, demonstrating that the structure avoids imbalance even under heavy updates. Impact of updates on query performance. Table 7 compares query performance between the initial and final batches across all methods. A clear difference emerges between skd-tree and the competitors. In skd-tree, query times remain almost unchanged across both batches and datasets, indicating that updates have little

Table 6: skd-tree structural characteristics across the EDGES and GAIA datasets under different update scenarios 10% Insertions - 2% Deletions Datasets EDGES GAIA

Avg. Leaf Capacity

# Leaves

Light Leaves [%]

Heavy Leaves [%]

Outlier Leaves [%]

Initial

Final

Initial

Final

Initial

Final

Initial

Final

Initial

Final

128.7 133.87

140.13 145.77

355K 1.45M

98.68 100

92.47 99.64

∼1.32 0

∼7.53 0.36

< 0.01 0

30% Insertions - 6% Deletions Datasets EDGES GAIA

Avg. Leaf Capacity

# Leaves

Light Leaves [%]

Heavy Leaves [%]

Outlier Leaves [%]

Initial

Final

Initial

Final

Initial

Final

Initial

Final

Initial

Final

127.76 124.73

131.32 165.07

278K 1.21M

363K 1.23M

99.98 100

95.19 46.37

0.02 0

4.69 53.63

0 0

0.12 0

Table 7: Queries execution time under different update scenarios. We report the initial and final query batches for the EDGES and GAIA datasets 10% Insertions - 2% Deletions Initial Batch Query Time [sec]

Final Batch Query Time [sec]

Datasets

skd-tree

R-tree

PH-tree

skd-tree

R-tree

PH-tree

EDGES GAIA

0.016 0.611

0.05 2.216

0.265 3.188

0.017 0.634

0.05 3.818

0.32 3.533

30% Insertions - 6% Deletions Initial Batch Query Time [sec]

Final Batch Query Time [sec]

Datasets

skd-tree

R-tree

PH-tree

skd-tree

R-tree

PH-tree

EDGES GAIA

0.014 0.536

0.038 2.28

0.237 2.647

0.019 0.796

0.058 6.787

0.378 3.625

impact on the structure relevant to query processing. In contrast, R-tree and PH-tree consistently show higher query times in the final batch, with the effect becoming stronger as update intensity increases. This reflects how updates affect structural quality. skdtree preserves leaf organization and access efficiency over time, maintaining stable traversal costs. In contrast, R-tree and PH-tree gradually lose partitioning quality, reducing pruning efficiency and increasing query cost in later batches.

5.8

Scalability

In the last experiment, we study the scalability of the tested methods to the data size and dimensionality, using synthetic datasets (uniformly and normally distributed) for range queries and 𝑘NN queries. We apply the same setup as the previous experimental sections, using range selectivity 0.01% and 𝑘 = 10. Gaussian datasets were generated by choosing a random point as the mean of the distribution and using as standard deviation in each dimension a random number between 5% and 30% of the dimension’s domain. We exclude IFI and PH-tree from these experiments, as they run out of memory in some experimental settings. We first fix the dimensionality to 𝐷 = 4 and vary the data size from 𝑁 = 200M to 800M. Figures 8a and 8b show that all methods scale well with the data size and their relative differences are not affected by the data scale for range queries. The same behavior is observed in Figures 9a and 9b for the 𝑘NN queries. In the second experiment, we fix 𝑁 = 400M and vary the data dimensionality 𝐷. Figures 8c and 8d show that skd-tree prevails in all cases and scales well with 𝐷 for range queries. Note that Flood performs better compared to the case of real data, as synthetic data distributions are easy to learn. However, Flood does

Achilleas Michalopoulos, Dimitrios Tsitsigkos, and Nikos Mamoulis

10-2

15-3

20-4

25-5

Total Time (sec)

10 0

5-1

30-6

100 0

15-3

20-4

25-5

5-1

30-6

25-5

30-6

20 0

5-1

10-2

15-3

20-4

25-5

30-6

200 0

25-5

5-1

30-6

10-2

15-3

20-4

25-5

30-6

Updates ratio (Insertions-Deletions (%))

(d) GAIA (𝐷 = 6)

15-3

Updates ratio (Insertions-Deletions (%))

10-2

Updates ratio (Insertions-Deletions (%))

skd R tre PH-tree -tr e ee skd R-tree PH tre -tr e ee skd R-tree PH tre -tr e ee skd R-tree PH tre -tr e ee skd R-tree PH tre -tr e ee skd R-tree PH tre -tr e ee

20-4

10-2

Total Time (sec)

200

15-3

(b) TORONTO (𝐷 = 3)

skd R tre PH-tree -tr e ee skd R-tree PH tre -tr e ee skd R-tree t PH re -tr e ee skd R-tree PH tre -tr e ee skd R-tree PH tre -tr e ee skd R-tree PH tre -tr e ee

Total Time (sec)

(a) EDGES (𝐷 = 2)

10-2

Updates ratio (Insertions-Deletions (%))

5-1

100

skd R tre PH-tree -tr e ee skd R-tree PH tre -tr e ee skd R tre PH-tree -tr e ee skd R-tree PH tre -tr e ee skd R-tree PH tre -tr e ee skd R-tree PH tre -tr e ee

5-1

Queries

skd R tre PH-tree -tr e ee skd R-tree PH tre -tr e ee skd R tre PH-tree -tr e ee skd R-tree PH tre -tr e ee skd R-tree PH tre -tr e ee skd R-tree PH tre -tr e ee

Total Time (sec)

Deletions

skd R tre PH-tree -tr e ee skd R-tree PH tre -tr e ee skd R-tree PH tre -tr e ee skd R-tree PH tre -tr e ee skd R-tree PH tre -tr e ee skd R-tree PH tre -tr e ee

skd R tre PH-treee -tr ee skd -tr R e PH-treee -tr ee skd -tr R e PH-treee -tr ee skd -tr R e PH-treee -tr ee skd -tr R e PH-treee -tr ee skd -tr R e PH-treee -tr ee

Total Time (sec)

Insertions 20

(e) NYT (𝐷 = 8)

(f) TPC-H (𝐷 = 8)

Figure 7: Breakdown of execution time under a mixed workload of queries (mixed range and 𝑘NN) and updates. The x-axis shows the percentage of the initial dataset used for insertions and deletions

103

101 200M

400M

600M

Data Cardinality

103 10

101 100

800M

(a) Uniform (𝐷 = 4) Throughput (QPS)

Throughput (QPS)

400M

600M

Data Cardinality

104 102 100

800M

200M

400M

600M

Data Cardinality

102 100

800M

R-tree

104

(a) Uniform (𝐷 = 4)

(b) Gaussian (𝐷 = 4)

103 2

101 100

200M

kd-tree

200M

400M

600M

Data Cardinality

800M

(b) Gaussian (𝐷 = 4)

104

skd-tree

Flood

Dimensions

103 10

101 100

Dimensions

(d) Gaussian (𝑁 = 400M)

Throughput (QPS)

100

Throughput (QPS)

R-tree

Throughput (QPS)

kd-tree

Throughput (QPS)

skd-tree

104 102 100

Dimensions

104 102 100

Dimensions

(d) Gaussian (𝑁 = 400M)

Figure 8: Scalability test using uniform and gaussian data for range queries

Figure 9: Scalability test using uniform and gaussian data for knn queries

not support 𝑘NN queries and it is best for static data, as already discussed. Regarding the 𝑘NN queries, Figures 9c and 9d show similar behavior, with the R-tree as the second-best performer.

One direction for future work is to make the skd-tree adaptive to a known query workload before construction, in the same spirit as [25, 75], by adapting the number of splitters per dimension in each subtree during construction, considering both the data and the queries distribution locally. Another important direction is the implementation of a multithreaded version of skd-tree that can process a workload of queries and updates in parallel.

Conclusions

In this paper, we proposed skd-tree, a multi-way kd-tree for indexing multidimensional points in memory, which applies at each node (i) multiple partitions in the same dimension, (ii) compression, (iii) data parallelism at search. We proposed range and 𝑘NN search algorithms, an effective construction algorithm, and efficient update methods for dynamic data. We compared our skd-tree with the best performing, according to [49], multi-dimensional classic and learned indices and shown that it consistently outperforms all of them in range and 𝑘NN queries, while being several times faster in mixed workloads with updates and queries.

References [1] [n. d.]. Boost C++ Library. https://www.boost.org/ [2] [n. d.]. GAIA source. https://cdn.gea.esac.esa.int/Gaia/gdr3/gaia_source/ [3] [n. d.]. NYC Yellow Taxi Trip Data. https://www.kaggle.com/datasets/elemento/ nyc-yellow-taxi-trip-data [4] [n. d.]. OOKLA. https://www.kaggle.com/datasets/dhruvildave/ookla-internetspeed-dataset [5] [n. d.]. PH-tree Code. https://github.com/tzaeschke/phtree-cpp [6] [n. d.]. TPC-H Homepage. http://www.tpc.org/tpch/ [7] 2015. Spatial Hadoop Datasets. https://spatialhadoop.cs.umn.edu/datasets.html

In-memory Multidimensional Indexing Using the skd-tree

[8] Pankaj K. Agarwal, Lars Arge, Andrew Danner, and Bryan Holland-Minkley. 2003. Cache-oblivious data structures for orthogonal range searching. In Proceedings of the 19th ACM Symposium on Computational Geometry, San Diego, CA, USA, June 8-10, 2003, Steven Fortune (Ed.). ACM, 237–245. doi:10.1145/777792.777828 [9] Ibraheem Al-Furaih, Srinivas Aluru, Sanjay Goil, and Sanjay Ranka. 2000. Parallel Construction of Multidimensional Binary Search Trees. IEEE Trans. Parallel Distributed Syst. 11, 2 (2000), 136–148. doi:10.1109/71.841750 [10] Abdullah Al-Mamun, Ch. Md. Rakin Haider, Jianguo Wang, and Walid G. Aref. 2022. The "AI + R" - tree: An Instance-optimized R - tree. In 23rd IEEE International Conference on Mobile Data Management, MDM 2022, Paphos, Cyprus, June 6-9, 2022. IEEE, 9–18. doi:10.1109/MDM55031.2022.00023 [11] Lars Arge, Mark de Berg, Herman J. Haverkort, and Ke Yi. 2004. The Priority R-Tree: A Practically Efficient and Worst-Case Optimal R-Tree. In Proceedings of the ACM SIGMOD International Conference on Management of Data, Paris, France, June 13-18, 2004, Gerhard Weikum, Arnd Christian König, and Stefan Deßloch (Eds.). ACM, 347–358. doi:10.1145/1007568.1007608 [12] Rudolf Bayer. 1997. The universal B-tree for multidimensional indexing: General concepts. In International Conference on Worldwide Computing and Its Applications. Springer, 198–209. [13] Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, and Bernhard Seeger. 1990. The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles. In Proceedings of the 1990 ACM SIGMOD International Conference on Management of Data, Atlantic City, NJ, USA, May 23-25, 1990, Hector GarciaMolina and H. V. Jagadish (Eds.). ACM Press, 322–331. doi:10.1145/93597.98741 [14] Norbert Beckmann and Bernhard Seeger. 2009. A revised R*-tree in comparison with related index structures. In Proceedings of the 2009 ACM SIGMOD International Conference on Management of data. 799–812. [15] Jon Louis Bentley. 1975. Multidimensional Binary Search Trees Used for Associative Searching. Commun. ACM 18, 9 (1975), 509–517. doi:10.1145/361002.361007 [16] Jon Louis Bentley. 1979. Multidimensional Binary Search Trees in Database Applications. IEEE Trans. Software Eng. 5, 4 (1979), 333–340. doi:10.1109/TSE. 1979.234200 [17] Robert Binna, Eva Zangerle, Martin Pichl, Günther Specht, and Viktor Leis. 2018. HOT: A Height Optimized Trie Index for Main-Memory Database Systems. In Proceedings of the 2018 International Conference on Management of Data, SIGMOD Conference 2018, Houston, TX, USA, June 10-15, 2018, Gautam Das, Christopher M. Jermaine, and Philip A. Bernstein (Eds.). ACM, 521–534. doi:10.1145/3183713. 3196896 [18] Jose Luis Blanco and Pranjal Kumar Rai. 2014. nanoflann: a C++ header-only fork of FLANN, a library for Nearest Neighbor (NN) with KD-trees. https: //github.com/jlblancoc/nanoflann. [19] Russell A. Brown. 2014. Building a Balanced k-d Tree in O(kn log n) Time. CoRR abs/1410.5420 (2014). arXiv:1410.5420 http://arxiv.org/abs/1410.5420 [20] Yixi Cai, Wei Xu, and Fu Zhang. 2021. ikd-Tree: An Incremental K-D Tree for Robotic Applications. CoRR abs/2102.10808 (2021). arXiv:2102.10808 https: //arxiv.org/abs/2102.10808 [21] Yu Cao, Xiaojiang Zhang, Boheng Duan, Wenjing Zhao, and Huizan Wang. 2020. An Improved Method to Build the KD Tree Based on Presorted Results. In 2020 IEEE 11th International Conference on Software Engineering and Service Science (ICSESS). 71–75. doi:10.1109/ICSESS49938.2020.9237636 [22] Byn Choi, Rakesh Komuravelli, Victor Lu, Hyojin Sung, Robert L. Bocchino Jr., Sarita V. Adve, and John C. Hart. 2010. Parallel SAH k-D tree construction. In Proceedings of the ACM SIGGRAPH/EUROGRAPHICS Conference on High Performance Graphics 2010, Saarbrücken, Germany, June 25-27, 2010, Justin Hensley, Philipp Slusallek, David K. McAllister, and Christiaan P. Gribble (Eds.). Eurographics Association, 77–86. doi:10.2312/EGGH/HPG10/077-086 [23] Gaia Collaboration. 2023. Gaia Data Release 3: Summary of the content and survey properties. Astronomy & Astrophysics 674 (June 2023), A1. doi:10.1051/ 0004-6361/202243940 [24] Angjela Davitkova, Evica Milchevski, and Sebastian Michel. 2020. The ML-Index: A Multidimensional, Learned Index for Point, Range, and Nearest-Neighbor Queries.. In EDBT. 407–410. [25] Jialin Ding, Vikram Nathan, Mohammad Alizadeh, and Tim Kraska. 2020. Tsunami: A Learned Multi-dimensional Index for Correlated Data and Skewed Workloads. Proc. VLDB Endow. 14, 2 (2020), 74–86. doi:10.14778/3425879.3425880 [26] Haowen Dong, Chengliang Chai, Yuyu Luo, Jiabin Liu, Jianhua Feng, and Chaoqun Zhan. 2022. RW-Tree: A Learned Workload-aware Framework for R-tree Construction. In 38th IEEE International Conference on Data Engineering, ICDE 2022, Kuala Lumpur, Malaysia, May 9-12, 2022. IEEE, 2073–2085. doi:10.1109/ICDE53745.2022.00201 [27] Gaia Collaboration et al. 2016. TheGaiamission. Astronomy & Astrophysics 595 (Nov. 2016), A1. doi:10.1051/0004-6361/201629272 [28] Raphael A Finkel and Jon Louis Bentley. 1974. Quad trees a data structure for retrieval on composite keys. Acta informatica 4, 1 (1974), 1–9. [29] Jian Gao, Xin Cao, Xin Yao, Gong Zhang, and Wei Wang. 2023. LMSFC: A Novel Multidimensional Index based on Learned Monotonic Space Filling Curves. Proc. VLDB Endow. 16, 10 (2023), 2605–2617. doi:10.14778/3603581.3603598

[30] Goetz Graefe. 2024. More Modern B-Tree Techniques. Found. Trends Databases 13, 3 (2024), 169–249. [31] Tu Gu, Kaiyu Feng, Gao Cong, Cheng Long, Zheng Wang, and Sheng Wang. 2023. The RLR-Tree: A Reinforcement Learning Based R-Tree for Spatial Data. Proc. ACM Manag. Data 1, 1 (2023), 63:1–63:26. doi:10.1145/3588917 [32] Antonin Guttman. 1984. R-Trees: A Dynamic Index Structure for Spatial Searching. In SIGMOD’84, Proceedings of Annual Meeting, Boston, Massachusetts, USA, June 18-21, 1984, Beatrice Yormark (Ed.). ACM Press, 47–57. doi:10.1145/602259. 602266 [33] Ali Hadian, Behzad Ghaffari, Taiyi Wang, and Thomas Heinis. 2023. COAX: Correlation-Aware Indexing. In 39th IEEE International Conference on Data Engineering, ICDE 2023 - Workshops, Anaheim, CA, USA, April 3-7, 2023. IEEE, 55–59. doi:10.1109/ICDEW58674.2023.00014 [34] Ali Hadian, Ankit Kumar, and Thomas Heinis. 2020. Hands-off Model Integration in Spatial Index Structures. In AIDB@VLDB 2020, 2nd International Workshop on Applied AI for Database Systems and Applications, Held with VLDB 2020, Monday, August 31, 2020, Online Event / Tokyo, Japan, Bingsheng He, Berthold Reinwald, and Yingjun Wu (Eds.). https://drive.google.com/file/d/ 1c3uPyv9apCHWz2wcr1bYNB3JVgCKteKM/view?usp=sharing [35] Marios Hadjieleftheriou, Yannis Manolopoulos, Yannis Theodoridis, and Vassilis J. Tsotras. 2017. R-Trees: A Dynamic Index Structure for Spatial Searching. In Encyclopedia of GIS, Shashi Shekhar, Hui Xiong, and Xun Zhou (Eds.). Springer, 1805–1817. doi:10.1007/978-3-319-17885-1_1151 [36] Warren Hunt, William R. Mark, and Gordon Stoll. 2006. Fast kd-tree Construction with an Adaptive Error-Bounded Heuristic. In 2006 IEEE Symposium on Interactive Ray Tracing. 81–88. doi:10.1109/RT.2006.280218 [37] Stratos Idreos, Martin L. Kersten, and Stefan Manegold. 2007. Database Cracking. In Third Biennial Conference on Innovative Data Systems Research, CIDR 2007, Asilomar, CA, USA, January 7-10, 2007, Online Proceedings. www.cidrdb.org, 68–78. [38] Hosagrahar V Jagadish, Beng Chin Ooi, Kian-Lee Tan, Cui Yu, and Rui Zhang. 2005. iDistance: An adaptive B+-tree based indexing method for nearest neighbor search. ACM Transactions on Database Systems (TODS) 30, 2 (2005), 364–397. [39] Ibrahim Kamel and Christos Faloutsos. 1994. Hilbert R-tree: An Improved Rtree using Fractals. In VLDB’94, Proceedings of 20th International Conference on Very Large Data Bases, September 12-15, 1994, Santiago de Chile, Chile, Jorge B. Bocca, Matthias Jarke, and Carlo Zaniolo (Eds.). Morgan Kaufmann, 500–509. http://www.vldb.org/conf/1994/P500.PDF [40] Changkyu Kim, Jatin Chhugani, Nadathur Satish, Eric Sedlar, Anthony D. Nguyen, Tim Kaldewey, Victor W. Lee, Scott A. Brandt, and Pradeep Dubey. 2010. FAST: fast architecture sensitive tree search on modern CPUs and GPUs. In Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2010, Indianapolis, Indiana, USA, June 6-10, 2010, Ahmed K. Elmagarmid and Divyakant Agrawal (Eds.). ACM, 339–350. doi:10.1145/1807167.1807206 [41] Kihong Kim, Sang Kyun Cha, and Keunjoo Kwon. 2001. Optimizing Multidimensional Index Trees for Main Memory Access. In Proceedings of the 2001 ACM SIGMOD international conference on Management of data, Santa Barbara, CA, USA, May 21-24, 2001, Sharad Mehrotra and Timos K. Sellis (Eds.). ACM, 139–150. doi:10.1145/375663.375679 [42] Tim Kraska, Mohammad Alizadeh, Alex Beutel, Ed H. Chi, Ani Kristo, Guillaume Leclerc, Samuel Madden, Hongzi Mao, and Vikram Nathan. 2019. SageDB: A Learned Database System. In 9th Biennial Conference on Innovative Data Systems Research, CIDR 2019, Asilomar, CA, USA, January 13-16, 2019, Online Proceedings. www.cidrdb.org. http://cidrdb.org/cidr2019/papers/p117-kraska-cidr19.pdf [43] Tim Kraska, Alex Beutel, Ed H. Chi, Jeffrey Dean, and Neoklis Polyzotis. 2018. The Case for Learned Index Structures. In Proceedings of the 2018 International Conference on Management of Data, SIGMOD Conference 2018, Houston, TX, USA, June 10-15, 2018, Gautam Das, Christopher M. Jermaine, and Philip A. Bernstein (Eds.). ACM, 489–504. doi:10.1145/3183713.3196909 [44] Yongsik Kwon, Seonho Lee, Yehyun Nam, Joong Chae Na, Kunsoo Park, Sang K. Cha, and Bongki Moon. 2023. DB+-tree: A new variant of B+-tree for mainmemory database systems. Inf. Syst. 119 (2023), 102287. [45] Viktor Leis, Alfons Kemper, and Thomas Neumann. 2013. The adaptive radix tree: ARTful indexing for main-memory databases. In 29th IEEE International Conference on Data Engineering, ICDE 2013, Brisbane, Australia, April 8-12, 2013, Christian S. Jensen, Christopher M. Jermaine, and Xiaofang Zhou (Eds.). IEEE Computer Society, 38–49. doi:10.1109/ICDE.2013.6544812 [46] Scott T. Leutenegger, Jeffrey Edgington, and Mario Alberto López. 1997. STR: A Simple and Efficient Algorithm for R-Tree Packing. In Proceedings of the Thirteenth International Conference on Data Engineering, April 7-11, 1997, Birmingham, UK, W. A. Gray and Per-Åke Larson (Eds.). IEEE Computer Society, 497–506. doi:10.1109/ICDE.1997.582015 [47] Mingxin Li, Hancheng Wang, Haipeng Dai, Meng Li, Chengliang Chai, Rong Gu, Feng Chen, Zhiyuan Chen, Shuaituan Li, Qizhi Liu, and Guihai Chen. 2024. A Survey of Multi-Dimensional Indexes: Past and Future Trends. IEEE Trans. Knowl. Data Eng. 36, 8 (2024), 3635–3655. doi:10.1109/TKDE.2024.3364183

Achilleas Michalopoulos, Dimitrios Tsitsigkos, and Nikos Mamoulis

[48] Pengfei Li, Hua Lu, Qian Zheng, Long Yang, and Gang Pan. 2020. LISA: A learned index structure for spatial data. In Proceedings of the 2020 ACM SIGMOD international conference on management of data. 2119–2133. [49] Qiyu Liu, Maocheng Li, Yuxiang Zeng, Yanyan Shen, and Lei Chen. 2025. How good are multi-dimensional learned indexes? An experimental survey. VLDB J. 34, 2 (2025), 17. doi:10.1007/S00778-024-00893-6 [50] Donald Meagher. 1982. Geometric modeling using octree encoding. Computer graphics and image processing 19, 2 (1982), 129–147. [51] Ziyang Men, Zheqi Shen, Yan Gu, and Yihan Sun. 2025. Parallel kd-tree with Batch Updates. Proc. ACM Manag. Data 3, 1 (2025), 62:1–62:26. doi:10.1145/3709712 [52] Mohamed F. Mokbel, Xiaopeng Xiong, and Walid G. Aref. 2004. SINA: Scalable Incremental Processing of Continuous Queries in Spatio-temporal Databases. In SIGMOD. 623–634. [53] Moin Hussain Moti, Panagiotis Simatis, and Dimitris Papadias. 2022. Waffle: A Workload-Aware and Query-Sensitive Framework for Disk-Based Spatial Indexing. Proc. VLDB Endow. 16, 4 (2022), 670–683. doi:10.14778/3574245.3574253 [54] Kyriakos Mouratidis, Marios Hadjieleftheriou, and Dimitris Papadias. 2005. Conceptual Partitioning: An Efficient Method for Continuous Nearest Neighbor Monitoring. In SIGMOD. 634–645. [55] Vikram Nathan, Jialin Ding, Mohammad Alizadeh, and Tim Kraska. 2020. Learning multi-dimensional indexes. In Proceedings of the 2020 ACM SIGMOD international conference on management of data. 985–1000. [56] Sachith Pai, Michael Mathioudakis, and Yanhao Wang. 2024. WaZI: A Learned and Workload-aware Z-Index. In Proceedings 27th International Conference on Extending Database Technology, EDBT 2024, Paestum, Italy, March 25 - March 28, Letizia Tanca, Qiong Luo, Giuseppe Polese, Loredana Caruccio, Xavier Oriol, and Donatella Firmani (Eds.). OpenProceedings.org, 559–571. doi:10.48786/EDBT. 2024.48 [57] Yongxin Peng, Wei Zhou, Lin Zhang, and Hongle Du. 2020. A Study of Learned KD Tree Based on Learned Index. In International Conference on Networking and Network Applications, NaNA 2020, Haikou City, China, December 10-13, 2020. IEEE, 355–360. doi:10.1109/NANA51271.2020.00067 [58] 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. Springer, 46–65. [59] Jianzhong Qi, Guanli Liu, Christian S Jensen, and Lars Kulik. 2020. Effectively learning spatial indices. Proceedings of the VLDB Endowment 13, 12 (2020), 2341– 2354. [60] Jianzhong Qi, Yufei Tao, Yanchuan Chang, and Rui Zhang. 2018. Theoretically Optimal and Empirically Efficient R-trees with Strong Parallelizability. Proc. VLDB Endow. 11, 5 (2018), 621–634. doi:10.1145/3187009.3177738 [61] Frank Ramsak, Volker Markl, Robert Fenk, Martin Zirkel, Klaus Elhardt, and Rudolf Bayer. 2000. Integrating the UB-tree into a database system kernel.. In VLDB, Vol. 2000. 263–272. [62] Jun Rao and Kenneth A. Ross. 2000. Making B+ -Trees Cache Conscious in Main Memory. In Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data, May 16-18, 2000, Dallas, Texas, USA, Weidong Chen, Jeffrey F. Naughton, and Philip A. Bernstein (Eds.). ACM, 475–486. [63] Suprio Ray, Rolando Blanco, and Anil K. Goel. 2014. Supporting Location-Based Services in a Main-Memory Database. In IEEE MDM. 3–12. [64] Yeasir Rayhan and Walid G. Aref. 2023. SIMD-ified R-tree Query Processing and Optimization. In Proceedings of the 31st ACM International Conference on Advances in Geographic Information Systems, SIGSPATIAL 2023, Hamburg, Germany, November 13-16, 2023, Matthias Renz and Mario A. Nascimento (Eds.). ACM, 37:1–37:10. doi:10.1145/3589132.3625610 [65] Maximilian Reif and Thomas Neumann. 2022. A Scalable and Generic Approach to Range Joins. Proc. VLDB Endow. 15, 11 (2022), 3018–3030. doi:10.14778/3551793. 3551849 [66] John T. Robinson. 1981. The K-D-B-Tree: A Search Structure For Large Multidimensional Dynamic Indexes. In Proceedings of the 1981 ACM SIGMOD International Conference on Management of Data, Ann Arbor, Michigan, USA, April 29 May 1, 1981, Y. Edmund Lien (Ed.). ACM Press, 10–18. doi:10.1145/582318.582321 [67] Hanan Samet. 2006. Foundations of multidimensional and metric data structures. Academic Press. [68] Benjamin Schlegel, Rainer Gemulla, and Wolfgang Lehner. 2009. k-ary search on modern processors. In Proceedings of the Fifth International Workshop on Data Management on New Hardware, DaMoN 2009, Providence, Rhode Island, USA, June 28, 2009, Peter A. Boncz and Kenneth A. Ross (Eds.). ACM, 52–60. doi:10.1145/1565694.1565705 [69] Timos K. Sellis, Nick Roussopoulos, and Christos Faloutsos. 1987. The R+-Tree: A Dynamic Index for Multi-Dimensional Objects. In VLDB’87, Proceedings of 13th International Conference on Very Large Data Bases, September 1-4, 1987, Brighton, England, Peter M. Stocker, William Kent, and Peter Hammersley (Eds.). Morgan Kaufmann, 507–518. http://www.vldb.org/conf/1987/P507.PDF [70] Amirhesam Shahvarani and Hans-Arno Jacobsen. 2016. A Hybrid B+-tree as Solution for In-Memory Indexing on CPU-GPU Heterogeneous Computing Platforms. In Proceedings of the 2016 International Conference on Management of Data, SIGMOD Conference 2016, San Francisco, CA, USA, June 26 - July 01,

2016, Fatma Özcan, Georgia Koutrika, and Sam Madden (Eds.). ACM, 1523–1538. doi:10.1145/2882903.2882918 [71] Maxim Shevtsov, Alexei Soupikov, and Alexander Kapustin. 2007. Highly Parallel Fast KD-tree Construction for Interactive Ray Tracing of Dynamic Scenes. Comput. Graph. Forum 26, 3 (2007), 395–404. doi:10.1111/J.1467-8659.2007.01062.X [72] Darius Sidlauskas, Simonas Saltenis, Christian W. Christiansen, Jan M. Johansen, and Donatas Saulys. 2009. Trees or grids?: indexing moving objects in main memory. In SIGSPATIAL/ACM-GIS. 236–245. [73] Stefan Sprenger, Patrick Schäfer, and Ulf Leser. 2018. Multidimensional range queries on modern hardware. In Proceedings of the 30th International Conference on Scientific and Statistical Database Management, SSDBM 2018, Bozen-Bolzano, Italy, July 09-11, 2018, Dimitris Sacharidis, Johann Gamper, and Michael H. Böhlen (Eds.). ACM, 4:1–4:12. doi:10.1145/3221269.3223031 [74] Stefan Sprenger, Patrick Schäfer, and Ulf Leser. 2019. BB-Tree: A practical and efficient main-memory index structure for multidimensional workloads. In Advances in Database Technology - 22nd International Conference on Extending Database Technology, EDBT 2019, Lisbon, Portugal, March 26-29, 2019, Melanie Herschel, Helena Galhardas, Berthold Reinwald, Irini Fundulaki, Carsten Binnig, and Zoi Kaoudi (Eds.). OpenProceedings.org, 169–180. doi:10.5441/002/EDBT. 2019.16 [75] Sivaprasad Sudhir, Michael J. Cafarella, and Samuel Madden. 2021. Replicated Layout for In-Memory Database Systems. Proc. VLDB Endow. 15, 4 (2021), 984–997. doi:10.14778/3503585.3503606 [76] Weikai Tan, Nannan Qin, Lingfei Ma, Ying Li, Jing Du, Guorong Cai, Ke Yang, and Jonathan Li. 2020. Toronto-3D: A large-scale mobile lidar dataset for semantic segmentation of urban roadways. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops. 202–203. [77] Dimitrios Tsitsigkos, Achilleas Michalopoulos, Nikos Mamoulis, and M. Terrovitis. 2026. BS-tree: A gapped data-parallel B-tree. In Proceedings of the 42nd International Conference on Data Engineering, May 4-8, 2026, Montreal, Canada. [78] Haixin Wang, Xiaoyi Fu, Jianliang Xu, and Hua Lu. 2019. Learned index for spatial queries. In 2019 20th IEEE International Conference on Mobile Data Management (MDM). IEEE, 569–574. [79] Lijun Wang, Linshu Hu, Chenhua Fu, Yuhan Yu, Peng Tang, Feng Zhang, and Renyi Liu. 2023. SLBRIN: a spatial learned index based on brin. ISPRS International Journal of Geo-Information 12, 4 (2023), 171. [80] Ning Wang and Jianqiu Xu. 2020. Spatial queries based on learned index. In International Conference on Spatial Data and Intelligence. Springer, 245–257. [81] Yiqiu Wang, Rahul Yesantharao, Shangdi Yu, Laxman Dhulipala, Yan Gu, and Julian Shun. 2022. ParGeo: A Library for Parallel Computational Geometry. In 30th Annual European Symposium on Algorithms, ESA 2022, September 5-9, 2022, Berlin/Potsdam, Germany (LIPIcs, Vol. 244), Shiri Chechik, Gonzalo Navarro, Eva Rotenberg, and Grzegorz Herman (Eds.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 88:1–88:19. doi:10.4230/LIPICS.ESA.2022.88 [82] 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), Yonago, Japan, July 12-13, 2018. IEEE Computer Society, 23–30. doi:10.1109/BCD2018.2018.00012 [83] Zhaofeng Yan, Yuzhe Lin, Lu Peng, and Weihua Zhang. 2019. Harmonia: a high throughput B+tree for GPUs. In Proceedings of the 24th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2019, Washington, DC, USA, February 16-20, 2019, Jeffrey K. Hollingsworth and Idit Keidar (Eds.). ACM, 133–144. doi:10.1145/3293883.3295704 [84] Rahul Yesantharao, Yiqiu Wang, Laxman Dhulipala, and Julian Shun. 2021. Parallel Batch-Dynamic kd-Trees. CoRR abs/2112.06188 (2021). arXiv:2112.06188 https://arxiv.org/abs/2112.06188 [85] Tilmann Zäschke, Christoph Zimmerli, and Moira C. Norrie. 2014. The PH-tree: a space-efficient storage structure and multi-dimensional index. In International Conference on Management of Data, SIGMOD 2014, Snowbird, UT, USA, June 22-27, 2014, Curtis E. Dyreson, Feifei Li, and M. Tamer Özsu (Eds.). ACM, 397–408. doi:10.1145/2588555.2588564 [86] Songnian Zhang, Suprio Ray, Rongxing Lu, and Yandong Zheng. 2021. SPRIG: A Learned Spatial Index for Range and kNN Queries. In Proceedings of the 17th International Symposium on Spatial and Temporal Databases, SSTD 2021, Virtual Event, USA, August 23-25, 2021, Erik Hoel, Dev Oliver, Raymond Chi-Wing Wong, and Ahmed Eldawy (Eds.). ACM, 96–105. doi:10.1145/3469830.3470892 [87] Jingren Zhou and Kenneth A. Ross. 2002. Implementing database operations using SIMD instructions. In Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data, Madison, Wisconsin, USA, June 3-6, 2002, Michael J. Franklin, Bongki Moon, and Anastassia Ailamaki (Eds.). ACM, 145–156. doi:10.1145/564691.564709 [88] Jingren Zhou and Kenneth A. Ross. 2003. Buffering Accesses to Memory-Resident Index Structures. In Proceedings of 29th International Conference on Very Large Data Bases, VLDB 2003, Berlin, Germany, September 9-12, 2003, Johann Christoph Freytag, Peter C. Lockemann, Serge Abiteboul, Michael J. Carey, Patricia G. Selinger, and Andreas Heuer (Eds.). Morgan Kaufmann, 405–416. doi:10.1016/ B978-012722442-8/50043-4

In-memory Multidimensional Indexing Using the skd-tree

Related documents