- The Frequent Items Problem in Online Streaming under Various Performance Measures.
- Joan Boyar, Kim S. Larsen, and Abyayananda Maiti.
International Journal of Foundations of Computer Science. Accepted for publication.
This is a contribution to the ongoing study of properties 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. More systematic comparative studies of
performance measures have been initiated recently, and we continue this work,
considering competitive analysis, relative interval analysis, and relative
worst order analysis on the frequent items problem, a fundamental online
open access (301 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.