• use auxiliary (spatial) data structure to identify candidates

• space-partitioning methods: Grid file, k-d-b-tree, quadtree

• data-partitioning methods: R-tree, X-tree, SS-tree, TV-tree, ...

Approximation-based

• use approximating data structure to identify candidates

• signature files: VA-files

• projections: space-filling curves

A new approach, the pyramid technique [Berchtold et al.,] has elements of both partitioning and projection.