网络空间移动对象模型的应用与发展

doi:10.3724/SP.J.1047.2013.00328

摘要/Abstract

摘要：

海量移动对象轨迹数据的涌现促使移动对象数据库成为一个新兴的研究领域。网络空间是人与交通工具移动的主要空间范围,也是移动对象数据库领域最重要的研究空间。网络空间下的移动对象建模是交通科学、社会与城市计算的基础性关键技术。由于受到所依附的地理空间的限制,网络环境下的移动对象数据表达与自由空间相比具有很大的特殊性,面临新的挑战。本文分析了网络空间移动对象建模的基本需求,对20年来,业界提出的各种网络空间移动对象数据模型进行了系统回顾和分类,深入分析了各种网络空间移动对象数据模型的特征、优点与局限性,提出了现阶段网络空间移动对象数据建模需要关注的关键问题,并对未来研究方向进行了展望。

关键词: 移动对象, 轨迹, 空间数据库, 网络空间, 数据模型

Abstract:

In recent years, along with the rapid development of location technologies such as GPS, RFID and wireless sensor networks as well as the widespread use of location-aware devices such as mobile phones and GPS receivers, large amounts of trajectories of moving objects can be easily acquired. By using moving objects databases, massive trajectories of moving objects can be manipulated and handled for various applications, which makes the study of moving objects databases more and more important. Among the most recent researches, the study space where moving objects travel can be mainly divided into two types, the Euclidean space and the geographic road networks. In Euclidean space, moving objects can move freely. However, under geographic network environment, moving objects are limited to geographic networks and must follow the road regulation. For the latter research branch is much more practical than the former one, this paper concerns the latter branch and focuses on modeling moving objects in geographic networks, which is the foundation of the study of moving objects databases. It has been a hot research topic in the field of moving objects database management and also provides key technology for many other areas such as transportation, location-based services, urban mobility and social computing. Although it is of great theoretical significance and application value, modeling moving object in geographic networks challenges the research community a lot due to network constraints. In this paper, firstly, most existent geographic network-constrained moving object data models over recent decades has been systematically reviewed and classified. The related literatures show that most geographic network-constrained models can be divided into four categories including edge-based network-constrained model, route-based network-constrained model, partition-based network-constrained model and spatial-temporal network-constrained model. Then model characteristics, advantages as well as limitations have been elaborately analyzed, based on which, finally some crucial points on modeling moving objects in geographic networks has been proposed and discussed.

Key words: spatial network, data model, moving objects databases, trajectories

张恒才, 陆锋, 陈洁. 网络空间移动对象模型的应用与发展[J]. 地球信息科学学报, 2013, 15(3): 328-337.DOI:10.3724/SP.J.1047.2013.00328

ZHANG Heng-Cai, LIU Feng, CHEN Ji. Advance in Moving Object Data Modeling under Geographic Network Environment[J]. , 2013, 15(3): 328-337.DOI:10.3724/SP.J.1047.2013.00328

参考文献

[1] 陆锋,郑年波,段滢滢,等.出行信息服务关键技术研究进展与问题探讨[J].中国图象图形学报,2009(7):1219-1229.

[2] Wolfson O. Moving objects information management: Thedatabase challenge[J]. Next Generation Information Technologiesand Systems, 2002(2382):15-26.

[3] Han J, Li Z, Tang L. Mining moving object, trajectory andtraffic data[M]. Berlin:Springer Berlin Heidelberg, 2010.

[4] Wolfson O, Xu B, Chamberlain S, et al. Moving objects databases:Issues and solutions[C]. Scientific and StatisticalDatabase Management, 1998,111-122.

[5] Gao Y, Zheng B, Chen G, et al. Continuous nearest-neighborsearch in the presence of obstacles[J]. ACM Transactionson Database Systems (TODS), 2011,36(2):9-59.

[6] Guting R H, Ding Z. Modeling and querying moving objectsin networks[J]. TheVLDB Journal, 2006, 15(2):165-190.

[7] Jensen C S, Lu H, Yang B. Graph model based indoortracking[C]. Mobile Data Management: Systems, Servicesand Middleware, 2009,122-131.

[8] Zheng Y, Xie X. Learning transportation mode from rawGPS data for geographic application on the web[C]. // Proceedingsof International conference on World Wild Web,2008,247-256.

[9] Zheng Y, Zhang L, Xie X, et al. Mining interesting locationsand travel sequences from GPS trajectories[C]. Proceedingsof the 18th International Conference on WorldWideWeb, 2009,791-800.

[10] Zheng Y, Zhang L, Xie X, et al. Mining correlation be-tween locations using human location history[C]. In Proceedingsof ACM SIGSPATIAL Conference on Advancesin Geographical Information Systems, 2010,472-475.

[11] Zheng Y, Zhang L, Xie X. Recommending friends and locationsbased on individual location history[J]. ACMTransactions on theWeb (TWEB), 2011,5(1):5-44.

[12] Wei L Y, Zheng Y, Peng W C. Constructing popularroutes from uncertain trajectories[C]. Proceedings of the18th ACM SIGKDD International Conference on KnowledgeDiscovery and Data Mining, 2012,195-203.

[13] Yuan J, Zheng Y, Xie X. Discovering regions of differentfunctions in a city using human mobility and POIs[C].Proceedings of the 18th ACM SIGKDD InternationalConference on Knowledge Discovery and Data Mining,2012,186-194.

[14] 陈传彬,陆锋,励惠国,等.城市路网信息融合的关键技术[J].地球信息科学学报,2009,11(4):520-525.

[15] 周亮,陆锋,张恒才.基于动态中介中心性的城市道路网实时分层方法[J].地球信息科学学报,2012,14(3):292-298.

[16] Aref W G, Ouzzani M. Data management challenges forcomputational transportation[C]. Proceedings of the 5thAnnual International Conference on Mobile and UbiquitousSystems: Computing, Networking, and Services,2008,4-42.

[17] Geers D G. Some research questions for computationaltransportation science[C]. Proceedings of the 5th AnnualInternational Conference on Mobile and Ubiquitous Systems:Computing, Networking, and Services, 2008,1-5.

[18] 陆锋,段滢滢,臧志刚.短时交通预测的动态出行信息服务协同工作平台[J]. 地球信息科学学报.2009,11(5):5617- 5622.

[19] Hu H, Lee D L, Lee V. Distance indexing on road networks[C]. Proceedings of the 32nd International Conferenceon Very Large Data Bases, 2006,894-905.

[20] Wolfson O, Chamberlain S, Dao S, et al. Cost and imprecisionin modeling the position of moving objects[C]. DataEngineering, 1998,588-596.

[21] Güting RH. Moving object databases[M]. United States:Morgan Kaufmann, 2005.

[22] Forlizzi L, Güting R H, Nardelli E, et al. A data modeland data structures for moving objects databases[C]. Proceedingsof the 2000 ACM SIGMOD International Conferenceon Management of Data, 2000,319-330.

[23] Meng X, Ding Z. DSTTMOD: A future trajectory basedmoving objects database[C]. Database and Expert SystemsApplications, 2003,444-453.

[24] Jandt S. Network data model and BerlinMOD benchmark[DB/OL]. http://dna.fernuni-hagen.de/secondo/ Berlin-MOD/Network.html, 2010.

[25] Kakoudakis I, Theodoulidis B. The TAU temporal objectmodel[R]. Rapport de recherche TR-96-4, TimeLab, Universityof Manchester UMIST, 1996.

[26] Allen J F. Maintaining knowledge about temporal intervals[J]. Communications of the ACM, 1983,26(11):832-843.

[27] Güting R H. Graph D B: Modeling and querying graphsin databases[C]. Proceedings of the International Conferenceon Very Large Data Bases, 1994,297-297.

[28] Becker L, Güting R H. The Graph D B. Algebra: Specificationof advanced data models with second-order signature[R]. 1995.

[29] Kanjilal V, Schneider M. Spatial network modeling for databases[C]. Proceedings of the 2011 ACM Symposium onApplied Computing, 2011,827-832.

[30] Scarponcini P. Generalized model for linear referencingin transportation[J]. GeoInformatica, 2002,6(1):35-55.

[31] Vonderohe A, Chou C, Sun F, et al. A generic data modelfor linear referencing systems[R]. Transportation ResearchBoard: National Cooperative Highway ResearchProgram, 1997(218):1-28.

[32] Zhu Y, Zheng VW, Yang Q. Computing with Spatial Trajectories[M].New York: Springer New York, 2011.

[33] Giannotti F, Nanni M, Pinelli F, et al. Trajectory patternmining[C]. Proceedings of the 13th ACM SIGKDD InternationalConference on Knowledge Discovery and DataMining, 2007,330-339.

[34] Li X, Claramunt C, Ray C, et al. Progress in patial datahandling[M]. Berlin:Springer Berlin Heidelberg, 2006.

[35] Wang H, Zimmermann R. Snapshot location-based queryprocessing on moving objects in road networks[C]. Proceedingsof the 16th ACM SIGSPATIAL InternationalConference on Advances in Geographic Information Systems,2008.

[36] Stojanovic D, Papadopoulos A N, Predic B, et al. Continuousrange monitoring of mobile objects in road networks[J]. Data & Knowledge Engineering, 2008,64(1):77-100.

[37] Mouratidis K, Papadias D, Hadjieleftheriou M. Conceptualpartitioning: An efficient method for continuous nearestneighbor monitoring[C]. Proceedings of the 2005ACM SIGMOD International Conference on Managementof Data, 2005,634-645.

[38] Demiryurek U, Banaei-Kashani F, Shahabi C. Efficientcontinuous nearest neighbor query in spatial networks usingeuclidean restriction[J]. Advances in Spatial and TemporalDatabases, 2009(5644):25-43.

[39] Huang Y K, Chen Z W, Lee C. Continuous k-nearestneighbor query over moving objects in road networks[J].Advances in Data and Web Management, 2009(5446):27-38.

[40] Jang S M, Yoo J S. Processing continuous skyline queriesin road networks[C]. Computer Science and Its Applications,2008,353-356.

[41] Yiu M L, Mamoulis N, Papadias D. Aggregate nearestneighbor queries in road networks[J]. IEEE Transactionson Knowledge and Data Engineering, 2005,17(6):820-833.

[42] Sistla A P, Wolfson O. Temporal triggers in active databases[J]. IEEE Transactions on Knowledge and Data Engineering,1995,7(3):471-486.

[43] Jensen C, Pedersen T, Spei?ys L et al. Data modeling formobile services in the real world[J]. Advances in Spatialand Temporal Databases, 2003(2750):1-9.

[44] Gupta S, Kopparty S, Ravishankar C. Roads, codes, andspatiotemporal queries[C]. Proceedings of the Twenty-third ACM SIGMOD-SIGACT-SIGART Symposiumon Principles of Database Systems, 2004,115-124.

[45] Hage C, Jensen C S, Pedersen T B et al. Integrated datamanagement for mobile services in the real world[C]. Proceedingsof the 29th International Conference on VeryLarge Data Bases, 2003,1019-1030.

[46] Shekhar S, Yoo J S. Processing in-route nearest neighborqueries: A comparison of alternative approaches[C]. Proceedingsof the 11th ACM International Symposium onAdvances in Geographic Information Systems, 2003,9-16.

[47] Le T T T, Nickerson B G. A data structure for I/O efficientsearch of objects moving on a graph[R]. Canada:Faculty of Computer Science, University of New Brunswick,2009,1-13.

[48] Vazirgiannis M, Wolfson O. A spatiotemporal model andlanguage for moving objects on road networks[J]. Advancesin Spatial and Temporal Databases, 2001(2121):20-35.

[49] Brinkhoff T. A framework for generating network-basedmoving objects[J]. GeoInformatica, 2002,6(2):153-180.

[50] Ding Z, Güting R. Modeling temporally variable transportationnetworks[J]. Database Systems for Advanced Applications,2004(2973):651-724.

[51] Ding Z, Guting R H. Managing moving objects on dynamictransportation networks[C]. 16th International Conferenceon Scientific and Statistical Database Management,2004,287-296.

[52] Frentzos E. Indexing objects moving on fixed networks[J]. Advances in Spatial and Temporal Databases, 2003(2750):289-305.

[53] Almeida V T D, Guting R H, IV P I. Indexing the trajectoriesof moving objects in networks[J]. GeoInformatica.20059(1):33-60.

[54] Roh G P, Roh J W, Hwang S W, et al. Supporting pattern-matching queries over trajectories on road networks[J]. IEEE Transactions on Knowledge and Data Engineering,2011, 23(11): 1753-1758.

[55] Huang Y K, Lin L F, Chung Y C, et al. Continuousmin-max distance bounded query in road networks[J].Web Technologies and Applications, 2012(7235):423-434.

[56] Liu F, Hua K A. Moving query monitoring in spatial networkenvironments[J]. Mobile Networks and Applications,2012,17(2):234-254.

[57] Jeung H, Yiu M L, Zhou X, et al. Path prediction and predictiverange querying in road network databases[J]. TheVLDB Journal, 2010,19(4):585-602.

[58] Papadias D, Zhang J, Mamoulis N, et al. Query processingin spatial network databases[C]. Proceedings of the29th International Conference on Very Large Data Bases,2003,802-813.

[59] Spei?vcys L, Jensen C S, Kligys A. Computational datamodeling for network-constrained moving objects[C].Proceedings of the 11th ACM International Symposiumon Advances in Geographic Information Systems, 2003,118-125.

[60] Spei?ys L, Jensen C S. Enabling location-based services—multi-graph representation of transportation networks[J].GeoInformatica, 2008,12(2):219-253.

[61] Jensen C S, Kolá?vr J, Pedersen T B, et al. Nearest neighborqueries in road networks[C]. Proceedings of the 11thACM International Symposium on Advances in GeographicInformation Systems,2003,1-8.

[62] Chen J, Meng X, Guo Y, et al. Modeling and predictingfuture trajectories of moving objects in a constrained network[C]. The 7th International Conference on Mobile DataManagement, 2006,156-156.

[63] 陆锋,周成虎,万庆.基于特征的城市交通网络非平面数据模型[J].测绘学报,2000(4):334-341.

[64] Xu J, Güting R H. Manage and query generic moving objectsin SECONDO[J]. Proceedings of the VLDB Endowment,2012,5(12):2002-2005.

[65] Xu J, Güting R H. A generic data model for moving objects[J]. GeoInformatica, 2012,17(1):125-172.

[66] Qi L, Schneider M. MONET: Modeling and queryingmoving objects in spatial networks[C]. ACM SIGSPATIALInternational Workshop on GeoStreaming (IWGS),2012.

[67] Ding Z, Huang G. Real-time traffic flow statistical analysisbased on network-constrained moving object trajecto-ries[J]. Database and Expert Systems Applications, 2009(5690):173-183.

[68] Kim D O, Lee K J, Hong D S, et al. An efficient indexingtechnique for location prediction of moving objects[J].Knowledge-Based Intelligent Information and EngineeringSystems, 2007(4693):1-9.

[69] Kolahdouzan M, Shahabi C. Voronoi-based k nearestneighbor search for spatial network databases[C]. Proceedingsof the Thirtieth International Conference onVery Large Data Bases, 2004(30):840-851.

[70] Huang X, Jensen C, ?altenis S. The islands approach tonearest neighbor querying in spatial networks[J]. Advancesin Spatial and Temporal Databases, 2005(3633):73-90.

[71] Bok K, Yoon H, Seo D, et al. Indexing the current positionsof moving objects on road networks[J]. Advances inWeb and Network Technologies, and Information Management,2007(4537):247-252.

[72] Sandu Popa I, Zeitouni K. Modeling and querying mobilelocation sensor data[C]. The Fourth International Conferenceon Advanced Geographic Information Systems, Applications,and Services, 2012, 222-231.

[73] Güting R H, B?hlen M H, Erwig M, et al. A foundationfor representing and querying moving objects[J]. ACMTransactions on Database Systems (TODS), 2000,25(1):1-42.

[74] Parent C, Spaccapietra S, Renso C, et al. Semantic trajectoriesmodeling and analysis[J]. ACM Computing Surveys,201345(4):39-76.

[75] Spaccapietra S, Parent C. Adding meaning to your steps(Keynote Paper)[C]. International Conference on ConceptualModeling,2011,13-31.

[76] Li Z, Ding B, Han J, et al. Mining periodic behaviors formoving objects[C]. Proceedings of the 16th ACM SIGKDDInternational Conference on Knowledge Discoveryand Data Mining, 2010,1099-1108.

[77] Huang Y, Chen C, Dong P. Modeling herds and theirevolvements from trajectory data[J]. Geographic InformationScience, 2008(5266):90-105.

[78] Li Z, Ding B, Han J, et al. Swarm: Mining relaxed temporalmoving object clusters[J]. Proceedings of the VLDBEndowment, 2010,3(1-2):723-734.

[79] Benkert M, Gudmundsson J, Hübner F, et al. Reportingflock patterns[J]. Computational Geometry, 2008, 41(3):111-125.