Wie funktioniert der RKV-Algorithmus?
Der RKV-Algo ist ein modifizierter Branch-and-Bound-Algo. Er setzt voraus, dass ein Baum mit lokaler Gruppierung, Minimum Bounding Rectangles (MBRs) als Cluster-Geometrie und Feature-Objekten nur in den Blättern vorliegt.
Die Kindknoten werden anhand der MIN- (optimistisch) oder MINMAX-Dist (pessimistisch) sortiert. Die sortierten Kindknoten werden in der Active Branch List verwaltet. Es gibt drei Strategien, um nicht die gesamte ABL durchsuchen zu müssen:
1. Alle Knoten mit MIN-Dist > MINMAX-Dist entfernen.
2. obereGrenze auf kleinste MINMAX-Dist setzen.
3. Alle Knoten mit MINMAX-Dist > obereGrenze entfernen.
Für KNN-Anfragen: Sortierte Warteschlange mit k NN-Kandidaten, obereGrenze ist Distanz zum letzten Kandidat.
Die Kindknoten werden anhand der MIN- (optimistisch) oder MINMAX-Dist (pessimistisch) sortiert. Die sortierten Kindknoten werden in der Active Branch List verwaltet. Es gibt drei Strategien, um nicht die gesamte ABL durchsuchen zu müssen:
1. Alle Knoten mit MIN-Dist > MINMAX-Dist entfernen.
2. obereGrenze auf kleinste MINMAX-Dist setzen.
3. Alle Knoten mit MINMAX-Dist > obereGrenze entfernen.
Für KNN-Anfragen: Sortierte Warteschlange mit k NN-Kandidaten, obereGrenze ist Distanz zum letzten Kandidat.
Tags: mehrdimensional index rkv
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)
mehrdimensional index rkv (1)
modelle (1)
objektrelational (1)
oodbms (1)
probleme (1)
r-baum (3)
x-baum (2)
