建立基于位置敏感哈希索引的移动感知数据查询方法

专利主权项内容

1.一种建立基于位置敏感哈希索引的移动感知数据查询方法，其特征在于：将高维空间中的对象视为带有位置信息的空间数据点，通过一族哈希函数F()将空间所有对象点映射到m个哈希表T中，其中m＝|F|，给定一个查询点q，分别计算每个q点在哈希函数中的结果值：{f, f…f, f∈F, i＝1, 2…m}.将所有f落入到哈希表T桶中的点作为候选集，用以计算与q之间的距离，最终排序选出距离最近的k个点，即得到kNN结果集；i1(q)2(q)m(q)ii(q)i建立基于倒排位置敏感哈希索引的具体方法为，预先将数据集存储到HDFS分布式文件系统中，启动任务时，通过分布式缓存机制读入一些配置文件LSH哈希函数族，每个Map任务读入由JobTracker指定的数据分片作为输入，然后根据给定的哈希函数对每一个数据对象进行哈希映射降维，将高维向量通过哈希映射之后得到一个哈希值，这一哈希值作为索引值，以键值对的形式进行输出，Map过程的输出作为Reduce的输入，在Reduce里将相同哈希的所有数据对象收集到一起，将数据对象分隔，作为结果输出到HDFS分布式文件系统中进行存储；所述查询是建立基于位置敏感哈希分布式倒排索引的kNN查询，步骤是：设定网格单元大小为ɡ*ɡ，给定一个查询点q，用Aq表示q点所在网格，以r为半径，q为圆心作圆，对于特定的哈希函数，给定一点q，求其相邻点时，首先利用函数分成若干个“桶”key，所述“桶”key代指特定关系存在区域，用hv1、hv2、hv3、、、hvN表示；然后函数利用数据与哈希函数之间的关系对应哈希到特定的桶内同时会使q与其有对应关系的桶内数据进行碰撞，筛选出与q碰撞次数较高的数据进行整合，则就得到某一特定点的相似数据；对于图片的索引，需要更多的特征才能确定某一具体图片，需要求出其他特征的相似数据，给定另一点P，同样建立在同一数据表格中，以R为半径，p为圆心，找出其近邻数据点，p与q点的最近邻中可能出现同一点M，则M为索引的特征数据点的概率就特别大，以此类推，进行哈希，直至找出最终数据；筛选出与q碰撞次数较高的数据的方法如下：设高维数据集合为S，S是图象检索系统中已有大规模图象库，查询对象集合为Q，Q是查询图象对象，先进行高维特征提取后，形成特征集, 对于每个查询对象q属于Q, 初始化关联函数h, h属于G，G是一个哈希族，LSH是一个多轮哈希的算法，不同的哈希函数，会得到不同的哈希结果，h对应q的相似点集合，半径集合R＝getCandidates(hashvalue)，hashvalue是哈希值，不同的哈希值，得到不同的哈希结果，R是桶宽；在某一半径为r的区域内进行有关哈希函数的哈希冲突碰撞，哈希的每个对象为hashvalue＝Computer(q, h)，每一个hashvalue是通过哈希计算函数得到的，多次碰撞直至将数据全部哈希，筛选出碰撞次数相对比较高的对象d＝Computer(q, c), 对象d为对象q的临近点的概率最高，对象d是碰撞可能性最高的对象，用碰撞计数统计代替实际的值，统计碰撞的次数作为最后的排序结果。 搜索马 克 数 据 网