Distributed Spatial-Keyword kNN Monitoring for Location-aware Pub/Sub

Shohei Tsuruoka, Daichi Amagata, Shunya Nishio, Takahiro HaraarXiv 2021 · arXiv

TL;DR

D$k$M-SKS is a distributed framework designed for real-time, continuous spatial-keyword $k$NN query monitoring over massive data streams. By combining spatial and keyword distributions into an intelligent hybrid cost model, it evenly balances the computational workload across multiple distributed workers. This approach achieves over a 10x speedup in update efficiency compared to state-of-the-art methods while scaling seamlessly to millions of subscriptions.

What Problem Does This Paper Address?

Location-aware publish/subscribe (Pub/Sub) systems are everywhere—from location-based social networks sending you alerts about nearby friends to apps notifying you of local restaurant deals. In these systems, users register "subscriptions" consisting of a location and a set of target keywords (e.g., "show me the nearest 2 Japanese noodle shops"). Meanwhile, a continuous stream of new "objects" (geo-tagged tweets, business check-ins) is generated by publishers.

The core challenge is continuous $k$ nearest neighbor ($k$NN) monitoring: the system must instantly update the top-$k$ relevant objects for millions of active subscriptions every time a new object arrives.

Doing this on a single server is a bottleneck. Scaling out to a distributed cluster seems like the obvious answer, but it introduces a major hurdle: load balancing. Subscriptions are highly unpredictable; some locations are incredibly dense, and certain keywords are vastly more popular than others. If you partition work naively, a few cluster nodes will get slammed with updates while others sit idle.

Figure 1: An example of 𝑘NN monitoring in a location- aware Pub/Sub system, where 𝑜𝑖and 𝑠𝑗respectively denote an spatial-keyword object and a subscription

Methods

The authors propose D$k$M-SKS (Distributed $k$NN Monitoring on Spatial-Keyword data Stream), which introduces a cost-based subscription partitioning pipeline:

  1. Dual-Aspect Cost Modeling: Instead of looking at just space or just keywords, D$k$M-SKS estimates the processing cost of a subscription by calculating the probability that a new streaming object will fall within its spatial $k$NN bounding region and match its keywords.
  2. Adaptive Partitioning (Space vs. Hybrid): The system recursively splits the subscription space. For each subset, it dynamically chooses between two strategies:
  3. Space-only-Partition: Splitting the region into equal quadtree-like quadrants.
  4. Hybrid-Partition: Using a greedy algorithm to group subscriptions based on shared keyword and spatial costs. The system automatically picks whichever method yields the lower total estimated workload.

  5. Greedy Worker Assignment: Subscriptions are distributed across $m$ workers such that each worker handles an approximately equal total cost, ensuring strict load balancing.

  6. Efficient New Subscription Handling: When a new user registers a query, the main server avoids an expensive global re-partitioning. Instead, it quickly identifies which existing spatial-keyword subset the new query aligns with most and routes it to the least-loaded worker.

Datasets

The framework was evaluated using two large-scale, real-world spatial-keyword stream datasets:

  • Place: 9,356,750 objects with 53,931 distinct keywords (representing point-of-interest data).
  • Twitter: 20,000,000 objects with 2,225,654 distinct keywords (representing highly dynamic social media streams).

Subscriptions were synthetically generated to match the underlying spatial and keyword distributions of these real-world datasets to ensure realistic experimental conditions.

Key Insights and Ideas

  • The Pitfalls of Single-Metric Partitioning: Purely spatial partitioning fails when a dense geographic area contains highly diverse keyword requests. Conversely, keyword-only partitioning creates massive bottlenecks when a trending keyword causes a single worker node to handle a disproportionate amount of the stream.
  • Bounding Boxes as Workload Proxies: A key "aha moment" is that a subscription's current $k$NN spatial boundary serves as an excellent proxy for its future update risk. If a subscription already has $k$ very close neighbors, its bounding circle is tiny, meaning the probability of a new object landing inside it and forcing an update is low.

Key Results

The authors compared D$k$M-SKS against $PS^2Stream$ (a state-of-the-art spatial-keyword range query processing method adapted for $k$NN) alongside pure keyword-oriented (KOP) and space-oriented (SOP) baselines.

  • 10x Processing Speedup: D$k$M-SKS consistently executed $k$NN updates more than 10 times faster than competing methods.
  • Near-Perfect Load Balancing: On the Place dataset, the workload imbalance (the time delta between the fastest and slowest worker) was a mere 32.08 ms for D$k$M-SKS, compared to a staggering 27,490.11 ms for $PS^2Stream$ and 14,037.33 ms for SOP.
  • Linear Scalability: As the number of subscriptions scaled up to 10 million, D$k$M-SKS's update time grew linearly, proving its readiness for production-scale deployment.

Limitations and Future Work

The primary limitation of D$k$M-SKS is its reliance on an initial dataset ($O_{init}$) to build its keyword and spatial distribution profiles. The cost model assumes that these distributions remain relatively stable over time.

If the data stream experiences extreme concept drift—such as a sudden localized emergency causing an unexpected spike in specific geographic coordinates and unique keywords—the initial cost mappings will degrade. The authors note that developing an online, dynamic re-partitioning mechanism to handle severe stream drift without interrupting real-time monitoring is a vital direction for future research.

Summary updated

Abstract

Recent applications employ publish/subscribe (Pub/Sub) systems so that publishers can easily receive attentions of customers and subscribers can monitor useful information generated by publishers. Due to the prevalence of smart devices and social networking services, a large number of objects that contain both spatial and keyword information have been generated continuously, and the number of subscribers also continues to increase. This poses a challenge to Pub/Sub systems: they need to continuously extract useful information from massive objects for each subscriber in real time. In this paper, we address the problem of k nearest neighbor monitoring on a spatial-keyword data stream for a large number of subscriptions. To scale well to massive objects and subscriptions, we propose a distributed solution, namely DkM-SKS. Given m workers, DkM-SKS divides a set of subscriptions into m disjoint subsets based on a cost model so that each worker has almost the same kNN-update cost, to maintain load balancing. DkM-SKS allows an arbitrary approach to updating kNN of each subscription, so with a suitable in-memory index, DkM-SKS can accelerate update efficiency by pruning irrelevant subscriptions for a given new object. We conduct experiments on real datasets, and the results demonstrate the efficiency and scalability of DkM-SKS.
BibTeX
@misc{tsuruoka2021distributed,
  author = {Shohei Tsuruoka and Daichi Amagata and Shunya Nishio and Takahiro Hara},
  title = {{Distributed Spatial-Keyword kNN Monitoring for Location-aware Pub/Sub}},
  year = {2021},
  eprint = {2101.12417},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2101.12417},
}

Loading related content...

Figure