Efficient processing of optimal obstructed sequenced route queries

Abstract

Trip planning has become an important class of location-based services (LBSs) in recent years thatenable users to plan trips for visiting different points of interests (POIs) like a restaurant, a shoppingcenter and a movie theater with the minimum travel distance. Researchers have focused on developingefficient algorithms for processing trip planning queries in real time. In this thesis, we introduceoptimal obstructed sequenced route (OOSR) queries, a novel type of trip planning in spatial databases.For a given source and destination locations and the sequence of required types of POIs (e.g., first anATM booth then a restaurant), an OOSR query returns the locations of POIs, one from every requiredtype, that together minimize the obstructed trip distance (OTD) from the source to the destinationvia the POIs. A pedestrian’s walking path is obstructed by the presence of obstacles like a river, afence or a private property, and an obstructed distance is measured as the length of the shortest pathbetween two locations by avoiding the obstacles. We develop the first solution to address OOSRqueries. The efficiency of an OOSR algorithm depends on the OTD computation technique and thenumber of POIs explored for finding the optimal answer. We exploit elliptical properties and developnovel OTD computation techniques that do not retrieve the same obstacles multiple times, reuses thealready computed obstructed distances, and minimizes the retrieval of the extra obstacles. We refinethe POI search space and propose efficient algorithms to evaluate OOSR queries with reduced IO andquery processing overhead. We perform experiments using a real dataset and show the efficiency ofour OOSR algorithms. Experiments show that our OTD computation technique outperforms existingliterature with a large margin.