共查询到20条相似文献,搜索用时 62 毫秒
1.
2.
3.
模糊聚类计算的最佳算法 总被引:14,自引:0,他引:14
给出模糊关系传递闭包在对应模糊图上的几何意义,并提出一个基于图连通分支计算的模糊聚类最佳算法.对任给的n个样本,新算法最坏情况下的时间复杂性函数T(n)满足O(n)≤T(n)≤O(n2).与经典的基于模糊传递闭包计算的模糊聚类算法的O(n3logn)计算时间相比,新算法至少降低了O(n相似文献
4.
5.
分别在两种重要并行计算模型中给出计算有向基因组排列的反转距离新的并行算法.基于Hannenhalli和Pevzner理论,分3个主要部分设计并行算法:构建断点图、计算断点图中圈数、计算断点图中障碍的数目.在CREW-PRAM模型上,算法使用O(n2)处理器,时间复杂度为O(log2n);在基于流水光总线的可重构线性阵列系统(linear array with a reconfigurable pipelined bus system, LARPBS)模型上,算法使用O(n3)处理器,计算时间复杂度为O(logn). 相似文献
6.
区域查询是数据仓库上支持联机分析处理(on-line analytical processing,简称OLAP)的重要操作.近几年,人们提出了一些支持区域查询和数据更新的Cube存储结构.然而这些存储结构的空间复杂性和时间复杂性都很高,难以在实际中使用.为此,提出了一种层次式Cube存储结构HDC(hierarchical data cube)及其上的相关算法.HDC上区域查询的代价和数据更新代价均为O(logdn),综合性能为O((logn)2d)(使用CqCu模型)或O(K(logn)d)(使用Cqnq+Cunu模型).理论分析与实验表明,HDC的区域查询代价、数据更新代价、空间代价以及综合性能都优于目前所有的Cube存储结构. 相似文献
7.
本文在一个EREW PRAM(exclusive read exclusive write paralled random accessmachine)上提出一个并行快速排序算法,这个算法用k个处理器可将n个项目在平均O((n/k+logn)logn)时间内排序.所以平均来说算法的时间和处理器数量的乘积对任何k≤n/logn是
O(nlogn). 相似文献
8.
9.
10.
11.
图作为表示实体间的数据结构,在社区发现、生物化学分析、社会安全分析等数据关联性要求较高的领域有着广泛的应用。对于大规模数据下进行实时的图查询问题,通过构建合适的索引可以有效降低查询响应时间,提高查询精确度。首先介绍基于索引的子图查询算法的基本结构;然后按索引的构建方式将主流算法分为基于枚举的方法和基于频繁模式挖掘的方法两大类,分别从索引特征、索引结构、应用数据集等方面进行介绍和分析;最后对基于索引的子图查询算法面临的主要问题进行总结和分析,阐述了最新的分布式系统下图查询技术,并对未来趋势进行展望。 相似文献
12.
13.
14.
在对图形数据库中的几种有代表性的传统相似性搜索及索引构造方法进行总结分析的基础上,探讨了近似图包含搜索区别于传统相似性搜索的特征,并且提出了一种针对近似图包含搜索的基于覆盖率和支持度对频繁子模式进行筛选的索引构造算法。实验结果验证了该方法的有效性。 相似文献
15.
传统的子图查询算法大多只在图数据库上进行一次挖掘算法,即在图数据库上建立稳定的数据库索引后将不再对索引进行更新.随着查询兴趣的改变或数据库的频繁更新,原有的数据库索引将不再能提供有用的信息来减少查询过程中候选图的数量.为此,提出一种双索引的子图查询算法,同时在数据库和查询流上挖掘频繁子图并建立索引.子图查询和查询流索引的建立同步进行,即使查询兴趣改变,查询流索引也能自适应地更新索引信息来优化查询效率.针对数据库的频繁更新,查询流索引已提供实时的有效信息,数据库索引无需重新建立.实验结果表明,双索引的结合能有效提高查询子图的处理效率. 相似文献
16.
图挖掘已成为数据挖掘领域研究的热点,然而挖掘全部频繁子图很困难且得到的频繁子图过多,影响结果的理解和应用。可通过挖掘最大频繁子图来解决挖掘结果数量巨大的问题,最大频繁子图挖掘得到的结果数量很少且不丢失信息,节省了空间和以后的分析工作。基于算法FSG提出了最大频繁子图挖掘算法FSG-MaxGraph;结合节点的度、标记及邻接列表来计算规范编码,提出两个定理来减少子图同构判断的次数,并应用改进后的决策树来计算支持度。实验证明,新算法解决了挖掘结果太多理解困难的问题,且提高了挖掘效率。 相似文献
17.
频繁子图挖掘算法研究 总被引:3,自引:1,他引:2
图像能表达丰富语义,但增加了数据结构的复杂性和感兴趣子结构的挖掘难度。综合应用图论知识和数据挖掘的各种技术,对图像进行规范化编码,通过连接和扩展操作产生所有候选子图,引用嵌入集概念,计算候选子图的支持度和频繁度。提出频繁子图挖掘算法FSubgraphM,能从图数据库中挖掘频繁导出子图。 相似文献
18.
Given a pattern graph H with l edges, and a host graph G guaranteed to contain at most one occurrence of a subgraph isomorphic to H, we show that the time complexity of the problem of finding such an occurrence (if any) in G as well as that of the decision version of the problem are within a multiplicative factor O(l) of the time complexity for the corresponding problem in the general case, when G may contain several occurrences of H. It follows that for pattern graphs of constant size, the aforementioned uniqueness guarantee cannot yield any asymptotic speed up. We also derive analogous results with the analogous multiplicative factor linear in the number of vertices of H in the induced case when occurrences of induced subgraphs of G isomorphic to H are sought. 相似文献
19.
基于频繁子树挖掘算法中的前缀节点思想,将模式图分为图核—分支—连接向量三个部分,提出了CBE算法。对在分支上扩展得到的候选模式图,CBE算法能够在常数时间内完成规范化判定。通过实验证明CBE算法的子图挖掘效率有显著提高。 相似文献