• 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

Other Optimisations

• reduce I/O by reducing size of vectors   (compression)

• reduce I/O by placing "similar" records together   (clustering)

• reduce I/O by remembering previous pages   (caching)

• reduce cpu by making D computation faster   (ColorHist)