# Data Structures

This course contains the basics of Data Structures

Course introduction
Interview Questions
Pragnya Meter Exam

#### Data Structures

Space-partitioning trees
Space partitioning

In mathematics, space partitioning is the process of dividing a space (usually a Euclidean space) into two or more disjoint subsets (see also partition of a set). In other words, space partitioning divides a space into non-overlapping regions. Any point in the space can then be identified to lie in exactly one of the regions. Space-partitioning systems are often hierarchical, meaning that a space (or a region of space) is divided into several regions, and then the same space-partitioning system is recursively applied to each of the regions thus created. The regions can be organized into a tree, called a space-partitioning tree.

Most space-partitioning systems use planes (or, in higher dimensions, hyperplanes) to divide space: points on one side of the plane form one region, and points on the other side form another. Points exactly on the plane are usually arbitrarily assigned to one or the other side. Recursively partitioning space using planes in this way produces a BSP tree, one of the most common forms of space partitioning.

Space partitioning is particularly important in computer graphics, where it is frequently used to organize the objects in a virtual scene. Storing objects in a space-partitioning data structure makes it easy and fast to perform certain kinds of geometry queries — for example, determining whether two objects are close to each other in collision detection, or determining whether a ray intersects an object in ray tracing (Ray Tracing - Auxiliary Data Structures ). In integrated circuit design, an important step is design rule check. This step ensures that the completed design is manufacturable. The check involves rules that specify widths and spacings and other geometry patterns. A modern design can have billions of polygons that represent wires and transistors. Efficient checking relies heavily on geometry query.

For example, a rule may specify that any polygon must be at least n nanometers from any other polygon. This is converted into a geometry query by enlarging a polygon by n at all sides and query to find all intersecting polygons.

Common space partitioning systems include:

• BSP trees
• Octrees
kd-trees
• Bins
• R-trees
• Bounding volume hierarchies

Binary space partitioning

Binary space partitioning (BSP) is a method for recursively subdividing a space into convex sets by hyperplanes. This subdivision gives rise to a representation of the scene by means of a tree data structure known as a BSP tree. Originally, this approach was proposed in 3D computer graphics to increase the rendering efficiency. Some other applications include performing geometrical operations with shapes (constructive solid geometry) in CAD, collision detection in robotics and 3D computer games, and other computer applications that involve handling of complex spatial scenes.

Overview

In computer graphics it is desirable that the drawing of a scene be both correct and quick. A simple way to draw a scene is the painter's algorithm: draw it from back to front painting the background over with each closer object. However, that approach is quite limited since time is wasted drawing objects that will be overdrawn later, and not all objects will be drawn correctly. Z-buffering can ensure that scenes are drawn correctly and eliminate the ordering step of the painter's algorithm, but it is expensive in terms of memory use. BSP trees will split up objects so that the painter's algorithm will draw them correctly without need of a Z-buffer and eliminate the need to sort the objects; as a simple tree traversal will yield them in the correct order. It also serves as base for other algorithms, such as visibility lists, which seek to reduce overdraw.

The downside is the requirement for a time consuming pre-processing of the scene, which makes it difficult and inefficient to directly implement moving objects into a BSP tree. This is often overcome by using the BSP tree together with a Z-buffer, and using the Z-buffer to correctly merge movable objects such as doors and monsters onto the background scene. BSP trees are often used by 3D computer games, particularly first-person shooters and those with indoor environments. Probably the earliest game to use a BSP data structure was Doom (see Doom engine for an in-depth look at Doom's BSP implementation). Other uses include ray tracing and collision detection.

Generation

Binary space partitioning is a generic process of recursively dividing a scene into two until the partitioning satisfies one or more requirements. The specific method of division varies depending on its final purpose. For instance, in a BSP tree used for collision detection, the original object would be partitioned until each part becomes simple enough to be individually tested, and in rendering it is desirable that each part be convex so that the painter's algorithm can be used.

The final number of objects will inevitably increase since lines or faces that cross the partitioning plane must be split into two, and it is also desirable that the final tree remains reasonably balanced. Therefore the algorithm for correctly and efficiently creating a good BSP tree is the most difficult part of an implementation. In 3D space, planes are used to partition and split an object's faces; in 2D space lines split an object's segments. The following picture illustrates the process of partitioning an irregular polygon into a series of convex ones. Notice how each step produces polygons with fewer segments until arriving at G and F, which are convex and require no further partitioning.

In this particular case, the partitioning line was picked between existing vertices of the polygon and intersected none of its segments. If the partitioning line intersects a segment, or face in a 3D model, the offending segment(s) or face(s) have to be split into two at the line/plane because each resulting partition must be a full, independent object.

Since the usefulness of a BSP tree depends upon how well it was generated, a good algorithm is essential. Most algorithms will test many possibilities for each partition until finding a good compromise and might also keep backtracking information in memory so that if a branch of the tree is found to be unsatisfactory other alternative partitions may be tried. Therefore producing a tree usually requires long computations. BSP trees were also used to represent natural images. Construction methods of BSP trees of images were first introduced as efficient representations, where only a few hundred nodes can represent an image that normally require hundreds-of-thousands of pixels.

Fast algorithms were also developed to construct BSP trees of images using computer vision and signal processing algorithms. These algorithms in conjunction with advanced entropy coding and signal approximation approaches were used to develop image compression methods.

Rendering a scene with visibility information from the BSP tree

BSP trees are used to improve rendering performance in calculating visible triangles for the painter's algorithm for instance. The tree can be traversed in linear time from an arbitrary viewpoint.

Since a painter's algorithm works by drawing polygons farthest from the eye first, the following code recurses to the bottom of the tree and draws the polygons. As the recursion unwinds, polygons closer to the eye are drawn over far polygons. Because the BSP tree already splits polygons into trivial pieces, the hardest part of the painter's algorithm is already solved - code for back to front tree traversal.

```  traverse_tree(bsp_tree* tree,point eye)
{
location = tree->find_location(eye);if(tree->empty())return;if(location > 0)    // if eye in front of location
{
traverse_tree(tree->back,eye);
display(tree->polygon_list);
traverse_tree(tree->front,eye);
}else if(location < 0) // eye behind location
{
traverse_tree(tree->front,eye);
display(tree->polygon_list);
traverse_tree(tree->back,eye);
}else    // eye coincidental with  partition hyperplan
{
traverse_tree(tree->front,eye);
traverse_tree(tree->back,eye);
}
}```

Other space partitioning structures

BSP trees divide a region of space into two subregions at each node. They are related to quadtrees and octrees, which divide each region into four or eight subregions, respectively.

Relationship Table

where p is the number of dividing planes used, and s is the number of subregions formed. BSP trees can be used in spaces with any number of dimensions, but quadtrees and octrees are most useful in subdividing 2- and 3-dimensional spaces, respectively. Another kind of tree that behaves somewhat like a quadtree or octree, but is useful in any number of dimensions, is the kd-tree.

Timeline

• 1969 Schumacker et al published a report that described how carefully positioned planes in a virtual environment could be used to accelerate polygon ordering. The technique made use of depth coherence, which states that a polygon on the far side of the plane cannot, in any way, obstruct a closer polygon. This was used in flight simulators made by GE as well as Evans and Sutherland. However, creation of the polygonal data organization was performed manually by scene designer.
• 1980 Fuchs et al. [FUCH80] extended Schumacker’s idea to the representation of 3D objects in a virtual environment by using planes that lie coincident with polygons to recursively partition the 3D space. This provided a fully automated and algorithmic generation of a hierarchical polygonal data structure known as a Binary Space Partitioning Tree (BSP Tree). The process took place as an off-line preprocessing step that was performed once per environment/object. At run-time, the view-dependent visibility ordering was generated by traversing the tree.
• 1981 Naylor's Ph.D thesis containing a full development of both BSP trees and a graph-theoretic approach using strongly connected components for pre-computing visibility, as well as the connection between the two methods. BSP trees as a dimension independent spatial search structure was emphasized, with applications to visible surface determination. The thesis also included the first empirical data demonstrating that the size of the tree and the number of new polygons was reasonable (using a model of the Space Shuttle).
• 1983 Fuchs et al. describe a micro-code implementation of the BSP tree algorithm on an Ikonas frame buffer system. This was the first demonstration of real-time visible surface determination using BSP trees.
• 1987 Thibault and Naylor described how arbitrary polyhedra may be represented using a BSP tree as opposed to the traditional b-rep (boundary representation). This provided a solid representation vs. a surface based-representation. Set operations on polyhedra were described using a tool, enabling Constructive Solid Geometry (CSG) in real-time. This was the fore runner of BSP level design using brushes, introduced in the Quake editor and picked up in the Unreal Editor.
• 1990 Naylor, Amanatides, and Thibault provide an algorithm for merging two bsp trees to form a new bsp tree from the two original trees. This provides many benefits including: combining moving objects represented by BSP trees with a static environment (also represented by a BSP tree), very efficient CSG operations on polyhedra, exact collisions detection in O(log n * log n), and proper ordering of transparent surfaces contained in two interpenetrating objects (has been used for an x-ray vision effect).
• 1990 Teller and Séquin proposed the offline generation of potentially visible sets to accelerate visible surface determination in orthogonal 2D environments.
• 1991 Gordon and Chen [CHEN91] described an efficient method of performing front-to-back rendering from a BSP tree, rather than the traditional back-to-front approach. They utilised a special data structure to record, efficiently, parts of the screen that have been drawn, and those yet to be rendered. This algorithm, together with the description of BSP Trees in the standard computer graphics textbook of the day (Foley, Van Dam, Feiner and Hughes) was used by John Carmack in the making of Doom.
• 1992 Teller’s PhD thesis described the efficient generation of potentially visible sets as a pre-processing step to acceleration real-time visible surface determination in arbitrary 3D polygonal environments. This was used in Quake and contributed significantly to that game's performance.
• 1993 Naylor answers the question of what characterizes a good bsp tree. He used expected case models (rather than worst case analysis) to mathematically measure the expected cost of searching a tree and used this measure to build good BSP trees. Intuitively, the tree represents an object in a multi-resolution fashion (more exactly, as a tree of approximations). Parallels with Huffman codes and probabilistic binary search trees are drawn.
• 1993 Hayder Radha's PhD thesis described (natural) image representation methods using BSP trees. This includes the development of an optimal BSP-tree construction framework for any arbitrary input image. This framework is based on a new image transform, known as the Least-Square-Error (LSE) Partitioning Line (LPE) transform. H. Radha' thesis also developed an optimal rate-distortion (RD) image compression framework and image manipulation approaches using BSP trees.

Segment tree

In computer science, a segment tree is a tree data structure for storing intervals, or segments. It allows querying which of the stored segments contain a given point. It is, in principle, a static structure; that is, its content cannot be modified once the structure is built. A similar data structure is the interval tree.

A segment tree for a set I of n intervals uses O(n log n) storage and can be built in O(n log n) time. Segment trees support searching for all the intervals that contain a query point in O(log n + k), k being the number of retrieved intervals or segments . In the common word-level RAM model, the query time is not optimal, since O(√(log n / log log n)+k) for a query can be achieved by a predecessor search combined with the data structure in.

If the range of all interval end points is in {1,...,O(n)}, a simple data structure with preprocessing time O(n) and query time O(1+k) exists [1]. Applications of the segment tree are in the areas of computational geometry, and geographic information systems. The segment tree can be generalized to higher dimension spaces as well.

Structure description

This section describes the structure of a segment tree in a one -dimensional space. Let S be a set of intervals, or segments. Let p1, p2, ..., pm be the list of distinct interval endpoints, sorted from left toright. Consider the partitioning of the real line induced by those points. The regions of this partitioning are called elementary intervals. Thus, the elementary intervals are, from left to right:

That is, the list of elementary intervals consists of open intervals between two consecutive endpoints pi and pi+1, alternated with closed intervals consisting of a single endpoint. Single points are treated themselves as intervals because the answer to a query is not necessarily the same at the interior of an elementary interval and its endpoints

Graphic example of the structure of the segment tree. This instance is built for the segments shown at the bottom.

Given a set I of intervals, or segments, a segment tree T for I is structured as follows:

• T is a binary tree.
• Its leafs correspond to the elementary intervals induced by the endpoints in I, in an ordered way: the leftmost leaf corresponds to the leftmost interval, and so on. The elementary intervals corresponding to a leaf v is denoted Int(v).
• The internal nodes of T corresponds to intervals that are the union of elementary intervals: the interval Int(N) corresponding to node N is the union of the intervals corresponding to the leafs of the tree rooted at N. That implies that Int(N) is the union of the intervals of its two children.
• Each node or leaf v in T stores the interval Int(v) and a set of intervals, in some data structure. This canonical subset of node v contains the intervals [x, x] from I such that [x, x] contains Int(v) and does not contain Int(parent(v)). That is, each segment in I stores the segments that span through its interval, but does not span through the interval of any parent.

Storage requirements

This section analyzes the storage cost of a segment tree in a one -dimensional space. A segment tree T on a set I of n intervals uses O(nlogn) storage.

Proof:

Lemma: Any interval [x, x] of I is stored in the canonical set for at most two nodes at the same depth.

Proof: Let v1, v2, v3 be the three nodes at the same depth, numbered from left to right; and let w be the parent node of v2. Suppose [x, x] is stored at v1 and v3. This means that [x, x] spans the whole interval from the left endpoint of Int(v1) to the right endpoint of Int(v3). Because v2 lies between v1 and v3, Int(w) must be contained in [x, x]. Hence, [x, x] will not be stored at v2. The set I has at most 4n + 1 elementary intervals. Because T is a binary balanced tree with at most 4n + 1 leaves, its height is O(logn). Since any interval is stored at most twice at a given depth of the tree, that the total amount of storage is O(nlogn) .

Construction

This section describes the construction of a segment tree in a one -dimensional space.

A segment tree from the set of segments I, can be built as follows. First, the endpoints of the intervals in I are sorted. The elementary intervals are obtained from that. Then, a balanced binary tree is built on the elementary intervals, and for each node v it is determined the interval Int(v) it represents. It remains to compute the canonical subsets for the nodes. To achieve this, the intervals in I are inserted one by one into the segment tree. An interval X = [x, x] can be inserted in a subtree rooted at T, using the following procedur :

• If Int(T) is contained in X then store X at T, and finish.
• Else:
• If X intersects the canonical subset of the left child of T, then insert X in that child, recursively.
• If X intersects the canonical subset of the right child of T, then insert X in that child, recursively.

The complete construction operation takes O(nlogn) time, being n the amount of segments in I.

Proof Sorting the endpoints takes O(nlogn). Building a balanced binary tree from the sorted endpoints, takes linear time on n. The insertion of an interval X = [x, x] into the tree, costs O(logn).

Proof: Visiting every node takes constant time (assuming that canonical subsets are stored in a simple data structure like a linked list). When we visit node v, we either store X at v, or Int(v) contains an endpoint of X. As proved above, an interval is stored at most twice at each level of the tree. There is also at most one node at every level whose corresponding interval contains x, and one node whose interval contains x. So, at most four nodes per level are visited. Since there are O(logn) levels, the total cost of the insertion is O(logn).

Query

This section describes the query operation of a segment tree in a one -dimensional space.

A query for a segment tree, receives a point qx, and retrieves a list of all the segments stored which contain the point qx. Formally stated; given a node (subtree) v and a query point qx, the query can be done using the following algorithm:

• Report all the intervals in I(v).
• If v is not a leaf:
• If qx is in Int(left child of v) then
• Perform a query in the left child of v.
• Else
• Perform a query in the right child of v.

In a segment tree that contains n intervals, those containing a given query point can be reported in O(logn + k) time, where k is the number of reported intervals.

Proof: The query algorithm visits one node per level of the tree, so O(logn) nodes in total. In the other hand, at a node v, the segments in I are reported in O(1 + kv) time, where kv is the number of intervals at node v, reported. The sum of all the kv for all nodes v visited, is k, the number of reported segments.

Generalization for higher dimensions

The segment tree can be generalized to higher dimension spaces, in the form of multi-level segment trees. In higher dimension versions, the segment tree stores a collection of axis-parallel (hyper-)rectangles, and can retrieve the rectangles that contain a given query point. The structure uses O(nlogd-1n) storage, and answers queries in O(logdn). The use of fractional cascading lowers the query time bound by a logarithmic factor. The use of the Interval tree on the deepest level of associated structures lowers the storage bound with a logarithmic factor.

Notes

The query that asks for all the intervals containing a given point, is often referred as stabbing query .

The segment tree is less efficient than the interval tree for range queries in one dimension, due to its higher storage requirement: O(nlogn) against the O(n) of the interval tree. The importance of the segment tree is that the segments within each node’s canonical subset can be stored in any arbitrary manner.

Another plus of the segment tree, is that it can easily be adapted to counting queries; that is, report the number of segments containing a given point, instead of reporting the segments themselves. Instead of storing the intervals in the canonical subsets, it can simply be stored an integer representing their amount. Such a segment tree uses linear storage, and requires an O(log n) query time.

A version for higher dimensions of the interval tree and the priority search tree does not exist, that is, there is no clear extension of these structures that solves the analogous problem in higher dimensions. But the structures can be used as associated structure of segment trees

Interval tree

In computer science, an interval tree is an ordered tree data structure to hold intervals. Specifically, it allows one to efficiently find all intervals that overlap with any given interval or point. It is often used for windowing queries, for example, to find all roads on a computerized map inside a rectangular viewport, or to find all visible elements inside a three-dimensional scene. The trivial solution is to visit each interval and test whether it intersects the given point or interval, which requires Θ(n) time, where n is the number of intervals in the collection.

Since a query may return all intervals, for example if the query is a large interval intersecting all intervals in the collection, this is asymptotically optimal; however, we can do better by considering output-sensitive algorithms, where the runtime is expressed in terms of m, the number of intervals produced by the query. Interval trees are dynamic, i.e., they allow inserting or deleting intervals. They obtain a query time of O(log n) while the preprocessing time to construct the data structure is O(n log n) (but the space consumption is O(n)). Data structures with better query times and preprocessing time exists for the static setting: If the unit-cost word RAM is the model of computation, O(√(log n / log log n)+m) can be obtained for each query. If the range of interval end points is in {1,...,O(n)}, a preprocessing time of O(n) with a query time of O(1+m) is possible [Schmidt].

Naive approach

In a simple case, the intervals do not overlap and they can be inserted into a simple binary tree and queried in O(log n) time. However, with arbitrarily overlapping intervals, there is no way to compare two intervals for insertion into the tree since orderings sorted by the beginning points or the ending points may be different. A naive approach might be to build two parallel trees, one ordered by the beginning point, and one ordered by the ending point of each interval. This allows discarding half of each tree in O(log n) time, but the results must be merged, requiring O(n) time. This gives us queries in O(n + log n) = O(n), which is no better than brute-force. Interval trees solve this problem. This article describes two alternative designs for an interval tree, dubbed the centered interval tree and the augmented tree.

Centered interval tree

Queries require O(log n + m) time, with n being the total number of intervals and m being the number of reported results. Construction requires O(n log n) time, and storage requires O(n) space.

Construction

Given a set of n intervals on the number line, we want to construct a data structure so that we can efficiently retrieve all intervals overlapping another interval or point. We start by taking the entire range of all the intervals and dividing it in half at x _center (in practice, x _center should be picked to keep the tree relatively balanced). This gives three sets of intervals, those completely to the left of x _center which we'll call S _left, those completely to the right of x_center which we'll call S_right, and those overlapping x _center which we'll call S _center.

The intervals in S _left and S _right are recursively divided in the same manner until there are no intervals left. The intervals in S _center that overlap the center point are stored in a separate data structure linked to the node in the interval tree. This data structure consists of two lists, one containing all the intervals sorted by their beginning points, and another containing all the intervals sorted by their ending points. The result is a binary tree with each node storing:

• A center point
• A pointer to another node containing all intervals completely to the left of the center point
• A pointer to another node containing all intervals completely to the right of the center point
• All intervals overlapping the center point sorted by their beginning point
• All intervals overlapping the center point sorted by their ending point

Intersecting

Given the data structure constructed above, we receive queries consisting of ranges or points, and return all the ranges in the original set overlapping this input.

With an Interval

First, we can reduce the case where an interval R is given as input to the simpler case where a single point is given as input. We first find all ranges with beginning or end points inside the input interval R using a separately constructed tree. In the one-dimensional case, we can use a simple tree containing all the beginning and ending points in the interval set, each with a pointer to its corresponding interval.

A binary search in O(log n) time for the beginning and end of R reveals the minimum and maximum points to consider. Each point within this range references an interval that overlaps our range and is added to the result list. Care must be taken to avoid duplicates, since an interval might begin and end within R. This can be done using a binary flag on each interval to mark whether or not it has been added to the result set. The only intervals not yet considered are those overlapping R that do not have a point inside R, in other words, intervals that enclose it. To find these, we pick any point inside R and use the algorithm below to find all intervals intersecting that point (again, being careful to remove duplicates).

With a Point

The task is to find all intervals in the tree that overlap a given point x. The tree is walked with a similar recursive algorithm as would be used to traverse a traditional binary tree, but with extra affordance for the intervals overlapping the "center" point at each node. For each tree node, x is compared to x _center, the midpoint used in node construction above. If x is less than x _center, the leftmost set of intervals, S _left, is considered. If x is greater than x _center, the rightmost set of intervals, S _right, is considered. As each node is processed as we traverse the tree from the root to a leaf, the ranges in its S _center are processed. If x is less than x _center, we know that all intervals in S _center end after x, or they could not also overlap x _center. Therefore, we need only find those intervals in S _center that begin before x.

We can consult the lists of S _center that have already been constructed. Since we only care about the interval beginnings in this scenario, we can consult the list sorted by beginnings. Suppose we find the closest number no greater than x in this list. All ranges from the beginning of the list to that found point overlap x because they begin before x and end after x (as we know because they overlap x _center which is larger than x).

Thus, we can simply start enumerating intervals in the list until the endpoint value exceeds x. Likewise, if x is greater than x _center, we know that all intervals in S _center must begin before x, so we find those intervals that end after x using the list sorted by interval endings. If x exactly matches x _center, all intervals in S _center can be added to the results without further processing and tree traversal can be stopped.

Higher Dimensions

The interval tree data structure can be generalized to a higher dimension N with identical query and construction time and O(n log n) space. First, a range tree in N dimensions is constructed that allows efficient retrieval of all intervals with beginning and end points inside the query region R. Once the corresponding ranges are found, the only thing that is left are those ranges that enclose the region in some dimension. To find these overlaps, N interval trees are created, and one axis intersecting R is queried for each. For example, in two dimensions, the bottom of the square R (or any other horizontal line intersecting R) would be queried against the interval tree constructed for the horizontal axis.

Likewise, the left (or any other vertical line intersecting R) would be queried against the interval tree constructed on the vertical axis. Each interval tree also needs an addition for higher dimensions. At each node we traverse in the tree, x is compared with S _center to find overlaps. Instead of two sorted lists of points as was used in the one-dimensional case, a range tree is constructed. This allows efficient retrieval of all points in S _center that overlap region R.

Deletion

If after deleting an interval from the tree, the node containing that interval contains no more intervals, that node may be deleted from the tree. This is more complex than a normal binary tree deletion operation. An interval may overlap the center point of several nodes in the tree. Since each node stores the intervals that overlap it, with all intervals completely to the left of its center point in the left subtree, similarly for the right subtree, it follows that each interval is stored in the node closest to the root from the set of nodes whose center point it overlaps.

Normal deletion operations in a binary tree (for the case where the node being deleted has two children) involve promoting a node further from the root to the position of the node being deleted (usually the leftmost child of the right subtree, or the rightmost child of the left subtree). As a result of this promotion, some nodes that were above the promoted node will become descendents of it; it is necessary to search these nodes for intervals that also overlap the promoted node, and move those intervals into the promoted node. As a consequence, this may result in new empty nodes, which must be deleted, following the same algorithm again.

Balancing

The same issues that affect deletion also affect rotation operations; rotation must preserve the invariant that intervals are stored as close to the root as possible.

Augmented tree

Another way to represent intervals is described in CLRS, Section : Interval trees. Both insertion and deletion require O(log n) time, with n being the total number of intervals. Use a simple ordered tree, for example a binary search tree or self-balancing binary search tree, where the tree is ordered by the 'low' values of the intervals, and an extra annotation is added to every node recording the maximum high value of both its subtrees. It is simple to maintain this attribute in only O(h) steps during each addition or removal of a node, where h is the height of the node added or removed in the tree, by updating all ancestors of the node from the bottom up. Additionally, the tree rotations used during insertion and deletion may require updating the high value of the affected nodes.

Now, it's known that two intervals A and B overlap only when both A.low ≤ B.high and A.high ≥ B.low. When searching the trees for nodes overlapping with a given interval, you can immediately skip:

• all nodes to the right of nodes whose low value is past the end of the given interval.
• all nodes that have their maximum 'high' value below the start of the given interval.

A total order can be defined on the intervals by ordering them first by their 'low' value and finally by their 'high' value. This ordering can be used to prevent duplicate intervals from being inserted into the tree in O(log n) time, versus the O(k + log n) time required to find duplicates if k intervals overlap a new interval.

Java Example: Adding a new interval to the tree

The key of each node is the interval itself and the value of each node is the end point of the interval:

```  public void add(Interval i) {
put(i, i.getEnd());
}```

Java Example: Searching a point or an interval in the tree

To search for an interval, you walk the tree, omitting those branches which can't contain what you're looking for. The simple case is looking for a point:

```// Search for all intervals which contain "p",     starting with the// node "n" and adding matching intervals to the    list  "result"public void search(IntervalNode n, Point p, List<
Interval> result) {// Don't search nodes that don't existif (n == null)return;// If p is to the right of the rightmost point of any interval// in this node and all children, there won't be any matches.if (p.compareTo(n.getValue()) > 0)return;// Search left childrenif (n.getLeft() != null)
search(cast(n.getLeft()), p, result);// Check this nodeif (n.getKey().contains(p))
result.add(n.getKey());// If p is to the left of the start of this interval,// then it can't be in any child to the right.if (p.compareTo(n.getKey().getStart()) < 0)return;// Otherwise, search right childrenif (n.getRight() != null)
search(cast(n.getRight()), p, result);
}```
```The code to search for an interval is exactly the same except
for the check in the middle:// Check this nodeif (n.getKey().overlapsWith(i))

overlapsWith() is defined as:

republic boolean overlapsWith(Interval other) {
return start.compareTo(other.getEnd()) <= 0 &&
end.compareTo(other.getStart()) >= 0;
}

Higher dimension

This can be extended to higher dimensions by cycling through the dimensions at each level of the tree. For example, for two dimensions, the odd levels of the tree might contain ranges for the x coordinate, while the even levels contain ranges for the y coordinate. However, it is not quite obvious how the rotation logic will have to be extended for such cases to keep the tree balanced. A much simpler solution is to use nested interval trees. First, create a tree using the ranges for the y coordinate. Now, for each node in the tree, add another interval tree on the the x ranges, for all elements whose y range intersect that node's y range.

The advantage of this solution is that it can be extended to an arbitrary amount of dimensions using the same code base. At first, the cost for the additional trees might seem prohibitive but that is usually not the case. As with the solution above, you need one node per x coordinate, so this cost is the same in both solutions. The only difference is that you need an additional tree structure per vertical interval. This structure is typically very small (a pointer to the root node plus maybe the number of nodes and the height of the tree).

Range tree

In computer science, a range tree is an ordered tree data structure to hold a list of points. It allows all points within a given range to be efficiently retrieved, and is typically used in two or higher dimensions. It is similar to a kd-tree except with faster query times of O(logd n + k) but worse storage of O(n log(d-1) n), with d being the dimension of the space, n being the number of points in the tree, and k being the number of points retrievedfor a given query. Range trees may be contrasted with interval trees: instead o storing points and allowing points in a given range to beretrieved efficiently, an interval tree stores intervals and allows the intervals containing a given point to be retrievedefficiently.

Bin

In computational geometry, the bin data structure allows efficient region queries, i.e., if there are some axis-aligned rectangles on a 2D plane, answer the question Given a queryrectangle, return all rectangles intersecting it. kd-tree is another data structure that can answer this question efficiently. In the example in the figure, A, B, C, D, E, and F are existing rectangles, the query with the rectangle Q should return C, D, E and F, if we define allrectangles as closed intervals. The data structure partitions a region of the 2D plane into uniform-sized bins. The bounding box of the bins encloses all candidate rectangles to be queried.

All the bins are arranged in a 2D array. All the candidates are represented also as 2D arrays. The size of a candidate's array is the number of bins it intersects. For example, in the figure, candidate B has 6 elements arranged in a 3 row by 2 column array because it intersects 6 bins in such an arrangement. Each bin contains the head of a singly-linked list. If a candidate intersects a bin, it is chained to the bin's linked list. Each element in a candidate's array is a link node in the corresponding bin's linked list.

The bin data structure

Operations

Query

From the query rectangle Q, we can find out which bin its lower-left corner intersects efficiently by simply subtracting the bin's bounding box's lower-left corner from the lower-left corner of Q and dividing the result by the width and height of a bin respectively. We then iterate the bins Q intersects and examine all the candidates in the linked-lists of these bins. For each candidate we check if it does indeed intersect Q. If so and it is not previously reported, then we report it. We can use the convention that we only report a candidate the first time we find it. This can be done easily by clipping the candidate against the query rectangle and comparing its lower-left corner against the current location. If it is a match then we report, otherwise we skip.

Insertion and deletion

Insertion is linear to the number of bins a candidate intersects because inserting a candidate into 1 bin is constant time. Deletion is more expensive because we need to search the singly-linked list of each bin the candidate intersects. In a multithread environment, insert, delete and query are mutually exclusive. However, instead of locking the whole data structure, a sub-range of bins may be locked. Detailed performance analysis should be done to justify the overhead.

Efficiency and tuning

The analysis is similar to a hash table. The worst-case scenario is that all candidates are concentrated in one bin. Then query is O(n), delete is O(n), and insert is O(1), where n is the number of candidates. If the candidates are evenly spaced so that each bin has a constant number of candidates, The query is O(k) where k is the number of bins the query rectangle intersects. Insert and delete are O(m) where m is the number of bins the inserting candidate intersects. In practice delete is much slower than insert. Like a hash table, bin's efficiency depends a lot on the distribution of both location and size of candidates and queries.

In general, the smaller the query rectangle, the more efficient the query. The bin's size should be such that it contains as few candidates as possible but large enough so that candidates do not span too many bins. If a candidate span many bins, a query has to skip this candidate over and over again after it is reported at the first bin of intersection. For example, in the figure, E is visited 4 times in the query of Q and so has to be skipped 3 times. To further speed up the query, divisions can be replaced by right shifts. This requires the number of bins along an axis direction to be an exponent of 2.

Compared to other range query data structures

Against kd-tree, the bin structure allows efficient insertion and deletion without the complexity of rebalancing. This can be very useful in algorithms that need to incrementally add shapes to the search data structure.

kd- tree

In computer science, a kd-tree (short for k-dimensional tree) is a space partitioning data structure for organizing points in a k-dimensional space. Kd trees are a useful data structure for several applications, such as searches involving a multidimensional search key (e.g. range searches and nearest neighbor searches). kd-trees are a special case of BSP trees.

Informal Description

The kd-tree is a binary tree in which every node is a k-dimensional point. Every non-leaf node can be thought of as implicitly generating a splitting hyperplane that divides the space into two parts, known as subspaces. Points to the left of this hyperplane represent the left sub-tree of that node and points right of the hyperplane are represented by the right sub-tree. The hyperplane direction is chosen in the following way: every node in the tree is associated with one of the k-dimensions, with the hyperplane perpendicular to that dimension's axis. So, for example, if for a particular split the "x" axis is chosen, all points in the subtree with a smaller "x" value than the node will appear in the left subtree and all points with larger "x" value will be in the right sub tree. In such a case, the hyperplane would be set by the x-value of the point, and its normal would be the unit x-axis.

Operations on kd-trees

Construction

Since there are many possible ways to choose axis-aligned splitting planes, there are many different ways to construct kd-trees. The canonical method of kd-tree construction has the following constraints:

• As one moves down the tree, one cycles through the axes used to select the splitting planes. (For example, the root would have an x-aligned plane, the root's children would both have y-aligned planes, the root's gran children would all have z-aligned planes, the next level would have an x-aligned plane, and so on.)
• Points are inserted by selecting the median of the points being put into the subtree, with respect to their coordinates in the axis being used to create the splitting plane.

(Note the assumption that we feed the entire set of points into the algorithm up-front.) This method leads to a balanced kd-tree, in which each leaf node is about the same distance from the root. However, balanced trees are not necessarily optimal for all applications. Note also that it is not required to select the median point. In that case, the result is simply that there is no guarantee that the tree will be balanced. A simple heuristic to avoid coding a complex linear-time median-finding algorithm nor using an O(n log n) sort is to use sort to find the median of a fixed number of randomly selected points to serve as the cut line. Practically this technique often results in nicely balanced trees. Given a list of n points, the following algorithm will construct a balanced kd-tree containing those points.

```  function kdtree
(list  of points pointList, int depth)
{if pointList is  emptyreturn  nil;else
{//  Select axis based on depth so that axis cycles through allvalid  valuesvar int axis := depth mod k;//  Sort point list and choose median as pivot elementselect median by axis from pointList;//  Create node and construct subtreesvar tree_node node;
node.location := median;
node.leftChild := kdtree(points in pointList before median,
depth+1);
node.rightChild := kdtree(points in pointList after median,
depth+1);return node;
}
}```

It is common that points "after" the median include only ones that are greater than or equal to the median. Another approach is to define a "superkey" function that compares the points in other dimensions. Lastly, it may be acceptable to let points equal to the median lie on either side. This algorithm implemented in the Python programming language is as follows:

```   class Node:passdef kdtree(pointList, depth=0):if not pointList:return# Select axis based on depth so that axis cycles through all  valid
values
k = len(pointList[0]) # assumes all points have the same dimension
axis = depth % k# Sort point list and choose median as pivot element
pointList.sort(key=lambda point: point[axis])
median = len(pointList)/2 # choose median# Create node and construct  subtrees
node = Node()
node.location = pointList[median]
node.leftChild = kdtree(pointList[0:median], depth+1)
node.rightChild = kdtree(pointList[median+1:], depth+1)return node```

The tree generated is shown on the right. This algorithm creates the invariant that for any node, all the nodes in the left subtree are on one side of a splitting plane, and all the nodes in the right subtree are on the other side. Points that lie on the splitting plane may appear on eithe side. The splitting plane of a node goes through the point associated with that node (referred to in the code as node.location).

The resulting kd-tree decomposition.

One adds a new point to a kd-tree in the same way as one adds an element to any other search tree. First, traverse the tree, starting from the root and moving to either the left or the right child depending on whether the point to be inserted is on the "left" or "right" side of the splitting plane. Once you get to the node under which the child should be located, add the new point as either the left or right child of the leaf node, again depending on which side of the node's splitting plane contains the new node. Adding points in this manner can cause the tree to become unbalanced, leading to decreased tree performance. The rate of tree performance degradation is dependent upon the spatial distribution of tree points being added, and the number of points added in relation to the tree size.

If a tree becomes too unbalanced, it may need to be re-balanced to restore the performance of queries that rely on the tree balancing, such as nearest neighbour searching.

Removing elements

To remove a point from an existing kd-tree, without breaking the invariant, the easiest way is to form the set of all nodes and leaves from the children of the target node, and recreate that part of the tree. This differs from regular search trees in that no child can be selected for a "promotion", since the splitting plane for lower-level nodes is not along the required axis for the current tree level.

Balancing

Balancing a kd-tree requires care. Because kd-trees are sorted in multiple dimensions, the tree rotation technique cannot be used to balance them — this may break the invariant.

Nearest neighbor search

The nearest neighbor (NN) algorithm aims to find the point in the tree which is nearest to a given input point. This search can be done efficiently by using the tree properties to quickly eliminate large portions of the search space. Searching for a nearest neighbor in a kd-tree proceeds as follows:

1. Starting with the root node, the algorithm moves down the tree recursively, in the same way that it would if the search point were being inserted (i.e. it goes right or left depending on whether the point is greater or less than the current node in the split dimension).
2. Once the algorithm reaches a leaf node, it saves that node point as the "current best"
3. The algorithm unwinds the recursion of the tree, performing the following steps at each node:
1. If the current node is closer than the current best, then it becomes the current best.
2. The algorithm checks whether there could be any points on the other side of the splitting plane that are closer to the search point than the current best. In concept, this is done by intersecting the splitting hyperplane with a hypersphere around the search point that has a radius equal to the current nearest distance. Since the hyperplanes are all axis-aligned this is implemented as a simple comparison to see whether the difference between the splitting coordinate of the search point and current node is less than the distance (overall coordinates) from the search point to the current best.

Animation of NN searching with a KD Tree in 2D

1. If the hypersphere crosses the plane, there could be nearer points on the other side of the plane, so the algorithm must move down the other branch of the tree from the current node looking for closer points, following the same recursive process as the entire search.
2. If the hypersphere doesn't intersect the splitting plane, then the algorithm continues walking up the tree, and the entire branch on the other side of that node is eliminated.
3. When the algorithm finishes this process for the root node, then the search is complete.

Generally the algorithm uses squared distances for comparison to avoid computing square roots. Additionally, it can save computation by holding the squared current best distance in a variable for comparison.

```   Sample LUA - NN Searchfunction kdsearchnn( here, point, best )if here == nil thenreturn bestendif best == nil then
best = hereend-- consider the current node --
disthere = distance(here,point)
distbest = distance(best,point)if disthere < distbest then
best = hereend-- search the near branch --
child = child_near(here,point)
best = kdsearchnn( child,  point, best )-- search the away branch - maybe --
distbest = distance(best,point)
distaxis = distance_axis(here,point)if distaxis < distbest then
child = child_away(here,point)
best = kdsearchnn( child,  point, best )endreturn bestend```

Finding the nearest point is an O(log N) operation in the case of randomly distributed points if N. Analyses of binary search trees has found that the worst case search time for an k-dimensional KD tree containing N nodes is given by the following equation .

These poor running times only apply when N is on the order of the number of dimensions. In very high dimensional spaces, the curse of dimensionality causes the algorithm to need to visit many more branches than in lower dimensional spaces. In particular, when the number of points is only slightly higher than the number of dimensions, the algorithm is only slightly better than a linear search of all of the points. The algorithm can be extended in several ways by simple modifications. It can provide the k-Nearest Neighbors to a point by maintaining k current bests instead of just one. Branches are only eliminated when they can't have points closer than any of the k current bests. It can also be converted to an approximation algorithm to run faster.

For example, approximate nearest neighbor searching can be achieved by simply setting an upper bound on the number points to examine in the tree, or by interrupting the search process based upon a real time clock (which may be more appropriate in hardware implementations). Nearest neighbour for points that are in the tree already can be achieved by not updating the refinement for nodes that give zero distance as the result, this has the downside of discarding points that are not unique, but are co-located with the original search point. Approximate nearest neighbor is useful in real time applications such as robotics due to the significant speed increase gained by not searching for the best point exhaustively. One of its implementations is Best Bin First.

High-Dimensional Data

kd-trees are not suitable for efficiently finding the nearest neighbour in high dimensional spaces. As a general rule, if the dimensionality is k, then number of points in the data, N, should be N >> 2k. Otherwise, when kd-trees are used with high -dimensional data, most of the points in the tree will be evaluated and the efficiency is no better than exhaustive search and approximate nearest-neighbour methods are used instead.

Complexity

• Building a static kd-tree from n points takes O(n log 2 n) time if an O(n log n) sort is used to compute the median at each level. The complexity is O(n log n) if a linear median-finding algorithm such as the one described in Cormen et al. is used.
• Inserting a new point into a balanced kd-tree takes O(log n) time.
• Removing a point from a balanced kd-tree takes O(log n) time.
• Querying an axis-parallel range in a balanced kd-tree takes O(n1-1/k +m) time, where m is the number of the reported points, and k the dimension of the kd-tree.

Variations

Instead of points, a kd-tree can also contain rectangles or hyper rectangles. A 2D rectangle is considered a 4D object (xlow, xhigh, ylow, yhigh). Thus range search becomes the problem of returning all rectangles intersecting the search rectangle. The tree is constructed the usual way with all the rectangles at the leaves. In an orthogonal range search, the opposite coordinate is used when comparing against the median. For example, if the current level is split along xhigh, we check the xlow coordinate of the search rectangle. If the median is less than the xlow coordinate of the search rectangle, then no rectangle in the left branch can ever intersect with the search rectangle and so can be pruned. Otherwise both branches should be traversed. See also interval tree, which is a 1-dimensional special case.

Points only in leaves

It is also possible to define a kd-tree with points stored solely in leaves . This form of kd-tree allows a variety of split mechanics other than the standard median split. The midpoint splitting rule[6] selects on the middle of the longest axis of the space being searched, regardless of the distribution of points. This guarantees that the aspect ratio will be at most 2:1, but the depth is dependent on the distribution of points. A variation, called sliding-midpoint, only splits on the middle if there are points on both sides of the split. Otherwise, it splits on point nearest to the middle. Maneewongvatana and Mount show that this offers "good enough" performance on common data sets. Using sliding-midpoint, an approximate nearest neighbor query can be answered in  Approximate range counting can be answered in

with this method.

Implicit kd- tree

An implicit kd-tree is a kd-tree defined implicitly above a rectilinear grid. Its split planes' positions and orientations are not given explicitly but implicitly by some recursive splitting-function defined on the hyperrectangles belonging to the tree's nodes. Each inner node's split plane is positioned on a grid plane of the underlying grid, partitioning the node's grid into two subgrids.

Nomenclature and References

The terms "min/max kd-tree" and "implicit kd-tree" are sometimes mixed up. This is because the first publication nusing the term "implicit kd-tree" did actually use explicit min/max kd-trees but referred to them as "implicit kd-trees" to indicate that they may be used to ray trace implicitly given iso surfaces. Nevertheless this publication used also slim kd-trees which are a subset of the implicit kd-trees with the restriction that they can only be built over integer hyperrectangles with sidelengths that are powers of two.

Implicit kd-trees as defined here have shortly after been introduced . A nice overview to implicit kd-trees can be found in. As it is possible to assign attributes to implicit kd-tree nodes, one may refer to an implicit kd-tree which has min/max values assigned to its nodes as an "implicit min/max

kd-tree".

Construction and storage of a 2D implicit max kd-tree using the grid median splitting-function. Each cell of the rectilinear grid has one scalar value from low (bright blue) to high (bright red) assigned to it. The grid's memory footprint is indicated in the lower line. The implicit max kd-tree's predefined memory footprint needs one scalar value less than that. The storing of the node's max values is indicated in the upper line.

Construction

Implicit kd-trees are in general not constructed explicitly. When accessing a node, its split plane orientation and position are evaluated using the specific splitting-function defining the tree. Different splitting-functions may result in different trees for the same underlying grid.

Splitting-functions

Splitting-functions may be adapted to special purposes. Underneath two specifications of special splitting-function classes.

• Non-degenerated splitting-functions do not allow the creation of degenerated nodes (nodes whose corresponding integer hyperrectangle's volume is equal zero). Their corresponding implicit kd-trees are full binary trees, which have for n leaf nodes n - 1 inner nodes. Their corresponding implicit kd-trees are non-degeneratedimplicit kd-trees.
• complete splitting -functions are non -degenerated splitting -functions whose corresponding implicit kd-tree's leaf nodes are single grid cells such that they have one inner node less than the amount of gridcells given in the grid. The corresponding implicit kd-trees are complete implicit kd-trees. A complete splitting function is for example the grid median splitting function. It creates fairly balanced implicit kd-trees by using k-dimensional integer hyperrectangles hyprec[2][k] belonging to each node of the implicit kd-tree.

The hyperrectangles define which gridcells of the rectilinear grid belong to their corresponding node. If the volume of this hyperrectangle equals one, the corresponding node is a single grid cell and is therefore not further subdivided and marked as leaf node. Otherwise the hyperrectangle's longest extend is chosen as orientation o. The corresponding split plane p is positioned onto the grid plane that is closest to the hyperrectangle's grid median along that orientation.

Split plane orientation o:

``` o = min{argmax(i = 1 ... k: (hyprec[1][i] - hyprec[0][i]))}
Split plane position p: p = roundDown((hyprec[0][o] + hyprec[1][o]) / 2) ```

Assigning attributes to implicit kd-tree-nodes

An obvious advantage of implicit kd-trees is that their split plane's orientations and positions need not to be stored explicitly. But some applications require besides the split plane's orientations and positions further attributes at the inner tree nodes. These attributes may be for example single bits or single scalar values, defining if the subgrids belonging to the nodes are of interest or not. For complete implicit kd-trees it is possible to pre-allocate a correctly sized array of attributes and to assign each inner node of the tree to a unique element in that allocated array.

The amount of gridcells in the grid is equal the volume of the integer hyperrectangle belonging to the grid. As a complete implicit kd-tree has one inner node less than grid cells, it is known in advance how many attributes need to be stored. The relation "Volume of integer hyperrectangle to inner nodes" defines together with the complete splitting -function a recursive formula assigning to each split plane a unique element in the allocated array. The corresponding algorithm is given in C-pseudo code underneath.

//Assigning attributes to inner nodes of a complete implicit kd-tree

```  // create an integer help hyperrectangle hyprec    (its volume vol(hyprec)is  equal the amount of leaves)int hyprec[2][k] = ;
// allocate once the array of attributes for the entire implicit
kd-treeattr *a = new attr[volume(hyprec) - 1];attr implicitKdTreeAttributes(int hyprec[2][k], attr *a)
{if(vol(hyprec) > 1) // the  current node is an inner node
{
// evaluate the split plane's orientation o and its position using the underlying complete split-function
int o, p;
completeSplittingFunction(hyprec, &o, &p);
// evaluate the children's integer hyperrectangles hyprec_l and
hyprec_r
int hyprec_l[2][k], hyprec_r[2][k];
hyprec_l = hyprec;
hyprec_l[1][o] = p;
hyprec_r = hyprec;
hyprec_r[0][o] = p;
// evaluate the children's  memory location a_l and a_r
attr* a_l = a + 1;
attr* a_r = a + vol(hyprec_l);
// evaluate recursively the  children's attributes c_l and c_r
attr c_l = implicitKdTreeAttributes(hyprec_l, a_l);
attr c_r = implicitKdTreeAttributes(hyprec_r, a_r);
// merge the children's  attributes to the current attribute c
attr c = merge(c_l, c_r);
// store the current attribute  and return it
a[0] = c;return c;
}
// The current node is a leaf  node. Return the attribute belonging tothe corresponding gridcellreturn attribute(hyprec);
}```

It is worth mentioning that this algorithm works for all rectilinear grids. The corresponding integer hyperrectangle does not necessarily have to have sidelengths that are powers of two.

Applications

Implicit max-kd trees are used for ray casting isosurfaces/MIP (maximum intensity projection). The attribute assigned to each inner node is the maximal scalar value given in the subgrid belonging to the node. Nodes ar not traversed if their scalar values are smaller than the searched iso value/current maximum intensity along the ray. The low storage requirements of the implicit max kd-tree and the favorible visualization complexity of ray casting allow to ray cast (and even change the isosurface for) very large scalar fields at interactive framerates on commodity PCs.

Complexity

Given an implicit kd-tree spanned over an k-dimensional grid with n gridcells.

• Assigning attributes to the nodes of the tree takes O(kn) time.
• Storing attributes to the nodes takes O(n) memory.
• Ray casting iso-surfaces/MIP an underlying scalar field using the corresponding implicit max kd-tree takes roughly O(lg(n)) time.

min/ max kd- tree

A min/max kd-tree is a kd-tree with two scalar values - a minimum and a maximum - assigned to its nodes. The minimum/ maximum of an inner node is equal the minimum/maximum of its children's minima/ maxima.

Construction

Min/max kd-trees may be constructed recursively. Starting with the root node, the splitting plane orientation and position is evaluated. Then the children's splitting planes and min/max values are evaluated recursively. The min/max value of the current node is simply the minimum/maximum of its children's minima/maxima.

Properties

The min/max kdtree has - besides the properties of an kd-tree - the special property that an inner node's min/max values coincide each with a min/max value of either one child. This allows to discard the storage of min/max values at the leaf nodes by storing two bits at inner nodes, assigning min/max values to the children: Each inner node's min/max values will be known in advance, where the root node's min/max values are stored separately. Each inner node has besides two min/max values also two bits given, defining to which child those min/max values are assigned (0: to the left child 1: to the right child). The non-assigned min/max values of the children are the from the current node already known min/max values.

The two bits may also be stored in the least significant bits of the min/max values which have therefore to be approximated by fractioning them down/up. The resulting memory reduction is not minor, as the leaf nodes of full binary kd-trees are one half of the tree's nodes.

Applications

Min/max kd-trees are used for ray casting isosurfaces/MIP (maximum intensity projection). Isosurface ray casting only traverses nodes for which the chosen isovalue lies in between the min/max value of the current node. Nodes that do not fulfill that requirement do not contain an isosurface to the given isovalue and are therefore skipped (empty space skipping). For MIP are nodes not traversed if their maximum is smaller than the current maximum intensity along the ray. The favorible visualization complexity of ray casting allows to ray cast (and even change the isosurface for) very large scalar fields at interactive framerates on commodity PCs. Especial implicit max kd-trees are an optimal choice for visualizing scalar fields defined on rectilinear grids.

An adaptive k-d tree is a tree for multidimensional points where successive levels may be split along different dimensions.

A quadtree is a tree data structure in which each internal node has up to four children. Quadtrees are most often used to partition a two dimensional space by recursively subdividing it into four quadrants or regions. The regions may be square or rectangular, or may have arbitrary shapes. This data structure was named a quadtree by Raphael Finkel and J.L. Bentley in 1974. A similar partitioning is also known as a Q-tree. All forms of Quadtrees share some common features:

A region quadtree with point data

• They decompose space into adaptable cells
• Each cell(or bucket) has a maximum capacity. When maximum capacity is reached, the bucket splits
• The tree directory follows the spatial decomposition of the Quadtree

Types

Quadtrees may be classified according to the type of data they represent, including areas, points, lines and curves. Quadtrees may also be classified by whether the shape of the tree is independent of the order data is processed. Some common types of quadtrees are:

The region quadtree represents a partition of space in two dimensions by decomposing the region into four equal quadrants, subquadrants, and so on with each leaf node containing data corresponding to a specific subregion. Each node in the tree either has exactly four children, or has no children (a leaf node). The region quadtree is not strictly a 'tree' - as the positions of subdivisions are independent of the data. They are more precisely called 'tries'. A region quadtree with a depth of n may be used to represent an image consisting of 2n × 2n pixels, where each pixel value is 0 or 1. The root node represents the entire image region.

If the pixels in any region are not entirely 0s or 1s, it is subdivided. In this application, each leaf node represents a block of pixels that are all 0s or all 1s. A region quadtree may also be used as a variable resolution representation of a data field. For example, the temperatures in an area may be stored as a quadtree, with each leaf node storing the average temperature over the subregion it represents.

If a region quadtree is used to represent a set of point data (such as the latitude and longitude of a set of cities), regions are subdivided until each leaf contains at most a single point.

The point quadtree is an adaptation of a binary tree used to represent two dimensional point data. It shares the features of all quadtrees but is a true tree as the center of a subdivision is always on a point. The tree shape depends on the order data is processed. It is often very efficient in comparing two dimensional ordered data points, usually operating in O(log n) time.

Node structure for a point quadtree

A node of a point quadtree is similar to a node of a binary tree, with the major difference being that it has four pointers (one for each quadrant) instead of two ("left" and "right") as in an ordinary binary tree. Also a key is usually decomposed into two parts, referring to x and y coordinates. Therefore a node contains following information:

• point; which in turn contains:
• key; usually expressed as x, y coordinates
• value; for example a name

Edge quadtree are specifically used to store lines rather than points. Curves are approximated by subdividing cells to a very fine resolution. This can result in extremely unbalanced trees which may defeat the purpose of indexing.

• Image representation

• Spatial indexing
• Efficient collision detection in two dimensions
• View frustum culling of terrain data
• Storing sparse data, such as a formatting information for a spreadsheet orfor some matrix calculations
• Solution of multidimensional fields (computational fluid dynamics, electromagnetism)
• Conway's Game of Life simulation program.Quadtrees are the two-dimensional analog of octrees.

Caveats

If geometric subdividing fails to reduce the item count for each quadrant, (e.g., for overlapping data,) QuadTree subpartitioning fails, and the capacity must be breached for the algorithm to continue. For example, if the maximum capacity for a quadrant is 8, and there are 9 points at (0, 0), subpartitioning would produce three empty quadrants, and one containing the original 9 points, and so on. Because the tree must allow more than 8 points in such a quadrant, QuadTrees can approach O(N) complexity for data sets with arbitrary geometry (e.g., maps or graphs).

Octree

An octree is a tree data structure in which each internal node has up to eight children. Octrees are most often used to partition a three dimensional space by recursively subdividing it into eight octants. Octrees are the three dimensional analog of quadtrees.

The name is formed from oct + tree, and normally written "octree", not "octtree".

Left: Recursive subdivision of a cube into octants. Right: The corresponding octree.

Each node in an octree subdivides the space it represents into eight octants. In a point region (PR) octree, the node stores an explicit 3-dimensional point, which is the "center" of the subdivision for that node; the point defines one of the corners for each of the eight children. In an MX octree, the subdivision point is implicitly the center of the space the node represents. The root node of a PR octree can represent infinite space; the root node of an MX octree must represent a finite bounded space so that the implicit centers are well-defined. Octrees are never considered kD-trees, as kD-trees split along a dimension and octrees split around a point. kD-trees are also always binary, which is not true of octrees.

• Spatial indexing
• Efficient collision detection in three dimensions
• View frustum culling
• Fast Multipole Method
• Unstructured grid
• Finite element analysis

Application to color quantization

The octree color quantization algorithm, invented by Gervautz and Purgathofer in 1988, encodes image color data as an octree up to nine levels deep. Octrees are used because FIGURE and there are three color components in the RGB system. The node index to branch out from at the top level is determined by a formula that uses the most significant bits of the red, green, and blue color components, e.g. 4r + 2g + b. The next lower level uses the next bit significance, and so on.

Less significant bits are sometimes ignored to reduce the tree size. The algorithm is highly memory efficient because the tree's size can be limited. The bottom level of the octree consists of leaf nodes that accrue color data not represented in the tree; these nodes initially contain single bits. If much more than the desired number of palette colors are entered into the octree, its size can be continually reduced by seeking out a bottom-level node and averaging its bit data up into a leaf node, pruning part of the tree. Once sampling is complete, exploring all routes in the tree down to the leaf nodes, taking note of the bits along the way, will yield approximately the required number of colors.

Linear octrees

An octree is said to be complete if every internal node has exactly 8 child nodes. If the maximum permissible depth of an octree is fixed a priori, then it is sufficient to store the complete list of leaf nodes of the octree. Such a representation is referred to a Linear octree, since a linear array is sufficient for this representation instead of the tree data structure. All the nodes of the octree can be generated from the list of its leaf nodes. Space filling curves are often used to represent linear octrees.

Z- order

Z-order, Morton-order or Morton code

first proposed in 1966 by G. M. Morton, is a space -filling curve which is often used in computer science: Due to its good locality -preserving behaviour it is used in data structures for mapping multidimensional data to one dimension. The z-value of a point in multidimensions is simply calculated by interleaving the binary representations of its coordinate values. Once the data are sorted into this ordering, any one -dimensional data structure can be used such as binary search trees, B-trees, skip lists or (with low significant bits truncated) hash tables. The resulting ordering can equivalently be described as the order one would get from a depth-first traversal of a quadtree; because of its close connection with quadtrees, the Z-ordering can be used to efficiently construct quadtrees and related higher dimensional data structures.

Four iterations of the Z-order curve.

Coordinate values

The figure below shows the Z-values for the two dimensional case with integer coordinates 0 ≤ x ≤ 7, 0 ≤ y ≤ 7 (shown both in decimal and binary). Interleaving the binary coordinate values yields binary z-values as shown. Connecting the z-values in their numerical order produces the recursively Z-shaped curve.

Z-order curve iterations extended to three dimensions.

Use with one-dimensional data structures for range searching

Although well locality preserving, for efficient range searches an algorithm is necessary for calculating, from a point encountered in the data structure, the next Z-value which is in the multidimensional search range:

In this example, the range being queried (x=2..3, y=2..6) is indicated by the dotted rectangle. Its highest Z-value (MAX) is 45. In this example, the value F=19 is encountered when searching a data structure in increasing Z-value direction, so we would have to search in the interval between F and MAX (hatched area). To speed up the search, one would calculate the next Z-value which is in the search range, called BIGMIN (36 in the example) and only search in the interval between BIGMIN and MAX (bold values), thus skipping most of the hatched area. Searching in decreasing direction is analogous with LITMAX which is the highest Z-value in the query range lower than F. The BIGMIN problem has first been stated and its solution shown in Tropf and Herzog.

This solution is also used in UB-trees ("GetNextZ-address"). As the approach does not depend on the one dimensional data structure chosen, there is still free choice of structuring the data, so well known methods such as balanced trees can be used to cope with dynamic data (in contrast for example to R-trees where special considerations are necessary). Similarly, this independence makes it easier to incorporate the method into existing databases. Applying the method hierarchically (according to the data structure at hand), optionally in both increasing and decreasing direction, yields highly efficient multidimensional range search which is important in both commercial and technical applications, e.g. as a procedure underlying nearest neighbour searches.

Z-order is one of the few multidimensional access methods that has found its way into commercial database systems (Oracle database 1995 , Transbase 2000 ). As long ago as 1966, G.M.Morton proposed Z-order for file sequencing of a static two dimensional geographical database. Areal data units are contained in one or a few quadratic frames represented by their sizes and lower right corner Z-values, the sizes complying with the Z-order hierarchy at the corner position. With high probability, changing to an adjacent frame is done with one or a few relatively small scanning steps.

Related structures

As an alternative, the Hilbert curve has been suggested as it has a better order -preserving behaviour, but here the calculations are much more complicated, leading to significant processor overhead. BIGMIN source code for both Z-curve and Hilbert -curve were described in a patent by H. Tropf. For a recent overview on multidimensional data processing, including.

Applications in linear algebra

The Strassen algorithm for matrix multiplication is based on splitting the matrices in four blocks, and then recursively each of these blocks in four smaller blocks, until the blocks are single elements (or more practically: unti reaching matrices so small that the trivial algorithm is faster). Arranging the matrix elements in Z-order then improves locality, and has the additional advantage (compared to row- or column-major ordering) that the subroutine for multiplying two blocks does not need to know the total size of the matrix, but only the size of the blocks and their location in memory.

UB- tree

The UB-tree as proposed by Rudolf Bayer and Volker Markl is a balanced tree for storing and efficiently retrieving multidimensional data. It is basically a B+ tree (information only in the leaves) with records stored according to Z-order, also called Morton order. Z-order is simply calculated by bitwise interlacing the keys. Insertion, deletion, and point query are done as with ordinary B+ trees.

To perform range searches in multidimensional point data, however, an algorithm must be provided for calculating, from a point encountered in the data base, the next Z-value which is in the multidimensional search range. The original algorithm to solve this key problem was exponential with the dimensionality and thus not feasible[1] ("GetNextZ-address"). A solution to this "crucial part of the UB-tree range query" linear with the z-address bit length has been described later. This method has already been described in an older paper where using Z-order with search trees has first been proposed.

R- tree

R-trees are tree data structures that are similar to B-trees, but are used for spatial access methods, i.e., for indexing multi-dimensional information; for example, the (X, Y) coordinates of geographical data. A common real-world usage for an R-tree might be: "Find all museums within 2 kilometres (1.2 mi) of my current location".

Simple example of an R-tree for 2D rectangles

The data structure splits space with hierarchically nested, and possibly overlapping, minimum bounding rectangles (MBRs, otherwise known as bounding boxes, i.e. "rectangle", what the "R" in R-tree stands for). Each node of an R-tree has a variable number of entries (up to some pre-defined maximum). Each entry within a non-leaf node stores two pieces of data: a way of identifying a child node, and the bounding box of all entries within this child node. The insertion and deletion algorithms use the bounding boxes from the nodes to ensure that "nearby" elements are placed in the same leaf node (in particular, a new element will go into the leaf node that requires the least enlargement in its bounding box).

Each entry within a leaf node stores two pieces of information; a way of identifying the actual data element (which, alternatively, may be placed directly in the node), and the bounding box of the data element. Similarly, the searching algorithms (e.g., intersection, containment, nearest) use the bounding boxes to decide whether or not to search inside a child node. In this way, most of the nodes in the tree are never "touched" during a search. Like B-trees, this makes R-trees suitable for databases, where nodes can be paged to memory when needed. Different algorithms can be used to split nodes when they become too full, resulting in the quadratic and linear R-tree sub-types.

R-trees do not historically guarantee good worst-case performance, but generally perform well with real-world data. However, a new algorithm was published in 2004 that defines the Priority R-Tree, which claims to be as efficient as the currently most efficient methods and is at the same time worst-case optimal.

Variants

•  R* tree
•  R+ tree
• Hilbert R-tree
• Priority R-Tree (PR-Tree) - The PR-tree performs similarly to the best known R-tree variants on real-life and relatively evenly distributed data, but outperforms them significantly on more extreme data.

Algorithm

Search

The input is a search rectangle (Query box). Searching is quite similar to searching in a B+tree. The search starts from the root node of the tree. Every internal node contains a set of rectangles and pointers to the corresponding child node and every leaf node contains the rectangles of spatial objects (the pointer to some spatial object can be there). For every rectangle in a node, it has to be decided if it overlaps the search rectangle or not. If yes, the corresponding child node has to be searched also. Searching is done like this in a recursive manner until all overlapping nodes have been traversed.

When a leaf node is reached, the contained bounding boxes (rectangles) are tested against the search rectangle and their objects (if there are any) are put into the result set if they lie within the search rectangle.

Insertion

To insert an object, the tree is traversed recursively from the root node. All rectangles in the current internal node are examined. The constraint of least coverage is employed to insert an object, i.e., the box that needs least enlargement to enclose the new object is selected. In the case where there is more than one rectangle that meets this criterion, the one with the smallest area is chosen. Inserting continues recursively in the chosen node. Once a leaf node is reached, a straightforward insertion is made if the leaf node is not full. If the leaf node is full, it must be split before the insertion is made. A few splitting algorithms have been proposed for good R-tree performance.

• Sort-Tile-Recursive (STR)
• Packed Hilbert R-Tree - Uses the Hilbert value of the center of a rectangle to sort the leaf nodes and recursively builds the tree.
• Nearest-X - Rectangles are sorted on the x-coordinate and nodes are created.

R+ tree

In computer science, an R+ tree is a tree data structure, a variant of the R tree, used for indexing spatial information.

Difference between R+ trees and R trees

• R+ trees are a compromise between R-trees; and kd-trees; they avoid overlapping of internal nodes by inserting an object into multiple leaves if necessary. R+ trees differ from R trees in that:
• Nodes are not guaranteed to be at least half filled
• The entries of any internal node do not overlap
• An object ID may be stored in more than one leaf node

• Because nodes are not overlapped with each other, point query performance benefits since all spatial regions are covered by at most one node.
• A single path is followed and fewer nodes are visited than with the R-tree

• Since rectangles are duplicated, an R+ tree can be larger than an R tree built on same data set.
• Construction and maintenance of R+ trees is more complex than the construction and maintenance of R trees and other variants of the R tree.

R* tree

R*-trees are a variant of R-trees used for indexing spatial information. R*-trees support point and spatial data at the same time with a slightly higher cost than other R-trees. It was proposed by Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, and Bernhard Seeger in 1990.

Difference between R*-trees and R-trees

Minimization of both coverage and overlap is crucial to the performance of R-trees. The R*-tree attempts to reduce both, using a combination of a revised node split algorithm and the concept of forced reinsertion at node overflow.

This is based on the observation that R-tree structures are highly susceptible to the order in which their entries are inserted, so an insertion -built (rather than bulk-loaded) structure is likely to be sub -optimal. Deletion and reinsertion of entries allows them to "find" a place in the tree that may be more appropriate than their original location. When a node overflows, a portion of its entries are removed from the node and reinserted into the tree. (In order to avoid an indefinite cascade of reinsertions caused by subsequent node overflow, the reinsertion routine may be called only once in each level of the tree when inserting any one new entry.) This has the effect of producing more well-clustered groups of entries in nodes, reducing node coverage. Furthermore, actual node splits are often postponed, causing average node occupancy to rise.

Performance

• Likely significant improvement over other R tree variants, but there is overhead due to the reinsertion method.
• Efficiently supports point and spatial data at the same time

Algorithm

The R*-tree uses the same algorithm as the R-tree for query and delete operations. The primary difference is the insert algorithm, specifically how it chooses which branch to insert the new node into and the methodology for splitting a node that is full.

Hilbert R- tree

Hilbert R-tree, an R-tree variant, is an index for multidimensional objects like lines, regions, 3-D objects, or high dimensional feature-based parametric objects. It can be thought of as an extension to B+-tree for multidimensional objects. The performance of R-trees depends on the quality of the algorithm that clusters the data rectangles on a node. Hilbert R-trees use space-filling curves, and specifically the Hilbert curve, to impose a linear ordering on the data rectangles.

There are two types of Hilbert R-tree, one for static database and one for dynamic databases. In both cases, space filling curves and specifically the Hilbert curve are used to achieve better ordering of multidimensional objects in the node. This ordering has to be ‘good’, in the sense that it should group ‘similar’ data rectangles together, to minimize the area and perimeter of the resulting minimum bounding rectangles (MBRs). Packed Hilbert R-trees are suitablefor static databases in which updates are very rare or in which there are no updates at all.

The dynamic Hilbert R-tree is suitable for dynamic databases where insertions, deletions, or updates may occur in real time. Moreover, dynamic Hilbert R-trees employ flexible deferred splitting mechanism to increase the space utilization. Every node has a well defined set of sibling nodes. By adjusting the split policy the Hilbert R-tree can achieve a degree of space utilization as high as is desired. This is done by proposing an ordering on the R-tree nodes. The Hilbert R-tree sorts rectangles according to the Hilbert value of the center of the rectangles (i.e., MBR). (The Hilbert value of a point is the length of the Hilbert curve from the origin to the point.) Given the ordering, every node has a well-defined set of sibling nodes; thus, deferred splitting can be used. By adjusting the split policy, the Hilbert R-tree can achieve as high utilization as desired. To the contrary, other R-tree variants have no control over the space utilization.

The basic idea

Although the following example is for a static environment, it explains the intuitive principles for good R-tree design. These principles are valid for both static and dynamic databases. Roussopoulos and Leifker proposed a method for building a packed R-tree that achieves almost 100% space utilization. The idea is to sort the data on the x or y coordinate of one of the corners of the rectangles. Sorting on any of the four coordinates gives similar results. In this discussion points or rectangles are sorted on the x coordinate of the lower left corner of the rectangle. In the discussion below the Roussopoulos and Leifker’s method is referred to as the lowx packed R-tree.

The sorted list of rectangles is scanned; successive rectangles are assigned to the same R-tree leaf node until that node is full; a new leaf node is then created and the scanning of the sorted list continues. Thus, the nodes of the resulting R-tree will be fully packed, with the possible exception of the last node at each level. Thus, the utilization is ≈100%. Higher levels of the tree are created in a similar way. Figure highlights the problem of the lowx packed R-tree. Figure [Right] shows the leaf nodes of the R-tree that the lowx packing method will create for the points of Figure 1 [Left].

The fact that the resulting father nodes cover little area explains why the lowx packed R-tree achieves excellent performance for point queries. However, the fact that the fathers have large perimeters, explains the degradation of performance for region queries. This is consistent with the analytical formulas for R-tree performance . Intuitively, the packing algorithm should ideally assign nearby points to the same leaf node. Ignorance of the y coordinate by the lowx packed R-tree tends to violate this empirical rule.

[Left] 200 points uniformly distributed; [Right] MBR of nodes generated by the lowx packed R-treealgorithm

This section describes two variants of the Hilbert R-trees. The first index is suitable for the static database in which updates are very rare or in which there are no updates at all. The nodes of the resulting R-tree will be fully packed, with the possible exception of the last node at each level. Thus, the space utilization is ≈100%; this structure is called a packed Hilbert R-tree. The second index, called a Dynamic Hilbert R-tree, supports insertions and deletions, and is suitable for a dynamic environment.

Packed Hilbert R-trees

The following provides a brief introduction to the Hilbert curve. The basic Hilbert curve on a 2x2 grid, denoted by H1 is shown in Figure. To derive a curve of order i, each vertex of the basic curve is replaced by the curve of order i – 1, which may be appropriately rotated and/or reflected. Figure also shows the Hilbert curves of order two and three. When the order of the curve tends to infinity, like other space filling curves, the resulting curve is a fractal, with a fractal dimension of two. The Hilbert curve can be generalized for higher dimensionalities. Algorithms for drawing the two -dimensional curve of a given order can be found.

An algorithm for higher dimensionalities is given in . The path of a space filling curve imposes a linear ordering on the grid points; this path may be calculated by starting at one end of the curve and following the path to the other end. The actual coordinate values of each point can be calculated. However, for the Hilbert curve this is much harder than for example the Z-order curve. Figure shows one such ordering for a 4x4 grid (see curve H2). For example, the point (0,0) on the H2 curve has a Hilbert value of 0, while the point (1,1) has a Hilbert value of 2.

Hilbert curves of order 1, 2, and 3

The Hilbert curve imposes a linear ordering on the data rectangles and then traverses the sorted list, assigning each set of C rectangles to a node in the R-tree. The final result is that the set of data rectangles on the same node will be close to each other in the linear ordering, and most likely in the native space; thus, the resulting R-tree nodes will have smaller areas. Figure 2 illustrates the intuitive reasons why our Hilbert-based methods will result in good performance. The data is composed of points (the same points as given in Figure). By grouping the points according to their Hilbert values, the MBRs of the resulting R-tree nodes tend to be small square-like rectangles. This indicates that the nodes will likely have small area and small perimeters. Small area values result in good performance for point queries; small area and small perimeter values lead to good performance for larger queries.

Algorithm Hilbert-Pack

(packs rectangles into an R-tree)

Step 1. Calculate the Hilbert value for each data rectangle
Step 2. Sort data rectangles on ascending Hilbert values
Step 3. /* Create leaf nodes (level l-0) */
• While (there are more rectangles)
• generate a new R-tree node
• assign the next C rectangles to this node
Step 4. /* Create nodes at higher level (l + 1) */
• While (there are > 1 nodes at level l)
• sort nodes at level l ≥ 0 on ascending
• creation time
• repeat Step 3

The assumption here is that the data are static or the frequency of modification is low. This is a simple heuristic for constructing an R-tree with 100% space utilization which at the same time will have as good response time as possible.

Dynamic Hilbert R-trees

The performance of R-trees depends on the quality of the algorithm that clusters the data rectangles on a node. Hilbert R-trees use space -filling curves, and specifically the Hilbert curve, to impose a linear ordering on the data rectangles. The Hilbert value of a rectangle is defined as the Hilbert value of its center.

Tree structure

The Hilbert R-tree has the following structure. A leaf node contains at most Cl entries each of the form (R, obj _id) where Cl is the capacity of the leaf, R is the MBR of the real object (xlow, xhigh, ylow, yhigh) and obj-id is a pointer to the object description record. The main difference between the Hilbert R-tree and the R*-tree is that non-leaf nodes also contain information about the LHVs (Largest Hilbert Value). Thus, a non-leaf node in the Hilbert R-tree contains at most Cn entries of the form (R, ptr, LHV) where Cn is the capacity of a non-leaf node, R is the MBR that encloses all the children of that node, ptr is a pointer to the child node, and LHV is the largest Hilbert value among the data rectangles enclosed by R. Notice that since the non-leaf node picks one of the Hilbert values of the children to be the value of its own LHV, there is not extra cost for calculating the Hilbert values of the MBR of non-leaf nodes.

Figure illustrates some rectangles organized in a Hilbert R-tree. The Hilbert values of the centers are the numbers near the ‘x’ symbols (shown only for the parent node ‘II’). The LHV’s are in [brackets]. Figure 4 shows how the tree of Figure is stored on the disk; the contents of the parent node ‘II’ are shown in more detail. Every data rectangle in node ‘I’ has a Hilbert value v ≤33; similarly every rectangle in node ‘II’ has a Hilbert value greater than 33 and ≤ 107, etc.

Data rectangles organized in a Hilbert R-tree (Hilbert values and LHV’s are in Brackets)

A plain R-tree splits a node on overflow, creating two nodes from the original one. This policy is called a 1-to-2 splitting policy. It is possible also to defer the split, waiting until two nodes split into three. Note that this is similar to the B*-tree split policy. This method is referred to as the 2-to-3 splitting policy. In general, this can be extended to s-to-(s+1) splitting policy; where s is the order of the splitting policy. To implement the order-s splitting policy, the overflowing node tries to push some of its entries to one of its s - 1 siblings; if all of them are full, then s-to-(s+1) split need to be done. The s -1 siblings are called the cooperating siblings. Next, the algorithms for searching, insertion, and overflow handling are described in details.

Searching

The searching algorithm is similar to the one used in other R-tree variants. Starting from the root, it descends the tree and examines all nodes that intersect the query rectangle. At the leaf level, it reports all entries that intersect the query window w as qualified data items.

Algorithm Search(node Root, rect w):

S1. Search nonleaf nodes:

Invoke Search for every entry whose MBR intersects the query window w. S2. Search leaf nodes: Report all entries that intersect the query window w as candidates.

The file structure for the Hilbert R-tree

Insertion

To insert a new rectangle r in the Hilbert R-tree, the Hilbert value h of the center of the new rectangle is used as a key. At each level the node with the minimum LHV of all its siblings is chosen. When a leaf node is reached, the rectangle r is inserted in its correct order according to h. After a new rectangle is inserted in a leaf node N,

AdjustTree is called to fix the MBR and LHV values in the upper-level nodes.

Algorithm Insert(node Root, rect r): /* Inserts a new rectangle r in the Hilbert R-tree. h is the Hilbert value of the rectangle*/

I1. Find the appropriate leaf node: Invoke ChooseLeaf(r, h) to select a leaf node L in which to place r.

I2. Insert r in a leaf node L: If L has an empty slot, insert r in L in th appropriate place according to the Hilbert order and return. If L is full, invoke HandleOverflow(L,r), which will return new leaf if split was inevitable,

I3. Propagate changes upward: Form a set S that contains L, its cooperating siblings and the new leaf (if any) Invoke AdjustTree(S).

I4. Grow tree taller:

If node split propagation caused the root to split, create a new root whose children are the two resulting nodes.

Algorithm ChooseLeaf(rect r, int h):

/* Returns the leaf node in which to place a new rectangle r. */

C1. Initialize: Set N to be the root node.
C2. Leaf check: If N is a leaf_ return N.
C3. Choose subtree: If N is a non-leaf node, choose the entry (R, ptr, LHV)
with the minimum LHV value greater than h.

C4. Descend until a leaf is reached: Set N to the node pointed by ptr and repeat from C2.

/* S is a set of nodes that contains the node being updated, its cooperating siblings (if overflow has occurred) and the newly created node NN (if split has occurred). The routine ascends from the leaf level towards the root, adjusting MBR and LHV of nodes that cover the nodes in S. It propagates splits (if any) */ A1. If root level is reached, stop.

A2. Propagate node split upward:
Let Np be the parent node of N.
If N has been split, let NN be the new node.
Insert NN in Np in the correct order according to its Hilbert
value if there is room. Otherwise, invoke HandleOverflow(Np , NN ).
If Np is split, let PP be the new node.
A3. Adjust the MBR’s and LHV’s in the parent level:
Let P be the set of parent nodes for the nodes in S.
Adjust the corresponding MBR’s and LHV’s of the nodes in P appropriately.
A4. Move up to next level:
Let S become the set of parent nodes P, with
NN = PP, if Np was split.
repeat from A1.

Deletion

In the Hilbert rflows. Instead, keys can be borrowed from the siblings or the underflowing node is merged with its siblings. This is possible because the nodes have a clear ordering (according to Largest Hilbert Value, LHV); in contrast, in R-trees there is no such concept concerning sibling nodes. Notice that deletion operations require s cooperating siblings, while insertion operations require s - 1 siblings.

Algorithm Delete(r):

D1. Find the host leaf:
Perform an exact match search to find the leaf node L
that contains r.
D2. Delete r :
Remove r from node L.
D3. If L underflows
borrow some entries from s cooperating siblings.
if all the siblings are ready to underflow.
merge s + 1 to s nodes,
D4. Adjust MBR and LHV in parent levels.
form a set S that contains L and its cooperating
siblings (if underflow has occurred).

Overflow handling

The overflow handling algorithm in the Hilbert R-tree treats the overflowing nodes either by moving some of the entries to one of the s - 1 cooperating siblings or by splitting s nodes into s +1 nodes.

Algorithm HandleOverflow(node N, rect r):

/* return the new node if a split occurred. */

H1. Let ε be a set that contains all the entries from N
and its s - 1 cooperating siblings.

H3. If at least one of the s - 1 cooperating siblings is not full, distribute ε evenly among the s nodes according to Hilbert values.

H4. If all the s cooperating siblings are full, create a new node NN and distribute ε evenly among the s + 1 nodes according to Hilbert values return NN.

X- tree

In computer science, an X-tree is an index tree structure based on the R-tree used for storing data in many dimensions. It differs from R-trees, R+-trees and R*-trees because it emphasizes prevention of overlap in the bounding boxes. In cases where nodes cannot be split without preventing overlap, the node split will be deferred, resulting in super-nodes. In extreme cases, the tree will linearize, which defends against worst-case behaviors observed in some other data structures.

Metric tree

A metric tree is any tree data structure specialized to index data in metric spaces. Metric trees exploit properties of metric spaces such as the triangle inequality to make accesses to the data more efficient. Examples include vp-trees, cover trees, m-trees and bk trees.

VP- tree

A vantage point tree, or vp-tree is a BSP tree that segregates data in a metric space by choosing a position in the space (the "vantage point") and dividing the data points into two partitions: those that are nearer to the vantage point than a threshold, and those that are not. By repeatedly applying this procedure to partition the data into smaller and smaller sets, a tree data structure is created where neighbors in the tree are likely to be neighbors in the space. This iterative partitioning process is similar to that of a kd-tree, but uses circular (or spherical, hyperspherical, etc) rather than rectilinear partitions. In 2D Euclidean space, this can be visualized as a series of circles segregating the data. The vp-tree is particularly useful in dividing data in a non-standard metric space into a BSP tree.

BK- tree

A BK-tree is a metric tree suggested by Burkhard and Keller BK73 specifically adapted to discrete metric spaces. For simplicity, let us consider integer discrete metric p(x,y). Then, BK-tree is defined in the following way. An arbitrary element a is selected as root node. Root node may have zero or more subtrees. The k-th subtree is recursively built of all elements b such that p(a,b)=k, BK-trees can be used for approximate string matching in a dictionary BN98.

Top