Re: Multidimensional query involving ranges

Together with Rudolf Bayer, the inventor of the B-Tree, I have been working on using space filling curves and B-Trees for Databases for more than 4 years by now. We invented the UB-Tree, a multidimensional index using B-Trees and the Z-curve and investigated it in a research project (http://mistral.in.tum.de), you can see the algorithms, performance results and further details under http://mistral.in.tum.de/results/presentations/ppt/index.html as well as
http://mistral.in.tum.de/results/publications/

This work resulted in enhancing a commercial DBMS (TransBase), www.transaction.de, with a so-called HyperCube option, i.e., the UB-Tree.
TransBase Hypercube was awarded the IST 2001 prize for its innovative new indexing technologie.

If you are interested in further details, please do not hesitate to contact
us at mistral_at_in.tum.de

Martin Drautzburg <drautzburg_at_altavista.net> wrote in message news:<87r8wwnrur.fsf_at_altavista.net>...
> I heared of a method that uses a "Z"-curve. If you have two integer
> columns then you create an index on the value that you get when you
> interwaeve the values of the two columns bitwise. If you increase this
> value then you traverse the 2dimensional plane in shapes that look
> like the letter "Z".
>
> Lookup is done by using this index, but it requires more than a simple
> range scan. Basically the problem is, that even though the Z-curve has
> a tendency to cover rectangular areas, it still may leave the area of
> interest. At the end you need multiple range scans and to compute
> these ranges is not trivial.
>
> I don't think this is available in any commercial database. Maybe this
> method is logically equivalent to what Paul is talking about.
Received on Sun Jul 22 2001 - 01:31:41 CEST