Product Range Search Problem
2026
Read Product Range Search Problem (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-2603-22500.txt.
Introduction
Chubet and co-authors study range search when two distance measures act at once. A standard query returns every point within one radius of a center. Their product query asks for points within a first radius under one metric and a second radius under another. The answer is the overlap of the two searches. The team builds two data structures for doubling metrics, both based on a greedy tree. One adapts the classic range tree. The other grows a single tree on the product space.
Catalog record
| YEAR | 2026 |
|---|---|
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 21117 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.22500
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Product Range Search Problem Thanks: This research was supported by the NSF (CCF-23491790). Abstract . Given a metric space, a standard metric range search, given a query ( q , r ) (q,r) , finds all points within distance r r of the point q q . Suppose now we have two different metrics 𝖽 1 \mathsf{d}_{1} and 𝖽 2 \mathsf{d}_{2} . A product range query ( q , r 1 , r 2 ) (q,r_{1},r_{2}) is a point q q and two radii r 1 r_{1} and r 2 r_{2} . The output is all points within distance r 1 r_{1} of q q with respect to 𝖽 1 \mathsf{d}_{1} and all points within r 2 r_{2} of q q with respect to 𝖽 2 \mathsf{d}_{2} . In other words, it is the intersection of two searches. We present two data structures for approximate product range search in doubling metrics. Both data structures use a net-tree variant, the greedy tree. The greedy tree is a data structure that can efficiently answer approximate range searches in doubling metrics. The first data structure is a generalization of the range tree from computational geometry using greedy trees rather than binary trees. The second data structure is a single greedy tree constructed on the product induced by the two metrics. Oliver Chubet North Carolina State University [email protected] Niyathi Kukkapalli Princeton University [email protected] Anvi Kudaraya University of California, Merced [email protected] Donald R. Sheehy North Carolina State University [email protected] 1. Introduction The metric range search problem is as follows: given a set of points P in a metric space, preprocess P into a data structure where queries are of the form (q,r) where q is a point in P and r\geq 0 is a real number. Such a query returns the points in P\hskip 1.42262pt\cap\hskip 1.42262pt\mathsf{ball}(q,r) . In one dimension, the metric balls are intervals and products of intervals are axis-aligned boxes. The corresponding range search problem is known as orthogonal range search . Thus, orthogonal range search is a product of one-dimensional range searches. In this paper, we generalize the metric range search problem to product metric range searches in doubling metrics. For two metrics, \mathsf{d}_{1} and \mathsf{d}_{2} , the queries will be of the form (q,r_{1},r_{2}) and the result will be: \{x\in P\mid\mathsf{d}_{1}(x,q)\leq r_{1}\text{ and }\mathsf{d}_{2}(x,q)\leq r_{2}\}. In other words, it is the intersection of two range searches (q,r_{1}) with respect to \mathsf{d}_{1} and (q,r_{2}) with respect to \mathsf{d}_{2} . We call this the Product Range Search Problem . In this paper, we present and analyze two data structures for product range search in doubling metrics. The first product range tree is a multi-level data structure. The construction uses the classical paradigm of cascading multiple decomposition schemes. The second product range tree is a greedy tree on the product metric itself. However, the query algorithm must be modified to accommodate products of balls, which may not correspond to a ball in the product metric. In settings where distance computations can be computed efficiently, there are several efficient data structures available, and some authors even consider range search a “solved” problem 2 . However, there are still cases when range queries over the full space may be impractical due to expensive metric computations. Recently, product range search approaches have been considered for cases where metric computations are expensive to compute, but the metric admits some decomposability into a product, such as is the case for the Ulam metric, discrete Frechet distance, and dynamic time warping 1 ; 8 . Other applications that can be formulated as product problems are multi-key range queries in databases 4 . Product-metric range search has recently been studied for metrics that decompose into l_{p} products of l_{\infty} or l_{1} spaces 3 . To the best of our knowledge, product range search has not been studied for products of non-normed spaces. 1.1. Related Work There are a plethora of data structures for range search in product metrics, but most are for Euclidean space. For coordinate-wise comparisons, the k-d tree partitions the plane into rectangular regions and has query time of O(n^{1-1/d}+k) for a d -dimensional query 7 . There are also range trees for orthogonal range queries, which have a query time of O(\log^{d-1}n+k) using fractional cascading 7 . Ball trees are the simplest hierarchical structure for range search in metric spaces. They are defined by recursively partitioning the data set, represented as a binary tree 13 . Each node of the tree represents a metric ball, storing a center and radius. Range searches are performed using branch and bound, where nodes can be pruned when the entire ball is disjoint from the query ball. Greedy trees are ball trees constructed using farthest point sampling to achieve packing and covering guarantees. The algorithms we propose in this work are built with greedy trees because they are simple, implementable, and admit strong theoretical guarantees, but other similar trees could work. 1.2. Our Contribution In Section 3 we introduce a cascading data structure to solve the product range search problem, analogous to using the Euclidean range tree for orthogonal range search. We call this data structure the greedy range tree because it uses a recent net-tree variant, the greedy tree. Given an n -point set P and m metrics \mathsf{d}_{1},\dots,\mathsf{d}_{m} , the greedy range tree can be built in 2^{O(\delta)}n\log^{m-1}\Delta time, where \delta=\sum_{i=1}^{m}\mathsf{ddim}(P,\mathsf{d}_{i}) is the sum of the doubling dimensions (see Section ), and the spread, \Delta , is the ratio between the maximum and minimum pairwise distances. For simplicity, we assume the spread of each metric is the same, otherwise we can take the maximum. The greedy range tree can be stored in 2^{O(\delta)}n\log^{m-1}\Delta space. Each query takes \left(2+\frac{1}{\varepsilon}\right)^{O(\delta)}\log\Delta+k time, where k is the size of the output. Note that this data structure can be easily generalized to use any ball tree. If the ball tree used is a net-tree, then the query time analysis will still hold. However, in order to achieve the preprocessing time, we rely on recent results allowing us to merge two existing greedy trees in linear time. It is unknown whether similar results can be achieved for other net-tree variants, making the greedy tree a powerful choice. In Section 4 we introduce an algorithm to perform approximate product range queries in a regular greedy tree built using the product metric itself. The data structure can be constructed in 2^{O(\delta)}n\log n time and uses only O(n) space. An approximate product range query takes A^{O(\delta)}\left(2+\frac{1}{\varepsilon}\right)^{O(\delta)}\log\Delta+k time, where A denotes the ratio between the maximum and minimum radii in the query. Table 1 highlights the tradeoffs between the greedy range tree and the greedy tree on the product metric in terms of storage, build time, and query complexity. Table 1 . The preprocessing times, query times, and space used by the data structures presented in Sections 3 and 4 . We assume the trees are built on an n -point set P with m metrics \mathsf{d}_{1},\dots,\mathsf{d}_{m} with spread \Delta . We define \delta:=\sum_{i=1}^{m}\mathsf{ddim}(P,\mathsf{d}_{i}) the sum of the doubling dimensions. A is the aspect ratio of a query, defined as the ratio of the maximum query radius to the minimum query radius, k denotes the output size, and \varepsilon is