基于位置的可拼接轨迹对搜索
|
摘要
移动设备的快速发展,生成了大量轨迹.基于位置的轨迹搜索,是指给定一组查询点,从数据集中检索top-k条轨迹,但是所得到的轨迹可能不能近距离通过所有查询点.利用轨迹可拼接的想法,提出基于位置的可拼接轨迹对搜索,使用户利用轨迹对得到的轨迹更加近距离地通过所有查询点.在搜索终止过程,给出可拼接的轨迹对搜索过程的有效终止条件.真实的数据集验证了所提方法的有效性.
With the proliferation of mobile devices,a large number of trajectories are generated.Location-based trajectory search is to find the top-ktrajectories from a database,given a small set of locations.However,the returned trajectory may not go through all locations as close as possible.Location-based splicing trajectories pair search was proposed based on the idea that trajectory could be spliced to help users to get closer trajectory to all the query points.In the termination of search process,an effective termination condition of the search process was given for splicing trajectory pairs.At last,the effectiveness and efficiency of the proposed algorithm were verified based on the real data set.
With the proliferation of mobile devices,a large number of trajectories are generated.Location-based trajectory search is to find the top-ktrajectories from a database,given a small set of locations.However,the returned trajectory may not go through all locations as close as possible.Location-based splicing trajectories pair search was proposed based on the idea that trajectory could be spliced to help users to get closer trajectory to all the query points.In the termination of search process,an effective termination condition of the search process was given for splicing trajectory pairs.At last,the effectiveness and efficiency of the proposed algorithm were verified based on the real data set.
引文
[1]Sherkat R,Rafiei D.On efficiently searching trajectories and archival data for historical similarities[J].Proceedings of the VLDB Endowment,2008,1(1):896-908.
[2]Agrawal R,Faloutsos C,Swami A N.Efficient similarity search in sequence databases[C]∥Proceedings of the4th International Conference on Foundations of Data Organization and Algorithms,FODO′93.Chicago,Illinois,USA:[s.n.],1993:69-84.
[3]Yi B K,Jagadish H V,Faloutsos C.Efficient retrieval of similar time sequences under time warping[C]∥Proceedings of the Fourteenth International Conference on Data Engineering.Orlando,Florida,USA:[s.n.],1998:201-208.
[4]Vlachos M,Gunopoulos D,Kollios G.Discovering similar multidimensional trajectories[C]∥Proceedings of the18th International Conference on Data Engineering.San Jose,CA,USA:[s.n.],2002:673-684.
[5]Chen L,Ng R T.On the marriage of lp-norms and edit distance[C]∥Proceedings of the Thirtieth International Conference on Very Large Data Bases.Toronto,Canada:[s.n.],2004:792-803.
[6]Chen L,Ozsu M T,Oria V.Robust and fast similarity search for moving object trajectories[C]∥Proceedings of the ACM SIGMOD International Conference on Management of Data.Baltimore,Maryland,USA:[s.n.],2005:491-502.
[7]Shang S,Ding R,Yuan B,et al.User oriented trajectory search for trip recommendation[C]∥Proceedings of the15th International Conference on Extending Database Technology,EDBT′12.Berlin,Germany:[s.n.],2012:156-167.
[8]Mao Y,Zhong H,Xiao X,et al.A Segment-based trajectory similarity measure in the urban transportation systems[J].Sensors,2017,17(3):524.
[9]Shang S,Ding R,Zheng K,et al.Personalized trajectory matching in spatial networks[J].The VLDB Journal,2014,23(3):449-468.
[10]Chen Z,Shen H T,Zhou X.Discovering Popular Routes from Trajectories[C]∥Proceedings of the 27th International Conference on Data Engineering.[S.l.]:IC-DE,2011:900-911.
[11]Ta N,Li G,Xie Y,et al.Signature-based trajectory similarity join[J].IEEE Transactions on Knowledge and Data Engineering,2017,29(4):870-883.
[12]Shang S,Chen L,Wei Z,et al.Trajectory similarity join in spatial networks[J].Proceedings of the VLDB Endowment,2017,10(11):1178-1189.
[13]Chen Z,Shen H T,Zhou X,et al.Searching trajectories by locations:an efficiency study[C]∥Proceedings of the ACM SIGMOD International Conference on Management of Data,SIGMOD 2010.Indianapolis,Indiana,USA:[s.n.],2010:255-266.
[14]Tang L A,Zheng Y,Xie X,et al:Retrieving k-nearest neighboring trajectories by a aet of point locations[C]∥Proceedings of Advances in Spatial and Temporal Databases-12th International Symposium.Minneapolis,MN,USA:[s.n.],2011:223-241.
[15]Qi S,Bouros P,Sacharidis D,et al.Efficient point-based trajectory search[C]∥Proceedings of Advances in Spatial and Temporal Databases-14th International Symposium,SSTD 2015.Hong Kong,China:[s.n.],2015:179-196.
[16]Qi S,Sacharidis D,Bouros P,et al.Snapshot and continuous points-based trajectory search[J].Geoinformatica,2017,21(4):669-701.
[17]Zheng K,Zheng Y,Xie X,et al:Reducing uncertainty of low-sampling-rate trajectories[C]∥Proceedings of IEEE 28th International Conference on Data Engineering(ICDE 2012).Washington,DC,USA:[s.n.],2012:1144-1155.
[18]董亭亭.大数据下空间数据索引和kNN查询技术的研究[D].大连:大连理工大学,2013.Dong Tingting.The research of spatial data indexing and kNN Query on large data sets[D].Dalian:Dalian Universty of Technology,2013.(in Chinese)
[19]Roussopoulos N,Kelley S,Vincent F.Nearest neighbor queries[C]∥Proceedings of the 1995 ACM SIGMODInternational Conference on Management of Data.San Jose,California:[s.n.],1995:71-79.
[2]Agrawal R,Faloutsos C,Swami A N.Efficient similarity search in sequence databases[C]∥Proceedings of the4th International Conference on Foundations of Data Organization and Algorithms,FODO′93.Chicago,Illinois,USA:[s.n.],1993:69-84.
[3]Yi B K,Jagadish H V,Faloutsos C.Efficient retrieval of similar time sequences under time warping[C]∥Proceedings of the Fourteenth International Conference on Data Engineering.Orlando,Florida,USA:[s.n.],1998:201-208.
[4]Vlachos M,Gunopoulos D,Kollios G.Discovering similar multidimensional trajectories[C]∥Proceedings of the18th International Conference on Data Engineering.San Jose,CA,USA:[s.n.],2002:673-684.
[5]Chen L,Ng R T.On the marriage of lp-norms and edit distance[C]∥Proceedings of the Thirtieth International Conference on Very Large Data Bases.Toronto,Canada:[s.n.],2004:792-803.
[6]Chen L,Ozsu M T,Oria V.Robust and fast similarity search for moving object trajectories[C]∥Proceedings of the ACM SIGMOD International Conference on Management of Data.Baltimore,Maryland,USA:[s.n.],2005:491-502.
[7]Shang S,Ding R,Yuan B,et al.User oriented trajectory search for trip recommendation[C]∥Proceedings of the15th International Conference on Extending Database Technology,EDBT′12.Berlin,Germany:[s.n.],2012:156-167.
[8]Mao Y,Zhong H,Xiao X,et al.A Segment-based trajectory similarity measure in the urban transportation systems[J].Sensors,2017,17(3):524.
[9]Shang S,Ding R,Zheng K,et al.Personalized trajectory matching in spatial networks[J].The VLDB Journal,2014,23(3):449-468.
[10]Chen Z,Shen H T,Zhou X.Discovering Popular Routes from Trajectories[C]∥Proceedings of the 27th International Conference on Data Engineering.[S.l.]:IC-DE,2011:900-911.
[11]Ta N,Li G,Xie Y,et al.Signature-based trajectory similarity join[J].IEEE Transactions on Knowledge and Data Engineering,2017,29(4):870-883.
[12]Shang S,Chen L,Wei Z,et al.Trajectory similarity join in spatial networks[J].Proceedings of the VLDB Endowment,2017,10(11):1178-1189.
[13]Chen Z,Shen H T,Zhou X,et al.Searching trajectories by locations:an efficiency study[C]∥Proceedings of the ACM SIGMOD International Conference on Management of Data,SIGMOD 2010.Indianapolis,Indiana,USA:[s.n.],2010:255-266.
[14]Tang L A,Zheng Y,Xie X,et al:Retrieving k-nearest neighboring trajectories by a aet of point locations[C]∥Proceedings of Advances in Spatial and Temporal Databases-12th International Symposium.Minneapolis,MN,USA:[s.n.],2011:223-241.
[15]Qi S,Bouros P,Sacharidis D,et al.Efficient point-based trajectory search[C]∥Proceedings of Advances in Spatial and Temporal Databases-14th International Symposium,SSTD 2015.Hong Kong,China:[s.n.],2015:179-196.
[16]Qi S,Sacharidis D,Bouros P,et al.Snapshot and continuous points-based trajectory search[J].Geoinformatica,2017,21(4):669-701.
[17]Zheng K,Zheng Y,Xie X,et al:Reducing uncertainty of low-sampling-rate trajectories[C]∥Proceedings of IEEE 28th International Conference on Data Engineering(ICDE 2012).Washington,DC,USA:[s.n.],2012:1144-1155.
[18]董亭亭.大数据下空间数据索引和kNN查询技术的研究[D].大连:大连理工大学,2013.Dong Tingting.The research of spatial data indexing and kNN Query on large data sets[D].Dalian:Dalian Universty of Technology,2013.(in Chinese)
[19]Roussopoulos N,Kelley S,Vincent F.Nearest neighbor queries[C]∥Proceedings of the 1995 ACM SIGMODInternational Conference on Management of Data.San Jose,California:[s.n.],1995:71-79.