AN EFFICIENT ALGORITHM TO COMPUTE MAX/MIN VALUES IN SLIDING WINDOW FOR DATA STREAMS

Ying Sha, Jianlong Tan

2007

Abstract

With the development of Internet, more and more data-stream based applications emerged, where calculation of aggregate functions plays an important role. Many studies were conducted on aggregation functions; however, an efficient algorithm to calculate Max/Min values remains an open problem. Here, we propose a novel, exact method to computer Max/Min values for the numerical input data. Employing an incrementally calculating strategy on sliding windows, this algorithm gains a high efficiency. We analyze the algorithm and prove the time-complexity and space-complexity in worst cases. Experimental results confirm its high performance on a testing dataset.

Paper Citation

in Harvard Style

Sha Y. and Tan J. (2007). AN EFFICIENT ALGORITHM TO COMPUTE MAX/MIN VALUES IN SLIDING WINDOW FOR DATA STREAMS . In Proceedings of the Second International Conference on Software and Data Technologies - Volume 3: ICSOFT, ISBN 978-989-8111-07-4, pages 123-128. DOI: 10.5220/0001338101230128

in Bibtex Style

@conference{icsoft07,
author={Ying Sha and Jianlong Tan},
title={AN EFFICIENT ALGORITHM TO COMPUTE MAX/MIN VALUES IN SLIDING WINDOW FOR DATA STREAMS},
booktitle={Proceedings of the Second International Conference on Software and Data Technologies - Volume 3: ICSOFT,},
year={2007},
pages={123-128},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0001338101230128},
isbn={978-989-8111-07-4},
}

in EndNote Style

TY - CONF
JO - Proceedings of the Second International Conference on Software and Data Technologies - Volume 3: ICSOFT,
TI - AN EFFICIENT ALGORITHM TO COMPUTE MAX/MIN VALUES IN SLIDING WINDOW FOR DATA STREAMS
SN - 978-989-8111-07-4
AU - Sha Y.
AU - Tan J.
PY - 2007
SP - 123
EP - 128
DO - 10.5220/0001338101230128