Abstrakt. Vi studerar det klassiska problemet med att uppskatta summan av n variabler. Den traditionella enhetliga provtagningsmetoden kräver ett linjärt antal prover för att ge eventuella icke-triviala garantier för den uppskattade summan. I detta papper överväger vi olika provtagningsmetoder förutom enhetlig provtagning, särskilt provtagning en variabel med sannolikhet i proportion till dess värde, som kallas linjär vägd provtagning. Om endast linjärt vägd provtagning är tillåten, visar vi en algoritm för att uppskatta summan med Õ( ε n) prover, och det är nästan optimalt i den meningen att  och ( ε n) prover är nödvändiga för någon rimlig summa estimator. Om det är tillåtet med både enhetlig provtagning och linjärt vägd provtagning, visar vi en summering av proven med Õ( 3 ε n). Mer allmänt kan vi tillåta generell viktad provtagning där sannolikheten för provtagning en variabel är proportionell mot någon funktion av dess värde. Vi bevisar en lägre gräns av  och 3 ε n) prover för en rimlig summa estimator med hjälp av allmän viktad provtagning, vilket innebär att vår algoritm som kombinerar enhetlig och linjär viktad provtagning är en nästan optimal summa estimator.
Viktad och enhetlig provtagning beaktas i Ref BBS09].
Estimating Sum by Weighted Sampling
{'venue': 'ICALP', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}