TY - CONF
T1 - MAGIC: A Multi-Activity Graph Index for Activity Detection
T2 - Information Reuse and Integration, 2007. IRI 2007. IEEE International Conference on
Y1 - 2007
A1 - Albanese, M.
A1 - Pugliese, A.
A1 - V.S. Subrahmanian
A1 - Udrea,O.
KW - complexity;graph
KW - detection;complexity
KW - graph
KW - index;probability
KW - MAGIC;activity
KW - reducing
KW - restrictions;exponential
KW - theory;probability;
KW - threshold;computational
KW - time;multiactivity
AB - 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 epsi A and O' sube 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.
JA - Information Reuse and Integration, 2007. IRI 2007. IEEE International Conference on
M3 - 10.1109/IRI.2007.4296632
ER -