21
Views
0
CrossRef citations to date
0
Altmetric
Award Papers

Efficient Pattern Matching over Uncertain Data Streams

&
Pages 10-19 | Received 02 Apr 2009, Accepted 05 Aug 2009, Published online: 09 Apr 2013
 

Abstract

Query processing in the streaming and uncertain environment is crucial in many real applications such as sensor data monitoring, location-based services, and online multimedia data analysis. Compared with query answering on ‘certain’ and static data, uncertain data are often modelled to reside in uncertainty regions (rather than at precise points) following arbitrary distributions; moreover, stream processing has its own constraints including the limited processing power and memory. Thus, previous techniques on precise and static data cannot be directly applied to our scenario. Inspired by this, in this paper, we formulate and tackle the problem of answering a very useful query type, range queries, on uncertain data streams (called URS). Specifically, we formalise URS queries in uncertain streams, which guarantees the query accuracy, and present effective pruning methods to filter out false alarms. Most importantly, observing the fact that URS processing cost increases with higher dimensionality (aka ‘dimensionality curse’ problem), we propose a novel methodology, namely UDR, to reduce the dimensionality of uncertain data (instead of precise points) and efficiently answer URS queries in high-dimensional spaces, which has practical applications such as video data analysis. We conduct extensive experiments to demonstrate the efficiency and effectiveness of our approaches under various settings.

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.