Maintaining stream statistics over multiscale sliding windows

	Maintaining stream statistics over multiscale sliding windows
	Jiao, Yishan
	2006-12-01
发表期刊	ACM TRANSACTIONS ON DATABASE SYSTEMS
ISSN	0362-5915
卷号	31 期号:4 页码:1305-1334
摘要	In this article, we propose a new multiscale sliding window model which differentiates data items in different time periods of the data stream, based on a reasonable monotonicity of resolution assumption. Our model, as a well-motivated extension of the sliding window model, stands halfway between the traditional all-history and time-decaying models. We also present algorithms for estimating two significant data stream statistics - F-0 and Jacard's similarity coefficient - with reasonable accuracies under the new model. Our algorithms use space logarithmic in the data stream size and linear in the number of windows; they support update time logarithmic in the number of windows and independent of the accuracy required. Our algorithms are easy to implement. Experimental results demonstrate the efficiencies of our algorithms. Our techniques apply to scenarios in which universe sampling is used.
关键词	algorithms performance data stream F-0 Jacard's similarity coefficient multiscale sliding window model
收录类别	SCI
语种	英语
WOS研究方向	Computer Science
WOS类目	Computer Science, Information Systems ; Computer Science, Software Engineering
WOS记录号	WOS:000243396000004
出版者	ASSOC COMPUTING MACHINERY
引用统计	被引频次：3[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/10634
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Jiao, Yishan
作者单位	Chinese Acad Sci, Inst Comp Technol, Div Intelligent Software Syst, Computat Biol Res Grp, Beijing, Peoples R China
推荐引用方式 GB/T 7714	Jiao, Yishan. Maintaining stream statistics over multiscale sliding windows[J]. ACM TRANSACTIONS ON DATABASE SYSTEMS,2006,31(4):1305-1334.
APA	Jiao, Yishan.(2006).Maintaining stream statistics over multiscale sliding windows.ACM TRANSACTIONS ON DATABASE SYSTEMS,31(4),1305-1334.
MLA	Jiao, Yishan."Maintaining stream statistics over multiscale sliding windows".ACM TRANSACTIONS ON DATABASE SYSTEMS 31.4(2006):1305-1334.