Key points are not available for this paper at this time.
Die Effizienz vieler bestehender hochdimensionaler Indexstrukturen ist auf spezifische Abfragetypen und Arbeitslasten begrenzt. Zum Beispiel sind die Pyramiden-Technik und der iMinMax effizient für Fensterabfragen, während der iDistance bei kNN-Abfragen überlegen ist. Wir präsentieren eine neue Struktur, die P/sup +/-Baum genannt wird, die sowohl Fensterabfragen als auch kNN-Abfragen unter verschiedenen Arbeitslasten effizient unterstützt. Im P/sup +/-Baum wird ein B/sup +/-Baum verwendet, um die Datenpunkte wie folgt zu indexieren. Der Datenraum wird basierend auf Clustering in Teilräume partitioniert, und Punkte in jedem Teilraum werden unter Verwendung der Pyramiden-Technik auf einen eindimensionalen Raum abgebildet und im B/sup +/ -Baum gespeichert. Der Kern des Schemas liegt in der Transformation der Daten, die zwei entscheidende Eigenschaften hat. Erstens wird jeder Teilraum in einen Hyperwürfel abgebildet, sodass die Pyramiden-Technik angewendet werden kann. Zweitens wird der Clusterzentrum an die Spitze der Pyramide verschoben, wodurch die Pyramiden-Technik sehr effizient funktioniert. Wir präsentieren Algorithmen zur Verarbeitung von Fenster- und kNN-Abfragen für den P/sup +/-Baum. Durch eine umfassende Leistungsstudie zeigen wir, dass der P/sup +/-Baum einen erheblichen Geschwindigkeitsvorteil gegenüber der Pyramiden-Technik und dem iMinMax für Fensterabfragen aufweist und den iDistance bei kNN-Abfragen übertrifft.
Zhang et al. (Tue,) haben diese Frage untersucht.