Efficient Pattern Matching over Uncertain Data Streams

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.

Keywords:

• Range Query
• Uncertain Data Streams
• URS
• Dimensionality Reduction on Uncertain Data
• UDR