En effektiv uppskattning av frekvensmoment för en dataström i en passage med begränsat utrymme och tidsåtgång per post är ett av de mest grundläggande problemen vid behandling av dataflöden. En särskilt viktig uppskattning är att hitta antalet olika element i en dataström, som i allmänhet kallas den nollte frekvens moment och betecknas med F 0. I detta papper, vi anser strömmar av rektanglar definieras över ett diskret utrymme och uppgiften är att beräkna det totala antalet distinkta punkter som omfattas av rektanglar. Detta är känt som Klee mäter problem i 2 dimensioner. Vi presenterar och analyserar en randomiserad streaming approximationsalgoritm som ger en ungefärlig F 0 för den totala arean av Klees mätproblem i 2 dimensioner. Vår algoritm uppnår följande komplexa gränser: (a) den amorterade bearbetningstiden per rektangel är O( 1  på 4 log 3 n log 1 δ ); (b) utrymme komplexiteten är O( 1 på 2 log n log 1 på ) bitar; och (c) tiden att svara på en fråga för F 0 är O(log 1 δ ), respektive. Så vitt vi vet är detta den första streaming approximationen för Klee's åtgärdsproblem som uppnår sub-polynomiska gränser.
Det finns ett tidigare försök till en lösning på Klee åtgärdsproblem på en dataström REF.
A Streaming Approximation Algorithm for Klee's Measure Problem
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}