The Frequent Items Problem in Online Streaming Under Various Performance Measures

DOI10.1142/S0129054115500239zbMATH Open1337.68297arXiv1306.0771MaRDI QIDQ2947799FDOQ2947799

Authors: Kim S. Larsen, Abyayananda Maiti, Joan Boyar 

Publication date: 29 September 2015

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Abstract: In this paper, we strengthen the competitive analysis results obtained for a fundamental online streaming problem, the Frequent Items Problem. Additionally, we contribute with a more detailed analysis of this problem, using alternative performance measures, supplementing the insight gained from competitive analysis. The results also contribute to the general study of performance measures for online algorithms. It has long been known that competitive analysis suffers from drawbacks in certain situations, and many alternative measures have been proposed. However, more systematic comparative studies of performance measures have been initiated recently, and we continue this work, using competitive analysis, relative interval analysis, and relative worst order analysis on the Frequent Items Problem.

Full work available at URL: https://arxiv.org/abs/1306.0771

Recommendations

• The frequent items problem in online streaming under various performance measures
• The frequent items problem, under polynomial decay, in the streaming model
• Approximating frequent items in asynchronous data stream over a sliding window
• Approximating frequent items in asynchronous data stream over a sliding window

zbMATH Keywords

online algorithmsperformance measuresstreaming algorithms

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27)

Cites Work

• Competitive snoopy caching
• A comparison of performance measures via online search
• The relative worst-order ratio applied to paging
• On the relative dominance of paging algorithms
• Maintaining time-decaying stream aggregates

Cited In (13)

• Quantum online streaming algorithms with logarithmic memory
• Relaxing the irrevocability requirement for online graph algorithms
• Competitive Analysis of Maintaining Frequent Items of a Stream
• The frequent items problem in online streaming under various performance measures
• Relative Worst-Order Analysis: A Survey
• Time efficient implementation for online \(k\)-server problem on trees
• Quantum versus classical online streaming algorithms with logarithmic size of memory
• Quantum algorithms for the most frequently string search, intersection of two string sequences and sorting of strings problems
• The frequent items problem, under polynomial decay, in the streaming model
• Quantum online algorithms with respect to space and advice complexity
• The fast algorithm for online \(k\)-server problem on trees
• Two-way and one-way quantum and classical automata with advice for online minimization problems
• Classical and Quantum Computations with Restricted Memory

This page was built for publication: The Frequent Items Problem in Online Streaming Under Various Performance Measures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2947799)