欧式空间与道路网上的Top-K查询处理研究

发布时间：2017-03-20 10:08

  本文关键词：欧式空间与道路网上的Top-K查询处理研究，由笔耕文化传播整理发布。

【摘要】：最近十年以来,移动互联网的巨大变革,激发了移动设备,如智能手机的革新以及手机上各类应用的快速发展。在各类应用中,基于地理位置信息的应用(Location-Based Services)就是其中很重要的一大类。Top-K查询就是最经典的一种查询模式。典型的应用场景就是用户使用手机,在某个地理坐标上,表达出查询意图(比如,关键词),系统返回距离用户最近,或跟意图最相关的Top-K结果。在这个问题上,已有不少的研究工作。但是,现有方法存在两方面的缺陷和不足。一方面是查询处理效率上的不足,导致的用户体验较差;另一方面是存储和运算的代价太高,很难支持大规模数据集。本文的研究核心,就是围绕不同的查询方式(是否支持即敲即得),不同空间距离度量(欧式距离,道路网距离),以及不同的文本相似性(是否支持关键词),这三个层面,解决现有方法的以上问题,论文的主要贡献如下:1.欧式空间上即敲即得的关键词Top-K查询:为了实现用户体验更好的即敲即得查询方式,并解决传统查询算法存储代价高,剪枝效果差的问题,论文提出了一种新颖的索引结构,叫做PR-Tree。跟传统方法只基于单个维度构造索引,再增加过滤器的方法的不同之处在于,PR-Tree在构造时候同时考虑了文本和空间这两个维度的信息,从而克服了传统方法在剪枝效果上的缺陷。基于PR-Tree,论文讨论了基于单前缀的查询算法,和基于多关键词的查询方法。与现有方法比较,PR-Tree能普遍快1到2个数量级。2.道路网上的可扩展索引与Top-K查询:基于道路距离的Top-K查询比基于欧式距离的查询更有现实意义,因为无论是行走还是驾车,人们都在道路网络上进行而非直线移动。相比欧式空间,道路网上的Top-K查询处理有两大挑战。第一是如何快速计算点到点最短路,第二是如何做到高效的剪枝。为了解决这两大难题,论文构造了一种平衡树索引,名为G-Tree。G-Tree是通过递归切割道路网构造而成的。为了计算道路距离,在每个G-Tree节点上,会预处理一系列最短路,并开创性的使用“距离拼接算法”,来求解任意两点的最短路。基于这个距离,可以利用最佳优先遍历算法,进行高效的Top-K查询剪枝。G-Tree比当今前沿算法能快2到3个数量级左右,并能轻松支持全美国道路网规模的数据集。3.道路网上基于关键词的Top-K查询:现实中,用户不仅只关心到目标对象的道路距离,还可能通过关键词表达查询意图。论文将查询关键词与目标对象的文本相似度,与道路最短路两者结合起来,加权得到一个新的排名度量进行Top-K查询处理。借助之前G-Tree的框架,论文改造出一种新的索引结构,称为IG-Tree。IG-Tree的每个节点会存储一个关键词的倒排索引,以表示该关键词在这棵子树下可能取得的文本相似性的上界。通过对最佳优先遍历算法的优化,IG-Tree表现出其优秀的剪枝能力和扩展性。
【关键词】：Top-K查询 空间数据库 即敲即得 欧式空间 道路网 关键词查询
【学位授予单位】：清华大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：TP311.13
【目录】：

• 摘要3-5
• abstract5-10
• 第1章 绪论10-21
• 1.1 选题背景和研究动机10-18
• 1.1.1 欧式空间上即敲即得的关键词Top-K查询12-14
• 1.1.2 道路网上的可扩展索引与Top-K查询14-16
• 1.1.3 道路网上基于关键词的Top-K查询16-18
• 1.2 主要研究内容及论文的贡献18-20
• 1.3 章节安排20-21
• 第2章 欧式空间上即敲即得的关键词Top-K查询21-44
• 2.1 研究背景21-22
• 2.2 问题定义22-23
• 2.3 前缀-区域树23-28
• 2.3.1 解决办法概要23-24
• 2.3.2 前缀-区域树24-26
• 2.3.3 PR-Tree的构造26-28
• 2.4 PR-Tree的性质讨论28-29
• 2.4.1 平衡性28-29
• 2.4.2 空间复杂度29
• 2.4.3 存储方式29
• 2.5 查询算法29-34
• 2.5.1 单前缀查询算法29-30
• 2.5.2 多关键词查询算法30-34
• 2.6 排名函数的扩展34-35
• 2.7 实验结果35-41
• 2.7.1 实验设定35-36
• 2.7.2 单前缀查询的对比实验36-38
• 2.7.3 多关键词查询的对比实验38-40
• 2.7.4 不同空间划分策略的影响40
• 2.7.5 可扩展性40-41
• 2.7.6 对排序函数的实验41
• 2.8 相关工作41-42
• 2.8.1 即敲即得的关键词查询41-42
• 2.8.2 空间关键词查询42
• 2.9 总结42-44
• 第3章 道路网上的可扩展索引与Top-K查询44-72
• 3.1 研究背景44-45
• 3.2 问题定义45
• 3.3 G-Tree索引45-49
• 3.3.1 解决办法概要45-46
• 3.3.2 G-Tree的定义46-48
• 3.3.3 G-Tree的构造48
• 3.3.4 G-Tree的空间复杂度48-49
• 3.4 查询算法49-57
• 3.4.1 查询算法概要49-51
• 3.4.2 SPDist函数的实现51-57
• 3.5 时间复杂度分析57
• 3.6 路径恢复57-60
• 3.6.1 概览57-58
• 3.6.2 路径恢复算法58-60
• 3.6.3 路径恢复时间空间复杂度分析60
• 3.7 补充讨论60-62
• 3.7.1 高效计算距离矩阵60-61
• 3.7.2 拓展到有向图61-62
• 3.7.3 平面图的讨论62
• 3.8 实验结果62-68
• 3.8.1 对参数f和τ的验证63-64
• 3.8.2 与现有最前沿方法的比较64-67
• 3.8.3 对路径恢复效率的评估67
• 3.8.4 可扩展性的评估67-68
• 3.8.5 对有向图的评估68
• 3.9 相关工作68-70
• 3.9.1 基于道路网的Top-K查询68-70
• 3.9.2 道路网上移动目标的Top-K查询70
• 3.9.3 道路网上点到点最短路问题70
• 3.10 总结70-72
• 第4章 道路网上基于关键词的Top-K查询72-86
• 4.1 研究背景72-73
• 4.2 问题定义73-74
• 4.3 IG-Tree索引74-77
• 4.3.1 解决办法概要74-75
• 4.3.2 IG-Tree的构造75-76
• 4.3.3 IG-Tree的空间复杂度76-77
• 4.4 查询算法77-80
• 4.4.1 G-Tree查询算法的改进77-79
• 4.4.2 基于IG-Tree的查询算法79-80
• 4.5 实验结果80-83
• 4.5.1 实验设定80-81
• 4.5.2 改进的G-Tree查询处理效率评估81-83
• 4.5.3 基于IG-Tree的关键词Top-K查询效率评估83
• 4.6 相关工作83-84
• 4.6.1 道路网上基于关键词的Top-K查询83-84
• 4.7 总结84-86
• 第5章 总结与展望86-88
• 5.1 论文主要研究工作总结86-87
• 5.2 进一步研究工作及展望87-88
• 参考文献88-93
• 致谢93-95
• 个人简历、在学期间发表的学术论文与研究成果95

【相似文献】

中国博士学位论文全文数据库 前1条

1 钟睿铖;欧式空间与道路网上的Top-K查询处理研究[D];清华大学;2015年

  本文关键词：欧式空间与道路网上的Top-K查询处理研究，由笔耕文化传播整理发布。

，

本文编号：257596