Event queries on correlated probabilistic streams

ABSTRACT

A major problem in detecting events in streams of data is that the data can be imprecise (e.g. RFID data). However, current state-ofthe-art event detection systems such as Cayuga [14], SASE [46] or SnoopIB[1], assume the data is precise. Noise in the data can be captured using techniques such as hidden Markov models. Inference on these models creates streams of probabilistic events which cannot be directly queried by existing systems. To address this challenge we propose Lahar1, an event processing system for probabilistic event streams. By exploiting the probabilistic nature of the data, Lahar yields a much higher recall and precision than deterministic techniques operating over only the most probable tuples. By using a novel static analysis and novel algorithms, Lahar processes data orders of magnitude more efficiently than a naïve approach based on sampling. In this paper, we present Lahar's static analysis and core algorithms. We demonstrate the quality and performance of our approach through experiments with our prototype implementation and comparisons with alternate methods.

REFERENCES

• 1: Raman Adaikkalavan , Sharma Chakravarthy, SnoopIB: interval-based event specification and detection for active databases, Data & Knowledge Engineering, v.59 n.1, p.139-165, October 2006 [doi>10.1016/j.datak.2005.07.009]
• 2: S. Arulampalam, S. Maskell, N. Gordon, and T. Clapp. A tutorial on particle filters for on-line non-linear/non-gaussian bayesian tracking. IEEE Transactions on Signal Processing, 50(2):174--188, February 2002.
• 3: Omar Benjelloun , Anish Das Sarma , Alon Halevy , Jennifer Widom, ULDBs: databases with uncertainty and lineage, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 4: C. Floerkemeier and M. Lampe. Issues with RFID usage in ubiquitous computing applications. In Proc. of the 2nd Pervasive Conf., April 2004.
• 5: Cisco Systems. Cisco IOS NetFlow. http://www.cisco.com/go/netflow.
• 6: Computerworld. Procter & Gamble: Wal-Mart RFID effort effective. http://www.computerworld.com/action/article.do?command=viewArticleBasic%&articleId=284160, February 2007.
• 7: Graham Cormode , Minos Garofalakis, Sketching probabilistic data streams, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247513]
• 8: Robert G. Cowell , Steffen L. Lauritzen , A. Philip David , David J. Spiegelhalter , V. Nair , J. Lawless , M. Jordan, Probabilistic Networks and Expert Systems, Springer-Verlag New York, Inc., Secaucus, NJ, 1999
• 9: Nilesh Dalvi , Dan Suciu, Efficient query evaluation on probabilistic databases, Proceedings of the Thirtieth international conference on Very large data bases, p.864-875, August 31-September 03, 2004, Toronto, Canada
• 10: Nilesh Dalvi , Dan Suciu, The dichotomy of conjunctive queries on probabilistic structures, Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 11-13, 2007, Beijing, China [doi>10.1145/1265530.1265571]
• 11: Dartmouth College. CRAWDAD: A Community Resource for Archiving Wireless Data At Dartmouth. http://crawdad.cs.dartmouth.edu/index.php.
• 12: Das, S.K. et al. The role of prediction algorithms in the MavHome smart home architecture. IEEE Wireless Communications, 9(6):77--84, 2002.
• 13: Alex Dekhtyar , Robert Ross , V. S. Subrahmanian, Probabilistic temporal databases, I: algebra, ACM Transactions on Database Systems (TODS), v.26 n.1, p.41-95, March 2001 [doi>10.1145/383734.383736]
• 14: A.J. Demers, J. Gehrke, M. Hong, M. Riedewald, and W.M. White. Towards expressive publish/subscribe systems. In EDBT, pages 627--644, 2006.
• 15: Norbert Fuhr , Thomas Rölleke, A probabilistic relational algebra for the integration of information retrieval and database systems, ACM Transactions on Information Systems (TOIS), v.15 n.1, p.32-66, Jan. 1997 [doi>10.1145/239041.239045]
• 16: M. Garofalakis , R. Rastogi , K. Shim, Mining Sequential Patterns with Regular Expression Constraints, IEEE Transactions on Knowledge and Data Engineering, v.14 n.3, p.530-552, May 2002 [doi>10.1109/TKDE.2002.1000341]
• 17: Garofalakis et. al. Probabilistic data management for pervasive computing: The Data Furnace project. IEEE Data Engineering Bulletin, 29(1), March 2006.
• 18: T. S. Jayram , Satyen Kale , Erik Vee, Efficient aggregation algorithms for probabilistic data, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.346-355, January 07-09, 2007, New Orleans, Louisiana
• 19: T. S. Jayram , Andrew McGregor , S. Muthukrishnan , Erik Vee, Estimating statistical aggregates on probabilistic data streams, Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 11-13, 2007, Beijing, China [doi>10.1145/1265530.1265565]
• 20: Shawn R. Jeffery , Minos Garofalakis , Michael J. Franklin, Adaptive cleaning for RFID data streams, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 21: Daniel Jobst , Gerald Preissler, Mapping clouds of SOA- and business-related events for an enterprise cockpit in a Java-based environment, Proceedings of the 4th international symposium on Principles and practice of programming in Java, August 30-September 01, 2006, Mannheim, Germany [doi>10.1145/1168054.1168089]
• 22: B. Kanagal and A. Deshpande. Online filtering, smoothing and probabilistic modeling of streaming data. Technical Report CS-TR-4867, University of Maryland, May 2007.
• 23: Nodira Khoussainova , Magdalena Balazinska , Dan Suciu, Towards correcting input data errors probabilistically using integrity constraints, Proceedings of the 5th ACM international workshop on Data engineering for wireless and mobile access, June 25-25, 2006, Chicago, Illinois, USA [doi>10.1145/1140104.1140114]
• 24: Mike Klaas , Mark Briers , Nando de Freitas , Arnaud Doucet , Simon Maskell , Dustin Lang, Fast particle smoothing: if I had a million particles, Proceedings of the 23rd international conference on Machine learning, p.481-488, June 25-29, 2006, Pittsburgh, Pennsylvania [doi>10.1145/1143844.1143905]
• 25: M. Lamming and D. Bohm. SPECs: Another approach to human context and activity sensing research, using tiny peer-to-peer wireless computers. In Ubicomp 2003, volume 2864, pages 192--199, 2003.
• 26: S. E. Levinson, L. R. Rabiner, and M. M. Sondhi. An introduction to the application of the theory of probabilistic functions of a Markov process to automatic speech recognition. Bell Sys. Tech. J., 62:1035, 1983.
• 27: Lin Liao , Donald J. Patterson , Dieter Fox , Henry Kautz, Learning and inferring transportation routines, Artificial Intelligence, v.171 n.5-6, p.311-331, April, 2007 [doi>10.1016/j.artint.2007.01.006]
• 28: Joseph F. McCarthy , Theodore D. Anagnost, EVENTMANAGER: Support for the Peripheral Awareness of Events, Proceedings of the 2nd international symposium on Handheld and Ubiquitous Computing, p.227-235, September 25-27, 2000, Bristol, UK
• 29: Gerome Miklau , Dan Suciu, A formal analysis of information disclosure in data exchange, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007633]
• 30: Michael Mitzenmacher , Eli Upfal, Probability and Computing: Randomized Algorithms and Probabilistic Analysis, Cambridge University Press, New York, NY, 2005
• 31: Judea Pearl, Probabilistic reasoning in intelligent systems: networks of plausible inference, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 32: Matthai Philipose , Kenneth P. Fishkin , Mike Perkowitz , Donald J. Patterson , Dieter Fox , Henry Kautz , Dirk Hahnel, Inferring Activities from Interactions with Objects, IEEE Pervasive Computing, v.3 n.4, p.50-57, October 2004 [doi>10.1109/MPRV.2004.7]
• 33: J. S. Provan and M. O. Ball. The complexity of counting cuts and of computing the probability that a graph is connected. SIAM J. Comput., 12(4):777--788, 1983.
• 34: Lawrence R. Rabiner, A tutorial on hidden Markov models and selected applications in speech recognition, Readings in speech recognition, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1990
• 35: C. Ré, J. Letchner, M. Balazinska, and D. Suciu. Event queries on correlated probabilistic streams (full version). Technical Report 08-03-02, University of Washington, Seattle, WA, 2008.
• 36: Christopher Ré , Dan Suciu, Materialized views in probabilistic databases: for information exchange and query optimization, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 37: Reuters. Stock Data Feed. http://about.reuters.com/productinfo/s/stock_data_feed/.
• 38: RFID Journal. Hospital gets ultra-wideband RFID. http://www.rfidjournal.com/article/view/1088/1/1, August 2004.
• 39: Crossbow Technology. Products: Wireless sensor networks. http://www.xbow.com/Products/wproductsoverview.aspx.
• 40: University of Washington. RFID Ecosystem. http://rfid.cs.washington.edu/.
• 41: G. Virone, A. Wood, L. Selavo, Q. Cao, L. Fang, T. Doan, Z. He, R. Stoleru, S. Lin, and J.A. Stankovic. An assisted living oriented information system based on a residential wireless sensor network. In 1st Distributed Diagnosis and Home Healthcare (D2H2) Conference, April 2006.
• 42: A. J. Viterbi. Error bounds for convolutional codes and an asymptotically optimum decoding algorithm. IEEE Transactions on Information Theory, IT-13:260--269, 1967.
• 43: Fusheng Wang , Peiya Liu, Temporal management of RFID data, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 44: Evan Welbourne , Magdalena Balazinska , Gaetano Borriello , Waylon Brunette, Challenges for Pervasive RFID-Based Infrastructures, Proceedings of the Fifth IEEE International Conference on Pervasive Computing and Communications Workshops, p.388-394, March 19-23, 2007 [doi>10.1109/PERCOMW.2007.26]
• 45: Walker White , Mirek Riedewald , Johannes Gehrke , Alan Demers, What is "next" in event processing?, Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 11-13, 2007, Beijing, China [doi>10.1145/1265530.1265567]
• 46: Eugene Wu , Yanlei Diao , Shariq Rizvi, High-performance complex event processing over streams, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142520]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS

General Terms:
Algorithms, Management, Performance, Theory

Keywords:
hidden markov models, probabilistic databases, query processing, streams