File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Filtering data streams for entity-based continuous queries

TitleFiltering data streams for entity-based continuous queries
Authors
KeywordsAdaptive filters
Continuous queries
Data streams
Fraction-based tolerance
Issue Date2010
PublisherIEEE. 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?
AbstractThe 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 Identifierhttp://hdl.handle.net/10722/65445
ISSN
2015 Impact Factor: 2.476
2015 SCImago Journal Rankings: 2.087
ISI Accession Number ID
Funding AgencyGrant Number
Research Grants Council of Hong Kong513508
513307
Germany/HK Joint Research SchemeG_HK013/06
University of Hong Kong200808159002
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 FieldValueLanguage
dc.contributor.authorCheng, Ren_HK
dc.contributor.authorKao, Ben_HK
dc.contributor.authorKwan, Aen_HK
dc.contributor.authorPrabhakar, Sen_HK
dc.contributor.authorTu, Yen_HK
dc.date.accessioned2010-08-06T03:22:22Z-
dc.date.available2010-08-06T03:22:22Z-
dc.date.issued2010en_HK
dc.identifier.citationIEEE Transactions On Knowledge And Data Engineering, 2010, v. 22 n. 2, p. 234-248en_HK
dc.identifier.issn1041-4347en_HK
dc.identifier.urihttp://hdl.handle.net/10722/65445-
dc.description.abstractThe 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.languageeng-
dc.publisherIEEE. The Journal's web site is located at http://www.computer.org/tkdeen_HK
dc.relation.ispartofIEEE Transactions on Knowledge and Data Engineeringen_HK
dc.rights©2010 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.rightsCreative Commons: Attribution 3.0 Hong Kong License-
dc.subjectAdaptive filtersen_HK
dc.subjectContinuous queriesen_HK
dc.subjectData streamsen_HK
dc.subjectFraction-based toleranceen_HK
dc.titleFiltering data streams for entity-based continuous queriesen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://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.emailCheng, R:ckcheng@cs.hku.hken_HK
dc.identifier.emailKao, B:kao@cs.hku.hken_HK
dc.identifier.authorityCheng, R=rp00074en_HK
dc.identifier.authorityKao, B=rp00123en_HK
dc.description.naturepublished_or_final_version-
dc.identifier.doi10.1109/TKDE.2009.63en_HK
dc.identifier.scopuseid_2-s2.0-75449092263en_HK
dc.identifier.hkuros162398-
dc.identifier.hkuros171744-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-75449092263&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume22en_HK
dc.identifier.issue2en_HK
dc.identifier.spage234en_HK
dc.identifier.epage248en_HK
dc.identifier.isiWOS:000272838500006-
dc.publisher.placeUnited Statesen_HK
dc.relation.projectEfficient Protocols for Quality-Aware Querying of Sensor Data in Pervasive Environments-
dc.identifier.scopusauthoridCheng, R=7201955416en_HK
dc.identifier.scopusauthoridKao, B=35221592600en_HK
dc.identifier.scopusauthoridKwan, A=14028804500en_HK
dc.identifier.scopusauthoridPrabhakar, S=7101672592en_HK
dc.identifier.scopusauthoridTu, Y=7201525630en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats