The Frequent Items Problem in Online Streaming Under Various Performance Measures

被引：11

作者：

Boyar, Joan ^{[1
]}

Larsen, Kim S. ^{[1
]}

Maiti, Abyayananda ^{[1
]}

机构：

[1] Univ Southern Denmark, Dept Math & Comp Sci, DK-5230 Odense M, Denmark

来源：

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE | 2015年 / 26卷 / 04期

关键词：

Online algorithms; streaming algorithms; performance measures; ALGORITHMS;

D O I：

10.1142/S0129054115500239

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

This is a contribution to the ongoing study of properties of perform nose 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 streaming problem.

引用

页码：413 / 439

页数：27

共 12 条

[1]

Becchetti L, 2009, LECT NOTES COMPUT SC, V5555, P156, DOI 10.1007/978-3-642-02927-1_15

[2]

Berinde R., 2009, 28 ACM SIGMOD SIGACT, P157

[3]

Boyar J., 2007, ACM T ALGORITHMS, V3

[4] The relative worst-order ratio applied to paging [J].

Boyar, Joan ;

Favrholdt, Lene M. ;

Larsen, Kim S. .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2007, 73 (05) :818-843

[5] A comparison of performance measures via online search [J].

Boyar, Joan ;

Larsen, Kim S. ;

Maiti, Abyayananda .

THEORETICAL COMPUTER SCIENCE, 2014, 532 :2-13

[6]

Boyar J, 2009, LECT NOTES COMPUT SC, V5664, P119, DOI 10.1007/978-3-642-03367-4_11

[7] Maintaining time-decaying stream aggregates [J].

Cohen, E ;

Strauss, MJ .

JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 2006, 59 (01) :19-36

[8] Finding Frequent Items in Data Streams [J].

Cormode, Graham ;

Hadjieleftheriou, Marios .

PROCEEDINGS OF THE VLDB ENDOWMENT, 2008, 1 (02) :1530-1541

[9] On the relative dominance of paging algorithms [J].

Dorrigiv, Reza ;

Lopez-Ortiz, Alejandro ;

Munro, J. Ian .

THEORETICAL COMPUTER SCIENCE, 2009, 410 (38-40) :3694-3701

[10]

Giannakopoulos Y., 2012, LECT NOTES COMPUTER, P340

← 1 2 →