Cache-Oblivious Data Structures:2d Orthogonal Range Searching
2d Orthogonal Range Searching
As discussed in Section 34.3, there exist cache-oblivious B-trees that support updates and queries in O(logB N ) memory transfers (e.g. Theorem 34.5); several cache-oblivious B- tree variants can also support (one-dimensional) range queries in O(logB N + K ) memory transfers [11, 12, 18], but at an increased amortized update cost of O(logB N + log O(log2 N ) memory transfers (e.g. Theorem 34.4).
In this section we discuss cache-oblivious data structures for two-dimensional orthogonal range searching, that is, structures for storing a set of N points in the plane such that the points in a axis-parallel query rectangle can be reported efficiently. In Section 34.5.1 we first discuss a cache-oblivious version of a kd-tree. This structure uses linear space and answers queries in O(IN/B + K ) memory transfers; this is optimal among linear space structures [22]. It supports updates in O( log N · logM/B N ) = O(log2 N ) transfers. In Section 34.5.2 we then discuss a cache-oblivious version of a two-dimensional range tree. The structure answers queries in the optimal O(logB N + K ) memory transfers but uses O(N log2 N ) space. Both structures were first described by Agarwal et al. [1].
Structure
The cache-oblivious kd-tree is simply a normal kd-tree laid out in memory using the van Emde Boas layout. This structure, proposed by Bentley [13], is a binary tree of height O(log N ) with the N points stored in the leaves of the tree. The internal nodes represent a recursive decomposition of the plane by means of axis-orthogonal lines that partition the set of points into two subsets of equal size. On even levels of the tree the dividing lines are horizontal, and on odd levels they are vertical. In this way a rectangular region Rv is naturally associated with each node v, and the nodes on any particular level of the tree partition the plane into disjoint regions. In particular, the regions associated with the leaves represent a partition of the plane into rectangular regions containing one point each. Refer to Figure 34.12.
Query
An orthogonal range query Q on a kd-tree T is answered recursively starting at the root: At a node v we advance the query to a child vc of v if Q intersects the region Rvc associated with vc. At a leaf w we return the point in w if it is contained in Q. A standard argument shows that the number of nodes in T visited when answering Q, or equivalently, the number of nodes v where Rv intersects Q, is O √ N + K); √ N nodes v are visited where Rv is intersected by the boundary of Q and K nodes u with Ru completely contained in Q [13].
If the kd-tree T is laid out using the van Emde Boas layout, we can bound the number of memory transfers used to answer a query by considering the nodes log B levels above the leaves of T . There are O( N ) such nodes as the subtree Tv rooted in one such node v contains B leaves. By the standard query argument, the number of these nodes visited by a query is O(IN/B + K ). Thus, the number of memory transfers used to visit nodes more than log B levels above the leaves is O(IN/B + K ). This is also the overall number of memory transfers used to answer a query, since (as argued in Section 34.2.1) the nodes in Tv are contained in O(1) blocks, i.e. any traversal of (any subset of) the nodes in a subtree Tv can be performed in O(1) memory transfers.
Construction
In the RAM model, a kd-tree on N points can be constructed recursively in O(N log N ) time; the root dividing line is found using an O(N ) time median algorithm, the points are distributed into two sets according to this line in O(N ) time, and the two subtrees are constructed recursively. Since median finding and distribution can be performed cache- obliviously in O(N/B) memory transfers [20, 24], a cache-oblivious kd-tree can be constructed in O( N log N ) memory transfers. Agarwal et al. [1] showed how to constructN = 1 log N levels in O(SortM,B (N )) memory transfers, leading to a recursive construction algorithms using only O(SortM,B (N )) memory transfers.
Updates
In the RAM model a kd-tree T can relatively easily be modified to support deletions in O(log N ) time using global rebuilding. To delete a point from T , we simply find the relevant leaf w in O(log N ) time and remove it. We then remove w’s parent and connect w’s grandparent to w’s sibling. The resulting tree is no longer a kd-tree but it still answers queries in O(√N + T ) time, since the standard argument still applies. To ensure that N is proportional to the actual number of points in T , the structure is completely rebuilt after 2 deletions. Insertions can be supported in O(log N ) time using the so-called logarithmic method [14], that is, by maintaining log N kd-trees where the i’th kd-tree is either empty or of size 2i and then rebuilding a carefully chosen set of these structures when performing an insertion.
The main part of the cache-oblivious range tree structure for answering (four-sided) orthogonal range queries is a structure for answering three-sided queries Q = [xl , xr ] × [yb, ∞), that is, for finding all points with x-coordinates in the interval [xl , xr ] and y-coordinates above yb. Below we discuss the two structures separately.
Three-Sided Queries.
Structure
Consider dividing the plane into √ vertical slabs X1, X2,..., X√ containing √ points each. Using these slabs we define 2√ — 1 buckets. A bucket is a rectangular region of the plane that completely spans one or more consecutive slabs and is unbounded in the positive y-direction, like a three-sided query. To define the 2√− 1 buckets we start with N active buckets b1, b2,... , b√ corresponding to the N slabs. The x-range of the slabs define a natural linear ordering on these buckets. We then imagine sweeping a horizontal sweep line from y = −∞ to y = ∞. Every time the total number of points above the sweep line in two adjacent active buckets, bi and bj , in the linear order falls to √ , we mark bi and bj as inactive. Then we construct a new active bucket spanning the slabs spanned by bi and bj with a bottom y-boundary equal to the current position of the sweep line. This bucket replaces bi and bj in the linear ordering of active buckets. The total number of buckets defined in this way is 2√ — 1, since we start with √ buckets and the number of active buckets decreases by one every time a new bucket is constructed. Note that the procedure defines an active y-interval for each bucket in a natural way. Buckets overlap but the set of buckets with active y-intervals containing a given y-value (the buckets active when the sweep line was at that value) are non-overlapping and span all the slabs. This means that the active y-intervals of buckets spanning a given slab are non-overlapping. Refer to Figure 34.13(a).
Query
To answer a three-sided query Q, we consider the buckets whose active y-interval contain yb. These buckets are non-overlapping and together they contain all points in Q, since they span all slabs and have bottom y-boundary below yb.
Four-sided queries.
Using the structure for three-sided queries, we can construct a cache-oblivious range tree structure for four-sided orthogonal range queries in a standard way. The structure consists of a cache-oblivious B-tree T on the N points sorted by x-coordinates. With each internal node v we associate a secondary structure for answering three-sided queries on the points stored in the leaves of the subtree rooted at v: If v is the left child of its parent then we have a three-sided structure for answering queries with the opening to the right, and if v is the right child then we have a three-sided structure for answering queries with the opening to the left. The secondary structures on each level of the tree use O(N log N ) space, for a total space usage of O(N log2 N ).
To answer an orthogonal range query Q, we search down T using O(logB N ) memory transfers to find the first node v where the left and right x-coordinate of Q are contained in different children of v. Then we query the right opening secondary structure of the left child of v, and the left opening secondary structure of the right child of v, using O(logB N + K ) memory transfers. Refer to Figure 34.14. It is easy to see that this correctly reports all K points in Q.
THEOREM 34.10 There exists a cache-oblivious data structure for storing N points in the plane using O(N log2 N ) space, such that an orthogonal range query can be answered in O(logB N + K ) memory transfers.
Comments
Post a Comment