In-memory Multidimensional Indexing Using the skd-tree
Achilleas Michalopoulos, Dimitrios Tsitsigkos, Nikos Mamoulis · 2026
Read In-memory Multidimensional Indexing Using the skd-tree by Achilleas Michalopoulos, Dimitrios Tsitsigkos, Nikos Mamoulis (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-03640.txt.
Introduction
Achilleas Michalopoulos, Dimitrios Tsitsigkos, and Nikos Mamoulis revisit in-memory indexing of multidimensional data, a classic database problem behind range and nearest-neighbor queries on several columns at once. Established structures include the R-tree, kd-tree, and quad-tree, and learned indexes have joined them recently. Their proposal is the slicing kd-tree, or skd-tree.
Each skd-tree node splits its subtree's space into multiple slices along one dimension, and the splitters are compressed. That design cuts the tree's depth sharply and, with data-parallel instructions, keeps query work per node to a few operations. The nodes resemble B+-tree nodes, but each level uses a different dimension. A new top-down construction algorithm completes the design.
Catalog record
| CREATOR | Achilleas Michalopoulos, Dimitrios Tsitsigkos, Nikos Mamoulis |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 69 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.03640
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
In-memory Multidimensional Indexing Using the skd-tree Achilleas Michalopoulos, Dimitrios Tsitsigkos, Nikos Mamoulis 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 k k 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 1. 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, R-trees) are considered the standard way to index and search across multiple attributes. In spatial databases, proximity queries, such as k nearest neighbor ( k NN) search are also prominent; besides, k 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 ( 60 ; 87 ; 88 ; 66 ; 40 ; 10 ; 77 ) , 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 ( 62 ; 46 ) . There is also work on workload-aware multi-dimensional indexing ( 50 ; 74 ) , where index partitions are determined considering the distribution of the expected query workload. (a) 2-d points (b) skd-tree (ours) (c) m-way kd-trees ( 64 ; 1 ) Figure 1 . Multiway kd-trees 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 m -way partitioning in a single splitting dimension at each node ( m =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 x -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 y -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 ( 64 ; 56 ; 1 ) , 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 k 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 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 ( 44 ) . The result show that skd-tree consistently outperforms the runner up by 1.5x-2x in range and k 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 skd-tree 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. Related Work 2.1. Conventional multidimensional indices The R-tree family. The popular multidimensional access method is the R-tree ( 27 ; 30 ) , 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 ( 67 ) , the R*-Tree ( 6 ) , and the Priority R-Tree ( 4 ) , bulk-loading methods ( 34 ; 41 ; 58 ; 48 ) , and optimizations ( 36 ; 7 ) have been proposed to improve its