CN110134758A - 一种面向连续空间-模糊关键字查询的索引方法 - Google Patents

Abstract

本发明提供了一种面向连续空间‑模糊关键字查询的索引方法，在搜索窗口输入查询语句，根据查询语句创建索引结构，根据索引结构对空间文本流数据进行过滤；对空间文本流数据进行过滤的过程中，对所述查询语句并行多线程进行one‑permutation hash signature处理，从空间文本流数据中得到与查询语句对应的相似标签；在自适应索引结构AP‑tree中嵌入相似标签，根据one‑permutation hash signature计算，进行相似标签的区分，得到最优标签，将与最优标签对应的数据作为最终的搜索结果进行输出。在GPU‑CPU之间的数据通信中，加入big‑kernel通信策略，以便加速搜索；数据通信分为四个阶段：预取地址生成、数据装填、数据传输和核计算。本发明的有益效果是：降低了索引结构的空间开销和时间开销，减少了搜索时间。

Description

一种面向连续空间-模糊关键字查询的索引方法

技术领域

本发明涉及空间文本流数据索引查询技术领域，尤其涉及一种面向连续空间-模糊关键字查询的索引方法。

背景技术

随着移动互联网时代的到来与高速发展，许多基于LBS(Location-BasedServices)的应用软件大量增加，这些软件的应用产生了海量的空间文本流数据，利用高效的分析技术处理空间文本流数据，可以给人们的生活带来极大的便利。但是海量的空间文本流数据也带来了许多挑战：数据量巨大、查询延时增长、数据冗余。

传统空间文本流数据索引查询方法大致可以分为三类：文本优先索引方法(RQ-tree等)、空间优先索引方法(IQ-tree和Rt-tree等)和基于位置信息和文本信息的自适应索引方法(AP-tree)。但是现有的索引方法在当前应用中面临两个问题：第一，这些索引结构中缺少支持文本近似查询，在搜索空间文本对象时，用户由于输入错误或其他原因可能会使得文本信息输入不准确，这时关键字模糊查询就显得十分重要；第二，上述传统空间文本流数据查询算法是基于CPU实现的，随着数据规模的增加，传统空间文本流数据查询方法已经无法满足软件对数据信息处理的实时性和高效性的需求。

因此，亟需研究一种新的索引方法，使其在满足查询性能的同时达到高效索引的目的，又尽可能降低查询时间和空间开销。

发明内容

为了解决现有技术在空间文本流数据规模增大后查询时间太长，无法满足软件对数据处理实时高效需求与支持文本模糊查询的问题，本发明提供了一种面向连续空间-模糊关键字查询的索引方法，主要包括以下步骤：

S101：在搜索窗口输入查询语句，根据查询语句创建索引结构，根据索引结构对空间文本流数据进行过滤；

S102：对空间文本流数据进行过滤的过程中，对所述查询语句并行多线程进行one-permutation hash signature处理，从空间文本流数据中得到与查询语句对应的相似标签；

S103：在自适应索引结构AP-tree中嵌入相似标签，根据one-permutation hashsignature计算，进行相似标签的区分，得到一个与查询语句最相似的相似标签作为最优标签，然后将空间文本流数据中与最优标签对应的数据作为最终的搜索结果进行输出。

进一步地，对空间文本流数据进行过滤的过程中，GPU-CPU之间进行数据通信在数据通信中加入big-kernel通信策略，以便加速过滤，得到与查询语句相关的信息；

数据通信分为四个阶段：

(1)预取地址生成：GPU端分配出一块内存，生成预取地址，作为地址缓冲器；该地址缓冲器中存储GPU线程需要处理one-permutation hash signature的查询语句的地址；

(2)数据装填：通过地址缓冲器中存储的预取数据的地址，找到查询语句，并将查询语句装配到CPU端的预取缓存器中；

(3)数据传输：通过DMA机制将CPU端的预取缓存器中的查询语句传输至GPU端的数据缓存器；

(4)核计算：GPU线程通过查询语句进行one-permutation hash signature的计算。

进一步地，每个线程处理一个空间-文本对象的文本信息的one-permutationhash signature的计算。

进一步地，通过高效启发算法关键字分区和空间分区算法，结合成本模型，创建自适应索引结构AP-tree；其中，成本模型定量测量两个分区方法的匹配成本，进而选择成本小的分区方法进行区分。

进一步地，采用深度优先的搜索策略以递归调用访问的方式进行相似标签的区分，以得到最终的搜索结果。

本发明提供的技术方案带来的有益效果是：降低了索引结构的空间开销和时间开销，减少了搜索时间。

附图说明

下面将结合附图及实施例对本发明作进一步说明，附图中：

图1是本发明实施例中一种面向连续空间-模糊关键字查询的索引方法的流程图；

图2是本发明实施例中big-kernel策略的原理示意图；

图3是本发明实施例中一种置换哈希方法的示意图；

图4是本发明实施例中空间-模糊关键字查询索引结构图。

具体实施方式

为了对本发明的技术特征、目的和效果有更加清楚的理解，现对照附图详细说明本发明的具体实施方式。

本发明的实施例提供了一种面向连续空间-模糊关键字查询的索引方法。

请参考图1，图1是本发明实施例中一种面向连续空间-模糊关键字查询的索引方法的流程图，具体包括如下步骤：

S101：在搜索窗口输入查询语句，根据查询语句创建索引结构，根据索引结构对空间文本流数据进行过滤；

S102：对空间文本流数据进行过滤的过程中，对所述查询语句并行多线程进行one-permutation hash signature(一种置换哈希标签)处理，从空间文本流数据中得到与查询语句对应的相似标签；

如图2所示，对空间文本流数据进行过滤的过程中，GPU-CPU之间进行数据通信在数据通信中加入big-kernel通信策略，以便加速过滤，得到与查询语句相关的信息；数据通信分为四个阶段：

(1)预取地址生成：GPU端分配出一块内存，生成预取地址，作为地址缓冲器；该地址缓冲器中存储GPU线程需要处理one-permutation hash signature的查询语句的地址；

(2)数据装填：通过地址缓冲器中存储的预取数据的地址，找到查询语句，并将查询语句装配到CPU端的预取缓存器中；

(3)数据传输：通过DMA机制将CPU端的预取缓存器中的查询语句传输至GPU端的数据缓存器；

(4)核计算：GPU线程通过查询语句进行one-permutation hash signature的计算；

首次将各个空间-文本对象中的文本信息提取出来，然后每个线程进行处理一个空间-文本对象的文本信息的one-permutation hash signature的计算；如图3所示，假设有两个关键字集合V₁和V₂，V₁的原始索引为π(V₁)＝{0，5，8}，V2的原始索引π(V₂)＝{1，6，8}；设置一个二进制的D维矩阵，D维矩阵的第一列表示特征，第二列和第三列中的1表示原始索引中含有对应于第一列的特征，0则表示原始索引中不含有对应于第一列的特征；将D维矩阵的列均匀的分为k个部分(bins)，本实施例中，k取3，即D维矩阵的列均匀分为3个部分：bin1、bin2和bin3；标记bin1、bin2和bin3中第二列和第三列的首个非零项，形成新的索引π(V₁)＝{0，2，2}，π(V₂)＝{1，3，2}，新的索引的计算方法如下：新的索引等于原始索引每个bin中第一个非零项的索引减去bins的总数乘以该第一个非零项的索引所属于的bin的编号的差，即π(V₁)＝[0-3×0，5-3×1，8-3×2]＝[0，2，2]，π(V₂)＝[1-3×0，6-3×1，8-3×2]＝[1，3，2]；

π(V₁)与π(V₂)的相似度为对应的bin中索引相同的项数目除以总的bin数目k，即本实施例中π(V₁)与π(V₂)的相似度为1/3。

S103：在自适应索引结构AP-tree中嵌入相似标签，根据one-permutation hashsignature计算，进行相似标签的区分，得到一个与查询语句最相似的相似标签作为最优标签，然后将空间文本流数据中与最优标签对应的数据作为最终的搜索结果进行输出；通过高效启发算法关键字分区和空间分区算法，结合成本模型，创建自适应索引结构AP-tree；其中，成本模型定量测量两个分区方法的匹配成本，进而选择成本小的分区方法进行区分；其中，关键字节点、查询节点和空间节点的原始文本信息都由one-permutation hashsignature代替；

如图4所示，如果查询语句拆分的查询关键字Q的数量不超过预设阈值或者查询关键字Q能按关键字或者空间分区进一步划分，就将所有的查询关键字Q都保留在q节点中；

如果一个查询关键字Q可以通过关键字或空间分区进一步划分，则从父节点传过来的查询关键字Q可以被设置为查询节点q、关键字节点k或者空间节点s；根据查询语句创建的索引结构为树形结构，该索引结构包括查询节点q、文本节点k和空间节点s，查询节点q包括q₁、q₂、......、q₁₀，文本节点k包括k₁-node和k₂-node，空间节点s包括s₁-node和s₂-node。S₁、S₂、......、S₈分别表示进行one-permutation hash signature处理的哈希标签。C₁、C₂、C₃和C₄表示索引结构中每个空间节点s的4块空间区域。若是以关键字分区进行划分，则在q节点中将关键字分区的偏移量l赋给关键字分区成本Ck，偏移量l表示q节点中查询的第l个关键字被用于关键字分区，并记录采用关键字分区方法的成本；同理，若以空间分区进行划分，则在q节点中将空间分区的偏移量m赋给空间分区成本Cs，偏移量m表示q节点中查询的第m个关键字被用于空间分区，并记录采用空间分区方法的成本；然后将当前节点N构建成s节点或者k节点，并将q节点中的查询移动到相关的子节点根据上述方法做进一步处理，采用深度优先的搜索策略以递归调用访问的方式进行相似标签的区分，以得到最终的搜索结果。

本发明的有益效果是：降低了索引结构的空间开销和时间开销，减少了搜索时间。

以上所述仅为本发明的较佳实施例，并不用以限制本发明，凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。

Claims (5)

1.一种面向连续空间-模糊关键字查询的索引方法，其特征在于：包括以下步骤：

S101：在搜索窗口输入查询语句，根据查询语句创建索引结构，根据索引结构对空间文本流数据进行过滤；

S102：对空间文本流数据进行过滤的过程中，对所述查询语句并行多线程进行one-permutation hash signature处理，从空间文本流数据中得到与查询语句对应的相似标签；

S103：在自适应索引结构AP-tree中嵌入相似标签，根据one-permutation hashsignature计算，进行相似标签的区分，得到一个与查询语句最相似的相似标签作为最优标签，然后将空间文本流数据中与最优标签对应的数据作为最终的搜索结果进行输出。

2.如权利要求1所述的一种面向连续空间-模糊关键字查询的索引方法，其特征在于：在步骤S102中，对空间文本流数据进行过滤的过程中，GPU-CPU之间进行数据通信在数据通信中加入big-kernel通信策略，以便加速过滤，得到与查询语句相关的信息；

数据通信分为四个阶段：

(1)预取地址生成：GPU端分配出一块内存，生成预取地址，作为地址缓冲器；该地址缓冲器中存储GPU线程需要处理one-permutation hash signature的查询语句的地址；

(2)数据装填：通过地址缓冲器中存储的预取数据的地址，找到查询语句，并将查询语句装配到CPU端的预取缓存器中；

(3)数据传输：通过DMA机制将CPU端的预取缓存器中的查询语句传输至GPU端的数据缓存器；

(4)核计算：GPU线程通过查询语句进行one-permutation hash signature的计算。

3.如权利要求2所述的一种面向连续空间-模糊关键字查询的索引方法，其特征在于：每个线程处理一个空间-文本对象的文本信息的one-permutation hash signature的计算。

4.如权利要求1所述的一种面向连续空间-模糊关键字查询的索引方法，其特征在于：在步骤S103中，通过高效启发算法关键字分区和空间分区算法，结合成本模型，创建自适应索引结构AP-tree；其中，成本模型定量测量两个分区方法的匹配成本，进而选择成本小的分区方法进行区分。

5.如权利要求1所述的一种面向连续空间-模糊关键字查询的索引方法，其特征在于：在步骤S103中，采用深度优先的搜索策略以递归调用访问的方式进行相似标签的区分，以得到最终的搜索结果。