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

Parallel implementation of the finite element method using compressed data structures

COMPUTATIONAL MECHANICS 2007年第1期41卷 31-48页

作者： Ribeiro, F. L. B. Ferreira, I. A. Univ Fed Rio de Janeiro COPPE Programa Engn Civil BR-21945970 Rio De Janeiro Brazil

This paper presents a parallel implementation of the finite element method designed for coarse-grain distributed memory architectures. The MPI standard is used for message passing and tests are run on a PC cluster and on an SGI Altix 350. compressed data structures are employed to store the coefficient matrix and obtain iterative solutions, based on Krylov methods, in a subdomain-by-subdomain approach. Two mesh partitioning schemes are compared: non-overlapping and overlapping. The pros and cons of these partitioning methods are discussed. Numerical examples of symmetric and non-symmetric problems in two and three dimensions are presented.

关键词： parallel computing message passing interface compressed data structures finite element method

来源：评论

学校读者我要写书评

暂无评论

Computing MEMs and Relatives on Repetitive Text Collections

引用

ACM TRANSACTIONS ON ALGORITHMS 2025年第1期21卷 1-33页

作者： Navarro, Gonzalo Univ Chile Ctr Biotechnol & Bioengn CeBiB Dept Comp Sci Beauchef 851 Santiago Chile

We consider the problem of computing the Maximal Exact Matches (MEMs) of a given pattern P[1..m] on a large repetitive text collection T[1..n] over an alphabet of size sigma, which is represented as a (hopefully much smaller) run-length context-free grammar of size g(rl). We show that the problem can be solved in time O(m(2) log(is an element of) n), for any constant is an element of > 0, on a data structure of size O(g(rl)). Further, on a locally consistent grammar r of size O(delta log n log sigma/delta log n), the time decreases to O(mlog m(log m+log (is an element of) n)). The value delta is a function of the substring complexity of T and Omega(delta log n log sigma/delta log n) a tight lower bound on the compressibility of repetitive texts T, so our structure has optimal size in terms of n, sigma, and 8. We extend our results to several related problems, such as finding k-MEMs, MUMs, rare MEMs, and applications.

关键词： Repetitive texts Substring complexity Grammar compression Locally consistent parsing compressed data structures MEMs MUMs

来源：评论

学校读者我要写书评

暂无评论

A Learned Approach to Design compressed Rank/Select data structures

引用

ACM TRANSACTIONS ON ALGORITHMS 2022年第3期18卷 24-24页

作者： Boffa, Antonio Ferragina, Paolo Vinciguerra, Giorgio Univ Pisa Largo Bruno Pontecorvo 3 I-56127 Pisa Italy

We address the problem of designing, implementing, and experimenting with compressed data structures that support rank and select queries over a dictionary of integers. We shine a new light on this classical problem by showing a connection between the input integers and the geometry of a set of points in a Cartesian plane suitably derived from them. We then build upon some results in computational geometry to introduce the first compressed rank/select dictionary based on the idea of "learning" the distribution of such points via proper linear approximations (LA). We therefore call this novel data structure the la_vector. We prove time and space complexities of the la_vector in several scenarios: in the worst case, in the case of input distributions with finite mean and variance, and taking into account the kth order entropy of some of its building blocks. We also discuss improved hybrid data structures, namely, ones that suitably orchestrate known compressed rank/select dictionaries with the la_vector. We corroborate our theoretical results with a large set of experiments over datasets originating from a variety of applications (Web search, DNAsequencing, information retrieval, and natural language processing) and show that our approach provides new interesting space-time tradeoffs with respect to many well-established compressed rank/select dictionary implementations. In particular, we show that our select is the fastest, and our rank is on the space-time Pareto frontier.

关键词： compressed data structures rank/select dictionaries piecewise linear approximations high order entropy algorithm engineering

来源：评论

学校读者我要写书评

暂无评论

Entropy-bounded representation of point grids

引用

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 2014年第1期47卷 1-14页

作者： Farzan, Arash Gagie, Travis Navarro, Gonzalo Aalto Univ Dept Comp Sci Helsinki Finland Univ Chile Dept Comp Sci Santiago Chile

We give the first fully compressed representation of a set of m points on an n x n grid, taking H + o(H) bits of space, where H = lg ((n2)(m)) is the entropy of the set. This representation supports range counting, range reporting, and point selection queries, with complexities that go from O(1) to O(lg(2) n/lg lg n) per answer as the entropy of the grid decreases. Operating within entropy-bounded space, as well as relating time complexity with entropy, opens a new line of research on an otherwise well-studied area. (C) 2013 Elsevier B.V. All rights reserved.

关键词： compressed data structures Geometric grids Range queries

来源：评论

学校读者我要写书评

暂无评论

Range Majorities and Minorities in Arrays

引用

ALGORITHMICA 2021年第6期83卷 1707-1733页

作者： Belazzougui, Djamal Gagie, Travis Munro, J. Ian Navarro, Gonzalo Nekrich, Yakov Res Ctr Tech & Sci Informat CERIST Algiers Algeria Dalhousie Univ Fac Comp Sci Halifax NS Canada Univ Waterloo David Cheriton Sch Comp Sci Waterloo ON Canada Univ Chile Dept Comp Sci Millennium Inst Fdn Res Data Santiago Chile Michigan Technol Univ Dept Comp Sci Houghton MI 49931 USA

The problem of parameterized range majority asks us to preprocess a string of length n such that, given the endpoints of a range, one can quickly find all the distinct elements whose relative frequencies in that range are more than a threshold tau. This is a more tractable version of the classical problem of finding the range mode, which is unlikely to be solvable in polylogarithmic time and linear space. In this paper we give the first linear-space solution with optimal O(1/tau) query time, even when tau can be specified with the query. We then consider data structures whose space is bounded by the entropy of the distribution of the symbols in the sequence. For the case when the alphabet size sigma is polynomial on the computer word size, we retain the optimal time within optimally compressed space (i.e., with sublinear redundancy). Otherwise, either the compressed space is increased by an arbitrarily small constant factor or the time rises to any function in (1 /tau) . omega(1). We obtain the same results on the complementary problem of parameterized range minority.

关键词： compressed data structures Range majority and minority Range mode

来源：评论

学校读者我要写书评

暂无评论

Algorithms and Complexity on Indexing Founder Graphs

引用

ALGORITHMICA 2023年第6期85卷 1586-1623页

作者： Equi, Massimo Norri, Tuukka Alanko, Jarno Cazaux, Bastien Tomescu, Alexandru, I Makinen, Veli Univ Helsinki Dept Comp Sci POB 68Pietari Kalmin Katu 5 Helsinki 00014 Finland Dalhousie Univ Fac Comp Sci POB 150006050 Univ Ave Halifax NS Canada Univ Montpellier CNRS LIRMM LIRMM UMR 5506 CC477161 Rue Ada F-34095 Montpellier 5 France

We study the problem of matching a string in a labeled graph. Previous research has shown that unless the Orthogonal Vectors Hypothesis (OVH) is false, one cannot solve this problem in strongly sub-quadratic time, nor index the graph in polynomial time to answer queries efficiently (Equi et al. ICALP 2019, SOFSEM 2021). These conditional lower-bounds cover even deterministic graphs with binary alphabet, but there naturally exist also graph classes that are easy to index: For example, Wheeler graphs (Gagie et al. Theor. Comp. Sci. 2017) cover graphs admitting a Burrows-Wheeler transform -based indexing scheme. However, it is NP-complete to recognize if a graph is a Wheeler graph (Gibney, Thankachan, ESA 2019). We propose an approach to alleviate the construction bottleneck of Wheeler graphs. Rather than starting from an arbitrary graph, we study graphs induced from multiple sequence alignments (MSAs). Elastic degenerate strings (Bernadini et al. SPIRE 2017, ICALP 2019) can be seen as such graphs, and we introduce here their generalization: elastic founder graphs. We first prove that even such induced graphs are hard to index under OVH. Then we introduce two subclasses, repeat-free and semi-repeat-free graphs, that are easy to index. We give a linear time algorithm to construct a repeat-free (non-elastic) founder graph from a gapless MSA, and (parameterized) near-linear time algorithms to construct a semi-repeat-free (repeat-free, respectively) elastic founder graph from general MSA. Finally, we show that repeat-free founder graphs admit a reduction to Wheeler graphs in polynomial time.

关键词： Graph algorithms Computational complexity compressed data structures String matching Multiple sequence alignment Segmentation algorithms Pangenomics

来源：评论

学校读者我要写书评

暂无评论

Algorithms to compute the Burrows-Wheeler Similarity Distribution

引用

THEORETICAL COMPUTER SCIENCE 2019年第0期782卷 145-156页

作者： Louza, Felipe A. Telles, Guilherme P. Gog, Simon Zhao, Liang Univ Sao Paulo Dept Comp & Math Ribeirao Preto Brazil Univ Estadual Campinas Inst Comp Campinas SP Brazil eBay Inc San Jose CA USA

The Burrows-Wheeler transform (BWT) is a well studied text transformation widely used in data compression and text indexing. The BWT of two strings can also provide similarity measures between them, based on the observation that the more their symbols are intermixed in the transformation, the more the strings are similar. In this article we present two new algorithms to compute similarity measures based on the BWT for string collections. In particular, we present practical and theoretical improvements to the computation of the Burrows-Wheeler Similarity Distribution for all pairs of strings in a collection. Our algorithms take advantage of the BWT computed for the concatenation of all strings, and use compressed data structures that allow reducing the running time with a small memory footprint, as shown by a set of experiments with real and artificial datasets. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Burrows-Wheeler transform String similarity String collections compressed data structures Parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

Practical compressed string dictionaries

引用

INFORMATION SYSTEMS 2016年第Mar.期56卷 73-108页

作者： Martinez-Prieto, Miguel A. Brisaboa, Nieves Canovas, Rodrigo Claude, Francisco Navarro, Gonzalo Univ Valladolid Dept Comp Sci DataWeb Res E-47002 Valladolid Spain Univ A Coruna Database Lab La Coruna Spain Univ Melbourne Dept Comp & Informat Syst CIS NICTA Victoria Res Lab Melbourne Vic 3010 Australia Univ Diego Portales Escuela Informat & Telecomunicac Santiago Chile Univ Chile Dept Comp Sci CeBiB Ctr Biotechnol & Bioengn Santiago Chile

The need to store and query a set of strings - a string dictionary - arises in many kinds of applications. While classically these string dictionaries have accounted for a small share of the total space budget (e.g., in Natural Language Processing or when indexing text collections), recent applications in Web engines, Semantic Web (RDF) graphs, Bioinformatics, and many others handle very large string dictionaries, whose size is a significant fraction of the whole data. In these cases, string dictionary management is a scalability issue by itself. This paper focuses on the problem of managing large static string dictionaries in compressed main memory space. We revisit classical solutions for string dictionaries like hashing, tries, and front-coding, and improve them by using compression techniques. We also introduce some novel string dictionary representations built on top of recent advances in succinct data structures and full-text indexes. All these structures are empirically compared on a heterogeneous testbed formed by real-world string dictionaries. We show that the compressed representations may use as little as 5% of the original dictionary size, while supporting lookup operations within a few microseconds. These numbers outperform the state-of-the-art space/time tradeoffs in many cases. Furthermore, we enhance some representations to provide prefix- and substring-based searches, which also perform competitively. The results show that compressed string dictionaries are a useful building block for various data-intensive applications in different domains. (C) 2015 Elsevier Ltd. All rights reserved.

关键词： compressed string dictionaries Text processing Text databases compressed data structures

来源：评论

学校读者我要写书评

暂无评论

Rank/select on dynamic compressed sequences and applications

引用

THEORETICAL COMPUTER SCIENCE 2009年第43期410卷 4414-4422页

作者： Gonzalez, Rodrigo Navarro, Gonzalo Univ Chile Dept Comp Sci Santiago Chile

Operations rank and select over a sequence of symbols have many applications to the design of succinct and compressed data structures managing text collections, structured text, binary relations, trees, graphs, and so on. We are interested in the case where the collections can be updated via insertions and deletions of symbols. Two current solutions stand out as the best in the tradeoff of space versus time (when considering all the operations). One solution, by Makinen and Navarro, achieves compressed space (i.e., nH(0) + o(n log sigma) bits) and O(log n log sigma) worst-case time for all the operations, where n is the sequence length, sigma is the alphabet size, and H-0 is the zero-order entropy of the sequence. The other solution, by Lee and Park, achieves O(log n(1 + log sigma/log log n)) amortized time and uncompressed space, i.e. n log(2) sigma + O(n) + o(n log sigma) bits. In this paper we show that the best of both worlds can be achieved. We combine the solutions to obtain nH(0) + o(n log sigma) bits of space and O(log n(1 + log sigma/log log n)) worst-case time for all the operations. Apart from the best current solution to the problem, we obtain several byproducts of independent interest applicable to partial sums, text indexes, suffix arrays, the Burrows-Wheeler transform, and others. (C) 2009 Elsevier B.V. All rights reserved.

关键词： compressed data structures Empirical entropy Text indexing

来源：评论

学校读者我要写书评

暂无评论

Faster entropy-bounded compressed suffix trees

引用

THEORETICAL COMPUTER SCIENCE 2009年第51期410卷 5354-5364页

作者： Fischer, Johannes Makinen, Veli Navarro, Gonzalo Univ Chile Dept Comp Sci Santiago Chile Univ Helsinki Dept Comp Sci FIN-00014 Helsinki Finland Univ Tubingen Ctr Bioinformat ZBIT D-72074 Tubingen Germany

Suffix trees are among the most important data structures in stringology, with a number of applications in flourishing areas like bioinformatics. Their main problem is space usage, which has triggered much research striving for compressed representations that are still functional. A smaller suffix tree representation could fit in a faster memory, outweighing by far the theoretical slowdown brought by the space reduction. We present a novel compressed suffix tree, which is the first achieving at the same time sublogarithmic complexity for the operations, and space usage that asymptotically goes to zero as the entropy of the text does. The main ideas in our development are compressing the longest common prefix information, totally getting rid of the suffix tree topology, and expressing all the suffix tree operations using range minimum queries and a novel primitive called next/previous smaller value in a sequence. Our solutions to those operations are of independent interest. (C) 2009 Elsevier B.V. All rights reserved.

关键词： Suffix trees compressed data structures Range minimum queries

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：