De distinkta element problem är ett av de grundläggande problemen i strömmande algoritmer -med tanke på en ström av heltal i intervallet {1,..., n}, Vi vill ge en (1 + ε) approximation till antalet olika element i inmatningen. Efter en lång rad forskning en optimal lösning för detta problem med konstant sannolikhet för framgång, med hjälp av O( 1 ε 2 + lg n) bitar av utrymme, gavs av Kane, Nelson och Woodruff 2010. Den standardmetod som används för att uppnå låg felsannolikhet är att ta medianvärdet för ng δ –1 parallella upprepningar av den ursprungliga algoritmen. Vi visar att en sådan multiplikativ rymduppblåsning är onödig: vi tillhandahåller en optimal algoritm med hjälp av O( lg δ −1 ε 2 + lg n) bitar av utrymme -matchning kända nedre gränser för detta problem. Det vill säga, faktorn lg δ −1 multiplicerar inte lg n-termen. Detta löser helt rymdkomplexet hos de olika elementen problem med avseende på alla standardparametrar. Vi överväger också den starka spårning (eller kontinuerlig övervakning) varianten av de olika element problem, där vi vill ha en algoritm som ger en approximation av antalet olika element som setts hittills, vid alla tidpunkter av strömmen. Vi visar att denna variant kan lösas med hjälp av O( lg lg n+lg δ −1 ε 2 +lg n) bitar av utrymme, som vi visar att vara optimal.
Blasiok REF visar att för att öka denna sannolikhet upp till 1 − δ för en given 0 < δ < 1, är standardmetoden för att köra O log 1 δ oberoende instanser faktiskt suboptimal och ger en optimal algoritm som använder O log δ −1  och 2 + log n bitar av utrymme.
Optimal streaming and tracking distinct elements with high probability
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}