Product Range Search Problem
This work addresses a specialized computational geometry problem for handling multi-metric queries, representing an incremental advancement in data structure design.
The paper tackles the product range search problem in doubling metrics by introducing two data structures based on greedy trees, achieving approximate query results with efficient performance.
Given a metric space, a standard metric range search, given a query $(q,r)$, finds all points within distance $r$ of the point $q$. Suppose now we have two different metrics $d_1$ and $d_2$. A product range query $(q, r_1, r_2)$ is a point $q$ and two radii $r_1$ and $r_2$. The output is all points within distance $r_1$ of $q$ with respect to $d_1$ and all points within $r_2$ of $q$ with respect to $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.