I den här tidningen presenterar vi nästan optimala rymdgränser för Lpsamplers. Med tanke på en ström av uppdateringar (additioner och subtraktion) till koordinaterna för en underliggande vektor x  på R n, en perfekt Lp sampler outputs i-th koordinat med sannolikhet  på x x p p. I SODA 2010, Monemizadeh och Woodruff visade polylog utrymme övre gränser för ungefärliga Lp-samplers och demonstrerade olika tillämpningar av dem. Helt nyligen förbättrade Andoni, Krauthgamer och Onak de övre gränserna och gav ett O(-p log 3 n) utrymme relativt fel och konstant felfrekvens Lp-sampler för p  på [1, 2]. I detta arbete ger vi en annan sådan algoritm som kräver endast O( −p log 2 n) utrymme för p  till (1, 2). För p 0, 1) är vår rymdgräns O( −1 log 2 n), medan för p = 1 fall har vi en O(log(1/ ) −1 log 2 n) rymdalgoritm. Vi ger också en O(log 2 n) bitar noll relativ fel L0-sampler, förbättra O(log 3 n) bitar algoritm på grund av Frahling, Indyk och Sohler. Som en tillämpning av våra provtagare, ger vi bättre övre gränser för problemet med att hitta dubbletter i dataströmmar. Om strömmens längd är längre än alfabetets storlek, ger L1-provtagning oss en O(log 2 n) rymdalgoritm, vilket förbättrar den tidigare O(log 3 n) bunden på grund av Gopalan och Radhakrishnan. I den andra delen av vårt arbete visar vi en lägre (log 2 n) gräns för provtagning från 0, ±1 vektorer (i detta speciella fall är parametern p inte relevant för Lp provtagning). Detta matchar utrymmet för våra provtagningsalgoritmer för konstant > 0. Vi visar också snäva utrymme nedre gränser för att hitta dubbletter och tunga hitters problem. Vi får dessa lägre gränser med hjälp av minskningar från kommunikations komplexitet problem förstärkt indexering.
För p = 1 var det avstånd som uppnåddes med REF en log(1/ε) faktor som var sämre: O(ε −1 log(1/ε) log(1/δ) log 2 n) bits.
Tight bounds for Lp samplers, finding duplicates in streams, and related problems
{'venue': 'PODS', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}