Anfragebearbeitung für reverse k-nächste Nachbarn Anfragen
Zusammenfassung der Projektergebnisse
Ziel einer reversen k-nächsten Nachbarn (RkNN) Anfrage ist es, zu einem gegebenen Anfrageobjekt diejenigen Objekte einer Datenbank zu bestimmen, die das Anfrageobjekt als einen ihrer k-nächsten Nachbarn (k NN) erkennen. Das Ergebnis kann als Menge von Datenbankobjekten interpretiert werden, die von dem Anfrageobjekt beeinflusst werden. Eine effiziente Bearbeitung dieses Anfragetyps ist in verschiedensten Anwendungsbereichen wie z.B. bei Location-based Services, bei Online-Informationssystemen etc. sowie als Basisoperation in Data Mining Algorithmen von wesentlicher Bedeutung. Bisherige Anfragemethoden basieren auf Schätzungen der kNN-Distanzen der einzelnen Datenobjekte und verwenden dabei meist sehr einschränkende Annahmen bzgl. des Ähnlichkeitsmaßes bzw. der Modellierung der Datenobjekte. Die kNN-Distanz-Approximationen werden insbesondere für das Pruning, also das Ausschließen von Datenbankobjekten, die keine Treffer sind, verwendet. In diesem Projekt wurden neue Methoden entwickelt, um einige Einschränkungen der existierenden Methoden zu beseitigen. Dazu wurde zunächst ein neues mehrstufiges Verfahren vorgestellt, das zur Schätzung der kNN-Distanzen das Konzept der Intrinsischen Dimensionalität verwendet. Anschließend wurde ein neues Verfahren erforscht, das die kNN-Distanzen mit einem Verfahren aus dem Maschinellen Lernen lernt. Ein weiteres Ergebnis des Projekts schließt mit der Entwicklung eines ersten Kostenmodells für RkNN-Anfragen eine wichtige Lücke in der automatischen Anfrageoptimierung. Zudem wurde ein neues Partitionierungsverfahren für die Indexierung vorgestellt, welches auf Verfahren des maschinellen Lernens basiert. Zuletzt wurden die theoretischen Grundlagen für optimale Pruning-Strategien erarbeitet und formalisiert.
Projektbezogene Publikationen (Auswahl)
-
Dimensional testing for reverse k -nearest neighbor search. Proceedings of the VLDB Endowment, 10(7), 769-780.
Casanova, Guillaume; Englmeier, Elias; Houle, Michael E.; Kröger, Peer; Nett, Michael; Schubert, Erich & Zimek, Arthur
-
k-Distance Approximation for Memory-Efficient RkNN Retrieval. Lecture Notes in Computer Science (2019), 57-71. Springer International Publishing.
Berrendorf, Max; Borutta, Felix & Kröger, Peer
-
Memory-Efficient RkNN Retrieval by Nonlinear k-Distance Approximation. 2020 IEEE/WIC/ACM International Joint Conference on Web Intelligence and Intelligent Agent Technology (WI-IAT), 12(2020, 12), 387-390. IEEE.
Obermeier, Sandra; Berrendorf, Max & Kroger, Peer
-
A Cost Model for Reverse Nearest Neighbor Query Processing on R-Trees Using Self Pruning. Lecture Notes in Computer Science (2021), 45-53. Springer International Publishing.
Borutta, Felix; Kröger, Peer & Renz, Matthias
-
Towards a Learned Index Structure for Approximate Nearest Neighbor Search Query Processing. Lecture Notes in Computer Science (2021), 95-103. Springer International Publishing.
Hünemörder, Maximilian; Kröger, Peer & Renz, Matthias
-
Complete and Sufficient Spatial Domination of Multidimensional Rectangles. Spatial Gems, Volume 1 (2022, 8, 5), 25-32. ACM.
Emrich, Tobias; Kriegel, Hans-Peter; Züfle, Andreas; Kröger, Peer & Renz, Matthias
