位置服务中非确定数据对象查询处理技术

VIP免费

3.0 高德中 2024-11-19 9 4 1.6MB 62 页 15积分

侵权投诉

摘要

LBS 的模式共有四种：休闲娱乐型、生活服务型、社交型及商业型。随着 3G

业务的发展，这些模式得到了很好地体现。在 LBS 中，定位与查询是两个关键的

技术，在查询方面，反向最近邻查询是 LBS 的一个重要运用，在生活中，如商场

的选址、出租车智能呼叫以及影响度调查等均需运用到反向最近邻查询技术。

在反向最近邻查询中，移动对象的反向最近邻查询、移动对象反向 K最近邻

查询以及在概率数据库上概率反向最近邻查询是研究的重点，然而在之前的研究

中，移动反向最近邻查询在查询效率、通信开销及服务器的稳定性方面，仍有许

多的不足之处：查询效率低下，查询的通信开销过大，服务器的稳定性不佳。在

移动对象反向 K最近邻的研究中，进行剪枝时大多沿用反向最近邻的剪枝规则，

使得在剪枝效率低下，从而影响了查询的总效率。对于概率反向最近邻查询，之

前所做的研究很少，未提出较好的解决方法，但重要性却不容忽视。为了解决以

上提到的问题，本文给出以下解决方案：

1. 为了提高查询效率，本文引入了索引技术。索引是提高查询效率的直接途

径，本文研究的对象具有时空特性，所以必须引入时空数据库的索引技术。本文

分别研究了离散及连续两种时空数据的树索引，并且给出了插入、删除及查询的

实现方法。

2. 为了减少移动对象的通信开销，本文采取了为移动对象分配安全域的方

法。如果查询过于频繁，服务器重定位及重计算将非常频繁，开销非常大，而本

文通过分配安全域的方法，减少了的重定位与重计算的次数。

3. 为了提高服务器的稳定性，本文采取了自适应调整安全域的方法。安全域

分配得不恰当，会使服务器请求重定位与重计算的时间间隔不一，这会导致服务

器在不同时刻负载不均，而自适应的方法使重计算的频度更稳定。

4. 为了提高移动对象反向 K最近邻剪枝的区域，本文采取了 K-Binding 的方

法。K-Binding 通过筛选 K个查询候选对象进行 TPL 剪枝，提高了剪枝效率。

5. 为了使反向最近邻查询能够在概率数据库上高效进行，本文增加了概率剪

枝规则。成熟的四大剪枝规则在概率数据库上不完全适用，而概率剪枝特为概率

反向最近邻量身定做，提高了查询效率。

关键词:位置服务时空索引反向最近邻概率反向最近邻剪枝规则

ABSTRACT

There are four patterns in LBS: entertainment, life service, socializing and business.

With the development of 3G services, these patterns have been well reflected. In LBS,

the location and query are two key technologies, about query, the reverse nearest

neighbor query is an important use of LBS in life, such as the location of shopping

centers, intelligent call a taxi and the affect of investigation, all of them need to use

reverse nearest neighbor queries.

About moving objects, RNN，RkNN and PRNN are the focus of previous studies.

However, in RNN reserch, there are still many deficiencies: inefficient queries, large

communication cost and poor stability of the server. In RkNN study, because of using

old pruning rules, that makes the pruning low efficiency and affectes the overall

efficiency of the query. The research of PRNN on uncertern database was done less

before, but its importance should not be overlooked.

In order to solve the problems mentioned above, this paper proposes the following

solutions:

1. It introduces the index of technology. Index is a direct way to improve query

efficiency, the dataes studied in this paper space-time data, so it is necessary to

introduce temporal and spatial database index.

2. It assigns ervery object to a security area to reduce the communication cost of

moving objects.

3. In order to improve stability of the server, the paper adopted a method to adjust

security area adaptively.

4. To improve moving objects RkNN pruning area, this paper adoptes K-Binding

approach. K-Binding binds K objects by screening candidates and then uses TPL

pruning to improve the pruning efficiency.

5. In order to making RNN efficiently carried out on the probability database. It

proposes probability pruning which just belong PRNN.

Keywords: LBS, Space-time Index, RNN, RkNN, PRNN, Prune Rule

摘要

ABSTRACT

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

§1.1 研究背景 .................................................. 1

§1.2 国内外研究现状 ............................................ 2

§1.3 本文的研究思路 ............................................ 3

§1.3.1 反向最近邻查询 ....................................... 3

§1.3.2 反向最近邻与本文研究内容的关系 ....................... 3

§1.3.3 研究思路 ............................................. 4

§1.4 本文结构 .................................................. 4

第二章相关概念及关键技术 ............................................ 6

§2.1 相关概念 .................................................. 6

§2.1.1 位置服务 ............................................. 6

§2.1.2 最近邻及反向最近邻查询 ............................... 6

§2.1.3 时空数据库 ........................................... 7

§2.1.4 概率数据库 ........................................... 8

§2.2 关键技术 .................................................. 8

§2.2.1 时空数据库索引技术 ................................... 9

§2.2.2 六分区域及 TPL 剪枝 ................................... 9

§2.2.3 Lazy updates 方法 ................................... 10

第三章时空数据库索引技术 ........................................... 11

§3.1 时空数据库 ............................................... 11

§3.1.1 时空数据库模型 ...................................... 11

§3.1.2 移动数据对象查询 .................................... 13

§3.2 离散数据索引结构 ......................................... 13

§3.2.1 3DR-树索引 .......................................... 13

§3.2.2 HR-树索引 ........................................... 14

§3.3 连续数据索引结构 ......................................... 15

§3.3.1 TPR-树索引 .......................................... 16

§3.3.2 PMR-四叉树索引 ...................................... 17

§3.3.3 Q+R 树索引 ...........................................18

§3.4 时空数据库索引技术的实现 ................................. 20

§3.4.1 HR-树索引的实现 ..................................... 20

§3.4.2 TPR-树索引的实现 .................................... 22

§3.4.3 PMR-四叉树索引的实现 ................................ 23

§3.5 本章小结 ................................................. 25

第四章移动对象反向最近邻及反向 K 最近邻查询 ......................... 27

§4.1 移动对象反向最近邻查询 ................................... 27

§4.1.1 思想来源 ............................................ 27

§4.1.2 自适应安全域算法 .................................... 28

§4.1.3 剪枝规则 ............................................ 30

§4.1.4 综合剪枝及验证算法 .................................. 33

§4.2 移动对象反向 k 最近邻查询 ................................. 35

§4.2.1 研究动机 ............................................ 35

§4.2.2 K-Binding 算法 .......................................36

§4.2.3 K-Binding 扩展 ...................................... 37

§4.2.4 性能评估 ............................................ 38

§4.3 本章小结 ................................................. 39

第五章非确定数据对象概率反向最近邻查询 ............................. 40

§5.1 概率反向最近邻 ........................................... 40

§5.1.1 问题的提出 .......................................... 40

§5.1.2 问题的定义 .......................................... 42

§5.2 概率剪枝规则 ............................................. 43

§5.3 剪枝算法验证 ............................................. 45

§5.3.1 Prune 算法 ...........................................45

§5.3.2 Shortlisting ........................................ 47

§5.3.3 Refinement .......................................... 47

§5.3.4 Verification ........................................ 48

§5.4 性能评估 ................................................. 50

§5.5 本章小结 ................................................. 52

第六章总结与展望 .................................................. 53

参考文献 ............................................................ 55

作者在读期间科研成果简介 ............................................ 59

致谢 ............................................................. 60

第一章绪论

§1.1 研究背景

LBS(Location-Based Services）即位置服务，是一种与空间位置有关的业务，

是由移动通信网络和定位系统相结合的一种增值业务，该业务通过定位技术来获

得移动终端的位置信息，并将该信息运用于与位置相关的各种个人或商业业务[1]。

当前，基于个人消费者需求的智能化，位置信息服务将伴随GPS和无线上网技

术的发展，需求呈大幅度增长趋势[2]。位置服务不但可以提升企业运营与服务水平，

也能为车载GPS的用户提供了更多样化的便捷服务。GPS用户，从地址点导航到兴

趣点服务，再到实时路况技术的应用，不仅可引导用户找到附近的产品和服务，

并可获得更高的便捷性和安全性[3]。

目前，“智慧城市”的概念也逐渐被众多信息化城市实践，同时这也使得反

向最近邻在位置服务中受到了极大的关注。反向最近邻的运用如：大型商场的修

建位置，出租呼叫等业务在生我们的生活中扮演者重要的角色。在军事领域中的

战略部署以及美国911服务等都充分运用到了反向最近邻查询技术[4]。

在现实应用中，对象的位置可以是不断移动变化的，这带来了一系列的不确

定的时空问题，不确定的时空同时也带来了非确定性的数据。因为不确定数据有

其概率的特征，因此在其上所做的查询操作有其特有的复杂性，所以目前在不确

定数据库上做反向最近邻查询的研究不多，但研究的意义却非常的重大。

为了提高查询的效率，索引是提高效率的有效途径。尤其是在移动中的查询，

效率更是服务提供商成败的关键。由于本文涉及到的数据均是时空数据，时空数

据最显著的特点就是多维性和海量数据，它在三维空间数据的基础上添加了时间

维度，使得数据的存储及查询带来了相当大的难度；海量数据使得我们在进行查

询时不仅仅要使用索引，还得使用剪枝规则对海量数据进行高效的筛选，这才能

使反向最近邻查询更高效、更人性化。所以时空数据库索引和剪枝规则成为本文

研究的重点，在时空数据库索引中，本文对离散和连续的索引结构进行深入研究，

在剪枝规则中，本文也研究了多个高效的剪枝方法。

位置服务中非确定数据对象查询处理技术

§1.2 国内外研究现状

美国 Foursquare 的出现，使地理位置服务迅速成为了互联网上的热点，美国

Foursquare 在2009 年3月开始上线，每天新增用户 1.5 万，其狂飙突进的风头盖

过当年的 Twitter；目前，国内的许多嗅觉灵敏的企业已经开始布局 LBS 市场，让

激烈的竞争更加热闹。去年 5月份，街旁网在国内上线，目前已经拥有 25 万用户，

以及超过 300 万的地理位置数据库[4]。

本文主要是对位置服务中的三大重要技术进行了深入研究：时空数据库索引、

移动对象的反向最近邻、不确定数据库上的概率反向最近邻。所以下面将对以上

三个方面进行研究现状介绍。

1. 时空数据库索引：时空数据模型、时空分析和推理、时空数据库管理系统、

时空数据可视化研究成为了时空数据库主要集中研究的几个方向[5]。目前国内外大

多的索引结构是在离散的情况下提出的，它最大的特点是能查询移动对象的过去

及当前属性；学者对连续的索引结构研究甚少，在连续情况下的索引通过建立移

动对象变化的函数来进行，所以它不仅能查询移动对象的过去和当前属性，而且

能预测未来。目前，时空数据库的研究主要是针对移动数据对象进行，它指的是

位置不断变化的空间对象，其变化可以是离散的，但我们在应用中更希望是连续

的，但是目前对连续的研究仍然不足，有待于研究出更高效的连续变化的时空数

据库及其索引。

2. 移动对象的反向最近邻查询：该方面的研究主要是集中于在提高查询效率

的同时，如何减少移动终端的通信开销及如何保持服务器的稳定性。在这方面，

Muhammad Aamir Cheema 及Xuemin Lin 等人提出了 Lazy updates[6]方法，他们通

过为移动对象分配安全域而大大减少了通信开销，通过新的剪枝方法而提高了查

询的效率；但是在服务器稳定性方面有一定的缺陷，不能很好的保证服务器的稳

定负载。在移动对象的反向 K最近邻方面，国内外所做的研究甚少，因为反向 K

最近邻的复杂性高于反向 1最近邻（简称反向最近邻），尤其是剪枝规则，如果

沿用反向 1最近邻的方法进行剪枝，则效果不佳，所剪范围小，且开销特大。

3. 不确定数据库上的概率反向最近邻查询：国内在该方面的研究几乎是空

白，在国外，唯有 Lazy updates 方法的提出者们在该领域有研究性成果，他们在不

确定数据库上首次提出概率反向最近邻查询定义，并给出了较好的查询方法[7]。在

不确定数据库上的概率反向 K最近邻查询，目前在国内外均是空白，尚未有研究

论文在刊物上公开发表，但这并不意味着该方面的研究不重要，或者没有研究者，

主要是因为不确定数据库上的概率反向 K最近邻查询具有相当的复杂性。

第一章绪论

§1.3 本文的研究思路

本节首先给出反向最近邻的简单介绍，然后给出反向最近邻查询与本文研究

内容的关系，最后给出本文的研究思路。

§1.3.1 反向最近邻查询

反向最近邻按查询对象和查询候选对象来分，可分为单色与双色反向最近邻

查询。单色反向最近邻指的是查询对象与查询候选对象都属于同一种类型；双色

反向最近邻指的是查询对象与查询候选对象分别属于不同的类型。在实际运用中，

双色反向最近邻运用较为广泛，如大型商场对居民的反向最近邻查询；战场上救

护人员对受伤士兵的寻找等都属于双色反向最近邻查询。按照查询返回的最近邻

的级数来分，可分为反向 1最近邻与反向 K最近邻查询。反向 1最近邻查询指的

是找出满足以下条件的查询候选对象集：该集合中的每个查询候选对象的 1最近

邻是查询对象。反向 K最近邻查询指的是找出满足以下条件的候选对象：该集合

中的每个查询候选对象的 K最近邻是查询对象[8]。

目前对反向最近邻查询的研究大多集中在对移动对象的研究。包括移动对象

连续反向最近邻查询的研究、移动对象连续反向 K最近邻查询的研究、移动对象

概率反向最近邻的研究。

§1.3.2 反向最近邻与本文研究内容的关系

随着美国的 Foursquare 的出现，街旁网在国内上线，玩转四方、贝多、立方

网、嘀咕网也纷纷涌现，并得到了迅速的发展。这说明，国内外的 LBS 最近发展

相当迅速[4]。

反向最近邻是 LBS 的一个重要运用，随着 LBS 的发展，基于用户位置周边的

商家信息，LBS 会根据用户的过往行为习惯主动的推送至用户眼前。而 LBS 中的

许多运用都用到了反向最近邻查询[4]。

反向最近邻的研究对象通常都具有空间特性和时间的连续性，在实际运用中，

不仅要能查找到过去和当前的信息，而且能对未来的进行预测。这要求在研究反

向最近邻查询的同时要对时空数据库必须深入的研究，时空数据库提供了海量的

时空数据而且其数据具有连续性，能够让我们在现实运用中较精准的预测未来。

因此时空数据库是本文研究的重点之一。

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

15 积分 4人已下载

立即下载 VIP免费下载

摘要：

摘要LBS的模式共有四种：休闲娱乐型、生活服务型、社交型及商业型。随着3G业务的发展，这些模式得到了很好地体现。在LBS中，定位与查询是两个关键的技术，在查询方面，反向最近邻查询是LBS的一个重要运用，在生活中，如商场的选址、出租车智能呼叫以及影响度调查等均需运用到反向最近邻查询技术。在反向最近邻查询中，移动对象的反向最近邻查询、移动对象反向K最近邻查询以及在概率数据库上概率反向最近邻查询是研究的重点，然而在之前的研究中，移动反向最近邻查询在查询效率、通信开销及服务器的稳定性方面，仍有许多的不足之处：查询效率低下，查询的通信开销过大，服务器的稳定性不佳。在移动对象反向K最近邻的研究中，进行剪枝...

展开>> 收起<<

位置服务中非确定数据对象查询处理技术.pdf

共62页,预览7页

还剩页未读，继续阅读

位置服务中非确定数据对象查询处理技术

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

推荐作者

热门标签

举报选择: