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

Efficient external memory algorithms by simulating coarse-grained parallel algorithms

ALGORITHMICA 2003年第2期36卷 97-122页

作者： Dehne, F Dittrich, W Hutchinson, D Carleton Univ Sch Comp Sci Ottawa ON K1S 5B6 Canada Bosch Telecom GMBH Backnang Germany Carleton Univ Dept Syst & Comp Engn Ottawa ON K1S 5B6 Canada

external memory (EM) algorithms are designed for large-scale computational problems in which the size of the internal memory of the computer is only a small fraction of the problem size. Typical EM algorithms are specially crafted for the EM situation. In the past, several attempts have been made to relate the large body of work on parallel algorithms to EM, but with limited success. The combination of EM computing, on multiple disks, with multiprocessor parallelism has been posted as a challenge by the ACM Working Group on Storage I/O for Large-Scale Computing. In this paper we provide a simulation technique which produces efficient parallel EM algorithms from efficient BSP-like parallel algorithms. The techniques obtained can accommodate one or multiple processors on the EM target machine, each with one or more disks, and they also adapt to the disk blocking factor of the target machine. When applied to existing BSP-like algorithms, our simulation technique produces improved parallel EM algorithms for a large number of problems.

关键词： parallel algorithms coarse grained parallel computing external memory algorithms parallel I/O

来源：评论

学校读者我要写书评

暂无评论

Clustering Nodes in Large-Scale Biological Networks Using external memory algorithms

Clustering Nodes in Large-Scale Biological Networks Using Ex...

引用

11th International Conference on algorithms and Architectures for Parallel Processing (ICA3PP)

作者： Arefin, Ahmed Shamsul Inostroza-Ponta, Mario Mathieson, Luke Berretta, Regina Moscato, Pablo Univ Newcastle Ctr Bioinformat Biomarker Discovery & Informat Ba Callaghan NSW 2308 Australia Univ Santiago Chile Dept Ingn Informat Santiago Chile Macquarie Univ Fac Sci Dept Comp Sydney NSW Australia Hunter Med Res Inst Informat Based Med Program Newcastle NSW 2300 Australia ARC Ctr Excellence Bioinformat Callaghan NSW Australia

ISBN: (纸本)9783642246685

Novel analytical techniques have dramatically enhanced our understanding of many application domains including biological networks inferred from gene expression studies. However, there are clear computational challenges associated to the large datasets generated from these studies. The algorithmic solution of some NP-hard combinatorial optimization problems that naturally arise on the analysis of large networks is difficult without specialized computer facilities (i.e. supercomputers). In this work, we address the data clustering problem of large-scale biological networks with a polynomial-time algorithm that uses reasonable computing resources and is limited by the available memory. We have adapted and improved the MSTkNN graph partitioning algorithm and redesigned it to take advantage of external memory (EM) algorithms. We evaluate the scalability and performance of our proposed algorithm on a well-known breast cancer microarray study and its associated dataset.

关键词： Data clustering external memory algorithms graph algorithms gene expression data analysis

来源：评论

学校读者我要写书评

暂无评论

Random Access on Narrow Decision Diagrams in external memory 30th

Random Access on Narrow Decision Diagrams in External Memory

引用

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

来源：评论

学校读者我要写书评

暂无评论

A survey of practical algorithms for suffix tree construction in external memory

引用

SOFTWARE-PRACTICE & EXPERIENCE 2010年第11期40卷 965-988页

作者： Barsky, M. Stege, U. Thomo, A. Univ Victoria STN CSC Victoria Victoria BC V8W 3P6 Canada

The construction of suffix trees in secondary storage was considered impractical due to its excessive I/O cost. algorithms developed in the last decade show that a suffix tree can efficiently be built in secondary storage for inputs which fit the main memory. In this paper, we analyze the details of algorithmic approaches to the external memory suffix tree construction and compare the performance and scalability of existing state-of-the-art software based on these algorithms. Copyright (C) 2010 John Wiley & Sons, Ltd.

关键词： suffix tree external memory algorithms string index

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Approximate Range Searching in external memory

引用

ALGORITHMICA 2011年第2期59卷 115-128页

作者： Streppel, Micha Yi, Ke HKUST Dept Comp Sci & Engn Kowloon Hong Kong Peoples R China NCIM Grp Eindhoven Netherlands

In this paper, we present two linear-size external memory data structures for approximate range searching. Our first structure, the BAR-B-tree, stores a set of N points in a"e (d) and can report all points inside a query range Q by accessing O(log (B) N+epsilon (gamma) +k (epsilon) /B) disk blocks, where B is the disk block size, gamma=1-d for convex queries and gamma=-d otherwise, and k (epsilon) is the number of points lying within a distance of epsilon a <...diam (Q) to the query range Q. Our second structure, the object-BAR-B-tree, is able to store objects of arbitrary shapes of constant complexity and provides similar query guarantees. In addition, both structures can support other types of range searching queries such as range aggregation and nearest-neighbor. Finally, we present I/O-efficient algorithms to build these structures.

关键词： Approximate range searching external memory algorithms

来源：评论

学校读者我要写书评

暂无评论

Efficient external memory structures for range-aggregate queries

引用

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 2013年第3期46卷 358-370页

作者： Agarwal, Pankaj K. Arge, Lars Govindarajan, Sathish Yang, Jun Yi, Ke HKUST Dept Comp Sci & Engn Hong Kong Hong Kong Peoples R China Duke Univ Dept Comp Sci Durham NC 27708 USA Aarhus Univ Dept Comp Sci MADALGO Ctr Mass Data Algorithm DK-8000 Aarhus Denmark Indian Inst Sci CSA Dept Bangalore 560012 Karnataka India

We present external memory data structures for efficiently answering range-aggregate queries. The range-aggregate problem is defined as follows: Given a set of weighted points in R-d, compute the aggregate of the weights of the points that lie inside a d-dimensional orthogonal query rectangle. The aggregates we consider in this paper include COUNT, sum, and MAX. First, we develop a structure for answering two-dimensional range-COUNT queries that uses O(N/B) disk blocks and answers a query in O(log(B) N) I/Os, where N is the number of input points and B is the disk block size. The structure can be extended to obtain a near-linear-size structure for answering range-sum queries using O(log(B) N) I/Os, and a linear-size structure for answering range-MAX queries in O(log(B)(2) N) I/Os. Our structures can be made dynamic and extended to higher dimensions. (C) 2012 Elsevier B.V. All rights reserved.

关键词： external memory algorithms Range-aggregation Data structures

来源：评论

学校读者我要写书评

暂无评论

RAM-Efficient external memory Sorting

引用

ALGORITHMICA 2015年第4期73卷 623-636页

作者： Arge, Lars Thorup, Mikkel Aarhus Univ Dept Comp Sci Ctr Mass Data Algorithm MADALGO DK-8000 Aarhus Denmark Univ Copenhagen Dept Comp Sci Copenhagen Denmark

In recent years a large number of problems have been considered in external memory models of computation, where the complexity measure is the number of blocks of data that are moved between slow external memory and fast internal memory (also called I/Os). In practice, however, internal memory time often dominates the total running time once I/O-efficiency has been obtained. In this paper we initiate a study of algorithms for fundamental problems that are simultaneously I/O-efficient and internal memory efficient in the RAM model of computation. For sorting the conventional wisdom is to use merging base algorithms in external memory but we describe how this leads to suboptimal RAM performance. However, by using a splitting based algorithm in combination with existing RAM sorting techniques we obtain a sorting algorithm that is both I/O and RAM model efficient. Furthermore, we design an I/O- and RAM-efficient priority queue. Finally, we prove a sorting lower bound that shows that in most cases our results are optimal both in terms of I/O and internal computation.

关键词： I/O algorithms RAM algorithms external memory algorithms Sorting Priority queue

来源：评论

学校读者我要写书评

暂无评论

Optimal external memory Planar Point Enclosure

引用

ALGORITHMICA 2009年第3期54卷 337-352页

作者： Arge, Lars Samoladas, Vasilis Yi, Ke Univ Aarhus MADALGO Dept Comp Sci Aarhus Denmark Tech Univ Crete Dept Elect & Comp Engn Khania Greece Hong Kong Univ Sci & Technol Dept Comp Sci & Engn Kowloon Hong Kong Peoples R China

In this paper we study the external memory planar point enclosure problem: Given N axis-parallel rectangles in the plane, construct a data structure on disk (an index) such that all K rectangles containing a query point can be reported I/O-efficiently. This problem has important applications in e.g. spatial and temporal databases, and is dual to the important and well-studied orthogonal range searching problem. Surprisingly, despite the fact that the problem can be solved optimally in internal memory with linear space and O(log N+K) query time, we show that one cannot construct a linear sized external memory point enclosure data structure that can be used to answer a query in O(log (B) N+K/B) I/Os, where B is the disk block size. To obtain this bound, Omega(N/B (1-epsilon) ) disk blocks are needed for some constant epsilon > 0. With linear space, the best obtainable query bound is O(log (2) N+K/B) if a linear output term O(K/B) is desired. To show this we prove a general lower bound on the tradeoff between the size of the data structure and its query cost. We also develop a family of structures with matching space and query bounds.

关键词： external memory algorithms Point enclosure Data structures

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：