Vi studerar kärnor för olika typer av intervall räkna frågor på osäkra data. I vår modell har varje osäker punkt en sannolikhetstäthet som beskriver dess placering, ibland definierad som k distinkta platser. Vårt mål är att bygga en delmängd av de osäkra punkter, inklusive deras plats osäkerhet, så att avstånd räkna frågor kan besvaras genom att bara undersöka denna delmängd. Vi studerar tre olika typer av frågor. RE-frågor returnerar det förväntade antalet poäng i ett frågeintervall. RC frågor returnerar antalet poäng i intervallet med sannolikhet minst ett tröskelvärde. RQ-frågor returnerar sannolikheten att mindre än någon tröskelfraktion av punkterna är i intervallet. I både RC- och RQ-kärnor anges tröskeln som en del av frågan. Och för varje typ av fråga vi ger coreset konstruktioner med approximation storlek kompromisser. Vi visar att slumpmässig provtagning kan användas för att konstruera varje typ av coreset, och vi ger också avsevärt förbättrade gränser genom att använda diskrepansbaserade metoder på axeljusterade intervallfrågor.
Abdullah m.fl. REF har också studerat coreset för intervallfrågor över stokastiska data.
Range counting coresets for uncertain data
{'venue': "SoCG '13", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}