Abstract
Given two sets of moving objects with nonzero extents, the continuous intersection joins query reports every pair of intersecting objects, one from each of the two moving object sets, for every timestamp. This type of queries is important for a number of applications, e. g., in the multi-billion-dollar computer game industry, massively multiplayer online games like World of Warcraft need to monitor the intersection among players' attack ranges and render players' interaction in real time. the computational cost of a straightforward algorithm or an algorithm adapted from another query type is prohibitive, and answering the query in real time poses a great challenge. Those algorithms compute the query answer for either too long or too short a time interval, which results in either a very large computation cost per answer update or too frequent answer updates, respectively. This observation motivates us to optimize the query processing in the time dimension. in this study, we achieve this optimization by introducing the new concept of time-constrained (TC) processing. Further, TC processing enables a set of effective improvement techniques on traditional intersection join algorithms. Finally, we provide a method to find the optimal value for an important parameter required in our technique, the maximum update interval. as a result, we achieve a highly optimized algorithm for processing continuous intersection join queries on moving objects. with a thorough experimental study, we show that our algorithm outperforms the best adapted existing solution by several orders of magnitude. We also validate the accuracy of our cost model and its effectiveness in optimizing the performance. © 2011 Springer-Verlag.
Recommended Citation
R. Zhang et al., "A Highly Optimized Algorithm for Continuous Intersection Join Queries over Moving Objects," VLDB Journal, vol. 21, no. 4, pp. 561 - 586, Springer, Aug 2012.
The definitive version is available at https://doi.org/10.1007/s00778-011-0259-1
Department(s)
Computer Science
Keywords and Phrases
Continuous intersection join; Moving objects; Spatial databases
International Standard Serial Number (ISSN)
0949-877X; 1066-8888
Document Type
Article - Journal
Document Version
Citation
File Type
text
Language(s)
English
Rights
© 2024 Springer, All rights reserved.
Publication Date
01 Aug 2012
