Abstract
We study the well-known frequent items problem in data streams from a competitive analysis point of view. We consider the standard worst-case input model, as well as a weaker distributional adversarial setting. We are primarily interested in the single-slot memory case and for both models we give (asymptotically) tight bounds of \(\varTheta(\sqrt{N})\) and \(\varTheta(\sqrt[3]{N})\) respectively, achieved by very simple and natural algorithms, where N is the stream’s length. We also provide lower bounds, for both models, in the more general case of arbitrary memory sizes of k ≥ 1.
This work has been partially supported by the ESF-NSRF research program Thales (ALGONOW). The first author acknowledges the support of Propondis Foundation.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aggarwal, C.: Data Streams: Models and Algorithms. Advances in Database Systems. Springer (2007)
Alon, N., Matias, Y., Szegedy, M.: The Space Complexity of Approximating the Frequency Moments. Journal of Computer and System Sciences 58(1), 137–147 (1999)
Babaioff, M., Immorlica, N., Kempe, D., Kleinberg, R.: Online auctions and generalized secretary problems. ACM SIGecom Exchanges 7(2), 1–11 (2008)
Becchetti, L., Chatzigiannakis, I., Giannakopoulos, Y.: Streaming techniques and data aggregation in networks of tiny artefacts. Computer Science Review 5(1), 27–46 (2011)
Becchetti, L., Koutsoupias, E.: Competitive Analysis of Aggregate Max in Windowed Streaming. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009, Part I. LNCS, vol. 5555, pp. 156–170. Springer, Heidelberg (2009)
Borodin, A., El-Yaniv, R.: Online Computation and Competitive Analysis. Cambridge University Press (1998)
Boyer, R.S., Moore, J.S.: MJRTY-A Fast Majority Vote Algorithm. Technical report, Texas University at Austin, Insitute for Computing Science and Computer Applications (1981)
Cormode, G., Hadjieleftheriou, M.: Finding frequent items in data streams. Proceedings of the VLDB Endowment 1(2), 1530–1541 (2008)
Datar, M., Gionis, A., Indyk, P., Motwani, R.: Maintaining stream statistics over sliding windows. SIAM Journal on Computing, 635–644 (2002)
Ferguson, T.S.: Who solved the secretary problem? Statistical Science 4(3), 282–296 (1989)
Fiat, A., Woeginger, G.J. (eds.): Online Algorithms 1996. LNCS, vol. 1442. Springer, Heidelberg (1998)
Gama, J., Geber, M.M. (eds.): Learning from Data Streams: Processing Techniques in Sensor Networks. Springer (2007)
Liu, L., Tamer Ozsu, M. (eds.): Encyclopedia of Database Systems. Springer (2009)
Misra, J., Gries, D.: Finding repeated elements. Science of Computer Programming 2(2), 143–152 (1982)
Mitzenmacher, M., Upfal, E.: Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press (2005)
Munro, J.I., Paterson, M.S.: Selection and sorting with limited storage. In: Proceedings of FOCS 1978, pp. 253–258 (1978)
Muthukrishnan, S.: Data streams: Algorithms and applications. Now Publishers Inc. (2005)
Yao, A.C.-C.: Probabilistic computations: Toward a unified measure of complexity. In: Proceedings of FOCS 1977, pp. 222–227 (1977)
Yi, K., Zhang, Q.: Multidimensional online tracking. ACM Trans. Algorithms 8(2), 12:1–12:16 (2012)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Giannakopoulos, Y., Koutsoupias, E. (2012). Competitive Analysis of Maintaining Frequent Items of a Stream. In: Fomin, F.V., Kaski, P. (eds) Algorithm Theory – SWAT 2012. SWAT 2012. Lecture Notes in Computer Science, vol 7357. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-31155-0_30
Download citation
DOI: https://doi.org/10.1007/978-3-642-31155-0_30
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-31154-3
Online ISBN: 978-3-642-31155-0
eBook Packages: Computer ScienceComputer Science (R0)