基于图形复杂度的空间矢量数据划分和索引技术

矢量空间数据的划分存在计算性能及跨区域的问题。基于空间位置的划分虽可满足空间索引和快速查询的需求,但难以实现并行空间分析的计算负载均衡。本文提出了一种基于图形复杂度的空间矢量数据划分和索引技术,该技术基于图形复杂度,结合Hilbert空间填充曲线进行矢量数据划分,并采用R树建立分布式索引,不仅提升了数据访问速度,还解决了数据倾斜导致的计算失衡问题,为矢量空间计算任务的负载均衡提供了更优支持。

基于滑动窗口的流式RDF数据的模式匹配方法

数据在社交网络中通常呈现为流式的特征。针对流式RDF数据,提出一种增量的模式匹配方法。设计一种面向RDF数据的索引结构,被定义为顶点聚簇的数据子图。提出一种基于顶点-边标签映射的有效验证的匹配算法,减少遍历过程中候选数据规模。实验结果表明,该方法在环状和星状查询图的模式匹配算法效率更具时间优势。

双网络中影响力凝聚子图发现算法

双网络由物理图和概念图构成,其中物理图和概念图共享网络结点集合而具有不同边集合.物理图中边表示结点间实际存在的关系;概念图中边表示结点间的相似程度,通常由计算得出.最近,从双网络中发现凝聚子图,即物理图中连通且概念图中稠密的子图受到研究者的广泛关注,在研讨会筹备、商品推荐和致病基因发现等真实场景中具有广泛应用.但现有研究鲜有考虑双网络中凝聚子图的影响力.为此:1)提出一种基于最小边权重定义的影响力凝聚子图,即影响力k-连通truss(k-ICT)子图模型.k-ICT子图模型能够有效刻画子图在双网络中的重要性且对低影响力边鲁棒.2)由证明可知,发现影响力最大的k-ICT子图是NP-难的,因此提出一种基于概念图边等价类划分的CT索引结构.利用索引的概要图,能够根据不同的k值,快速发现包含所有k-ICT子图的候选子图.3)提出了基于全局枚举删除和局部子图扩展的精确算法Exact-G kICT和Exact-LkICT,用于发现top-r具有最大影响力的k-ICT子图.通过大量在真实数据集上的实验,验证算法的高效性和有效性.

基于图结构特征采样数据摘要的联邦知识图谱查询

联邦SPARQL查询是通过构建查询计划来指导查询执行,数据摘要索引文件捕获了RDF数据集的结构和语义信息,对查询计划生成过程中子查询基数评估至关重要。现有的数据摘要生成方法需要远程遍历每个数据源的完整数据,该过程成本消耗较高,且在大部分环境中联邦查询无法完成对大数据集的统计工作。为在减少数据摘要索引文件生成时间和内存开销的同时捕获尽可能真实的计数信息,考虑主语和谓语的分布偏差,提出利用样图生成原始图近似数据摘要的方法。使用对RDF图出度特征加权的采样方法获取原始图的典型样图,通过改进的映射函数将样图中的信息映射到原始图上,从而生成原始图的近似数据摘要。实验结果表明,该方法相比于基线方法至少节省了70%的数据摘要索引文件生成时间,并且仅采样0.5%的原始图生成的近似数据摘要即可在查询正确率上与基线方法保持高度一致。

面向大规模图数据的关键词覆盖最优路径规划方法

针对个性化自驾游路径规划中存在规划路径无法满足不同用户个性化需求的问题,提出了基于不同用户兴趣点的关键词覆盖最优路径规划方法。首先,建立路网信息预处理模型并通过路网信息预处理算法绘制路网信息查询图;其次,使用倒排索引算法根据用户设定的个性化需求对路网信息查询图进行剪枝,在减小大规模数据处理内存开销的同时提升了关键词覆盖最优路径规划方法的执行效率;最后,通过双向并行拓展方式的关键词覆盖最优路径拓展算法实现满足用户兴趣点的个性化旅游路径推荐。实验结果表明,关键词覆盖最优路径规划方法不仅实现了满足用户个性化需求的路径规划,而且通过剪枝和双向并行拓展的方式提高了方法的执行效率。

统计数据分析的若干挑战与进展

大数据时代,数据的特征相较以往已经发生了巨大的变化,从而对传统的统计数据分析提出了新的挑战.本文将从若干角度介绍大数据分析的机遇与挑战,并回顾近年来在相关领域的研究进展.

图数据格式对三角形计数算法影响的特性分析

图计算由当前图应用与输入图数据驱动,而图应用各式各样、图结构也千差万别,相同图应用处理不同图时性能差异巨大.为探究图数据格式对图算法的性能影响,本文选取5种常用的图数据格式COO、CSC、CSR、DCSC和CSCI以及社区发现算法三角形计数在图数据p2p-Gnutella04、p2p-Gnutella06、soc-Epinions1上的应用作为分析对象,定义了图数据格式对图计算系统影响的性能指标,包括执行时间、数据移动量、计算量、功耗和各级cache MPKI等,基于Skylake Xeon(R)Platinum 8164处理器进行性能事件采集.实验结果表明,TC在COO、CSC、CSR、DCSC和CSCI格式下运行p2p-Gnutella04/06、soc-Epinions1图数据的执行时间(归一化到最长执行时间)之比为35.7%、0.04%、0.15%、9.7%、100%与34.1%、0.05%、1.81%、9.76%、100%和9.49%、0.92%、0.99%、9.1%、100%,数据移动量(归一化到最大数据移动量)之比为74.9%、3.7%、4.5%、20.32%、100%与100%、0.65%、0.81%、27.37%、13.43%和97.08%、42.94%、42.95%、86.38%、100%,计算量(归一化到最大计算量)之比为39.36%、6.5%、8.62%、10.68%、100%与31.6%、6.97%、8.64%、8.67%、100%和100%、0.9%、0.89%、28.09%、33.07%,功耗(归一化到最大功耗)之比为100%、57.39%、47.73%、33.24%、75.28%与37.03%、84.7%、40.8%、43.4%、100%和100%、34.77%、29.01%、28.39%、86%.实验结果对于为TC应用的输入图数据格式选择提供了依据.

基于指数成分股关联的图卷积指数走势预测

利用历史交易数据预测股市指数未来走势是金融领域的重要问题,使用图卷积网络融合指数间走势关联性是该领域的前沿热点。针对当前图卷积指数预测中历史与未来动态图不一致的问题,提出一种基于指数成分股构建图结构的图卷积指数走势预测方法G-Conv。该方法提取传统量化特征和一维卷积网络的深度特征作为预测样本的特征。使用指数的成分股数据构建指数图结构,并对不同指数样本特征做图卷积以得到指数预测结果。使用A股中42个常用指数验证该方法的有效性。实验使用MAE和MSE作为模型训练的损失函数,选取GC-CNN、ADGAT等经典方法作为比较基准,结果表明在两种误差评价标准下,G-Conv分别降低平均预测误差5.10%和4.20%,且表现出较好的泛化性能。

支持动态图数据的子图查询方法

近年来,子图查询作为图数据库管理的一项重要课题受到国内外学者的广泛关注。在现实应用中大部分图数据是频繁更新的,而现有方法对图数据的频繁更新的维护代价较高。子图查询本身就是NP完全问题,在动态图数据上子图查询问题就变得更加困难。针对上述问题,提出了支持动态图数据的子图查询方法。该方法首先构造出每张图的拓扑层次序列作为索引,在序列中加入标号以便数据更新后对索引进行维护,再根据序列间的匹配关系过滤出候选集合,最后采用图同构算法验证候选集中的图,最终得到结果集合。该方法的索引构造简单且体积小,并且在图数据库更新后无需重构索引,不仅支持动态图数据上的子图查询,在静态图数据上也表现出良好的性能。

大规模数据图上的个性化子图匹配算法

以图结构来描述实体间复杂的关联关系被广泛应用于多种不同的领域.但是,随着这些领域的蓬勃发展,图结构数据的数据量也与日俱增.如何根据用户提交的查询图,在大规模数据图上高效地返回满足用户要求的匹配成为目前学术界和工业界首要的研究问题.然而,之前的工作,多数都是在无权图上查询,没有考虑用户的个性化需求,并且算法运行在大规模数据图上的执行时间并不是很理想.提出一个适用于有权查询图并且适用于大规模数据图上查询的个性化子图匹配算法(personalized subgraph matching,PSM).首先,通过已有的社团检测GN算法将数据图划分成若干个子区域,并构建2个线下索引:GP-Tree索引和排序边集索引(sorted lists index,SL);然后,基于索引结构,通过增加优化策略进而加速子图匹配;最后,本文通过大量实验验证了本文算法的有效性和扩展性.

大规模图数据可达性索引技术:现状与展望

随着社交网络、生物信息网、本体等新兴领域的飞速发展,在现实应用中涌现出大量的图数据.可达性查询是有向图上一类最基本的查询.当图的规模非常小时,利用深度优先遍历(depth-first search,DFS)或可达性传递闭包可以很容易处理可达性查询.但是,随着图的规模越变越大,由于DFS方法的查询效率太低而可达性传递闭包方法占用的存储空间太大,这2种方法不再适用.因此,许多可达性索引方法相继被提出.这些方法已经被广泛应用于多个计算机科学领域,如软件工程、编程语言、分布式计算、社交网络分析、生物网络分析、XML和RDF数据库、路由规划等领域.此外,可达性索引还可用于加速其他图算法,如最短路径查询和子图模式匹配.首先介绍了可达性索引的应用背景.接着,依据支持的数据规模、数据类型以及查询类别,将现有可达性索引工作进行了分类,并对代表性工作进行分类比较;最后,讨论了现有的大规模图数据可达性索引方法存在的问题,并指出了未来的研究方向.

面向大规模图数据的分布式可达性索引与查询策略

针对构建大规模图数据可达性索引时的构建时间长、存储代价高和响应时间长等问题,提出一种分布式可达性索引与查询策略(DRIQ)。在不破坏原图中节点可达性的前提下,将大规模图划分成若干小规模子图,并对每个子图分布式并行地创建可达性索引,从而提高可达性索引创建效率。给出保持图划分后各子图内节点间以及子图间节点可达性的方法,从而保证基于DRIQ进行可达性查询的正确性。实验结果表明,与传统可达性查询方法相比,该策略具有高效性和可扩展性。

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

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

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

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

一种大规模图数据上已知项搜索的优化方法

近年来,在社交网络、生物信息、软件工程、知识工程等领域,以图为天然组织结构的数据开始大量涌现,从而使得图数据的查询、搜索、挖掘等问题迅速成为研究热点.然而,由于图的计算复杂度高,现有的图数据关键词搜索方法的可伸缩性差,难以应用于大规模图数据.创新性地从对用户搜索意图的探索出发,探讨了可能存在的不同类型的图搜索及其优化潜力,提出了根据不同类型搜索的特点采用专门的优化策略的思想;并针对其中非常重要和常见的"已知项搜索"提出了一种启发式优化方法,利用图中局部拓扑信息构建索引,并使用MapReduce技术处理大规模图数据,实现在搜索前裁剪匹配顶点,以少量可能存在的top-k答案丢失为代价来显著缩减搜索空间.实验证明该方法能够极大地减少已知项搜索的响应时间.

云环境下基于MKd-Tree的大规模图数据索引技术

由于高维属性和海量数据所带来的影响,数据管理需要相当高的计算负载,传统的集中索引技术已经变得不切实际。为满足数据的快速增长、海量和高维特性的要求,实现了一个高层次的分布式树形索引结构框架MRC-Tree。基于MRC-Tree框架基础上,提出了两种MKd-Tree索引结构构建方法,即OMKd-Tree和MMKd-Tree。理论分析和实验结果表明,基于MRC-Tree框架的MKd-Tree索引结构构建方法具有良好的可扩展性和较高的检索效率。

基于优化过滤策略的XML数据查询处理

如何高效地处理XML查询,是目前研究的热点。由于当前方法存在过多扫描无用节点引起效率下降的问题,本文设计了一种XML数据的二级索引结构,基于该结构给出路径查询处理算法。首先,本文对XML模式中每个节点按路径类型进行分类编码,然后把每个节点按该编码进行聚类存储。在查询时,就可以先根据模式信息和查询信息得到目标节点的编码,然后只需将二级索引中这些编码对应的部分载入内存,进行过滤操作。这样就不必扫描整个索引,提高CPU和IO效率。本文还对二级索引结构进行扩展,使本文的过滤索引能方便应用在有分支结构的查询上。实验结果表明,本文的XML数据过滤算法效率优于基于Bitvector的过滤算法,并且索引结构所需要的存储空间也小于Bitvector索引。

CWI中的分布式图数据存储与查询

现存的Web分析技术大多基于数据的文本内容,而忽视了数据本身的结构信息。为此,介绍CWI——一种新的海量数据分析和查询工具。作为CWI的一部分,TLGM和TLGM-Ql实现了对于Web数据内容和结构的查询分析,并且在分布式环境下实现了TLGM的图数据存储,实现了TLGM-QL的4个基本算子,实验证明该结构具有良好的平衡性和可扩展性。

基于知识元标引的《王旭高医案》逻辑数据及知识图谱探析

目的采用知识元理论的信息技术梳理、分析中医古籍内容,构建知识图谱探析隐含的逻辑关系以发现新知识。方法以《王旭高医案》为例,在基于知识元理论与技术深度标引的基础上,首先利用MS SQL Server数据库将标引数据读取为逻辑数据并初步分析;其次以基于neo4j数据库构建的中医古籍知识图谱技术呈现出显性知识,同时探析其深层的逻辑推理关系,进一步发现隐性知识。结果《王旭高医案》共有知识体787个,知识元5153个,语义类型共有1149个,语义关联共有510个。分析逻辑数据和机构化知识图谱可知,虚劳的知识元与语义关联最多,其中与肝脏、脾胃的语义关联最多。结论《王旭高医案》整体来看特点在于重视对各类疾病证候表现的描述以及病因病机的分析,王氏诊治虚劳的经验较为丰富,从肝入手诊疗虚劳,尤其重视肝脾同病的病机。

图数据隐私保护可达性查询算法研究

数据库领域越来越多的数据通过图的结构进行存储,随着图数据规模的快速增长和云计算的兴起,数据拥有者希望将数据外包给具有强大计算能力的服务商为其客户提供查询服务。为解决数据库中的可达性查询问题,提出一种隐私保护的可达性索引和查询方法。对原始的2-hop索引构建方法进行优化,设计max ISCover启发式方法,给出根据人工节点添加算法建立pp-2-hop索引的unify IS和unify LS算法,并在此基础上,给出基于密文域的优化可达性查询方法。实验结果表明,基于max ISCover优化方法和unify IS算法建立的索引大小相比于基于原始2-hop索引的方法减小1个-2个数量级。