移动对象的存储和查询系统设计与实现

ABSTRACT

With the development and maturation of GPS technology, a lot of \services\applications are rapidly developed. When we get lost on travel, phone navigation system can tell us where we are. We can get the nearest public transportation points, or even the taxis coming in our direction.

Either people, public transportation points or taxis can be abstracted into a moving object. The Movement of these objects can be described as a track. The position of moving objects may change all the time. Traditional index structures do not work well on moving objects because of the need of frequently updating the index which leads to the poor performance. We presents a novel indexing structure based on quadtree and Hash table which use location as the first index and time second. Merging timely the corresponding nodes to degrade the depth of the tree can guarantee the query efficiency.

This paper focuses on several major data modeling of moving objects and analyze it's indexing and storage and query technology. In this study, we base on the density of space-time history point data, introduce the quadtree and divide the track point on region to storage and query. Inside the quad tree cell system, the data blocks are divided by time index. Last we introduce several query on this index storage structure and we can see the advantages of this index storage structure.

Keywords: moving object; quadtree; index structure

II

目 录

第1章 绪论..................................................................................................................1

1.1 研究背景和意义 .................................................................................................1 1.2 国内外研究现状 .................................................................................................1

1.2.1时空数据库国内外研究现状 ....................................................................1 1.2.2移动对象索引研究现状 ............................................................................2 1.3 该课题研究的主要内容 .....................................................................................3 1.4 本论文结构与安排 .............................................................................................3 1.5 本章小结 .............................................................................................................3

第2章 相关技术介绍 ...............................................................................................4

2.1 移动对象数据库基本概念 .................................................................................4 2.2 移动对象数据建模 .............................................................................................5

2.2.1 线段模型 ...................................................................................................5 2.2.2 点模型 .......................................................................................................6 2.3 基于Quadtree和Hash表的移动对象索引 .....................................................7 2.4 磁盘块存储技术 .................................................................................................8 2.5 本章小结 .............................................................................................................9

第3章 系统实现 ...................................................................................................... 10

3.1 系统介绍 ........................................................................................................... 10 3.2 模块介绍 ........................................................................................................... 10

3.2.1 内存处理 ................................................................................................. 10 3.2.2 存储结构 ................................................................................................. 16 3.3 四叉树生成 ....................................................................................................... 24

3.3.1 数据导入 ................................................................................................. 24 3.3.2 生成算法 ................................................................................................. 24 3.4 几类查询算法 ................................................................................................... 25

3.4.1 范围查询 ................................................................................................. 25 3.4.2 轨道查询 ................................................................................................. 28 3.4.3 某时刻位置查询 ..................................................................................... 28 3.4.4 KNN查询 .................................................................................................. 30 3.5 本章小结 ........................................................................................................... 30

第4章 结论................................................................................................................ 31 参考文献....................................................................................................................... 32 致 谢....................................................................................................................... 33

III

第1章 绪论

1.1 研究背景和意义

近年来，随着无线通信技术的高速发展，时空数据库越来越多地应用在地理信息系统、交通管理、定位、城市规划等各个领域。在无线定位业务（Location-BasedService,LBS）应用中，LBS通过无线通信网络获取移动对象的位置信息，在地理信息系统平台的支持下为客户提供相应的服务，其中包括儿童保护、个人导航应用、寻友服务、销售人员管理、资产跟踪服务等，获取的移动对象及其位置信息组成的数据库称为移动对象数据库（Moving Objects Databases,MOD），它基于时空数据库中时间和空间变化类型之一：实体的运动。

随着GPS技术的发展和成熟，很多“基于位置的服务”应用软件也迅速的发展起来。旅行时迷路了，我们可以用手机上的导航系统定位现在所处的位置，还可以查询离我们最近的公交点，甚至可以查询正向我们这个方向驶来的无人出租车。

人，公交点，出租车都可抽象成一个个的移动对象，这些对象的运动生成一条条的轨道。移动对象的位置可能时刻发生变化，像以往的数据库，是无法存储这种数据量且更新频繁的数据。因此我们提出了移动对象数据库，用来存储移动对象的运动轨迹。为了解决大量移动对象位置频繁更新所带来的性能下降问题，我们必须在移动对象数据库上加上空间和时间的索引。

1.2 国内外研究现状

1.2.1时空数据库国内外研究现状

目前国外对于时空数据库已经开展了广泛的研究工作。其中，chorochronos项目组是由欧洲委员会资助的培训和流动的研究人员项目组，他们在时空数据库的设计、实现和应用方面做了大量的研究工作，研究内容主要包括时空对象表达、时空数据的建模、时空信息图形用户接口、时空对象查询处理、时空对象的存储、时空对象索引以及时空数据库体系结构等内容。美国普顿(Purdue)大学的PLACE

1

项目组在时空数据库方面也有一定的研究成果，主要涉及无线通讯技术、个人定位系统、信息科技环境下为用户提供基于位置的服务等，其中为用户提供的基于位置的服务是一个可扩展的基于位置的数据库服务器。

国内在时空数据库的研究方面起步稍晚，目前主要有复旦大学、香港城市大学、华中科技大学等几所高校的教研室对时空数据库进行了广泛研究。

当前国际上一些权威期刊如VLDB Journal、ACM TODS、IEEE TKDE、DKE等和国际著名会议如ACM SIGMOD、VLDB、ICDE、SSTD等也对空间和时空数据库给予了很大的重视，并将其作为主要研究内容之一。

全球主流的数据库厂商Oracle、DB2以及Informix等也纷纷提供了可扩展的对象关系数据库技术，以支持时空数据库方面的扩展。例如，Oracle定位器(LocatoO、Cartridges的DomainIndexes技术以及Oraclc9i数据库系统中提供的对基于位置查询的支持等。

1.2.2移动对象索引研究现状

为了快速、有效地处理海量数据，近年来，针对移动对象索引的研究，专家们提出了大量基于磁盘的时空数据库索引方法。其中时空索引研究的两个重要的途径是对于R-tree和四叉树(Quadtree)扩展构建新的索引结构。在针对移动对象索引结构的性能测试中，大量的合成数据集被用来进行试验工作。

虽然时空数据处理对于现实世界建模非常重要，但是由于时空数据的复杂性，目前好的时空索引却不是很多。索引的研究多集中在支持多维数据的纯空间索引研究和对于一般传统数据类型(如数字，字符串)的时态索引上。由于R-tree及其变体在空间索引上的优势，在过去几年里，研究者们提出了许多基于R-tree的时空索引版本，可以把它们大致分为如下几类：(1)把时间信息添加到空间维中，从而将空间索引转变为支持时空的移动对象索引方法；(2)使用重叠和多版本结构，将时间维和空间维隔离开来，一个时间片的空间数据集中存放在一个索引结构中；(3)处理迹线方式，将数据在逻辑上看成是各条轨迹的集合。同时，T．Tzouramanis等人的四叉树(Quadtree)也被广泛地应用于时空对象索引中。

2