Was ist das Problem bei hohen Dimensionen? Was kann man tun?
Ab 20 Dimensionen versagt NN-Suche in Indexbäumen, es werden keine Teilbäume mehr ausgeschlossen, und ein sequentieller Durchlauf wäre effizienter: Der Fluch der hohen Dimensionen. Der Grund liegt in steigenden Approximationsfehlern und konstantem Abstand zwischen größter und kleinster Distanz. Das gilt auch für Metrik-Bäume wie den M-Baum.
Man kann versuchen:
Komplexe Distanzfunktionen durch einfache Distanzfunktion substituieren, solange diese Objekte korrekt ausschließt.
FastMap etwa bildet eine Metrik (Objekte und Distanzen) approximativ auf k-dimensionale Punkte und euklidische Distanzfunktionen ab.
Man kann versuchen:
Komplexe Distanzfunktionen durch einfache Distanzfunktion substituieren, solange diese Objekte korrekt ausschließt.
FastMap etwa bildet eine Metrik (Objekte und Distanzen) approximativ auf k-dimensionale Punkte und euklidische Distanzfunktionen ab.
Tags: baum, mehrdimensional, probleme
Source: MMDB 2009 Kapitel 7
Source: MMDB 2009 Kapitel 7
Flashcard set info:
Author: kread
Main topic: Informatik
Topic: Semantic Web
School / Univ.: Universität Koblenz-Landau
City: Koblenz
Published: 22.10.2010
Card tags:
All cards (35)
baum (9)
eigenschaften (1)
hs (1)
indexstruktur (1)
m-baum (2)
mehrdimensional (10)
modelle (1)
objektrelational (1)
oodbms (1)
probleme (1)
r-baum (3)
x-baum (2)
