三维运动目标的数据组织与管理
|
摘要
无线通讯、空间定位和测量等技术的发展，使得人们对空间目标的信息管理由静态逐渐扩展到动态。特别是活动于现实三维空间的运动目标越来越受到关注。智能交通、电子战场、物流管理、移动电子商务、旅行者服务以及其它各类LBS服务都离不开高效的运动目标信息管理机制。随着三维GIS(地理信息系统)和虚拟现实技术的成熟，运动目标的信息管理也需要由原来的一维或二维扩展到三维。对运动目标的信息处理不仅涉及到空间属性，而且涉及到时间属性，因而相对复杂。然而，传统的数据库管理系统不能完全满足运动目标信息管理的需要。它们是为“静态”数据管理而设计的，数据的任何改变将导致数据库的显式更新，这与目标运动的空间状态持续变化特征不相符，而且，结构化查询语言SQL不是为处理时空数据而设计和优化的，在查询目标运动数据时有明显的不足。另一方面，目前时态数据库主要以变化相对缓慢的以统计为重要目的的数据作为管理和研究对象，它的实时性不强，而且对时间序列的管理较少涉及到空间属性。因此，有必要研究新的数据组织与处理方式来管理与运动目标相关的时空数据。本文研究的重点是三维运动目标的数据组织和管理，包括运动目标的表示和运动数据的索引技术。
对于运动目标信息管理的研究，目前普遍的方法是将运动目标抽象成空间移动的点，忽略目标的形状、大小、外观等因素，集中注意力研究目标空间状态及其变化，通过各种手段采集、传输、存储、索引、查询和处理目标的空间状态数据。在这种情况下，运动目标的表示也就简化成了目标的运动表示。现有的目标运动模型有多种，但可以归纳为点模型、时段模型、折线模型和函数模型四类。这四类模型各有特点，适于不同的应用需要，但它们多基于一维或二维运动目标的管理，要处理三维运动目标，需要做一定的扩展，而且上述所有模型中没有一个模型考虑到目标的姿态，而运动目标的姿态在决定三维目标的空间状态中也是至关重要的。本文在分析了三维运动目标的时间特性、空间特性和运动特性的基础上，改进函数模型，特别是MOST(Moving Object Spatio-Temporal)模型，消除其对运动函数所隐含的显式、增量式和分离式要求，设计了综合运动模型。并提出运动数据的细节层次概念，以不同精度和不同计算复杂度的数据及其相应的计算方法满足不同应用的需要。综合运动模型将运动数据和相关的处理用面向对象的方法进行封装，允许不同类型、不同结构的数据和不同种类的处理方式并存，适用于函数法与样本法的不同运动模型构造方式。针对多数应用系统中数据采集的方式和类型，从目标的运动位置、姿态、运动方向、速度、加速度、旋转速度、旋转加速度等各项指标及其相互关系出发，本文还提出了状态序列模型。该模型用离散的样本加上相应的插值方法，拟合目标运动的过程，对数据和处理过程进行封装，形成简洁的运动表示模型，弥补了现有模型对三维运动目标表达上的缺陷，同时还兼容对一维和二维运动目标的管理。本文还分类讨论了状态序列模型对不同运动目标的表示方式，分析了模型中所表达的信息，包括基本信息和导出信息。
在状态序列模型的基础上。本文提出了以2~n索引树为中心的多向多级运动数据索引机制。运动数据的索引依赖于所采用的运动模型，几乎每一类模型都提出了自己相应的索引方法。通过分析运动数据索引的需求发现，根据运动目标的特点和运动数据访问的需要，所采用的算法应该不仅能够对大量运动目标当前的运动状态建立索引，而且能够管理历史数据，按照运动数据模型所规定的方式提供对将来运动状态的预测。运动数据的追加是大量发生的，所以所建立的索引应该满足这种经常更新的需要，不至于频繁引起大范围或多级结点的大规模操作。运动数据的查询有多种形式，其中有快照式查询，也有连续查询。因此，所建立的索引机制应该兼顾到各种查询的方式。为了满足这些要求，本文采用空间分割的方法，扩展四叉树和八叉树，建立n维空间的2~n索引树。结合运动数据及其处理过程的特点，给出了2~n索引树的数据结构，以及树的建立、状态向量定位、添加、删除、滞后更新和树扩展等相关算法。为满足不同类型查询的需要，特别
是连续查询对于相同目标连续一段时间内运动状态的查询要求，在建立运动数据索引时，需要将
样本数据与2”索引树相分离，同时按照目标与样本时刻建立索引，从而形成多向多级的索引结
构。本文探讨了这种混合索引方式，并给出了状态样本数据的具体存储形式。
在详细分析各种运动数据访问类型的基础上，本文讨论了各种查询方式，给出了基本状态
查询和运动过程查询的方法，介绍了正向查询（目标一时刻查询）和反向查询（时间一状态查询）
的不同检索程序和步骤，详细讨论了对相容区域和相交区域查询的不同处理方式。从运动数据在
n维空间的分布和数据访问过程出发，介绍了运动目标查询的准确性问题，探讨了准确找出所有
满足条件的运动目标的不同方法，找出了前期处理法与扩展查询区域法在处理过程和效率上的不
同，分析了一般查询与精确查询在查询步骤上的区别。通过分析目标与目标之间的相互关系，提
出了目标关系查询的方法，并
With the development of wireless communication, positioning and photogrametry, people are able to expand the information management of spatial objects from static to dynamic, and the moving objects in 3D real world are drawing more and more attentions. Many applications, such as ITS (Intelligent Transport System), digital battle field, logistics management, mobile e-commerce, traveler service and other LBS (Location Based Service) systems, need efficient MOIM (Moving Objects Information Management). And MOIM is expanding from 1D or 2D to 3D with the application of 3D GIS (Geographical Information System) and VR (Virtual Reality). The information process of moving objects is complicated as it deals with spatial attributes as well as temporal attributes. However, conventional DBMS (Database Management System) can not meet the needs of MOIM. It is designed for static data management, thus any data change will lead to explicit update in database. This is not fit for continuous spatial state change of moving obje
cts. And SQL (Structural Query Language) is not designed and optimized for processing of spatio-temporal data. It is not good enough for moving objects data query. On the other hand, the current study of temporal database is focused on data which change slowly and to which statistic process is one of the important processes. It is not effective enough for real time process and it does not deal with spatial attributes. Therefore, it is necessary to study novel data organization and management algorithms to process the spatio-temporal data of moving objects. This paper is focused on the data organization and management of 3D moving objects, including representation of moving objects and index technique of motion data.
The current study of MOIM is to regard the moving objects as the points in space, to pay no attention to the shape, size and appearance of the objects, and to study the objects' spatial states and their changes, to collect, transfer, store, index, query and process the spatial state data by different means. In this way, the representation of moving objects is simplified as the representation of objects' moving or objects' motion. There are various motion models developed. They can be classified into four categories, point model, time interval model, polyline model and function model. Each kind of model has its own advantage and fits for certain application. But most of the models are for ID or 2D moving objects, and need further improvement before they can deal with 3D moving objects. And none of the existing models takes the orientation of objects into consideration, which is very important in spatial state of 3D objects. After analyzing the temporal attributes, spatial attributes and motion attributes, thi
s paper improves function model, especially MOST (Moving Object Spatio-Temporal) model, eliminates the implicit requirement for explicity, increment and separation of elements to motion function, and proposes GMM (General Motion Model). It also introduces LOD (Level of Details) to motion data and satisfies different application requirements by different accuracies and complexities for motion data and their processing. GMM encapsulates motion data and their processing according to object oriented method. It allows different processing methods and data with different types existing in same object, and is suitable for both function method and sampling method of motion model. In compliance with data collecting and types in most application systems, this paper proposes SSM (State Sequence Model) based on the position, orientation, moving direction, moving speed, moving acceleration, rotating speed, rotating acceleration and their relations of the moving objects. SSM restores objects' motion using discrete sample
data with interpolation and extrapolation, and also encapsulates data and their process. It is a concise model for representing moving objects, which is
good for 3D objects as well as ID and 2D objects. This paper also discusses the representation for different kinds of object using S
对于运动目标信息管理的研究，目前普遍的方法是将运动目标抽象成空间移动的点，忽略目标的形状、大小、外观等因素，集中注意力研究目标空间状态及其变化，通过各种手段采集、传输、存储、索引、查询和处理目标的空间状态数据。在这种情况下，运动目标的表示也就简化成了目标的运动表示。现有的目标运动模型有多种，但可以归纳为点模型、时段模型、折线模型和函数模型四类。这四类模型各有特点，适于不同的应用需要，但它们多基于一维或二维运动目标的管理，要处理三维运动目标，需要做一定的扩展，而且上述所有模型中没有一个模型考虑到目标的姿态，而运动目标的姿态在决定三维目标的空间状态中也是至关重要的。本文在分析了三维运动目标的时间特性、空间特性和运动特性的基础上，改进函数模型，特别是MOST(Moving Object Spatio-Temporal)模型，消除其对运动函数所隐含的显式、增量式和分离式要求，设计了综合运动模型。并提出运动数据的细节层次概念，以不同精度和不同计算复杂度的数据及其相应的计算方法满足不同应用的需要。综合运动模型将运动数据和相关的处理用面向对象的方法进行封装，允许不同类型、不同结构的数据和不同种类的处理方式并存，适用于函数法与样本法的不同运动模型构造方式。针对多数应用系统中数据采集的方式和类型，从目标的运动位置、姿态、运动方向、速度、加速度、旋转速度、旋转加速度等各项指标及其相互关系出发，本文还提出了状态序列模型。该模型用离散的样本加上相应的插值方法，拟合目标运动的过程，对数据和处理过程进行封装，形成简洁的运动表示模型，弥补了现有模型对三维运动目标表达上的缺陷，同时还兼容对一维和二维运动目标的管理。本文还分类讨论了状态序列模型对不同运动目标的表示方式，分析了模型中所表达的信息，包括基本信息和导出信息。
在状态序列模型的基础上。本文提出了以2~n索引树为中心的多向多级运动数据索引机制。运动数据的索引依赖于所采用的运动模型，几乎每一类模型都提出了自己相应的索引方法。通过分析运动数据索引的需求发现，根据运动目标的特点和运动数据访问的需要，所采用的算法应该不仅能够对大量运动目标当前的运动状态建立索引，而且能够管理历史数据，按照运动数据模型所规定的方式提供对将来运动状态的预测。运动数据的追加是大量发生的，所以所建立的索引应该满足这种经常更新的需要，不至于频繁引起大范围或多级结点的大规模操作。运动数据的查询有多种形式，其中有快照式查询，也有连续查询。因此，所建立的索引机制应该兼顾到各种查询的方式。为了满足这些要求，本文采用空间分割的方法，扩展四叉树和八叉树，建立n维空间的2~n索引树。结合运动数据及其处理过程的特点，给出了2~n索引树的数据结构，以及树的建立、状态向量定位、添加、删除、滞后更新和树扩展等相关算法。为满足不同类型查询的需要，特别
是连续查询对于相同目标连续一段时间内运动状态的查询要求，在建立运动数据索引时，需要将
样本数据与2”索引树相分离，同时按照目标与样本时刻建立索引，从而形成多向多级的索引结
构。本文探讨了这种混合索引方式，并给出了状态样本数据的具体存储形式。
在详细分析各种运动数据访问类型的基础上，本文讨论了各种查询方式，给出了基本状态
查询和运动过程查询的方法，介绍了正向查询（目标一时刻查询）和反向查询（时间一状态查询）
的不同检索程序和步骤，详细讨论了对相容区域和相交区域查询的不同处理方式。从运动数据在
n维空间的分布和数据访问过程出发，介绍了运动目标查询的准确性问题，探讨了准确找出所有
满足条件的运动目标的不同方法，找出了前期处理法与扩展查询区域法在处理过程和效率上的不
同，分析了一般查询与精确查询在查询步骤上的区别。通过分析目标与目标之间的相互关系，提
出了目标关系查询的方法，并
With the development of wireless communication, positioning and photogrametry, people are able to expand the information management of spatial objects from static to dynamic, and the moving objects in 3D real world are drawing more and more attentions. Many applications, such as ITS (Intelligent Transport System), digital battle field, logistics management, mobile e-commerce, traveler service and other LBS (Location Based Service) systems, need efficient MOIM (Moving Objects Information Management). And MOIM is expanding from 1D or 2D to 3D with the application of 3D GIS (Geographical Information System) and VR (Virtual Reality). The information process of moving objects is complicated as it deals with spatial attributes as well as temporal attributes. However, conventional DBMS (Database Management System) can not meet the needs of MOIM. It is designed for static data management, thus any data change will lead to explicit update in database. This is not fit for continuous spatial state change of moving obje
cts. And SQL (Structural Query Language) is not designed and optimized for processing of spatio-temporal data. It is not good enough for moving objects data query. On the other hand, the current study of temporal database is focused on data which change slowly and to which statistic process is one of the important processes. It is not effective enough for real time process and it does not deal with spatial attributes. Therefore, it is necessary to study novel data organization and management algorithms to process the spatio-temporal data of moving objects. This paper is focused on the data organization and management of 3D moving objects, including representation of moving objects and index technique of motion data.
The current study of MOIM is to regard the moving objects as the points in space, to pay no attention to the shape, size and appearance of the objects, and to study the objects' spatial states and their changes, to collect, transfer, store, index, query and process the spatial state data by different means. In this way, the representation of moving objects is simplified as the representation of objects' moving or objects' motion. There are various motion models developed. They can be classified into four categories, point model, time interval model, polyline model and function model. Each kind of model has its own advantage and fits for certain application. But most of the models are for ID or 2D moving objects, and need further improvement before they can deal with 3D moving objects. And none of the existing models takes the orientation of objects into consideration, which is very important in spatial state of 3D objects. After analyzing the temporal attributes, spatial attributes and motion attributes, thi
s paper improves function model, especially MOST (Moving Object Spatio-Temporal) model, eliminates the implicit requirement for explicity, increment and separation of elements to motion function, and proposes GMM (General Motion Model). It also introduces LOD (Level of Details) to motion data and satisfies different application requirements by different accuracies and complexities for motion data and their processing. GMM encapsulates motion data and their processing according to object oriented method. It allows different processing methods and data with different types existing in same object, and is suitable for both function method and sampling method of motion model. In compliance with data collecting and types in most application systems, this paper proposes SSM (State Sequence Model) based on the position, orientation, moving direction, moving speed, moving acceleration, rotating speed, rotating acceleration and their relations of the moving objects. SSM restores objects' motion using discrete sample
data with interpolation and extrapolation, and also encapsulates data and their process. It is a concise model for representing moving objects, which is
good for 3D objects as well as ID and 2D objects. This paper also discusses the representation for different kinds of object using S
引文
[1]．白云、金锋．基于OpenGL的交互式三维图形软件开发工具．计算机工程．2000．26(11)：158-160．
[2]．崔国华．计算方法．武汉：华中理工大学出版社，1996．11．
[3]．杜国明．序列数据的处理算法及其在城市供水管网系统中应用的研究．武汉大学博士学位论文，2002．
[4]．冯玉才．数据库系统基础．武汉；华中理工大学出版社，1993．9．
[5]．龚健雅．当代GIS的若干理论与技术．武汉：武汉测绘科技大学出版社，1999．3．
[6]．龚健雅．地理信息系统基础．北京：科学出版社，2001．2．
[7]．贾云得．机器视觉．北京：科学出版社．2000．
[8]．李德仁．论21世纪遥感与GIS的发展．武汉大学学报(信息科学版)，2003，28(2)：127-131．
[9]．李德仁、关泽群．空间信息系统的集成与实现．武汉：武汉测绘科技大学出版社，2000．3．
[10]．李捷、唐泽圣、郭红晖．基于分形维数的层次分辨率模型．计算机学报，1998，21(9)：780-786．
[11]．李庆扬、王能超、易大义．数值分析．武汉：华中理工大学出版社，1986．12．
[12]．李青元、林宗坚、李成明．真三维GIS技术研究的现状与发展．测绘科学，2000，25(2)：47-51．
[13]．刘经南．测绘科学发展前沿．给武汉大学信息学部博士生的讲座．2001．12．
[14]．骆温平．第三方物流理论、操作与案例．上海：上海社会科学院出版社，2001．
[15]．马骥、裴玉龙．智能交通系统(ITS)信息采集技术评述．哈尔滨工业大学学报，2003，35 (1)：17-20．
[16]．潘志庚、马小虎、石教英．虚拟环境中多细节层次模型自动生成算法．软件学报，1996，7(9)：526-531．
[17]．萨师煊、王珊．数据库系统概论．北京：高等教育出版社，2000．2．
[18]．石教英．计算机图形学会议述评．国际学术动态．1997(7)．13-17．
[19]．孙家广等．计算机图形学．北京：清华大学出版社，1998．9．
[20]．藤继涛、张飞舟、李跃鹏、范跃祖．智能交通系统中车辆调度问题的遗传算法研究．北京航空航天大学学报，2003，29(1)：13-16．
[21]．王能超．数值分析简明教程．北京：高等教育出版社，1984．10．
[22]．王汝传、张登银、辛晨昀．虚拟现实中3D图形建模方法的研究．计算机辅助工程，2000，4：25-30．
[23]．王永君．基于DEM数据库建立大范围虚拟地形环境的若干关键技术研究．武汉大学博士学位论文．2003．4．
[24]．吴必军、李利新、雷小平．基于城市道路数据库的最短路径搜索．西南交通大学学报，2003，38(1)：80-83．
[25]．吴乐南．数据压缩．北京：电子工业出版社，东南大学出版社，2000．6．
[26]．吴信才、曹志月．时态GIS的基本概念、功能及实现方法．地球科学——中国地质大学学报．2002，27(3)：241-245．
[27]．徐享忠、王精业．虚拟战场态势的表现．系统仿真学报，2001，13(增刊)：570-572．575．
[28]．严蔚敏、吴伟民．数据结构．北京：清华大学出版社，1996．
[29]．杨瑞元、邱建雄．基于图像的建模和绘制技术综述．计算机辅助设计与图形学学报．2002，14(2)：185-188．
[30]．叶兵．移动商务创造盈利新希望．通讯世界，2002，12：33．
[31]．叶焕倬、龚健雅、潘建平．三维运动目标的数据组织．测绘信息与工程．2003，28(4)：26-28．
[32]．袁峰、周涛发、岳书仓．时态GIS初探．地质与勘探，2003，39(1)：54-57．
[33]．张飞舟、晏磊、孙敏．基于GPS／GIS／RS集成技术的物流监控管理．系统工程，2003，21(1)：49-55
[34]．张滢、杨者青．STL、DXF等通用文件格式图形的真实感显示．小型微型计算机系统．2001．22(10)：1277-1280
[35]．张祖勋、黄明智．时态GIS的概念、功能和应用．测绘通报，1995，2：12-14，35．
[36]．赵永军、李汉林、王海起．GIS三维空间数据模型的发展与集成．石油大学学报(自然科学版)．2001，25(5)：24-28．
[37]．郑阿奇、丁有和、郑进．Visual C++实用教程．北京：电子工业出版社，2000．8．
[38]．周昆、潘志庚、石教英．基于三角形折叠的网格简化算法．计算机学报，1998，21(6)：506-514．
[39]．周昆、潘志庚、石教英．一种新的基于顶点聚类的网格简化算法．自动化学报，1999，25(1)：1-8．
[40]．周昆、潘志庚、石教英．基于混合多细节层次技术的实时绘制算法．软件学报，2001，12(1)：74-82．
[41]．周立新、刘琨．智能物流运输系统．同济大学学报，2002．30(7)：829-832．
[42]．周晓云、刘慎权．基于特征角准则的多面体模型简化方法．计算机学报，1996，19(9)：217-223．
[43]．周忠谟、易杰军、周琪．GPS卫星测量原理与应用(修订本)．北京：测绘出版社，1997．1．
[44]．[日]交通工程研究会．智能交通系统．北京：人民交通出版社，2000．
[45]. A. Guttman. R-tree: a dynamic index structure for spatial searching. Proceedings of ACM SIGMOD International Conference on the Management of Data. 1984.
[46]. A. Naka, N. Saiwaki, and S. Nishida. Spatio-temporai data management for highly interactive environment. Proceedings of 6th IEEE International Workshop on Robot and Human Communication (ROMAN'97). pp. 571-576. 1997.
[47]. A. Naka, N. Saiwaki, and S. Nishida. An adaptive spatio-temporal data management for highly interactive environment. Proceedings of the DMIB'97, pp. 68-73, 1997.
[48]. A. Nanopoulos. Indexing time-series databases for inverse queries. Proceedings of 1998 International Conference on Database and Expert System Applications, Vienna, Austria, 1998. pp. 551-560.
[49]. A. Prasad Sistla, O. Wolfson, S. Chanberlain, and S. Dao. Modeling and querying moving objects. Proceedings of the 13th International Conference on Data Engineering, pp. 422-432, 1997.
[50]. B. Becker, S. Gschwind, T. Ohler, B. Seeger, P. Widmayer. An asymptotically optimal multiversion B-Tree. VLDB Journal 1996, 5(4): 264-275.
[51]. B. Salzberg, V. Tsotras. A comparison of access methods for temporal data. ACM Computing Surveys, 1999, 31(2): 158-221.
[52]. Braun, Alexander E. Intelligent transportation systems: mirage or reality. Microwave Journal, 1997, 40(8): 22-38,
[53]. C. E. Perkins. Mobile IP. IEEE Communications Magazine. May 1997. pp. 84-99.
[54]. C. Faloutsos. Fast subsequence matching in time-series databases. Proceedings of the 1994 ACM SIGMOD International Conference on Management of Data, 1994. pp. 419-429.
[55]. C. Forum. Cellular digital packet data system specification, release 1.1. Technical report, Jan. 1995.
[56]. C. E Shannon. A mathematical theory of communication. Bell System Technical Journal. 1948, 27: 379-423, 623-656.
[57]. C. Olston, J. Widom. Offering a precision-performance tradeoff of aggregation queries over replicated data. Proceedings of the 2th International Conference on Very Large Databases (VLDB), 2000.
[58]. C. P. Kolovson. Indexing techniques for historical databases. Proceedings of Theory, Design and Implementation in Temporal Databases, 1993. pp. 418-432.
[59]. C. Shao, K. Zhang, J. Xu. A Distributed and Parallel Algorithm of Dynamic Traffic Assignment Based on Computer Simulation. Journal of Transportation Engineering and Information, 2003, 1(1): 94-101.
[60]. D. B. Lomet and B. Salzberg. The hB-tree: a multiattribute indexing method with good guaranteed performance. ACM Transactions on Database Systems, 1990, 15(4): 625-658.
[61]. D. Blythe, B. Grantham, M. J. Kilgard, T. McReynolds, and S. R. Nelson. Advanced Graphics Programming Techniques Using OpenGL. In SIGGRAPH'99 Course Notes, August, 1999.
[62]. D. Lomet. Transaction time database. Proceedings of Theory, Design and Implementation in Temporal Databases, 1993. pp. 388-417.
[63]. D. Kwon, S. J. Lee, and S. Lee. Indexing the current position of moving objects using the lazy update R-tree. Proceedings of the 3rd International Conference on Mobile Data Management, Jan. 2002.
[64]. D. Pfoser, C. S. Jensen, and Y. Theodoridis. Novel approaches in query processing for moving objects. Proceedings of the 26th International Conference on Very Large Databases(YLDB), 2000.
[65]. D. Pfoser, Y. Theodoridis, and C. S. Jensen. Indexing Trajectories of moving point objects. Chorochronos Tech. Pre. CH-99-3, June 1999,
[66]. E. Pitoura, G. Samaras. Locating objects in mobile computing. IEEE Transaction on Knowledge and Data Engineering, Vol. 13, No. 4, July/August 2001.
[67]. F.R. Hoots, R. L. Roehrich. Spacetrack report No.3, models for propagation of NORAD element sets. December 1980. http://www.amsat.org/amsat/ftp/docs/spacetrk.pdf.
[68]. G. Kollios, D. Gunopuios, V. J. Tsotras. On indexing moving objects. ACM PODS 1999 conference. ACM press.
[69]. G. Kollios, and V. J. Tsotras. Hashing methods for temporal data. IEEE Transaction on Knowledge and Data Engineering. 2002, 14(4): 902-919.
[70]. G. Turk. Re-Tiling polygonal surface. Computer Graphics, 1992, 26(2): 55-64.
[71]. H. D. Chon, D. Agrawal, A. El Abbadi. Storage and retrieval of moving objects. Proceedings of Mobile Data Management 2001 conference, pp. 173-184, 2001.
[72]. H. D. Chon, D. Agrawal, A. El Abbadi. Using space-time grid for efficient management of moving objects. MobiDE, pp. 59-65, May 2001.
[73]. H. D. Chon, D. Agrawal, A. El Abbadi. Query processing for moving objects with space-time grid storage model. Proceedings of the International Conferenceon Mobile Data Management, 2002.
[74]. H. G. Gok, and O. Ulusoy. Transmission of continuous query results in mobile computing systems. Information Sciences, vol. 125, No. 1-4, pp. 37-63, 2000.
[75]. H. Gunadhi, and A. Segev. Efficient indexing methods for temporal relations. Transactions of Knowledge and Data Engineering, 1993, 5(3): 496-509.
[76]. H. Hoppe. Progressive meshes. Computer Graphics(SIGGRAPH'96), 1996, 30: 99-108.
[77]. H. Nozawa, N. Saiwaki, S. Nishida. Spatio-temporal indexing methods for moving objects for
highly interactive environment. Proceedings of 1999 IEEE International Conference on Systems, Man, and Cybernetics, 1999. IEEE SMC '99 Conference, 12-15 Oct. 1999, Volume: 6. Pages: 7-12.
[78]. H. Samet. Applications of Spatial Data Structures: Computer Graphics, Image Processing, and GIS, Addison-Wesley, Reading, MA, 1990.
[79]. H. Samet. The Design and Analysis of Spatial Data Structures, Addison-Wesley, Reading, MA, 1990.
[80]. H. Samet. Spatial data structure. VLDB'97 Tutorial, Greece, 1997.
[81]. H. Ye, J. Gong. Motion data management of 3D moving objects. Proceedings of 2003 IEEE International Geoscience and Remote Sensing Symposium (IGARSS2003), Toulouse, France, July 2003. Vol. Ⅵ: 3736-3738.
[82]. J. Basch, L. Guibas, and J. Hershberger. Data structure for mobile data. Proceedings of the 8th ACM-SIAM Symposium on Discrete Algorithms. pp. 747-756, 1997.
[83]. J. Cohen, M. Olano, D. Manocha. Appearance-preserving simplification. Computer Graphics (SIGGRAPH'98), 1998, 2(3): 189-198.
[84]. J. F. Allen. Maintaining knowledge about temporal intervals. Communications of the ACM, 1983, 26(11): 832-843.
[85]. J. H. Friedman, J. L. Bentley and R. A. Finkel. An algorithm for finding best matches in logarithmic expected time. ACM Transaction on Math. Software (TOMS), 1977, 3(3): 209-226.
[86]. J. M. Hellerstein, J. F. Naughton, and A. Pfeffer. Generalized search trees for database system. Proceedings of the VLDB Conference. pp. 562-573, 1995.
[87]. J. R. Driscoll, N. Sarnak, D. D. Sleator, R. E. Tarjan. Making data structures persistent. Journal of Comp. and System Sci., 1989, 38: 86-124.
[88]. J. Tayeb, O. Ulusoy, and O. Wolfson. A quadtree-based dynamic attribute indexing method. The Computer Journal, pp. 185-200, 1998.
[89]. J. T. Robinson. The K-D-B-tree: a search structure for large multidimensional dynamix indexes. Proceedings of SIGMOD Conference 1981. pages 10-18.
[90]. K. Chakarabarti and S. Mehrotra. The hybrid tree: an index structure for high dimensional feature spaces. Proceedings of the 4th International Conference on Data Engineering(ICDE'99), 1999.
[91]. K. Lam, O. Ulusoy, T. S. H. Lee, E. Chan and G. Li. An efficient method for generating location updates for processing of location-dependent continuous queries. Proceedings of International Conference on Database Systems for Advanced Applications (DASFAA'01), Hong Kong, April 2001.
[92]. L. Forlizzi, R. H. Guting, E. Nardelli, and M. Schneider. A data model and data structure for moving objects database. Proceedings of ACM-SIGMOD International Conference on Management of Data. Pp. 319-330, June 2000.
[93]. L. Lin Indexing value of time sequences. Proceedings of 5th International Conference on Information and Knowledge Management (CIKM), Maryland, USA, 1996. pp. 223-232.
[94]. M. A. Nascimento. Efficient indexing of temporal database via B~+-trees. Ph.D dissertation, 1996.
[95]. M. Cai, and P. Z. Revesz. Parametric R-Tree: an index structure for moving objects. Proceedings of the COMAD Conference, 2000.
[96]. M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf. Computational geometry: algorithms and applications, Springer-Verlag, Berlin, 1997.
[97]. M. J. Egenhofer and R. D. Franzosa. Point-set topological spatial relations. International Journal
of Geographical Information Systems, 1991.5:161-174.
[98]. M. Erwig, R. H. Guting, M. Schneider and M. Vazirgianis. Abstract and discrete modeling of spatio-temporal data types. Proceedings of the 6th ACM Symposium on Geographic Information System. Pp. 131-136, Nov. 1998.
[99]. M. Erwig, R. H. Guting, M. Schneider and M. Vazirgianis. Spatio-temporal data types: an approach to modeling and querying moving objects in database. Proceedings of ACM GIS Sympostom'98. 1998.
[100]. M. Garland, P. S. Heckbert, Surface simplification using quadric error metrics. Computer Graphics (SIGGRAPH'97),1997, 31:209-216.
[101]. M.H. Dunham, and V. Kumar. Location dependent data and its management in mobile databases. Proceedings of International Workshop of Database and Expert System Application, pp. 414-419, 1998.
[102]. M. Nascimento, J. Silva. Towards historical R-trees. ACM SAC, 1998.
[103]. M. Vazirgiannis and O. Wolfson. A spatiotemporal model and language for moving objects on road networks. Proceedings of International Symposium on Spatial and Temporal Databases, pp. 20-35, 2001.
[104]. M. Wheeler. Automatic modeling and localization for object recognition, Ph.D. Dissertation, Department of Computer Science, Carnegie Mellon University, 1996.
[105]. N. Beckmann, Hans-Peter Kriegel. The R~*-tree: an efficient and robust access method for points and rectangles. Proceedings of ACM SIGMOD International Conference on the Management of Data, Atlantic City, NJ, May 1990.
[106]. N. Katayama, S. Satoh. The SR-Tree: An index structure for high-dimensional nearest neighbor queries. Proceedings of 16th ACM SIGMOD, page 369-380. 1997.
[107]. O. Wolfson. Moving objects information management: the database challenge. Proceedings of the 5th Workshop on Next Generation Information Technologies and Systems (NGITS'2002), Dan Caesarea Hotel, Caesarea, Israel, June 25-26, 2002.
[108]. O. Wolfson, B. Xu, S. Chamberlain, and L. Liang. Moving objects database: Issues and solutions. Proceedings of the 10th International Conference on Scientific and Statistical Database Management, pp. 111-122, 1998.
[109]. O. Wolfson, P. Sistla, B. Xu, J. Zhou, S. Chamberlain, N. Rishe, Y. Yesha. Tracking moving objects using database technology in DOMINO, Springer-Verlag Lecture Notes in Computer Science, number 1649, Proceedings of NGITS'99, the 4th Workshop on Next Generation Information Technologies and Systems, pp.112-119, July 1999.
[110]. O. Wolfson, P. Sistla, S. Chamberlain, Y. Yesha. Updating and querying databases that track mobile units. Distributed and Parallel Databases, 7, 257-287, 1999.
[111]. O. Woifson, S. Chamberlain, S. Dao, and L. Jiang. Location management in moving objects databases. WOSBIS'97, pp.7-13, Oct. 1997.
[112]. P. Ciaccia, M. Patella and P. Zezula. M-tree: an efficient method for similarity search in metric space. Proceedings of the 23rd VLDB Conference, Athens Greece, 1997.
[113]. P.K. Agarwal, I. Arge, J. Ericskon. Indexing moving points. Proceedings of ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS) 2000 conference. May 2000.
[114]. P.K. Agrawal and K. R. Varadarajan. Algorithms for Approximating Polygonal Chains. Discrete Comput. Geom., 23:273-291, 2000.
[115]. P.N. Yianilos. Data structure and algorithm for the nearest neighbor search in general metric spaces. Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Austin-Texas, Jan. 1993.
[116]. P. Seshadri. Management of sequence data. PhD Dissertation, 1996.
[117]. R.A. Finkei, J. L. Bentley. Quad Trees-A Data Structure for Retrieval on Composite Keys. Acta Informatica, pages 1-9, 1974.
[118]. R. Ding, X. Meng. A quadtree based dynamic attribute index structure and query process. Proceedings of International Conference on Computer Networks and Mobile Computing, pp. 446-451, 2001.
[119]. R. Elmasri. The time index: an access structure for temporal data. Proceedings of l6th Very Large Database Conference, Australia, 1990. pp. 1-12.
[120]. R. Elmasri. Efficient implementation techniques for the time index. Proceedings of 7th International Conference on Data Engineering, 1991. pp. 102-111.
[121]. R. Elmasri. Partitioning of time index for optical disks. Proceedings of 8th International Conference on Data Engineering, 1992. pp. 574-583.
[122]. R. Elmasri. The time index and the monotonic B~+-tree. Proceedings of Theory Design and Implimentation in Temporal Databases, 1993. pp. 433-456.
[123]. R. Elmasri. Fundamentals of database systems. Benjamin/Cummings, Redwood City, CA, 2nd Edition, 1994.
[124]. R.H. Mazza Ⅲ; C. B. Congdon. Towards a genetic algorithms approach to designing 3D polygonal tree models. Proceedings of the 2002 Congress on Evolutionary Computation, 2002. CEC'02. Volume: 2,2002: 1842-1847.
[125]. R. H. Guting, et al. A foundation for representing and querying moving objects. ACM-Transactions on Database System Journal, 25(1), 1-42, 2000.
[126]. R. Jain, R. Kastud, B. G. Schunck. Machine vision. Beijing: China Machine Press. 2003.8.
[127]. R.K.V. Kothuri, S. Ravada, and D. Abugov. Quadtree and R-tree indexes in Oracle Spatial: a comparison using GIS data. Proceedings of ACMSIGMOD Conference, 2002.
[128]. S. Chamberlain. Automated information distribution in bandwidth-constrained environments. Proceedings of MILCON-94 conference, 1994.
[129]. S. Chamberlain. Model-based battle command: A paradigm whose time has come. Proceedings of 1995 Symposium on C2 Research & Technology, NDU, June 1995.
[130]. S. Prabhakar, Y. Xia, D. Kalashoikov, W. Aref, and S. Haanbrusch. Query indexing and velocity constrained indexing: scalable techniques for continuous queries on moving objects. IEEE Transaction on Computers, 51(10):1124-1140, Oct. 2002.
[131]. S. Saltenis, C. S. Jensen, S. T. Leutenegger, M. A. Lopez. Indexing the positions of continuously moving objects. Proceedings of ACM SIGMOD Conference 2000.
[132]. S. Saltonis, C. S. Jensen. Indexing of moving objects for location-based services, the 18th International Conference on Data Engineering (ICDE'02), pp. 463-472, 2002.
[133]. T. Sellis, N. Roussopoulos and C. Faloutos. The R+-tree: a dynamic index for multi-dimensional objects. Proceedings of the 13th VLDB Conference, Brighton 1987. pages 507-518.
[134]. V. J. Tsotras. The snapshot index, aa I/O optimal access method for timeslice queries. Information System, 1995, 3(20): 237-260.
[135]. V. Gaede and O. Gunther. Multidimensional access methods. ACM Computing Surveys, 1998,
3(2): 170-231.
[136]. V. Kouramajian. The time index~+: an incremental access structure for temporal databases. Proceedings of 3rd International Conference on Knowledge and Management, 1994. pp. 296-303.
[137]. W.J. Schroeder, J. A. Zarge, W. E. Lorensen. Decimation of triangle meshes. Computer Graphics, 1992, 26 (2): 65-70.
[138]. Y. Jiar, M. Wheeler, K. Ikeuchi. Hand action perception for robot programming. Proceedings of International Conference on Intelligent Robots and Systems, Japan, 1996.
[139]. Y. Masunaga, N. Ukai. Toward a 3D moving object data model. Proceedings of 1999 International Symposium on Database Applications in Non-Traditional Environments (DANTE'99), November 28-30, 1999 Kyoto, Japan. pp. 302-312.
[140]. Y. Tao and D. Papdias. Mv3r-tree: a spatio-temporal access method for timestamp and interval queries. Proceedings of the 27th International Conference on.Very Large Databases. 2001.
[141]. Y. Xia, S. Prabhakar. Q+Rtree: efficient indexing for moving object databases. Proceedings of the 8th International Conference on Database Systems for Advanced Applications (DASFAA 2003), pp. 175-182, 2003.
[142]. Z. Song and N. Roussopoulos. Hashing moving objects. Proceedings of the 2nd International Conference on Mobile Data Management, pp. 161-172, 2001.
[2]．崔国华．计算方法．武汉：华中理工大学出版社，1996．11．
[3]．杜国明．序列数据的处理算法及其在城市供水管网系统中应用的研究．武汉大学博士学位论文，2002．
[4]．冯玉才．数据库系统基础．武汉；华中理工大学出版社，1993．9．
[5]．龚健雅．当代GIS的若干理论与技术．武汉：武汉测绘科技大学出版社，1999．3．
[6]．龚健雅．地理信息系统基础．北京：科学出版社，2001．2．
[7]．贾云得．机器视觉．北京：科学出版社．2000．
[8]．李德仁．论21世纪遥感与GIS的发展．武汉大学学报(信息科学版)，2003，28(2)：127-131．
[9]．李德仁、关泽群．空间信息系统的集成与实现．武汉：武汉测绘科技大学出版社，2000．3．
[10]．李捷、唐泽圣、郭红晖．基于分形维数的层次分辨率模型．计算机学报，1998，21(9)：780-786．
[11]．李庆扬、王能超、易大义．数值分析．武汉：华中理工大学出版社，1986．12．
[12]．李青元、林宗坚、李成明．真三维GIS技术研究的现状与发展．测绘科学，2000，25(2)：47-51．
[13]．刘经南．测绘科学发展前沿．给武汉大学信息学部博士生的讲座．2001．12．
[14]．骆温平．第三方物流理论、操作与案例．上海：上海社会科学院出版社，2001．
[15]．马骥、裴玉龙．智能交通系统(ITS)信息采集技术评述．哈尔滨工业大学学报，2003，35 (1)：17-20．
[16]．潘志庚、马小虎、石教英．虚拟环境中多细节层次模型自动生成算法．软件学报，1996，7(9)：526-531．
[17]．萨师煊、王珊．数据库系统概论．北京：高等教育出版社，2000．2．
[18]．石教英．计算机图形学会议述评．国际学术动态．1997(7)．13-17．
[19]．孙家广等．计算机图形学．北京：清华大学出版社，1998．9．
[20]．藤继涛、张飞舟、李跃鹏、范跃祖．智能交通系统中车辆调度问题的遗传算法研究．北京航空航天大学学报，2003，29(1)：13-16．
[21]．王能超．数值分析简明教程．北京：高等教育出版社，1984．10．
[22]．王汝传、张登银、辛晨昀．虚拟现实中3D图形建模方法的研究．计算机辅助工程，2000，4：25-30．
[23]．王永君．基于DEM数据库建立大范围虚拟地形环境的若干关键技术研究．武汉大学博士学位论文．2003．4．
[24]．吴必军、李利新、雷小平．基于城市道路数据库的最短路径搜索．西南交通大学学报，2003，38(1)：80-83．
[25]．吴乐南．数据压缩．北京：电子工业出版社，东南大学出版社，2000．6．
[26]．吴信才、曹志月．时态GIS的基本概念、功能及实现方法．地球科学——中国地质大学学报．2002，27(3)：241-245．
[27]．徐享忠、王精业．虚拟战场态势的表现．系统仿真学报，2001，13(增刊)：570-572．575．
[28]．严蔚敏、吴伟民．数据结构．北京：清华大学出版社，1996．
[29]．杨瑞元、邱建雄．基于图像的建模和绘制技术综述．计算机辅助设计与图形学学报．2002，14(2)：185-188．
[30]．叶兵．移动商务创造盈利新希望．通讯世界，2002，12：33．
[31]．叶焕倬、龚健雅、潘建平．三维运动目标的数据组织．测绘信息与工程．2003，28(4)：26-28．
[32]．袁峰、周涛发、岳书仓．时态GIS初探．地质与勘探，2003，39(1)：54-57．
[33]．张飞舟、晏磊、孙敏．基于GPS／GIS／RS集成技术的物流监控管理．系统工程，2003，21(1)：49-55
[34]．张滢、杨者青．STL、DXF等通用文件格式图形的真实感显示．小型微型计算机系统．2001．22(10)：1277-1280
[35]．张祖勋、黄明智．时态GIS的概念、功能和应用．测绘通报，1995，2：12-14，35．
[36]．赵永军、李汉林、王海起．GIS三维空间数据模型的发展与集成．石油大学学报(自然科学版)．2001，25(5)：24-28．
[37]．郑阿奇、丁有和、郑进．Visual C++实用教程．北京：电子工业出版社，2000．8．
[38]．周昆、潘志庚、石教英．基于三角形折叠的网格简化算法．计算机学报，1998，21(6)：506-514．
[39]．周昆、潘志庚、石教英．一种新的基于顶点聚类的网格简化算法．自动化学报，1999，25(1)：1-8．
[40]．周昆、潘志庚、石教英．基于混合多细节层次技术的实时绘制算法．软件学报，2001，12(1)：74-82．
[41]．周立新、刘琨．智能物流运输系统．同济大学学报，2002．30(7)：829-832．
[42]．周晓云、刘慎权．基于特征角准则的多面体模型简化方法．计算机学报，1996，19(9)：217-223．
[43]．周忠谟、易杰军、周琪．GPS卫星测量原理与应用(修订本)．北京：测绘出版社，1997．1．
[44]．[日]交通工程研究会．智能交通系统．北京：人民交通出版社，2000．
[45]. A. Guttman. R-tree: a dynamic index structure for spatial searching. Proceedings of ACM SIGMOD International Conference on the Management of Data. 1984.
[46]. A. Naka, N. Saiwaki, and S. Nishida. Spatio-temporai data management for highly interactive environment. Proceedings of 6th IEEE International Workshop on Robot and Human Communication (ROMAN'97). pp. 571-576. 1997.
[47]. A. Naka, N. Saiwaki, and S. Nishida. An adaptive spatio-temporal data management for highly interactive environment. Proceedings of the DMIB'97, pp. 68-73, 1997.
[48]. A. Nanopoulos. Indexing time-series databases for inverse queries. Proceedings of 1998 International Conference on Database and Expert System Applications, Vienna, Austria, 1998. pp. 551-560.
[49]. A. Prasad Sistla, O. Wolfson, S. Chanberlain, and S. Dao. Modeling and querying moving objects. Proceedings of the 13th International Conference on Data Engineering, pp. 422-432, 1997.
[50]. B. Becker, S. Gschwind, T. Ohler, B. Seeger, P. Widmayer. An asymptotically optimal multiversion B-Tree. VLDB Journal 1996, 5(4): 264-275.
[51]. B. Salzberg, V. Tsotras. A comparison of access methods for temporal data. ACM Computing Surveys, 1999, 31(2): 158-221.
[52]. Braun, Alexander E. Intelligent transportation systems: mirage or reality. Microwave Journal, 1997, 40(8): 22-38,
[53]. C. E. Perkins. Mobile IP. IEEE Communications Magazine. May 1997. pp. 84-99.
[54]. C. Faloutsos. Fast subsequence matching in time-series databases. Proceedings of the 1994 ACM SIGMOD International Conference on Management of Data, 1994. pp. 419-429.
[55]. C. Forum. Cellular digital packet data system specification, release 1.1. Technical report, Jan. 1995.
[56]. C. E Shannon. A mathematical theory of communication. Bell System Technical Journal. 1948, 27: 379-423, 623-656.
[57]. C. Olston, J. Widom. Offering a precision-performance tradeoff of aggregation queries over replicated data. Proceedings of the 2th International Conference on Very Large Databases (VLDB), 2000.
[58]. C. P. Kolovson. Indexing techniques for historical databases. Proceedings of Theory, Design and Implementation in Temporal Databases, 1993. pp. 418-432.
[59]. C. Shao, K. Zhang, J. Xu. A Distributed and Parallel Algorithm of Dynamic Traffic Assignment Based on Computer Simulation. Journal of Transportation Engineering and Information, 2003, 1(1): 94-101.
[60]. D. B. Lomet and B. Salzberg. The hB-tree: a multiattribute indexing method with good guaranteed performance. ACM Transactions on Database Systems, 1990, 15(4): 625-658.
[61]. D. Blythe, B. Grantham, M. J. Kilgard, T. McReynolds, and S. R. Nelson. Advanced Graphics Programming Techniques Using OpenGL. In SIGGRAPH'99 Course Notes, August, 1999.
[62]. D. Lomet. Transaction time database. Proceedings of Theory, Design and Implementation in Temporal Databases, 1993. pp. 388-417.
[63]. D. Kwon, S. J. Lee, and S. Lee. Indexing the current position of moving objects using the lazy update R-tree. Proceedings of the 3rd International Conference on Mobile Data Management, Jan. 2002.
[64]. D. Pfoser, C. S. Jensen, and Y. Theodoridis. Novel approaches in query processing for moving objects. Proceedings of the 26th International Conference on Very Large Databases(YLDB), 2000.
[65]. D. Pfoser, Y. Theodoridis, and C. S. Jensen. Indexing Trajectories of moving point objects. Chorochronos Tech. Pre. CH-99-3, June 1999,
[66]. E. Pitoura, G. Samaras. Locating objects in mobile computing. IEEE Transaction on Knowledge and Data Engineering, Vol. 13, No. 4, July/August 2001.
[67]. F.R. Hoots, R. L. Roehrich. Spacetrack report No.3, models for propagation of NORAD element sets. December 1980. http://www.amsat.org/amsat/ftp/docs/spacetrk.pdf.
[68]. G. Kollios, D. Gunopuios, V. J. Tsotras. On indexing moving objects. ACM PODS 1999 conference. ACM press.
[69]. G. Kollios, and V. J. Tsotras. Hashing methods for temporal data. IEEE Transaction on Knowledge and Data Engineering. 2002, 14(4): 902-919.
[70]. G. Turk. Re-Tiling polygonal surface. Computer Graphics, 1992, 26(2): 55-64.
[71]. H. D. Chon, D. Agrawal, A. El Abbadi. Storage and retrieval of moving objects. Proceedings of Mobile Data Management 2001 conference, pp. 173-184, 2001.
[72]. H. D. Chon, D. Agrawal, A. El Abbadi. Using space-time grid for efficient management of moving objects. MobiDE, pp. 59-65, May 2001.
[73]. H. D. Chon, D. Agrawal, A. El Abbadi. Query processing for moving objects with space-time grid storage model. Proceedings of the International Conferenceon Mobile Data Management, 2002.
[74]. H. G. Gok, and O. Ulusoy. Transmission of continuous query results in mobile computing systems. Information Sciences, vol. 125, No. 1-4, pp. 37-63, 2000.
[75]. H. Gunadhi, and A. Segev. Efficient indexing methods for temporal relations. Transactions of Knowledge and Data Engineering, 1993, 5(3): 496-509.
[76]. H. Hoppe. Progressive meshes. Computer Graphics(SIGGRAPH'96), 1996, 30: 99-108.
[77]. H. Nozawa, N. Saiwaki, S. Nishida. Spatio-temporal indexing methods for moving objects for
highly interactive environment. Proceedings of 1999 IEEE International Conference on Systems, Man, and Cybernetics, 1999. IEEE SMC '99 Conference, 12-15 Oct. 1999, Volume: 6. Pages: 7-12.
[78]. H. Samet. Applications of Spatial Data Structures: Computer Graphics, Image Processing, and GIS, Addison-Wesley, Reading, MA, 1990.
[79]. H. Samet. The Design and Analysis of Spatial Data Structures, Addison-Wesley, Reading, MA, 1990.
[80]. H. Samet. Spatial data structure. VLDB'97 Tutorial, Greece, 1997.
[81]. H. Ye, J. Gong. Motion data management of 3D moving objects. Proceedings of 2003 IEEE International Geoscience and Remote Sensing Symposium (IGARSS2003), Toulouse, France, July 2003. Vol. Ⅵ: 3736-3738.
[82]. J. Basch, L. Guibas, and J. Hershberger. Data structure for mobile data. Proceedings of the 8th ACM-SIAM Symposium on Discrete Algorithms. pp. 747-756, 1997.
[83]. J. Cohen, M. Olano, D. Manocha. Appearance-preserving simplification. Computer Graphics (SIGGRAPH'98), 1998, 2(3): 189-198.
[84]. J. F. Allen. Maintaining knowledge about temporal intervals. Communications of the ACM, 1983, 26(11): 832-843.
[85]. J. H. Friedman, J. L. Bentley and R. A. Finkel. An algorithm for finding best matches in logarithmic expected time. ACM Transaction on Math. Software (TOMS), 1977, 3(3): 209-226.
[86]. J. M. Hellerstein, J. F. Naughton, and A. Pfeffer. Generalized search trees for database system. Proceedings of the VLDB Conference. pp. 562-573, 1995.
[87]. J. R. Driscoll, N. Sarnak, D. D. Sleator, R. E. Tarjan. Making data structures persistent. Journal of Comp. and System Sci., 1989, 38: 86-124.
[88]. J. Tayeb, O. Ulusoy, and O. Wolfson. A quadtree-based dynamic attribute indexing method. The Computer Journal, pp. 185-200, 1998.
[89]. J. T. Robinson. The K-D-B-tree: a search structure for large multidimensional dynamix indexes. Proceedings of SIGMOD Conference 1981. pages 10-18.
[90]. K. Chakarabarti and S. Mehrotra. The hybrid tree: an index structure for high dimensional feature spaces. Proceedings of the 4th International Conference on Data Engineering(ICDE'99), 1999.
[91]. K. Lam, O. Ulusoy, T. S. H. Lee, E. Chan and G. Li. An efficient method for generating location updates for processing of location-dependent continuous queries. Proceedings of International Conference on Database Systems for Advanced Applications (DASFAA'01), Hong Kong, April 2001.
[92]. L. Forlizzi, R. H. Guting, E. Nardelli, and M. Schneider. A data model and data structure for moving objects database. Proceedings of ACM-SIGMOD International Conference on Management of Data. Pp. 319-330, June 2000.
[93]. L. Lin Indexing value of time sequences. Proceedings of 5th International Conference on Information and Knowledge Management (CIKM), Maryland, USA, 1996. pp. 223-232.
[94]. M. A. Nascimento. Efficient indexing of temporal database via B~+-trees. Ph.D dissertation, 1996.
[95]. M. Cai, and P. Z. Revesz. Parametric R-Tree: an index structure for moving objects. Proceedings of the COMAD Conference, 2000.
[96]. M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf. Computational geometry: algorithms and applications, Springer-Verlag, Berlin, 1997.
[97]. M. J. Egenhofer and R. D. Franzosa. Point-set topological spatial relations. International Journal
of Geographical Information Systems, 1991.5:161-174.
[98]. M. Erwig, R. H. Guting, M. Schneider and M. Vazirgianis. Abstract and discrete modeling of spatio-temporal data types. Proceedings of the 6th ACM Symposium on Geographic Information System. Pp. 131-136, Nov. 1998.
[99]. M. Erwig, R. H. Guting, M. Schneider and M. Vazirgianis. Spatio-temporal data types: an approach to modeling and querying moving objects in database. Proceedings of ACM GIS Sympostom'98. 1998.
[100]. M. Garland, P. S. Heckbert, Surface simplification using quadric error metrics. Computer Graphics (SIGGRAPH'97),1997, 31:209-216.
[101]. M.H. Dunham, and V. Kumar. Location dependent data and its management in mobile databases. Proceedings of International Workshop of Database and Expert System Application, pp. 414-419, 1998.
[102]. M. Nascimento, J. Silva. Towards historical R-trees. ACM SAC, 1998.
[103]. M. Vazirgiannis and O. Wolfson. A spatiotemporal model and language for moving objects on road networks. Proceedings of International Symposium on Spatial and Temporal Databases, pp. 20-35, 2001.
[104]. M. Wheeler. Automatic modeling and localization for object recognition, Ph.D. Dissertation, Department of Computer Science, Carnegie Mellon University, 1996.
[105]. N. Beckmann, Hans-Peter Kriegel. The R~*-tree: an efficient and robust access method for points and rectangles. Proceedings of ACM SIGMOD International Conference on the Management of Data, Atlantic City, NJ, May 1990.
[106]. N. Katayama, S. Satoh. The SR-Tree: An index structure for high-dimensional nearest neighbor queries. Proceedings of 16th ACM SIGMOD, page 369-380. 1997.
[107]. O. Wolfson. Moving objects information management: the database challenge. Proceedings of the 5th Workshop on Next Generation Information Technologies and Systems (NGITS'2002), Dan Caesarea Hotel, Caesarea, Israel, June 25-26, 2002.
[108]. O. Wolfson, B. Xu, S. Chamberlain, and L. Liang. Moving objects database: Issues and solutions. Proceedings of the 10th International Conference on Scientific and Statistical Database Management, pp. 111-122, 1998.
[109]. O. Wolfson, P. Sistla, B. Xu, J. Zhou, S. Chamberlain, N. Rishe, Y. Yesha. Tracking moving objects using database technology in DOMINO, Springer-Verlag Lecture Notes in Computer Science, number 1649, Proceedings of NGITS'99, the 4th Workshop on Next Generation Information Technologies and Systems, pp.112-119, July 1999.
[110]. O. Wolfson, P. Sistla, S. Chamberlain, Y. Yesha. Updating and querying databases that track mobile units. Distributed and Parallel Databases, 7, 257-287, 1999.
[111]. O. Woifson, S. Chamberlain, S. Dao, and L. Jiang. Location management in moving objects databases. WOSBIS'97, pp.7-13, Oct. 1997.
[112]. P. Ciaccia, M. Patella and P. Zezula. M-tree: an efficient method for similarity search in metric space. Proceedings of the 23rd VLDB Conference, Athens Greece, 1997.
[113]. P.K. Agarwal, I. Arge, J. Ericskon. Indexing moving points. Proceedings of ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS) 2000 conference. May 2000.
[114]. P.K. Agrawal and K. R. Varadarajan. Algorithms for Approximating Polygonal Chains. Discrete Comput. Geom., 23:273-291, 2000.
[115]. P.N. Yianilos. Data structure and algorithm for the nearest neighbor search in general metric spaces. Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Austin-Texas, Jan. 1993.
[116]. P. Seshadri. Management of sequence data. PhD Dissertation, 1996.
[117]. R.A. Finkei, J. L. Bentley. Quad Trees-A Data Structure for Retrieval on Composite Keys. Acta Informatica, pages 1-9, 1974.
[118]. R. Ding, X. Meng. A quadtree based dynamic attribute index structure and query process. Proceedings of International Conference on Computer Networks and Mobile Computing, pp. 446-451, 2001.
[119]. R. Elmasri. The time index: an access structure for temporal data. Proceedings of l6th Very Large Database Conference, Australia, 1990. pp. 1-12.
[120]. R. Elmasri. Efficient implementation techniques for the time index. Proceedings of 7th International Conference on Data Engineering, 1991. pp. 102-111.
[121]. R. Elmasri. Partitioning of time index for optical disks. Proceedings of 8th International Conference on Data Engineering, 1992. pp. 574-583.
[122]. R. Elmasri. The time index and the monotonic B~+-tree. Proceedings of Theory Design and Implimentation in Temporal Databases, 1993. pp. 433-456.
[123]. R. Elmasri. Fundamentals of database systems. Benjamin/Cummings, Redwood City, CA, 2nd Edition, 1994.
[124]. R.H. Mazza Ⅲ; C. B. Congdon. Towards a genetic algorithms approach to designing 3D polygonal tree models. Proceedings of the 2002 Congress on Evolutionary Computation, 2002. CEC'02. Volume: 2,2002: 1842-1847.
[125]. R. H. Guting, et al. A foundation for representing and querying moving objects. ACM-Transactions on Database System Journal, 25(1), 1-42, 2000.
[126]. R. Jain, R. Kastud, B. G. Schunck. Machine vision. Beijing: China Machine Press. 2003.8.
[127]. R.K.V. Kothuri, S. Ravada, and D. Abugov. Quadtree and R-tree indexes in Oracle Spatial: a comparison using GIS data. Proceedings of ACMSIGMOD Conference, 2002.
[128]. S. Chamberlain. Automated information distribution in bandwidth-constrained environments. Proceedings of MILCON-94 conference, 1994.
[129]. S. Chamberlain. Model-based battle command: A paradigm whose time has come. Proceedings of 1995 Symposium on C2 Research & Technology, NDU, June 1995.
[130]. S. Prabhakar, Y. Xia, D. Kalashoikov, W. Aref, and S. Haanbrusch. Query indexing and velocity constrained indexing: scalable techniques for continuous queries on moving objects. IEEE Transaction on Computers, 51(10):1124-1140, Oct. 2002.
[131]. S. Saltenis, C. S. Jensen, S. T. Leutenegger, M. A. Lopez. Indexing the positions of continuously moving objects. Proceedings of ACM SIGMOD Conference 2000.
[132]. S. Saltonis, C. S. Jensen. Indexing of moving objects for location-based services, the 18th International Conference on Data Engineering (ICDE'02), pp. 463-472, 2002.
[133]. T. Sellis, N. Roussopoulos and C. Faloutos. The R+-tree: a dynamic index for multi-dimensional objects. Proceedings of the 13th VLDB Conference, Brighton 1987. pages 507-518.
[134]. V. J. Tsotras. The snapshot index, aa I/O optimal access method for timeslice queries. Information System, 1995, 3(20): 237-260.
[135]. V. Gaede and O. Gunther. Multidimensional access methods. ACM Computing Surveys, 1998,
3(2): 170-231.
[136]. V. Kouramajian. The time index~+: an incremental access structure for temporal databases. Proceedings of 3rd International Conference on Knowledge and Management, 1994. pp. 296-303.
[137]. W.J. Schroeder, J. A. Zarge, W. E. Lorensen. Decimation of triangle meshes. Computer Graphics, 1992, 26 (2): 65-70.
[138]. Y. Jiar, M. Wheeler, K. Ikeuchi. Hand action perception for robot programming. Proceedings of International Conference on Intelligent Robots and Systems, Japan, 1996.
[139]. Y. Masunaga, N. Ukai. Toward a 3D moving object data model. Proceedings of 1999 International Symposium on Database Applications in Non-Traditional Environments (DANTE'99), November 28-30, 1999 Kyoto, Japan. pp. 302-312.
[140]. Y. Tao and D. Papdias. Mv3r-tree: a spatio-temporal access method for timestamp and interval queries. Proceedings of the 27th International Conference on.Very Large Databases. 2001.
[141]. Y. Xia, S. Prabhakar. Q+Rtree: efficient indexing for moving object databases. Proceedings of the 8th International Conference on Database Systems for Advanced Applications (DASFAA 2003), pp. 175-182, 2003.
[142]. Z. Song and N. Roussopoulos. Hashing moving objects. Proceedings of the 2nd International Conference on Mobile Data Management, pp. 161-172, 2001.