IEEE Transactions on Parallel and Distributed Systems · 2020 · 14 citations · 23 references
ComputingComputer ScienceComputer SystemsData ManagementData StructuresDatabasesData WarehousingQuery ProcessingCell Width OptimizationForwarding SystemsMaintenance Cost ModelingMaintenance Cost OptimizationPublish-subscribe SystemsScalable IndexingSpatiotemporal Data PublishingSpatiotemporal Indexing
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.
23
The R*-tree: an efficient and robust access method for points and rectangles
Norbert Beckmann, Hans‐Peter Kriegel, Ralf Schneider et al. · 1990 · 4.2K citations · Full text
Keyword Search on Spatial Databases
Ian De Felipe, Vagelis Hristidis, Naphtali Rishe · 2008 · 485 citations