Noname manuscript No. (will be inserted by the editor) A Highly Optimized Algorithm for Continuous Intersection Join Queries over Moving Objects

the date of receipt and acceptance should be inserted later Abstract Given two sets of moving objects with non-zero 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 im-portant for a number of applications, e.g., in the multi-billion dollar computer game industry, massively multiplayer on-line games (MMOGs) like World of Warcraft need to moni-tor 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 an-other query type is prohibitive and answering the query in real time poses a great challenge. Those algorithms com-pute the query answer for either too long or too short a time interval, which results in either a very large computa-tion 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 tra-ditional intersection join algorithms. Finally, we provide