A highly optimized algorithm for continuous inters

Authors: Rui Zhang Jianzhong Qi Dan Lin Wei Wang Raymond ChiWing Wong

Publish Date: 2011/10/29

Volume: 21, Issue: 4, Pages: 561-586

PDF Link

Abstract

Given two sets of moving objects with nonzero extents the continuous intersection join 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 eg in the multibillion 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 timeconstrained 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

Keywords: