Discovering non-compliant window co-occurrence patterns

A summary of results

Reem Y. Ali, Venkata M.V. Gunturi, Andrew J. Kotz, Shashi Shekhar, William Northrop

Research output: Contribution to journalConference article

5 Citations (Scopus)

Abstract

Given a set of trajectories annotated with measurements of physical variables, the problem of Non-compliant Window Co-occurrence (NWC) pattern discovery aims to determine temporal signatures in the explanatory variables which are highly associated with windows of undesirable behavior in a target variable. NWC discovery is important for societal applications such as eco-friendly transportation (e.g. identifying engine signatures leading to high greenhouse gas emissions). Challenges of designing a scalable algorithm for NWC discovery include the non monotonicity of popular spatio-temporal statistical interest measures of association such as the cross-K function. This challenge renders the anti-monotone pruning based algorithms (e.g. Apriori) inapplicable. To address this limitation, we propose two novel upper bounds for the cross- K function which help in filtering uninteresting candidate patterns. Using these bounds, we also propose a Multi-Parent Tracking approach (MTNMiner) for mining NWC patterns. A case study with real world engine data demonstrates the ability of the proposed approach to discover patterns which are interesting to engine scientists. Experimental evaluation on real-world data show that MTNMiner results in substantial computational savings over the naive approach.

Original languageEnglish (US)
Pages (from-to)391-410
Number of pages20
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9239
DOIs
StatePublished - Jan 1 2015
Event14th International on Symposium on Spatial and Temporal Databases, SSTD 2015 - Hong Kong, China
Duration: Aug 26 2015Aug 28 2015

Fingerprint

Engines
Engine
Gas emissions
Greenhouse gases
Signature
Apriori Algorithm
Measures of Association
Pattern Discovery
Trajectories
Greenhouse Gases
Pruning
Experimental Evaluation
Monotonicity
Mining
Monotone
Filtering
Trajectory
Upper bound
Target
Demonstrate

Cite this

@article{6dcce4590785491caf4bcb49bd3d35dd,
title = "Discovering non-compliant window co-occurrence patterns: A summary of results",
abstract = "Given a set of trajectories annotated with measurements of physical variables, the problem of Non-compliant Window Co-occurrence (NWC) pattern discovery aims to determine temporal signatures in the explanatory variables which are highly associated with windows of undesirable behavior in a target variable. NWC discovery is important for societal applications such as eco-friendly transportation (e.g. identifying engine signatures leading to high greenhouse gas emissions). Challenges of designing a scalable algorithm for NWC discovery include the non monotonicity of popular spatio-temporal statistical interest measures of association such as the cross-K function. This challenge renders the anti-monotone pruning based algorithms (e.g. Apriori) inapplicable. To address this limitation, we propose two novel upper bounds for the cross- K function which help in filtering uninteresting candidate patterns. Using these bounds, we also propose a Multi-Parent Tracking approach (MTNMiner) for mining NWC patterns. A case study with real world engine data demonstrates the ability of the proposed approach to discover patterns which are interesting to engine scientists. Experimental evaluation on real-world data show that MTNMiner results in substantial computational savings over the naive approach.",
author = "Ali, {Reem Y.} and Gunturi, {Venkata M.V.} and Kotz, {Andrew J.} and Shashi Shekhar and William Northrop",
year = "2015",
month = "1",
day = "1",
doi = "10.1007/978-3-319-22363-6_21",
language = "English (US)",
volume = "9239",
pages = "391--410",
journal = "Lecture Notes in Computer Science",
issn = "0302-9743",
publisher = "Springer Verlag",

}

TY - JOUR

T1 - Discovering non-compliant window co-occurrence patterns

T2 - A summary of results

AU - Ali, Reem Y.

AU - Gunturi, Venkata M.V.

AU - Kotz, Andrew J.

AU - Shekhar, Shashi

AU - Northrop, William

PY - 2015/1/1

Y1 - 2015/1/1

N2 - Given a set of trajectories annotated with measurements of physical variables, the problem of Non-compliant Window Co-occurrence (NWC) pattern discovery aims to determine temporal signatures in the explanatory variables which are highly associated with windows of undesirable behavior in a target variable. NWC discovery is important for societal applications such as eco-friendly transportation (e.g. identifying engine signatures leading to high greenhouse gas emissions). Challenges of designing a scalable algorithm for NWC discovery include the non monotonicity of popular spatio-temporal statistical interest measures of association such as the cross-K function. This challenge renders the anti-monotone pruning based algorithms (e.g. Apriori) inapplicable. To address this limitation, we propose two novel upper bounds for the cross- K function which help in filtering uninteresting candidate patterns. Using these bounds, we also propose a Multi-Parent Tracking approach (MTNMiner) for mining NWC patterns. A case study with real world engine data demonstrates the ability of the proposed approach to discover patterns which are interesting to engine scientists. Experimental evaluation on real-world data show that MTNMiner results in substantial computational savings over the naive approach.

AB - Given a set of trajectories annotated with measurements of physical variables, the problem of Non-compliant Window Co-occurrence (NWC) pattern discovery aims to determine temporal signatures in the explanatory variables which are highly associated with windows of undesirable behavior in a target variable. NWC discovery is important for societal applications such as eco-friendly transportation (e.g. identifying engine signatures leading to high greenhouse gas emissions). Challenges of designing a scalable algorithm for NWC discovery include the non monotonicity of popular spatio-temporal statistical interest measures of association such as the cross-K function. This challenge renders the anti-monotone pruning based algorithms (e.g. Apriori) inapplicable. To address this limitation, we propose two novel upper bounds for the cross- K function which help in filtering uninteresting candidate patterns. Using these bounds, we also propose a Multi-Parent Tracking approach (MTNMiner) for mining NWC patterns. A case study with real world engine data demonstrates the ability of the proposed approach to discover patterns which are interesting to engine scientists. Experimental evaluation on real-world data show that MTNMiner results in substantial computational savings over the naive approach.

UR - http://www.scopus.com/inward/record.url?scp=84984639964&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84984639964&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-22363-6_21

DO - 10.1007/978-3-319-22363-6_21

M3 - Conference article

VL - 9239

SP - 391

EP - 410

JO - Lecture Notes in Computer Science

JF - Lecture Notes in Computer Science

SN - 0302-9743

ER -