File Download
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1109/TKDE.2009.63
- Scopus: eid_2-s2.0-75449092263
- WOS: WOS:000272838500006
- Find via
Supplementary
- Citations:
- Appears in Collections:
Article: Filtering data streams for entity-based continuous queries
Title | Filtering data streams for entity-based continuous queries | ||||||||
---|---|---|---|---|---|---|---|---|---|
Authors | |||||||||
Keywords | Adaptive filters Continuous queries Data streams Fraction-based tolerance | ||||||||
Issue Date | 2010 | ||||||||
Publisher | IEEE. The Journal's web site is located at http://www.computer.org/tkde | ||||||||
Citation | IEEE Transactions On Knowledge And Data Engineering, 2010, v. 22 n. 2, p. 234-248 How to Cite? | ||||||||
Abstract | The idea of allowing query users to relax their correctness requirements in order to improve performance of a data stream management system (e.g., location-based services and sensor networks) has been recently studied. By exploiting the maximum error (or tolerance) allowed in query answers, algorithms for reducing the use of system resources have been developed. In most of these works, however, query tolerance is expressed as a numerical value, which may be difficult to specify. We observe that in many situations, users may not be concerned with the actual value of an answer, but rather which object satisfies a query (e.g., "who is my nearest neighbor?). In particular, an entity-based query returns only the names of objects that satisfy the query. For these queries, it is possible to specify a tolerance that is "nonvalue-based. In this paper, we study fraction-based tolerance, a type of nonvalue-based tolerance, where a user specifies the maximum fractions of a query answer that can be false positives and false negatives. We develop fraction-based tolerance for two major classes of entity-based queries: 1) nonrank-based query (e.g., range queries) and 2) rank-based query (e.g., k-nearest-neighbor queries). These definitions provide users with an alternative to specify the maximum tolerance allowed in their answers. We further investigate how these definitions can be exploited in a distributed stream environment. We design adaptive filter algorithms that allow updates be dropped conditionally at the data stream sources without affecting the overall query correctness. Extensive experimental results show that our protocols reduce the use of network and energy resources significantly. © 2006 IEEE. | ||||||||
Persistent Identifier | http://hdl.handle.net/10722/65445 | ||||||||
ISSN | 2023 Impact Factor: 8.9 2023 SCImago Journal Rankings: 2.867 | ||||||||
ISI Accession Number ID |
Funding Information: This work was supported by the Research Grants Council of Hong Kong (GRF Projects 513508 and 513307), the Germany/HK Joint Research Scheme (Project G_HK013/06), and the University of Hong Kong (Project 200808159002). The authors thank the reviewers for their insightful comments. | ||||||||
References | |||||||||
Grants |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Cheng, R | en_HK |
dc.contributor.author | Kao, B | en_HK |
dc.contributor.author | Kwan, A | en_HK |
dc.contributor.author | Prabhakar, S | en_HK |
dc.contributor.author | Tu, Y | en_HK |
dc.date.accessioned | 2010-08-06T03:22:22Z | - |
dc.date.available | 2010-08-06T03:22:22Z | - |
dc.date.issued | 2010 | en_HK |
dc.identifier.citation | IEEE Transactions On Knowledge And Data Engineering, 2010, v. 22 n. 2, p. 234-248 | en_HK |
dc.identifier.issn | 1041-4347 | en_HK |
dc.identifier.uri | http://hdl.handle.net/10722/65445 | - |
dc.description.abstract | The idea of allowing query users to relax their correctness requirements in order to improve performance of a data stream management system (e.g., location-based services and sensor networks) has been recently studied. By exploiting the maximum error (or tolerance) allowed in query answers, algorithms for reducing the use of system resources have been developed. In most of these works, however, query tolerance is expressed as a numerical value, which may be difficult to specify. We observe that in many situations, users may not be concerned with the actual value of an answer, but rather which object satisfies a query (e.g., "who is my nearest neighbor?). In particular, an entity-based query returns only the names of objects that satisfy the query. For these queries, it is possible to specify a tolerance that is "nonvalue-based. In this paper, we study fraction-based tolerance, a type of nonvalue-based tolerance, where a user specifies the maximum fractions of a query answer that can be false positives and false negatives. We develop fraction-based tolerance for two major classes of entity-based queries: 1) nonrank-based query (e.g., range queries) and 2) rank-based query (e.g., k-nearest-neighbor queries). These definitions provide users with an alternative to specify the maximum tolerance allowed in their answers. We further investigate how these definitions can be exploited in a distributed stream environment. We design adaptive filter algorithms that allow updates be dropped conditionally at the data stream sources without affecting the overall query correctness. Extensive experimental results show that our protocols reduce the use of network and energy resources significantly. © 2006 IEEE. | en_HK |
dc.language | eng | - |
dc.publisher | IEEE. The Journal's web site is located at http://www.computer.org/tkde | en_HK |
dc.relation.ispartof | IEEE Transactions on Knowledge and Data Engineering | en_HK |
dc.rights | ©2009 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE. | - |
dc.subject | Adaptive filters | en_HK |
dc.subject | Continuous queries | en_HK |
dc.subject | Data streams | en_HK |
dc.subject | Fraction-based tolerance | en_HK |
dc.title | Filtering data streams for entity-based continuous queries | en_HK |
dc.type | Article | en_HK |
dc.identifier.openurl | http://library.hku.hk:4550/resserv?sid=HKU:IR&issn=1041-4347&volume=22&issue=2&spage=234&epage=248&date=2010&atitle=Filtering+data+streams+for+entity-based+continuous+queries | - |
dc.identifier.email | Cheng, R:ckcheng@cs.hku.hk | en_HK |
dc.identifier.email | Kao, B:kao@cs.hku.hk | en_HK |
dc.identifier.authority | Cheng, R=rp00074 | en_HK |
dc.identifier.authority | Kao, B=rp00123 | en_HK |
dc.description.nature | published_or_final_version | - |
dc.identifier.doi | 10.1109/TKDE.2009.63 | en_HK |
dc.identifier.scopus | eid_2-s2.0-75449092263 | en_HK |
dc.identifier.hkuros | 162398 | - |
dc.identifier.hkuros | 171744 | - |
dc.relation.references | http://www.scopus.com/mlt/select.url?eid=2-s2.0-75449092263&selection=ref&src=s&origin=recordpage | en_HK |
dc.identifier.volume | 22 | en_HK |
dc.identifier.issue | 2 | en_HK |
dc.identifier.spage | 234 | en_HK |
dc.identifier.epage | 248 | en_HK |
dc.identifier.isi | WOS:000272838500006 | - |
dc.publisher.place | United States | en_HK |
dc.relation.project | Efficient Protocols for Quality-Aware Querying of Sensor Data in Pervasive Environments | - |
dc.identifier.scopusauthorid | Cheng, R=7201955416 | en_HK |
dc.identifier.scopusauthorid | Kao, B=35221592600 | en_HK |
dc.identifier.scopusauthorid | Kwan, A=14028804500 | en_HK |
dc.identifier.scopusauthorid | Prabhakar, S=7101672592 | en_HK |
dc.identifier.scopusauthorid | Tu, Y=7201525630 | en_HK |
dc.identifier.issnl | 1041-4347 | - |