一种基于路网反空间关键字查询的最佳选址方法

摘要

一种基于路网反空间关键字查询的最佳选址方法，对于数据集采用基于连接聚簇的索引结构存储，并利用类迪杰斯特拉搜索方法来遍历索引；在遍历索引时本发明首先计算得到查询商家的潜在竞争商家的候选结果；接着利用提出的相关规则进行验证，判断其是否为真正的竞争商家。本发明结合了空间数据库的现有技术和反空间关键字算法，并且整个查询过程不需要遍历整个数据集，从而提供了最佳性能。

说明书

技术领域

本发明涉及数据库的索引与查询技术，特别是一种基于路网反空 间关键字查询的最佳选址方法。

背景技术

空间数据库是作为一种应用技术而诞生和发展起来的，其目的是 为了存储、管理和检索各种地理空间数据(包括空间数据和非空间数 据)。目前，空间数据库被广泛地应用于地理信息系统、计算机辅助 设计、多媒体信息系统以及数据仓库，为以上系统提供数据存储和查 询解决方案。路网空间数据库作为空间数据库的重要组成部分，由于 其广泛的应用得到了越来越多的关注。

为了快速、有效的访问路网空间数据，专家学者们提出了大量的 空间索引方式。迄今为止，影响最大、应用最广泛的基于路网空间的 索引是基于连接聚簇的索引方法。它利用了现有的路网的邻接信息， 其构建思想是对任意路网节点的邻接节点以及路网上得数据点分别 聚类存储，再用B树进行索引，从而达到最小化存取代价的目的。

在此基础上，专家学者们提出了各种各具特色的基于路网的查询 及解决方法，如最近邻查询、连续最近邻查询、反向最近邻查询。其 中基于路网的反最近邻查询是最近提出的一种新颖的查询。它主要从 商家的角度进行查询，向商家返回基于路网距离影响用户最多的地 址，从而向帮助商家进行选址推荐。

目前，针对路网反最近邻查询已有成熟的解决方案。但是在某些 情况下，路网反最近邻查询不仅仅需要考虑空间信息，文本描述信息 作为数据点的重要组成部分，在已有的方法中却没有得到有效利用。 为了更好的帮助商家做出最佳选址决策，这就要求系统能够处理路网 环境下带有文本信息的反最近邻查询结果。但是现有的方法都不能有 效的解决。

发明内容

本发明要克服现有技术不能有效利用文本描述信息的缺点，提供 一种基于路网反空间关键字查询的最佳选址方法。

本发明解决其技术问题所采用的技术方案步骤如下：

步骤(1)：收集已有商家信息，对其建立索引，收集查询商家备 选地址信息和文本信息；

步骤(2)：对于每一个查询商家备选地址，通过类迪杰斯特拉方 法，并利用查询文本信息，找到与查询商家有潜在竞争关系的商家；

步骤(3)：利用判断规则对步骤(2)中得到的每一个查询商家 备选地址的潜在竞争商家进行验证；

步骤(4)：利用步骤(3)中的结果找到查询商家的最优备选地 址。

所述的步骤(1)中每一个商家的信息包括地址信息和文本信息， 其中地址信息是通过一个地理坐标表示的，文本信息是由一组或多组 关键字表示的；所有商家信息是通过基于连接聚簇的索引模型对其建 立索引的，索引文件包含了所有的商家地理位置信息以及文本信息， 其中地理信息存储于连接表文件中，文本信息存放于数据点文件中； 查询商家的所有信息都存储于文本文件中。

所述的步骤(2)中对于每一个查询商家备选地址，通过类迪杰 斯特拉方法，并利用查询文本信息，找到与查询商家有潜在竞争关系 的商家，是通过判断关键字包含性以及路网距离实现的，计算得到的 数据点集合也就是对查询商家可能构成竞争关系的商家；在计算的过 程中，需要维护一个存放路网节点以及该节点到查询商家地址距离的 优先队列，在该优先队列的队首总是当前距离查询点最近的路网节 点；通过迪杰斯特拉方法扩展路网的获取数据点的过程中，还需要维 护对应于当前路网节点的计数树用于保存关键字计数信息；计数树由 2ⁿ-1个节点构成，每个节点包含三个计数值分别为c₁，c₂以及c₃，其 中c₁表示查询节点到当前节点中关键字等于当前关键字的数据点个 数，c₂表示查询节点到当前节点中关键字包含当前关键字的数据点个 数，c₃表示查询节点到当前节点中邻接边上关键字包含当前关键字的 数据点个数；若所有边界节点计数树的c₁或c₂数值都达到了给定的k 值，则路网扩展结束，因为扩展的路网区域内不可能存在潜在的竞争 商家；其中，在判断数据点是否是潜在竞争商家的过程中，分三种情 况考虑：

2.1)该数据点的关键字集合被查询商家的关键字集合全部包含， 这种状况下根据其当前路网节点的计数树中对应关键字的数值分为 两种情况分别做出不同处理：

a)该数据点关键字集合所对应的当前路网节点的计数树的计数 值小于给定的k值，则将当前数据点添加至候选集合并更新当前节点 的计数树对应数值；

b)该数据点关键字集合所对应的当前路网节点的计数树的计数 值大于或等于给定的k值，更新当前节点的计数树对应数值；

2.2)该数据点的关键字集合被查询商家的关键字集合部分包含， 这种状况下需要更新当前节点的计数树对应数值，不将数据点加入候 选集合中；

2.3)该数据点的关键字集合完全不被查询商家的关键字集合包 含，这种状况下不需要对数据点以及计数树做任何处理。

所述的步骤(3)中利用判断规则对步骤(2)中得到的每一个查 询商家备选地址的潜在竞争商家进行验证，是通过验证潜在竞争商家 的k个包含其关键字集合的最近商家是否包含查询商家来实现的；对 于每一个待验证的潜在竞争商家，首先要在索引中定位该商家的地理 位置以及关键字集合，再根据潜在竞争商家到查询商家的距离范围 内，关键字集合包含潜在竞争商家的关键字集合的所有商家数量来判 断；在判断时，需考虑两种情况：

3.1)在潜在竞争商家到查询商家的距离范围内，如果存在多于 或等于k个商家，其关键字集合包含潜在竞争商家的关键字集合，那 么该潜在竞争商家不是查询商家的真正竞争商家；

3.2)在潜在竞争商家到查询商家的距离范围内，存在小于k个 商家，其关键字集合包含潜在竞争商家的关键字集合，那么该潜在竞 争商家是查询商家的真正竞争商家。

所述的步骤(4)中利用步骤(3)中的结果找到查询商家的最优 备选地址，是根据每一个备选地址所具有的真正竞争商家数量来实现 的，所具有的真正竞争商家数量最少的备选地址即是查询商家的最优 备选地址。

本发明具有的有益效果是：

本发明充分利用了空间数据库中现有索引技术，反最近邻查询以 及带有关键字查询技术，通过只遍历部分路网范围的商家信息便能得 到查询结果，大大降低了I/O时间和CPU时间，提供了最佳性能。

附图说明

图1是本发明的实施步骤流程图。

图2为基于路网反空间关键字查询的最佳选址方法的工作原理 示意图。

图3为查询示意图。

具体实施方式

现结合附图和具体实施对本发明的技术方案作进一步说明：

如图1，图2所示，本发明具体实施过程和工作原理如下：

步骤(1)：收集已有商家信息，对其建立索引，收集查询商家备 选地址信息和文本信息；

步骤(2)：对于每一个查询商家备选地址，通过类迪杰斯特拉方 法，并利用查询文本信息，找到与查询商家有潜在竞争关系的商家；

步骤(3)：利用判断规则对步骤(2)中得到的每一个查询商家 备选地址的潜在竞争商家进行验证；

步骤(4)：利用步骤(3)中的结果找到查询商家的最优备选地 址。

步骤(1)中每一个商家的信息包括地址信息和文本信息，其中 地址信息是通过一个地理坐标表示的，文本信息是由一组或多组关键 字表示的；所有商家信息是通过基于连接聚簇的索引模型对其建立索 引的，索引文件包含了所有的商家地理位置信息以及文本信息，其中 地理信息存储于连接表文件中，文本信息存放于数据点文件中；查询 商家的所有信息都存储于文本文件中。具体如图2中的索引模块所 示。

步骤(2)中对于每一个查询商家备选地址，通过类迪杰斯特拉 方法，并利用查询文本信息，找到与查询商家有潜在竞争关系的商家， 是通过判断关键字包含性以及路网距离实现的，计算得到的数据点集 合也就是对查询商家可能构成竞争关系的商家；在计算的过程中，需 要维护一个存放路网节点以及该节点到查询商家地址距离的优先队 列，在该优先队列的队首总是当前距离查询点最近的路网节点；通过 迪杰斯特拉方法扩展路网的获取数据点的过程中，还需要维护对应于 当前路网节点的计数树用于保存关键字计数信息；计数树由2ⁿ-1个节 点构成，每个节点包含三个计数值分别为c₁，c₂以及c₃，其中c₁表示 查询节点到当前节点中关键字等于当前关键字的数据点个数，c₂表示 查询节点到当前节点中关键字包含当前关键字的数据点个数，c₃表示 查询节点到当前节点中邻接边上关键字包含当前关键字的数据点个 数；若所有边界节点计数树的c₁或c₂数值都达到了给定的k值，则 路网扩展结束，因为扩展的路网区域内不可能存在潜在的竞争商家。 该步骤具体是由图2中的潜在竞争商家计算引擎求得。其中，在判断 数据点是否是潜在竞争商家的过程中，分三种情况考虑：

2.1)该数据点的关键字集合被查询商家的关键字集合全部包含， 这种状况下根据其当前路网节点的计数树中对应关键字的数值分为 两种情况分别做出不同处理：

a)该数据点关键字集合所对应的当前路网节点的计数树的计数 值小于给定的k值，则将当前数据点添加至候选集合并更新当前节点 的计数树对应数值；

b)该数据点关键字集合所对应的当前路网节点的计数树的计数 值大于或等于给定的k值，更新当前节点的计数树对应数值；

2.2)该数据点的关键字集合被查询商家的关键字集合部分包含， 这种状况下需要更新当前节点的计数树对应数值，不将数据点加入候 选集合中；

2.3)该数据点的关键字集合完全不被查询商家的关键字集合包 含，这种状况下不需要对数据点以及计数树做任何处理。

以图3中查询点q为例，我们可以看到，p₄，p₆，p₇以及p₈为舍 弃掉的点，故不需要对这些点进行进一步验证。

步骤(3)中利用判断规则对步骤(2)中得到的每一个查询商家 备选地址的潜在竞争商家进行验证，是通过验证潜在竞争商家的k个 包含其关键字集合的最近商家是否包含查询商家来实现的；对于每一 个待验证的潜在竞争商家，首先要在索引中定位该商家的地理位置以 及关键字集合，再根据潜在竞争商家到查询商家的距离范围内，关键 字集合包含潜在竞争商家的关键字集合的所有商家数量来判断。具体 由图2中潜在竞争商家过滤引擎计算求得，在判断时，需考虑两种情 况：

3.1)在潜在竞争商家到查询商家的距离范围内，如果存在多于 或等于k个商家，其关键字集合包含潜在竞争商家的关键字集合，那 么该潜在竞争商家不是查询商家的真正竞争商家；

3.2)在潜在竞争商家到查询商家的距离范围内，存在小于k个 商家，其关键字集合包含潜在竞争商家的关键字集合，那么该潜在竞 争商家是查询商家的真正竞争商家。

步骤(4)中利用步骤(3)中的结果找到查询商家的最优备选地 址，是根据每一个备选地址所具有的真正竞争商家数量来实现的，所 具有的真正竞争商家数量最少的备选地址即是查询商家的最优备选 地址，具体由图2中真正竞争商家计算引擎计算求得。

本说明书实施例所述的内容仅仅是对发明构思的实现形式的列 举，本发明的保护范围不应当被视为仅限于实施例所陈述的具体形 式，本发明的保护范围也及于本领域技术人员根据本发明构思所能够 想到的等同技术手段。