Geometric and Spatial Data Structures in External Memory:Related Problems

Related Problems

For other types of range searching, such as in higher dimensions and for nonorthogonal queries, different filtering techniques are needed. So far, relatively little work has been done, and many open problems remain.

Vengroff and Vitter [121] develop the first theoretically near-optimal EM data structure for static three-dimensional orthogonal range searching. They create a hierarchical partitioning in which all the points that dominate a query point are densely contained in a set of blocks. Compression techniques are needed to minimize disk storage. With some recent modifications [126], queries can be done in O(logB N + z) I/Os, which is optimal, and the space usage is O(n(log n)k+1/(log(logB N + 1))k ) disk blocks to support (3 + k)-sided 3-D range queries, in which k of the dimensions (0 ≤ k ≤ 3) have finite ranges. The result also provides optimal O(log N + Z)-time query performance for three-sided 3-D queries in the (internal memory) RAM model, but using O(N log N ) space.

By the reduction in [37], a data structure for three-sided 3-D queries also applies to 2- D homothetic range search, in which the queries correspond to scaled and translated (but not rotated) transformations of an arbitrary fixed polygon. An interesting special case is “fat” orthogonal 2-D range search, where the query rectangles are required to have bounded aspect ratio. For example, every rectangle with bounded aspect ratio can be covered by two overlapping squares. An interesting open problem is to develop linear-sized optimal data structures for fat orthogonal 2-D range search. By the reduction, one possible approach would be to develop optimal linear-sized data structures for three-sided 3-D range search.

Agarwal et al. [4] consider half space range searching, in which a query is specified by a hyper plane and a bit indicating one of its two sides, and the output of the query consists of all the points on that side of the hyper plane. They give various data structures for half space range searching in two, three, and higher dimensions, including one that works for simplex (polygon) queries in two dimensions, but with a higher query I/O cost. They have subsequently improved the storage bounds for half space range queries in two dimensions to obtain an optimal static data structure satisfying Criteria O1 and O2 of Section 27.1.2.

The number of I/Os needed to build the data structures for 3-D orthogonal range search and half space range search is rather large (more than Ω(N )). Still, the structures shed useful light on the complexity of range searching and may open the way to improved solutions. An open problem is to design efficient construction and update algorithms and to improve upon the constant factors.

Callahan et al. [34] develop dynamic EM data structures for several online problems in d dimensions. For any fixed E > 0, they can find an approximate nearest neighbor of a query point (within a 1 + E factor of optimal) in O(logB N ) I/Os; insertions and deletions can also be done in O(logB N ) I/Os. They use a related approach to maintain the closest pair of points; each update costs O(logB N ) I/Os. Govindrajan et al. [60] achieve the same bounds for closest pair by maintaining a well-separated pair decomposition. For finding nearest neighbors and approximate nearest neighbors, two other approaches are partition trees [3, 4] and locality-sensitive hashing [58]. Numerous other data structures have been developed for range queries and related problems on spatial data. We refer to [8, 56, 92] for a broad survey.