Journal of Computer Science and Technology ›› 2019, Vol. 34 ›› Issue (4): 747-761.doi: 10.1007/s11390-019-1940-x

Special Issue: Data Management and Data Mining

• Special Section on Spatio-Temporal Big Data Analytics • Previous Articles     Next Articles

Scalable and Adaptive Joins for Trajectory Data in Distributed Stream System

Jun-Hua Fang1,2, Member, CCF, Peng-Peng Zhao1, An Liu1, Member, CCF, Zhi-Xu Li1, Member, CCF, ACM, IEEE, Lei Zhao1, Member, CCF   

  1. 1 Institute of Artificial Intelligence, School of Computer Science and Technology, Soochow University, Suzhou 215006, China;
    2 Neusoft Corporation, Shenyang 110179, China
  • Received:2019-01-13 Revised:2019-05-13 Online:2019-07-11 Published:2019-07-11
  • Supported by:
    This work was partially supported by the National Natural Science Foundation of China under Grant Nos. 61802273, 61772356, and 61836007, the Postdoctoral Science Foundation of China under Grant No. 2017M621813, the Postdoctoral Science Foundation of Jiangsu Province of China under Grant No. 2018K029C, and the Natural Science Foundation for Colleges and Universities in Jiangsu Province of China under Grant No. 18KJB520044. This work was also supported by the Open Program of Neusoft Corporation under Grant No. SKLSAOP1801 and Blockshine Technology Corporation of China.

As a fundamental operation in LBS (location-based services), the trajectory similarity of moving objects has been extensively studied in recent years. However, due to the increasing volume of moving object trajectories and the demand of interactive query performance, the trajectory similarity queries are now required to be processed on massive datasets in a real-time manner. Existing work has proposed distributed or parallel solutions to enable large-scale trajectory similarity processing. However, those techniques cannot be directly adapted to the real-time scenario as it is likely to generate poor balancing performance when workload variance occurs on the incoming trajectory stream. In this paper, we propose a new workload partitioning framework, ART (Adaptive Framework for Real-Time Trajectory Similarity), which introduces practical algorithms to support dynamic workload assignment for RTTS (real-time trajectory similarity). Our proposal includes a processing model tailored for the RTTS scenario, a load balancing framework to maximize throughput, and an adaptive data partition manner designed to cut off unnecessary network cost. Based on this, our model can handle the large-scale trajectory similarity in an on-line scenario, which achieves scalability, effectiveness, and efficiency by a single shot. Empirical studies on synthetic data and real-world stream applications validate the usefulness of our proposal and prove the huge advantage of our approach over state-of-the-art solutions in the literature.

Key words: real-time data processing; distributed computing; trajectory similarity; load balancing;

[1] Trasarti R, Pinelli F, Nanni M et al. Mining mobility user profiles for car pooling. In Proc. the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, August 2011, pp.1190-1198.
[2] Zheng K, Zheng Y, Yuan N J et al. Online discovery of gathering patterns over trajectories. IEEE Transactions on Knowledge and Data Engineering, 2014, 26(8):1974-1988.
[3] Li L, Kim J, Xu J et al. Time-dependent route scheduling on road networks. SIGSPATIAL Special, 2018, 10(1):10-14.
[4] Shang S, Ding R, Zheng K et al. Personalized trajectory matching in spatial networks. The International Journal on Very Large Data Bases, 2014, 23(3):449-468.
[5] Shang S, Chen L, Wei Z et al. Collective travel planning in spatial networks. IEEE Transactions on Knowledge and Data Engineering, 2016, 28(5):1132-1146.
[6] Su H, Zheng K, Wang H et al. Calibrating trajectory data for similarity-based analysis. In Proc. the 2013 ACM SIGMOD International Conference on Management of Data, June 2013, pp.833-844.
[7] Su H, Zheng K, Huang J et al. Calibrating trajectory data for spatio-temporal similarity analysis. The International Journal on Very Large Data Bases, 2015, 24(1):93-116.
[8] Sun J, Xu J, Zhou R et al. Discovering expert drivers from trajectories. In Proc. the 34th International Conference on Data Engineering, April 2018, pp.1332-1335.
[9] Shang S, Chen L, Wei Z et al. Parallel trajectory similarity joins in spatial networks. The International Journal on Very Large Data Bases, 2018, 27(3):395-420.
[10] Shang S, Chen L, Wei Z et al. Trajectory similarity join in spatial networks. Proceedings of the VLDB Endowment, 2017, 10(11):1178-1189.
[11] Xie D, Li F, Phillips J M. Distributed trajectory similarity search. Proceedings of the VLDB Endowment, 2017, 10(11):1478-1489.
[12] Toshniwal A, Taneja S, Shukla A et al. Storm@twitter. In Proc. the 2014 ACM SIGMOD International Conference on Management of Data, June 2014, pp.147-156.
[13] Kulkarni S, Bhagat N, Fu M et al. Twitter heron:Stream processing at scale. In Proc. the 2015 ACM SIGMOD International Conference on Management of Data, May 2015, pp.239-250.
[14] Zaharia M, Das T, Li H et al. Discretized streams:Faulttolerant streaming computation at scale. In Proc. the 24th ACM SIGOPS Symposium on Operating Systems Principles, November 2013, pp.423-438.
[15] Nasir M A U, Morales G D F, Garcia-Soriano D et al. The power of both choices:Practical load balancing for distributed stream processing engines. In Proc. the 31st IEEE International Conference on Data Engineering, April 2015, pp.137-148.
[16] Nasir M A U, Morales G D F, Kourtellis N et al. When two choices are not enough:Balancing at scale in distributed stream processing. In Proc. the 32nd IEEE International Conference on Data Engineering, May 2016, pp.589-600.
[17] Lin Q, Ooi B C, Wang Z et al. Scalable distributed stream join processing. In Proc. the 2015 ACM SIGMOD International Conference on Management of Data, May 2015, pp.811-825.
[18] Elseidy M, Elguindy A, Vitorovic A et al. Scalable and adaptive online joins. Proceedings of the VLDB Endowment, 2014, 7(6):441-452.
[19] Wang H, Su H, Zheng K et al. An effectiveness study on trajectory similarity measures. In Proc. the 24th Australasian Database Conference, February 2013, pp.13-22.
[20] Ying R, Pan J, Fox K et al. A simple efficient approximation algorithm for dynamic time warping. In Proc. the 24th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, October 2016, Article No. 21.
[21] Vlachos M, Kollios G, Gunopulos D. Discovering similar multidimensional trajectories. In Proc. the 18th International Conference on Data Engineering, February 2002, pp.673-684.
[22] Chen L, Özsu M T, Oria V. Robust and fast similarity search for moving object trajectories. In Proc. the 2005 ACM SIGMOD International Conference on Management of Data, June 2005, pp.491-502.
[23] Frentzos E, Gratsias K, Theodoridis Y. Index-based most similar trajectory search. In Proc. the 23rd International Conference on Data Engineering, April 2007, pp.816-825.
[24] Yanagisawa Y, Akahani J, Satoh T. Shape-based similarity query for trajectory of mobile objects. In Proc. the 3rd International Conference on Mobile Data Management, January 2003, pp.63-77.
[25] Jiang Y, Li G, Feng J et al. String similarity joins:An experimental evaluation. Proceedings of the VLDB Endowment, 2014, 7(8):625-636.
[26] Gedik B. Partitioning functions for stateful data parallelism in stream processing. The International Journal on Very Large Data Bases, 2014, 23(4):517-539.
[27] Shah M A, Hellerstein J M, Chandrasekaran S et al. Flux:An adaptive partitioning operator for continuous query systems. In Proc. the 19th International Conference on Data Engineering, March 2003, pp.25-36.
[1] Yun-Cong Zhang, Xiao-Yang Wang, Cong Wang, Yao Xu, Jian-Wei Zhang, Xiao-Dong Lin, Guang-Yu Sun, Gong-Lin Zheng, Shan-Hui Yin, Xian-Jin Ye, Li Li, Zhan Song, Dong-Dong Miao. Bigflow: A General Optimization Layer for Distributed Computing Frameworks [J]. Journal of Computer Science and Technology, 2020, 35(2): 453-467.
[2] Guo-Wei Wang, Jin-Dou Zhang, Jing Li. Complete Your Mobility: Linking Trajectories Across Heterogeneous Mobility Data Sources [J]. , 2018, 33(4): 792-806.
[3] Qin Liu, Yuhong Guo, Jie Wu, Guojun Wang. Effective Query Grouping Strategy in Clouds [J]. Journal of Computer Science and Technology, 2017, 32(6): 1231-1249.
[4] Xin Bi, Xiang-Guo Zhao, Guo-Ren Wang. Efficient Processing of Distributed Twig Queries Based on Node Distribution [J]. , 2017, 32(1): 78-92.
[5] Dong-Hong Han, Xin Zhang, Guo-Ren Wang. Classifying Uncertain and Evolving Data Streams with Distributed Extreme Learning Machine [J]. , 2015, 30(4): 874-887.
[6] Wen-Yu Li, Xiang Zhang, Shu-Cong Jia, Xin-Yu Gu, Lin Zhang, Xiao-Yu Duan, and Jia-Ru Lin. A Novel Dynamic Adjusting Algorithm for Load Balancing and Handover Co-Optimization in LTE SON [J]. , 2013, 28(3): 437-444.
[7] Yong Wu (吴勇) and Arun Kumar. A Parallel Interval Computation Model for Global Optimization with Automatic Load Balancing [J]. , 2012, 27(4): 744-753.
[8] Jin Huang, Feng Zhao, Jian Chen, Member, CCF, Jian Pei, Senior Member, ACM, IEEE, and Jian Yin, Senior Member, CCF. Towards Progressive and Load Balancing Distributed Computation: A Case Study on Skyline Analysis [J]. , 2010, 25(3): 431-443.
[9] Li-Na Ni, Jin-Quan Zhang, Chun-Gang Yan, and Chang-Jun Jiang. A Heuristic Algorithm for Task Scheduling Based on Mean Load on Grid [J]. , 2006, 21(4): 559-564 .
[10] Jun-Feng Tian, Jun-Wei Zhang, and Feng-Xian Wang. Fault Tolerant Algorithm Based on Dynamic and Active Load Balancing for Redundant Services [J]. , 2004, 19(6): 0-0.
[11] JIN Hai (金 海), ZOU DeQing (邹德清), CHEN HanHua (陈汉华), SUN JianHua (孙建华) and WU Song (吴 松). Fault-Tolerant Grid Architecture and Practice [J]. , 2003, 18(4): 0-0.
[12] ZHANG Wensong(章文嵩),JIN Shiyao(金士尧)and WU Quanyuan(吴泉源). LinuxDirector:A Connection Director for Scalable Internet Services [J]. , 2000, 15(6): 0-0.
[13] ZHANG Wensong; JIN Shiyao; WU Quanyuan;. LinuxDirector: A Connection Director for Scalable Internet Services [J]. , 2000, 15(6): 560-571.
[14] LU Sanglu; ZHOU Xiaoboand; XIE Li;. A Model for Dynamic Adaptive Coscheduling [J]. , 1999, 14(3): 267-275.
[15] Lin Chengiiang; Li Sanli;. Strategy and Simulation of Adaptive RID for Distributed Dynamic Load Balancing in Parallel Systems [J]. , 1997, 12(2): 113-120.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!

ISSN 1000-9000(Print)

         1860-4749(Online)
CN 11-2296/TP

Home
Editorial Board
Author Guidelines
Subscription
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
Tel.:86-10-62610746
E-mail: jcst@ict.ac.cn
 
  Copyright ©2015 JCST, All Rights Reserved