Informatica

Continuous query is a monitoring query issued by a moving object to keep the query condition satisfied. In the continuous query, the safe-region method is preferable to reduce the load for several requests on the server. A safe-region is a region in which the query result is unchanged, and it is created and sent to the moving object with the query result. The moving object always checks the current position in the region. When it leaves the region, it requests a new result to the server. Safe-region generation methods have been eagerly discussed for simple query types, including kNN, distance range, and RkNN queries. This paper challenges to generate the safe-region for trip route planning queries (TRPQ). This type of query is very time consuming even for snap-shot queries, and therefore, there are many restrictions on the safe-region generation methods in existing studies. This paper first investigates the property of the safe-region on TRPQ, and then proposes two types of efficient algorithms, the preceding rival addition (PRA) and the tardy rival addition (TRA) algorithms. The former algorithm runs fast, however, it still requires long processing time when the density of the data object is high. The latter algorithm is very fast independent of the density of data objects, however, the safe-region generated by TRA becomes about 5% larger in the size of generated safe-region. We evaluate the performance through intensive experiments.