计算机科学 ›› 2024, Vol. 51 ›› Issue (11A): 240200114-8.doi: 10.11896/jsjkx.240200114
孟祥福, 李天朔, 张霄雁
MENG Xiangfu, LI Tianshuo, ZHANG Xiaoyan
摘要： 对于路网上广泛的轨迹数据集,传统结合关键字特征的时空范围查询方法存在存储结构冗余和查询效率低下的问题,同时这些方法忽视了文本特征对优化查询结果个性化方面的潜在影响。为此,提出了一种结合文本特征的时空轨迹索引结构,称为IG-Tree。其基本思想是将道路网络图划分为分层子图,并据此构建一个平衡的树结构,其中每个树节点均关联并存储其特定的轨迹数据。此外,设计的查询算法利用与IG-Tree节点相关联的子路网图的文本特征,筛选并提出范围边界处的不相关轨迹,实现高效且精准的文本空间范围查询。这种索引结构不仅有效集成了时间、空间和文本3个维度的信息,而且基于这种结构的查询方法能够支持基于时空关键字的轨迹范围查询,从而极大地满足用户查询的个性化需求。在Porto和LA数据集上的实验证明,IG-Tree索引结构不仅在查询精度上表现出色,而且在响应速度上也具有显著优势,这进一步验证了其处理大规模轨迹数据集时的有效性和实用性。
中图分类号:
| [1]WANG Y,ZHENG Y,XUE Y.Travel time estimation of a path using sparse trajectories[C]//Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.2014:25-34. [2]SONG R,SUN W,ZHENG B,et al.Press:A novel framework of trajectory compression in road networks[J].arXiv:1402.1546,2014. [3]SU H,ZHENG K,HUANG J,et al.Crowdplanner:A crowd-based route recommendation system[C]//2014 IEEE 30th International Conference on Data Engineering.IEEE,2014:1144-1155. [4]LUO W,TAN H,CHEN L,et al.Finding time period-basedmost frequent path in big trajectory data[C]//Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data.2013:713-724. [5]ALVARES L O,BOGORNY V,KUIJPERS B,et al.Towardssemantic trajectory knowledge discovery[J].Data Mining and Knowledge Discovery,2007,12. [6]ZHANG C,HAN J,SHOU L,et al.Splitter:Mining fine-grained sequential patterns in semantic trajectories[C]//Proceedings of the VLDB Endowment.2014:769-780. [7]ZHENG K,SHANG S,YUAN N J,et al.Towards efficientsearch for activity trajectories[C]//2013 IEEE 29Th International Conference on Data Engineering(ICDE).IEEE,2013:230-241. [8]ZHONG R,LI G,TAN K L,et al.G-tree:An efficient and scalable index for spatial search on road networks[J].IEEE Transactions on Knowledge and Data Engineering,2015,27(8):2175-2189. [9]WANG Y,LI K,LI G,et al.Road-aware indexing for trajectory range queries[J].IEEE Transactions on Knowledge and Data Engineering,2023,35:8476-8489 [10]CONG G,LU H,OOI B C,et al.Efficient spatial keywordsearch in trajectory databases[J].arXiv:1205.2880,2012. [11]CHAKKA V P,EVERSPAUGH A,PATEL J M,et al.Indexing large trajectory datasets with seti[C]//CIDR.2003:76. [12]PFOSER D,JENSEN C S,THEODORIDIS Y.Novel approaches to the indexing of moving object trajectories[C]//Very Large Data Bases Conference.2000. [13]CHRISTOFORAKI M,HE J,DIMOPOULOS C,et al.Text vs.space:efficient geo-search query processing[C]//Proceedings of the 20th ACM International Conference on Information and Knowledge Management.2011:423-432. [14]ZHOU Y,XIE X,WANG C,et al.Hybrid index structures for location-based web search[C]//Proceedings of the 14th ACM International Conference on Information and Knowledge Mana-gement.2005:155-162. [15]DEFELIPE I,HRISTIDIS V,RISHE N.Keyword search onspatial databases[C]//2008 IEEE 24th International Confe-rence on Data Engineering.IEEE,2008:656-665. [16]HAN Y,WANG L,ZHANG Y,et al.Spatial keyword rangesearch on trajectories[C]//International Conference on Database Systems for Advanced Applications.2015. [17]FAN X,LI S,LAFORGE P D,et al.Em-based design approach for multi-band filters by reflected group delay method and cascade space mapping[C]//2019 IEEE MTT-S International Microwave Symposium(IMS).2019:1035-1037. [18]CHANDRIKA G N,REDDY E S.An efficient filtered classifier for classification of unseen test data in text documents[C]//2017 IEEE International Conference on Computational Intelligence and Computing Research(ICCIC).2017:1-4. [19]WANG Y,LIU Y,BLASCH E,et al.Simultaneous trajectoryassociation and clustering for motion segmentation[J].IEEE Signal Processing Letters,2018,25(1):145-149 [20]HSUEH Y L,CHEN H C.Map matching for low-sampling-rate GPS trajectories by exploring real-time moving directions[J].Information Sciences,2018,433-434:55-69. [21]LIAO C,CHEN C,XIANG C,et al.Taxi-passenger's destina-tion prediction via GPS embedding and attention-based bilstm model[J].IEEE Transactions on Intelligent Transportation Systems,2022,23(5):4460-4473. [22]YUAN J,ZHENG Y,XIE X,et al.T-drive:Enhancing driving directions with taxi drivers' intelligence[J].IEEE Transactions on Knowledge and Data Engineering,2013,25(1):220-232. [23]YANG Z,SUN H,HUANG J,et al.An efficient destinationprediction approach based on future trajectory prediction and transition matrix optimization[J].IEEE Transactions on Knowledge and Data Engineering,2020,32(2):203-217. [24]YU D,SHI X,CHAI L,et al.Balancing localization accuracy andlocation privacy in mobile cooperative localization[J].IEEE Transactions on Signal Processing,2023,71:2804-2818, [25]DZISEVIČ R,SĚOK D.Text classification using different feature extraction approaches[C]//2019 Open Conference of Electrical,Electronic and Information Sciences(eStream).2019:1-4. [26]ZHENG Y,CHEN Y,XIE X,et al.Geolife2.0:A location based social networking service[C]//2009 tenth International Confe-rence on Mobile Data Management:Systems,Services and Middleware.IEEE,2009:357-358. |
|
||
首页