一种关键字查询方法与装置的制造方法

一种关键字查询方法与装置的制造方法
【技术领域】
[0001] 本发明设及信息处理技术，特别地，设及一种关键字查询方法与装置。
【背景技术】
[0002] 最近，随着大规模空间数据的出现，空间数据查询成为研究的热点。给定一组带有 空间和文字描述的物体，一个空间关键词查询由一组关键字和位置信息构成。一个物体懂 得文字描述含有制定关键字我们就说该个物体覆盖该个关键字。一个查询力图找到覆盖所 有关键字的最近的物体。然而，在一些特定的应用中，只有一些物体的组合才能满足用户的 需求；例如，一个游客想要找到附近一组感兴趣的地方，包括饭店、超市和旅馆；另一个例 子是在交叉学科合作中，项目负责人往往想要找到不同领域的专家或者是具有不能技能的 人。该样看来，一组物体协同的满足用户的需求可W用协同空间关键词查询确切的描述。
[0003] 现有技术已经公开了基于IR树的协同空间关键词算法。在现有技术中，当待处理 的数据集在增大时，算法被发现存在扩展性问题；构建IR树需要大量的时间和内存，并且 找出的结果不能保证最优、效率低下；同时，不依赖索引的精确算法想要的到最优解需要大 量的运行时间。
[0004] 针对现有技术中协同空间关键词算法扩展性差、效率低下的问题，目前尚未有有 效的解决方案。

【发明内容】

[0005] 针对现有技术中协同空间关键词算法扩展性差、效率低下的问题，本发明的目的 在于提出一种关键字查询方法与装置，能够兼容大规模的数据运算，扩展性好；且可W保证 获得最优解，工作效率高。
[0006] 基于上述目的，本发明提供的技术方案如下：
[0007] 根据本发明的一个方面，提供了一种关键字查询方法，包括：
[000引扫描定义范围内的每个物体，并获取每个物体的数据信息；
[0009] 将每个物体的数据信息构建为数据集合；
[0010] 获取查询请求，验证查询请求的合法性；
[ocm] 若查询请求合法，则根据合法查询请求在数据集合中进行查询，并返回符合查询 请求的结果。
[0012] 其中，每个物体的数据信息，包括每个物体的位置信息与关键字信息，其中，每个 物体的关键字信息包括至少一关键字；获取查询请求，为获取一查询向量与一查询范围集 合，其中，查询向量包括一查询位置信息与一查询关键字集合，其中，查询关键字集合包括 至少一关键字，查询范围集合为数据集合的子集；验证查询请求的合法性，为判断查询范围 集合中的每个物体元素是否都包含关键字集合中的至少一关键字，W及判断查询关键字集 合是否为查询范围集合中的每个物体元素的关键字所组成的集合的子集，如果是，则认为 查询请求合法；根据查询请求在数据集合中进行查询，为构建一结果范围集合，其中，结果 范围集合为数据集合的子集，结果范围集合中的每个物体元素都包含关键字集合中的至少 一关键字，查询关键字集合为结果范围集合中的每个物体元素的关键字所组成的集合的子 集，并且结果范围集合与查询向量组成的损失函数应小于查询请求本身的加性损失函数， 其中，加性损失函数为查询向量到查询范围集合或结果范围集合中每个物体元素的距离之 和。
[0013] 并且，访问数据集合，将数据集合分割为大小相同的多个网格，并为每个网格进行 特异性编号，多个网格覆盖数据集合内所有的物体元素；根据每个网格覆盖数据集合内物 体元素的实际情况，建立网格表与反向关键字表；根据网格表与反向关键字表获得数据集 合的局部最优结果范围集合；根据局部最优结果范围集合构建有效物体数据集合，并根据 有效物体数据集合构建结果范围集合。
[0014] 并且，根据每个网格覆盖数据集合内物体元素的实际情况，建立网格表与反向关 键字表包括；根据每个网格的特异性编号与每个网格各自覆盖的物体元素的数据信息，建 立网格表，网格表记录了每个网格与数据集合内的物体元素的对应关系；根据每个网格的 特异性编号、每个网格各自覆盖的物体元素的数据信息、W及物体元素的数据信息被存储 的位置，建立反向关键字表，反向关键字表在每个网格的特异性编号、每个网格各自覆盖的 物体元素的关键字信息、与物体元素的数据信息被存储的位置=者之间建立了对应关系， 反向关键字表还在数据集合内的每个关键字与包含关键字的物体元素所在的每个网格的 特异性编号二者之间建立了对应关系，在数据集合内包含某一关键字的所有物体元素均在 反向关键字表中W-个对应关系进行表示。
[0015] 并且，根据网格表与反向关键字表获得数据集合的局部最优结果范围集合包括： 计算所有网格与查询向量所在网格的网格间距，其中，网格间距的数值等于从任意网格垂 直移动到查询向量所在网格的同一水平线上穿过的网格数量值、与任意网格水平移动到查 询向量所在网格的同一垂直线上穿过的网格数量值中，二者的较大值；建立局部最优有效 结果范围集合，按照网格间距从小到大对所有网格进行排序，按照排序依次选取每一网格， 并检查当前网格中的物体元素的关键字集合中是否包括查询向量的查询关键字集合中至 少一关键字，且该关键字尚未被局部最优有效结果范围集合内的任何物体元素覆盖，如果 是，则将当前网格中的物体元素加入局部最优有效结果范围集合中；检查查询向量中的所 有查询关键字是否都被局部最优有效结果范围集合中所有物体元素的关键字集合的并集 覆盖，若否，则按照网格排序选取下一个网格并W该网格作为当前网格重复进行上一步骤， 直到查询向量中的所有查询关键字都能被局部最优有效结果范围集合中所有物体元素的 关键字集合的并集覆盖。
[0016] 并且，根据局部最优结果范围集合构建有效物体数据集合包括：根据局部最优结 果范围集合与查询请求，计算局部最优结果范围集合的局部最优损失函数；建立有效物体 数据集合，有效物体数据集合为数据集合的子集，有效物体数据集合是W查询向量为中屯、、 W局部最优结果范围集合的局部最优损失函数为半径所构成的球体覆盖的所有数据集合 中物体元素组成的集合。
[0017] 具体地，根据有效物体数据集合构建结果范围集合包括；访问查询关键字集合，并 根据查询关键字集合构建关键字排布集合，关键字排布集合为查询关键字集合的幕集合减 去空集；建立最小距离数组与最小贡献物体数组，最小距离数组与最小贡献物体数组的长 度数值等于关键字排布集合中元素的个数数值，最小距离数组与最小贡献物体数组的内容 与关键字排布集合中的元素一一对应；依次指定关键字排布集合中每个元素为迭代关键字 集合，并将迭代关键字集合与查询位置信息结合构成迭代向量；访问有效物体数据集合中 的每个物体元素，并获取每个物体元素到迭代向量的最小距离、W及达成该最小距离的物 体元素，并将迭代向量的最小距离存入最小距离数组内与关键字排布集合中当前元素相对 应的位置上，并将达成该最小距离的物体元素存入最小贡献物体数组内与关键字排布集合 中当前元素相对应的位置上，其中，若关键字排布集合中当前元素未被有效物体数据集合 中的任意物体元素的关键词所覆盖使得当前物体元素到迭代向量的最小距离不存在，则将 正无穷存入最小距离数组内与关键字排布集合中当前元素相对应的位置上、W及最小贡献 物体数组内与关键字排布集合中当前元素相对应的位置上；根据有效物体数据集合建立有 效物体对数据集合，有效物体对数据集合的元素为有效物体数据集合中的每两个不同物体 元素进行组合的形成的物体对元素；访问有效物体对数据集合中的每个物体对元素，并获 取每个物体对元素中两个物体元素各自到迭代向量的最小距离之和、W及达成该最小距离 的物体对元素，并将迭代向量的最小距离之和与最小距离数组内与关键字排布集合中当前 元素相对应的位置上的现有数字进行比对，若迭代向量的最小距离之和小于现有数字，贝U 将现有数字置为迭代向量的最小距离之和，并清除最小贡献物体数组内与关键字排布集合 中当前元素相对应位置上的内容，将达成该最小距离之和的物体对元素写入最小贡献物体 数组内与关键字排布集合中当前元素相对应位置；依次指定关键字排布集合中每个元素为 迭代关键字集合并执行上述步骤，直到关键字排布集合中的所有元素都被指定过；输出最 小距离数组与最小贡献物体数组的最终结果，最小距离数组全数组之和为加性损失函数的 最小值，最小贡献物体数组全数组所有元素组成的集合为结果范围集合。
[0018] 进一步地，获取每个物体元素到迭代向量的最小距离、W及达成该最小距离的物 体元素，并将迭代向量的最小距离存入最小距离数组内与关键字排布集合中当前元素相对 应的位置上，并将达成该最小距离的物体元素存入最小贡献物体数组内与关键字排布集合 中当前元素相对应的位置上，为使用并行方式处理并写入数据；获取每个物体对元素中两 个物体元素各自到迭代向量的最小距离之和、W及达成该最小距离的物体对元素，并将迭 代向量的最小距离之和与最小距离数组内与关键字排布集合中当前元素相对应的位置上 的现有数字进行比对，若迭代向量的最小距离之和小于现有数字，则将现有数字置为迭代 向量的最小距离之和，并清除最小贡献物体数组内与关键字排布集合中当前元素相对应位 置上的内容，将达成该最小距离之和的物体对元素写入最小贡献物体数组内与关键字排布 集合中当前元素相对应位置，为使用串行方式处理并写入数据。
[0019] 更进一步地，将每个物体的数据信息构建为数据集合，为将每个物体的数据信息 存储在分布式文件系统中，并将数据信息按分布式文件系统的形式构建为数据集合；获取 每个物体元素到迭代向量的最小距离、W及达成该最小距离的物体元素，并将迭代向量的 最小距离存入最小距离数组内与关键字排布集合中当前元素相对应的位置上，并将达成该 最小距离的物体元素存入最小贡献物体数组内与关键字排布集合中当前元素相对应的位 置上，为通过使用服务器控制分布式文件系统的多个物理地址的处理终端处理并写入数 据，并将处理并写入的数据传送到服务器；获取每个物体对元素中两个物体元素各自到迭 代向量的最小距离之和、W及达成该最小距离的物体对元素，并将迭代向量的最小距离之 和与最小距离数组内与关键字排布集合中当前元素相对应的位置上的现有数字进行比对， 若迭代向量的最小距离之和小于现有数字，则将现有数字置为迭代向量的最小距离之和， 并清除最小贡献物体数组内与关键字排布集合中当前元素相对应位置上的内容，将达成该 最小距离之和的物体对元素写入最小贡献物体数组内与关键字排布集合中当前元素相对 应位置，为服务器接受前一步骤的数据，并在服务器本地进行运算，进一步处理并写入数 据。
[0020] 根据本发明的另一个方面，提供了一种关键字查询装置，包括：
[0021] 一服务器，服务器连接至多个处理终端，服务器用于获取查询请求、验证查询请求 的合法性、并根据查询请求访问多个处理终端、向多个处理终端分配第一处理任务、接收第 一处理任务的结果并进行第二处理任务、将第二处理任务的结果输出；
[0022] 多个处理终端，多个处理终端均连接至服务器，每个处理终端各连接至一分布式 存储器，每个处理终端用于接收服务器分配的第一处理任务、访问分布式存储器中的数据、 进行第一处理 任务并将第一处理任务输出到服务器；
[0023] 多个分布式存储器，每个分布式存储器各连接至一处理终端，多个分布式存储器 用于联合存储数据集合中的所有数据信息。
[0024] 其中，服务器建立网格表、建立反向关键字表、建立局部最优结果范围集合、建立 有效物体数据集合，包括；服务器根据每个网格的特异性编号与每个网格各自覆盖的物体 元素的数据信息，建立网格表，网格表记录了每个网格与数据集合内的物体元素的对应关 系；服务器根据每个网格的特异性编号、每个网格各自覆盖的物体元素的数据信息、W及物 体元素的数据信息被存储的位置，建立反向关键字表，反向关键字表在每个网格的特异性 编号、每个网格各自覆盖的物体元素的关键字信息、与物体元素的数据信息被存储的位置 =者之间建立了对应关系，反向关键字表还在数据集合内的每个关键字与包含关键字的物 体元素所在的每个网格的特异性编号二者之间建立了对应关系，在数据集合内包含某一关 键字的所有物体元素均在反向关键字表中W-个对应关系进行表示；服务器计算所有网格 与查询向量所在网格的网格间距，其中，网格间距的数值等于从任意网格垂直移动到查询 向量所在网格的同一水平线上穿过的网格数量值、与任意网格水平移动到查询向量所在网 格的同一垂直线上穿过的网格数量值中，二者的较大值；服务器建立局部最优有效结果范 围集合，按照网格间距从小到大对所有网格进行排序，按照排序依次选取每一网格，并检查 当前网格中的物体元素的关键字集合中是否包括查询向量的查询关键字集合中至少一关 键字，且该关键字尚未被局部最优有效结果范围集合内的任何物体元素覆盖，如果是，则将 当前网格中的物体元素加入局部最优有效结果范围集合中；服务器检查查询向量中的所有 查询关键字是否都被局部最优有效结果范围集合中所有物体元素的关键字集合的并集覆 盖，若否，则按照网格排序选取下一个网格并W该网格作为当前网格重复进行上一步骤，直 到查询向量中的所有查询关键字都能被局部最优有效结果范围集合中所有物体元素的关 键字集合的并集覆盖；服务器根据局部最优结果范围集合与查询请求，计算局部最优结果 范围集合的局部最优损失函数；服务器建立有效物体数据集合，有效物体数据集合为数据 集合的子集，有效物体数据集合是W查询向量为中屯、、W局部最优结果范围集合的局部最 优损失函数为半径所构成的球体覆盖的所有数据集合中物体元素组成的集合。
[0025] 并且，依次指定关键字排布集合中每个元素为迭代关键字集合，并将迭代关键字 集合与查询位置信息结合构成迭代向量；访问有效物体数据集合中的每个物体元素，并获 取每个物体元素到迭代向量的最小距离、W及达成该最小距离的物体元素，并将迭代向量 的最小距离存入最小距离数组内与关键字排布集合中当前元素相对应的位置上，并将达成 该最小距离的物体元素存入最小贡献物体数组内与关键字排布集合中当前元素相对应的 位置上，其中，若关键字排布集合中当前元素未被有效物体数据集合中的任意物体元素的 关键词所覆盖使得当前物体元素到迭代向量的最小距离不存在，则将正无穷存入最小距离 数组内与关键字排布集合中当前元素相对应的位置上、W及最小贡献物体数组内与关键字 排布集合中当前元素相对应的位置上。
[0026] 同时，根据有效物体数据集合建立有效物体对数据集合，有效物体对数据集合的 元素为有效物体数据集合中的每两个不同物体元素进行组合的形成的物体对元素；访问有 效物体对数据集合中的每个物体对元素，并获取每个物体对元素中两个物体元素各自到迭 代向量的最小距离之和、W及达成该最小距离的物体对元素，并将迭代向量的最小距离之 和与最小距离数组内与关键字排布集合中当前元素相对应的位置上的现有数字进行比对， 若迭代向量的最小距离之和小于现有数字，则将现有数字置为迭代向量的最小距离之和， 并清除最小贡献物体数组内与关键字排布集合中当前元素相对应位置上的内容，将达成该 最小距离之和的物体对元素写入最小贡献物体数组内与关键字排布集合中当前元素相对 应位置。
[0027] 同时，服务器验证查询请求的合法性，为判断查询范围集合中的每个物体元素是 否都包含关键字集合中的至少一关键字，W及判断查询关键字集合是否为查询范围集合中 的每个物体元素的关键字所组成的集合的子集，如果是，则认为查询请求合法。
[002引从上面所述可W看出，本发明提供的技术方案通过将构建结果范围集合拆分为第 一任务与第二任务并分别进行计算，避免了使用IR树，得W兼容大规模的数据运算，增强 了扩展性；使用迭代算法构建结果范围集合可W保证获得的结果范围集合最优解，提高了 工作效率；另外，使用网格法将数据集合缩减成有效物体数据集合再进行迭代运算，大幅度 削减了不相关的计算量，降低了输入输出数据的耗时，进一步缩减了运算时间。
【附图说明】
[0029] 为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例中所 需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施 例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可W根据该些附图获 得其他的附图。
[0030] 图1为根据本发明实施例的一种关键字查询方法的流程图；
[0031] 图2为根据本发明实施例的一种关键字查询方法中，反向关键字表中所记载的对 应关系的示意图；
[0032] 图3为根据本发明实施例的一种关键字查询方法中，W查询向量所在的网格为中 屯、的网格内物体元素分布图；
[0033] 图4为根据本发明实施例的一种关键字查询方法中，W查询向量所在的网格为中 屯、的网格对查询向量所包含的关键字的覆盖情况示意图；
[0034] 图5为根据本发明实施例的一种关键字查询方法中，为解决MKC问题而建立的有 效物体数据集合在网格中的覆盖情况示意图；
[0035] 图6为根据本发明实施例的一种关键字查询方法的分布式文件系统架构图；
[0036] 图7为根据本发明实施例的一种关键字查询装置的框图；
[0037] 图8为根据本发明实施例的一种关键字查询方法与装置中，Sum-BS与8皿-化〇在 GN数据集上的运算时间走势图；
[003引图9为根据本发明实施例的一种关键字查询方法与装置中，Sum-BS与8皿-化0在Web数据集上的运算时间走势图；
[0039] 图10为根据本发明实施例的一种关键字查询方法与装置中，固定查询关键字数 量为5时，Sum-BS与Sum-Cao在Hotel数据集上的运算时间走势图。
[0040] 图11为根据本发明实施例的一种关键字查询方法与装置中，Sum-GS与Sum-BS在 GN数据集上的运算时间走势图；
[0041] 图12为根据本发明实施例的一种关键字查询方法与装置中，Sum-GS与Sum-BS在 Web数据集上的运算时间走势图；
[0042] 图13为根据本发明实施例的一种关键字查询方法与装置中，平均关键字数量 0.ilH逐渐增加时，Sum-GS与Sum-BS在化tel数据集上的运算时间走势图；
[0043] 图14为根据本发明实施例的一种关键字查询方法与装置中，逐渐拓展GN数据集 的物体元素数量时，Sum-GS与Sum-BS在GN数据集上的运算时间走势图；
[0044] 图15为根据本发明实施例的一种关键字查询方法与装置中，运算节点数量逐步 扩展时，Sum-GS与Sum-BS在Web数据集上的运算时间走势图。
【具体实施方式】
[0045] 为使本发明的目的、技术方案和优点更加清楚明白，下面将结合本发明实施例中 的附图，对本发明实施例中的技术方案进一步进行清楚、完整、详细地描述，显然，所描述的 实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域 普通技术人员所获得的所有其他实施例，都属于本发明保护的范围。
[0046] 根据本发明的实施例，提供了一种关键字查询方法。
[0047] 如图1所示，根据本发明实施例提供的关键字查询方法包括：
[0048] 步骤S101，扫描定义范围内的每个物体，并获取每个物体的数据信息；
[0049] 步骤S103,将每个物体的数据信息构建为数据集合；
[0化日]步骤S105,获取查询请求，验证查询请求的合法性；
[0化1] 步骤S107,若查询请求合法，则根据合法查询请求在数据集合中进行查询，并返回 符合查询请求的结果。
[0化2] 其中，每个物体的数据信息，包括每个物体的位置信息与关键字信息，其中，每个 物体的关键字信息包括至少一关键字。物体的位置信息用于计算物体之间、或物体与某一 点之间的距离，可用于比较远近，而比较远近在本发明的环境下就意味着价值大小。在其他 条件相同时，相对于查询的起点越近的物体被选中的倾向就越高。
[0化3]其中，获取查询请求，为获取一查询向量与一查询范围集合，其中，查询向量包括 一查询位置信息与一查询关键字集合，其中，查询关键字集合包括至少一关键字，查询范围 集合为数据集合的子集。对于任一查询请求，均通过查询范围集合指定一个查询范围，查询 请求只在查询范围中生效。查询向量中的查询位置信息即查询的起始点，查询位置信息与 物体位置信息决定了物体的距离，即物体的价值；查询关键字集合包括了查询关键字，所有 物体的关键字信息与查询关键字新型比对时可判断出物体是否为被查询所需要的物体。
[0054] 其中，验证查询请求的合法性，为判断查询范围集合中的每个物体元素是否都包 含关键字集合中的至少一关键字，W及判断查询关键字集合是否为查询范围集合中的每个 物体元素的关键字所组成的集合的子集，如果是，则认为查询请求合法。查询请求的合法性 表示着查询范围集合中的确存在着查询向量所指向的物体，一个合法的查询请求必然会获 得结果。相反地，没有合法性的查询请求意味着查询向量在查询范围集合中找不到符合条 件的物体，该查询请求不会得出查询结果，也没有实际意义。
[0055] 其中，根据查询请求在数据集合中进行查询，为构建一结果范围集合，其中，结果 范围集合为数据集合的子集，结果范围集合中的每个物体元素都包含关键字集合中的至少 一关键字，查询关键字集合为结果范围集合中的每个物体元素的关键字所组成的集合的子 集，并且结果范围集合与查询向量组成的损失函数应小于查询请求本身的加性损失函数， 其中，加性损失函数为查询向量到查询范围集合或结果范围集合中每个物体元素的距离之 和。本发明中使用了加性损失函数，即单纯的线性距离之和来判定物体的价值，因为单纯的 线性距离之和是最普适的；如果有需要，也可W按需更换成其他带有不同权重的、非线性的 价值判定方式。
[0056] 使用数学语言对问题进行描述如下：
[0057] 设数据集合为0。对于每一个物体元素0G0,都有0.A表示0的位置信息，0.iD 表示0的关键字信息。对于给定的查询q= (q.A，q.iD)与相关物体集合S，如果每个oGS 都至少包含 A,iD中的一个关键字，且S.iD能够覆盖q.iK我们称S，q该个查询请求是合 法的。
[0化8] 我们使用Cost(q，巧表示S的损失函数。给定一个查询q= (q.A，q.iD)，我们将 会找到一组S*，使得S*. 1])能够覆盖q.iK且Cost(q，S*)取得最小值。目P，S*应满足W下 =个条件：
[0061] Cost(q,S*)〈Cost(q,巧。
[0062] 同时，在加法损失函数中，d(〇i，〇p为两点之间的欧氏距离。S的加法损失函数
[0063] 构建结果范围集合包括；访问数据集合，将数据集合分割为大小相同的多个网格， 并为每个网格进行特异性编号，多个网格覆盖数据集合内所有的物体元素；根据每个网格 覆盖数据集合内物体元素的实际情况，建立网格表与反向关键字表；根据网格表与反向关 键字表获得数据集合的局部最优结果范围集合；根据局部最优结果范围集合构建有效物体 数据集合，并根据有效物体数据集合构建结果范围集合。使用网格方式分割数据集合，并使 用下述的技术方案，可W有效地降低不必要的计算量，大幅度缩减计算时间与资源占用；另 一方面，使用网格中屯、坐标取代物体元素坐标，降低的计算精度要求，也大幅度提高了计算 效率。
[0064] 根据每个网格覆盖数据集合内物体元素的实际情况，建立网格表与反向关键字表 包括；根据每个网格的特异性编号与每个网格各自覆盖的物体元素的数据信息，建立网格 表，网格表记录了每个网格与数据集合内的物体元素的对应关系；根据每个网格的特异性 编号、每个网格各自覆盖的物体元素的数据信息、W及物体元素的数据信息被存储的位置， 建立反向关键字表，反向关键字表在每个网格的特异性编号、每个网格各自覆盖的物体元 素的关键字信息、与物体元素的数据信息被存储的位置=者之间建立了对应关系，反向关 键字表还在数据集合内的每个关键字与包含关键字的物体元素所在的每个网格的特异性 编号二者之间建立了对应关系，在数据集合内包含某一关键字的所有物体元素均在反向关 键字表中W-个对应关系进行表示。网格表与反向关键字表都是静态的，只需计算一次就 能持续使用，不需要更新。
[0065] 根据网格表与反向关键字表获得数据集合的局部最优结果范围集合包括；计算所 有网格与查询向量所在网格的网格间距，其中，网格间距的数值等于从任意网格垂直移动 到查询向量所在网格的同一水平线上穿过的网格数量值、与任意网格水平移动到查询向量 所在网格的同一垂直线上穿过的网格数量值中，二者的较大值；建立局部最优有效结果范 围集合，按照网格间距从小到大对所有网格进行排序，按照排序依次选取每一网格，并检查 当前网格中的物体元素的关键字集合中是否包括查询向量的查询关键字集合中至少一关 键字，且该关键字尚未被局部最优有效结果范围集合内的任何物体元素覆盖，如果是，则将 当前网格中的物体元素加入局部最优有效结果范围集合中；检查查询向量中的所有查询 关键字是否都被局部最优有效结果范围集合中所有物体元素的关键字集合的并集覆盖，若 否，则按照网格排序选取下一个网格并W该网格作为当前网格重复进行上一步骤，直到查 询向量中的所有查询关键字都能被局部最优有效结果范围集合中所有物体元素的关键字 集合的并集覆盖。
[0066] 根据局部最优结果范围集合构建有效物体数据集合包括：根据局部最优结果范围 集合与查询请求，计算局部最优结果范围集合的局部最优损失函数；建立有效物体数据集 合，有效物体数据集合为数据集合的子集，有效物体数据集合是W查询向量为中屯、、W局部 最优结果范围集合的局部最优损失函数为半径所构成的球体覆盖的所有数据集合中物体 元素组成的集合。
[0067] 数据集合的每一个物体元素都会被W分布式的方式检查是否对损失函数作出贡 献。根据我们系统的体系架构，所有数据被存储在分布式系统中。数据输入输出消耗的时 间成本远高于在内存中的计算的时间成本。由此可W判断，为了进一步提高算法的效率，我 们需要减少数据输入输出的总量。
[0068] 我们应该消除掉不会对最终损失函数结果有影响的物体元素。因此，我们提出运 用基于网格的方法去优化基准算法。首先，我们把整个查询空间划分成小的网格。选择基 于网格的索引主要基于W下两点：网格索引是，也就是数据独立的，或者叫空间驱动的，任 意物体元素的改变不会影响网格索引的结构；同时，其他索引技术一一如IR树一一是数据 驱动型的，更加有利于数据的存储和捜索，而非静态处理。
[0069] 我们试图特定区域的目标数据量。一旦区域被确定了，目标点也就被确定了。该 样，空间驱动的网格算法更加适合我们的需求。因此，我们使用网格的方法去划分数据。
[0070] 下面根据具体实施例进一步说明本发明从划分网格到获得有效物体数据集合部 分的技术方案。
[0071] 使用网格（尤其是正方形网格）来对物体元素分区。起始阶段，我们把空间划分 成多个网格c= {cj。如图2的左表所示，每个网格有一特异性编码。所有的网格覆盖了 所有的数据元素，而所有的数据点可W按网格的方式被访问。我们预先计算分区过程，并建 立了网格表和反向关键字表。
[0072] 为了从网格中选择相应的目标项，我们构建一种网格结构。该种结构形如 (Ci，Lo(Ci)}，其中，Ci表示网格的特异性编码，Lo(Ci)表示网格的位置信息。基于该样的结 构，给定一个Ci，我们可W直接访问到其中的所有物体元素。此外，我们还使用中屯、点的坐 标来加速网格的访问速度。一旦查询向量q已知，那么包含该个查询点的网格已经相应的 目标物体都会被确定下来。
[0073] 为了加速查询过程，我们创建了反向关键字表。反向关键字表包括所有独立关键 字的字典，与按照网格特异性编码和对应关键字划分的网格信息列表。存储网格特异性编 码而非物体元素可W有效在于减少存储开销并提高访问速度。所有包含关键字k的在一个 网格中的物体都会被表示成一条反向关键字列表中的记录。可W找到任一给定关键字k相 应的网格，W及同时该些覆盖给定关键字k的网格里的其他物体。
[0074] 如图2所示，我们把整个数据集合划分成10*7的长方形网格，其中，Ce,4和C8,5分 别表示坐标点化4)和化5)的网格。每个网格中的节点都有一个纸箱存储物体信息的标 示点，如Ps在C8,5中，被存储于Blocks;pe在Ce，4中，被存储于Blocks。
[0075] 网格中不包含查询向量q所包含的关键字都没有进行进一步计算的必要。对于一 个给定的查询向量q，首先检查查询向量q被哪个网格C。覆盖，并检查该网格是否包括能满 足查询向量q的关键字。如果存在该样的关键字，那么C。被加入候选列表化ist。如果仍 然有未被化ist中的网格所满足的查询向量q的关键字，就进一步查询C。周围的网格。我 们用Q表示对于查询向量q的当前捜索空间，r作为从任意网格到C。的查询步长。r的计 算方法如下：
[0076]r=max值N(X),DN(y))
[0077] 该里DN(x)指的是从X轴上看c。到指定网格之间穿过的网格数量，DN(y)同理。 如图3所示，cy到C4,3的步长为r= 1。我们通过增加步长的方式逐渐增大当前捜索空间 0,直到查询向量q的所有关键字都被化ist中的网格所覆盖。如图4所示，在第一次迭代 中，步长r= 0, 〇4,3被加入化ist，因为〇4,3包含ks;q的关键字为k2与ks，还没有被化ist 所完全覆盖，算法继续运行；在第二次迭代中，步长r= 1，C5,2被加入化ist，因为C5,2包含 k,。至此，所有关键字都被覆盖，算法终止。为了加速匹配关键字的过程，每个网格都有一 个关键字向量，用来表示是否包含关键字（即图3中所示的Q0和0 1)，该样我们就可W方 便的中选出至少查询向量q中一个关键字的网格。
[007引对于一个给定的查询向量q，其结果范围集合用S表示。如果每个物体元素只覆盖 一个关键字，即满足W下条件：
[0079] VoES
[0080] ISnq.1])I I= 1
[0081] ISI二Iq?嗦
[0082] 则该问题被称为单点覆盖。直接选取能覆盖查询向量q的满足最小化条件的所有 物体元素就得到结果范围集合。如果一个物体元素含有多个关键字，我们就称该样的问题 为MKC问题。单点覆盖的解不一定是MKC问题的解。
[0083] 如图4所示，对于查询向量q，q.A被C。所覆盖，且q. 1])=化2,kg}。在单点覆盖问 题中，结果范围集合为S〇= {p。Pa}。加入MKC问题的情况讨论一般性时，那么S〇= {p。Pal 就不是结果范围集合，因为存在〔〇31:(9，口6)<〔〇31：(9,5。）使得5。={口1，口2}的损失函数并非 最小值。
[0084] 对于MKC问题，虽然依照上述方法不能直接获得结果范围集合，但我们可W确定 其结果范围集合的损失函数不能超过Cost(q，S。）。在极端情况下，所有的查询关键字q.iD 被一个单独的目标物体P*所覆盖，即q.1]^np*.i]) =q.i])若。S=p*优于S。，则必有 Cost(q,p*)<Cost(q,S〇) 〇
[0085] 我们可W证明，所有不在已查询向量q为中心Cost(q，S。）为半径的球内的点都不 在结果范围集合中。
[0086]如图5所示，显然有Cost(q, {pe})<Cost(q,{pi，P2})，而在MKC问题中目前只能获 得非最优的近似解或二{p 1，P2：}。基于Cost (q，S。)，我们拓展捜索空间到一个圆形区域Q*， 获取Q*内所覆盖的所有物体元素。将该些物体元素全部加入化ist，包括Cs，2，C4,3与C&4。 现在获得的化ist可再次使用迭代法进行精确的计算。CList中的物体元素与数据集合相 比，省略了大量不会对结果范围集合产生影响的物体元素的相关计算，CList被称为有效物 体数据集合，因为化ist中的物体元素对于查询向量q都是有影响力的。
[0087] 访问查询关键字集合，并根据查询关键字集合构建关键字排布集合，关键字排布 集合为查询关键字集合的幕集合减去空集。关键字排布集合为所有可能形式的关键字的组 合，对于n个关键字，关键字排布集合中会存在2D-1个元素。每个元素会被依次标号用于 下属的两数组中。
[008引建立最小距离数组与最小贡献物体数组，最小距离数组与最小贡献物体数组的长 度数值等于关键字排布集合中元素的个数数值，最小距离数组与最小贡献物体数组的内容 与关键字排布集合中的元素一一对应。最小距离数组，记为Cost[i]，用于存储每一个由i 编码的加法损失函数最小值；最小贡献物体数组，记为Group[i]，用于存储每一个Cost[i] 所对应的贡献物体。
[0089] 依次指定关键字排布集合中每个元素为迭代关键字集合，并将迭代关键字集合与 查询位置信息结合构成迭代向量。
[0090] 访问有效物体数据集合中的每个物体元素，并获取每个 物体元素到迭代向量的最 小距离、W及达成该最小距离的物体元素，并将迭代向量的最小距离存入最小距离数组内 与关键字排布集合中当前元素相对应的位置上，并将达成该最小距离的物体元素存入最小 贡献物体数组内与关键字排布集合中当前元素相对应的位置上，其中，若关键字排布集合 中当前元素未被有效物体数据集合中的任意物体元素的关键词所覆盖使得当前物体元素 到迭代向量的最小距离不存在，则将正无穷存入最小距离数组内与关键字排布集合中当前 元素相对应的位置上、W及最小贡献物体数组内与关键字排布集合中当前元素相对应的位 置上。到此获得的是初步结果查询结果。
[0091] 根据有效物体数据集合建立有效物体对数据集合，有效物体对数据集合的元素为 有效物体数据集合中的每两个不同物体元素进行组合的形成的物体对元素。
[0092] 访问有效物体对数据集合中的每个物体对元素，并获取每个物体对元素中两个物 体元素各自到迭代向量的最小距离之和、W及达成该最小距离的物体对元素，并将迭代向 量的最小距离之和与最小距离数组内与关键字排布集合中当前元素相对应的位置上的现 有数字进行比对，若迭代向量的最小距离之和小于现有数字，则将现有数字置为迭代向量 的最小距离之和，并清除最小贡献物体数组内与关键字排布集合中当前元素相对应位置上 的内容，将达成该最小距离之和的物体对元素写入最小贡献物体数组内与关键字排布集合 中当前元素相对应位置。
[0093] 依次指定关键字排布集合中每个元素为迭代关键字集合并执行上述步骤，直到关 键字排布集合中的所有元素都被指定过。
[0094] 输出最小距离数组与最小贡献物体数组的最终结果，最小距离数组全数组之和为 加性损失函数的最小值，最小贡献物体数组全数组所有元素组成的集合为结果范围集合。
[0095] 下面根据具体实施例进一步说明本发明从构建关键字排布集合到获得结果范围 集合部分的技术方案。
[0096] 现给定一个查询q= (q.入，{kiA.kg})与；个物体元素 〇1= (〇1. {ki，k2})、〇2 =(〇2.^，化1，1^3})、〇3=(〇3.^，化1，1^)，其初步查询结果如下表所示：
[0097]
[009引基于初步查询结果继续进行处理得到的最终结果如下表所示：
[0099]
[0100] 对比上下两步可知，变化出现在i= 3与i= 7位置。当i= 3时，对应的关键 字元素是（ki，k2)，在检索单个物体元素时，只有〇1符合条件，Cost(q，〇i) =4;在访问有效 物体对数据集合中的每个物体对元素时，存在（〇2,〇3)符合条件，且有C〇st(q，{〇2,〇3})= Cost(q, 〇2)+Cost(q, 〇3) =3<4,因此使用（〇2,〇3)取代 〇1，并更新CostU]与GroupU]的对 应项。按照该种方法，我们取到了Cost(q，〇i)的最小值，将损失函数降低到理论值。
[0101] 获取每个物体元素到迭代向量的最小距离、W及达成该最小距离的物体元素，并 将迭代向量的最小距离存入最小距离数组内与关键字排布集合中当前元素相对应的位置 上，并将达成该最小距离的物体元素存入最小贡献物体数组内与关键字排布集合中当前元 素相对应的位置上，为使用并行方式处理并写入数据；获取每个物体对元素中两个物体元 素各自到迭代向量的最小距离之和、W及达成该最小距离的物体对元素，并将迭代向量的 最小距离之和与最小距离数组内与关键字排布集合中当前元素相对应的位置上的现有数 字进行比对，若迭代向量的最小距离之和小于现有数字，则将现有数字置为迭代向量的最 小距离之和，并清除最小贡献物体数组内与关键字排布集合中当前元素相对应位置上的内 容，将达成该最小距离之和的物体对元素写入最小贡献物体数组内与关键字排布集合中当 前元素相对应位置，为使用串行方式处理并写入数据。考虑到前半部分的计算量较大，使用 并行方式计算前半部分可W缩减等待时间，提高计算速度。
[0102] 具体地，如图10所示，将每个物体的数据信息构建为数据集合，为将每个物体的 数据信息存储在分布式文件系统中，并将数据信息按分布式文件系统的形式构建为数据集 合；获取每个物体元素到迭代向量的最小距离、W及达成该最小距离的物体元素，并将迭代 向量的最小距离存入最小距离数组内与关键字排布集合中当前元素相对应的位置上，并将 达成该最小距离的物体元素存入最小贡献物体数组内与关键字排布集合中当前元素相对 应的位置上，为通过使用服务器控制分布式文件系统的多个物理地址的处理终端处理并写 入数据，并将处理并写入的数据传送到服务器；获取每个物体对元素中两个物体元素各自 到迭代向量的最小距离之和、W及达成该最小距离的物体对元素，并将迭代向量的最小距 离之和与最小距离数组内与关键字排布集合中当前元素相对应的位置上的现有数字进行 比对，若迭代向量的最小距离之和小于现有数字，则将现有数字置为迭代向量的最小距离 之和，并清除最小贡献物体数组内与关键字排布集合中当前元素相对应位置上的内容，将 达成该最小距离之和的物体对元素写入最小贡献物体数组内与关键字排布集合中当前元 素相对应位置，为服务器接受前一步骤的数据，并在服务器本地进行运算，进一步处理并写 入数据。
[0103] 根据本发明的实施例，还提供了一种关键字查询装置。
[0104] 如图7所示，根据本发明实施例提供的关键字查询装置包括：
[01化]一服务器31，服务器31连接至多个处理终端32,服务器31用于获取查询请求、验 证查询请求的合法性、并根据查询请求访问多个处理终端32、向多个处理终端32分配第一 处理任务、接收第一处理任务的结果并进行第二处理任务、将第二处理任务的结果输出；
[0106] 多个处理终端32,多个处理终端32均连接至服务器31，每个处理终端32各连接 至一分布式存储器33,每个处理终端32用于接收服务器31分配的第一处理任务、访问分布 式存储器33中的数据、进行第一处理任务并将第一处理任务输出到服务器31 ;
[0107] 多个分布式存储器33,每个分布式存储器33各连接至一处理终端32,多个分布式 存储器33用于联合存储数据集合中的所有数据信息。
[0108] 其中，服务器31建立网格表、建立反向关键字表、建立局部最优结果范围集合、建 立有效物体数据集合，包括；服务器31根据每个网格的特异性编号与每个网格各自覆盖 的物体元素的数据信息，建立网格表，网格表记录了每个网格与数据集合内的物体元素的 对应关系；服务器31根据每个网格的特异性编号、每个网格各自覆盖的物体元素的数据信 息、W及物体元素的数据信息被存储的位置，建立反向关键字表，反向关键字表在每个网格 的特异性编号、每个网格各自覆盖的物体元素的关键字信息、与物体元素的数据信息被存 储的位置=者之间建立了对应关系，反向关键字表还在数据集合内的每个关键字与包含关 键字的物体元素所在的每个网格的特异性编号二者之间建立了对应关系，在数据集合内包 含某一关键字的所有物体元素均在反向关键字表中W-个对应关系进行表示；服务器31 计算所有网格与查询向量所在网格的网格间距，其中，网格间距的数值等于从任意网格垂 直移动到查询向量所在网格的同一水平线上穿过的网格数量值、与任意网格水平移动到查 询向量所在网格的同一垂直线上穿过的网格数量值中，二者的较大值；服务器31建立局部 最优有效结果范围集合，按照网格间距从小到大对所有网格进行排序，按照排序依次选取 每一网格，并检查当前网格中的物体元素的关键字集合中是否包括查询向量的查询关键字 集合中至少一关键字，且该关键字尚未被局部最优有效结果范围集合内的任何物体元素覆 盖，如果是，则将当前网格中的物体元素加入局部最优有效结果范围集合中；服务器31检 查查询向量中的所有查询关键字是否都被局部最优有效结果范围集合中所有物体元素的 关键字集合的并集覆盖，若否，则按照网格排序选取下一个网格并W该网格作为当前网格 重复进行上一步骤，直到查询向量中的所有查询关键字都能被局部最优有效结果范围集合 中所有物体元素的关键字集合的并集覆盖；服务器31根据局部最优结果范围集合与查询 请求，计算局部最优结果范围集合的局部最优损失函数；服务器31建立有效物体数据集 合，有效物体数据集合为数据集合的子集，有效物体数据集合是W查询向量为中屯、、W局部 最优结果范围集合的局部最优损失函数为半径所构成的球体覆盖的所有数据集合中物体 元素组成的集合。
[0109] 并且，多个处理终端32执行第一任务包括；依次指定关键字排布集合中每个元 素为迭代关键字集合，并将迭代关键字集合与查询位置信息结合构成迭代向量；访问有效 物体数据集合中的每个物体元素，并获取每个物体元素到迭代向量的最小距离、W及达成 该最小距离的物体元素，并将迭代向量的最小距离存入最小距离数组内与关键字排布集合 中当前元素相对应的位置上，并将达成该最小距离的物体元素存入最小贡献物体数组内与 关键字排布集合中当前元素相对应的位置上，其中，若关键字排布集合中当前元素未被有 效物体数据集合中的任意物体元素的关键词所覆盖使得当前物体元素到迭代向量的最小 距离不存在，则将正无穷存入最小距离数组内与关键字排布集合中当前元素相对应的位置 上、W及最小贡献物体数组内与关键字排布集合中当前元素相对应的位置上。
[0110] 同时，服务器31执行第二任务包括；根据有效物体数据集合建立有效物体对数 据集合，有效物体对数据集合的元素为有效物体数据集合中的每两个不同物体元素进行组 合的形成的物体对元素；访问有效物体对数据集合中的每个物体对元素，并获取每个物体 对元素中两个物体元素各自到迭代向量的最小距离之和、W及达成该最小距离的物体对元 素，并将迭代向量的最小距离之和与最小距离数组内与关键字排布集合中当前元素相对应 的位置上的现有数字进行比对，若迭代向量的最小距离之和小于现有数字，则将现有数字 置为迭代向量的最小距离之和，并清除最小贡献物体数组内与关键字排布集合中当前元素 相对应位置上的内容，将达成该最小距离之和的物体对元素写入最小贡献物体数组内与关 键字排布集合中当前元素相对应位置。
[0111] 同时，服务器31验证查询请求的合法性，为判断查询范围集合中的每个物体元素 是否都包含关键字集合中的至少一关键字，W及判断查询关键字集合是否为查询范围集合 中的每个物体元素的关键字所组成的集合的子集，如果是，则认为查询请求合法。
[0112] 实验证明了本发明的方法相对于现有技术的方法具有较好的效果。
[0113] 我们使用S种真实数据集合，分别是化tel,GN和Web。化tel数据集合是从 allstays,com美国数据库中提取出的数据。每个物体元素包含对一个酒店的描述和位置信 息。GN数据集合是从geonames,usgs.gov中提取的地理信息数据。Web数据集合是从Tiger CensusBlock和肥BSPAMUK2007.中随机抽取的数据。在扩展性试验中，我们把化tel数据 集合的物体元素数量扩展到2M，4M，8 M和16M。
[0114] 每一组实验中，我们随机生成100个查询进行算法测试，每个算法时间取平局值。 查询点位置信息随机产生，关键字信息首先按频率排序后再随机产生。对于Sum-CoSKQ 问题，我们考虑S种算法Sum-化〇(-种现有技术算法），Sum-BS(另一种相关算法）和 Sum-GS(本发明提供的基于网格的算法）在scala语言中的实现。其中，Sum-GS划分数据 集合网格大小为64X64。所有算法都在21个节点的Amazo址C2集群上执行。每个节点的配 置为 4vCPU。每CPU4Cores，15GBRAM和 80GBSSD。软件环境为Linux、j化1.7、scala1.02 与hadoop2. 2. 0。
[0115] 我们考虑两种指标，运行时间和访问物体数。
[0116] Sum-BS与Sum-Cao的比较结果如图8所示，Sum-BS在GN数据集上比Sum-Cao明显 的缩短了运行时间。另一方面，Sum-BS和Sum-Cao的第二任务上运行时间都与查询关键字 呈现相关性。由于并行化处理数据的帮助，Sum-BS的运行时间从1. 71s缓慢上升到3. 28s 而Sum-Cao从2s大幅上升到548s。图9是Web数据集和GN数据集的运行时间对比图。Web 数据集的特点是更少的物体数量，更多的独立关键字数目W及单位物体数量下更多的平均 关键字。和预期的一样，Sum-BS比Sum-Cao的表现要好。更进一步观察，Sum-BS大部分情 况下，在Web数据集上的运行时间比在GN上要快，并且在关键字等于15的时候只稍微慢了 0.28秒。相反，SmiH：ao当关键字数量上升时，Sum-Cao需要更多的时间去处理数据。进一 步，我们固定查询关键字数量为5,并且扩展物体数量的平均关键字数量|〇.iDl。化tel数 据集原始的平均关键字数为4,现在我们相应的拓展到2倍、4倍、6倍、10倍形成总共5个 数据集。图10表明，Sum-Cao在小数据集上的表现比Sum-BS在并行化框架下的表现要好但 Sum-BS仍然能高效的并行处理CoSKQ问题。原因主要有W下两点出otel数据集的物体数 量与关键字数量都很小，集中式算法也能高效处理；同时，并行框架需要额外的通信开销。
[0117] 我们又测试了一组实验来对比Sum-BS和Sum-GS的性能表现。Sum-GS目标在于减 少捜索空间从而提高效率。在Sum-GS中，只有有可能产生贡献的物体才会被选择，所W，第 二任务的计算开销会减少。图11和图12说明，Sum-GS在GN和Web数据集合上比Sum-BS 要好。和Sum-BS相比，Sum-GS的运行时间，随着查询关键字的增长，会稍微增长。下列S 表分别是化tel,GN和Web数据集合上不同关键词数量下的第二任务中检索物体元素总数， Sum-GS会在第二阶段剪枝掉很多不相关物体。
[0118] TABLEIII;GN，AccessedObjects
[0119]
[0120] TABLEIV;Web，AccessedObjects
[0121]
[0122] TABLEV;Hotel，AccessedObjects
[0123]
[0124]图13示出了在拓展物体关键字数量时Sum-GS和Sum-BS的运行时间差异。当平 均关键字数量|〇. 增加时，候选区域变小从而缩短了处理时间。Sum-GS不仅在运行时间 上快于Sum-BS，而且读取的数量更小。如表5所示，Sum-GS只分别读取了 97, 68, 53, 44, 27 个物体元素，相对应于平均关键字数量为4, 8, 16, 24, 40。
[01巧]可扩展性测试分成数据集扩展性测试和运算节点可扩展性测试两个方面。首先我 们拓展GN数据集的物体元素数量，再拓展运算节点的数量。查询关键字数量设置为5。我 们首先考察算法的扩展性在5个人造数据集上的表现。GN数据集合一共含有1868821个物 体元素。我们拓展其数量为2倍，4倍，8倍，16倍。如图14所示，两种算法都能高效的处 理扩展后的数据。Sum-GS由于剪枝的作用快运Sum-BS。表6显示了两种算法访问的物体 元素数量。归功于Sum-GS的剪枝策略，当数据量增长时，其拥有更好的运行时间低成长率。 之后我们测试了算法在运算节点扩充时的表现。我们从起始5节点扩展到30节点，步长为 5。如图15所示，两个算法随着节点的扩展，运行时间在下降。同时我们观察到，Sum-BS在 20个节点，Sum-GS在10个节点时，由于并行通信的开销，运行时间略微上升。
[01%] 总体上，Sum-GS在运行时间和访问数据量上都比Sum-BS和Sum-Cao要好，并且Sum-GS具有较好的可扩展性。
[0127]综上所述，借助于本发明的上述技术方案，通过将构建结果范围集合拆分为第一 任务与第二任务并分别进行计算，避免了使用IR树，得W兼容大规模的数据运算，增强了 扩展性；使用迭代算法构建结果范围集合可W保证获得的结果范围集合最优解，提高了工 作效率；另外，使用网格法将数据集合缩减成有效物体数据集合再进行迭代运算，大幅度削 减了不相关的计算量，降低了输入输出数据的耗时，进一步缩减了运算时间。
[0128] 所属领域的普通技术人员应当理解；W上所述仅为本发明的具体实施例而已，并 不用于限制本发明，凡在本发明的精神和原则之内，所做的任何修改、等同替换、改进等，均 应包含在本发明的保护范围之内。
【主权项】
1. 一种关键字查询方法，其特征在于，包括： 扫描定义范围内的每个物体，并获取所述每个物体的数据信息； 将所述每个物体的数据信息构建为数据集合； 获取查询请求，验证所述查询请求的合法性； 若所述查询请求合法，则根据所述合法查询请求在所述数据集合中进行查询，并返回 符合查询请求的结果。2. 根据权利要求1所述的一种关键字查询方法，其特征在于： 所述每个物体的数据信息，包括每个物体的位置信息与关键字信息，其中，所述每个物 体的关键字信息包括至少一关键字； 所述获取查询请求，为获取一查询向量与一查询范围集合，其中，所述查询向量包括一 查询位置信息与一查询关键字集合，其中，所述查询关键字集合包括至少一关键字，所述查 询范围集合为所述数据集合的子集； 验证所述查询请求的合法性，为判断所述查询范围集合中的每个物体元素是否都包含 所述关键字集合中的至少一关键字，以及判断所述查询关键字集合是否为所述查询范围集 合中的每个物体元素的关键字所组成的集合的子集，如果是，则认为所述查询请求合法； 根据所述查询请求在所述数据集合中进行查询，为构建一结果范围集合，其中，所述结 果范围集合为所述数据集合的子集，所述结果范围集合中的每个物体元素都包含所述关键 字集合中的至少一关键字，所述查询关键字集合为所述结果范围集合中的每个物体元素的 关键字所组成的集合的子集，并且所述结果范围集合与所述查询向量组成的损失函数应小 于所述查询请求本身的加性损失函数，其中，所述加性损失函数为所述查询向量到所述查 询范围集合或所述结果范围集合中每个物体元素的距离之和。3. 根据权利要求2所述的一种关键字查询方法，其特征在于，构建所述结果范围集合 包括： 访问所述数据集合，将所述数据集合分割为大小相同的多个网格，并为所述每个网格 进行特异性编号，所述多个网格覆盖所述数据集合内所有的物体元素； 根据所述每个网格覆盖所述数据集合内物体元素的实际情况，建立网格表与反向关键 字表； 根据所述网格表与所述反向关键字表获得所述数据集合的局部最优结果范围集合； 根据所述局部最优结果范围集合构建有效物体数据集合，并根据所述有效物体数据集 合构建所述结果范围集合。4. 根据权利要求3所述的一种关键字查询方法，其特征在于，根据所述每个网格覆盖 所述数据集合内物体元素的实际情况，建立网格表与反向关键字表包括： 根据所述每个网格的特异性编号与所述每个网格各自覆盖的所述物体元素的数据信 息，建立所述网格表，所述网格表记录了所述每个网格与所述数据集合内的物体元素的对 应关系； 根据所述每个网格的特异性编号、所述每个网格各自覆盖的所述物体元素的数据信 息、以及所述物体元素的数据信息被存储的位置，建立所述反向关键字表，所述反向关键字 表在所述每个网格的特异性编号、所述每个网格各自覆盖的所述物体元素的关键字信息、 与所述物体元素的数据信息被存储的位置三者之间建立了对应关系，所述反向关键字表还 在所述数据集合内的每个关键字与包含所述关键字的所述物体元素所在的所述每个网格 的特异性编号二者之间建立了对应关系，在所述数据集合内包含某一关键字的所有所述物 体元素均在所述反向关键字表中以一个对应关系进行表示。5. 根据权利要求4所述的一种关键字查询方法，其特征在于，根据所述网格表与所述 反向关键字表获得所述数据集合的局部最优结果范围集合包括： 计算所述所有网格与所述查询向量所在网格的网格间距，其中，所述网格间距的数值 等于从所述任意网格垂直移动到所述查询向量所在网格的同一水平线上穿过的网格数量 值、与所述任意网格水平移动到所述查询向量所在网格的同一垂直线上穿过的网格数量值 中，二者的较大值； 建立所述局部最优有效结果范围集合，按照所述网格间距从小到大对所述所有网格进 行排序，按照排序依次选取每一网格，并检查所述当前网格中的物体元素的所述关键字集 合中是否包括所述查询向量的所述查询关键字集合中至少一关键字，且该关键字尚未被所 述局部最优有效结果范围集合内的任何物体元素覆盖，如果是，则将所述当前网格中的物 体元素加入所述局部最优有效结果范围集合中； 检查所述查询向量中的所有所述查询关键字是否都被所述局部最优有效结果范围集 合中所有物体元素的所述关键字集合的并集覆盖，若否，则按照所述网格排序选取下一个 网格并以该网格作为当前网格重复进行上一步骤，直到所述查询向量中的所有所述查询关 键字都能被所述局部最优有效结果范围集合中所有物体元素的所述关键字集合的并集覆 盖。6. 根据权利要求5所述的一种关键字查询方法，其特征在于，根据所述局部最优结果 范围集合构建有效物体数据集合包括： 根据所述局部最优结果范围集合与所述查询请求，计算所述局部最优结果范围集合的 局部最优损失函数； 建立所述有效物体数据集合，所述有效物体数据集合为所述数据集合的子集，所述有 效物体数据集合是以所述查询向量为中心、以所述局部最优结果范围集合的局部最优损失 函数为半径所构成的球体覆盖的所有所述数据集合中所述物体元素组成的集合。7. 根据权利要求6所述的一种关键字查询方法，其特征在于，根据所述有效物体数据 集合构建所述结果范围集合包括： 访问所述查询关键字集合，并根据所述查询关键字集合构建关键字排布集合，所述关 键字排布集合为所述查询关键字集合的幂集合减去空集； 建立最小距离数组与最小贡献物体数组，所述最小距离数组与所述最小贡献物体数组 的长度数值等于所述关键字排布集合中元素的个数数值，所述最小距离数组与所述最小贡 献物体数组的内容与所述关键字排布集合中的元素一一对应； 依次指定所述 关键字排布集合中每个元素为迭代关键字集合，并将所述迭代关键字集 合与所述查询位置信息结合构成迭代向量； 访问所述有效物体数据集合中的每个物体元素，并获取所述每个物体元素到所述迭代 向量的最小距离、以及达成该最小距离的物体元素，并将所述迭代向量的最小距离存入所 述最小距离数组内与关键字排布集合中当前元素相对应的位置上，并将所述达成该最小距 离的物体元素存入最小贡献物体数组内与关键字排布集合中当前元素相对应的位置上，其 中，若关键字排布集合中当前元素未被所述有效物体数据集合中的任意物体元素的关键词 所覆盖使得当前物体元素到所述迭代向量的最小距离不存在，则将正无穷存入所述最小距 离数组内与关键字排布集合中当前元素相对应的位置上、以及最小贡献物体数组内与关键 字排布集合中当前元素相对应的位置上； 根据所述有效物体数据集合建立有效物体对数据集合，所述有效物体对数据集合的元 素为所述有效物体数据集合中的每两个不同物体元素进行组合的形成的物体对元素； 访问所述有效物体对数据集合中的每个物体对元素，并获取所述每个物体对元素中两 个物体元素各自到所述迭代向量的最小距离之和、以及达成该最小距离的物体对元素，并 将所述迭代向量的最小距离之和与所述最小距离数组内与关键字排布集合中当前元素相 对应的位置上的现有数字进行比对，若所述迭代向量的最小距离之和小于现有数字，则将 现有数字置为所述迭代向量的最小距离之和，并清除所述最小贡献物体数组内与关键字排 布集合中当前元素相对应位置上的内容，将所述达成该最小距离之和的物体对元素写入所 述最小贡献物体数组内与关键字排布集合中当前元素相对应位置； 依次指定所述关键字排布集合中每个元素为迭代关键字集合并执行上述步骤，直到所 述关键字排布集合中的所有元素都被指定过； 输出所述最小距离数组与所述最小贡献物体数组的最终结果，所述最小距离数组全数 组之和为所述加性损失函数的最小值，所述最小贡献物体数组全数组所有元素组成的集合 为所述结果范围集合。8. 根据权利要求7所述的一种关键字查询方法，其特征在于： 获取所述每个物体元素到所述迭代向量的最小距离、以及达成该最小距离的物体元 素，并将所述迭代向量的最小距离存入所述最小距离数组内与关键字排布集合中当前元素 相对应的位置上，并将所述达成该最小距离的物体元素存入最小贡献物体数组内与关键字 排布集合中当前元素相对应的位置上，为使用并行方式处理并写入数据； 获取所述每个物体对元素中两个物体元素各自到所述迭代向量的最小距离之和、以及 达成该最小距离的物体对元素，并将所述迭代向量的最小距离之和与所述最小距离数组内 与关键字排布集合中当前元素相对应的位置上的现有数字进行比对，若所述迭代向量的最 小距离之和小于现有数字，则将现有数字置为所述迭代向量的最小距离之和，并清除所述 最小贡献物体数组内与关键字排布集合中当前元素相对应位置上的内容，将所述达成该最 小距离之和的物体对元素写入所述最小贡献物体数组内与关键字排布集合中当前元素相 对应位置，为使用串行方式处理并写入数据。9. 根据权利要求8所述的一种关键字查询方法，其特征在于： 将所述每个物体的数据信息构建为数据集合，为将所述每个物体的数据信息存储在分 布式文件系统中，并将所述数据信息按所述分布式文件系统的形式构建为数据集合； 获取所述每个物体元素到所述迭代向量的最小距离、以及达成该最小距离的物体元 素，并将所述迭代向量的最小距离存入所述最小距离数组内与关键字排布集合中当前元素 相对应的位置上，并将所述达成该最小距离的物体元素存入最小贡献物体数组内与关键字 排布集合中当前元素相对应的位置上，为通过使用服务器控制所述分布式文件系统的多个 物理地址的处理终端处理并写入数据，并将所述处理并写入的数据传送到服务器； 获取所述每个物体对元素中两个物体元素各自到所述迭代向量的最小距离之和、以及 达成该最小距离的物体对元素，并将所述迭代向量的最小距离之和与所述最小距离数组内 与关键字排布集合中当前元素相对应的位置上的现有数字进行比对，若所述迭代向量的最 小距离之和小于现有数字，则将现有数字置为所述迭代向量的最小距离之和，并清除所述 最小贡献物体数组内与关键字排布集合中当前元素相对应位置上的内容，将所述达成该最 小距离之和的物体对元素写入所述最小贡献物体数组内与关键字排布集合中当前元素相 对应位置，为服务器接受前一步骤的数据，并在服务器本地进行运算，进一步处理并写入数 据。10. -种关键字查询装置，其特征在于，包括： 一服务器，所述服务器连接至多个处理终端，所述服务器用于获取查询请求、验证所述 查询请求的合法性、并建立网格表、建立反向关键字表、建立局部最优结果范围集合、建立 有效物体数据集合、同时根据所述查询请求访问所述多个处理终端、向所述多个处理终端 分配第一处理任务、接收所述第一处理任务的结果并进行第二处理任务、将所述第二处理 任务的结果输出； 多个处理终端，所述多个处理终端均连接至所述服务器，所述每个处理终端各连接至 一分布式存储器，所述每个处理终端用于接收服务器分配的所述第一处理任务、访问分布 式存储器中的数据、进行所述第一处理任务并将所述第一处理任务输出到所述服务器； 多个分布式存储器，所述每个分布式存储器各连接至一所述处理终端，所述多个分布 式存储器用于联合存储所述数据集合中的所有数据信息。11. 根据权利要求10所述的一种关键字查询装置，其特征在于，所述服务器建立网格 表、建立反向关键字表、建立局部最优结果范围集合、建立有效物体数据集合，包括： 所述服务器根据所述每个网格的特异性编号与所述每个网格各自覆盖的所述物体元 素的数据信息，建立所述网格表，所述网格表记录了所述每个网格与所述数据集合内的物 体兀素的对应关系； 所述服务器根据所述每个网格的特异性编号、所述每个网格各自覆盖的所述物体元素 的数据信息、以及所述物体元素的数据信息被存储的位置，建立所述反向关键字表，所述反 向关键字表在所述每个网格的特异性编号、所述每个网格各自覆盖的所述物体元素的关键 字信息、与所述物体元素的数据信息被存储的位置三者之间建立了对应关系，所述反向关 键字表还在所述数据集合内的每个关键字与包含所述关键字的所述物体元素所在的所述 每个网格的特异性编号二者之间建立了对应关系，在所述数据集合内包含某一关键字的所 有所述物体元素均在所述反向关键字表中以一个对应关系进行表示； 所述服务器计算所述所有网格与所述查询向量所在网格的网格间距，其中，所述网格 间距的数值等于从所述任意网格垂直移动到所述查询向量所在网格的同一水平线上穿过 的网格数量值、与所述任意网格水平移动到所述查询向量所在网格的同一垂直线上穿过的 网格数量值中，二者的较大值； 所述服务器建立所述局部最优有效结果范围集合，按照所述网格间距从小到大对所述 所有网格进行排序，按照排序依次选取每一网格，并检查所述当前网格中的物体元素的所 述关键字集合中是否包括所述查询向量的所述查询关键字集合中至少一关键字，且该关键 字尚未被所述局部最优有效结果范围集合内的任何物体元素覆盖，如果是，则将所述当前 网格中的物体元素加入所述局部最优有效结果范围集合中； 所述服务器检查所述查询向量中的所有所述查询关键字是否都被所述局部最优有效 结果范围集合中所有物体元素的所述关键字集合的并集覆盖，若否，则按照所述网格排序 选取下一个网格并以该网格作为当前网格重复进行上一步骤，直到所述查询向量中的所有 所述查询关键字都能被所述局部最优有效结果范围集合中所有物体元素的所述关键字集 合的并集覆盖； 所述服务器根据所述局部最优结果范围集合与所述查询请求，计算所述局部最优结果 范围集合的局部最优损失函数； 所述服务器建立所述有效物体数据集合，所述有效物体数据集合为所述数据集合的子 集，所述有效物体数据集合是以所述查询向量为中心、以所述局部最优结果范围集合的局 部最优损失函数为半径所构成的球体覆盖的所有所述数据集合中所述物体元素组成的集 合。12. 根据权利要求11所述的一种关键字查询装置，其特征在于，所述第一任务包括： 依次指定所述关键字排布集合中每个元素为迭代关键字集合，并将所述迭代关键字集 合与所述查询位置信息结合构成迭代向量； 访问所述有效物体数据集合中的每个物体元素，并获取所述每个物体元素到所述迭代 向量的最小距离、以及达成该最小距离的物体元素，并将所述迭代向量的最小距离存入所 述最小距离数组内与关键字排布集合中当前元素相对应的位置上，并将所述达成该最小距 离的物体元素存入最小贡献物体数组内与关键字排布集合中当前元素相对应的位置上，其 中，若关键字排布集合中当前元素未被所述有效物体数据集合中的任意物体元素的关键词 所覆盖使得当前物体元素到所述迭代向量的最小距离不存在，则将正无穷存入所述最小距 离数组内与关键字排布集合中当前元素相对应的位置上、以及最小贡献物体数组内与关键 字排布集合中当前元素相对应的位置上。13. 根据权利要求11所述的一种关键字查询装置，其特征在于，所述第二任务包括： 根据所述有效物体数据集合建立有效物体对数据集合，所述有效物体对数据集合的元 素为所述有效物体数据集合中的每两个不同物体元素进行组合的形成的物体对元素； 访问所述有效物体对数据集合中的每个物体对元素，并获取所述每个物体对元素中两 个物体元素各自到所述迭代向量的最小距离之和、以及达成该最小距离的物体对元素，并 将所述迭代向量的最小距离之和与所述最小距离数组内与关键字排布集合中当前元素相 对应的位置上的现有数字进行比对，若所述迭代向量的最小距离之和小于现有数字，则将 现有数字置为所述迭代向量的最小距离之和，并清除所述最小贡献物体数组内与关键字排 布集合中当前元素相对应位置上的内容，将所述达成该最小距离之和的物体对元素写入所 述最小贡献物体数组内与关键字排布集合中当前元素相对应位置。14. 根据权利要求11所述的一种关键字查询装置，其特征在于，所述服务器验证所述 查询请求的合法性，为判断所述查询范围集合中的每个物体元素是否都包含所述关键字集 合中的至少一关键字，以及判断所述查询关键字集合是否为所述查询范围集合中的每个物 体元素的关键字所组成的集合的子集，如果是，则认为所述查询请求合法。
【专利摘要】本发明公开了一种关键字查询方法与装置，其中，该方法包括：扫描定义范围内的每个物体，并获取每个物体的数据信息；将每个物体的数据信息构建为数据集合；获取查询请求，验证查询请求的合法性；若查询请求合法，则根据合法查询请求在数据集合中进行查询，并返回符合查询请求的结果。本发明将构建结果范围集合拆分为第一任务与第二任务并分别进行计算，避免了使用IR树，得以兼容大规模的数据运算，增强了扩展性；使用迭代算法构建结果范围集合可以保证获得的结果范围集合最优解，提高了工作效率。
【IPC分类】G06F17/30
【公开号】CN104881426
【申请号】CN201510133447
【发明人】赵翔, 徐浩, 何培俊, 葛斌
【申请人】中国人民解放军国防科学技术大学
【公开日】2015年9月2日
【申请日】2015年3月25日