SEARCHING TRAJECTORIES BY REGIONS OF INTEREST
ABSTRACT
With the increasing availability of moving-object tracking data, trajectory search is increasingly important. We propose andinvestigate a novel query type named trajectory search by regions of interest (TSR query). Given an argument set of trajectories, a TSRquery takes a set of regions of interest as a parameter and returns the trajectory in the argument set with the highest spatial-densitycorrelation to the query regions. This type of query is useful in many popular applications such as trip planning and recommendation,and location based services in general. TSR query processing faces three challenges: how to model the spatial-density correlationbetween query regions and data trajectories, how to effectively prune the search space, and how to effectively schedule multipleso-called query sources. To tackle these challenges, a series of new metrics are defined to model spatial-density correlations. Anefficient trajectory search algorithm is developed that exploits upper and lower bounds to prune the search space and that adopts aquery-source selection strategy, as well as integrates a heuristic search strategy based on priority ranking to schedule multiple querysources. The performance of TSR query processing is studied in extensive experiments based on real and synthetic spatial data.
EXISTING SYSTEM:
Trajectory search queries aim to find trajectories with thehighest relevance to query arguments (e.g., a single spatialpoint, multiple spatial points, or a trajectory). Trajectory similarity functions may contain spatial, temporal , textual, and density elements.The resulting queries are useful in many popular applicationsincluding travel planning, carpooling, friend recommendationin social networks, and location-based services in general.We classify the existing trajectory search queries intothree categories according to their arguments. In the point-totrajectorycategory, the query argument is a single spatial point,and the query finds trajectories spatially close to the querypoint. Zheng et al. extended this query to cover spatial andtextual domains and propose the TkSK query, which retrievesthe trajectories that are spatially close to the query pointand also meet semantic requirements defined by the query.In the points-to-trajectory category, the query takes a set oflocations (e.g., sightseeing places) as argument and returnsa trajectory that connects or is close to the query locationsaccording to specific metrics. The concept of trajectory searchby locations (TSL) was first proposed by Chen et al. . Thisstudy considers the spatial domain only (Euclidean space).Shang et al.
PROPOSED SYSTEM
We define a novel trajectory search by regions of interest(TSR) query, which is useful in trip planning and recommendation,and in location-based services in general._ We define new measures to evaluate the spatial-densitycorrelation between a trajectory and a set of regions ofinterest._ We develop a best-expansion search (BES) algorithmto compute the TSR query efficiently with the supportof upper and lower bounds and heuristic query-sourcescheduling._ We further extend the BES algorithm to scenarios wherea sequence of query regions is given._ We conduct extensive experiments with real and syntheticspatial data to investigate the performance of the proposedalgorithms.
CONCLUSION AND FUTURE DIRECTIONS
We propose and study a novel problem, namely trajectorysearch by regions of interest (TSR query), that finds thetrajectory with the highest spatial-density correlation to asequence of query regions. Compared to existing studies oftrajectory search by locations, we take the concept of queryregion and the density of spatial objects into account. This typeof query is useful in many popular applications such as tripplanning and recommendation, and location based services ingeneral. To compute the TSR query efficiently, we developa best-expansion search algorithm that exploits upper andlower bounds to prune the search space and adopts a querysourceselection strategy, as well as a heuristic search strategybased on priority ranking to schedule multiple query sources.The performance of the TSR query was investigated throughextensive experiments on both real and synthetic spatial data.Three directions for future research are promising. First,users may assign different significance for different queryregions, making it of interest to take the significance of queryregions into account. The upper and lower bounds, querysourceselection strategy, and the heuristic search strategy mustbe reworked correspondingly. Second, it is of interest to taketemporal information into account and further extend the TSRquery into a spatiotemporal query. The resulting query aimsto find the trajectory with the highest spatial-temporal-densitycorrelation to the query regions. Third, it is of interest to studyhow to effectively split and combine trajectories in order toreturn better results.
REFERENCES
[1] R. Agrawal, C. Faloutsos, and A. N. Swami. Efficient similarity searchin sequence databases. In FODO, pages 69–84, 1993.
[2] S. Brakatsoulas, D. Pfoser, R. Salas, and C. Wenk. On map-matchingvehicle tracking data. In VLDB, pages 853–864, 2005.
[3] L. Chen and R. Ng. On the marriage of lp-norms and edit distance. InVLDB, pages 792–803, 2004.[4] L. Chen, M. T. Ozsu, and V. Oria. Robust and fast similarity search formoving object trajectories. In SIGMOD, pages 491–502, 2005.
[5] Z. Chen, H. T. Shen, X. Zhou, Y. Zheng, and X. Xie. Searchingtrajectories by locations: an efficiency study. In SIGMOD, pages 255–266, 2010.
[6] E. W. Dijkstra. A note on two problems in connection with graphs.Numerische Math, 1:269–271, 1959.
[7] E. Frentzos, K. Gratsias, N. Pelekis, and Y. Theodoridis. Algorithms fornearest neighbor search on moving object trajectories. Geoinformatica,11(2):159–193, 2007.
[8] E. Frentzos, K. Gratsias, and Y. Theodoridis. Index-based most similartrajectory search. In ICDE, pages 816–825, 2007.
[9] H. Gonzalez, J. Han, X. Li, M. Myslinska, and J. Sondag. Adaptivefastest path computation on a road network: A traffic mining approach.In VLDB, pages 794–805, 2007.
[10] C. Guo, Y. Ma, B. Yang, C. S. Jensen, and M. Kaul. Ecomark: evaluatingmodels of vehicular environmental impact. In SIGSPATIAL/GIS, pages269–278, 2012.
[11] A. Guttman. R-trees: a dynamic index structure for spatial searching.In SIGMOD, pages 47–57, 1984.
[12] E. Keogh. Exact indexing of dynamic time warping. In VLDB, pages406–417, 2002.