Abstrakt. De senaste åren har ökat intresset för effektiva algoritmer för att sammanfatta och ifrågasätta massiva, snabba dataströmmar. Randomiserade skisssynops ger exakta approximationer för allmänna sammanfattningar av streaming datadistribution (t.ex., wavelets). Fokus för det befintliga arbetet har vanligtvis varit att minimera rymdbehoven för den bibehållna synopsis - dock, för att effektivt stödja höghastighetsdata-ström analys, är ett viktigt praktiskt krav också att optimera: (1) uppdateringstiden för att införliva en strömmande dataelement i skissen, och (2) frågetiden för att producera en ungefärlig sammanfattning (t.ex. de översta våget koefficienter) från skissen. Sådana tidsåtgångskostnader måste vara tillräckligt små för att klara snabba stream-arrivalhastigheter och krav på realtidsförfrågan för typiska streamingapplikationer (t.ex. ISP-nätverksövervakning). Med billigt och gott minne, utrymme är ofta bara en sekundär oro efter förfrågan / update tid kostnader. I detta dokument föreslår vi den första snabba lösningen på problemet med att spåra våget representationer av endimensionella och flerdimensionella dataströmmar, baserat på en ny ström synopsis, Group-Count Sketch (GCS). Genom att införa en hierarkisk struktur av grupper över data och tillämpa GCS, våra algoritmer kan snabbt återställa de viktigaste våget koefficienter med garanterad noggrannhet. En avvägning mellan frågetid och uppdateringstid etableras genom att gruppernas hierarkiska struktur varieras, vilket gör det möjligt att hitta rätt balans för specifika dataflöden. Experimentell analys bekräftar denna kompromiss och visar att alla våra metoder avsevärt överträffar tidigare kända metoder både vad gäller uppdateringstid och frågetid, samtidigt som en hög grad av noggrannhet upprätthålls.
Cormode m.fl. REF förbättrade sedan effektiviteten i skissen med Group-Count Sketch (GCS).
Fast approximate wavelet tracking on streams
{'venue': 'In EDBT', 'journal': None, 'mag_field_of_study': ['Computer Science']}