doi: 10.4304/jsw.8.1.19-24
Estimation of the Number of Distinct Values over Data Stream Based on Compound Sliding Window
Abstract—Estimating the number of distinct values in a data stream is a vital problem with many applications such as complex join query over multiple data streams. In this paper, we focus on the continuous and periodic distinct values estimation over sliding windows. We propose a compound sliding window model to compute the distinct values over basic sliding windows in an incremental way. LDV, HDV and AHDV are the three algorithms that are based on compound sliding windows. The basic idea behind the compound sliding windows is to organize the basic windows into a Hash table according to distinct values. Whenever a new data arrives at the data stream, it is inserted into a basic window. Once the basic window is full, a scan using distinct values is executed and the distinct values number is updated incrementally. Theoretical analysis and experiment results show that the distinct values estimation algorithms based on compound sliding windows have a great performance benefits.
Index Terms—Data stream, basic window, compound sliding window, distinct values estimation.
Cite: Yingli Zhong, Jinghua Zhu, Meirui Ren, Yan Yang, "Estimation of the Number of Distinct Values over Data Stream Based on Compound Sliding Window," Journal of Software vol. 8, no. 1, pp. 19-24, 2013.
General Information
ISSN: 1796-217X (Online)
Abbreviated Title: J. Softw.
Frequency: Quarterly
APC: 500USD
DOI: 10.17706/JSW
Editor-in-Chief: Prof. Antanas Verikas
Executive Editor: Ms. Cecilia Xie
Abstracting/ Indexing: DBLP, EBSCO,
CNKI, Google Scholar, ProQuest,
INSPEC(IET), ULRICH's Periodicals
Directory, WorldCat, etcE-mail: jsweditorialoffice@gmail.com
-
Oct 22, 2024 News!
Vol 19, No 3 has been published with online version [Click]
-
Jan 04, 2024 News!
JSW will adopt Article-by-Article Work Flow
-
Apr 01, 2024 News!
Vol 14, No 4- Vol 14, No 12 has been indexed by IET-(Inspec) [Click]
-
Apr 01, 2024 News!
Papers published in JSW Vol 18, No 1- Vol 18, No 6 have been indexed by DBLP [Click]
-
Jun 12, 2024 News!
Vol 19, No 2 has been published with online version [Click]