图数据库中的相似性搜索算法研究与应用*

图数据库的相似性搜索是一个非常重要的研究内容,图的相似性匹配属于图同构的判定问题,是NP完全问题,传统的高开销搜索的方法已经不能满足复杂图查询的需要;另外,由于图数据库的复杂性和特殊性,已有的优化算法不能直接使用。为了提高图数据库的搜索效率,提出了一种基于索引的相似性搜索算法,通过数据库中的频繁结构建立特征索引,算法可高效准确地滤除大量的非相似图集合,避免了图之间精确匹配即图同构的计算,最后将本算法应用于化学数据库,实验结果证明了该方法的有效性和可行性。     

面向图相似性搜索的高效图编辑距离算法

在图相似性搜索问题中,图编辑距离是较为普遍的度量方法,其计算性能很大程度上决定了图相似性搜索算法的性能。针对传统图编辑距离算法中存在的因大量冗余映射和较大搜索空间导致的性能低下问题,提出了一种改进的图编辑距离算法。该算法首先对图中顶点进行等价划分,以此计算映射编码来判断等价映射;然后定义映射完整性更新等价映射优先级,选出主映射参与扩展;其次,设计高效的启发式函数,提出基于映射编码的下界计算方法,快速得到最优映射。最后,将改进的图编辑距离算法扩展应用于图相似性搜索。在不同数据集上的实验结果表明,该算法具有更好的搜索性能,在搜索空间上最大可降低49%,速度提升了约29%。     

基于SQL的图相似性查询方法

图作为一种表示复杂信息的数据结构,被广泛应用于社交网络,知识图谱,语义网,生物信息学和化学信息学等领域.随着各领域应用的普及和深入开展,如何管理这些复杂图数据是目前图数据库技术面临的巨大挑战.图的相似性查询是图数据管理中的热点问题之一.对图查询问题的研究主要包括图的相似性查询等.本文重点研究基于编辑距离（Graph Edit Distance）的图相似性查询处理问题.首先,通过对目前代表性的问题求解算法分析发现,其提出的过滤规则都具有自己的优缺点和适用性.其次,针对已有方法在过滤阶段自身存在优缺点和适用性的问题,提出一种全新的面向关系型数据库的过滤框架,新的过滤框架可以支持所有已有的过滤规则,从而通过结合不同的过滤规则来优化图相似查询算法以提高查询效率.该方法可以最大程度保留不同过滤规则的优点并克服其缺点,从而对不同查询具有普遍适用性.最后,基于PubChem数据集,通过比较算法在求解查询结果的时间消耗,验证本文提出算法的高效性及可扩展性,实验结果表明,本文提出的方法优于现有算法.     

基于节点相似性分组与图压缩的图摘要算法

方法压缩率较高,图压缩算法无法直接被用于下游任务分析的问题,提出一种图摘要与图压缩的融合算法,即基于节点相似性分组与图压缩的图摘要算法（GSNSC）。首先,初始化节点为超节点,并根据相似度对超节点分组;其次,将每个组的超节点合并,直到达到指定次数或指定节点数;再次,在超节点之间添加超边和校正边以恢复原始图;最后,对于图压缩部分,判断对每个超节点的邻接边压缩和摘要的代价,并选择二者中代价较小的执行。在Web-NotreDame、Web-Google和Web-Berkstan等6个数据集上进行了图压缩率和图查询实验。实验结果表明,在6个数据集上,与SLUGGER(Scalable Lossless sUmmarization of Graphs with HiERarchy)算法相比,所提算法的压缩率至少降低了23个百分点;与SWeG(Summarization of Web-scale Graphs)算法相比,所提算法的压缩率至少降低了13个百分点;在Web-NotreDame数据集上,所提算法的度误差比SWeG降低了41.6%。以上验证了所提算法具有更好的图压缩率和图查询准确度。     

基于LSH的相似性搜索算法研究探讨

相似性搜索(近邻搜索)是从一个大数据集合中找出与查询对象距离最近的数据对象集合,局部敏感哈希(LSH)及其变种是解决这个问题著名且有效的算法,本文对相关研究成果进行了广泛的调查研究。     

基于键值存储的分布式时序相似性搜索方法

时序相似性搜索是时序数据分析最基本的操作之一,具有广泛的应用场景.针对现有分布式算法无法应对维度增长、扫描范围过大和相似性计算耗时的问题,提出一种面向键值存储的分布式时序相似性搜索方法KV-Search.首先对时序数据分块,并设计其键值存入键值数据库,解决了时序数据维度高且不断增长的问题;其次,基于切比雪夫距离计算其下...     

比特串划分多索引的近邻搜索算法

哈希表示的比特串是解决海量数据相似性搜索问题最有效的方法之一.针对比特串索引方式导致搜索效果低下的问题,提出一种基于比特串划分多索引的近邻搜索算法.首先由于比特串划分本质是一个组合优化问题,采用贪婪的思想给出该问题的近似解;其次在近邻查询阶段,结合多索引结构提出新的查询扩展和融合机制;最后通过采用一种查询自适应的办法优化多索引之间的不平衡性.在MNIST, CIFAR-10, SIFT-1M和GIST-1M数据集上使用Matlab软件进行实验的结果表明,该算法在基于哈希表示的索引结构以及在近邻搜索方面具有有效性和通用性.     

一种基于文档拓扑的相似性搜索算法

从海量文档中快速有效地搜索到相似文档是一个重要且耗时的问题。现有的文档相似性搜索算法是先找出候选文档集,再对候选文档进行相关性排序,找出最相关的文档。提出了一种基于文档拓扑的相似性搜索算法——Hub-N,将文档相似性搜索问题转化为图搜索问题,应用相应的剪枝技术,缩小了扫描文档的范围,提高了搜索效率。通过实验验证了算法的有效性和可行性。     

基于广义超曲面树的相似性搜索算法

相似性搜索是数据挖掘的主要领域之一.它在数据库中检索出相似的数据,发现数据间的相似性.它可以应用于图像数据库、空间数据库和时间序列分析.对于欧氏空间(一种特殊的度量空间),相似性搜索算法中基于R-tree的方法,在低维时是高效的,当维数增加时,R-tre e的方法将退化为线性扫描.该现象被称为维数灾难(dimensionality curse),主要原因是存在数据重复.当数据量很大且维数很高时,距离计算和I/O操作将非常费时.提出了度量空间上新的空间分割方法和索引结构rgh-tree,利用数据库的数据对象与很少几个固定参考对象的距离信息进行数据分割和分布,产生一个各节点没有数据重复的平衡树.另外,在rgh-tree的基础上提出了相应的相似性搜索算法,该算法具有较小的I/O代价和距离计算次数,平均复杂性近似为o(n^0.58).解决了目前算法存在的一些问题.     

一种基于PageRank的文献相似性搜索算法

在分析了PageRank算法基础上,提出了PageRank应用于科技文献相似性搜索的可行性,针对PageRank的不足提出了一种改进算法,该算法结合了对文献内容和文献间的引用关系的分析,综合计算文献间相似度,提高了搜索结果的准确率,并通过实验验证了算法的有效性和可行性。     

基于形态特征的时间序列相似性搜索算法

时间序列相似性搜索是数据挖掘的一个重要基础性研究内容,它的相似性定义主要是基于欧氏距离,这类算法的缺点:如果时间序列产生偏移,会产生错误的结果.基于形态特征的时间序列相似性快速搜索算法,以界标为分界点,利用界标提取了时间序列的特征,将时序分为若干子序列,并对每个子序列进行线性化,将线性化后的子序列进行预处理;同样将查询序列进行基于界标的分段算法,然后利用一种改进的快速相似性搜索算法,可以快速地搜索到与查询序列相似的序列.?＃ 箅例表明了算法的有效性.     

基于特征索引的图相似查询过滤算法

分析图相似查询候选集的产生过程以及特征图之间的关系对候选图集的影响,提出一种基于特征索引的图相似查询过滤算法,使用GIndex算法建立特征图索引结构,通过特征图之间的选择性关系给出一个有序的特征集,并借助特征-图矩阵对数据库进行筛选得到候选图集。实验结果证明,该方法能准确地产生候选图集,从而提高图查询的效率。     

一种不确定图数据库上的相似性连接方法

在确定图上进行的相似性连接已有许多研究成果.然而,在实际应用中会有许多因素使得图结构数据变得不确定.研究了不确定图数据库上的相似性连接问题.采用联合概率分布表示法来描述图中边的不确定性,结合一种新的图的相似性度量方法,给出了不确定图数据库上的相似性连接的形式化定义,并设计了一组过滤策略来减少连接过程中候选图对的数量.大量的实验数据表明,所提出的方法具有较好的可行性和准确性.     

基于三角不等式的时间序列相似性搜索算法

由于传统的时序相似性度量方式不满足距离三角不等式关系,影响后续的相似性搜索及关联规则的获取,在时序符号化的基础上,提出一种满足三角不等式的符号化距离度量方式。与MINDIST_PAA_SAX和Sym_PAA_SAX度量方式进行比较,其结果表明,该度量方式在异常检测和相似性查询上具有较好的优越性。实验结果表明,该方法在相似性搜索及关联规则的获取方面具有更高的可信度。     

基于相似性叙词表的模糊集合模型

传统的模糊集合模型基于词词关联矩阵来实现模糊检索,词词关联矩阵只考虑语词在文献内部的同时出现.本文提出了一个基于相似性叙词表的模糊集合模型,考虑语词与查询之间的相似性,并将查询扩展包含在此模型中,从而在一定程度上提高了检索性能.     

基于索引的并行图可达性查询算法

随着图数据库(Graph Database)的不断发展,各种应用程序中都存在着大规模图数据,使得图的可达性查询算法受到了广泛的关注.然而由于其空间消耗与查询效率难以平衡,图可达性查询算法面临着严峻的挑战.基于串行运算的传统图查询算法,很难发挥现有多核心处理器的计算性能.针对上述问题,提出了一种基于双链表的索引,称为2-lists.该索引表由两部分组成,其中一部分存储图数据的信息,另一部分辅助索引,实现顶点的随机访问.基于该索引,提出了一种并行化深度优先搜索算法(Parallel Depth-First Search, PDFS).该算法利用多线程技术,并为每个线程分配独立的存储空间.通过对线程工作量的监督,为线程的指定缓冲区分配指定数量的任务,进而完成负载平衡.在斯坦福SNAP(Stanford Network Analysis Platform, SNAP)实验室的公开数据集上的实验结果表明,2-lists索引占用的空间更小,基于2-lists的并行化深度优先搜索算法的表现更好.     

外存中高效的字符串相似性查询处理

字符串相似性查询是众多应用的基础操作,如数据清洁、拼写校验、生物信息学和信息集成等.随着数据的爆炸性增长,大规模字符串数据日益普遍,现代的信息系统中也广泛使用字符串作为数据的表达形式.现有支持字符串相似性查询的方法大多是基于q-gram的内存倒排索引,在处理大规模字符串集合会消耗无法忍受的内存容量,甚至在数据量过大时造成内存容量不足而无法支持查询处理.现有的外存倒排索引Behm-Index在查询的过滤阶段只支持少数过滤器,不能有效地减少查询I/O代价.提出了LPA-Index：一种支持长度过滤器和位置过滤器的外存倒排索引,并通过选择查询时使用的倒排表来有效地降低查询I/O代价.实验结果表明,与现有性能最好的外存索引Behm-Index相比,LPA-Index能够大幅降低查询的I/O代价,获得了更短的查询响应时间.     

低冗余计算的可达性查询保持图压缩策略

针对可达性查询保持图压缩（QPGC）算法存在冗余计算的问题,提出了一种高性能压缩策略。在求解顶点的祖先后代集阶段,针对普通图数据,提出一种基于拓扑排序的求解算法TSB,首先将图数据顶点拓扑排序,然后沿拓扑序列顺序（逆序）求解顶点的祖先（后代）集,避免了求解顺序不明确导致的冗余计算;针对最长路径较短的图数据,提出一种基于图聚合运算的求解算法AGGB,可在确定次数的聚合运算内完成顶点的祖先和后代集的求解。在求解可达性等价类阶段,提出一种分段统计剪枝算法PSP,先对祖先后代集分段统计,再比较统计值以实现粗匹配,剪除了部分不必要的精细匹配。实验结果表明,与QPGC算法相比：在祖先后代集求解阶段,TSB和AGGB在不同数据集上的性能平均提升94.22%和90.00%;在求解可达性等价类阶段,PSP算法在大部分数据集上性能提升超过70%;随着数据集的增大,TSB和AGGB配合PSP算法,性能提升了近28倍。理论分析和模拟实验表明,该策略与QPGC算法相比冗余计算更少、压缩速度更快。     

对等网络中基于节点相似性的改进破圈搜索算法

对等网络中资源搜索算法的研究是近十几年的一个研究热点.当前无结构对等网中的搜索算法很多是基于泛洪算法的改进,这些算法在网络中查全率和查准率都比较高,但由于在搜索过程中产生大量的冗余信息导致对等网的扩展性很差,不能满足大范围组网的要求.本文提出一种对等网中基于稳定性和相似性的改进破圈路由搜索算法,在此算法中,如果节点在路由中发现与另外几个节点形成一个圈,则节点根据与圈中邻居节点之间的稳定性和内容相似性等因素选择其中的一个邻居节点转发信息.在这种破圈法构造的拓扑结构中采用泛洪协议去搜索资源,转发信息数将从指数级增长有效地减少到常数值,并且资源搜索成功率始终在一个稳定的范围.仿真实验表明所提算法在保证一定搜索成功率的前提下大大减少了搜索中产生的冗余信息.     

超平面树:度量空间中相似性搜索的索引结构

相似性搜索是从数据库中检索出同给定数据对象相似的数据对象，已有的基于R-tree的相似性搜索，当搜索空间的维的个数较小时效率较高，但当搜索空间的维的个数较大时则效率很低．针对此问题，提出了新的度量空间分割方法和索引结构pgh-tree，利用数据对象与很少几个固定参考对象的距离之差进行数据分割和索引，产生一个平衡的索引树．在此基础上，提出了新的算法，利用查询数据对象与固定参考对象的距离之差过滤掉大部分的不相关数据，具有较小的I／O代价和距离计算复杂性，平均复杂性为θ(n^0.58)，是目前复杂性最小的相似性搜索算法．另外还讨论了基于pgh-tree的最近相邻点搜索策略．