Abstrakt. Viktad provtagning utan ersättning har visat sig vara ett mycket viktigt verktyg för att utforma nya algoritmer. Efraimidis och Spirakis (IPL 2006) presenterade en algoritm för viktad provtagning utan ersättning från dataströmmar. Deras algoritm fungerar under antagandet av exakta beräkningar över intervallet [0, 1]. Cohen och Kaplan (VLDB 2008) använde liknande metoder för sina bottenskisser. Efraimidis och Spirakis frågar som en öppen fråga om användningen av ändlig precision aritmetisk påverkar noggrannheten hos deras algoritm. I detta dokument visar vi en metod för att undvika detta problem genom att ge en exakt minskning från k-sampling utan ersättning till k-sampling med ersättning. Vi kallar den resulterande metoden Cascade Provtagning.
Braverman m.fl. REF presenterade en annan sekventiell algoritm för viktad SWOR, med hjälp av en reduktion till provtagning med ersättning genom en "cascade sampling"-algoritm.
Weighted Sampling Without Replacement from Data Streams
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}