TY - JOUR
T1 - Efficient process of top-k range-sum queries over multiple streams with minimized global error
AU - Hung, Hao Ping
AU - Chuang, Kun Ta
AU - Chen, Ming Syan
N1 - Funding Information:
The work was supported in part by the National Science Council of Taiwan, ROC, under Contracts NSC93-2752-E-002-006-PAE.
PY - 2007/10
Y1 - 2007/10
N2 - Due to the resource limitation in the data stream environments, it has been reported that answering user queries according to the wavelet synopsis of a stream is an essential ability of a Data Stream Management System (DSMS). In the literature, recent research has been elaborated upon minimizing the local error metric of an individual stream. However, many emergent applications such as stock marketing and sensor detection also call for the need of recording multiple streams in a commercial DSMS. As shown In our thorough analysis and experimental studies, minimizing global error in multiple-stream environments leads to good reliability for DSMS to answer the queries. In contrast, only minimizing local error may lead to a significant loss of query accuracy. As such, we first study in this paper the problem of maintaining the wavelet coefficients of multiple streams within collective memory so that the predetermined global error metric Is minimized. Moreover, we also examine a promising application In the multistream environment, that is, the queries for top-k range sum. We resolve the problem of efficient top-k query processing with minimized global error by developing a general framework. For the purposes of maintaining the wavelet coefficients and processing top-k queries, several well-designed algorithms are utilized to optimize the performance of each primary component of this general framework. We also evaluate the proposed algorithms empirically on real and simulated data streams and show that our framework can process top-k queries accurately and efficiently.
AB - Due to the resource limitation in the data stream environments, it has been reported that answering user queries according to the wavelet synopsis of a stream is an essential ability of a Data Stream Management System (DSMS). In the literature, recent research has been elaborated upon minimizing the local error metric of an individual stream. However, many emergent applications such as stock marketing and sensor detection also call for the need of recording multiple streams in a commercial DSMS. As shown In our thorough analysis and experimental studies, minimizing global error in multiple-stream environments leads to good reliability for DSMS to answer the queries. In contrast, only minimizing local error may lead to a significant loss of query accuracy. As such, we first study in this paper the problem of maintaining the wavelet coefficients of multiple streams within collective memory so that the predetermined global error metric Is minimized. Moreover, we also examine a promising application In the multistream environment, that is, the queries for top-k range sum. We resolve the problem of efficient top-k query processing with minimized global error by developing a general framework. For the purposes of maintaining the wavelet coefficients and processing top-k queries, several well-designed algorithms are utilized to optimize the performance of each primary component of this general framework. We also evaluate the proposed algorithms empirically on real and simulated data streams and show that our framework can process top-k queries accurately and efficiently.
UR - http://www.scopus.com/inward/record.url?scp=34648857559&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=34648857559&partnerID=8YFLogxK
U2 - 10.1109/TKDE.2007.1070
DO - 10.1109/TKDE.2007.1070
M3 - Article
AN - SCOPUS:34648857559
SN - 1041-4347
VL - 19
SP - 1404
EP - 1419
JO - IEEE Transactions on Knowledge and Data Engineering
JF - IEEE Transactions on Knowledge and Data Engineering
IS - 10
ER -