MAGIC: A multi-activity graph index for activity detection

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

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Suppose we are given a set A of activities of interest, a set O of observations, and a probability threshold p. We are interested in finding the set of all pairs (a, O'), where a ∈ A and O' ⊆ O, that minimally validate the fact that an instance of activity a occurs in O with probability p or more. The novel contribution of this paper is the notion of the multi-activity graph index (MAGIC), which can index very large numbers of observations from interleaved activities and quickly retrieve completed instances of the monitored activities. We introduce two complexity reducing restrictions of the problem (which takes exponential time) and develop algorithms for each. We experimentally evaluate our exponential algorithm as well as the restricted algorithms on both synthetic data and a real (depersonalized) travel data set consisting of 5.5 million observations. Our experiments show that MAGIC consumes reasonable amounts of memory and can retrieve completed instances of activities in just a few seconds. We also report appropriate statistical significance results validating our experimental hypotheses.

Original languageEnglish (US)
Title of host publication2007 IEEE International Conference on Information Reuse and Integration, IEEE IRI-2007
Pages267-272
Number of pages6
DOIs
StatePublished - 2007
Externally publishedYes
Event2007 IEEE International Conference on Information Reuse and Integration, IEEE IRI-2007 - Las Vegas, NV, United States
Duration: Aug 13 2007Aug 15 2007

Publication series

Name2007 IEEE International Conference on Information Reuse and Integration, IEEE IRI-2007

Conference

Conference2007 IEEE International Conference on Information Reuse and Integration, IEEE IRI-2007
Country/TerritoryUnited States
CityLas Vegas, NV
Period8/13/078/15/07

ASJC Scopus subject areas

  • Information Systems
  • Information Systems and Management
  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'MAGIC: A multi-activity graph index for activity detection'. Together they form a unique fingerprint.

Cite this