MO-Tree: An Efficient Forwarding Engine for Spatiotemporal-Aware Pub/Sub Systems
Lists
Only you see this
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...