MEHRDIMENSIONALE BEREICHSSUCHE

Mehrdimensionale Daten werden durch Bitverschränkung auf eine Dimension abgebildet und in Suchbäumen eindimensional geordnet abgespeichert. Durch die Bitverschränkung ergibt sich eine raumfüllende Kurve, die später in der Literatur Z-Kurve genannt wurde. Zur Beschleunigung wird mit einer trickreichen Methode, ausgehend von einem in der Datenbank außerhalb des aktuellen Suchbereichs "zufällig" angetroffenen Eintrag, der nächstliegende potentielle Eintrag innerhalb des Suchbereichs berechnet.

Die Methode wird inzwischen vielfach eingesetzt, sowohl in kommerziellen als auch in technischen Anwendungen, u.a. als Basisprozedur zur Nachbarschaftssuche in großen mehrdimensionalen Datenbeständen.

Kurzbeschreibung siehe http://en.wikipedia.org/wiki/Z-order (curve)
Original Artikel: H. Tropf, H. Herzog: Multidimensional Range Search in Dynamically Balanced Trees, Angewandte Informatik, 2/1981, pp 71-77;
siehe Multidimensionalrangequery.pdf

Das Verfahren ist anwendbar mit allen eindimensional sortierenden Datenstrukturen. Professor Rudolf Bayer und Mitarbeiter, München, verwenden als Suchbaum den bekannten B+-Baum (Information nur in den Blättern), in diesem Fall UB-Baum genannt ("universeller B-Baum"). Dies wurde im EU-Projekt MISTRAL (1997 bis 2003) ausgearbeitet. Ein UB-Baum wird verwendet im Datenbanksystem Transbase der Firma Transaction Software.

Kurzbeschreibung zum UB-Baum siehe http://en.wikipedia.org/wiki/UB-tree

Zum Mistral-Projekt siehe http://mistral.in.tum.de/project/
oder http://www.abayfor.de/forwiss/projekte_detail.php?pk=22

Siehe auch
V. Markl: MISTRAL: Processing Relational Queries using a Multidimensional Access Technique. Doctoral Thesis University of Munich, Germany, 1999.F. Ramsak et al: Integrating the UB-tree into a Database System Kernel. Int. Conf. on Very Lage Databases, (VLDB) 2000, pp 263-272.

Bei Vision Tools findet die 1981 von Tropf/Herzog vorgestellte Methode Anwendung im Rahmen von Verfahren zur Werkstückerkennung. Fortführungen der Grundlagenarbeiten finden sich in unserem erteilten EU-Patent EP 1441293 (Übergang von der Z-Kurve auf die Hilbert-Kurve, s.a.  http://en.wikipedia.org/wiki/Hilbert_curve und US Patentanmeldung 2004/0177065). Eine für beliebige Raumkurven anwendbare Verbesserung, besonders vorteilhaft für externes Speichern, findet man in unserem deutschen Patent DE 103 31 679.