论文部分内容阅读
空间关键字查询处理技术是近年来数据库领域中的一个研究重点与热点。作为空间数据库查询重要的分支，反Top-k最近邻查询由于其在决策支持，资源分配以及市场营销等方面的广泛应用得到了越来越多学者的关注。然而已有的基于反Top-k最近邻查询的研究要么没有考虑文本信息要么受限于传统的欧式空间。在现实生活中，大部分的空间物体带有文本描述信息且受限于路网空间，已有的方法并不能够高效的处理路网下的带有文本描述信息的反Top-k最近邻查询。鉴于此，本文着重研究了路网下的反Top-k布尔空间关键字查询及其变体处理技术，主要包括如下几个方面: 1.首次引入了基于路网的反Top-k布尔空间关键字查询，并给出其形式化定义以及特征; 2.提出了若干基于过滤和精炼框架的高效的基于路网的反Top-k布尔空间关键字查询算法，算法能够有效地处理任意的k值而不需要任何的预算。 3.我们提出了若干新颖的剪枝规则分别作用于过滤以及精炼两个不同的阶段，以用来高效的剪枝大量的不需要精炼的数据点。除此之外，我们提出了相应的数据结构来辅助剪枝，与此同时起到了加速算法的作用。 4.基于我们提出算法的优良扩展性，我们展示了如何将提出的算法扩展至路网下的反Top-k布尔空间关键字最近邻查询变体问题，分别是双色体查询变体、受限的查询变体以及排序的查询变体。 5.我们设计并实施了基于大量合成数据集以及真实数据集的实验来验证我们提出算法的有效性以及高效性。