QPOPSS: Abfrage und Parallelismus optimierter Speicherersparnis zur Auffindung häufiger Stream-Elemente

Das Problem der häufigen Elemente, ein Schlüsselkomponente in anspruchsvoller Stream-Datenanalyse, beinhaltet die Auswahl von Elementen, deren Auftreten einen benutzerdefinierten Schwellenwert überschreitet. Schnelle, speichereffiziente -approximative Synopsis-Algorithmen wählen alle häufigen Elemente aus, können diese jedoch je nach (benutzerdefiniertem Parameter) überschätzen. Fortschrittliche Anwendungen erfordern eine Leistung, die nur durch Parallelisierung erreicht werden kann. Algorithmische Garantien hinsichtlich konkurrierender Updates und Abfragen wurden jedoch übersehen. Wir schlagen Query and Parallelism Optimized Space-Saving (QPOPSS) vor, das Konsistenzgarantien bietet. Das Design beinhaltet eine Implementierung des Space-Saving-Algorithmus, der schnelle Abfragen unterstützt, was eine minimale Überlappung mit konkurrierenden Updates impliziert. QPOPSS integriert dies mit der Verteilung der Arbeit und einer feingranularen Synchronisation zwischen Threads, wodurch ein schnelles Gleichgewicht zwischen hohem Durchsatz, hoher Genauigkeit und niedrigem Speicherverbrauch hergestellt wird. Unsere Analyse unter verschiedenen Bedingungen der Parallelität und Datenverteilung zeigt Platz- und Approximationsgrenzen. Unsere empirische Bewertung im Vergleich zu repräsentativen Methoden des aktuellen Stands der Technik zeigt, dass der Multi-Threaded-Durchsatz von QPOPSS linear skaliert und gleichzeitig die höchste Genauigkeit aufrechterhält, mit um Größenordnungen kleinerem Speicherbedarf.