[MUD-Dev] Re Hilbert Curves
Cynbe ru Taren
cynbe at muq.org
Thu Nov 4 16:44:54 New Zealand Daylight Time 1999
"Christopher Allen" <ChristopherA at Skotos.net> wrote:
| There is an excellent article in July 1999 issue of Dr. Dobbs 'Space-Filling
| Curves in Geospatial Applications' by Ron Gutman on page 115, with the summary
| "B-Tree databases are very efficient with one-dimensional data. Ron shows how
| Hilbert curves can be used to efficiently manage multidimensional data, with no
| changes to the underlying database".
(1) Many thanks to Christopher for this post! I've a collection of photocopied
papers on R* trees, but was unfamiliar with Morton and Peano curves in this
context. Posts like this keep me on this mailing list. :)
(2) Feeding "morton and peano and order" in to Alta Vista advanced
search turns up a few more references which might be of interest
to this audience in this context:
Covers the general idea in tutorial fashion with diagrams and references.
A similar tutorial, less detailed.
Short overview of Morton, Hilbert and other orders in the context
of splitting R-tree nodes.
Includes a detailed third-party (GIS) review of what the big DB vendors are
doing on the spatial indexing front. In particular, Oracle 7.3
uses Peano ordering to do spatial indexing on top of standard B-trees.
Overall conclusion: Current efforts are very crude, but promising.
Some snippets of common wisdom I found interesting:
* R-trees have been the academic favorite for over a decade.
* Peano style indexing seems an established favorite of the GIS
(Geographic Information System) crowd, who have to produce
practical results from huge masses of data. (I tend to bet
on practical experience over academic fashion when push comes
to shove, myself...)
* R-trees don't handle points efficiently, and become rapidly less
effective as one goes above two dimensions.
* Peano-style queries drop rapidly in efficiency as the tiling fit
used gets better (i.e., more complex): Simpler is better.
* As with quadtees, subdividing to provide more accuracy has the
effect of appending bits to the code: The prefix remains invariant.
MUD-Dev maillist - MUD-Dev at kanga.nu
More information about the MUD-Dev