Spatio-Temporal Signatures of User-Centric Data: How Similar Are We?

Samta Shukla, Aditya Telang, Salil Joshi, L. Venkata SubramaniamAAAI 2015 · DOI

Abstract

Finding similar movement patterns in massive GPS datasets is computationally expensive due to the unstructured and noisy nature of raw location data. This paper proposes "Spatio-Temporal Signatures" (ST-Signatures)—directed weighted graphs representing user mobility—and a hybrid pruning scheme. This approach enables efficient similarity searches in logarithmic time while maintaining near-optimal accuracy, facilitating applications in security and targeted marketing.

Introduction

As location-tracking devices become ubiquitous, we are generating unprecedented volumes of human mobility data. Security agencies may need to identify "potential suspects" who frequent the same locations as a known individual, while marketers seek to target groups with identical commuting patterns. However, raw GPS traces are unstructured and noisy. Comparing one person's movements against millions of others using a brute-force approach takes $O(NT)$ time (where $N$ is the number of users and $T$ is the number of time steps), which is computationally prohibitive. This research addresses the challenge of making these similarity searches both accurate and fast enough for real-world applications.

Methodology: ST-Signatures and Pruning

The authors introduce a two-part framework to structure and search mobility data efficiently.

1. ST-Signatures

Instead of a linear list of coordinates, a user’s history is transformed into a directed weighted graph called an ST-Signature. In this model, nodes represent "hangouts" (discretized spatial locations like cell towers), and edges represent movement between them. Metadata attached to the graph stores the frequency and duration of visits at specific timestamps.

Transformation of raw CDR traces into a structured ST-Signature graph.

2. Hybrid Pruning Scheme

To avoid exhaustive comparisons, the framework employs a two-step filter:

  • Lossless Pruning: A "Master Signature" tracks which users were at specific locations at specific times. This global index allows the system to immediately discard any user who never crossed paths with the query subject.
  • Lossy Pruning: For the remaining candidates, data is compressed into "Time-Buckets" (e.g., 4-hour windows). User behavior is represented as a probability distribution in a $d$-dimensional space ($d \approx 20$), and a k-d tree data structure is used to find nearest neighbors in logarithmic time.
The Master Signature structure used for lossless pruning, mapping nodes and edges to timestamps and user indices.

Insights and Datasets

The framework leverages the inherent predictability of human movement. We exhibit "spatial regularity," tending to visit the same types of places at consistent times. This regularity allows for the compression of complex movement into 20-dimensional vectors without losing the "essence" of a user's behavior. The model was tested against real-world urban mobility data, specifically a dataset of GPS users in Beijing, justifying the assumption that human movement is structured enough for graph-based representation.

Key Results and Discussion

The hybrid pruning scheme significantly reduces search complexity. The lossless step alone reduces the search space from $O(NT)$ to $O(QT)$, where $Q$ (the number of locations a specific user visits) is typically much smaller than the total population $N$. By combining this with k-d trees, search time becomes logarithmic ($\log N$). Crucially, the authors demonstrate that this approximation stays within a $(1 + \epsilon)$ factor of the mathematically optimal result, ensuring speed gains do not compromise accuracy.

Limitations

While effective, the system assumes relatively complete records. Real-world GPS data is often fragmented due to signal loss or device failure, and the framework's robustness to significant data gaps requires further study. Additionally, the ability to efficiently identify "location doppelgängers" raises substantial privacy concerns regarding the potential for deanonymization and tracking, which must be addressed in production environments.

Summary updated

BibTeX
@inproceedings{shukla2015spatio,
  author = {Samta Shukla and Aditya Telang and Salil Joshi and L. Venkata Subramaniam},
  title = {{Spatio-Temporal Signatures of User-Centric Data: How Similar Are We?}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2015},
  doi = {10.1609/aaai.v29i1.9712},
}
Figure