[MUD-Dev] Re Hilbert Curves

[Cynbe ru Taren]

"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:

    http://www.csc.liv.ac.uk/~frans/dGKBIS/tesseral.html
    Covers the general idea in tutorial fashion with diagrams and references.

    http://www.gisca.adelaide.edu.au/kea/gisrs/gisrsrc/courses/gis/ncgia/u35.html#SEC35.4
    A similar tutorial, less detailed.

    http://www.cs.umd.edu/~brabec/quadtree/docs/rtree_split_rules.html
    Short overview of Morton, Hilbert and other orders in the context
    of splitting R-tree nodes.

    http://www.alexandria.ucsb.edu/public-documents/annual_report98/node37.html
    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.

 -- Cynbe




_______________________________________________
MUD-Dev maillist  -  MUD-Dev at kanga.nu
http://www.kanga.nu/lists/listinfo/mud-dev