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

Optimal Sparse Matrix Dense Vector Multiplication in the I/O-Model

THEORY OF COMPUTING SYSTEMS 2010年第4期47卷 934-962页

作者： Bender, Michael A. Brodal, Gerth Stolting Fagerberg, Rolf Jacob, Riko Vicari, Elias Tech Univ Munich Dept Comp Sci Munich Germany SUNY Stony Brook Dept Comp Sci Stony Brook NY 11794 USA Aarhus Univ Dept Comp Sci MADALGO DK-8000 Aarhus Denmark Univ So Denmark Dept Math & Comp Sci Odense Denmark ETH Inst Theoret Comp Sci CH-8092 Zurich Switzerland

We study the problem of sparse-matrix dense-vector multiplication (SpMV) in external memory. The task of SpMV is to compute y :=Ax, where A is a sparse N x N matrix and x is a vector. We express sparsity by a parameter k, and for each choice of k consider the class of matrices where the number of nonzero entries is kN, i.e., where the average number of nonzero entries per column is k. We investigate what is the external worst-case complexity, i.e., the best possible upper bound on the number of I/Os, as a function of k, N and the parameters M (memory size) and B (track size) of the I/O-model. We determine this complexity up to a constant factor for all meaningful choices of these parameters, as long as k <= signN(1-epsilon) , where epsilon depends on the problem variant. Our model of computation for the lower bound is a combination of the I/O-models of Aggarwal and Vitter, and of Hong and Kung. We study variants of the problem, differing in the memory layout of A. If A is stored in column major layout, we prove that SpMV has I/O complexity Theta (min{kN/B max{1, log(M/B) N/max{k,M}}, kN}) for k <= N1-epsilon and any constant 0 < epsilon < 1. If the algorithm can choose the memory layout, the I/O complexity reduces to Theta(min{kN/B max{1, log(M/B) N/kM}, kN}) for k <= 3 root N. In contrast, if the algorithm must be able to handle an arbitrary layout of the matrix, the I/O complexity is Theta (min{kN/B max{1, log(M/B) N/M}, kN}) for k <= N/2. In the cache oblivious setting we prove that with tall cache assumption M >= B1+epsilon, the I/O complexity is O(kN/B max{1, log(M/B) N/max{k, M}}) for A in column major layout.

关键词： I/O-model external memory algorithms Lower bound Sparse matrix dense vector multiplication

来源：评论

学校读者我要写书评

暂无评论

I/O-Efficient Path Traversal in Succinct Planar Graphs

引用

ALGORITHMICA 2017年第3期77卷 714-755页

作者： Dillabaugh, Craig He, Meng Maheshwari, Anil Zeh, Norbert Carleton Univ Sch Comp Sci 5302 HP1125 Colonel By Dr Ottawa ON K1S 5B6 Canada Dalhousie Univ Fac Comp Sci 6050 Univ AvePOB 15000 Halifax NS B3H 4R2 Canada Dalhousie Univ Fac Comp Sci 6050 Univ Ave Halifax NS B3H 1W5 Canada

We present a technique for representing bounded-degree planar graphs in a succinct fashion while permitting I/O-efficient traversal of paths. Using our representation, a graph with N vertices, (In this paper denotes ) each with an associated key of bits, can be stored in bits and traversing a path of length K takes I/Os, where B denotes the disk block size. By applying our construction to the dual of a terrain represented as a triangular irregular network, we can represent the terrain in the above space bounds and support path traversals on the terrain using I/Os, where K is the number of triangles visited by the path. This is useful for answering a number of queries on the terrain, such as reporting terrain profiles, trickle paths, and connected components.

关键词： external memory algorithms Path traversal Planar graphs Succinct data structures

来源：评论

学校读者我要写书评

暂无评论

Metric space similarity joins

引用

ACM TRANSACTIONS ON DATABASE SYSTEMS 2008年第2期33卷 49-86页

作者： Jacox, Edwin H. Samet, Hanan Univ Maryland Dept Comp Sci Ctr Automat Res College Pk MD 20742 USA Univ Maryland Inst Adv Comp Studies College Pk MD 20742 USA

Similarity join algorithms find pairs of objects that lie within a certain distance epsilon of each other. algorithms that are adapted from spatial join techniques are designed primarily for data in a vector space and often employ some form of a multidimensional index. For these algorithms, when the data lies in a metric space, the usual solution is to embed the data in vector space and then make use of a multidimensional index. Such an approach has a number of drawbacks when the data is high dimensional as we must eventually find the most discriminating dimensions, which is not trivial. In addition, although the maximum distance between objects increases with dimension, the ability to discriminate between objects in each dimension does not. These drawbacks are overcome via the introduction of a new method called Quickjoin that does not require a multidimensional index and instead adapts techniques used in distance-based indexing for use in a method that is conceptually similar to the Quicksort algorithm. A formal analysis is provided of the Quickjoin method. Experiments show that the Quickjoin method significantly outperforms two existing techniques.

关键词： algorithms performance similarity join external memory algorithms distance-based indexing nearest neighbor queries range queries ranking

来源：评论

学校读者我要写书评

暂无评论

Efficient sampling of random permutations

引用

JOURNAL OF DISCRETE algorithms 2008年第1期6卷 125-139页

作者： Gustedt, Jens INRIA Lorraine Villers les Nancy France LORIA Villers les Nancy France

We show how to uniformly distribute data at random (not to be confounded with permutation routing) in two settings that are able to deal with massive data: coarse grained parallelism and external memory. In contrast to previously known work for parallel setups, our method is able to fulfill the three criteria of uniformity, work-optimality and balance among the processors simultaneously. To guarantee the uniformity we investigate the matrix of communication requests between the processors. We show that its distribution is a generalization of the multivariate hypergeometric distribution and we give algorithms to sample it efficiently in the two settings. (C) 2006 Elsevier B.V. All rights reserved.

关键词： Random permutations Random shuffling Coarse grained parallelism external memory algorithms Uniformly generated communication matrix

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

external memory Layout vs. Schematic

引用

ACM TRANSACTIONS ON DESIGN AUTOMATION OF ELECTRONIC SYSTEMS 2009年第2期14卷 1–20页

作者： Kumar, Yokesh Gupta, Prosenjit Univ Minnesota Minneapolis MN 55455 USA

The circuit represented by a VLSI layout must be verified by checking it against the schematic circuit as an important part of the functional verification step. This involves two central problems of matching the circuit graphs with each other (graph isomorphism) and extracting a higher level of circuit from a given level by finding subcircuits in the circuit graph (subgraph isomorphism). Modern day VLSI layouts contain millions of devices. Hence the memory requirements of the data structures required by tools for verifying them become huge and can easily exceed the amount of internal memory available on a computer. In such a scenario, a program not aware of the memory hierarchy performs badly because of its unorganized input/output operations (I/Os) as the speed of a disk access is about a million times slower than accessing a main memory location. In this article, we present I/O-efficient algorithms for the graph isomorphism and subgraph isomorphism problems in the context of verification of VLSI layouts. Experimental results show the need and utility of I/O-efficient algorithms for handling problems with large memory requirements.

关键词： algorithms Verification Graph subgraph isomorphism external memory algorithms verification of layouts design automation

来源：评论

学校读者我要写书评

暂无评论

Generalized enhanced suffix array construction in external memory

引用

algorithms FOR MOLECULAR BIOLOGY 2017年第1期12卷 26-26页

作者： Louza, Felipe A. Telles, Guilherme P. Hoffmann, Steve Ciferri, Cristina D. A. Univ Sao Paulo Dept Comp & Math Av Bandeirantes 3900 BR-14040901 Ribeirao Preto Brazil Univ Estadual Campinas Inst Comp Av Albert Einstein 1251 BR-13083852 Campinas SP Brazil Fritz Lipman Inst Leibniz Inst Aging Computat Biol Beutenbergstr 11 D-07745 Jena Germany Friedrich Schiller Univ Jena Beutenbergstr 11 D-07745 Jena Germany Univ Sao Paulo Inst Math & Comp Sci Av Trabalhador Sao Carlense 400 BR-13560970 Sao Carlos SP Brazil

Background: Suffix arrays, augmented by additional data structures, allow solving efficiently many string processing problems. The external memory construction of the generalized suffix array for a string collection is a fundamental task when the size of the input collection or the data structure exceeds the available internal memory. Results: In this article we present and analyze eGSA [introduced in CPM (external memory generalized suffix and LCP arrays construction. In: Proceedings of CPM. pp 201-10, 2013)], the first external memory algorithm to construct generalized suffix arrays augmented with the longest common prefix array for a string collection. Our algorithm relies on a combination of buffers, induced sorting and a heap to avoid direct string comparisons. We performed experiments that covered different aspects of our algorithm, including running time, efficiency, external memory access, internal phases and the influence of different optimization strategies. On real datasets of size up to 24 GB and using 2 GB of internal memory, eGSA showed a competitive performance when compared to eSAIS and SAscan, which are efficient algorithms for a single string according to the related literature. We also show the effect of disk caching managed by the operating system on our algorithm. Conclusions: The proposed algorithm was validated through performance tests using real datasets from different domains, in various combinations, and showed a competitive performance. Our algorithm can also construct the generalized Burrows-Wheeler transform of a string collection with no additional cost except by the output time.

关键词： Suffix array LCP array Burrows-Wheeler transform external memory algorithms String collections

来源：评论

学校读者我要写书评

暂无评论

Optimal Sparse Matrix Dense Vector Multiplication in the I/O-Model 07

Optimal Sparse Matrix Dense Vector Multiplication in the I/O...

引用

19th Annual Symposium on Parallelism in algorithms and Architectures

作者： Bender, Michael A. Brodal, Gerth Stolting Fagerberg, Rolf Jacob, Riko Vicari, Elias SUNY Stony Brook Dept Comp Sci Stony Brook NY 11794 USA Univ Aarhus Danish Natl Res Fdn DK-8000 Aarhus C Denmark Univ Southern Denmark Dept Math & Comp Sci DK-5230 Odense Denmark ETH Inst Theoret Comp Sci CH-8092 Zurich Switzerland

ISBN: (纸本)9781595936677

We analyze the problem of sparse-matrix dense-vector multiplication (SpMV) in the I/O-model. The task of SpMV is to compute y := Ax, where A is a sparse N x N matrix and x and y are vectors. Here, sparsity is expressed by the parameter k that states that A has a total of at most kN nonzeros, i.e., an average number of k nonzeros per column. The extreme choices for parameter k are well studied special cases, namely for k = 1 permuting and for k = N dense matrix-vector multiplication. We study the worst-case complexity of this computational task, i.e., what is the best possible upper bound on the number of I/Os depending on k and N only. We determine this complexity up to a constant factor for large ranges of the parameters. By our arguments, we find that most matrices with kN nonzeros require this number of I/Os, even if the program may depend on the structure of the matrix. The model of computation for the lower bound is a combination of the I/O-models of Aggarwal and Vitter, and of Hong and Kung. We study two variants of the problem, depending on the memory layout of A. If A is stored in column major layout, SpMV has I/O complexity circle minus(min {kN/B (1 + log(M/B) N/(max){M,k}), kN}) for k <= N1-epsilon and any constant 1 > epsilon > 0. If the algorithm can choose the memory layout, the I/O complexity of SpMV is circle minus(min {kN/B (1 + log(M/B) N/kM), kN}) for k <= (3)root N. In the cache oblivious setting with tall cache assumption M >= B1+epsilon, the I/O complexity is O (kN/B (1 + log(M/B) N/k)) for A in column major layout.

关键词： I/O-Model external memory algorithms Lower Bound Sparse Matrix Dense Vector Multiplication

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Matrix zoom: A visual interface to semi-external graphs

Matrix zoom: A visual interface to semi-external graphs

引用

10th Annual IEEE Symposium on Information Visualization (InfoVis 2004)

作者： Abello, J van Ham, F Rutgers State Univ DIMACS Piscataway NJ 08855 USA

ISBN: (纸本)0780387791

In web data, telecommunications traffic and in epidemiological studies, dense subgraphs correspond to subsets of subjects (i.e. users, patients) that share a collection of attributes values (i.e. accessed web pages, email-calling patterns or disease diagnostic profiles). Visual and computational identification of these "clusters" becomes useful when domain experts desire to determine those factors of major influence in the formation of access and communication clusters or in the detection and contention of disease spread. With the current increases in graphic hardware capabilities and RAM sizes, it is more useful to relate graph sizes to the available screen real estate S and the amount of available RAM M, instead of the number of edges or nodes in the graph. We offer a visual interface that is parameterized by M and S and is particularly suited for navigation tasks that require the identification of subgraphs whose edge density is above certain threshold. This is achieved by providing a zoomable matrix view of the underlying data. This view is strongly coupled to a hierarchical view of the essential information elements present in the data domain. We illustrate the applicability of this work to the visual navigation of cancer incidence data and to an aggregated sample of phone call traffic.

关键词： graph visualization hierarchy trees clustering external memory algorithms cancer data phone traffic

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：