Name
Abstract | ||
|---|---|---|
We introduce a new method of data collection for flow size estimation, the Optimized Flow Sampling Sketch, which combines the optimal properties of Flow Sampling with the computational advantages of a counter array sketch. Using Fisher Information as a definitive basis of comparison, we show that the statistical efficiency of the method is within a constant factor of that of Flow Sampling, which is known to be optimal but which cannot be implemented without a flowtable, which has higher memory and computational costs. In the process we derive new results on the Fisher-Information theoretic and variance properties of the counter array sketch, proving that an overloaded sketch actually destroys information. We revisit the ‘Eviction Sketch’ of Ribeiro et alia using the Fisher Information framework. We show that its performance is much higher than previously supposed, and we define a new method, the Optimized Eviction Sketch, which has very high efficiency. We compare these methods against each other and a third skampling method, ‘Sketch Guided Sampling’, theoretically, on models and on data. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1109/TIT.2015.2418770 | Information Theory, IEEE Transactions |
Keywords | Field | DocType |
cramer-rao lower bounds,internet,maximum likelihood estimation,sampling methods,sketching,vectors,statistical efficiency,radiation detectors,estimation,fisher information,transport protocols,data collection | Efficiency,Data collection,Discrete mathematics,Computer science,Flow (psychology),Algorithm,Maximum likelihood,Theoretical computer science,Sampling (statistics),Fisher information,Sketch | Journal |
Volume | Issue | ISSN |
PP | 99 | 0018-9448 |
Citations | PageRank | References |
3 | 0.39 | 13 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Darryl Veitch | 1 | 903 | 84.47 |
| Paul Tune | 2 | 83 | 8.83 |