Browse Prior Art Database

A System & Method for Determining Similarity between Spatio-Temporal Behavior of Users

IP.com Disclosure Number: IPCOM000245212D
Publication Date: 2016-Feb-18
Document File: 5 page(s) / 203K

Publishing Venue

The IP.com Prior Art Database

Abstract

Given a compact representation (signature) that captures hangouts and movement patterns of each user distinctly, our proposed system can determine top-K users for a given user by using a novel Similarity model to compare spatio-temporal behavior. The system presents features such as pruning for rapid discovery, and visualization of the similarity model for intuitive understanding of similarity between a pair of users.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 40% of the total text.

Page 01 of 5

A System & Method for Determining Similarity between Spatio -Temporal Behavior of Users

Problem: Existing techniques for processing spatio-temporal data do not provide a technique to compare spatio-temporal signatures, or to visualize the similarity model between two signatures.

Proposal: Given a compact representation (signature) that captures hangouts and movement

patterns of each user distinctly, our proposed system can determine top-K users for a given user by using a novel Similarity model to compare spatio-temporal behavior. The proposed system also provides a method for visualizing the similarity model to intuitively understand the similarity between two users.

Known Solutions & Their Drawbacks: Existing works in this domain can be classified and differentiated from our proposed system as follows:

1. Dynamic Time Warping (DTW) [Park et al. ICDE 00]
 Capable of only computing the spatial distance. Ignores temporal distance.

2. Longest Common Sub-sequence (LCSS)[Vlachos et al. ICDE 02]
 Assumes uniform sampling rate. Requires spatial and temporal thresholds which are hard to determine.

3. Edit Distance with Real Penalty (ERP) [Chen et al. VLDB 04]
 Capable of only computing the spatial distance. Ignores temporal distance. Requires spatial threshold which is hard to determine. Assumes Uniform Sampling Rate.

4. Edit Distance on Real Sequence (EDR) [Chen et al. SIGMOD 05]
 Capable of only computing the spatial distance. Ignores temporal distance. Requires spatial threshold which is hard to determine.

5. DISSIM [Frentzos et al. ICDE 07]
 Cannot handle non-uniform time shifting. As a result, cannot compare identical trajectories originating on different days.

Summary of Method:

Method Idea:

Input


- A large set (N) of users


- For each user, spatio-temporal data (GPS traces, CDR records, etc.) collected over time that represents his/her behavior in terms of movement patterns and hangouts

Output


- For a given user (U), top-K users most similar to U is determined based on the collected spatio-temporal data

Novelty

- Similarity model to compare spatio-temporal behavior: Given two users U and U', spatio-temporal similarity is determined that accounts for both hangout information as well as movement patterns

1


Page 02 of 5


- Centroid-based Pruning: Given that N is a very large number (e.g., Vodafone has 200 million users), a novel pruning strategy is proposed that significantly reduces the number of users to be compared to U


- Similarity Visualization: Instead of just giving a list of top-K users and/or just showing the similarity as a number, a visualization which shows which hangouts and/or movement patterns are similar between users leads to a more intuitive understanding of similarity and can be used for further analytics

Contributions:


Some of the contributions of this proposal are -

A similarity framework for comparing users based on their spatio-temporal behavior (this includes similarity captured across hangouts as wel...