Multi-Dimensional Range Search Tree

What It Does

A multi-dimensional range search tree (also known as a range tree) is a data structure for efficiently locating points contained within a specified multi-dimensional region (box).

A sample query: Given a set of points in 3D, find all points such that:

10 <= point.X <= 15
35 <= point.Y <= 67
24 <= point.Z <= 32

The above three constraints define a multi-dimensional range (or box). Once built, this search tree is able to answer any such query efficiently.

What It Looks Like

An example 2D range search tree data structure.

A multi-dimensional range search tree data structure is actually a collection of many trees. In the implementaion provided on this page, items are only present in the leaf nodes. Intermediate nodes are simply used for guiding a search. For searching within the first dimension, there is a single search tree. Each internal node of the first dimension search tree points to a tree for searching within the second dimension as in the example above.

This pattern of trees pointing to other trees can continue for more than two dimensions. For example, if the items were three dimensional, each internal node of each second dimension search tree would point to a third dimension search tree.

This may seem like it takes a lot of space, but it has been proven that the total amount of space of this data structure is O(n·logd-1(n)) where n is the number of nodes and d is the number of dimensions.

Complexity Gaurantees

Let n be the number of points, d be the number of dimensions, and t be the number of points that match the search criteria (are in the multi-dimensional range). Then the complexities are:

  • Build Time: O(n·logd-1(n))
  • Space: O(n·logd-1(n))
  • Query Time: O(logd(n) + t)

2D Demo

The following is a 2D demo that uses the C# source code provided on this page. You must have Microsoft Silverlight 2 or a later version installed to view it.

Source Code

Download

  • C# Source Code for an arbitrary number of dimensions. This implementation does not allow inserting or removing elements; the tree is built once and for all.

Sample Usage

The following code sample, creates a list of several points and uses the multi-dimensionalge range search tree data structure to get all points for which 2 <= x <= 5 and 3 <= y <= 5.

// Create a list of points. List<Point> points = new List<Point>() { new Point(3, 6), new Point(2, 5), new Point(5, 2), new Point(2, 1), new Point(3, 4), new Point(4, 4), new Point(2, 6), new Point(2, 2) }; // Create a new range search tree for the points, specifying that it should have 2 dimension. RangeSearchTree<Point> tree = new RangeSearchTree<Point>(2, points); // Get all of the points in the range determined by the two corner points (2, 3) and (5, 5). List<Point> pointsInRange = tree.GetAllInRange(new Point(2, 3), new Point(5, 5));

Related Work

© 2014 Emil Stefanov
About this Website