基于LSH的中文文本快速检索

目前,高维数据的快速检索问题已经受到越来越多的关注.当向量空间的维度高于10时,R-tree,Kd-tree,SR-tree的检索效率反而不如线性检索,而位置敏感的哈希(Locality Sensitive Hashing,缩写为LSH)算法成功地解决了高维近邻数据的快速检索问题,因而受到国内外学术界的高度关注.首先介绍了LSH算法的基本原理和方法,然后使用多重探测的方法对二进制向量的LSH算法做了进一步改进.最后实现了这两种LSH算法,并通过详细的实验验证表明:在改进后的算法中,通过增加偏移量可以提高检索的召回率,而在不提高时间复杂度的情况下则可降低空间复杂度.     

低空间复杂度的LSH算法及其在图像检索中的应用

局部敏感哈希LSH算法是有效的高维数据索引方法,如何生成哈希函数是算法的关键部分。LSH算法的哈希函数是基于p-稳态分布随机生成的,为了提高算法性能就需要增加哈希表的数量,但这会增加算法的空间复杂度。改进后的LSH算法(I-LSH)在生成哈希函数时不需要有标记的训练样本,而是仅仅利用数据点的分布信息构造投影方向。实验结果表明,在不显著降低检索性能的情况下,ILSH有效地降低了内存的使用量,适合处理大规模数据。     

版权数据库管理中基于内容的版权检索方法

局部敏感哈希LSH(Locality Sensitive Hashing)是一种常见的用于处理高维向量的索引办法。首先介绍LSH算法的基本原理和方法,然后通过更快哈希函数的计算和跳过重复点等方法对LSH算法进行改进,与传统的索引方法相比,改进后算法在不降低准确度的情况下,耗费时间更短。实验结果证明,将该优化算法应用于基于内容数字版权检索中,其性能优于传统的索引方法。     

面向高维图像特征匹配的多次随机子向量量化哈希算法

为了解决高维图像特征的高效匹配问题,提出一种新的基于多次随机子向量量化哈希(MRSVQH)的索引算法.该算法根据随机选择的若干子向量的L2范数对特征向量进行量化,并根据量化值对特征向量进行散列,构建出哈希索引结构;为了提高搜索精度,类似的哈希索引结构被多次构建.搜索时仅考察与查询向量有相同哈希值的特征向量集合,缩减了搜索范围.实验数据表明,与经典的BBF和LSH算法相比,MRSVQH算法在图像特征的最近邻搜索精度和搜索速度方面都有较大的性能提升,在图像匹配和图像检索的应用中具有优势.     

面向视觉搜索的空间局部敏感哈希方法

目的 视觉检索需要准确、高效地从大型图像或者视频数据集中检索出最相关的视觉内容,但是由于数据集中图像数据量大、特征维度高的特点,现有方法很难同时保证快速的检索速度和较好的检索效果。方法 对于面向图像视频数据的高维数据视觉检索任务,提出加权语义局部敏感哈希算法（weighted semantic locality-sensitive hashing, WSLSH）。该算法利用两层视觉词典对参考特征空间进行二次空间划分,在每个子空间里使用加权语义局部敏感哈希对特征进行精确索引。其次,设计动态变长哈希码,在保证检索性能的基础上减少哈希表数量。此外,针对局部敏感哈希（locality sensitive hashing, LSH）的随机不稳定性,在LSH函数中加入反映参考特征空间语义的统计性数据,设计了一个简单投影语义哈希函数以确保算法检索性能的稳定性。结果 在Holidays、Oxford5k和DataSetB数据集上的实验表明,WSLSH在DataSetB上取得最短平均检索时间0.034 25 s;在编码长度为64位的情况下,WSLSH算法在3个数据集上的平均精确度均值（mean average precision,mAP）分别提高了1.2%32.6%、1.7%19.1%和2.6%28.6%,与几种较新的无监督哈希方法相比有一定的优势。结论 通过进行二次空间划分、对参考特征的哈希索引次数进行加权、动态使用变长哈希码以及提出简单投影语义哈希函数来对LSH算法进行改进。由此提出的加权语义局部敏感哈希（WSLSH）算法相比现有工作有更快的检索速度,同时,在长编码的情况下,取得了更为优异的性能。     

基于多媒体图像数据的查询检索

本文对多媒体图像数据提出一套较灵活的存储、索引查询方式。针对多媒体数据库信息查询通用性的问题，构建了一个较为集成的特征库。针对高维数据查询效率问题，将基于内容、颜色、距离和形状的匹配算法与FNN算法及查找聚类重心的加速检索算法集成于查询检索引擎IRE，使查询更高效、应用更广泛。     

一种基于密度峰值的高效分布式聚类算法

基于密度峰值的聚类算法（DPC）是最近提出的一种高效密度聚类算法。该算法可以对非球形分布的数据聚类,有待调节参数少、聚类速度快等优点,但在计算每个数据对象的密度值和高密度最邻近距离时,需要进行距离度量,其时间复杂度为 。在大数据时代,尤其是处理海量高维数据时,该算法的效率会受到很大的影响。为了提高该算法的效率和扩展性,利用 Spark 在内存计算以及迭代计算上的优势,提出一种高效的基于E2LSH分区的聚类算法ELSDPC（an efficient distributed density peak clustering algorithm based on E2LSH partition with spark）。算法利用DPC算法的局部特性,引入局部敏感哈希算法LSH实现将邻近点集划分到一个区域。通过实验分析表明：该算法可在满足较高准确率的同时有效提高聚类算法的扩展性和时间效率。     

基于内容的SIFT+LSH管道缺陷检索算法研究

各个城市对地下管道安全的检测一直是研究的热点和难点。传统的检测仪器不仅费时费力而且误检率特别高,随着技术的发展计算机视觉相关的方法也有在管道检测中应用,但是检测的速度和效果不尽人意。针对当前传统的检测方法操作复杂,成本高的问题,提出了一种基于内容的SIFT+LSH管道缺陷图像检索方法。该方法首先选取了优势较为明显的局部特征SIFT,充分利用了管道缺陷图像的特征,同时选取LSH算法对图像SIFT特征进行优化,将其转化为Hash编码,提高了检索速度。实验结果表明,基于SIFT特征和LSH算法的管道缺陷检索方法,相比与传统的SIFT特征和欧式距离的检索方法,大大提高了检索的速度,使得检测人员在实际操作中能够更快地获取到比较满意的检索结果。     

基于四元数描述和EMD的人体运动捕获数据检索

针对运动捕获数据的高效匹配问题,提出了一种新的基于四元数描述和EMD（ Earth Mover＆#39;s Distance）的人体运动检索算法。该算法主要包括特征提取和运动匹配两部分。在特征提取部分,为了解决高维数据检索效率低的问题,引入了四元数描述符对关节点的数据信息特征进行描述,通过映射姿态分布的原始数据,并采取K-means聚类方法对待查询动作和运动数据库的特征数据进行降维并归类。在运动匹配部分,根据聚类结果,建立每个特征数据集的距离矩阵,将匹配问题转换为运输优化问题。然后,用EMD算法度量待查询动作和数据库动作之间的相似值。仿真实验结果证明了提出的算法是有效的。     

基于FP-Tree的QAR数据故障检测研究

QAR(Quick Access Recorder)数据具有高维、复杂及数据量大的特性,严重影响数据处理效率。为降低其数据量与数据复杂性,高效检索并确定当前QAR数据是否是故障数据及其故障类型,首先通过PAA表示方法对QAR数据初步压缩,然后采用FP-Growth算法思想对压缩后的数据创建FP-Tree并只保留其频繁前缀子树,最后通过子树匹配确定测试数据与故障模型数据之间的匹配度。采用真实的飞机飞行QAR数据验证了算法的有效性和准确度。     

基于可扩展LSH的高维动态数据索引

提出了一种可扩展的局部敏感哈希索引(SLSH),以解决高维动态数据索引中,由于数据集大小及分布特征无法确定而导致索引效率降低的问题.SLSH架构于E2LSH之上,继承了其对高维数据索引速度快,并可直接对欧式空间上的数据点进行索引的特点.为了使得哈希索引具有动态的相似性区分能力,SLSH修改了E2LSH的哈希族,通过哈希桶容量约束自适应调节哈希参数.因此对于分布密度动态变化的数据空间,SLSH也能够给出鲁棒的划分.     

改进的二进制特征图像检索算法

提出一种针对嵌入式系统的图像检索算法,通过提取目标局部特征来进行图像检索。为了提高检索的实时性并兼顾正确率,选用经典SIFT特征为基础进行改进。在关键点检测阶段使用均值滤波代替高斯滤波大大提高特征提取速度。在描述符生成阶段通过稀疏矩阵将SIFT特征映射为二进制描述符。引入基于K-means的 Multi-probe LSH方法对二进制描述符进行快速检索和匹配。通过一系列的图像缩放、旋转、模糊和光照变化对比实验,可以看出该算法与现有的经典算法相比在检索正确率及实时性方面均有很好的表现。     

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

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

基于Hadamard变换的高维图像检索方法

传统索引方法对高维数据进行近邻搜索时会面临维数灾难问题,向量近似方法是一种有效的高维检索方法。提出一种 Hadamard 变换域上的向量近似方法,在变换域能量最大的分量上建立顺序索引,然后建立近似向量文件。同时提出低維过滤算法,可以在近邻搜索过程中高效排除不匹配近似向量,减少 I/O 访问时间,提高查询效率。在大型高维图像特征库上的实验表明,该方法性能优于小波变换域的向量近似方法。     

基于双向参考索引的大规模人体运动数据库的检索

因为运动特征数据的高维复杂性,采用非线性的Isomap流形学习的降维算法来对运动特征数据进行降维,为了能让Isomap方法处理训练数据集之外的数据,通过学习主成分特征核函数逼近降维结果,以扩展传统Isomap的局限性.在运动数据降维之后,为大规模运动捕获数据库建立一种双向参考索引(DRI),在检索过程中索引用来排除绝大部分与查询例子无关的运动数据,这样运动检索中的相似度的计算通过索引被缩小到一个小范围候选数据集合中,避免了大量不必要的匹配开销,从而提高了检索的效率.     

逐维聚类的相似度索引算法

随着多媒体信息技术的迅速发展，多维度索引技术在图像、视频等可视信息的存储、检索方面成为一个重要的研究领域，针对“维数危机”难题，提出逐维聚类相似度索引算法，该算法根据数据集的分布特性，对特征矢量的每一维进行聚类，算法在实现检索时可以逐步滤除与查询矢量不相似的数据集，缩小检索范围，进而提高了检索速度，实验结果表明，逐维聚类算法适用于基于相似度的高维数据矢量检索和查询，是一种简单、灵活的索引结构。     

基于LSH索引的快速图像检索

高维空间中点数据的索引及检索是基于内容图像检索领域的关键问题,文中将LSH(localitysensitivehashing)索引算法应用于基于内容图像检索系统中,与传统的索引方法相比,该算法具有复杂度比较低、支持非常高的维数、极低的I/O代价等特点。实验结果证明,将该索引算法应用于基于内容图像检索系统中,其性能优于传统的索引方法.     

基于MapReduce与相关子空间的局部离群数据挖掘算法

针对高维海量数据,在MapReduce编程模型下,提出了一种基于相关子空间的局部离群数据挖掘算法.该算法首先利用属性维上的局部稀疏程度,重新定义了相关子空间,从而能够有效地刻画各种局部数据集上的分布特征;其次,利用局部数据集的概率密度,给出了相关子空间中的局部离群因子计算公式,有效地体现了相关子空间中数据对象不服从局部数据集分布特征的程度,并选取离群程度最大的N个数据对象定义为局部离群数据;在此基础上,采用LSH分布式策略,提出了一种MapReduce编程模型下的局部离群数据挖掘算法;最后,采用人工数据集和恒星光谱数据集,实验验证了该算法的有效性、可扩展性和可伸缩性.     

基于小世界模型的高维数据查询算法

提出了一种从海量高维数据中进行高效查询的算法,该算法基于小世界网络模型,并采用网络节点表示高维数据的特征向量。算法主要包含两个部分,基于K-Means的索引生成算法和随机逼近查询算法,两个算法均给出了具体的操作步骤。算法经大量实验仿真,得出通过合理设置小世界网络节点的近邻节点数量以及最大查询路径和最大迭代次数等参数,算法可以满足不同精度的用户查询请求。实验结果表明,实现的算法在高维度海量数据查询中具有良好的检索效果。     

量化编码的分层可通航小世界图算法

随着大数据和人工智能的高速发展,针对多媒体数据的结构化处理与基于内容的检索受到极大的关注,面对多媒体数据结构化后的海量高维特征向量,如何快速、准确地检索是人工智能处理大规模数据所必须解决的问题。最近提出的分层可通航小世界图HNSW检索算法在多个公开数据集取得了最佳的性能表现,但该算法存在内存开销大的问题。而基于量化编码的检索算法能够压缩数据集向量,大幅度降低内存占用。将量化编码和分层可通航小世界图算法结合,提出了2种基于量化编码改进的HNSW算法,分别是使用标量量化编码向量的HNSWSQ算法和使用乘积量化编码向量的HNSWPQ算法,2种算法使用不同的量化策略存储原始向量编码,以降低内存开销,再通过HNSW算法建立索引达到缩短检索耗时的目的。其中HNSWSQ算法在多个数据集上获得了与HNSW算法相近的查全率和平均检索耗时,而内存开销大幅降低。实验结果表明,HNSWSQ算法在SIFT-1M和GIST-1M数据集上的内存开销比HNSW算法分别降低了45.1%和70.4%。