Orthogonal searching
www.sciencedirect.com
www.cs.wustl.edu
www.sable.mcgill.ca
Problem definition
• Lets consider a finite set of points P. The goal
is to find a structure enabling efficient search
for points in a given range.
• E.g., in 2D rectangle:
Solution
• k-D trees
• Range trees
wp.soulwasted.net
graphics.stanford.edu
k-D trees
• Usage – GIS, computer graphics, databases
• By dividing the space we create a binary tree.
Its inner nodes contain the dividing axis and
two pointers, leaves contain the data
• Disadvantages
– Sensitive to the order of points entering the
structure
k-D trees
• Initial requirement: any two points from P
don’t have the same x or y axis (this
requirement can be later removed)
• We build the tree by alternating the division
by x and y axis
k-D trees
• Line l1 intersects with p4, which lies in the
center of the set of points sorted according to
x axis
• This divides the space
to two half-planes,
in each of them we
divide according to y
axis using the same
criterion
k-D trees
• Lines l2, l3 intersect points lying in the middle
of “their” half-planes (according to y axis)
• We divide recursively until the half-planes
contain more points
or until we reach
a given number of
iteration (depth of
the tree)
k-D trees
k-D trees
Pseudocode
k-D trees
• Inserting to k-D tree:
public void insert(Vector <T> x)
{
root = insert( x, root, 0);
}
// this code is specific for 2-D trees
private KdNode<T> insert(Vector <T> x, KdNode<T> t, int level)
{
if (t == null)
t = new KdNode(x);
int compareResult = x.get(level).compareTo(t.data.get(level));
if (compareResult < 0)
t.left = insert(x, t.left, 1 - level);
else if( compareResult > 0)
t.right = insert(x, t.right, 1 - level);
else
; // do nothing if equal
return t;
}
k-D trees
• Inserting node (55, 62)
Region
k-D trees
• Searching for a given range:
/**
* Print items satisfying
* lowRange.get(0) <= x.get(0) <= highRange.get(0)
* and
* lowRange.get(1) <= x.get(1) <= highRange.get(1)
*/
public void printRange(Vector <T> lowRange,
Vector <T>highRange)
{
printRange(lowRange, highRange, root, 0);
}
private void
printRange(Vector <T> low,Vector <T> high,
KdNode<T> t, int level)
{
if (t != null)
{
if ((low.get(0).compareTo(t.data.get(0)) <= 0 &&
t.data.get(0).compareTo(high.get(0)) <=0)
&&(low.get(1).compareTo(t.data.get(1)) <= 0 &&
t.data.get(1).compareTo(high.get(1)) <= 0))
System.out.println("(" + t.data.get(0) + "," +
t.data.get(1) + ")");
if (low.get(level).compareTo(t.data.get(level)) <= 0)
printRange(low, high, t.left, 1 - level);
if (high.get(level).compareTo(t.data.get(level)) >= 0)
printRange(low, high, t.right, 1 - level);
}
}
Range search
k-D trees
• Complexity:
– Building k-D tree
• O(n log n)
• Memory complexity O(n)
– Search
• O(n1-1/d + k), where d is dimension, k is the number of
nodes in a given query range [x,x’] x [y, y’]
k-D trees
• Removing node from k-D tree
– Efficient solution doesn’t exist, a node is marked
as deleted
• Balancing k-D tree
– Any known strategy ensuring the balance of 2-D
tree
– Can be reached by repeated balancing the tree
Assignment
• Implement k-D tree to the basic framework
and visualize the dividing lines
Implementation
• KdNode:
– int k = 2; // dimensionality
– int depth = 0; // current depth
– Point id = null; // point representation
– KdNode parent = null; // pointer to parent node
– KdNode lesser = null; // pointer to left child
– KdNode greater = null; // pointer to right child
Implementation
• Point
– double x;
– double y;
• Store the results, e.g., to:
– TreeSet<KdNode> results;
• The comparator of points should be
implemented using the Euclidean distance