Paper Info
Title
Continuous query processing in data streams using duality of data and queries
Abstract
Recent data stream systems such as TelegraphCQ have employed the well-known property of duality between data and queries. In these systems, query processing methods are classified into two dual categories -- data-initiative and query-initiative -- depending on whether query processing is initiated by selecting a data element or a query. Although the duality property has been widely recognized, previous data stream systems do not fully take advantages of this property since they use the two dual methods independently: data-initiative methods only for continuous queries and query-initiative methods only for ad-hoc queries. We contend that continuous query processing can be better optimized by adopting an approach that integrates the two dual methods. Our primary contribution is based on the observation that spatial join is a powerful tool for achieving this objective. In this paper, we first present a new viewpoint of transforming the continuous query processing problem to a multi-dimensional spatial join problem. We then present a continuous query processing algorithm based on spatial join, which we name Spatial Join CQ. This algorithm processes continuous queries by finding the pairs of overlapping regions from a set of data elements and a set of queries, both defined as regions in the multi-dimensional space. The algorithm achieves the advantages of the two dual methods simultaneously. Experimental results show that the proposed algorithm outperforms earlier algorithms by up to 36 times for simple selection continuous queries and by up to 7 times for sliding window join queries.
Year
DOI
Venue
2006
10.1145/1142473.1142509
SIGMOD Conference
Keywords
Field
DocType
continuous query processing problem,continuous query,ad-hoc query,data element,dual method,query processing method,continuous query processing algorithm,continuous query processing,query processing,previous data stream system,data streams,duality,batch processing,sliding window,batch process
Query optimization,Data mining,Data stream mining,Sliding window protocol,Data stream,Computer science,Data element,Web query classification,Theoretical computer science,Duality (optimization),Spatial query,Database
Conference
ISBN
Citations 
PageRank 
1-59593-434-0
26
0.90
References 
Authors
21
5
Name
Order
Citations
PageRank
Hyo-Sang Lim119512.50
Jae-Gil Lee2129174.15
Minjae Lee356595.62
Kyu-Young Whang42282716.85
Il-Yeol Song52041301.54