Fast activity detection: Indexing for temporal stochastic automaton-based activity models

Massimiliano Albanese*, Andrea Pugliese, V. S. Subrahmanian

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

31 Scopus citations

Abstract

Today, numerous applications require the ability to monitor a continuous stream of fine-grained data for the occurrence of certain high-level activities. A number of computerized systems-including ATM networks, web servers, and intrusion detection systems-systematically track every atomic action we perform, thus generating massive streams of timestamped observation data, possibly from multiple concurrent activities. In this paper, we address the problem of efficiently detecting occurrences of high-level activities from such interleaved data streams. A solution to this important problem would greatly benefit a broad range of applications, including fraud detection, video surveillance, and cyber security. There has been extensive work in the last few years on modeling activities using probabilistic models. In this paper, we propose a temporal probabilistic graph so that the elapsed time between observations also plays a role in defining whether a sequence of observations constitutes an activity. We first propose a data structure called temporal multiactivity graph to store multiple activities that need to be concurrently monitored. We then define an index called Temporal Multiactivity Graph Index Creation (tMAGIC) that, based on this data structure, examines and links observations as they occur. We define algorithms for insertion and bulk insertion into the tMAGIC index and show that this can be efficiently accomplished. We also define algorithms to solve two problems: the evidence problem that tries to find all occurrences of an activity (with probability over a threshold) within a given sequence of observations, and the identification problem that tries to find the activity that best matches a sequence of observations. We introduce complexity reducing restrictions and pruning strategies to make the problem-which is intrinsically exponential-linear to the number of observations. Our experiments confirm that tMAGIC has time and space complexity linear to the size of the input, and can efficiently retrieve instances of the monitored activities.

Original languageEnglish (US)
Article number6095553
Pages (from-to)360-373
Number of pages14
JournalIEEE Transactions on Knowledge and Data Engineering
Volume25
Issue number2
DOIs
StatePublished - 2013
Externally publishedYes

Keywords

  • Activity detection
  • indexing
  • stochastic automata
  • timestamped data

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics

Fingerprint

Dive into the research topics of 'Fast activity detection: Indexing for temporal stochastic automaton-based activity models'. Together they form a unique fingerprint.

Cite this