Safe-Region Generation Method for Versatile Continuous Vicinity Queries in the Road Network Distance

Tin Nilar WIN  Htoo HTOO  Yutaka OHSAWA  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E101-A   No.2   pp.472-480
Publication Date: 2018/02/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E101.A.472
Type of Manuscript: PAPER
Category: Intelligent Transport System
location based services,  continuous queries,  safe-region,  road network distance,  

Full Text: PDF(813.7KB)
>>Buy this Article

This paper proposes a fast safe-region generation method for several kinds of vicinity queries including set k nearest neighbor (NN) queries, ordered kNN queries, reverse kNN queries, and distance range queries. When a user is driving a car on a road network, he/she wants to know about objects located in the vicinity of the car. However, the result changes according to the movement of the car, and therefore, the user needs to request up-to-date result to the server. On the other hand, frequent requests for up-to-date results cause heavy loadings on the server. To cope with this problem efficiently, the idea of the safe-region has been proposed, however, it takes long processing time in existing works. This paper proposes a fast generation method of the safe-region applicable to several types of vicinity queries. Through experimental evaluations, we demonstrate that the proposed method outperforms the existing algorithms in the processing time by one or two orders of magnitude.