Subspace Similarity Search
Motivation
Ähnlichkeitssuche in Datenbanken umfasst viele spannende Anwendungsgebiete, u.a.:
- Suche nach ähnlichen Musikstücken in einer Musikdatenbank
- Auffinden gleichartiger Bilder in einer Bildersammlung
- Suchen von ähnlichen elektronischen Krankenakten
- U.v.m.
Die Objekte werden dabei meist über eine gewisse Anzahl von numerischen Attributen (Features) beschrieben, welche dann miteinander vergleichen werden um Ähnlichkeit zu erkennen. Ein Hauptaspekt um solche Anwendungen nutzbar zu machen ist die effiziente Beantwortung der Anfragen, da Nutzer in der Regel keine Suchzeiten von mehreren Minuten in Kauf nehmen. Daher wurden in den letzten 2 Jahrzehnten vielen Indexstrukturen (u.a. R- und R*-Baum) entwickelt um diese Art von Anfragen zu beschleunigen. Eine interessante Problemstellung ergibt sich, wenn Nutzer Ähnlichkeit zwischen den Objekten nun nicht mehr aufgrund aller Features definieren, sondern nur noch auf einer Untermenge der Attribute. Beispielsweise:
- Suche nach einem Musikstück mit gleicher Taktfrequenz
- Auffinden eines Bildes mit gleichen Farben
- Suchen von ähnlichen Anomalien in elektronischen Krankenakten
Da die gesuchte Untermenge an Attributen vorab nicht bekannt ist, können hier nur neuartige Suchtechniken Abhilfe schaffen, welche Subspace Anfragen effizient unterstützen.
Problemstellung
In diesem Projekt sollen zunächst vorhandene Subspace-Suchverfahren (Indexunterstützt) implementiert und evaluiert werden. Anschließend soll auf dieser Basis eine neue Struktur geschaffen werden, welche verschiedene Vorteile der bestehenden Verfahren vereint.
Vorkenntnisse
- Gute Kenntnisse in Java
- Kenntnisse in „Indexstrukturen“
- Kenntnisse in „Spatial, Temporal and Multimedia Databases“ sind hilfreich
Kontakt
