Mining significant time intervals for relationship detection

Zhenhui Li, Cindy Xide Lin, Bolin Ding, Jiawei Han

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


Spatio-temporal data collected from GPS have become an important resource to study the relationships of moving objects. While previous studies focus on mining objects being together for a long time, discovering real-world relationships, such as friends or colleagues in human trajectory data, is a fundamentally different challenge. For example, it is possible that two individuals are friends but do not spend a lot of time being together every day. However, spending just one or two hours together at a location away from work on a Saturday night could be a strong indicator of friend relationship. Based on the above observations, in this paper we aim to analyze and detect semantically meaningful relationships in a supervised way. That is, with an interested relationship in mind, a user can label some object pairs with and without such relationship. From labeled pairs, we will learn what time intervals are the most important ones in order to characterize this relationship. These significant time intervals, namely T-Motifs, are then used to discover relationships hidden in the unlabeled moving object pairs. While the search for T-Motifs could be time-consuming, we design two speed-up strategies to efficiently extract T-Motifs. We use both real and synthetic datasets to demonstrate the effectiveness and efficiency of our method.

Original languageEnglish (US)
Title of host publicationAdvances in Spatial and Temporal Databases - 12th International Symposium, SSTD 2011, Proceedings
Number of pages18
StatePublished - 2011
Event12th International Symposium on Advances in Spatial and Temporal Databases, SSTD 2011 - Minneapolis, MN, United States
Duration: Aug 24 2011Aug 26 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6849 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other12th International Symposium on Advances in Spatial and Temporal Databases, SSTD 2011
Country/TerritoryUnited States
CityMinneapolis, MN

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Mining significant time intervals for relationship detection'. Together they form a unique fingerprint.

Cite this