Location-aware publish/subscribe

Guoliang Li, Yang Wang, Ting Wang, Jianhua FengKDD 2013 · DOI

TL;DR

This paper introduces a novel location-aware publish/subscribe system designed for mobile devices, moving beyond traditional pull-based models to a more efficient push-based approach. They propose a new R-tree based index structure (Rt-tree and its variants) that integrates textual descriptions into spatial indexing, enabling significantly faster filtering of messages to relevant subscribers.

What Problem Does This Paper Address?

The proliferation of location-based services (LBS) on mobile devices has created a demand for more responsive and proactive information delivery. Existing LBS often rely on a "pull" model, where users explicitly query for information. However, for next-generation LBS, a "push" model is becoming essential, where users subscribe to interests (spatio-textual subscriptions), and the system proactively pushes relevant messages from publishers. This shift presents a significant challenge: building a high-performance system that can efficiently match millions of subscriptions with incoming messages, considering both their spatial proximity and textual content, and delivering results in milliseconds. The core problem is the computational cost of filtering these spatio-textual messages against a massive number of subscriptions.

Methods

The paper proposes a series of R-tree based index structures to tackle the spatio-textual filtering problem:

  • Rt-tree: This is the foundational index structure. It extends the standard R-tree by integrating textual descriptions directly into R-tree nodes. Each node stores a "TokenSet" representing the union of tokens from subscriptions within its subtree. This allows for an initial "token filter" in addition to the standard MBR (spatial) filter.
  • Rt+-tree: To further improve pruning efficiency and reduce index size, the Rt+-tree uses "representative tokens." Instead of storing all tokens, each subscription is assigned a single representative token, and each node stores a set of these representative tokens. This significantly reduces the size of the token sets within nodes, leading to better pruning.
  • Rt++-tree: This advanced variant uses multiple representative tokens per subscription, strategically assigned to different levels of the tree. This allows for more granular filtering and avoids redundant checks. It also introduces inverted lists for each representative token at each node, enabling a filter-and-verification-free approach where answers are directly identified.

The filtering process generally follows a "filter-and-verification" framework, where candidate nodes are identified using spatial (MBR) and textual (token) filters, and then subscriptions within those candidate leaf nodes are verified. The Rt++-tree aims to eliminate the verification step altogether. The paper also explores different strategies for selecting representative tokens (random, df-based, idf-based, and locality-aware) to maximize pruning power.

Datasets

The paper uses two primary datasets for evaluation:

  • Twitter Dataset: A real-world dataset derived from 60 million tweets, with 13 million having location information. 10 million tweets with region information were used as subscriptions, and the rest as messages. Subscriptions had 1-5 tokens and an MBR.
  • Synthetic Dataset: This dataset combines Points of Interest (POIs) from the USA (17 million) and publications from DBLP (1.5 million). MBRs were generated from POIs, and subscriptions were created using these MBRs and DBLP tokens.

The paper also mentions generating four groups of messages for each dataset: short/long point messages and short/long range messages, varying in token count and location type.

Key Insights and Ideas

  • Push Model Necessity: The paper strongly advocates for the push model in next-generation LBS, highlighting its potential for instant replies and improved user experience over traditional pull models.
  • Integrating Text and Space: The core innovation is the effective integration of textual information directly into spatial indexing structures (R-trees). This allows for simultaneous pruning based on both location and content, which is crucial for efficiency.
  • Representative Tokens for Pruning: The idea of using representative tokens (Rt+-tree) and multiple representative tokens (Rt++-tree) is a key insight. By strategically selecting tokens, the system can achieve much higher pruning rates, significantly reducing the search space.
  • Filter-and-Verification-Free: The Rt++-tree's ability to directly identify answers without a separate verification step is a significant performance improvement.
  • Token Selection Matters: The choice of how to select representative tokens (e.g., idf-based or locality-aware) has a substantial impact on pruning efficiency and overall performance.

Key Results

  • High Performance: The proposed Rt++-tree method demonstrates significantly higher performance compared to baseline methods (keyword-first, spatial-first) and a state-of-the-art spatial keyword search method (IRTree).
  • Scalability: The Rt++-tree scales well with an increasing number of subscriptions, showing sublinear increases in elapsed time.
  • Efficiency Gains: For example, on long range messages with 1000 tokens, the Rt++-tree reduced filtering time to 12 milliseconds, compared to 50 ms for the basic R-tree and 28 ms for the Rt+-tree. For short messages (tweets), it achieved filtering in 1-2 milliseconds.
  • Index Size Reduction: The Rt+-tree and Rt++-tree variants offer substantial reductions in index size compared to the basic Rt-tree, due to the use of representative tokens.

Limitations and Future Work

  • Textual Constraint: The paper primarily focuses on conjunctive textual semantics (all tokens must match). While they mention supporting disjunctive semantics by decomposing subscriptions, this adds complexity.
  • Future Work: The authors suggest exploring range queries (e.g., price between X and Y) and ranking queries (finding top-k subscriptions based on similarity) in future work, which would require extensions to their current model. They also mention the potential for further optimization by considering locality-aware token distributions.

Summary updated

BibTeX
@inproceedings{li2013location,
  author = {Guoliang Li and Yang Wang and Ting Wang and Jianhua Feng},
  title = {{Location-aware publish/subscribe}},
  booktitle = {ACM SIGKDD Conference on Knowledge Discovery and Data Mining},
  year = {2013},
  doi = {10.1145/2487575.2487617},
}
Figure