Abstract
In this paper, we study the problem of order-sensitive activity trajectory search. Given a query containing a set of time-order target locations, the problem is to find the most suitable trajectory from the trajectory database such that the resulting trajectory can achieve the minimum distance from the query. We formulate the problem using two different order-sensitive distance functions: the sum-up objective function, and the maximum objective function. For the sum-up objective function, we propose a dynamic programming (DP) algorithm with time complexity \(O(mn^2)\) where m is the length of the trajectory and n is the number of query locations. To improve the efficiency, we also propose an improved DP algorithm. For the maximum objective function, we propose exact and approximation algorithms to tackle it. The approximation algorithm achieves a near-optimal performance ratio, and it improves the time complexity from \(O(mn^2)\) to \(O(n\log (d/\epsilon ))\) in comparison with the DP algorithm. Extensive experimental studies over both synthetic and real-world datasets demonstrate the efficiency and effectiveness of our approaches.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Agrawal, R., Faloutsos, C., Swami, A.: Efficient similarity search in sequence databases. In: Lomet, D.B. (ed.) FODO 1993. LNCS, vol. 730, pp. 69–84. Springer, Heidelberg (1993). doi:10.1007/3-540-57301-1_5
Cai, Y., Ng, R.T.: Indexing spatio-temporal trajectories with Chebyshev polynomials. In: SIGMOD (2004)
Chen, L., Ng, R.T.: On the marriage of lp-norms and edit distance. In: VLDB, pp. 792–803 (2004)
Chen, L., Özsu, M.T., Oria, V.: Robust and fast similarity search for moving object trajectories. In: SIGMOD, pp. 491–502 (2005)
Chen, Z., Shen, H.T., Zhou, X., Zheng, Y., Xie, X.: Searching trajectories by locations: an efficiency study. In: SIGMOD (2010)
Faloutsos, C., Ranganathan, M., Manolopoulos, Y.: Fast subsequence matching in time-series databases. In: SIGMOD (1994)
Jeung, H., Yiu, M.L., Zhou, X., Jensen, C.S., Shen, H.T.: Discovery of convoys in trajectory databases. PVLDB 1(1), 1068–1080 (2008)
Lee, J., Han, J., Whang, K.: Trajectory clustering: a partition-and-group framework. In: SIGMOD (2007)
Li, Q., Zheng, Y., Xie, X., Chen, Y., Liu, W., Ma, W.: Mining user similarity based on location history. In: GIS, p. 34 (2008)
Li, R., Qin, L., Yu, J.X., Mao, R.: Optimal multi-meeting-point route search. IEEE Trans. Knowl. Data Eng. 28(3), 770–784 (2016)
Morse, M.D., Patel, J.M.: An efficient and accurate method for evaluating time series similarity. In: SIGMOD, pp. 569–580 (2007)
Ni, J., Ravishankar, C.V.: Indexing spatio-temporal trajectories with efficient polynomial approximations. IEEE Trans. Knowl. Data Eng. 19(5), 663–678 (2007)
Sefidmazgi, M.G., Sayemuzzaman, M., Homaifar, A.: Non-stationary time series clustering with application to climate systems. In: Jamshidi, M., Kreinovich, V., Kacprzyk, J. (eds.) Advance Trends in Soft Computing. SFSC, vol. 312, pp. 55–63. Springer, Cham (2014). doi:10.1007/978-3-319-03674-8_6
Shang, S., Chen, L., Jensen, C.S., Wen, J., Kalnis, P.: Searching trajectories by regions of interest. IEEE Trans. Knowl. Data Eng. 29(7), 1549–1562 (2017)
Shang, S., Ding, R., Yuan, B., Xie, K., Zheng, K., Kalnis, P.: User oriented trajectory search for trip recommendation. In: EDBT (2012)
Shang, S., Ding, R., Zheng, K., Jensen, C.S., Kalnis, P., Zhou, X.: Personalized trajectory matching in spatial networks. VLDB J. 23(3), 449–468 (2014)
Sherkat, R., Rafiei, D.: On efficiently searching trajectories and archival data for historical similarities. PVLDB 1(1), 896–908 (2008)
Vlachos, M., Gunopulos, D., Kollios, G.: Discovering similar multidimensional trajectories. In: ICDE, pp. 673–684 (2002)
Yang, A.Y., Jafari, R., Sastry, S., Bajcsy, R.: Distributed recognition of human actions using wearable motion sensor networks. JAISE 1(2), 103–115 (2009)
Yi, B., Jagadish, H.V., Faloutsos, C.: Efficient retrieval of similar time sequences under time warping. In: ICDE (1998)
Zheng, K., Shang, S., Yuan, N.J., Yang, Y.: Towards efficient search for activity trajectories. In: ICDE (2013)
Acknowledgement
The work was supported in part by (i) NSFC Grants (61402292, U1301252, 61033009), NSF-Shenzhen Grants (JCYJ20150324140036826, JCYJ20140418095735561), and Startup Grant of Shenzhen Kongque Program (827/000065). Dr. Zhenjun Li and Prof. Minhua Lu are the corresponding authors of this paper.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Guo, K., Li, RH., Qiao, S., Li, Z., Zhang, W., Lu, M. (2017). Efficient Order-Sensitive Activity Trajectory Search. In: Bouguettaya, A., et al. Web Information Systems Engineering – WISE 2017. WISE 2017. Lecture Notes in Computer Science(), vol 10569. Springer, Cham. https://doi.org/10.1007/978-3-319-68783-4_27
Download citation
DOI: https://doi.org/10.1007/978-3-319-68783-4_27
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-68782-7
Online ISBN: 978-3-319-68783-4
eBook Packages: Computer ScienceComputer Science (R0)