Vi ger den första optimala algoritmen för att uppskatta antalet olika element i en dataström, stänga en lång rad teoretisk forskning om detta problem som inleddes av Flajolet och Martin i deras seminal papper i FOCS 1983. Detta problem har applikationer för att fråga optimering, Internet routing, nätverk topologi, och data mining. För en ström av index i {1,..., n} beräknar vår algoritm en (1 ± ε)-uppskattning med en optimal O(ε −2 +log(n)) bitar av utrymme med 2/3 framgångsannolikhet, där 0 < ε < 1 ges. Denna sannolikhet kan förstärkas genom oberoende upprepning. Dessutom processar vår algoritm varje ström uppdatering i O(1) värsta fall tid, och kan rapportera en uppskattning vid någon punkt mittström i O(1) värsta fall tid, vilket löser både utrymme och tids komplexitet samtidigt. Vi ger också en algoritm för att uppskatta hamming normen för en ström, en generalisering av antalet olika element, som är användbart vid datarengöring, paketspårning och databasrevision. Vår algoritm använder nästan optimalt utrymme och har optimala uppdaterings- och rapporteringstider för O(1).
Kane, Nelson och Woodruff REF ger en optimal algoritm, med hjälp av O 1  på 2 + log n bitar av utrymme, för att ge en (1 +  på)- tillnärmning till antalet olika element i en dataström, med konstant sannolikhet.
An optimal algorithm for the distinct elements problem
{'venue': "PODS '10", 'journal': None, 'mag_field_of_study': ['Computer Science']}