Count-Min skiss är en viktig och välstuderad data summeringsmetod. Det kan uppskatta antalet av alla objekt i en ström med hjälp av en liten, xed storlek data skiss. Emellertid exaktheten av Count-Min skissen beror på karakteristika av de underliggande data. Detta har lett till ett antal beräkningsförfaranden som fungerar bra i ett scenario men fungerar dåligt i andra. En utövare ställs inför två grundläggande, obesvarade frågor. Med tanke på en uppskattning, vad är dess fel? Vilket skattningsförfarande bör väljas när uppgifterna är okända? Vi ger svar på dessa frågor. Vi härleder nya räknare estimatorer, inklusive en bevisligen optimal estimator, som bäst eller matcha tidigare estimatorer i alla scenarier. Vi tillhandahåller också praktiska, snäva felgränser vid frågestunden för alla estimatorer och metoder för att justera skissparametrar med hjälp av dessa gränser. Den viktigaste iakttagelsen är att den fullständiga fördelningen av fel i varje räknare empiriskt kan beräknas från själva skissen. Genom rst uppskattning av denna fördelning, räknas uppskattning blir en statistisk uppskattning och slutsats problem med en känd felfördelning. Detta ger både ett principfast sätt att härleda nya och optimala estimatorer samt ett sätt att studera fel och egenskaper hos befintliga estimatorer.
Precis som de distinkta räkningsresultaten ger REF en påvisbar optimal uppskattning för CountMin-skissen.
Count-Min: Optimal Estimation and Tight Error Bounds using Empirical Error Distributions
{'venue': None, 'journal': 'Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining', 'mag_field_of_study': ['Computer Science', 'Mathematics']}