Pantheon: Erzeugung und Instandhaltung von semantisch sinnvollen Entitäts-Ranglisten über großen Datenmengen

• Antragsteller: Professor Dr.-Ing. Sebastian Michel
• Fachliche Zuordnung: Sicherheit und Verlässlichkeit, Betriebs-, Kommunikations- und verteilte Systeme
• Förderung: Förderung von 2013 bis 2020
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 241616207

• Erstellungsjahr: 2021

Zusammenfassung der Projektergebnisse

In diesem Forschungsprojekt sollte untersucht werden, wie sich aus Datenbanken oder Wissensdatenbanken (Knowledge Bases) interessante Top-k Ranglisten generieren lassen, wie diese instand gehalten werden können und letztendlich für die Datenexploration ausgenutzt werden können. Top-k Ranglisten enthalten die aus einer Gruppe von Entitäten hervorragenden Entitäten bzgl. Ausgewählter Kriterien, beispielsweise die Länder sortiert nach Anzahl gewonnener Goldmedaillen bei olympischen Winterspielen, oder Produkte eines Lebensmittelhandels geordnet nach Umsatz pro Quartal und Land. Mit Expertenwissen erscheint die Nennung solcher Ranglisten nicht sonderlich kompliziert zu sein. Die automatische Bewertung, welche Ranglisten interessant sind, ist für Daten in Wissensdatenbanken oder relationalen Daten mit unbekanntem Schemata allerdings nicht trivial. In diesem Projekt haben wir einen Ansatz entwickelt, der anhand statistischer Maße (wie Entropy und weiteren vorgeschlagenen Maßen) und aus Wikipedia extrahierten Beispielranglisten, via maschinellem Lernen, dies entscheiden kann. Beispielsweise konnte der Algorithmus aufgrund der in Wikipedia vorhandenen Informationen eine Rangliste vorschlagen, die in Wikipedia selbst zum Zeitpunkt des Experiments nicht vorhanden war, aber von Teilnehmern einer Benutzerstudie als interessant deklariert wurde. Einige Wochen später erschien ohne unser Mitwirken dann auch diese Rangliste in Wikipedia. Darüber hinaus haben wir neue Methoden zur Ähnlichkeitssuche und der Berechnung von paarweisen Ähnlichkeiten über großen Mengen von Ranglisten entwickelt. Dabei wurden Indexierungsmethoden auf die Besonderheiten der beteiligten Ähnlichkeitsmaße zugeschnitten (Spearman’s Footrule oder Kendall’s Tau). Für Kendall’s Tau waren wir in der Lage, einen auf invertierten Indexen basierenden Ansatz durch Locality Sensitive Hashing (LSH) zu modellieren und zu optimieren. Für Footrule-Distance waren wir ebenfalls in der Lage, durch die Entwicklung von Schwellwerten den Suchraum gezielt einzugrenzen. Speziell für die Ähnlichkeitssuche haben wir einen neuartigen hybriden Index entwickelt, der die Vorteile von herkömmlichen invertierten Indexen mit den Vorteilen von Indexierungsmethoden für metrische Räume zu kombinieren. Neben der Generierung von Ranglisten anhand von Kombinationen aus interessanten kategorischen und numerischen Attributen (wie Land und Anzahl Goldmedaillen) haben wir durch Arbeiten im Bereich Reverse-Engineering von Anfragen eine weitere Möglichkeit eröffnet, Ranglisten zu generieren sowie Datenbanken zu explorieren. Darüber hinaus haben wir mit Ranglisten-basierter Dominanz und den entsprechenden Algorithmen eine neuartige Möglichkeit entwickelt, wie Benutzer interaktiv Datenbankinhalte erforschen können.

Projektbezogene Publikationen (Auswahl)

• he Sweet Spot between Inverted Indices and Metric-Space Indexing for Top-K-List Similarity Search. In 18th International Conference on Extending Database Technology (EDBT), 253- 264, 2015
  Evica Milchevski, Avishek Anand, Sebastian Michel
  
• Efficient Similarity Search across Top-k Lists under the Kendall’s Tau Distance. 28th International Conference on Scientific and Statistical Database Management (SSDBM), 6:1-6:12, 2016
  Koninika Pal, Sebastian Michel
  
• Exploring Databases via Reverse Engineering Ranking Queries with PALEO. In Proc. VLDB Endow. (PVLDB) 9(13), 1525-1528, 2016
  Kiril Panev, Sebastian Michel, Evica Milchevski, Koninika Pal
  
• Mining Entity Rankings. Datenbank-Spektrum 16(1), 27-38, 2016
  Fabian Reinartz, Koninika Pal, Sebastian Michel
  
• Quantifying Likelihood of Change through Update Propagation across Top-k Rankings. In 19th International Conference on Extending Database Technology (EDBT), 660-661, 2016
  Evica Milchevski, Sebastian Michel
  
• Reverse Engineering Top-k Database Queries with PALEO. In 19th International Conference on Extending Database Technology (EDBT), 113-124, 2016
  Kiril Panev, Sebastian Michel
  
• Reverse Engineering Top-k Join Queries. In Datenbanksysteme für Business, Technologie und Web (BTW), 17. Fachtagung des GI-Fachbereichs Datenbanken und Informationssysteme (DBIS), 61-80, 2017
  Kiril Panev, Nico Weisenauer, Sebastian Michel
  
• Learning interesting attributes for automated data categorization. In 30th International Conference on Scientific and Statistical Database Management (SSDBM), 9:1-9:12, 2018
  Koninika Pal, Sebastian Michel
  
• Concept and Computation of Ranking-based Dominance. In Information Systems. 84: 174-188, 2019
  Kiril Panev and Sebastian Michel
  
• Distributed Similarity Joins over Top-K Rankings. In 23rd International Conference on Extending Database Technology (EDBT), pages 205-216, 2020
  Evica Milchevski, Sebastian Michel