栏目文章

Select

1. 大数据存储架构和算法研究综述

杨俊杰, 廖卓凡, 冯超超

计算机应用 2016, 36 (9): 2465-2471. DOI: 10.11772/j.issn.1001-9081.2016.09.2465

摘要（680）

PDF （1246KB）（912）

随着大数据计算需求的增长，集群的处理速度需要得到快速的提升，然而目前大数据处理框架的处理性能已逐渐满足不了这种快速增长的需求。由于集群的存储架构是分布式存储，因此数据的存放在大数据处理过程中成为影响集群的处理性能的因素之一。首先，对当今的分布式文件存储系统的结构进行了介绍；接着，根据不同的优化目标，例如减少网络负载、负载均衡、降低能耗和高容错性等，对近年国内外大数据存储算法的研究进行了总结，分析和对比了已有算法的优点以及存在的问题；最后，对大数据存储架构和优化算法设计的挑战和未来研究方向作了展望。

参考文献 | 相关文章 | 多维度评价

Select

2. 基于导数序列的时间序列同构关系发现

邹蕾, 高学东

计算机应用 2016, 36 (9): 2472-2474. DOI: 10.11772/j.issn.1001-9081.2016.09.2472

摘要（583）

PDF （595KB）（319）

时间序列子序列匹配作为时间序列检索、聚类、分类、异常监测等挖掘任务的基础被广泛研究。但传统的时间序列子序列匹配都是对精确相同或近似相同的模式进行匹配，为此定义了一种全新的具有相似发展趋势的序列模式——时间序列同构关系，经过数学推导给出了时间序列同构关系判定的法则，并基于此提出了同构关系时间序列片段发现的算法。该算法首先对原始时间序列进行预处理，然后分段拟合后对各时间序列分段进行同构关系判定。针对现实背景数据难以满足理论约束的问题，通过定义一个同构关系容忍度参数使实际时间序列数据的同构关系挖掘成为可能。实验结果表明，该算法能有效挖掘出满足同构关系的时间序列片段。

参考文献 | 相关文章 | 多维度评价

Select

3. 多子域隔离学习组合决策用于不均衡样本

靳燕, 彭新光

计算机应用 2016, 36 (9): 2475-2480. DOI: 10.11772/j.issn.1001-9081.2016.09.2475

摘要（528）

PDF （878KB）（224）

为进一步弱化数据不均衡对分类算法的束缚，从数据集区域分布特性着手，提出了不均衡数据集上基于子域学习的复合分类模型。子域划分阶段，扩展支持向量数据描述（SVDD）算法给出类的最小界定域，划分出域内密集区与域外稀疏区。借鉴不同类存在相似样本的类重叠概念，对边界样本进行搜索，组合构成重叠域。子域清理阶段，基于邻近算法（ KNN）的邻近性假设，结合不同域的密疏程度，设置样本有效性参数，对域内样本逐个检测以清理噪声。各子域隔离参与分类建模，按序组合产生出用于不均衡数据集的复合分类器CCRD。在相似算法对比以及代价敏感MetaCost对比中，CCRD对正类的正确分类改善明显，且未加重负类误判；在SMOTE抽样比较中，CCRD改善了负类的误判情形，且未影响正类的正确分类；在五类数据集的逐个比较中，CCRD分类性能均有提升，在Haberman_sur的正类分类性能提升上尤为明显。结果表明，基于子域学习的复合分类模型的分类性能较好，是一种研究不均衡数据集的较有效的方法。

参考文献 | 相关文章 | 多维度评价

Select

4. 基于改进核模糊C均值类间极大化聚类算法

李斌, 狄岚, 王少华, 于晓瞳

计算机应用 2016, 36 (7): 1981-1987. DOI: 10.11772/j.issn.1001-9081.2016.07.1981

摘要（350）

PDF （886KB）（343）

传统的核聚类仅考虑了类内元素的关系而忽略了类间的关系，对边界模糊或边界存在噪声点的数据集进行聚类分析时，会造成边界点的误分问题。为解决上述问题，在核模糊C均值（KFCM）聚类算法的基础上提出了一种基于改进核模糊C均值类间极大化聚类（MKFCM）算法。该算法考虑了类内元素和类间元素的联系，引入了高维特征空间的类间极大惩罚项和调控因子，拉大类中心间的距离，使得边界处的样本得到了较好的划分。在各模拟数据集的实验中，该算法在类中心的偏移距离相对其他算法均有明显降低。在人造高斯数据集的实验中，该算法的精度（ACC）、归一化互信息（NMI）、芮氏指标（RI）指标分别提升至0.9132，0.7575，0.9138。

参考文献 | 相关文章 | 多维度评价

Select

5. 改进的多数据流协同频繁项集挖掘算法

王鑫, 刘方爱

计算机应用 2016, 36 (7): 1988-1992. DOI: 10.11772/j.issn.1001-9081.2016.07.1988

摘要（436）

PDF （769KB）（396）

针对已有的多数据流协同频繁项集挖掘算法存在内存占用率高以及发现频繁项集效率低的问题，提出了改进的多数据流协同频繁项集挖掘（MCMD-Stream）算法。首先，该算法利用单遍扫描数据库的字节序列滑动窗口挖掘算法发现数据流中的潜在频繁项集和频繁项集；其次，构建类似频繁模式树（FP-Tree）的压缩频繁模式树（CP-Tree）存储已发现的潜在频繁项集和频繁项集，同时更新CP-Tree树中每个节点生成的对数倾斜时间表中的频繁项计数；最后，通过汇总分析得出在多条数据流中多次出现的且有价值的频繁项集，即协同频繁项集。相比A-Stream和H-Stream算法，MCMD-Stream算法不仅能够提高多数据流中协同频繁项集挖掘的效率，并且还降低了内存空间的使用率。实验结果表明MCMD-Stream算法能够有效地应用于多数据流的协同频繁项集挖掘。

参考文献 | 相关文章 | 多维度评价

Select

6. 基于卡方分布的高维数据相似性连接查询算法

马友忠, 贾世杰, 张永新

计算机应用 2016, 36 (7): 1993-1997. DOI: 10.11772/j.issn.1001-9081.2016.07.1993

摘要（615）

PDF （829KB）（355）

为了解决高维数据相似性连接查询中存在的维度灾难和计算代价高等问题，基于 p-稳态分布，将高维数据映射到低维空间。根据卡方分布的性质，证明了如果低维空间的距离大于 kε，则原始空间距离大于 ε的概率具有一定的下界，从而可以在低维空间以较低的计算代价进行有效过滤。在此基础上，提出了基于卡方分布的高维数据相似性连接查询算法。为了进一步提高查询效率，提出了基于双重过滤的高维数据相似性连接查询算法。利用真实数据集进行了实验，实验结果表明所提方法具有较好的性能。基于卡方分布的相似性连接查询算法召回率可以达到90%以上。基于双重过滤的相似性连接查询算法可以进一步提高性能，但是会损失一定的召回率。对时间性能要求比较高、对召回率要求不太严格的查询任务可以采用基于双重过滤的相似性连接查询算法；反之，可以采用基于卡方分布的相似性连接查询算法。

参考文献 | 相关文章 | 多维度评价

Select

7. 基于参考节点嵌入的图可达性查询

温菊屏, 胡小生, 林冬梅, 曾亚光

计算机应用 2016, 36 (7): 1998-2005. DOI: 10.11772/j.issn.1001-9081.2016.07.1998

摘要（467）

PDF （1390KB）（303）

针对 k步可达性查询算法无法解决带距离约束的图可达性查询问题，提出基于参考节点嵌入的图可达性查询算法。首先，从所有节点中选出极少数有代表性的全局参考节点，预先计算所有节点与全局参考节点之间的最短路径距离；然后，采用最短路径树和范围最小值查询技术求得局部参考节点；接着，利用三角不等式关系得到查询点对距离范围；最后，根据查询条件中的距离值与查询点对距离范围上、下限值的大小关系，可快速得出可达性结论。针对社会关系网络和公路网络数据，将所提算法与Dijkstra算法、 K-Reach算法进行实验对比测试。相较于 K-Reach算法，其索引建立时间小4个数量级，其索引规模小2个数量级；相较于Dijkstra算法，在公路网络和社会关系网络中，直接得出可达性结论的比例分别为92%和78.6%，其查询时间大大缩短，分别降低了95.5%和92%。实验结果表明：所提算法能够通过使用较小的索引开销，实现在线查询计算复杂度的降低，可很好地解决既适用于有权图又适用于无权图带距离约束的可达性查询问题。

参考文献 | 相关文章 | 多维度评价

Select

8. 基于巴氏系数和Jaccard系数的协同过滤算法

杨家慧, 刘方爱

计算机应用 2016, 36 (7): 2006-2010. DOI: 10.11772/j.issn.1001-9081.2016.07.2006

摘要（629）

PDF （729KB）（395）

针对传统基于邻域的协同过滤推荐算法存在数据稀疏性及相似性度量只能利用用户共同评分的问题，提出一种基于巴氏系数和Jaccard系数的协同过滤算法（CFBJ）。在项目相似性度量中，该算法引入巴氏系数和Jaccard系数，巴氏系数利用用户所有评分信息克服共同评分的限制，Jaccard系数可以增加相似性度量中共同评分项所占的比重。该算法通过提高项目相似度准确率来选取最近邻，优化了对目标用户的偏好预测和个性化推荐。实验结果表明，该算法比平均值-杰卡德差分（MJD）算法、皮尔森系数（PC）算法、杰卡德均方差（JMSD）算法、PIP算法误差更小，分类准确率更高，有效缓解了用户评分数据稀疏所带来的问题，提高了推荐系统的预测准确率。

参考文献 | 相关文章 | 多维度评价

Select

9. 融合时间衰减与偏好波动的协同偏好获取方法

杨立, 胡运红, 邵桂荣

计算机应用 2016, 36 (7): 2011-2015. DOI: 10.11772/j.issn.1001-9081.2016.07.2011

摘要（466）

PDF （709KB）（378）

针对现有的推荐系统多采用近邻用户的偏好行为来预测当前用户的偏好，而不考虑用户的偏好会随着时间的变化而改变，影响了推荐准确率的问题，提出了一种基于时间衰减与偏好波动的协同偏好获取方法。首先，基于时间因素、用户历史偏好等获取偏好衰减增量与衰减速度，并据此生成衰减函数，使用衰减函数对用户历史行为数据进行衰减修正；其次，基于用户的历史偏好分布获取其偏好波动幅度；最后，将衰减函数与偏好波动幅度分别加入到最近邻获取与偏好获取流程，协同为用户生成推荐列表。在大规模真实数据集上的实验结果表明，所提出的方法与基于属性评分分布的协同过滤（RDCF）与最优Top- N的协同过滤（OTCF）相比，平均绝对误差（MAE）值分别降低了近6.42%和7.73%。实验结果表明所提方法能够提高推荐准确度，提升推荐质量。

参考文献 | 相关文章 | 多维度评价

Select

10. 基于层次划分的密度优化聚类算法

逄琳, 刘方爱

计算机应用 2016, 36 (6): 1634-1638. DOI: 10.11772/j.issn.1001-9081.2016.06.1634

摘要（499）

PDF （731KB）（409）

针对传统的聚类算法对数据集反复聚类,且在大型数据集上计算效率欠佳的问题,提出一种基于层次划分的最佳聚类数和初始聚类中心确定算法——基于层次划分密度的聚类优化(CODHD)。该算法基于层次划分,对计算过程进行研究,不需要对数据集进行反复聚类。首先,扫描数据集获得所有聚类特征的统计值;其次,自底向上地生成不同层次的数据划分,计算每个划分数据点的密度,将最大密度点定为中心点,计算中心点距离更高密度点的最小距离,以中心点密度与最小距离乘积之和的平均值为有效性指标,增量地构建一条关于不同层次划分的聚类质量曲线;最后,根据曲线的极值点对应的划分估计最佳聚类数和初始聚类中心。实验结果表明,所提CODHD算法与预处理阶段的聚类优化(COPS)算法相比,聚类准确度提高了30%,聚类算法效率至少提高14.24%。所提算法具有较强的可行性和实用性。

参考文献 | 相关文章 | 多维度评价

Select

11. 弹性粗粒度动态弯曲时序相似性算法

陈明威, 孙丽华, 徐健锋

计算机应用 2016, 36 (6): 1639-1644. DOI: 10.11772/j.issn.1001-9081.2016.06.1639

摘要（478）

PDF （974KB）（428）

针对动态时间弯曲(DTW)算法在提高计算速度同时不能兼顾分类正确率的问题,提出了一种基于朴素粒计算思想的弹性粗粒度动态时间弯曲(CG-DTW)算法。首先,通过计算时序方差特征的方法来获取较优的时序粒度,用粒度特征代替原始序列;其次,再代入执行DTW算法,允许动态调整被比较时序粒间的弹性大小,从而获得相对最优的时序对应粒;最后,在对应最优粒的情况下计算DTW距离。同时引入下界函数的提前终止策略进一步提高CG-DTW算法效率。实验结果表明,所提算法要比经典算法运行速率提高21.4%左右,比降维策略算法正确率提高近32.3个百分点,尤其是长序列的分类,CG-DTW能够在保持正确率的情况下兼顾较高的运行效率。CG-DTW在实际应用中能适应不确定长序列分类。

参考文献 | 相关文章 | 多维度评价

Select

12. 基于可延迟调度提升实时数据对象时序一致性服务质量算法

于鸽, 冯山

计算机应用 2016, 36 (6): 1645-1649. DOI: 10.11772/j.issn.1001-9081.2016.06.1645

摘要（491）

PDF （709KB）（348）

针对保证实时数据对象时序一致性调度算法在软实时数据库系统环境下的应用问题,提出了一种基于概率统计的可延迟优化(SDS-OPT)算法。首先,分析和比较了现有算法在可调度性、服务质量(QoS)以及工作负载方面的特征与不足,指出优化现有算法的必要性;然后,利用最速下降法提升作业的执行时间筛选基准值,进而增加实时更新事务可调度的作业数量,以确保实时数据对象的时序一致性服务质量(QoS)最大化;最后,从工作负载和服务质量两个方面对所提算法和现有算法的性能进行对比分析。仿真实验结果表明,相对于已有的针对固定优先级可延迟调度算法(DS-FP)和统计性的非确定性可延迟调度算法(DS-PS),所提算法能够保证实时数据对象的时序一致性,同时降低工作负载,服务质量提升明显。

参考文献 | 相关文章 | 多维度评价

Select

13. 基于图的服务起源追踪机制

罗波, 李涛, 王杰

计算机应用 2016, 36 (6): 1650-1653. DOI: 10.11772/j.issn.1001-9081.2016.06.1650

摘要（395）

PDF （691KB）（298）

针对服务起源数据存储在关系型数据库和文档型数据库中无法提供高效的服务追踪以及采用图形数据库存储无法进行快速聚合运算等问题,提出了一种基于图的服务起源追踪机制。该机制以图形数据库存储服务起源数据为基础,重新定义服务起源在图形数据库中的存储结构,并提供基于此存储结构的聚合操作。然后提出了基于静态权值、基于混合操作与基于实时任务三种不同的服务起源追踪模型。实验结果表明该服务起源追踪机制能够满足聚合、追踪等不同类型的服务起源数据的查询需求,减少了服务追踪耗时,提高了服务起源数据的追踪效率。

参考文献 | 相关文章 | 多维度评价

Select

14. 扩展知识图谱上的实体关系检索

王秋月, 覃雄派, 曹巍, 覃飙

计算机应用 2016, 36 (4): 985-991. DOI: 10.11772/j.issn.1001-9081.2016.04.0985

摘要（917）

PDF （1139KB）（670）

现有文本数据集上的实体搜索和自然语言查询方法无法处理需要将分散在不同文档中的信息碎片链接起来以满足有复杂实体关系的查询,而知识库上的查询虽然可以表示实体间的复杂关系,但由于知识库的异构性和不完全性,通常查全率较低。针对这些问题,提出使用文本数据集对知识库进行扩展,并设计相应的含文本短语的三元组模式查询以支持对知识库和文本数据的统一查询。在此基础上,设计并实现了查询放松机制和对结果元组的评分模型,并给出了高效的查询处理方法。使用YAGO、ClueWeb09和其上的FACC1数据集,在三个不同的查询测试集(实体检索、实体关系检索和复杂的实体关系查询)上与两个典型相关工作作了比较。实验结果显示,扩展知识图谱上使用查询放松规则的实体关系检索系统的检索效果大大超出了其他系统,具体地在三个查询测试集上,其平均正确率均值(MAP)比其他系统分别提升了27%、37%和64%以上。

参考文献 | 相关文章 | 多维度评价

Select

15. 自动化构建的中文知识图谱系统

鄂世嘉, 林培裕, 向阳

计算机应用 2016, 36 (4): 992-996. DOI: 10.11772/j.issn.1001-9081.2016.04.0992

摘要（1149）

PDF （932KB）（1274）

为解决当前中文知识图谱构建的准确率低、耗时长且需要大量人工参与的问题,提出一种端到端基于中文百科数据的完整中文知识图谱自动化构建解决方案,并在此基础上开发实现了面向用户的中文知识图谱系统。在此方案中,通过自定义的网络爬虫,原始百科数据的词条属性以及相关的文本信息会不间断地被抓取到本地系统中,并以带扩展属性的三元组形式保存。后端系统则自动通过图数据库Cayley以及MongoDB数据库系统,对三元组文件数据进行导入,转换为庞大的知识图谱系统,从而在前端为用户提供丰富的基于知识图谱的应用服务。通过与其他知识图谱系统的比较,该方案在构建时间上明显减少,并且知识图谱中的实体及关系数量总规模高于YAGO、知网(HowNet)和中文概念词典等中文知识图谱系统至少50%。

参考文献 | 相关文章 | 多维度评价

Select

16. 基于间隔链表改进的频繁项集挖掘算法

徐永秀, 刘旭敏, 徐维祥

计算机应用 2016, 36 (4): 997-1001. DOI: 10.11772/j.issn.1001-9081.2016.04.0997

摘要（551）

PDF （748KB）（461）

针对PrePost算法中需要建立复杂的前序和后序编码树(PPC-tree)和节点链表(N-list)的问题,提出一种基于间隔链表(I-list)改进的高效频繁项集挖掘算法。首先,该算法采用了比频繁模模式树(FP-tree)更加压缩的数据存储结构间隔编码的频繁模式树(IFP-tree),无需迭代地建立条件FP-tree;其次,该算法利用更简洁的I-list代替了PrePost中复杂的N-list,从而提高了建树和挖掘速度;最后,对于单分支路径的情况,该算法通过组合的方法,直接求得某些频繁项集,以提高算法的时间性能。实验结果表明:一方面,对于同一数据集在相同支持数下挖掘的结果相同,验证了改进算法的正确性;另一方面,无论在时间还是空间上改进算法的整体性能均比PrePost算法提高约10%;且对于稀疏型数据库或密集型数据库的挖掘都有较好的应用。

参考文献 | 相关文章 | 多维度评价

Select

17. 基于多线程的并行实例恢复方法

卢栋栋, 何清法

计算机应用 2016, 36 (4): 1002-1007. DOI: 10.11772/j.issn.1001-9081.2016.04.1002

摘要（501）

PDF （1114KB）（480）

针对数据库实例恢复串行化执行效率低的问题,以神通数据库为基础提出一种基于多线程的并行实例恢复方法。首先,在数据库原有实例恢复模型基础上,增加"构建脏页表"和"脏页预取"两个步骤,得到改进后的实例恢复模型;其次,结合多线程并发处理思想,提出并行实例恢复方法,对改进的实例恢复模型进行并发处理;最后,由于采用回滚段进行undo日志管理,可以实现undo日志的正常数据化管理,提前结束实例恢复。通过进行TPC-C基准测试,并行实例恢复方法的读取、解析redo日志效率与原有方法相比提高了2~7倍,重做redo日志效率提高了4~9倍,整体所用时间减少为原有方法的20%~40%。实验结果表明,并行实例恢复方法实现了各阶段的并行化,减少了实例恢复所需时间,保证了数据库在实际应用中的高效性。

参考文献 | 相关文章 | 多维度评价

Select

18. 基于列表的可扩展标记语言流数据查询处理方法

何志学, 廖湖声

计算机应用 2016, 36 (3): 665-669. DOI: 10.11772/j.issn.1001-9081.2016.03.665

摘要（415）

PDF （845KB）（397）

针对半结构化可扩展标记语言(XML)流数据实时在线到达,顺序性一次访问及处理时效性高、缓存量小的需求,以及目前算法在大规模数据处理中查询表达式的能力有限、效率尚不能满足实际应用的现状,基于SAX解析,提出以列表及关系指针组合处理XPath查询的QXSList方法。首先定义数据模型,给出算法实现的整体框架,然后分别针对两个不同的XPath查询片段重点考虑了谓词判断条件和通配符的处理方法;该方法通过层次值计算判断节点的结构关系,利用关系指针链接多个候选节点列表,获取查询查询结果;最后分析给出优化算法,进一步减少缓存管理。通过实验对该方法与QStream++方法及MonetDB和SAXON查询引擎的运行时间和内存占比进行分析,得出与同类算法相比,随着数据量级的增加,效率提升在30%以上,且运行过程中内存占比接近于常量。

参考文献 | 相关文章 | 多维度评价

Select

19. 面向海量非结构化数据的非关系型存储管理机制

刘超, 胡成玉, 姚宏, 梁庆中, 颜雪松

计算机应用 2016, 36 (3): 670-674. DOI: 10.11772/j.issn.1001-9081.2016.03.670

摘要（677）

PDF （819KB）（513）

针对传统的关系数据存储系统性能不足、容错性差,无法适应海量非结构化数据管理的问题,提出一种高性能、高可用非关系型存储管理机制。首先,设计了良好的用户访问服务接口,通过高效的一致性哈希算法支持数据分发到多个存储节点;其次,采用可配置的数据副本机制改善存储系统的可用性;最后,提出查询故障处理机制,用以提升存储系统的容错性,避免节点失效导致服务中断问题。实验结果表明,在不同规模用户负载下,新的存储系统的并发访问请求能力和传统的文件系统、关系数据库相比,分别提升了30%和50%;同时,在合理响应时间内,故障状态下的存储系统的可用性损失小于14%。因此,该机制适用于海量非结构化数据的高效存储管理。

参考文献 | 相关文章 | 多维度评价

Select

20. 基于并行遗传最大最小蚁群算法的分布式数据库查询优化

林基明, 班文娇, 王俊义, 童记超

计算机应用 2016, 36 (3): 675-680. DOI: 10.11772/j.issn.1001-9081.2016.03.675

摘要（605）

PDF （962KB）（540）

针对分布式数据库中关系及其分片多副本、多站点存储的特性会增加查询搜索空间及时间复杂度,从而降低查询执行计划(QEP)搜索效率的问题,提出一种基于分片分配选择器(FSS)设计准则的并行遗传-最大最小蚁群算法(PGA-MMAS)。首先,结合实际的企业分布式信息管理系统设计FSS,启发式选择较优关系副本,以减少查询连接代价并缩小PGA-MMAS的搜索空间;然后结合遗传算法(GA)收敛较快的优势,对最终连接关系进行编码和并行遗传操作,得到一组相对较优的QEP,并将其转化为并行最大最小蚁群算法(MMAS)的初始信息素分布,从而使其更快速地搜索到全局最优QEP;最后分别在不同关系数情况下对算法进行仿真实验,结果表明,基于FSS的PGA-MMAS搜索最优QEP的效率高于原GA以及基于FFS的GA、MMAS和GA-MMAS;经实际工程应用验证,所提算法搜索出的高质量QEP可以提高分布式数据库多关系查询效率。

参考文献 | 相关文章 | 多维度评价

栏目文章信息