Uppskattning av frekvenser av objekt över dataströmmar är en vanlig byggsten i streaming datamätning och analys. Misra och Gries introducerade sin sädesalgoritm för problemet 1982, och problemet har sedan dess återbesökts många gånger på grund av dess praktiska och tillämplighet. Vi beskriver en mycket optimerad version av Misra och Gries algoritm som lämpar sig för installation i industriella miljöer. Vår kod offentliggörs via ett open source-bibliotek som heter Data Sketches och som redan används av flera företag och produktionssystem. Vår algoritm förbättrar två teoretiska och praktiska aspekter av tidigare arbete. För det första hanterar den viktade uppdateringar i amorterad konstant tid, ett vanligt krav i praktiken. För det andra använder den en enkel och snabb metod för att slå samman sammanfattningar som asymptotiskt förbättras på tidigare arbete även för oviktade strömmar. Vi beskriver experiment som bekräftar att våra algoritmer är effektivare än tidigare förslag. • Teori för beräkning → Streaming, sublinjär och nära linjär tid algoritmer; • Nätverk → Nätverksmätning; KEYWORDS strömmande algoritmer, sammanslagningsbara sammanfattningar, frekventa objekt ACM Referensformat:
Det mycket senaste arbetet av REF, introducerar en sammanslagningsbar algoritm som fungerar i amortized konstant tid.
A high-performance algorithm for identifying frequent items in data streams
{'venue': "IMC '17", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}