Access Methods for Markovian Streams
Authors:
- Julie LetchnerJLJulie Letchner
- Christopher ReCRChristopher Re
- Magdalena BalazinskaMBMagdalena Balazinska
- Matthai PhiliposeMPMatthai Philipose
- 1 March 2009
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10636382,p. 246-257
Abstract
Model-based views have recently been proposed as an effective method for querying noisy sensor data. Commonly used models from the AI literature (e.g., the hidden Markov model) expose to applications a stream of probabilistic and correlated state estimates computed from the sensor data. Many applications want to detect sophisticated patterns of states from these Markovian streams. Such queries are called event queries. In this paper, we present a new Markovian stream storage manager, Caldera. We develop and evaluate Caldera as a component of Lahar, a Markovian stream event query processing system developed in previous work. At the heart of Caldera is a set of access methods for Markovian streams that can improve event query performance by orders of magnitude compared to existing techniques, which must scan the entire stream. Our access methods use new adaptations of traditional B+ tree indexes, and a new index, called the Markov-chain index. They efficiently extract only the relevant timesteps from a stream, while retaining the stream's Markovian properties. We have implemented our prototype system on BDB and demonstrate its effectiveness on both synthetic data and real data from a building-wide RFID deployment.Keywords
This publication has 24 references indexed in Scilit:
- Architecture of RFID Spatio-Temporal Data ManagementAdvanced Materials Research, 2011
- Learning and inferring transportation routinesArtificial Intelligence, 2007
- OLAP over uncertain and imprecise dataThe VLDB Journal, 2006
- MauveDB2006
- Towards correcting input data errors probabilistically using integrity constraints2006
- Inferring Activities from Interactions with ObjectsIEEE Pervasive Computing, 2004
- Efficient Query evaluation on Probabilistic Databases2004
- A tutorial on particle filters for online nonlinear/non-Gaussian Bayesian trackingIEEE Transactions on Signal Processing, 2002
- Optimal aggregation algorithms for middleware2001
- Comparison of access methods for time-evolving dataACM Computing Surveys, 1999