面向时态查询的移动对象索引技术研究
|
摘要
随着定位技术与无线通信技术的迅速发展,跟踪与定位移动对象成为可能,如何有效地对移动对象进行管理、查询及提供准确的基于位置的服务是移动对象数据库研究面临的挑战。移动对象信息管理在交通监测、舰船导航、移动计算、气象预测、电子战场等许多领域有着广泛的应用。移动对象索引技术具有重要的理论和实际意义。目前移动对象数据库的研究处于初步阶段,理论和实际应用上还不成熟,存在许多问题需要新技术来解决。
移动对象索引技术得到了国内外研究者的广泛关注。对现有相关工作的分析与比较发现:越来越多的应用要求数据管理系统能够查询移动对象过去、现在和将来信息。为了满足统一查询的需求,提出了一种面向时态查询的索引结构FT树,支持全时态信息的查询,适应频繁更新的环境。
本文首先综述了移动对象索引的演变与发展历史,全面地总结和对比分析了国内外移动对象索引的研究工作。然后提出了面向时态查询的索引结构FT树:将多版本思想引入TPR树中,对支持将来查询的TPR树进行了改进,有效地保存TPR树的各个版本,支持全时态查询;同时,引入重叠技术,避免了结点的复制,节省磁盘存储空间。为了适应频繁更新的环境,采用批量更新技术,有效地利用不同对象位置更新之间的空间相关性,降低了更新代价。引入一个二级索引结构,实现叶结点的直接存取。接着建立了代价模型和选择性估计的数学模型,从理论角度评价FT树的性能,模型的优点是只采用了树的基本属性和数据本身的特点,实验证实了模型有较高的准确率。最后采用实验方法评价FT树的性能,生成移动对象数据,以索引大小、查询性能及更新性能等指标与其它的索引结构进行比较。实验表明,FT树索引占用磁盘空间较小,磁盘利用率较高,时间片查询性能很好,时间段查询性能一般,更新性能有显著提高,在不同的数据集上表现稳定,从而验证了索引技术的有效性。
With the rapid development of positioning and wireless communication technique, it is possible to track and position moving objects. What the challenge that moving object databases face is how to effectively manage and query moving objects and offer exact location based services. Managing moving objects’information is widely used in many fields, such as traffic monitoring, ship navigation, moving computing, weather forecasting, electronic battle, etc. Moving object indexing technique has vital theoretic and practical sense. It is immature and has many problems to solve.
Researchers pay much attention to moving object index. Based on the analysis of existing work, there are increasing demands in data management systems to support querying the past, present and future information of moving objects. To satisfy the unified query demand, propose an index structure named FT-tree towards temporal query, which supports full temporal information query and is adaptive in frequently updating environment.
Summarize and analyze the evolvement and progress of moving object indices. Then propose index towards temporal query. FT-tree introduces the multi-version idea into TPR-tree, effectively preserves each edition of TPR-tree and supports full temporal query, which introduces the overlapping technique, avoids node replication and saves disk storage. FT-tree adopts bulk-loading updating technique, which effectively uses the space relativity of various objects, reduces updating cost, and introduces a secondary index for directly reading and writing leaf nodes. Construct cost model and selectivity estimation for theoretic analysis. The model’s advantage is only using tree’s attribute and data’s property. Generate moving objects data and compare the FT-tree with other indices by index size, query and updating performance. Experiments show FT-tree’s validity. It occupies less disk space, uses higher disk space, has better timeslice query, but has common time interval query, remarkably enhances updating performance, and performs well on various data set.
移动对象索引技术得到了国内外研究者的广泛关注。对现有相关工作的分析与比较发现:越来越多的应用要求数据管理系统能够查询移动对象过去、现在和将来信息。为了满足统一查询的需求,提出了一种面向时态查询的索引结构FT树,支持全时态信息的查询,适应频繁更新的环境。
本文首先综述了移动对象索引的演变与发展历史,全面地总结和对比分析了国内外移动对象索引的研究工作。然后提出了面向时态查询的索引结构FT树:将多版本思想引入TPR树中,对支持将来查询的TPR树进行了改进,有效地保存TPR树的各个版本,支持全时态查询;同时,引入重叠技术,避免了结点的复制,节省磁盘存储空间。为了适应频繁更新的环境,采用批量更新技术,有效地利用不同对象位置更新之间的空间相关性,降低了更新代价。引入一个二级索引结构,实现叶结点的直接存取。接着建立了代价模型和选择性估计的数学模型,从理论角度评价FT树的性能,模型的优点是只采用了树的基本属性和数据本身的特点,实验证实了模型有较高的准确率。最后采用实验方法评价FT树的性能,生成移动对象数据,以索引大小、查询性能及更新性能等指标与其它的索引结构进行比较。实验表明,FT树索引占用磁盘空间较小,磁盘利用率较高,时间片查询性能很好,时间段查询性能一般,更新性能有显著提高,在不同的数据集上表现稳定,从而验证了索引技术的有效性。
With the rapid development of positioning and wireless communication technique, it is possible to track and position moving objects. What the challenge that moving object databases face is how to effectively manage and query moving objects and offer exact location based services. Managing moving objects’information is widely used in many fields, such as traffic monitoring, ship navigation, moving computing, weather forecasting, electronic battle, etc. Moving object indexing technique has vital theoretic and practical sense. It is immature and has many problems to solve.
Researchers pay much attention to moving object index. Based on the analysis of existing work, there are increasing demands in data management systems to support querying the past, present and future information of moving objects. To satisfy the unified query demand, propose an index structure named FT-tree towards temporal query, which supports full temporal information query and is adaptive in frequently updating environment.
Summarize and analyze the evolvement and progress of moving object indices. Then propose index towards temporal query. FT-tree introduces the multi-version idea into TPR-tree, effectively preserves each edition of TPR-tree and supports full temporal query, which introduces the overlapping technique, avoids node replication and saves disk storage. FT-tree adopts bulk-loading updating technique, which effectively uses the space relativity of various objects, reduces updating cost, and introduces a secondary index for directly reading and writing leaf nodes. Construct cost model and selectivity estimation for theoretic analysis. The model’s advantage is only using tree’s attribute and data’s property. Generate moving objects data and compare the FT-tree with other indices by index size, query and updating performance. Experiments show FT-tree’s validity. It occupies less disk space, uses higher disk space, has better timeslice query, but has common time interval query, remarkably enhances updating performance, and performs well on various data set.
引文
[1] Schneider W. The Future of the Global Positioning System[R]. Technical Report the Defense Science Board (DSB), 2005.
[2]王家耀,魏海平,成毅等.时空GIS的研究与进展[J].海洋测绘. 2004, 24(5): 1~4.
[3]龚健雅.当代地理信息系统进展综述[J].测绘与空间地理信息. 2004, 27(1): 5~11.
[4]孟小峰,周龙骧,王珊.数据库技术发展趋势[J].软件学报. 2004, 15(12): 1822~1836.
[5] Wolfson O, Xu B, Chamberlain S, et al. Moving Objects Databases:Issues and Solutions[C]. In Proceedings of the 10th International Conference on Scientific and Statistical Database Management (SSDM). 1998. 111~122.
[6] Wolfson O. Moving Objects Information Management: The Database Challenge[C]. In Workshop on Next Generation Information Technologies and Systems (NGITS). 2002. 75~89.
[7]郭薇,郭菁,胡志勇.空间数据库索引技术[M].上海:上海交通大学出版社, 2006.
[8] Jensen C S, Christensen A F, Pedersen T B, et al. Location Based Services: A Database Perspective[C]. In The 8th Scandinavian Research Conference on Geographical Information Science (ScanGIS). Norway: 2001. 59~68.
[9]王家耀.地理信息系统的发展及其在信息战中的应用[J].信息工程大学学报. 2004, 5(2): 103~106.
[10]全线通移动信息管理系统:http://wwashington.51.net/resume/mirror/omnitracs.htm
[11] Gaede V, Gunther O. Mulidimensional Access Methods[J]. ACM Computing Surveys. 1998, 30(2): 170~231.
[12]孟凡荣,闫秋艳.多版本TPR树[J].计算机工程与应用. 2004(11): 180～182.
[13] Geraldo Z, Moreira S J. The Temporal R-tree[C]. In Programa de Engenharia de Sistemas e Computacao, ES-492/99. 1999.
[14] Saltenis S, Jensen C S, Leutenegger S T. Indexing the Position of Continuously Moving Objects[C]. In Proceedings of the ACM International Conference on Management of Data (SIGMOD). 2000. 331~342.
[15]翁敬农.移动对象及其时空模型的研究[C].中国地理信息系统协会第九届年会.杭州: 2005.
[16] Erwig M, Guting R H, Schneider M. Spatio-temporal Data Types: an Approach to Modeling and Querying Moving Objects in Databases[J]. GeoInformation. 1999, 3(3): 269~296.
[17]汤庸,汤娜,叶小平.时态信息处理技术研究综述[J].中山大学学报(自然科学版). 2003, 42(4): 4~8.
[18] Pfoser D, Jensen C S, Yannis T. Novel Approaches in Query Processing for Moving Object Trajectories[C]. In Proceedings of the 26th International Conference on Very Large Data Bases (VLDB). Cairo, Egypt: 2000. 395~406.
[19] Theodoridis Y, Sellis T, Papadopoulos A N, et al. Specifications for Efficient Indexing in Spatiotemporal Databases[C]. In Proceedings of the International Conference on Scientific and Statistical Database Management (SSDM). 1998. 123~132.
[20] Chakka V P, Everspaugh A, Patel J M. Indexing Large Trajectory Data Sets With SETI[C]. In Proceedings of the Conference on Innovative Data Systems Research (CIDR). Asilomar, CA: 2003.
[21] Xu X, Han J, Lu W. RT-Tree: An Improved R-Tree Indexing Structure for Temporal Spatial Databases[C]. In Proceedings of the International Symposium on Spatial Data Handling (SDH). 1990. 1040~1049.
[22] Theoderidis Y, Vazirgiannis M, Sellis T. Spatio-temporal Indexing for Large Multimedia Applications[C]. In Proceedings of the 3rd IEEE International Conference on Multimedia Computing and Systems (ICMCS). 1996. 441~448.
[23] Nascimento M, Silva J. Towards Historical R-trees[C]. In Proceedings of ACM Symposium on Applied Computing (ACM-SAC). 1998. 235~240.
[24] Tayeb J, Ulusoy O, Wolfson O. A Quadtree Based Dynamic Attribute Indexing Method[J]. The Computer Journal. 1998, 41(3): 185~200.
[25] Saltenis S, Jensen C. Indexing of Now-relative Spatio-Bitemporal Data[J]. The VLDB Journal. 2002, 11(1): 1~16.
[26] Mokbel M F, Ghanem T M, Aref W G. Spatio-temporal Access Methods[J]. IEEE Data Engineering Bulletin. 2003, 26(2): 40~49.
[27] Guttman A. R-trees: A Dynamic Index Structure for Spatial Searching[C]. In Proceedings of International Conference on Management of Data (SIGMOD). 1984. 47~57.
[28] Song Z, Roussopoulos N. SEB-tree: An Approach to Index Continuously Moving Objects[C]. In Proceedings of Conference on Mobile Data Management (MDM). 2003. 340~344.
[29] Frentzos E. Indexing Objects Moving on Fixed Networks[C]. In Proceedings of the International Symposium on Advances in Spatial and Temporal Databases (SSTD). 2003. 289~305.
[30] Almeida V T, Guting R H. Indexing the Trajectories of Moving Objects in Networks[C]. In Proceedings of the 16th International Conference on Scientific and Statistical Database Management (SSDBM). 2004. 115~118.
[31] Gupta S, Ravishankar C. Using vTree Indices for Queries over Objects with Complex Motions[C]. In Proceedings of the 20th International Conference on Data Engineering (ICDE).2004.
[32] Lee E J, Ryu K H, Nam K W. Indexing for Efficient Managing Current and Past Trajectory of Moving Object[C]. In the Asia Pacific Web Conference (APWeb). Hangzhou,China: 2004. 782~787.
[33]李国徽,钟细亚.一种基于固定网络的移动对象运动轨迹索引模型[J].计算机研究与发展. 2006, 43(5): 828~833.
[34]卢炎生,彭祥礼,潘鹏.一种动态紧缩的移动对象索引结构[J].华中科技大学学报(自然科学版). 2007, 25(2): 50~53.
[35] Beckmann N, Kriegel H P, Schneider R, et al. The R*-tree: An Efficient and Robust Access Method for Points and Rectangles[C]. In Proceedings of ACM International Conference on Management of Data (SIGMOD). 1990. 322~331.
[36] Jinfeng N, Chinya V R. Indexing Spatio-Temporal Trajectories with Efficient Polynomial Approximations[J]. IEEE Transactions on Knowledge and Data Engineering (TKDE). 2007, 19(5): 663~678.
[37] Lomet D B, Salzberg B. Access Methods for Multiversion Data[C]. In Proceedings of the ACM International Conference on Management of Data (SIGMOD). 1989. 315~324.
[38] Burton F W, Kollias J G, Matsakis D G, et al. Implementation of Overlapping B-tree for Time and Space Efficient Representation of Collections of Similar Files[J]. The Computer Journal. 1990, 33(3): 279~280.
[39] Finkel R A, Bentley J L. Quadtrees: A Data Structure for Retrieval on Composite Keys[J]. Acta Informatica. 1974, 4(1): 1~9.
[40] Tzouramanis T, Vassilakopoulos M, Manolopoulos Y. Overlapping Linear Quadtrees: A Spatio-Temporal Access Method[C]. In Proceedings of the ACM workshop on Advances in GIS. (ACM GIS). 1998. 1~7.
[41] Tao Y, Papadias D. Efficient Historical R-trees[C]. In Proceedings of the International Conference on Scientific and Statistical Database Management (SSDBM). 2001. 223~232.
[42] Kollios G, Tsotras V J, Gunopulos D, et al. Indexing Animated Objects Using Spatiotemporal Access Methods[J]. IEEE Transactions on Knowledge and Data Engineering (TKDE). 2001(5): 758~777.
[43] Kumar A, Tsotras V J, Faloutsos C. Designing Access Methods for Bitemporal Databases[J]. IEEE Transactions on Knowledge and Data Engineering (TKDE). 1998, 10(1): 1~20.
[44] Hadjieleftheriou M, Kollios G, Tsotras V J, et al. Efficient Indexing of Spatiotemporal Objects[C]. In Proceedings of the International Conference onExtending Database Technology (EDBT). 2002. 251~268.
[45] Tao Y, Papadias D. MV3R-Tree: A Spatio-Temporal Access Method for Timestamp and Interval Queries[C]. In Proceedings of the 27th International Conference on Very Large Databases (VLDB). 2001. 431~440.
[46] Becker B, Gschwind S, Ohler T, et al. An Asymptotically Optimal Multiversion B-Tree[J]. VLDB Journal. 1996, 5(4): 264~257.
[47] Min J K, Cho H J, Chung C W. An Adaptive Indexing Technique Using Spatio-temporal Query Workloads[J]. Infomation and Software Technology. 2004, 46(4): 229~241.
[48] Gilberto G R, Gonzalo N, Andrea R T, et al. A Spatiotemporal Access Method based on Snapshots and Events[C]. In Proceedings of the ACM workshop on Advances in GIS. (ACM GIS).2005.
[49] Song Z, Roussopoulos N. Hashing Moving Objects[C]. In Proceedings of IEEE International of Conference on Mobile Data Management (MDM). 2001. 331~342.
[50] Kyoung-sook K, Si-wan K, Tae-wan K, et al. Fast Indexing and Updating Method for Moving Objects on Road Networks[C]. In Proceedings of the 4th International Conference on Web Information Systems Engineering Workshops (WISEW). 2003. 34~42.
[51] Abdelguerfi M, Givaudan J, Shaw K, et al. The 2-3 TR-tree: A Trajectory-Oriented Index Structure for Fully Evolving Valid-time Spatio-temporal Datasets[C]. In Proceedings of the ACM workshop on Advances in GIS. (ACM GIS). 2002. 29~34.
[52] Nascimento M A, Silva J R, Theodoridis Y. Evaluation of Acess Structures for Discretely Moveing Points[C]. In Workshop on Spatio-Temporal Database Management (STDBM). 1999.
[53] Kwon D, Lee S, Lee S. Indexing the Current Positions of Moving Objects Using the Lazy Update R-tree[C]. In Proceedings of the 3rd IEEE International of Conference on Mobile Data Management (MDM). 2002. 113~120.
[54] Lee M, Hsu W, Jensen C, et al. Supporting Frequent Updates in R-Trees: A Bottom-Up Approach[C]. In Proceedings of the International Conference on Very Large Data Bases (VLDB). 2003.
[55] Xia Y, Prabhakar S. Q+Rtree: Efficient Indexing for Moving Object Databases[C]. In Proceedings of the International Conference on Database Systems for Advanced Applications (DASFAA). 2003. 1~8.
[56] Kun-lung W, Shyh-kwei C, Philip S Y. Indexing Continual Range Queries for Location-Aware Mobile Services[C]. In Proceedings of the IEEE International Conference on e-Technology, e-Commerce and e-Service (EEE). 2004. 233~240.
[57] Lin B, Su J. Handling Frequent Updates of Moving Objects[C]. In ACMConference on Information and Knowledge Management (CIKM). 2005. 493~500.
[58] Kwon D, Lee S J, Choi W. An Adaptive Hashing Technique for Indexing Moving Objects[J]. IEEE Transactions on Knowledge and Data Engineering (TKDE). 2006, 56(3): 287~303.
[59] Kollios G, Gunopulos D, Tsotras V J. On Indexing Mobile Objects[C]. In Proceedings of the ACM Symposium on Principles of Database Systems (PODS). 1999. 261~272.
[60] Bentley J L. Multidimensional Binary Search Trees Used for Associative Searching[J]. Communications of the ACM. 1975, 18(9): 509~517.
[61] Agarwal P K, Arge L, J E. Indexing Moving Points[C]. In Proceedings of the ACM Symposium on Principles of Database Systems (PODS). 2000. 175~186.
[62] Basch J, Guibas L J, Hershberger J. Data Structure for Mobile Data[C]. In Proceedings of the ACM-SIAM Symposium on Discrete algorithm (SODA). 1997. 747~756.
[63] Chon H D, Agrawal D, Abbadi A E. Storage and Retrieval of Moving Objects[C]. In Proceedings of International of Conference on Mobile Data Management (MDM). 2001. 173~184.
[64] White D A, Jain R. Similarity Indexing with the SS-tree[C]. In Proceedings of International Conference on Data Engineering (ICDE). 1996. 516~523.
[65] Porkaew K, Lazaridis I, Mehrotra S. Querying Mobile Objects in Spatio-Temporal Databases[C]. In Proceedings of the International Symposium on Advances in Spatial and Temporal Databases (SSTD). Redondo Beach, CA: 2001. 59~78.
[66] Ding R, Meng X F, Bai Y. Efficient Index Update for Moving Objects with Future Trajectories[C]. In Proceedings of the International Conference on Database System for Advanced Applications (DASFAA). 2003.
[67] Jense C S, Lin D, Ooi B C. Query and Update Efficient B+tree Based Indexing of Moving Objects[C]. In Proceedings of the 30th International Conference on Very Large Data Bases (VLDB). 2004. 768~779.
[68] Tao Y, Faloutsos C, Papadias D, et al. Prediction and Indexing of Moving Objects with Unknown Motion Patterns[C]. In Proceedings of the ACM International Conference on Management of Data (SIGMOD). 2004.
[69] Cai M, Revesz P. Parametric R-Tree: An Index Structure for Moving Objects[C]. In Advances in Data Management. 2000.
[70] Prabhakar S, Xia Y, Kalashnikov D V, et al. Query Indexing and Velocity Constrained Indexing: Scalable Techniques for Continuous Queries on Moving Objects[J]. IEEE Transactions on Computers. 2002: 1124~1140.
[71] Saltenis S, Jensen C S. Indexing of Moving Objects for Location-BasedServices[C]. In Proceedings of the International Conference on Data Engineering (ICDE). 2002.
[72] Procopiuc C M, Agarwal P K, Har-peled S. STAR-Tree: An Efficient Self-Adjusting Index for Moving Objects[C]. In Proceedings of the Workshop on Algorithm Engineering and Experimentation (ALENEX). 2002. 178~193.
[73] Tao Y, Papadias D, J S. The TPR*-Tree: An Optimized Spatio-temporal Access Method for Predictive Queries[C]. In Proceedings of the International Conference on Very Large Data Bases (VLDB). 2003.
[74] Patel J M, Chen Y, Chakka V P. STRIPES: An Efficient Index for Predicted Trajectories[C]. In Proceedings of the ACM International Conference on Management of Data (SIGMOD). 2004.
[75]廖巍,熊伟,景宁等.支持频繁更新的移动对象混合索引方法[J].计算机研究与发展. 2006, 43(5): 888~893.
[76] Chen S, Ooi B C, Tan K L, et al. ST2B-tree: A Self-Tunable Spatio-Temporal B+-tree Index for Moving Objects[C]. In Proceedings of the ACM International Conference on Management of Data (SIGMOD). 2008.
[77] Yiu M L, Tao Y, Mamoulis N. The Bdual-Tree: Indexing Moving Objects by Space Filling Curves in the Dual Space[C]. In Encyclopedia of GIS 2008. 2008. 497~502.
[78] Liu Z, Xiaoli L, Junwei G, et al. Indexing Large Moving Objects from Past to Future with PCFI-Index[C]. In Advances in Data Management. 2005. 131~137.
[79] Pelanis M, Saltenis S, Jensen C S. Indexing the Past, Present, and Anticipated Future Positions of Moving Objects[J]. ACM Transactions on Database Systems (TODS). 2006, 31(1): 255~298.
[80]刘晓军.一种高效的移动对象位置索引机制的研究[D].硕士,山东大学, 2007.
[81]李东,彭宇辉,殷江龙.基于Quadtree和Hash表的移动对象全时态索引[J].计算机工程. 2009, 35(7).
[82] Arge L, Hinrichs K H, Vahrenhold J, et al. Efficient Bulk Operations on Dynamic R-trees[C]. In Workshop on Algorithm Engineering and Experimentation (ALENEX). 1999.
[83] Bercken V D J, Seeger B. An Evaluation of Generic Bulk Loading Techniques[C]. In Proceedings of the 27th International Conference on Very Large Data Bases (VLDB). 2001.
[84] Lin B, Su J W. On Bulk Loading TPR-Tree[C]. In Proceedings of the 2004 IEEE International of Conference on Mobile Data Management (MDM).2004.
[85] Theodoridis Y, Selis T. A Model for the Prediction of R-tree Performance[C]. In Proceedings of Symposium on Principles of Database Systems (PODS). 1996. 161~171.
[86] Tao Y, Papadias D, Zhang J. Cost Models for Overlapping and Multi-Version B-trees[C]. In Proceedings of the 18th International Conference on Data Engineering (ICDE).2002.
[87] Choi Y J, Ki M J, Chung C W. A Cost Model for Spatio-Temporal Queries Using the TPR-tree[J]. Journal of Systems and Software. 2004, 73(1): 101~112.
[88] Theodoridis Y, Sellis T. Efficient Cost Models for Spatial Queries Using R-Trees[J]. IEEE Transactions on Knowledge and Data Engineering (TKDE). 2000, 12(1).
[89] Yao S B. Approximating Block Accessess in Database Organizations[J]. Communications of the ACM. 1977, 20(4): 260~261.
[90] Tiger数据集:http://www.census.gov/geo/www/tiger
[91] Theodoridis Y, Silva J R, Nascimento M A. On the Generation of Spatio-temporal Datasets[C]. In the 6th International Symposium on the Advances in Spatial Databases. 1999. 147~164.
[2]王家耀,魏海平,成毅等.时空GIS的研究与进展[J].海洋测绘. 2004, 24(5): 1~4.
[3]龚健雅.当代地理信息系统进展综述[J].测绘与空间地理信息. 2004, 27(1): 5~11.
[4]孟小峰,周龙骧,王珊.数据库技术发展趋势[J].软件学报. 2004, 15(12): 1822~1836.
[5] Wolfson O, Xu B, Chamberlain S, et al. Moving Objects Databases:Issues and Solutions[C]. In Proceedings of the 10th International Conference on Scientific and Statistical Database Management (SSDM). 1998. 111~122.
[6] Wolfson O. Moving Objects Information Management: The Database Challenge[C]. In Workshop on Next Generation Information Technologies and Systems (NGITS). 2002. 75~89.
[7]郭薇,郭菁,胡志勇.空间数据库索引技术[M].上海:上海交通大学出版社, 2006.
[8] Jensen C S, Christensen A F, Pedersen T B, et al. Location Based Services: A Database Perspective[C]. In The 8th Scandinavian Research Conference on Geographical Information Science (ScanGIS). Norway: 2001. 59~68.
[9]王家耀.地理信息系统的发展及其在信息战中的应用[J].信息工程大学学报. 2004, 5(2): 103~106.
[10]全线通移动信息管理系统:http://wwashington.51.net/resume/mirror/omnitracs.htm
[11] Gaede V, Gunther O. Mulidimensional Access Methods[J]. ACM Computing Surveys. 1998, 30(2): 170~231.
[12]孟凡荣,闫秋艳.多版本TPR树[J].计算机工程与应用. 2004(11): 180～182.
[13] Geraldo Z, Moreira S J. The Temporal R-tree[C]. In Programa de Engenharia de Sistemas e Computacao, ES-492/99. 1999.
[14] Saltenis S, Jensen C S, Leutenegger S T. Indexing the Position of Continuously Moving Objects[C]. In Proceedings of the ACM International Conference on Management of Data (SIGMOD). 2000. 331~342.
[15]翁敬农.移动对象及其时空模型的研究[C].中国地理信息系统协会第九届年会.杭州: 2005.
[16] Erwig M, Guting R H, Schneider M. Spatio-temporal Data Types: an Approach to Modeling and Querying Moving Objects in Databases[J]. GeoInformation. 1999, 3(3): 269~296.
[17]汤庸,汤娜,叶小平.时态信息处理技术研究综述[J].中山大学学报(自然科学版). 2003, 42(4): 4~8.
[18] Pfoser D, Jensen C S, Yannis T. Novel Approaches in Query Processing for Moving Object Trajectories[C]. In Proceedings of the 26th International Conference on Very Large Data Bases (VLDB). Cairo, Egypt: 2000. 395~406.
[19] Theodoridis Y, Sellis T, Papadopoulos A N, et al. Specifications for Efficient Indexing in Spatiotemporal Databases[C]. In Proceedings of the International Conference on Scientific and Statistical Database Management (SSDM). 1998. 123~132.
[20] Chakka V P, Everspaugh A, Patel J M. Indexing Large Trajectory Data Sets With SETI[C]. In Proceedings of the Conference on Innovative Data Systems Research (CIDR). Asilomar, CA: 2003.
[21] Xu X, Han J, Lu W. RT-Tree: An Improved R-Tree Indexing Structure for Temporal Spatial Databases[C]. In Proceedings of the International Symposium on Spatial Data Handling (SDH). 1990. 1040~1049.
[22] Theoderidis Y, Vazirgiannis M, Sellis T. Spatio-temporal Indexing for Large Multimedia Applications[C]. In Proceedings of the 3rd IEEE International Conference on Multimedia Computing and Systems (ICMCS). 1996. 441~448.
[23] Nascimento M, Silva J. Towards Historical R-trees[C]. In Proceedings of ACM Symposium on Applied Computing (ACM-SAC). 1998. 235~240.
[24] Tayeb J, Ulusoy O, Wolfson O. A Quadtree Based Dynamic Attribute Indexing Method[J]. The Computer Journal. 1998, 41(3): 185~200.
[25] Saltenis S, Jensen C. Indexing of Now-relative Spatio-Bitemporal Data[J]. The VLDB Journal. 2002, 11(1): 1~16.
[26] Mokbel M F, Ghanem T M, Aref W G. Spatio-temporal Access Methods[J]. IEEE Data Engineering Bulletin. 2003, 26(2): 40~49.
[27] Guttman A. R-trees: A Dynamic Index Structure for Spatial Searching[C]. In Proceedings of International Conference on Management of Data (SIGMOD). 1984. 47~57.
[28] Song Z, Roussopoulos N. SEB-tree: An Approach to Index Continuously Moving Objects[C]. In Proceedings of Conference on Mobile Data Management (MDM). 2003. 340~344.
[29] Frentzos E. Indexing Objects Moving on Fixed Networks[C]. In Proceedings of the International Symposium on Advances in Spatial and Temporal Databases (SSTD). 2003. 289~305.
[30] Almeida V T, Guting R H. Indexing the Trajectories of Moving Objects in Networks[C]. In Proceedings of the 16th International Conference on Scientific and Statistical Database Management (SSDBM). 2004. 115~118.
[31] Gupta S, Ravishankar C. Using vTree Indices for Queries over Objects with Complex Motions[C]. In Proceedings of the 20th International Conference on Data Engineering (ICDE).2004.
[32] Lee E J, Ryu K H, Nam K W. Indexing for Efficient Managing Current and Past Trajectory of Moving Object[C]. In the Asia Pacific Web Conference (APWeb). Hangzhou,China: 2004. 782~787.
[33]李国徽,钟细亚.一种基于固定网络的移动对象运动轨迹索引模型[J].计算机研究与发展. 2006, 43(5): 828~833.
[34]卢炎生,彭祥礼,潘鹏.一种动态紧缩的移动对象索引结构[J].华中科技大学学报(自然科学版). 2007, 25(2): 50~53.
[35] Beckmann N, Kriegel H P, Schneider R, et al. The R*-tree: An Efficient and Robust Access Method for Points and Rectangles[C]. In Proceedings of ACM International Conference on Management of Data (SIGMOD). 1990. 322~331.
[36] Jinfeng N, Chinya V R. Indexing Spatio-Temporal Trajectories with Efficient Polynomial Approximations[J]. IEEE Transactions on Knowledge and Data Engineering (TKDE). 2007, 19(5): 663~678.
[37] Lomet D B, Salzberg B. Access Methods for Multiversion Data[C]. In Proceedings of the ACM International Conference on Management of Data (SIGMOD). 1989. 315~324.
[38] Burton F W, Kollias J G, Matsakis D G, et al. Implementation of Overlapping B-tree for Time and Space Efficient Representation of Collections of Similar Files[J]. The Computer Journal. 1990, 33(3): 279~280.
[39] Finkel R A, Bentley J L. Quadtrees: A Data Structure for Retrieval on Composite Keys[J]. Acta Informatica. 1974, 4(1): 1~9.
[40] Tzouramanis T, Vassilakopoulos M, Manolopoulos Y. Overlapping Linear Quadtrees: A Spatio-Temporal Access Method[C]. In Proceedings of the ACM workshop on Advances in GIS. (ACM GIS). 1998. 1~7.
[41] Tao Y, Papadias D. Efficient Historical R-trees[C]. In Proceedings of the International Conference on Scientific and Statistical Database Management (SSDBM). 2001. 223~232.
[42] Kollios G, Tsotras V J, Gunopulos D, et al. Indexing Animated Objects Using Spatiotemporal Access Methods[J]. IEEE Transactions on Knowledge and Data Engineering (TKDE). 2001(5): 758~777.
[43] Kumar A, Tsotras V J, Faloutsos C. Designing Access Methods for Bitemporal Databases[J]. IEEE Transactions on Knowledge and Data Engineering (TKDE). 1998, 10(1): 1~20.
[44] Hadjieleftheriou M, Kollios G, Tsotras V J, et al. Efficient Indexing of Spatiotemporal Objects[C]. In Proceedings of the International Conference onExtending Database Technology (EDBT). 2002. 251~268.
[45] Tao Y, Papadias D. MV3R-Tree: A Spatio-Temporal Access Method for Timestamp and Interval Queries[C]. In Proceedings of the 27th International Conference on Very Large Databases (VLDB). 2001. 431~440.
[46] Becker B, Gschwind S, Ohler T, et al. An Asymptotically Optimal Multiversion B-Tree[J]. VLDB Journal. 1996, 5(4): 264~257.
[47] Min J K, Cho H J, Chung C W. An Adaptive Indexing Technique Using Spatio-temporal Query Workloads[J]. Infomation and Software Technology. 2004, 46(4): 229~241.
[48] Gilberto G R, Gonzalo N, Andrea R T, et al. A Spatiotemporal Access Method based on Snapshots and Events[C]. In Proceedings of the ACM workshop on Advances in GIS. (ACM GIS).2005.
[49] Song Z, Roussopoulos N. Hashing Moving Objects[C]. In Proceedings of IEEE International of Conference on Mobile Data Management (MDM). 2001. 331~342.
[50] Kyoung-sook K, Si-wan K, Tae-wan K, et al. Fast Indexing and Updating Method for Moving Objects on Road Networks[C]. In Proceedings of the 4th International Conference on Web Information Systems Engineering Workshops (WISEW). 2003. 34~42.
[51] Abdelguerfi M, Givaudan J, Shaw K, et al. The 2-3 TR-tree: A Trajectory-Oriented Index Structure for Fully Evolving Valid-time Spatio-temporal Datasets[C]. In Proceedings of the ACM workshop on Advances in GIS. (ACM GIS). 2002. 29~34.
[52] Nascimento M A, Silva J R, Theodoridis Y. Evaluation of Acess Structures for Discretely Moveing Points[C]. In Workshop on Spatio-Temporal Database Management (STDBM). 1999.
[53] Kwon D, Lee S, Lee S. Indexing the Current Positions of Moving Objects Using the Lazy Update R-tree[C]. In Proceedings of the 3rd IEEE International of Conference on Mobile Data Management (MDM). 2002. 113~120.
[54] Lee M, Hsu W, Jensen C, et al. Supporting Frequent Updates in R-Trees: A Bottom-Up Approach[C]. In Proceedings of the International Conference on Very Large Data Bases (VLDB). 2003.
[55] Xia Y, Prabhakar S. Q+Rtree: Efficient Indexing for Moving Object Databases[C]. In Proceedings of the International Conference on Database Systems for Advanced Applications (DASFAA). 2003. 1~8.
[56] Kun-lung W, Shyh-kwei C, Philip S Y. Indexing Continual Range Queries for Location-Aware Mobile Services[C]. In Proceedings of the IEEE International Conference on e-Technology, e-Commerce and e-Service (EEE). 2004. 233~240.
[57] Lin B, Su J. Handling Frequent Updates of Moving Objects[C]. In ACMConference on Information and Knowledge Management (CIKM). 2005. 493~500.
[58] Kwon D, Lee S J, Choi W. An Adaptive Hashing Technique for Indexing Moving Objects[J]. IEEE Transactions on Knowledge and Data Engineering (TKDE). 2006, 56(3): 287~303.
[59] Kollios G, Gunopulos D, Tsotras V J. On Indexing Mobile Objects[C]. In Proceedings of the ACM Symposium on Principles of Database Systems (PODS). 1999. 261~272.
[60] Bentley J L. Multidimensional Binary Search Trees Used for Associative Searching[J]. Communications of the ACM. 1975, 18(9): 509~517.
[61] Agarwal P K, Arge L, J E. Indexing Moving Points[C]. In Proceedings of the ACM Symposium on Principles of Database Systems (PODS). 2000. 175~186.
[62] Basch J, Guibas L J, Hershberger J. Data Structure for Mobile Data[C]. In Proceedings of the ACM-SIAM Symposium on Discrete algorithm (SODA). 1997. 747~756.
[63] Chon H D, Agrawal D, Abbadi A E. Storage and Retrieval of Moving Objects[C]. In Proceedings of International of Conference on Mobile Data Management (MDM). 2001. 173~184.
[64] White D A, Jain R. Similarity Indexing with the SS-tree[C]. In Proceedings of International Conference on Data Engineering (ICDE). 1996. 516~523.
[65] Porkaew K, Lazaridis I, Mehrotra S. Querying Mobile Objects in Spatio-Temporal Databases[C]. In Proceedings of the International Symposium on Advances in Spatial and Temporal Databases (SSTD). Redondo Beach, CA: 2001. 59~78.
[66] Ding R, Meng X F, Bai Y. Efficient Index Update for Moving Objects with Future Trajectories[C]. In Proceedings of the International Conference on Database System for Advanced Applications (DASFAA). 2003.
[67] Jense C S, Lin D, Ooi B C. Query and Update Efficient B+tree Based Indexing of Moving Objects[C]. In Proceedings of the 30th International Conference on Very Large Data Bases (VLDB). 2004. 768~779.
[68] Tao Y, Faloutsos C, Papadias D, et al. Prediction and Indexing of Moving Objects with Unknown Motion Patterns[C]. In Proceedings of the ACM International Conference on Management of Data (SIGMOD). 2004.
[69] Cai M, Revesz P. Parametric R-Tree: An Index Structure for Moving Objects[C]. In Advances in Data Management. 2000.
[70] Prabhakar S, Xia Y, Kalashnikov D V, et al. Query Indexing and Velocity Constrained Indexing: Scalable Techniques for Continuous Queries on Moving Objects[J]. IEEE Transactions on Computers. 2002: 1124~1140.
[71] Saltenis S, Jensen C S. Indexing of Moving Objects for Location-BasedServices[C]. In Proceedings of the International Conference on Data Engineering (ICDE). 2002.
[72] Procopiuc C M, Agarwal P K, Har-peled S. STAR-Tree: An Efficient Self-Adjusting Index for Moving Objects[C]. In Proceedings of the Workshop on Algorithm Engineering and Experimentation (ALENEX). 2002. 178~193.
[73] Tao Y, Papadias D, J S. The TPR*-Tree: An Optimized Spatio-temporal Access Method for Predictive Queries[C]. In Proceedings of the International Conference on Very Large Data Bases (VLDB). 2003.
[74] Patel J M, Chen Y, Chakka V P. STRIPES: An Efficient Index for Predicted Trajectories[C]. In Proceedings of the ACM International Conference on Management of Data (SIGMOD). 2004.
[75]廖巍,熊伟,景宁等.支持频繁更新的移动对象混合索引方法[J].计算机研究与发展. 2006, 43(5): 888~893.
[76] Chen S, Ooi B C, Tan K L, et al. ST2B-tree: A Self-Tunable Spatio-Temporal B+-tree Index for Moving Objects[C]. In Proceedings of the ACM International Conference on Management of Data (SIGMOD). 2008.
[77] Yiu M L, Tao Y, Mamoulis N. The Bdual-Tree: Indexing Moving Objects by Space Filling Curves in the Dual Space[C]. In Encyclopedia of GIS 2008. 2008. 497~502.
[78] Liu Z, Xiaoli L, Junwei G, et al. Indexing Large Moving Objects from Past to Future with PCFI-Index[C]. In Advances in Data Management. 2005. 131~137.
[79] Pelanis M, Saltenis S, Jensen C S. Indexing the Past, Present, and Anticipated Future Positions of Moving Objects[J]. ACM Transactions on Database Systems (TODS). 2006, 31(1): 255~298.
[80]刘晓军.一种高效的移动对象位置索引机制的研究[D].硕士,山东大学, 2007.
[81]李东,彭宇辉,殷江龙.基于Quadtree和Hash表的移动对象全时态索引[J].计算机工程. 2009, 35(7).
[82] Arge L, Hinrichs K H, Vahrenhold J, et al. Efficient Bulk Operations on Dynamic R-trees[C]. In Workshop on Algorithm Engineering and Experimentation (ALENEX). 1999.
[83] Bercken V D J, Seeger B. An Evaluation of Generic Bulk Loading Techniques[C]. In Proceedings of the 27th International Conference on Very Large Data Bases (VLDB). 2001.
[84] Lin B, Su J W. On Bulk Loading TPR-Tree[C]. In Proceedings of the 2004 IEEE International of Conference on Mobile Data Management (MDM).2004.
[85] Theodoridis Y, Selis T. A Model for the Prediction of R-tree Performance[C]. In Proceedings of Symposium on Principles of Database Systems (PODS). 1996. 161~171.
[86] Tao Y, Papadias D, Zhang J. Cost Models for Overlapping and Multi-Version B-trees[C]. In Proceedings of the 18th International Conference on Data Engineering (ICDE).2002.
[87] Choi Y J, Ki M J, Chung C W. A Cost Model for Spatio-Temporal Queries Using the TPR-tree[J]. Journal of Systems and Software. 2004, 73(1): 101~112.
[88] Theodoridis Y, Sellis T. Efficient Cost Models for Spatial Queries Using R-Trees[J]. IEEE Transactions on Knowledge and Data Engineering (TKDE). 2000, 12(1).
[89] Yao S B. Approximating Block Accessess in Database Organizations[J]. Communications of the ACM. 1977, 20(4): 260~261.
[90] Tiger数据集:http://www.census.gov/geo/www/tiger
[91] Theodoridis Y, Silva J R, Nascimento M A. On the Generation of Spatio-temporal Datasets[C]. In the 6th International Symposium on the Advances in Spatial Databases. 1999. 147~164.