Optimal sampling from sliding windows

ABSTRACT

A sliding windows model is an important case of the streaming model, where only the most "recent" elements remain active and the rest are discarded in a stream. The sliding windows model is important for many applications (see, e.g., Babcock, Babu, Datar, Motwani and Widom (PODS 02); and Datar, Gionis, Indyk and Motwani (SODA 02)). There are two equally important types of the sliding windows model -- windows with fixed size, (e.g., where items arrive one at a time, and only the most recent n items remain active for some fixed parameter n), and bursty windows (e.g., where many items can arrive in "bursts" at a single step and where only items from the last t steps remain active, again for some fixed parameter t).

Random sampling is a fundamental tool for data streams, as numerous algorithms operate on the sampled data instead of on the entire stream. Effective sampling from sliding windows is a nontrivial problem, as elements eventually expire. In fact, the deletions are implicit; i.e., it is not possible to identify deleted elements without storing the entire window. The implicit nature of deletions on sliding windows does not allow the existing methods (even those that support explicit deletions, e.g., Cormode, Muthukrishnan and Rozenbaum (VLDB 05); Frahling, Indyk and Sohler (SOCG 05)) to be directly "translated" to the sliding windows model. One trivial approach to overcoming the problem of implicit deletions is that of over-sampling. When k samples are required, the over-sampling method maintains k'>k samples in the hope that at least k samples are not expired. The obvious disadvantages of this method are twofold:

(a) It introduces additional costs and thus decreases the performance; and

(b) The memory bounds are not deterministic, which is atypical for streaming algorithms (where even small probability events may eventually happen for a stream that is big enough).

Babcock, Datar and Motwani (SODA 02), were the first to stress the importance of improvements to over-sampling. They formally introduced the problem of sampling from sliding windows and improved the over-sampling method for sampling with replacement. Their elegant solutions for sampling with replacement are optimal in expectation, and thus resolve disadvantage (a) mentioned above. Unfortunately, the randomized bounds do not resolve disadvantage (b) above. Interestingly, all algorithms that employ the ideas of Babcock, Datar and Motwani have the same central problem of having to deal with randomized complexity (see e.g., Datar and Muthukrishnan (ESA 02); Chakrabarti, Cormode and McGregor (SODA 07)). Further, the proposed solutions of Babcock, Datar and Motwani for sampling without replacement are based on the criticized over-sampling method and thus do not solve problem (a). Therefore, the question of whether we can solve sampling on sliding windows optimally (i.e., resolving both disadvantages) is implicit in the paper of Babcock, Datar and Motwani and has remained open for all variants of the problem.

In this paper we answer these questions affirmatively and provide optimal sampling schemas for all variants of the problem, i.e., sampling with or without replacement from fixed or bursty windows. Specifically, for fixed-size windows, we provide optimal solutions that require O(k) memory; for bursty windows, we show algorithms that require O(klogn), which is optimal since it matches the lower bound by Gemulla and Lehner (SIGMOD 08). In contrast to the work of of Babcock, Datar and Motwani, our solutions have deterministic bounds. Thus, we prove a perhaps somewhat surprising fact: the memory complexity of the sampling-based algorithm for all variants of the sliding windows model is comparable with that of streaming models (i.e., without the sliding windows). This is the first result of this type, since all previous "translations" of sampling-based algorithms to sliding windows incur randomized memory guarantees only.

REFERENCES

• 1: Charu C. Aggarwal, Data Streams: Models and Algorithms (Advances in Database Systems), Springer-Verlag New York, Inc., Secaucus, NJ, 2006
• 2: Charu C. Aggarwal, On biased reservoir sampling in the presence of stream evolution, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 3: Noga Alon , Nick Duffield , Carsten Lund , Mikkel Thorup, Estimating arbitrary subset sums with few probes, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland [doi>10.1145/1065167.1065209]
• 4: Noga Alon , Yossi Matias , Mario Szegedy, The space complexity of approximating the frequency moments, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.20-29, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237823]
• 5: A. Arasu, B. Babcock, S. Babu, J. Cieslewicz, M. Datar, K. Ito, R. Motwani, U. Srivastava, J. Widom, "STREAM: The Stanford Data Stream Management System," Book Chapter, "Data-Stream Management: Processing High-Speed Data Streams", Springer-Verlag, 2005.
• 6: Arvind Arasu , Gurmeet Singh Manku, Approximate counts and quantiles over sliding windows, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France [doi>10.1145/1055558.1055598]
• 7: Ahmed M. Ayad , Jeffrey F. Naughton, Static optimization of conjunctive queries with sliding windows over infinite streams, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007616]
• 8: Brian Babcock , Shivnath Babu , Mayur Datar , Rajeev Motwani , Jennifer Widom, Models and issues in data stream systems, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543615]
• 9: Brian Babcock , Shivnath Babu , Mayur Datar , Rajeev Motwani , Dilys Thomas, Operator scheduling in data stream systems, The VLDB Journal — The International Journal on Very Large Data Bases, v.13 n.4, p.333-353, December 2004 [doi>10.1007/s00778-004-0132-6]
• 10: Brian Babcock , Mayur Datar , Rajeev Motwani, Sampling from a moving window over streaming data, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.633-634, January 06-08, 2002, San Francisco, California
• 11: Brian Babcock , Mayur Datar , Rajeev Motwani, Load Shedding for Aggregation Queries over Data Streams, Proceedings of the 20th International Conference on Data Engineering, p.350, March 30-April 02, 2004
• 12: Brain Babcock , Mayur Datar , Rajeev Motwani , Liadan O'Callaghan, Maintaining variance and k-medians over data stream windows, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.234-243, June 09-11, 2003, San Diego, California [doi>10.1145/773153.773176]
• 13: Ziv Bar-Yossef, Sampling lower bounds via information theory, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780593]
• 14: Ziv Bar-Yossef , T. S. Jayram , Ravi Kumar , D. Sivakumar, An Information Statistics Approach to Data Stream and Communication Complexity, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.209-218, November 16-19, 2002
• 15: Ziv Bar-Yossef , Ravi Kumar , D. Sivakumar, Reductions in streaming algorithms, with an application to counting triangles in graphs, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.623-632, January 06-08, 2002, San Francisco, California
• 16: Ziv Bar-Yossef , T. S. Jayram , Ravi Kumar , D. Sivakumar , Luca Trevisan, Counting Distinct Elements in a Data Stream, Proceedings of the 6th International Workshop on Randomization and Approximation Techniques, p.1-10, September 13-15, 2002
• 17: Ziv Bar-Yossef , Ravi Kumar , D. Sivakumar, Sampling algorithms: lower bounds and applications, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.266-275, July 2001, Hersonissos, Greece [doi>10.1145/380752.380810]
• 18: Lakshminath Bhuvanagiri , Sumit Ganguly , Deepanjan Kesh , Chandan Saha, Simpler algorithm for estimating frequency moments of data streams, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.708-713, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109634]
• 19: Vladimir Braverman , Rafail Ostrovsky, Smooth Histograms for Sliding Windows, Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, p.283-293, October 21-23, 2007 [doi>10.1109/FOCS.2007.63]
• 20: Luciana S. Buriol , Gereon Frahling , Stefano Leonardi , Alberto Marchetti-Spaccamela , Christian Sohler, Counting triangles in data streams, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA [doi>10.1145/1142351.1142388]
• 21: Amit Chakrabarti , Graham Cormode , Andrew McGregor, A near-optimal algorithm for computing the entropy of a stream, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.328-335, January 07-09, 2007, New Orleans, Louisiana
• 22: A. Chakrabarti, K. Do Ba, S. Muthukrishnan, "Estimating Entropy and Entropy Norm on Data Streams", In Proceedings of the 23rd International Symposium on Theoretical Aspects of Computer Science, 2006.
• 23: A. Chakrabarti, S. Khot, X. Sun, "Near-optimal lower bounds on the multi-party communication complexity of set-disjointness", Proceedings of the 18th Annual IEEE Conference on Computational Complexity, 2003.
• 24: Kevin L. Chang , Ravi Kannan, The space complexity of pass-efficient algorithms for clustering, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1157-1166, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109685]
• 25: Moses Charikar , Chandra Chekuri , Tomas Feder , Rajeev Motwani, Incremental Clustering and Dynamic Information Retrieval, SIAM Journal on Computing, v.33 n.6, p.1417-1440, 2004 [doi>10.1137/S0097539702418498]
• 26: K. Chaudhuri, N. Mishra, "When Random Sampling Preserves Privacy", CRYPTO, 2006.
• 27: Surajit Chaudhuri , Rajeev Motwani , Vivek Narasayya, On random sampling over joins, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.263-274, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 28: Yun Chi , Haixun Wang , Philip S. Yu , Richard R. Muntz, Moment: Maintaining Closed Frequent Itemsets over a Stream Sliding Window, Proceedings of the Fourth IEEE International Conference on Data Mining, p.59-66, November 01-04, 2004
• 29: Edith Cohen, Size-estimation framework with applications to transitive closure and reachability, Journal of Computer and System Sciences, v.55 n.3, p.441-453, Dec. 1997 [doi>10.1006/jcss.1997.1534]
• 30: Edith Cohen , Haim Kaplan, Summarizing data using bottom-k sketches, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA [doi>10.1145/1281100.1281133]
• 31: Graham Cormode , Mayur Datar , Piotr Indyk , S. Muthukrishnan, Comparing Data Streams Using Hamming Norms (How to Zero In), IEEE Transactions on Knowledge and Data Engineering, v.15 n.3, p.529-540, March 2003 [doi>10.1109/TKDE.2003.1198388]
• 32: Graham Cormode , S. Muthukrishnan , Irina Rozenbaum, Summarizing and mining inverse distributions on data streams via dynamic inverse sampling, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 33: Don Coppersmith , Ravi Kumar, An improved data stream algorithm for frequency moments, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 34: Abhinandan Das , Johannes Gehrke , Mirek Riedewald, Semantic Approximation of Data Stream Joins, IEEE Transactions on Knowledge and Data Engineering, v.17 n.1, p.44-59, January 2005 [doi>10.1109/TKDE.2005.17]
• 35: Anirban Dasgupta , Petros Drineas , Boulos Harb , Ravi Kumar , Michael W. Mahoney, Sampling algorithms and coresets for ℓ_p regression, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.932-941, January 20-22, 2008, San Francisco, California
• 36: Mayur Datar , Aristides Gionis , Piotr Indyk , Rajeev Motwani, Maintaining stream statistics over sliding windows: (extended abstract), Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.635-644, January 06-08, 2002, San Francisco, California
• 37: Mayur Datar , S. Muthukrishnan, Estimating Rarity and Similarity over Data Stream Windows, Proceedings of the 10th Annual European Symposium on Algorithms, p.323-334, September 17-21, 2002
• 38: Nick Duffield , Carsten Lund , Mikkel Thorup, Flow sampling under hard resource constraints, ACM SIGMETRICS Performance Evaluation Review, v.32 n.1, June 2004
• 39: J. Feigenbaum, S. Kannan, and J. Zhang, "Computing diameter in the streaming and sliding-window models", Algorithmica, 41:25--41, 2005.
• 40: Joan Feigenbaum , Sampath Kannan , Andrew McGregor , Siddharth Suri , Jian Zhang, Graph distances in the streaming model: the value of space, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 41: Joan Feigenbaum , Sampath Kannan , Andrew McGregor , Siddharth Suri , Jian Zhang, On graph problems in a semi-streaming model, Theoretical Computer Science, v.348 n.2, p.207-216, 8 December 2005 [doi>10.1016/j.tcs.2005.09.013]
• 42: J. Feigenbaum, S. Kannan, M. Strauss, M. Viswanathan, "Testing and Spot-Checking of Data Streams", Algorithmica, 34(1): 67--80, 2002.
• 43: Gereon Frahling , Piotr Indyk , Christian Sohler, Sampling in dynamic data streams and applications, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy [doi>10.1145/1064092.1064116]
• 44: S. Ganguly. "Estimating Frequency Moments of Update Streams using Random Linear Combinations". Proceedings of the 8th International Workshop on Randomized Algorithms, pp. 369--380, 2004.
• 45: Sumit Ganguly, Counting distinct items over update streams, Theoretical Computer Science, v.378 n.3, p.211-222, June, 2007 [doi>10.1016/j.tcs.2007.02.031]
• 46: Sorabh Gandhi , Subhash Suri , Emo Welzl, Catching elephants with mice: sparse sampling for monitoring sensor networks, Proceedings of the 5th international conference on Embedded networked sensor systems, November 06-09, 2007, Sydney, Australia [doi>10.1145/1322263.1322289]
• 47: R. Gemulla, "Sampling Algorithms for Evolving Datasets", PhD Dissertation.
• 48: Rainer Gemulla , Wolfgang Lehner, Sampling time-based sliding windows in bounded space, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376657]
• 49: Phillip B. Gibbons , Yossi Matias, New sampling-based summary statistics for improving approximate query answers, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.331-342, June 01-04, 1998, Seattle, Washington, United States
• 50: Phillip B. Gibbons , Srikanta Tirthapura, Distributed streams algorithms for sliding windows, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada [doi>10.1145/564870.564880]
• 51: Lukasz Golab , David DeHaan , Erik D. Demaine , Alejandro Lopez-Ortiz , J. Ian Munro, Identifying frequent items in sliding windows over on-line packet streams, Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement, October 27-29, 2003, Miami Beach, FL, USA [doi>10.1145/948205.948227]
• 52: Lukasz Golab , M Tamer Özsu, Processing sliding window multi-joins in continuous queries over data streams, Proceedings of the 29th international conference on Very large data bases, p.500-511, September 09-12, 2003, Berlin, Germany
• 53: Sudipto Guha , Andrew McGregor , Suresh Venkatasubramanian, Streaming and sublinear approximation of entropy and information distances, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.733-742, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109637]
• 54: Sudipto Guha , Adam Meyerson , Nina Mishra , Rajeev Motwani , Liadan O'Callaghan, Clustering Data Streams: Theory and Practice, IEEE Transactions on Knowledge and Data Engineering, v.15 n.3, p.515-528, March 2003 [doi>10.1109/TKDE.2003.1198387]
• 55: P.J. Haas, "Data stream sampling: Basic techniques and results", In M. Garofalakis, J. Gehrke, and R. Rastogi (Eds.), Data Stream Management: Processing High Speed Data Streams, Springer.
• 56: Nicholas J. A. Harvey , Jelani Nelson , Krzysztof Onak, Sketching and Streaming Entropy via Approximation Theory, Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science, p.489-498, October 25-28, 2008 [doi>10.1109/FOCS.2008.76]
• 57: Piotr Indyk , David Woodruff, Optimal approximations of the frequency moments of data streams, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060621]
• 58: H. Jowhari, M. Ghodsi, "New streaming algorithms for counting triangles in graphs", Proceedings of the 11th COCOON, pp. 710--716, 2005.
• 59: M. Kolonko , D. Wäsch, Sequential reservoir sampling with a nonuniform distribution, ACM Transactions on Mathematical Software (TOMS), v.32 n.2, p.257-273, June 2006 [doi>10.1145/1141885.1141891]
• 60: L. K. Lee , H. F. Ting, A simpler and more efficient deterministic scheme for finding frequent items over sliding windows, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA [doi>10.1145/1142351.1142393]
• 61: L. K. Lee , H. F. Ting, Maintaining significant stream statistics over sliding windows, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.724-732, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109636]
• 62: Kim-Hung Li, Reservoir-sampling algorithms of time complexity O(n(1 + log(N/n))), ACM Transactions on Mathematical Software (TOMS), v.20 n.4, p.481-493, Dec. 1994 [doi>10.1145/198429.198435]
• 63: Jin Li , David Maier , Kristin Tufte , Vassilis Papadimos , Peter A. Tucker, Semantics and evaluation techniques for window aggregates in data streams, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066193]
• 64: Jin Li , David Maier , Kristin Tufte , Vassilis Papadimos , Peter A. Tucker, No pane, no gain: efficient evaluation of sliding-window aggregates over data streams, ACM SIGMOD Record, v.34 n.1, March 2005 [doi>10.1145/1058150.1058158]
• 65: Gurmeet Singh Manku , Rajeev Motwani, Approximate frequency counts over data streams, Proceedings of the 28th international conference on Very Large Data Bases, p.346-357, August 20-23, 2002, Hong Kong, China
• 66: S. Muthukrishnan, Data streams: algorithms and applications, Foundations and Trends® in Theoretical Computer Science, v.1 n.2, p.117-236, August 2005 [doi>10.1561/0400000002]
• 67: Christopher R. Palmer , Christos Faloutsos, Density biased sampling: an improved method for data mining and clustering, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.82-92, May 15-18, 2000, Dallas, Texas, United States
• 68: V. Paxson , G. Almes , J. Mahdavi , M. Mathis, Framework for IP Performance Metrics, RFC Editor, 1998
• 69: C. Procopiuc, O. Procopiuc, "Density Estimation for Spatial Data Streams", Proceedings of the 9th International Symposium on Spatial and Temporal Databases, pp.109--126, 2005.
• 70: Mario Szegedy, The DLT priority sampling is essentially optimal, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132539]
• 71: Nesime Tatbul , Stan Zdonik, Window-aware load shedding for aggregation queries over data streams, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 72: Jeffrey S. Vitter, Random sampling with a reservoir, ACM Transactions on Mathematical Software (TOMS), v.11 n.1, p.37-57, March 1985 [doi>10.1145/3147.3165]
• 73: L. Zhang, Z. Li, M. Yu, Y. Wang, Y. Jiang, "Random sampling algorithms for sliding windows over data streams", Proc. of the 11th Joint International Computer Conference, pp. 572--575, 2005.
• 74: Haiquan (Chuck) Zhao , Ashwin Lall , Mitsunori Ogihara , Oliver Spatscheck , Jia Wang , Jun Xu, A data streaming algorithm for estimating entropies of od flows, Proceedings of the 7th ACM SIGCOMM conference on Internet measurement, October 24-26, 2007, San Diego, California, USA [doi>10.1145/1298306.1298345]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.m Miscellaneous

General Terms:
Algorithms, Theory

Keywords:
data streams, random sampling, sliding windows