Region-Based Message Exploration over Spatio-Temporal Data Streams

Lisi Chen, Shuo Shang

Introduction

Location-based social media platforms generate a continuous, massive stream of spatio-temporal data, such as geo-tagged tweets and Foursquare check-ins. Traditional methods for exploring this data often rely on "online spatial keyword search," which returns all individual items matching specific spatial and textual criteria. However, this item-based approach frequently leads to information overload, high redundancy (near-duplicate messages), and low-quality results due to spam or irrelevant content.

This paper proposes a shift from item-based search to a region-based exploration and summarization system. The goal is to match user interests to dynamic geographic clusters and provide a concise, diverse summary of events within those regions.

Overall system architecture for region-based message exploration, showing the pipeline from spatio-temporal messages to cluster summarization for users.

System Framework

The proposed framework consists of two primary technical components: a relevancy metric learning model to match users to message clusters, and a summarization algorithm to distill those clusters into representative feeds.

1. Relevancy Metric Learning via Triplet Network

To accurately match a user's "subscription region" to a dynamically generated "cluster region," the system must evaluate spatial and textual similarity. The authors employ a Convolutional Neural Network (CNN)-based Triplet Network (TN) to learn this metric.

Because labeled ground-truth data for region similarity is scarce, the system uses a self-supervised approach. As illustrated in the training data generation process, the model takes a reference region ($r$) and generates synthetic "positive" matches ($r^+$) by introducing noise—such as shifting locations or altering timestamps—while picking entirely different regions as "negative" matches ($r^-$).

The Triplet Network framework for learning region relevancy metrics through self-supervised training data generation and feature learning.

A key innovation in this model is the introduction of a normalized loss function. Spatial data is often highly skewed (e.g., city centers vs. suburbs); cardinality normalization ensures that the network does not allow dense regions to dominate the training process, treating a relevant region with few messages with the same importance as a dense one.

2. Region Summarization (GRS Algorithm)

Once a cluster is matched, the system must select $k$ messages that maximize "information coverage" while maintaining spatial and temporal diversity. The authors prove that this summarization task is NP-hard. To address this, they developed the GreedyRegionSummary (GRS) algorithm. GRS iteratively selects messages that provide the highest incremental information coverage. It utilizes an aggressive pruning strategy to filter redundant candidates, making the process computationally efficient enough for real-time data streams.

Experimental Evaluation

The system was evaluated using two large-scale datasets: FS (Foursquare), containing 1.2 million Points of Interest, and TT (Twitter), featuring 40 million geo-tagged tweets. Topic vectors were extracted using an Online Latent Dirichlet Allocation (OLDA) model.

Key Results

  • Metric Accuracy: The Triplet Network significantly outperformed baselines like SVSM and Spatial Pyramid (SP). In the presence of synthetic noise, TN's accuracy (top-k relevant ratio) remained robust, dropping only ~7-10%, while baselines saw performance decreases of up to 53%.
  • Summarization Quality: GRS consistently achieved higher information coverage scores than standard diversification algorithms (Max-Sum, Max-Min) across both datasets.
  • Efficiency: GRS proved to be at least an order of magnitude faster than competing algorithms, scaling to run in just a few milliseconds even as the number of requested summary messages increased.

Conclusion

By leveraging self-supervised deep metric learning and an efficient greedy summarization algorithm, this framework effectively addresses the challenges of information overload in spatio-temporal streams. The results demonstrate that cardinality normalization and incremental pruning are essential for building robust, real-time geographic exploration tools. Future work may involve exploring dynamic grid resolutions and integrating multimodal data, such as images, into the feature extraction process.

Summary updated

Abstract

Massive amount of spatio-temporal data that contain location and text content are being generated by location-based social media. These spatio-temporal messages cover a wide range of topics. It is of great significance to discover local trending topics based on users’ location-based and topicbased requirements. We develop a region-based message exploration mechanism that retrieve spatio-temporal message clusters from a stream of spatio-temporal messages based on users’ preferences on message topic and message spatial distribution. Additionally, we propose a region summarization algorithm that finds a subset of representative messages in a cluster to summarize the topics and the spatial attributes of messages in the cluster. We evaluate the efficacy and efficiency of our proposal on two real-world datasets and the results demonstrate that our solution is capable of high efficiency and effectiveness compared with baselines.
BibTeX
@inproceedings{chen2019region,
  author = {Lisi Chen and Shuo Shang},
  title = {{Region-Based Message Exploration over Spatio-Temporal Data Streams}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.3301873},
}
Figure