检索结果-内蒙古大学图书馆

30th International Symposium on Model Checking Software

作者： Solvsten, Steffan Christ Rysgaarde, Casper Moldrup Van de Pol, Jaco Aarhus Univ Aarhus Denmark

ISBN: (纸本)9783031661488;9783031661495

The external memory BDD package Adiar can manipulate Binary Decision Diagrams (BDDs) larger than the RAM of the machine. To do so, it uses one or more priority queues to defer processing each recursion until the relevant nodes are encountered in a sequential scan. We outline how to improve the performance of Adiar's algorithms if the BDD width of one of its inputs is small enough to fit into main memory. In this case, one of the algorithms' priority queues can entirely be replaced with (levelised) random access to the nodes of the narrow BDD. This preserves the I/O efficiency of the original algorithm, is applicable to other types of decision diagrams, and significantly improves performance for many larger BDD computations.

关键词： Binary Decision Diagrams external memory algorithms

来源：评论

学校读者我要写书评

暂无评论

Adiar 1.1 Zero-Suppressed Decision Diagrams in external memory 15th

Adiar 1.1 Zero-Suppressed Decision Diagrams in External Memo...

引用

15th International Symposium on NASA Formal Methods (NFM)

作者： Solvsten, Steffan Christ van de Pol, Jaco Aarhus Univ Aarhus Denmark

We outline how support for Zero-suppressed Decision Diagrams (ZDDs) has been achieved for the external memory BDD package Adiar. This allows one to use ZDDs to solve various problems despite their size exceed the mach... 详细信息

ISBN: (纸本)9783031331695;9783031331701

关键词： Zero-suppressed Decision Diagrams external memory algorithms

来源：评论

学校读者我要写书评

暂无评论

Adiar Binary Decision Diagrams in external memory 28th

Adiar Binary Decision Diagrams in External Memory

引用

28th International Conference on Tools and algorithms for the Construction and Analysis of Systems (TACAS) Held as Part of the 25th European Joint Conferences on Theory and Practice of Software (ETAPS)

作者： Solvsten, Steffan Christ van de Pol, Jaco Jakobsen, Anna Blume Thomasen, Mathias Weller Berg Aarhus Univ Aarhus Denmark

ISBN: (纸本)9783030995270;9783030995263

We follow up on the idea of Lars Arge to rephrase the Reduce and Apply operations of Binary Decision Diagrams (BDDs) as iterative I/O-efficient algorithms. We identify multiple avenues to simplify and improve the performance of his proposed algorithms. Furthermore, we extend the technique to other common BDD operations, many of which are not derivable using Apply operations alone. We provide asymptotic improvements to the few procedures that can be derived using Apply. Our work has culminated in a BDD package named Adiar that is able to efficiently manipulate BDDs that outgrow main memory. This makes Adiar surpass the limits of conventional BDD packages that use recursive depth-first algorithms. It is able to do so while still achieving a satisfactory performance compared to other BDD packages: Adiar, in parts using the disk, is on instances larger than 9.5 GiB only 1.47 to 3.69 times slower compared to CUDD and Sylvan, exclusively using main memory. Yet, Adiar is able to obtain this performance at a fraction of the main memory needed by conventional BDD packages to function.

关键词： Time-forward Processing external memory algorithms Binary Decision Diagrams

来源：评论

学校读者我要写书评

暂无评论

Belga B-Trees

引用

THEORY OF COMPUTING SYSTEMS 2021年第3期65卷 541-558页

作者： Demaine, Erik D. Iacono, John Koumoutsos, Grigorios Langerman, Stefan MIT CSAIL 77 Massachusetts Ave Cambridge MA 02139 USA Univ Libre Bruxelles Brussels Belgium NYU New York NY USA Fonds Rech Sci FRS FNRS Brussels Belgium

We revisitself-adjustingexternal memory tree data structures, which combine the optimal (and practical) worst-case I/O performances of B-trees, while adapting to the online distribution of queries. Our approach is analogous to undergoing efforts in the BST model, whereTango Trees(Demaine et al., SIAM J. Comput.37(1), 240-251,2007) were shown to be O(log log N)-competitive with the runtime of the best offline binary search tree on every sequence of searches. Here we formalize the B-Tree model as a natural generalization of the BST model. We prove lower bounds for the B-Tree model, and introduce a B-Tree model data structure, the Belga B-tree, that executes any sequence of searches within a O(log logN) factor of the best offline B-tree model algorithm, provided B = log O(1)N. We also show how to transform any static BST into a static B-tree which is faster by a Theta(log B) factor;the transformation is randomized and we show that randomization is necessary to obtain any significant speedup.

关键词： Dynamic optimality external memory algorithms Data structures Online algorithms

来源：评论

学校读者我要写书评

暂无评论

Better external memory LCP array construction

引用

ACM Journal of Experimental Algorithmics 2019年第1期24卷 1-27页

作者： Kärkkäinen, Juha Kempa, Dominik Helsinki FI-00014 Finland

The suffix array, perhaps the most important data structure in modern string processing, needs to be augmented with the longest-common-prefix (LCP) array in many applications. Their construction is often a major bottleneck, especially when the data is too big for internal memory. We describe two new algorithms for computing the LCP array from the suffix array in external memory. Experiments demonstrate that the new algorithms are about a factor of two faster than the fastest previous algorithm. We then further engineer the two new algorithms and improve them in three ways. First, we speed up the algorithms by up to a factor of two through parallelism. Eight threads is sufficient for making the algorithms essentially I/O bound. Second, we reduce the disk space usage of the algorithms making them in-place: the input (text and suffix array) is treated as read-only, and the working disk space never exceeds the size of the final output (the LCP array). Third, we add support for large alphabets. All previous implementations assume the byte alphabet. © 2019 Association for Computing Machinery.

关键词： external memory algorithms LCP array suffix array

来源：评论

学校读者我要写书评

暂无评论

An SNN-DBSCAN Based Clustering Algorithm for Big Data 3rd

An SNN-DBSCAN Based Clustering Algorithm for Big Data

引用

3rd International Conference on Advanced Computing and Intelligent Engineering (ICACIE)

作者： Pandey, Sriniwas Samal, Mamata Mohanty, Sraban Kumar PDPM Indian Inst Informat Technol Design & Mfg Comp Sci & Engn Jabalpur 482005 Madhya Pradesh India

ISBN: (纸本)9789811510816;9789811510809

Clustering is a technique to partition data into different groups in such a way that data items in a group are more similar to each other than the data points in any other group. The assumption of infinite main memory is very usual while designing most of the clustering algorithms but this assumption fails when the size of data set starts increasing. In this scenario, data needs to be stored in the secondary memory and time spent in the input/outputs (I/O) dominates the actual computational time. Therefore by reducing the I/O, the efficiency of the clustering techniques can be improved. In this paper, one shared near neighbor based algorithm is devised by minimizing its I/O complexity to make it suitable for the Big Data in external memory model proposed by Aggarwal and Vitter. There is no change in the computational steps, hence cluster quality remains the same. We implement the algorithm in the STXXL library to show its efficacy for Big Data sets.

关键词： Clustering SNN clustering external memory algorithms Big data clustering

来源：评论

学校读者我要写书评

暂无评论

An Input/Output Efficient Algorithm for Hessenberg Reduction

引用

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 2019年第8期30卷 1279-1300页

作者： Mohanty, Sraban Kumar Sajith, G. PDPM Indian Inst Informat Technol Design & Mfg Comp Sci & Engn Jabalpur MP India Indian Inst Technol Guwahati Comp Sci & Engn Gauhati Assam India

Reduction of an N x N nonsymmetric matrix to Hessenberg form which takes O(N-3) flops and O(N-3/B) I/Os is a major performance bottleneck in the computing of its eigenvalues. Usually to improve the performance, this Hessenberg reduction is computed in two steps: the first one reduces the matrix to a banded Hessenberg form, and the second one further reduces it to Hessenberg form by incorporating more matrix-matrix operations in the computation. We analyse the two steps of the Hessenberg reduction problem on the external memory model (of Aggarwal and Vitter) for their I/O complexities. We propose and analyse a tile based algorithm for the first step of the reduction and show that it takes O(N-3/B min{t, root M}) I/Os. For the reduction of a banded Hessenberg matrix of bandwidth t to Hessenberg form, we propose an algorithm, which uses tight packing of bulges, and requires only O(t(2)N(2)/B + N-3/tB) I/Os. Combining the results of the two steps of the reduction, we show that the Hessenberg reduction can be performed in O(N-3/root MB) I/Os, when N is sufficiently large. To the best of our knowledge, the proposed algorithm is the first I/O optimal algorithm for Hessenberg reduction;the worst case I/O complexity matches the known lower bound of the problem.

关键词： external memory algorithms Out-of-core algorithms matrix computations Hessenberg reduction I/O efficient matrix computation

来源：评论

学校读者我要写书评

暂无评论

Space-Efficient Merging of Succinct de Bruijn Graphs 26th

Space-Efficient Merging of Succinct de Bruijn Graphs

引用

26th International Symposium on String Processing and Information Retrieval (SPIRE)

作者： Egidi, Lavinia Louza, Felipe A. Manzini, Giovanni Univ Piemonte Orientale Alessandria Italy Univ Fed Uberlandia Fac Elect Engn Uberlandia MG Brazil IIT CNR Pisa Italy

ISBN: (纸本)9783030326852;9783030326869

We propose a new algorithm for merging succinct representations of de Bruijn graphs introduced in [Bowe et al. WABI 2012]. Our algorithm is based on the lightweight BWT merging approach by Holt and McMillan [Bionformatics 2014, ACM-BCB 2014]. Our algorithm has the same asymptotic cost of the state of the art tool for the same problem presented by Muggli et al. [bioRxiv 2017, Bioinformatics 2019], but it uses less than half of its working space. A novel important feature of our algorithm, not found in any of the existing tools, is that it can compute the Variable Order succinct representation of the union graph within the same asymptotic time/space bounds.

关键词： de Bruijn graphs Succinct data structures Merging Variable-order Colored graphs external memory algorithms

来源：评论

学校读者我要写书评

暂无评论

external memory BWT and LCP computation for sequence collections with applications

引用

algorithms FOR MOLECULAR BIOLOGY 2019年第1期14卷 6-6页

作者： Egidi, Lavinia Louza, Felipe A. Manzini, Giovanni Telles, Guilherme P. Univ Piemonte Orientale DiSIT Viale Michel 11 I-15121 Alessandria Italy Univ Sao Paulo Dept Comp & Math Av Bandeirantes 3900 BR-14040901 Ribeirao Preto Brazil CNR IIT Via Moruzzi 1 I-56124 Pisa Italy Univ Estadual Campinas Inst Comp Av Albert Einstein 1251 BR-13083852 Campinas SP Brazil

BackgroundSequencing technologies produce larger and larger collections of biosequences that have to be stored in compressed indices supporting fast search operations. Many compressed indices are based on the Burrows-Wheeler Transform (BWT) and the longest common prefix (LCP) array. Because of the sheer size of the input it is important to build these data structures in external memory and time using in the best possible way the available *** propose a space-efficient algorithm to compute the BWT and LCP array for a collection of sequences in the external or semi-external memory setting. Our algorithm splits the input collection into subcollections sufficiently small that it can compute their BWT in RAM using an optimal linear time algorithm. Next, it merges the partial BWTs in external or semi-external memory and in the process it also computes the LCP values. Our algorithm can be modified to output two additional arrays that, combined with the BWT and LCP array, provide simple, scan-based, external memory algorithms for three well known problems in bioinformatics: the computation of maximal repeats, the all pairs suffix-prefix overlaps, and the construction of succinct de Bruijn *** prove that our algorithm performs O(nmaxlcp) sequential I/Os, where n is the total length of the collection and maxlcp is the maximum LCP value. The experimental results show that our algorithm is only slightly slower than the state of the art for short sequences but it is up to 40 times faster for longer sequences or when the available RAM is at least equal to the size of the input.

关键词： Burrows-Wheeler Transform Longest common prefix array Maximal repeats All pairs suffix-prefix overlaps Succinct de Bruijn graph external memory algorithms

来源：评论

学校读者我要写书评

暂无评论

An external-memory Algorithm for String Graph Construction

引用

ALGORITHMICA 2017年第2期78卷 394-424页

作者： Bonizzoni, Paola Della Vedova, Gianluca Pirola, Yuri Previtali, Marco Rizzi, Raffaella Univ Milano Bicocca DISCo Milan Italy

Some recent results (Bauer et al. in algorithms in bioinformatics, Springer, Berlin, pp 326-337, 2012;Cox et al. in algorithms in bioinformatics, Springer, Berlin, pp. 214-224, 2012;Rosone and Sciortino in The nature of computation. Logic, algorithms, applications, Springer, Berlin, pp 353-364, 2013) have introduced external-memory algorithms to compute self-indexes of a set of strings, mainly via computing the Burrows-Wheeler transform of the input strings. The motivations for those results stem from Bioinformatics, where a large number of short strings (called reads) are routinely produced and analyzed. In that field, a fundamental problem is to assemble a genome from a large set of much shorter samples extracted from the unknown genome. The approaches that are currently used to tackle this problem are memory-intensive. This fact does not bode well with the ongoing increase in the availability of genomic data. A data structure that is used in genome assembly is the string graph, where vertices correspond to samples and arcs represent two overlapping samples. In this paper we address an open problem of Simpson and Durbin (Bioinformatics 26(12):i367-i373, 2010): to design an external-memory algorithm to compute the string graph.

关键词： external memory algorithms Burrows-Wheeler transform String graphs Genome assembly

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：