The Frequent Items Problem in Online Streaming Under Various Performance Measures

DOI10.1142/S0129054115500239MaRDI QIDQ2947799zbMATHFDO

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)

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

zbMATH Keywords

online algorithmsperformance measuresstreaming algorithms

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27)

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.

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

Cites work

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

Cited in

(13)

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