- The Frequent Items Problem in Online Streaming under Various Performance Measures.
- Joan Boyar, Kim S. Larsen, and Abyayananda Maiti.
In 19th International Symposium on Fundamentals of Computation Theory (FCT), volume 8070 of Lecture Notes in Computer Science, pages 60-71. Springer, 2013.
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.
- Link to the publication at the publisher's site - subscription may be required.
Text required by the publisher (if any):
The final publication is available at link.springer.com.
Link to the journal version containing all the material and proofs, some of which are usually omitted in the conference version due to space constraints.
open access (163 KB)
The same as the publisher's version, when the publisher permits. Otherwise, the author's last version before the publisher's copyright; this is often exactly the same, but sometimes fonts, page numbers, figure numbers, etc. are different. It may also be a full version. However, it is safe to read this version, and at the same time cite the official version, as long as references to concrete locations, numbered theorems, etc. inside the article are avoided.
Other publications by the author.