Datenbanken und Informationssysteme

News

Alle News

Das Forschungspapier "Counting Butterflies in Fully Dynamic Bipartite Graph Streams" wurde zur Veröffentlichung im ICDE 2024 angenommen.

Wir gratulieren den Autoren, bestehend aus aktuellen und ehemaligen Mitgliedern des Fachgebiets Datenbanksysteme und Informationsmanagement (DIMA) der TU Berlin, zur Annahme ihres Forschungspapiers "Counting Butterflies in Fully Dynamic Bipartite Graph Streams" zur Veröffentlichung im ICDE 2024.

Titel:
Counting Butterflies in Fully Dynamic Bipartite Graph Streams

Autoren:
Serafeim Papadias ( TU Berlin ); Varun Pandey ( TU Berlin ); Zoi Kaoudi ( IT University of Copenhagen ); Jorge Arnulfo Quiané Ruiz ( IT University of Copenhagen ); Volker Markl ( Technische Universität Berlin )  

Zusammenfassung:
Ein zweiseitiger Graph modelliert umfassend Beziehungen zwischen realen Entitäten zweier unterschiedlicher Typen, wie z. B. Benutzer-Produkt-Daten im elektronischen Handel. 
Solche Graphen werden von Natur aus immer mehr gestreamt, was ein kontinuierliches Einfügen und Löschen von Kanten mit sich bringt. Ein Schmetterling (d. h. eine 2x2-Bi-Clique) ist die kleinste nicht-triviale kohäsive Struktur, die eine entscheidende Rolle spielt. Das Zählen solcher Schmetterlingsmuster in strömenden zweistufigen Graphen ist ein Kernproblem bei Anwendungen wie der Entdeckung dichter Untergraphen und der Erkennung von Anomalien. 
Vorhandene ungefähre Lösungen berücksichtigen jedoch nur Einfügevorgänge und erreichen daher nur eine sehr geringe Genauigkeit in vollständig dynamischen zweistufigen Graphenströmen, die sowohl Einfügungen als auch Löschungen von Kanten beinhalten. Die Anpassung dieser Lösungen an die Berücksichtigung von Löschungen ist ebenfalls nicht trivial, da andere Stichprobenverfahren und neue Genauigkeitsanalysen erforderlich sind. In diesem Papier schlagen wir Abacus vor, einen neuartigen approximativen Algorithmus, der Schmetterlinge sowohl bei Einfügungen als auch bei Löschungen zählt, indem er Stichproben verwendet. 
Wir beweisen, dass Abacus immer unverzerrte Schätzungen liefert. Außerdem erweitern wir Abacus und entwickeln eine parallele Mini-Batch-Variante, nämlich Parabacus, die Schmetterlinge parallel zählt. Parabacus zählt Schmetterlinge in einer lastausgeglichenen Art und Weise unter Verwendung von versionierten Stichproben, was zu einer signifikanten Beschleunigung führt und somit ideal für kritische Anwendungen in der Streaming-Umgebung ist. Wir evaluieren Abacus/Parabacus anhand einer Reihe von realen zweistufigen Graphen und bewerten seine Leistung in Bezug auf Genauigkeit, Durchsatz und Beschleunigung. Die Ergebnisse zeigen, dass unser Vorschlag der erste ist, der in der Lage ist, genaue Schmetterlingszählungen in der generischsten Form, d.h. in einer vollständig dynamischen Graphen-Streaming-Umgebung, die sowohl Einfügungen als auch Löschungen beinhaltet, effizient bereitzustellen. Dies geschieht ohne Einbußen beim Durchsatz und verbessert diesen sogar mit der parallelen Version.