Pantheon: Efficiently Creating and Maintaining Semantically Meaningful Entity Rankings at Large-Scale
Final Report Abstract
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.
Publications
- 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
(See online at https://doi.org/10.5441/002/edbt.2015.23) - 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
(See online at https://doi.org/10.1145/2949689.2949709) - 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
(See online at https://doi.org/10.14778/3007263.3007300) - Mining Entity Rankings. Datenbank-Spektrum 16(1), 27-38, 2016
Fabian Reinartz, Koninika Pal, Sebastian Michel
(See online at https://doi.org/10.1007/s13222-015-0205-2) - 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
(See online at https://doi.org/10.5441/002/edbt.2016.74) - Reverse Engineering Top-k Database Queries with PALEO. In 19th International Conference on Extending Database Technology (EDBT), 113-124, 2016
Kiril Panev, Sebastian Michel
(See online at https://doi.org/10.5441/002/edbt.2016.13) - 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
(See online at https://doi.org/10.1145/3221269.3223035) - Concept and Computation of Ranking-based Dominance. In Information Systems. 84: 174-188, 2019
Kiril Panev and Sebastian Michel
(See online at https://doi.org/10.1016/j.is.2019.05.004) - Distributed Similarity Joins over Top-K Rankings. In 23rd International Conference on Extending Database Technology (EDBT), pages 205-216, 2020
Evica Milchevski, Sebastian Michel
(See online at https://doi.org/10.5441/002/edbt.2020.19)
