面向子图同构的高效索引构建算法

针对子图同构中索引构建方法效率低、内存占用大而影响查询效率的问题,本文提出基于2次排序查找等价顶点的数据图索引构建算法。该算法采用不同邻接链表表示类别不同的语法等价顶点的邻居集合,并依此设计2次排序的方法快速查找数据图中两两互连和两两互不相连的等价顶点,然后依据语法等价和语法包含关系为数据图构建索引来提高子图同构查询的效率。最后,基于不同规模的数据集,通过实验验证了本文提出索引构建算法的高效性和可扩展性。     

基于云计算数据查询的安全索引构建方法

为了加强云计算数据查询的安全性,防止用户数据查询过程中过度访问和检索过程的数据泄露,提出一种云计算服务端的数据安全索引构建方法.对图状部署的云计算数据采用相似子图和哈希函数进行构造,通过特征子结构将被查询对象与索引图状数据进行对比,找出被查询对象.该方法可防止非查询对象的图状数据泄露,同时将哈希函数对节点进行了散列,提高了节点安全性.仿真结果表明,该方法数据查询效率高,耗费存储资源少,安全性好.     

R-树和四叉树的空间索引结构:RQOP_树

针对现有的基于R-树和四叉树的空间索引结构中存在的问题,通过建立数据矩形间的序关系对数据空间进行分割,提出了一种新的空间数据索引结构:RQOP树.在此结构中,节点的构造是按照空间数据的分布来进行的而不是像其它基于R-树和四叉树的空间索引结构只是对数据空间进行均匀划分而得到,使树的高度尽可能低,同时使兄弟节点间的交叠相对较小.在区域查询算法中引入了查询窗口包含节点MBR的判断加快了查询的速度.给出了RQOP树的生成、节点插入和区域查询算法,并给出了相应算法的可行性和正确性定理及时间复杂度分析.实验表明:新索引结构的查询速度明显加快.     

一种基于数据图划分的关系数据库关键词检索方法

不同于常用的一次性将图加载入内存的检索方法,提出了一种基于数据图划分的关系数据库关键词检索方法,该方法首先将大图细分成多个相互之间具有简单连通性的小图并存储于缓存中,然后通过超图查询算法获取与查询条件相关的子图,进行关键词检索获取候选结果时,只需加载相关子图并恢复子图的初始结构,通过遍历子图获得最终结果.实验表明,该方法可以有效解决对无法放入内存的大型数据图的处理问题,使得关系数据库关键词检索实用于庞大而复杂的数据图中而不受内存约束.     

基于序的空间数据索引结构—MB-树

为了提高查询效率,提出了一种空间数据索引结构-MB-树,给出了全新的区域查询处理方法.给出了空间对象按其MBR进行排序的定义,并以此为基础给出了MB-树的定义,规定MB-树中的中间节点的所有孩子节点按其几何位置满足某种序的关系,使得在中间节点中查询时可以进行快速定位.在查询算法中引入查询窗口包含中间节点MBR的检测,对较大的查询窗口查询,有效地减少了相交性判断.给出了MB-树的生成算法、节点插入算法及算法的正确性、可终止性证明及时间复杂度,并给出区域查询算法及算法的性能分析.实验表明:给出的索引结构区域查询的速度得到有效的提高.     

支持近似最短距离查询的高效图加密机制

近似最短距离查询是图检索的基本模式.为了保护外包数据安全,通常对图数据进行加密.已有加密方案使用两跳覆盖模型构建加密图索引,导致索引结构复杂,降低了查询效率.本文提出了一种基于图压缩的加密机制,可以提高图的检索效率,并且支持加密图最短路径查询.该机制使用K-mediods聚类使得图中的节点按照距离分成K个簇,每个簇内的节点使用其中心节点代理,当查询2个点间最短距离时,对于相同簇内的点直接查询,对于簇间的点使用代理节点查询距离.实验结果表明该机制有效地减少了查询时间,提高了查询效率,且查询结果误差度在可接受范围内.     

概率可视最近邻查询算法

针对不确定对象的可视最近邻查询问题,对不确定Voronoi图的性质进行分析,提出多层邻接生成点和多层不确定Voronoi区域等概念,给出判断概率可视最近邻的理论方法,并提出基于不确定Voronoi图的概率可视最近邻查询算法,该算法通过直接确定参与查询的概率可视最近邻的范围以及参与可视性判断的障碍集的范围,避免了索引遍历时大量的比较计算和剪枝操作,采用真实数据集和模拟数据集对提出的算法进行了性能分析,实验结果表明,提出的算法能够有效地处理不确定对象的可视最近邻查询．     

基于子图交互关系的网络结构增强算法

已有研究基于子图交互关系构造子图网络来实现网络结构增强,然而其算法复杂度高.鉴于此,基于不同阶子图网络的拓扑属性分别对原始网络进行赋权,得到一阶和二阶加权网络,以权重的形式直观体现子图交互关系.同时,这两种加权网络的权重可以直接通过原始网络的拓扑结构计算得出,从而避免了子图网络的构造过程,大大降低了算法复杂度.最后,以...     

一种基于双重距离尺度的高维索引结构

为了提高高维数据相似查询的效率,提出一种基于双重距离尺度(DDM)的新型高维索引结构.通过建模得到该DDM的四元组数据结构, 对于高维空间中的数据点,通过k平均聚类算法将数据点聚成若干类，分别计算每个点对应的始点和质心距离,得到基于加权的质心距离, 并将加权的质心距离作为每个数据点的索引键值，且用基于分片的B+树建立索引，得到了该索引的创建算法.高维空间的查询就转变成对一维空间的检索，并研究了数据点的维数、数据量和查询请求参数对查询性能的影响.结果表明, 该DDM能更有效地缩小搜索空间，减少距离计算的开销,特别适合海量高维数据的查询.     

基于图模型决策的微博检索二次排序算法

为了解决微博检索面临的"用户查询"和"相关文档"都是极端短文本的情况,及由此造成的检索性能欠佳的难题,研究并实现了一种微博检索结果的二次重排算法,基于微博内容相似关系构建关系图模型,利用PageRank算法对微博检索结果进行二次排序.比较了基于余弦相似度、戴斯系数、单向戴斯系数等文本内容相似度计算方法.实验结果表明:二次排序算法能够有效提升微博检索性能,同时图模型迭代性能与相关主题比例存在依存关系.有鉴于此,讨论通过决策树重排算法去除非相关主题对微博排序的影响.     

关于可行图的几个新结论

设有n个集合X1,X2 ,… ,Xn,一个以X =∪ni=1Xi 为顶点集的图G称为是一个关于集合序列 (X1,X2 ,… ,Xn)的可行图 ,如果对每一个Xi(i=1 ,2 ,… ,n) ,导出子图Gi=G[Xi]是连通的。集合序列 (X1,X2 ,… ,Xn)含最少边数的可行图称为关于 (X1,X2 ,… ,Xn)的最小可行图。将n =3推广至任意的自然数n ,得出了集合序列 (X1,X2 ,… ,Xn)的最小可行图G =∪ni=1Gi,当满足∩ni=1Xi≠Φ时 ,G是关于集合序列 (X1,X2 ,… ,Xn)的最小可行图的一个充分必要条件 ,同时得出了集合序列 (X1,X2 ,… ,Xn)的最小可行图在某种条件下的两个主要结果。     

基于拓扑子图与编辑距离的距离测量方法

图结构数据搜索的核心是为图的匹配寻找一个好的相似性测量方法.图编辑距离法和最大公共子图法是现有的两种较成熟的测量方法.图编辑距离法善于描述细小的距离差距,但缺乏结构上的描述;最大公共子图法与之相反,在结构描述上很有优势,但是在细节的描述上很弱.鉴于这种情况,将最大拓扑公共子图法与编辑距离测量法相结合,提出了一种新的相似性测量方法.这种方法先用拓扑公共子图进行结构性描述,然后利用编辑距离的细节描述能力对最大拓扑公共子图内部的相似性距离进行调整,从而有效地发挥了最大公共子图法和编辑距离法各自的优点,使得图之间的相似性衡量更加有效、精确;同时在图的相似性搜索、图像检索、对象识别等领域也更有相容力和理解力.     

树网络上的连通p-median问题

给定一个连通图G=(V,E),每一个顶点和边都赋予一个非负的权重,传统的p-median问题是要找出V的一个包含p个点的子集H,使得其余各点到H的赋权距离和最小。如果要求由H导出的子图是连通的,则称之为连通p-median问题。该文研究树网络上的连通p-median问题,给出了一个O(pn)的算法,随后把该算法推广到带有禁选点的树网络上。     

On the graph traversal method for evaluating linear binary-chain programs

Grahne et al. have presented a graph algorithm for evaluating a subset of recursive queries. This method consists of two phases. In the first phase, the method transforms a linear binary-chain program into a set of equations over expressions containing predicate symbols. In the second phase, a graph is constructed from the equations and the answers are produced by traversing the relevant paths. A new algorithm is described which requires less time than Grahne' s. The key idea of the improvement is to reduce the search space that will be traversed when a query is invoked. Further, the evaluation of cyclic data is speeded up by generating most answers directly in terms of the answers already found and the associated "path information" instead of traversing the corresponding paths as usual. In this way, this algorithm achieves a linear time complexity for both acyclic and most of cyclic data.     

一种基于XQuery的查询分解算法

针对查询分解算法查询的局限性和较低的查全率,提出了一种基于本体XQuery语言FWR表达式的查询分解算法．该算法利用XQuery全局查询语句,以FWR表达式的3项操作（构造查询范围、子查询条件和子查询输出属性集）将基于全局本体的查询分解到针对局部本体的子查询,能够降低查询分解的复杂性、保证查询的语义完整性,并能提高查全率．通过实例进行具体分析,验证了算法的有效性．     

基于关联图关键边发现的人脸图像聚类算法

针对真实场景中大量类别数未知、样本数量不均衡、数据分布复杂等导致人脸图像智能提取准确率低的问题,提出了基于关联图关键边发现的人脸图像聚类算法。首先,通过融合多个卷积神经网络提取的图像样本特征,获得鉴别性更强的特征向量,并计算不同样本之间的相似度;然后,利用拒真率和认假率设置合适的门限值,将得到的相似度结果与门限值进行比较,筛选出相似程度高的样本对,并添加样本对之间的连接边来构建关联图;再利用介数中心性测度,设计关键边发现方法,挖掘关联图中可能连接不同簇的重要连接边;最后,采用图卷积网络确认是否存在上述重要连接边以获得最终的聚类簇。实验结果表明,所提算法能够提高人脸图像聚类的准确率。     

从GCC的AST文本提取C源程序静态信息的方法

为了能够正确的分析源程序的控制依赖关系和数据依赖关系,以便在此基础上进行程序切片及冗余代码和重复代码检测,提出一种利用GCC抽象语法树(AST)文本来提取源程序静态信息的方法.首先,对GCCAST文本进行标准化及消除文本中与控制流分析和数据流分析无关的结点信息;其次,构建控制依赖子图;同时如果需要数据流分析,在控制依赖子图的基础上构建控制流图,在控制流图的基础上构建数据流子图;最后通过引入过程间分析来完善系统依赖图.实验结果表明,这种方法基本能正确的分析源程序的控制依赖和数据依赖关系,具有更好的适应性和灵活性.