Product Range Search Problem

Abstract

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 d1 and d2. A product range query (q, r1, r2) is a point q and two radii $r1$ and $r2$. The output is all points within distance $r1$ of q with respect to d1 and all points within $r2$ of q with respect to $d2$. 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.

8 pages, 4 figures