Die in der Literatur zur Ähnlichteilsuche genannten Verfahren zum geometrischen Ähnlichkeitsvergleich (z.B. [AB 92], [Jag 91], [GM 93], [FRM 94]) entstammen den verschiedensten Bereichen von Informatik, Ingenieur- und Naturwissenschaft. Hieraus ergibt sich eine sehr große Vielfalt bezüglich des Ähnlichkeitsmaßes, das die Algorithmen verwenden. Deswegen ist einer der Forschungsschwerpunkte die Klassifikation der bekannten Algorithmen und damit eine Formalisierung des Begriffs "Ähnlichkeit" für das Anwendungsgebiet "Ähnlichteilsuche". Wichtig für die Klassifizierung sind Eigenschaften wie Rotations-, Translations- und Skalierungsinvarianz, sowie die Einteilung in lokale und globale Ähnlichkeitsbegriffe.
Ausgehend von dieser Klassifikation wurden von uns mehrere Algorithmen ent wickelt, die eine effiziente Ähnlichkeitssuche ermöglichen. Hierbei ist insbesondere [BKK 96a] zu nennen, ein Verfahren zur partiellen Ähnlichkeitssuche auf Polygonen im Zweidimensionalen. Ein anderes von uns entwickeltes Verfahren (Section Coding) wird in [BKK 97] vorgestellt. Dieses Verfahren ist für die globale Ähnlichkeitssuche geeignet. Im Gegensatz zu bisherigen Verfahren ist Section Coding robust gegen kleine Veränderungen der Polygonkontur und dennoch sehr effizient.
Um die verschiedenen Algorithmen auch experimentell auf ihre Leistungsfähigkeit hin zu untersuchen, wurden alle Algorithmen in unser Prototyp-Datenbanksystem S3 iintegriert, mit dessen Hilfe wir in der Lage sind, verschiedene Algorithmen miteinander zu kombinieren, zu vergleichen und auch auf sehr große Datenmengen anzuwenden.
Die in der Literatur vorherrschende Technik für die Ähnlichkeitssuche beruht auf einem Feature-basierten Ansatz. Das heißt, aus der Menge der Polygons in der Datenbank wird eine Menge von Eigenschaften extrahiert, die dann in einen sogenannten Feature-Vektor transformiert werden. Die Feature-Vektoren werden zum Zeitpunkt des Indexaufbaus in eine multidimensionale Indexstruktur, wie zum Beispiel den R*-Baum [BKSS 90] oder den X-Tree [BKK 96], eingefügt. Um eine Ähnlichkeitsanfrage zu bearbeiten, wird das Anfragepolygon ebenfalls in einen Feature-Vektor transformiert. Mit diesem Vektor wird eine Suche der k nächsten Nachbarn durchgeführt. Als Ergebnis der Suche erhält man eine Menge von Feature-Vektoren, deren euklidischer Abstand zum Feature-Vektor des Anfragepolygons klein ist. Diese gehören zu Polygonen aus der Datenbank, die ähnliche Eigenschaften wie das Anfragepolygon besitzen und daher ähnlich zum Anfragepolygon sind.
Bisher bekannte multidimensionale Indexstrukturen sind für Datenräume der Dimensionen 2 bis 6 effizient. Da Feature-Räume jedoch Dimensionen von bis zu 64 haben können, entwickelten wir eine neue Indexstruktur, die speziell für hochdimensionale Datenräume konzipiert wurde, den X-tree [BKK 96]. Der X-tree basiert ähnlich dem R*-Baum auf dem Konzept der überlappenden Regionen. Im Gegensatz zum R*-Baum jedoch verwendet der X- tree einen speziellen Splitalgorithmus für hochdimensionale Räume. Zudem nutzt der X- tree das Konzept der supernodes - speziellen Directoryknoten - die entstehen, wenn eine hierarchische Organisation des Datenraums nicht effizient möglich ist. Supernodes sind Directoryknoten variabler Größe (einem Vielfachen der Blockgröße). Eine ausführliche experimentelle Evaluierung des X-tree zeigte, daß er für hochdimensionale Datenräume sowohl dem R*-Baum als auch dem TV-tree überlegen ist. Dies gilt sowohl für verschiedene Anfragetypen wie Punktanfragen und Anfragen nach den k nächsten Nachbarn als auch für verschiedene Datenverteilungen. Der erzielte Leistungsgewinn liegt bei einem Faktor von bis zu 450.
[AB 92] Alt H., Blömer J.: `Resemblance and Symmetrics of Geometric Patterns', in: Momnien B., Ottmann T. (eds.): `Data Structures and Efficient Algorithms', Lecture Notes in Computer Science, Vol. 594, 1992, pp. 1-24.
[BBKK 96] Berchtold S., Böhm C., Keim D. A., Kriegel H.-P.: "A Cost Model For Nearest Neighbor Search in High-Dimensional Data Space", submitted for publication
[BHKS 93] Brinkhoff T., Horn H., Kriegel H.-P., Schneider R.: `Eine Speicher- und Zugriffsarchitektur für effiziente Anfragebearbeitung in Geo-Datenbanksystemen', Datenbanksysteme in Büro, Technik und Wissenschaft, Braunschweig, Informatik aktuell, Springer, 1993, pp. 356-374; englische Fassung: `A Storage and Access Architecture for Efficient Query Processing in Spatial Database Systems' in: Proc. 3rd Int. Symp. on Large Spatial Databases, Singapore, Lecture Notes in Computer Science, Vol. 692, Springer, 1993, pp. 357-376.
[BK 96] Berchtold S., Kriegel H.-P.: "S3: Similarity Search in CAD Database Systems", submitted for publication
[BKK 96] Berchtold S., Keim D. A., Kriegel H.-P.: "The X-Tree: An Index Structure for High-Dimensional Data", Proc. 22th Int. Conf. on Very Large Data Bases, Bombay, India, 1996
[BKK 96a] Berchtold S., Keim D. A., Kriegel H.-P.: "Using Extended Feature Objects for Partial Similarity Retrieval", accepted for publication in: VLDB Journal, 1996
[BKK 96b] Berchtold S., Keim D. A., Kriegel H.-P.: "Application of Similarity Search Techniques in the Car Manufacturing Industry", submitted for publication, 1996
[BKK 97] Berchtold S., Keim D. A., Kriegel H.-P.: "Section Coding: Ein Verfahren zur Ähnlichkeitssuche in CAD-Datenbanken", accepted for publication in: GI-Fachtagung Datenbanksysteme in Büro, Technik und Wissenschaft, Ulm, 1997, in: Informatik aktuell, Springer, 1997
[BKSS 90] Beckmann N., Kriegel H.-P., Schneider R., Seeger B.: `The R*-tree: An Efficient and Robust Access Method for Points and Rectangles', Proc. ACM SIGMOD Int. Conf. on Management of Data, Atlantic City, NJ, 1990, pp. 322-331.
[DIN 81] DIN 4000 Teil 1: `Sachmerkmalleisten, Begriffe und Grundsätze', Beuth, 1981.
[FRM 94] Faloutsos, C., Ranganthan, M., Manolopoulos, Y.: `Fast Subsequence Matching in Time-Series Databases', Proc. ACM SIGMOD Int. Conf. on Management of Data, Minneapolis,Minnesota, 1994.
[GM 93] Gary J.E., Mehrotra R.: `Similar Shape Retrieval Using a Structural Feature Index', Information Systems, Vol. 18, No. 7, 1993, pp. 525-537.
[Jag 91] Jagadish H.V.: `A Retrieval Technique for Similar Shapes', Proc. ACM SIGMOD Int. Conf. on Management of Data, Denver, CO, 1991, pp. 208-217.
[Opi 71] Opitz, H.: `Werkstückbeschreibende Klassifizierungssysteme', Girardet, 1971.
[SKSH 89] Schneider R., Kriegel H.-P., Seeger B., Heep S.: `Geometry-based Similarity Retrieval of Rotational Parts', Proc. Int. Conf. on Data and Knowledge Systems for Manufacturing and Engineering, Gaithersburg, ML, 1989, pp. 150-160.