This flashcard is just one of a free flashcard set. See all flashcards!
25
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 info:
Author: kread
Main topic: Informatik
Topic: Semantic Web
School / Univ.: Universität Koblenz-Landau
City: Koblenz
Published: 22.10.2010