MO-Tree: An Efficient Forwarding Engine for Spatiotemporal-Aware Pub/Sub Systems

Tianchen Ding, Shiyou Qian, Jian Cao, Guangtao Xue, Yanmin Zhu, Jiadi Yu, Minglu Li

Abstract

For large-scale spatiotemporal-aware publish/subscribe systems, it is critical to design an efficient forwarding engine to achieve fast matching and maintenance of events and subscriptions. For this goal, we propose a novel data structure called MO-Tree to index both subscriptions and events in a unified way. The design philosophy behind MO-Tree is to keep the data structure concise, which manifests in three aspects: limiting the height of MO-Tree, trading space for time, and avoiding node merging and splitting. The difficulty in designing MO-Tree is how to efficiently index width-variable intervals. We present a multi-level cell-overlapping partition scheme and build a theoretical model to optimize the cell width in each level. To evaluate the performance of MO-Tree, a series of experiments is conducted on real-world trace datasets. The experiment results show MO-Tree significantly outperforms the state-of-the-art in terms of matching speed and maintenance cost.
BibTeX
@article{ding2021mo,
  author = {Tianchen Ding and Shiyou Qian and Jian Cao and Guangtao Xue and Yanmin Zhu and Jiadi Yu and Minglu Li},
  title = {{MO-Tree: An Efficient Forwarding Engine for Spatiotemporal-Aware Pub/Sub Systems}},
  journal = {IEEE Trans. Parallel Distributed Syst.},
  year = {2021},
  doi = {10.1109/tpds.2020.3036014},
}

Loading related content...

Figure