Spatial indexing

Objectives of lecture

1. use of data structures to provide spatial access
2. prepare to understand WHIRLPOOL lecture (next)
   1. show code for Heap
   2. and Hash

Basic search structures:

Trees

• Binary trees can do one axis
• k-d trees (k-dimensions)
• Persistent trees

Issues: balancing, maintenance, degenerate behavior

Search versus insert versus delete...

Binary sorted Heaps

allow access to "top" item and a compact linear list; insert at end, bubble up; pop top, bubble down

Hash tables

Linear key, direct access with "collision"

Quad trees

Divide on X and Y; rules obvious for points, less obvious for lines and areas

(To divide or not divide...)

Morton sequence

The commerically important options:

XCELL : a Half-way Quadtree

Divide on X, then (if needed) on Y; object stored at node where they are undivided (hence all that cross the first divde are at the root...)

Used by ESRI in Arc 7, Vector Product Format (public domain for military)

Range trees

all objects have bounding rectangle; group objects into units, assign the composite bounding rectangle; search down a hierarchy of bounding rectangles...

Rectangles may overlap, requiring multiple boxes to be examined

Balancing can be tricky (time consuming)

Used by Intergraph (TIGRIS at least), other less important vendors

SDE Index?

SDE uses some kind of hash function... proprietary

Tradeoffs and choices

compute versus store - as always

approximate index [buckets] (give some candidates, compute the solution locally)

actually giving the solution (constructive index)

Thought experiment: nearest point

• the DO loop approach;

• set smallest to LARGE;
• For all points, compute distance, compare to smallest, update smallest

• Quadtrees or range trees

• find box that contains point, calculate only locally

• Voronoi (constructive) index

• Look up polygon that contains the point, that is the answer.

Index from here: Next Lecture | Schedule

Version of 19 February 2003