检索结果-南通市图书馆

在线全文

学校读者我要写书评

暂无评论

基于多路归并的演绎故障模拟方法

装甲兵工程学院学报 1996年第3期10卷 55-58页

作者：宫云战装甲兵工程学院计算机教研室北京100072

提出了一个基于多路归并技术的演绎故障模拟方法,该方法对于集合运算∪,∩,-的计算复杂性是拟线性的,从而保证本文所提出的故障模拟方法的计算复杂性是拟线性的。

关键词：多路归并演绎故障模拟计算复杂性

在线全文

学校读者我要写书评

暂无评论

纵横多路并行归并算法

计算机研究与发展 2006年第12期43卷 2180-2186页

作者：王颖李肯立李浪李仁发湖南大学计算机与通信学院

基于倾斜与振荡法多路归并排序算法,提出了纵横多路并行归并算法,与已有方法递归应用两路归并过程不同·该算法直接对m×k的矩阵(m,k为任意整数)进行排序,消除了对两路递归过程的依赖,是一种新的多路归并排序算法·通过和倾斜与振荡法... 详细信息

基于倾斜与振荡法多路归并排序算法,提出了纵横多路并行归并算法,与已有方法递归应用两路归并过程不同·该算法直接对m×k的矩阵(m,k为任意整数)进行排序,消除了对两路递归过程的依赖,是一种新的多路归并排序算法·通过和倾斜与振荡法多路归并排序算法和高效的任意路并行归并算法的性能分析比较,当3k40时,该算法的时间复杂性低于同类算法·同时,该算法在专用硬件实现的设计复杂性上也具有明显的优势·

关键词：倾斜与振荡法归并排序多路归并并行算法

在线全文

学校读者我要写书评

暂无评论

一种新的多路归并排序网络

计算机研究与发展 1999年第4期36卷 417-422页

作者：赵立军刘志勇中国科学院计算技术研究所

文中提出了一种新的多路归并排序网络，该网络基于倾斜与振荡多路归并排序算法．该网络有两个主要特点．一是其基本构件为ｋ－ｓｏｒｔｅｒｓ，即ｋ个数的排序器，ｋ为任意素数，而传统的排序网络的基本构件为两个数的排序，即２－ｓｏ... 详细信息

文中提出了一种新的多路归并排序网络，该网络基于倾斜与振荡多路归并排序算法．该网络有两个主要特点．一是其基本构件为ｋ－ｓｏｒｔｅｒｓ，即ｋ个数的排序器，ｋ为任意素数，而传统的排序网络的基本构件为两个数的排序，即２－ｓｏｒｔｅｒｓ．二是该网络的延迟可以小于传统的基于２－ｓｏｒｔｅｒｓ的Ｂａｔｃｈｅｒ排序网络．文中给出了该排序网络的具体实现；作为实例给出了Ｎ＝２７，ｋ＝３时的排序网络；分析了该网络的时间延迟；通过具体设计排序网络的基本构件２－ｓｏｒｔｅｒｓ和３－ｓｏｒｔｅｒｓ，表明这种新的多路归并排序网络和Ｂａｔｃｈｅｒ排序网络相比是一种高速的排序网络．

关键词：多路归并排序网络算法计算机

在线全文

学校读者我要写书评

暂无评论

桶外排序算法的抽样分点分发策略

软件学报 2005年第5期16卷 643-651页

作者：杨磊黄辉宋涛清华大学计算机科学与技术系北京100084 中联绿盟信息技术(北京)有限公司开发部北京100089

计算机外排序常用二阶段多路归并算法和桶算法.后者运算开销小,效率更高.但基于关键字高位比特的子文件分发策略应用受限:关键字必须是整数;得到的子文件可能大小不一;子文件数不能任意选择.基于统计学理论,提出抽样分点分发策略克服以... 详细信息

计算机外排序常用二阶段多路归并算法和桶算法.后者运算开销小,效率更高.但基于关键字高位比特的子文件分发策略应用受限:关键字必须是整数;得到的子文件可能大小不一;子文件数不能任意选择.基于统计学理论,提出抽样分点分发策略克服以上问题,扩展桶排序的应用范围.讨论了抽样分点估计的收敛性,给出了不发生内存溢出的保证概率.该策略使桶排序算法在SheenkSort排序系统上得到成功应用,并最终获得2003年度PennySort世界排序比赛Indy组冠军.

关键词：外排序桶排序多路归并分发策略抽样分点 PennySort

在线全文

学校读者我要写书评

暂无评论

基于选择性加载策略的电能质量数据处理

计算机应用 2016年第5期36卷 1434-1438页

作者：赵霞林天华马素霞齐林海北京航空航天大学自动化科学与电气工程学院北京100191 河北经贸大学信息技术学院石家庄050061 华北电力大学控制与计算机工程学院北京102206

根据电能质量系统中监测数据海量化的趋势,提出了一种基于部分存储和选择性加载的数据处理算法,彻底解决了现有数据处理算法中重复排序和多余处理的问题。在计算日指标时,根据存储率存储部分日排序数据;在计算周(月、季、年)指标时,利... 详细信息

根据电能质量系统中监测数据海量化的趋势,提出了一种基于部分存储和选择性加载的数据处理算法,彻底解决了现有数据处理算法中重复排序和多余处理的问题。在计算日指标时,根据存储率存储部分日排序数据;在计算周(月、季、年)指标时,利用多路归并算法将存储的部分日排序数据合并,计算出临时95概率大值(CP95);根据临时CP95确定需要重载的日数据,对部分存储的日数据和重载数据重新排序以计算稳态指标。部分存储的日排序数据可以重复利用,有效解决了传统处理方案中的重复排序问题;排序过程中只需读取部分日排序数据和少量重载数据,有效解决了传统处理方案中冗余处理问题。与传统的数据处理方法做测试对比,结果表明:日采样数据较小时,性能提升3倍以上;日采样数据超过2880时,性能提升15倍以上。数据量越大,性能提升越明显。所提方案已在山西、河北等监测系统中成功应用,实践证明所提方案正确、有效。

关键词：电能质量海量数据多路归并存储率重载率

大规模通用后缀树构建分布并行算法研究与实现

在线全文

学校读者我要写书评

暂无评论

大规模通用后缀树构建分布并行算法研究与实现

作者：郭晨南京大学

学位级别：硕士

通用后缀树是一种对序列集合中的所有序列的后缀进行索引形成的数据结构。其不仅可以高效解决诸如序列匹配与查找、最长公共子序列查询等很多基本序列分析问题,而且在DNA序列匹配、代码克隆检测、语言模型、序列模式挖掘等场景下有很大... 详细信息

通用后缀树是一种对序列集合中的所有序列的后缀进行索引形成的数据结构。其不仅可以高效解决诸如序列匹配与查找、最长公共子序列查询等很多基本序列分析问题,而且在DNA序列匹配、代码克隆检测、语言模型、序列模式挖掘等场景下有很大的应用价值。通用后缀树构建是一个大型复杂算法,其构建过程涉及大量复杂计算和I/0,使得构建过程复杂而耗时。尤其是,大数据时代,很多应用问题的数据集规模巨大,使得大规模数据场景下的通用后缀树构建变得更为复杂,难以在较短时间内快速完成构建。因此,大规模通用后缀树构建成为领域内的一个基础性研究热点问题。过去数十年来,后缀树构建已有诸多相关的研究工作。但现有研究工作仍存在三方面的主要问题:第一,现有研究工作并没有直接解决通用后缀树的构建问题,而是研究通用后缀树的特例——后缀树的构建算法,再转换为通用后缀树,这种做法对通用后缀树构建问题的特殊性,例如输入形态的多样性考虑不足;第二,经过几十年的发展,现有的后缀树构建算法虽然取得了长足的进步,但仍存在着I/0难以优化、未考虑数据扩展性、性能不稳定等问题,难以支撑大规模场景下的后缀树构建任务;第三,现有研究工作大多基于单机或超级计算机设计,大数据应用需求背景下,基于单机设计的传统算法难以应对大规模数据集的处理,而基于超级计算机设计的算法应用门槛太高、代价较大。大数据时代,基于分布式集群的大数据并行处理平台搭建成本低、易于维护、扩展性好,已成为解决大规模问题的主流计算平台。但目前尚缺少大数据应用场景下高效可扩展的大规模通用后缀树构建算法,设计并实现大规模通用后缀树构建分布并行算法存在着诸多技术难点。首先,算法需要针对大规模分布式场景,充分发挥分布式存储以及并行计算的优势;其次,算法需要具有良好的通用性,对不同的输入序列形态(例如大量短序列、一条长序列、若干长度差异很大的序列等)均需具有良好的处理能力,并具备良好的可扩展性以及较高的计算性能。基于上述问题背景,本文研究实现了一种分布式场景下的大规模通用后缀树并行构建算法LMdst,支持对不同规模和各种输入形态的序列数据,构建通用后缀树。本文的主要工作内容以及贡献点如下:(1)研究提出了一种基于Lcp多路归并的高效可扩展的大规模通用后缀树构建分布并行算法LMdst。(2)研究实现了基于trie树的分布并行化子树划分方法,可以高效并行化统计子序列频数进而划分子树;针对子树划分,进一步提出了一种基于输入片段的数据划分方法,屏蔽了输入序列形态、数据存储等因素对算法性能的影响。(3)研究提出了基于Lcp-range的高效序列比较方法和基于败者树多路归并的后缀子树并行构建方法。以此为基础,设计实现了一套综合考虑计算和I/O的后缀子树批量构建优化方法。(4)研究提出了基于装箱和整数划分的子树构建任务分配方法,既能充分利用每个计算单元的计算资源又能在分布式场景中保持良好的负载均衡。(5)对算法进行了计算复杂度以及I/O开销等方面的理论分析,并基于Apache Spark平台设计实现了大规模通用后缀树构建分布并行算法LMdst,实验结果表明LMdst在大规模场景下具有优异的计算性能、近线性的可扩展性以及良好的通用性。本文工作所设计实现的大规模通用化后缀树构建分布并行化算法,在2017年教育部科技发展中心主办的第三届“全国高校云计算应用创新大赛”大数据技能赛全国总决赛上,以其优异的算法性能,获得第一名的成绩,荣获技能赛一等奖。

关键词：大数据通用后缀树分布并行算法多路归并

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

Lucene架构下布尔查询的执行计划研究

云南民族大学学报（自然科学版） 2019年第6期28卷 606-611页

作者：赵广武汉体育学院体育工程与信息技术学院

Lucene是一个优秀的全文检索框架,布尔查询是其实现精准数据检索的重要功能.对于布尔查询执行计划的深入研究,有利于灵活应用布尔查询,优化查询表达式,提高执行效率.本文从Lucene架构下布尔查询的执行计划入手,研究了布尔查询的表示方... 详细信息

Lucene是一个优秀的全文检索框架,布尔查询是其实现精准数据检索的重要功能.对于布尔查询执行计划的深入研究,有利于灵活应用布尔查询,优化查询表达式,提高执行效率.本文从Lucene架构下布尔查询的执行计划入手,研究了布尔查询的表示方式、执行时序、逻辑运算规则和子查询归并算法.根据布尔查询的执行计划,提出了深度为2的复杂布尔查询的化简规律和布尔逻辑运算满足交换律的特性,并从理论上证明它们的正确性.最后通过实验模拟仿真,验证这些规律的有效性.

关键词： Lucene 布尔查询多路归并执行计划

在线全文

学校读者我要写书评

暂无评论

多属性汉字正文快速排序

中文信息 1995年第1期 34-35页

作者：黄水清南京农业大学

在编制中文应用软件中,常常会碰到汉字文件的排序问题。如图书情报单位要排卡片目录,人事部门要排档案材料。一般的西文软件都有排序功能,象DOS、Foxbase的Sort。但西文软件的排序命令是以字符的内码作为比较依据的,不适用于汉字排序。... 详细信息

在编制中文应用软件中,常常会碰到汉字文件的排序问题。如图书情报单位要排卡片目录,人事部门要排档案材料。一般的西文软件都有排序功能,象DOS、Foxbase的Sort。但西文软件的排序命令是以字符的内码作为比较依据的,不适用于汉字排序。为解决汉字文件的排序问题,笔者编制一个类似于DOS下的Sort命令的正文

关键词：快速排序四角号码笔画拼音笔顺多路归并临时文件正文快速排序法属性库

在线全文

同方期刊数据库

学校读者我要写书评

暂无评论

高效的任意路并行归并算法

中国科学（E辑） 1998年第5期28卷 463-471页

作者：赵立军刘志勇高庆狮中国科学院计算技术研究所北京100080 国家自然科学基金委员会信息科学部北京100083 北京科技大学计算机系北京100083

提出了一种新的k路 (k way)归并算法 ,该算法的目标是将k个m个关键字 (以m×k矩阵表示 )的有序序列归并成一个以行为主的有序序列 .其特点是采用k路归并 ,首先按斜率由大到小 (最后为 1 )对矩阵的元素进行斜向排序 ,然后再用常数步将其... 详细信息

提出了一种新的k路 (k way)归并算法 ,该算法的目标是将k个m个关键字 (以m×k矩阵表示 )的有序序列归并成一个以行为主的有序序列 .其特点是采用k路归并 ,首先按斜率由大到小 (最后为 1 )对矩阵的元素进行斜向排序 ,然后再用常数步将其排成有序序列 ,这里k为任意整数 .本算法所需的基本部件是k sorters ,而其基本过程是k个元素的排序 ,设其时间为tk,k路归并算法的时间为 ( 2 1 +[log(m/k) ])×tk.

关键词：归并排序多路归并奇偶归并并行算法排序