Re: Two-dimensional pattern matching/compression

On Wednesday 12 July 2006 17:55, Herbert Glarner wrote:
I must confess that I am absolutely
unfamiliar with the "Spatial Access Methods". So... back to study :)

Very quick motivation. How would one extend, say, binary search trees
to a 2D search? Search in X, then search in Y (each "leaf" in the X
dimension is a BST in Y)? Interleave X and Y levels (split on X, then
on Y, then on X, etc.)? If so, should the split of "cousins" (child
of parent's sibling) be the same or be allowed to be different? Now
what if you're searching for a *region* (e.g., which pizza place is
closest to zip code 20500)? All these and far more are ways to search
in more than one dimension.

A good survey is
Volker Gaede and Oliver Günther, Multidimensional Access Methods,
ACM Computing Surveys, 30(2):170-231, June 1998.

-paul-
--
Paul E. Black (p.black@xxxxxxx)
.