最近十年以来,移动互联网的巨大变革,激发了移动设备,如智能手机的革新以及手机上各类应用的快速发展。在各类应用中,基于地理位置信息的应用(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表现出其优秀的剪枝能力和扩展性。