基于改进LSH的协同过滤推荐算法 被引量：13

1

作者 李红梅 郝文宁 陈刚 《计算机科学》 CSCD 北大核心 2015年第10期256-261,共6页

协同过滤是个性化推荐系统中应用较为成功与广泛的技术之一,影响协同过滤推荐质量的关键在于获取目标用户的k近邻用户,然后基于k近邻对其未评价的项目进行评分预测与推荐。针对用户评分数据的规模大、维度高、高度稀疏以及直接进行相似... 协同过滤是个性化推荐系统中应用较为成功与广泛的技术之一,影响协同过滤推荐质量的关键在于获取目标用户的k近邻用户,然后基于k近邻对其未评价的项目进行评分预测与推荐。针对用户评分数据的规模大、维度高、高度稀疏以及直接进行相似性度量的实时性差等对推荐性能的影响,提出一种基于LSH的协同过滤推荐算法,并对其进行改进。该算法基于p稳态分布的局部敏感哈希对用户评分数据进行降维与索引,并采用多探寻的机制对其进行改进,缓解多个哈希表对内存的压力,快速获取目标用户的近邻用户集合,然后采用加权方法来预测用户评分并产生推荐。标准数据集上的实验结果表明,该方法能有效克服评分数据的高维稀疏,并在保证一定推荐精度的前提下,大幅度提高推荐效率和降低内存消耗。 展开更多

关键词 推荐系统 近似近邻 协同过滤 相似性度量 局部敏感哈希

下载PDF 职称材料

基于精确欧氏局部敏感哈希的协同过滤推荐算法 被引量：9

2

作者 李红梅 郝文宁 陈刚 《计算机应用》 CSCD 北大核心 2014年第12期3481-3486,共6页

针对推荐系统中用户评分数据的海量高维与稀疏性,以及直接利用传统相似性度量方法来获取近邻的计算量大、结果不准等对推荐质量的影响,提出基于精确欧氏局部敏感哈希(E2LSH)的协同过滤推荐算法。首先利用精确欧氏局部敏感哈希算法对用... 针对推荐系统中用户评分数据的海量高维与稀疏性,以及直接利用传统相似性度量方法来获取近邻的计算量大、结果不准等对推荐质量的影响,提出基于精确欧氏局部敏感哈希(E2LSH)的协同过滤推荐算法。首先利用精确欧氏局部敏感哈希算法对用户评分数据进行降维处理并构建索引,以快速获取目标用户的近邻用户;然后利用加权策略来预测用户评分,进而完成协同过滤推荐。实验结果表明,该算法能有效解决用户数据的海量高维与稀疏性问题,且运行效率高,具有较好的推荐质量。 展开更多

关键词 精确欧氏局部敏感哈希 协同过滤 相似性度量 推荐系统 近似近邻

下载PDF 职称材料

基于KD树的k-means聚类算法优化 被引量：6

3

作者 薛丁文 李建中 《智能计算机与应用》 2021年第11期194-197,共4页

作为模式识别最基本的分类方法之一,聚类在各个科学领域的数据分析中都扮演着重要的角色。然而随着大数据的出现,聚类分析在前沿发展中不断地面临着计算复杂度和计算成本等新的问题和挑战。通过研究k-means聚类算法的时间复杂度O(nk),... 作为模式识别最基本的分类方法之一,聚类在各个科学领域的数据分析中都扮演着重要的角色。然而随着大数据的出现,聚类分析在前沿发展中不断地面临着计算复杂度和计算成本等新的问题和挑战。通过研究k-means聚类算法的时间复杂度O(nk),针对迭代过程中大量的最近邻计算和其特殊场景,引入KD树作为索引,提出了基于单KD树的近似近邻算法和基于多KD树的交叉搜索算法。将k-means聚类算法的时间复杂度降为O(nlog k),并通过实验验证,基于多树的交叉搜索算法具有与k-means聚类算法相当的聚类质量。 展开更多

关键词 聚类分析 K-MEANS聚类 KD树 近似近邻

下载PDF 职称材料

基于卷积神经网络和监督核哈希的图像检索方法 被引量：36

4

作者 柯圣财 赵永威 +1 位作者 李弼程 彭天强 《电子学报》 EI CAS CSCD 北大核心 2017年第1期157-163,共7页

当前主流的图像检索方法采用的视觉特征,缺乏自主学习能力,导致其图像表达能力不强,此外,传统的特征索引方法检索效率较低,难以适用于大规模图像数据.针对这些问题,本文提出了一种基于卷积神经网络和监督核哈希的图像检索方法.首先,利... 当前主流的图像检索方法采用的视觉特征,缺乏自主学习能力,导致其图像表达能力不强,此外,传统的特征索引方法检索效率较低,难以适用于大规模图像数据.针对这些问题,本文提出了一种基于卷积神经网络和监督核哈希的图像检索方法.首先,利用卷积神经网络的学习能力挖掘训练图像内容的内在隐含关系,提取图像深层特征,增强特征的视觉表达能力和区分性;然后,利用监督核哈希方法对高维图像深层特征进行监督学习,并将高维特征映射到低维汉明空间中,生成紧致的哈希码;最后,在低维汉明空间中完成对大规模图像数据的有效检索.在Image Net-1000和Caltech-256数据集上的实验结果表明,本文方法能够有效地增强图像特征的表达能力,提高图像检索效率,优于当前主流方法. 展开更多

关键词 深度学习 图像检索 卷积神经网络 近似近邻检索 监督核哈希

下载PDF 职称材料

面向近似近邻查询的分布式哈希学习方法 被引量：10

5

作者 文庆福 王建民 +2 位作者 朱晗 曹越 龙明盛 《计算机学报》 EI CSCD 北大核心 2017年第1期192-206,共15页

近似近邻查询是信息检索领域中的一项重要技术.随着文本、图像、视频等非结构化数据规模的迅速增长,如何对海量高维数据进行快速、准确的查询是处理大规模数据所必须面对的问题.哈希作为近似近邻查询的关键方法之一,能够在保持数据相似... 近似近邻查询是信息检索领域中的一项重要技术.随着文本、图像、视频等非结构化数据规模的迅速增长,如何对海量高维数据进行快速、准确的查询是处理大规模数据所必须面对的问题.哈希作为近似近邻查询的关键方法之一,能够在保持数据相似性的条件下对高维数据进行大比例压缩.以往所提出的哈希方法往往都是应对集中式存储的数据,因而难以处理分布式存储的数据.该文提出了一种基于乘积量化的分布式哈希学习方法SparkPQ,并在Spark分布式计算框架下实现算法.在传统的乘积量化方法的基础上,该文首先给出了分布式乘积量化模型的形式化定义.然后,作者设计了一种按行列划分的分布式矩阵,采用分布式K-Means算法实现模型求解和码本训练,利用训练出的码本模型对分布式数据进行编码和索引.最终,该文构建了一套完整的近似近邻查询系统,不仅可以大幅降低存储和计算开销,而且在保证高检索准确率的条件下加速查询效率.在较大规模的图像检索数据集上进行的实验验证了方法的正确性和可扩展性. 展开更多

关键词 近似近邻查询 哈希学习 高维索引 分布式计算 SPARK

下载PDF 职称材料

基于卷积神经网络和E2LSH的遥感图像检索研究 被引量：7

6

作者 彭晏飞 陶进 訾玲玲 《计算机应用与软件》 北大核心 2018年第7期250-255,共6页

遥感图像是一种特征维度很高的图像,当前的遥感图像检索技术图像特征表达能力不强,并且利用海明距离排序后还需计算欧式距离,产生信息损失,严重制约了遥感图像检索技术的性能。基于上述问题,提出一种基于卷积神经网络和E2LSH的遥感图像... 遥感图像是一种特征维度很高的图像,当前的遥感图像检索技术图像特征表达能力不强,并且利用海明距离排序后还需计算欧式距离,产生信息损失,严重制约了遥感图像检索技术的性能。基于上述问题,提出一种基于卷积神经网络和E2LSH的遥感图像检索技术,将遥感图像进行降噪处理之后,利用已经预训练过的VGGNet-D卷积神经网络模型提取图像深层次的特征,挖掘隐含的图像信息;利用L个E2LSH(Exact Euclidean Locality-Sensitive Hashing)函数对提取的特征在保证度量距离的同时进行高效降维并构建L个索引结构;利用L个索引完成粗检索以构成候选集。直接计算并排序候选集的欧氏距离来完成近似最近邻搜索,避免了两种空间及距离的换算。实验结果表明,提出的检索方法减少了距离换算的信息损失并能有效提高遥感图像特征表达能力,使其在查准率和查全率上有更好的检索效果。 展开更多

关键词 遥感图像检索 卷积神经网络 E2LSH 欧氏距离 近似近邻搜索

下载PDF 职称材料

开放环境多分布特性的局部敏感哈希检索方法 被引量：7

7

作者 张仕 赖会霞 +3 位作者 肖如良 潘淼鑫 张路路 陈伟林 《软件学报》 EI CSCD 北大核心 2022年第4期1200-1217,共18页

基于局部敏感哈希的检索方法能够较好地解决高维大规模数据的近似近邻检索问题.但在开放环境下针对多种分布特性时,迄今尚未有令人满意的解决方案.利用Laplacian算子对数据分布剧烈变化敏感的特性,提出一种具有全局性、适用于开放环境... 基于局部敏感哈希的检索方法能够较好地解决高维大规模数据的近似近邻检索问题.但在开放环境下针对多种分布特性时,迄今尚未有令人满意的解决方案.利用Laplacian算子对数据分布剧烈变化敏感的特性,提出一种具有全局性、适用于开放环境下多种分布特性的基于Laplacian算子的局部敏感哈希搜索方法(LPLSH).该方法把Laplacian算子应用于数据投影的概率密度分布,找到数据投影分布的剧烈变化位置作为超平面的偏移量.从理论上证明了精简维度的哈希函数能够保持局部敏感性及低投影密度区间分割的有效性,分析了利用Laplacian算子计算的二阶导数对超平面偏移量设置的指导意义.与其他8种方法对比,LPLSH算法的F1值是其他方法最优值的0.8倍-5倍,耗费时间也大幅减少.通过对具有多种分布特性数据集上的实验验证,结果表明:LPLSH方法能够同时兼顾效率、精度和召回率,可满足开放环境下多分布特性的大规模高维检索的鲁棒性需求. 展开更多

关键词 开放环境 近似近邻检索 数据多分布特性 局部敏感哈希 数据检索

下载PDF 职称材料

基于离散优化的哈希编码学习方法 被引量：6

8

作者 刘昊淼 王瑞平 +1 位作者 山世光 陈熙霖 《计算机学报》 EI CSCD 北大核心 2019年第5期1149-1160,共12页

哈希作为近似近邻搜索的一种主流方法,通过将样本索引为紧致的二值编码,在计算效率和存储上都非常高效.由于二值码的离散特性,以往的哈希方法往往需要将二值码松弛为实数值才能高效地进行优化,因此在优化完成后重新将实数值的结果量化... 哈希作为近似近邻搜索的一种主流方法,通过将样本索引为紧致的二值编码,在计算效率和存储上都非常高效.由于二值码的离散特性,以往的哈希方法往往需要将二值码松弛为实数值才能高效地进行优化,因此在优化完成后重新将实数值的结果量化为二值时难免会由于二值的汉明空间与实数值的欧氏空间之间的差异而遇到性能上的损失问题.为了更好地解决量化损失的问题,本文提出了一种深度离散优化哈希(Deep Discrete Optimization Hashing,DDOH)方法.首先,设计了一种新的离散优化算法,通过直接在二值的汉明空间中对二值码进行优化,得到具有强判别性的二值编码.然后,训练卷积神经网络模型拟合上述二值码,得到用于编码的哈希函数.在CIFAR-10和ImageNet-100两个常用的评测数据集上的实验显示,本文提出的方法在CIFAR-10数据库上与目前最好的方法达到了同样的性能,在ImageNet-100数据库上的平均准确率指标与已有方法相比提升了约2.2%,证明了该方法的有效性. 展开更多

关键词 近似近邻搜索 高维特征索引 哈希学习 离散优化 卷积神经网络

下载PDF 职称材料

高维空间近邻检索的双层组合量化GPU加速算法 被引量：5

9

作者 邓理睿 包涵 +2 位作者 陈靓 全成斌 赵有健 《小型微型计算机系统》 CSCD 北大核心 2019年第2期390-394,共5页

在大规模视频、图像、文本检索等许多实际应用中,高维空间内海量数据的索引及近邻检索一直是难点和关键问题之一.传统的K-D树等树形索引方法在高维空间中容易陷入"维度灾难",而主流的哈希散列方法(如局部敏感哈希)空间复杂度... 在大规模视频、图像、文本检索等许多实际应用中,高维空间内海量数据的索引及近邻检索一直是难点和关键问题之一.传统的K-D树等树形索引方法在高维空间中容易陷入"维度灾难",而主流的哈希散列方法(如局部敏感哈希)空间复杂度较高,在大规模数据下难以应用.本文总结了近年来基于向量量化的检索算法的相关研究,提出了一种基于GPU优化的高维数据近似近邻检索算法,在组合量化算法的基础上融合双层索引树结构与局部子空间最优化思想,在提高算法准确率的同时针对GPU模型优化算法,极大改善了检索性能,在单张GPU上实现了十亿量级高维数据的高效近似近邻检索. 展开更多

关键词 近似近邻检索 组合量化 GPU 高维索引

下载PDF 职称材料

基于随机森林的哈希检索算法 被引量：5

10

作者 花强 郭欣欣 +1 位作者 张峰 董春茹 《计算机科学与探索》 CSCD 北大核心 2019年第7期1174-1183,共10页

从海量数据中进行近似数据的检索是数据挖掘领域许多应用的关键。尤其近年来,数据的规模出现爆炸式增长,数据检索需面对海量数据和“维度灾难”的叠加考验,这使得传统最近邻算法效率降低,而近似最近邻算法发挥了越来越重要的作用。其中... 从海量数据中进行近似数据的检索是数据挖掘领域许多应用的关键。尤其近年来,数据的规模出现爆炸式增长,数据检索需面对海量数据和“维度灾难”的叠加考验,这使得传统最近邻算法效率降低,而近似最近邻算法发挥了越来越重要的作用。其中哈希算法以其在存储空间和计算时间上的优势受到了广泛关注。提出了一种基于随机森林的哈希算法。该算法通过构建随机森林,将原始空间的样本映射为海明空间的二进制哈希码,并在哈希空间上定义了顺序敏感的海明距离,以最大程度保持数据在原空间的近邻关系不变。由于随机森林中不同决策树所使用的特征空间和学习过程是独立的,可以以增量的方式灵活地确定哈希码的长度。此外基于随机森林的哈希编码算法天然适合并行部署,从而可以大大提高算法速度。最后,在MNIST和CIFAR-10数据集对所提算法进行了实验验证,结果表明了算法的有效性和出色性能。 展开更多

关键词 近似近邻检索(ANNS) 哈希编码 随机森林 顺序敏感的海明距离

下载PDF 职称材料

基于电路板结构信息的近似近邻排序网络集生成算法 被引量：4

11

作者 陈圣俭 姚宗中 牛春平 《电子测量与仪器学报》 CSCD 2006年第2期43-47,共5页

结构测试算法是一类采用有限制故障模型获得紧凑性和完备性指标更为优化的边界扫描测试算法,现有的对该类算法的研究大多是在假定已具备近邻排序网络集的基础上进行的理论研究。本文提出了一种利用被测电路板的结构信息和最短路径算法... 结构测试算法是一类采用有限制故障模型获得紧凑性和完备性指标更为优化的边界扫描测试算法,现有的对该类算法的研究大多是在假定已具备近邻排序网络集的基础上进行的理论研究。本文提出了一种利用被测电路板的结构信息和最短路径算法获得准确的有限制短路故障模型,并基于此模型生成近似近邻网络排序集的算法。该算法获取电路板结构信息的方法简便科学,其数据计算在现有条件下易于实现,并且关键步骤可以编程完成,为结构测试算法从理论探讨进展到工程应用提供了必要条件。 展开更多

关键词 故障模型 有限制短路故障模型 近似近邻网络排序集 结构测试算法

下载PDF 职称材料

深度学习在哈希算法的应用 被引量：2

12

作者 亓海凤 王永 《科技资讯》 2018年第32期139-142,共4页

哈希,一种将任意长度的输入二值化输出的过程,被广泛用于快速查找,如分类、检索和拷贝检测等。近年来受到卷积神经网络强大学习能力的影响,很多学者尝试用深度学习的工具进行哈希的探索,也就是所谓的深度哈希算法。深度学习模型是一种... 哈希,一种将任意长度的输入二值化输出的过程,被广泛用于快速查找,如分类、检索和拷贝检测等。近年来受到卷积神经网络强大学习能力的影响,很多学者尝试用深度学习的工具进行哈希的探索,也就是所谓的深度哈希算法。深度学习模型是一种能够层进学习的机器工具,它可以通过从低级特征中构建高级特征来学习特征的层次结构,从而使特征构建过程自动化。本文对深度哈希算法进行了总结。 展开更多

关键词 深度哈希 近似近邻搜索 哈希性能

下载PDF 职称材料

稠密向量实体检索模型的二值化提速压缩 被引量：1

13

作者 王苑铮 范意兴 +2 位作者 陈薇 张儒清 郭嘉丰 《模式识别与人工智能》 EI CSCD 北大核心 2023年第1期60-69,共10页

在实体检索任务中,为了从大规模实体库中高效筛选与查询相关的候选实体,可使用稠密向量检索模型.然而在现有的稠密向量检索模型中,由于实体向量维度较高,导致实时计算效率较低、存储空间较大.文中通过实验发现这些实体向量存在大量的冗... 在实体检索任务中,为了从大规模实体库中高效筛选与查询相关的候选实体,可使用稠密向量检索模型.然而在现有的稠密向量检索模型中,由于实体向量维度较高,导致实时计算效率较低、存储空间较大.文中通过实验发现这些实体向量存在大量的冗余信息:一方面,绝大多数实体向量分布在互不相同的象限里;另一方面,语义相近的实体所在的象限也更近.因此,文中提出二值化的实体检索方法,用于压缩实体向量,加速相似度计算.具体而言,方法利用符号函数(sign),二值化压缩高维稠密的浮点向量,并通过汉明距离加快检索.从理论上分析文中方法保证检索性能的原因.通过定性、定量的分析实验验证理论的正确性,并给出基于随机升维旋转的二值检索性能改善方法. 展开更多

关键词 实体检索 嵌入式表示 稠密向量检索 近似近邻检索 乘积量化

下载PDF 职称材料

Rav-tree:一种有效支持反向近似近邻查询的索引结构 被引量：2

14

作者 李博涵 郝忠孝 《计算机科学》 CSCD 北大核心 2010年第1期158-162,共5页

空间数据库的索引结构是实现有效数据查询的前提和基础。空间数据反向近似近邻查询是空间查询的一个新方向,它避免了精确查询中过多的距离计算,从而能够在效率与准确性上取得平衡。提出的Rav-tree不同于基于启发式规则的索引结构,首先... 空间数据库的索引结构是实现有效数据查询的前提和基础。空间数据反向近似近邻查询是空间查询的一个新方向,它避免了精确查询中过多的距离计算,从而能够在效率与准确性上取得平衡。提出的Rav-tree不同于基于启发式规则的索引结构,首先利用局部近似,然后根据Voronoi cell区域和估计圆的方法实现近似近邻查询,并利用过滤结果和分域查询得到初步的候选集,最终通过反向近似近邻查询(RANNQuery)算法得到RANN集,并完整地给出基于Rav-tree的ANN查询算法和RANN查询算法。实验结果表明,Rav-tree对RANN等查询具有较好的查询效率和查全率。 展开更多

关键词 索引结构 反向近似近邻 分域查询 区域估计

下载PDF 职称材料

基于特征选择的局部敏感哈希位选择算法 被引量：1

15

作者 周文桦 刘华文 李恩慧 《大数据》 2021年第6期67-77,共11页

作为主流的信息检索方法,局部敏感哈希往往需要生成较长的哈希码才能达到检索要求。然而,长哈希码需要消耗巨大的存储空间且携带大量的冗余哈希位。为了解决此问题,采用特征工程中10种简单高效的选择算法从长局部敏感哈希码中选择信息... 作为主流的信息检索方法,局部敏感哈希往往需要生成较长的哈希码才能达到检索要求。然而,长哈希码需要消耗巨大的存储空间且携带大量的冗余哈希位。为了解决此问题,采用特征工程中10种简单高效的选择算法从长局部敏感哈希码中选择信息量丰富的哈希位,去除冗余、无效的哈希位。这10种选择算法使用不同的方式来刻画每一个哈希位的性能或两个哈希位之间的相关性,如方差、汉明距离等。通过去除长哈希码中性能较差或具有高相关性的哈希位进行哈希位的选择。将选择后的哈希码与原哈希码的性能进行比较。在4个常用数据集上的实验结果表明,去除冗余哈希位后的哈希码与原哈希码的性能几乎相同,且其哈希位的去除比率能达到30%~70%。 展开更多

关键词 近似近邻搜索 哈希学习 哈希位选择 特征选择 降维

下载PDF 职称材料

基于改进局部敏感哈希的协同过滤推荐算法

16

作者 曹界杰 张娟 《软件》 2021年第5期151-156,共6页

传统推荐系统中存在用户评分数据高维稀疏、分布不均匀和传统用户相似度计算准确性低等问题,本文提出一种基于改进局部敏感哈希的协同过滤算法。首先利用改进局部敏感哈希算法对用户评分数据进行降维处理并构建索引,并使用相似度修正系... 传统推荐系统中存在用户评分数据高维稀疏、分布不均匀和传统用户相似度计算准确性低等问题,本文提出一种基于改进局部敏感哈希的协同过滤算法。首先利用改进局部敏感哈希算法对用户评分数据进行降维处理并构建索引,并使用相似度修正系数对用户相似度计算做出改进;然后利用索引敏捷切确地计算目标对象的近邻用户集合;之后选择近邻用户聚集的高相似度用户,使用加权算法对目标对象未评分项目进行评定预估。实验结果表明,对于非均匀用户评分数据的高维稀疏问题,该算法不仅能明显缩短近邻用户检索时间,且能有效提高推荐精度。 展开更多

关键词 推荐系统 协同过滤 局部敏感哈希算法 相似性度量 近似近邻检索

下载PDF 职称材料

基于FAST和SURF的图像配准算法 被引量：22

17

作者 安维胜 余让明 伍玉铃 《计算机工程》 CAS CSCD 北大核心 2015年第10期232-235,239,共5页

尺度不变特征变换(SIFT)和加速鲁棒特征(SURF)方法在进行角点检测和特征点匹配时的时间较长。为此,提出一种改进的图像配准算法。建立参考图像与待配准图像的高斯图像金字塔,在金字塔各层图像进行检测,得到具有不同尺度的加速分割测试特... 尺度不变特征变换(SIFT)和加速鲁棒特征(SURF)方法在进行角点检测和特征点匹配时的时间较长。为此,提出一种改进的图像配准算法。建立参考图像与待配准图像的高斯图像金字塔,在金字塔各层图像进行检测,得到具有不同尺度的加速分割测试特征(FAST)点,采用SURF算法为各特征点分配方向,并计算各特征点的描述向量,使用快速近似最近邻搜索算法获取图像间的初始匹配点对,用随机抽样一致性算法剔除误匹配点对,同时得到2幅图像之间的几何变换矩阵。实验结果表明,与SURF算法和SIFT算法相比,该算法的特征检测速度和匹配速度较快,匹配正确率较高。 展开更多

关键词 图像配准 加速分割测试特征 加速鲁棒特征 近似最近邻 随机抽样一致性

下载PDF 职称材料

基于最优排序的局部敏感哈希索引 被引量：9

18

作者 冯小康 彭延国 +2 位作者 崔江涛 刘英帆 李辉 《计算机学报》 EI CSCD 北大核心 2020年第5期930-947,共18页

针对外存环境中海量高维数据近似最近邻(Approximate Nearest Neighbor,ANN)查询面临的"维度灾难"和I/O性能瓶颈难题,本文提出了一种基于最优排序的局部敏感哈希(Locality-Sensitive Hashing,LSH)索引方案O2LSH(Optimal Order... 针对外存环境中海量高维数据近似最近邻(Approximate Nearest Neighbor,ANN)查询面临的"维度灾难"和I/O性能瓶颈难题,本文提出了一种基于最优排序的局部敏感哈希(Locality-Sensitive Hashing,LSH)索引方案O2LSH(Optimal Order LSH).通过引入空间填充曲线为复合哈希键值建立线序并排序,使近邻候选点更多地分布在相同或相邻磁盘页面,实现用少量顺序I/O加载到足够多的候选点.本文对多种常用空间曲线技术进行了量化分析,发现:(1)基本排序方案SK-LSH使用的row-wise曲线具有"维度优先遍历"的特性,容易对ANN查询造成多种局限;(2)另一类"邻域优先遍历"特性的曲线能够产生更好的候选点局部分布,且排序性能更加稳定.通过对比,我们选取了一种最优的"邻域优先遍历"曲线构造线序,该线序能够最大程度地改善近邻候选点的局部分布,进一步提升磁盘访问效率和查询精度.在多个真实多媒体数据集上进行了对比实验,证实了O2LSH相对于先进LSH方案(包括C2LSH、SK-LSH、SRS以及QALSH)在查询精度和I/O效率上的优越性.特别地,O2LSH克服了基本排序方案SK-LSH对LSH关键参数的敏感性,算法实用性进一步提升. 展开更多

关键词 近似最近邻 高维索引 局部敏感哈希 空间线序 局部分布

下载PDF 职称材料

基于维度分组降维的高维数据近似k近邻查询 被引量：6

19

作者 李松 胡晏铭 +2 位作者 郝晓红 张丽平 郝忠孝 《计算机研究与发展》 EI CSCD 北大核心 2021年第3期609-623,共15页

针对现有的高维空间近似k近邻查询算法在数据降维时不考虑维度间关联关系的问题,首次提出了基于维度间关联规则进行维度分组降维的方法.该方法通过将相关联维度分成一组进行降维来减少数据信息的损失,同时针对Hash降维后产生的数据偏移... 针对现有的高维空间近似k近邻查询算法在数据降维时不考虑维度间关联关系的问题,首次提出了基于维度间关联规则进行维度分组降维的方法.该方法通过将相关联维度分成一组进行降维来减少数据信息的损失,同时针对Hash降维后产生的数据偏移问题,设置了符号位并基于符号位的特性对结果进行精炼;为提高维度间关联规则挖掘的效率,提出了一种新的基于UFP-tree的频繁项集挖掘算法.通过将数据映射成二进制编码来进行查询,有效地提高了近似k近邻查询效率,同时基于信息熵筛选编码函数,提高了编码质量;在查询结果精炼的过程,基于信息熵对候选集数据的编码位进行权重的动态设定,通过比较动态加权汉明距离和符号位碰撞次数返回最终近似k近邻结果.理论和实验研究表明,所提方法能够较好地处理高维空间中近似k近邻查询问题. 展开更多

关键词 近似k近邻 高维数据 关联规则 HASH 熵

下载PDF 职称材料

M2LSH:基于LSH的高维数据近似最近邻查找算法 被引量：5

20

作者 李灿 钱江波 +1 位作者 董一鸿 陈华辉 《电子学报》 EI CAS CSCD 北大核心 2017年第6期1431-1442,共12页

在许多应用中,LSH(Locality Sensitive Hashing)以及各种变体,是解决近似最近邻问题的有效算法之一.虽然这些算法能够很好地处理分布比较均匀的高维数据,但从设计方案来看,都没有针对数据分布不均匀的情况做相应的优化.针对这一问题,本... 在许多应用中,LSH(Locality Sensitive Hashing)以及各种变体,是解决近似最近邻问题的有效算法之一.虽然这些算法能够很好地处理分布比较均匀的高维数据,但从设计方案来看,都没有针对数据分布不均匀的情况做相应的优化.针对这一问题,本文提出了一种新的基于LSH的解决方案(M2LSH,2 Layers Merging LSH),对于数据分布不均匀的情况依然能得到一个比较好的查询效果.首先,将数据存放到具有计数功能的组合哈希向量表示的哈希桶中,然后通过二次哈希将这些桶号投影到一维空间,在此空间根据各个桶中存放的数据个数合并相邻哈希桶,使得新哈希桶中的数据量能够大致均衡.查询时仅访问有限个哈希桶,就能找到较优结果.本文给出了详细的理论分析,并通过实验验证了M2LSH的性能,不仅能减少访问时间,也可提高结果的正确率. 展开更多

关键词 近似最近邻 KNN查询 局部敏感哈希 高维数据

下载PDF 职称材料