User:Troyhildebr/sandbox

In computer science, a K-D-B tree (k-dimensional B-tree) is a tree data structure for subdividing a k-dimensional search space. The aim of the K-D-B tree is to provide the search efficiency of a balanced k-d tree, while providing the block-oriented storage of a B-tree.

Informal description

Much like the k-d tree, a K-D-B tree organizes points in k-dimensional space, useful for tasks such as range-searching and multi-dimensional database queries. K-D-B trees subdivide space into two subspaces by comparing elements in a single domain. Using a 2-D-B tree (2-dimensional K-D-B tree) as an example, space is subdivided in the same manner as a k-d tree: Using a point in just one of the domains, or axes in this case, all other values are either less than or greater than the current value, and fall to the left and right of the splitting plane respectively. For instance, if one chose the x-axis as the domain to split on, some point would have the x-coordinate x_i,

Like a B-tree, nodes in the K-D-B tree are stored as pages and the tree stores a pointer to the root page.

Structure

The K-D-B tree contains two types of pages:

• Region pages: A collection of (region, child) pairs containing a description of the bounding region along with a pointer to the child page corresponding to that region.
• Point pages: A collection of (point, location) pairs. In the case of databases, location may point to the index of the database record, while for points in k-dimensional space, it can be seen as the point's coordinates in that space.

Page overflows occur when inserting an element into the K-D-B tree results in the size of a node exceeding its optimal size. Since the purpose of the K-D-B tree is to optimize external memory accesses like those from a hard-disk, a page is considered to have overflowed or be overfilled if the size of the node exceeds the natural external memory page size.

Throughout insertion/deletion operations, the K-D-B maintains a certain set of properties:

• The graph is a multi-way tree. Region pages always point to child pages, and can not be empty. Point pages are the leaf nodes of the tree.
• Like a B-tree, the path length to the leaves of the tree is the same for all queries.
• The regions that make up a region page are disjoint.
• If the root is a region page the union of its regions is the entire search space.
• When the child of a (region, child) pair in a region page is also a region page, the union of all the regions in the child is region.
• Conversely in the case above, if child is a point page, all points in child must be contained in region. (TODO: Show image)

Operations on a K-D-B tree

Queries

Queries on a K-D-B tree are a range search over intervals in all domains or axes in the tree. This collection of intervals is called the query region. In k-space, the query region can be visualized as a bounding volume around some subspace in the entire k-dimensional search space. A query can fall into one of three categories:

• Some intervals span an entire domain or axis, making the query a partial range query.
• Some intervals are points, the others full domains, and so the query is a partial match query.
• The intervals are all points, and so the bounding volume is also just a point. This is an exact match query.

Algorithm

1. If the root of the tree is null, terminate, otherwise let page be root.
2. If page is a point page, return every point in a (point, location) pair that lies within the query region.
3. Otherwise, page is a region page, so for all (region, child) pairs where region and query region intersect, set page to be child and recurse from step 2.

Insertions

Since an insertion into a K-D-B tree may require the splitting of a page in the case of a page overflow, it is important to first define the splitting operation.

Splitting algorithm

First, a region page is split along some plane to create two new region pages, the left and right pages. These pages are filled with the regions from the old region page, and the old region page is deleted. Then, for every (region, child) in the original region page, remembering child is a page and region specifies an actual bounding region:

1. If region lies entirely to the left of the splitting plane, add (region, child) to the left page.
2. If region lies entirely to the right of the splitting plane, add (region, child) to the right page.
3. Otherwise:
   1. Recursively split child by the splitting plane, resulting in the pages new_left_page and new_right_page
   2. Split region by the splitting plane, resulting in left_region and right_region
   3. Add (left_region, new_left_page) to the left page, and (right_region, new_right_page) to the right page.

Insertion algorithm

Using the splitting algorithm, insertions of a new (point, location) pair can be implemented as follows:

1. If the root page is null, simply make the root page a new point page containing (point, location)
2. If an exact match query on point to find the page that point' should be added to. If it already exists in the page, terminate.
3. Add (point, location) to the page. If the page overflows, let page denote that page.
4. Let old_page be equal to page. Choose some element and a domain/axis to define a plane to split page by that results in two pages that will not also result in one of the pages being overfilled with the addition of a new point. Split page by the plane to make two new pages, new_left_page and new_right_page, and two new regions left_region and right_region.
5. If page was the root page, go to step 6. Otherwise, page becomes the parent of page. Replace (region, old_page) in page with (left_region, new_left_page) and (right_region, new_right_page). If page overflows, repeat step 4, otherwise terminate.
6. Let left_region be the entire search space to the left of the splitting plane, and right_region be the search space to the right, resulting from the split in Step 4. Set the root page to be a page containing to the regions left_region and right_region.

It is important to take care in the domain and element chosen to split page by, since it is desirable to try to balance the number of points on either side of the splitting plane. In some cases, a poor choice of splitting domain can result in undesirable splits. (TODO: Show image)

Deletions

Deletions from a K-D-B tree are incredibly simple if no minimum requirements are placed on storage utilization. Using an exact match query to find a (point, location) pair, we simply remove the record from the tree if it exists.

To guarantee some minimum storage usage, we may consider pages to be "underfull" if they