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

24th International Workshop on algorithms in Bioinformatics, WABI 2024

作者： Zentgraf, Jens Rahmann, Sven Algorithmic Bioinformatics Department of Computer Science Saarland University Saarbrücken Germany Center for Bioinformatics Saar Saarland Informatics Campus Saarbrücken Germany Graduate School of Computer Science Saarland Informatics Campus Saarbrücken Germany

ISBN: (纸本)9783959773409

Motivation. Short DNA sequences of length k that appear in a single location (e.g., at a single genomic position, in a single species from a larger set of species, etc.) are called unique k-mers. They are useful for placing sequenced DNA fragments at the correct location without computing alignments and without ambiguity. However, they are not necessarily robust: A single basepair change may turn a unique k-mer into a different one that may in fact be present at one or more different locations, which may give confusing or contradictory information when attempting to place a read by its k-mer content. A more robust concept are strongly unique k-mers, i.e., unique k-mers for which no Hamming-distance-1 neighbor with conflicting information exists in all of the considered sequences. Given a set of k-mers, it is therefore of interest to have an efficient method that can distinguish k-mers with a Hamming-distance-1 neighbor in the collection from those that do not. Results. We present engineered algorithms to identify and mark within a set K of (canonical) k-mers all elements that have a Hamming-distance-1 neighbor in the same set. One algorithm is based on recursively running a 4-way comparison on sub-intervals of the sorted set. The other algorithm is based on bucketing and running a pairwise bit-parallel Hamming distance test on small buckets of the sorted set. Both methods consider canonical k-mers (i.e., taking reverse complements into account) and allow for efficient parallelization. The methods have been implemented and applied in practice to sets consisting of several billions of k-mers. An optimized combined approach running with 16 threads on a 16-core workstation, yields wall-clock running times below 20 seconds on the 2.5 billion distinct 31-mers of the human telomere-to-telomere reference genome. Availability. An implementation can be found at https://***/rahmannlab/strong-kmers. © Jens Zentgraf and Sven Rahmann

关键词： algorithm engineering Hamming distance k-mer parallelization strong uniqueness

来源：评论

学校读者我要写书评

暂无评论

A practical approach to generating route sketches 2

A practical approach to generating route sketches

引用

2nd ACM SIGSPATIAL International Workshop on MapInteraction, MapInteract 2014

作者： Luxen, Dennis Niklaus, Patrick Mapbox Inc. 1714 14th St NW Rear Entrance WashingtonDC20009 United States Karlsruhe Institute of Technology Am Fasanengarten 5 Karlsruhe76128 Germany

ISBN: (纸本)9781450331418

Online mapping and navigation services are a corner stone of the World Wide Web. While automatically generated car directions have gone from static data to user-specific customizations, automatically generated route guidance has stayed very much the same. And as such, it doesn't necessarily reflect the complexity of turns and may also be hard to use while traveling. We report on a practical and efficient technique for computing and presenting generalizations of routes, so-called sketches that compress a route and its guidance into an easy to comprehend and usable form by non-uniformly scaling and generalizing certain parts of the route. Our work draws from a sound theoretical foundation, is easy to implement, and gives very good results in practice.

关键词： algorithm engineering Graph algorithm Route sketches

来源：评论

学校读者我要写书评

暂无评论

Fast deterministic selection 16

Fast deterministic selection

引用

16th Symposium on Experimental algorithms, SEA 2017

作者： Alexandrescu, Andrei D Language Foundation Washington United States

ISBN: (纸本)9783959770361

The selection problem, in forms such as finding the median or choosing the k top ranked items in a dataset, is a core task in computing with numerous applications in fields as diverse as statistics, databases, Machine Learning, finance, biology, and graphics. The selection algorithm Median of Medians, although a landmark theoretical achievement, is seldom used in practice because it is slower than simple approaches based on sampling. The main contribution of this paper is a fast linear-time deterministic selection algorithm MCEDIANOFNINTHERS based on a refined definition of MEDIANOFMEDIANS. A complementary algorithm MEDIANOFEXTREMA is also proposed. These algorithms work together to solve the selection problem in guaranteed linear time, faster than state-of-the-art baselines, and without resorting to randomization, heuristics, or fallback approaches for pathological cases. We demonstrate results on uniformly distributed random numbers, typical low-entropy artificial datasets, and real-world data. Measurements are opensourced alongside the implementation at https://***/andralex/MedianOfNinthers. © Andrei Alexandrescu.

关键词： algorithm engineering algorithmic libraries Median of Medians Quickselect Selection problem

来源：评论

学校读者我要写书评

暂无评论

Parallel computation of combinatorial symmetries 29

Parallel computation of combinatorial symmetries

引用

29th Annual European Symposium on algorithms, ESA 2021

作者： Anders, Markus Schweitzer, Pascal TU Darmstadt Germany

ISBN: (纸本)9783959772044

In practice symmetries of combinatorial structures are computed by transforming the structure into an annotated graph whose automorphisms correspond exactly to the desired symmetries. An automorphism solver is then employed to compute the automorphism group of the constructed graph. Such solvers have been developed for over 50 years, and highly efficient sequential, single core tools are available. However no competitive parallel tools are available for the task. We introduce a new parallel randomized algorithm that is based on a modification of the individualization-refinement paradigm used by sequential solvers. The use of randomization crucially enables parallelization. We report extensive benchmark results that show that our solver is competitive to state-of-the-art solvers on a single thread, while scaling remarkably well with the use of more threads. This results in order-of-magnitude improvements on many graph classes over state-of-the-art solvers. In fact, our tool is the first parallel graph automorphism tool that outperforms current sequential tools. © Markus Anders and Pascal Schweitzer;licensed under Creative Commons License CC-BY 4.0

关键词： algorithm engineering Automorphism groups Graph isomorphism Parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

Lightweight Massively Parallel Suffix Array Construction

Lightweight Massively Parallel Suffix Array Construction

引用

作者： Shukhrov, Yury Aalto University

学位级别：硕士

The suffix array is an array of sorted suffixes in lexicographic order, where each sorted suffix is represented by its starting position in the input string. It is a fundamental data structure that finds various applications in areas such as string processing, text indexing, data compression, computational biology, and many more. Over the last three decades, researchers have proposed a broad spectrum of suffix array construction algorithms (SACAs). However, the majority of SACAs were implemented using sequential and parallel programming models. The maturity of GPU programming opened doors to the development of massively parallel GPU SACAs that outperform the fastest versions of suffix sorting algorithms optimized for the CPU parallel computing. Over the last five years, several GPU SACA approaches were proposed and implemented. They prioritized the running time over lightweight design. In this thesis, we design and implement a lightweight massively parallel SACA on the GPU using the prefix-doubling technique. Our prefix-doubling implementation is memory-efficient and can successfully construct the suffix array for input strings as large as 640 megabytes (MB) on Tesla P100 GPU. On large datasets, our implementation achieves a speedup of 7-16x over the fastest, highly optimized, OpenMP-accelerated suffix array constructor, libdivsufsort, that leverages the CPU shared memory parallelism. The performance of our algorithm relies on several high-performance parallel primitives such as radix sort, conditional filtering, inclusive prefix sum, random memory scattering, and segmented sort. We evaluate the performance of our implementation over a variety of real-world datasets with respect to its runtime, throughput, memory usage, and scalability. We compare our results against libdivsufsort that we run on a Haswell compute node equipped with 24 cores. Our GPU SACA is simple and compact, consisting of less than 300 lines of readable and effective source code. Additionally, we

关键词： suffix array GPU prefix-doubling CUDA algorithm engineering Burrows-Wheeler transform

来源：评论

学校读者我要写书评

暂无评论

On the effectiveness of the genetic paradigm for polygonization

引用

INFORMATION PROCESSING LETTERS 2021年 171卷 106134-106134页

作者： Cicerone, Serafino D'Emidio, Mattia Di Stefano, Gabriele Navarra, Alfredo Univ Aquila Dipartimento Ingn & Sci Informaz & Matemat Laquila Italy Univ Perugia Dipartimento Matemat & Informat Perugia Italy

A polygon is simple if it is a closed chain of straight line segments that do not self-intersect. Given a finite set P of input points in the Euclidean plane, the search for a simple polygon with vertex set P is a very well-known and studied computational problem, referred to as the simple polygonization. Its optimization version, that requires to find a simple polygon having either minimum or maximum area, is known to be NP-hard. Moreover, no bounded approximation algorithm is known for the minimization flavor, while the maximization one admits an algorithm guaranteeing 1/2 worst-case approximation ratio. In this work, we design a new algorithm to practically attack both the optimization problems, based on the genetic paradigm. We demonstrate its effectiveness through an extensive experimental evaluation that employs a reference test-bed set of input instances. (C) 2021 Elsevier B.V. All rights reserved.

关键词： Polygonization Approximation algorithms Genetic optimization Computational geometry algorithm engineering

来源：评论

学校读者我要写书评

暂无评论

Practical Polytope Volume Approximation

引用

ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE 2018年第4期44卷 38-38页

作者： Emiris, Ioannis Z. Fisikopoulos, Vissarion Univ Athens Athens Greece Univ Libre Bruxelles Dept Comp Sci CP 216Blvd Triomphe B-1050 Brussels Belgium NKUA Dept Informat & Telecommun Athens Greece

We experimentally study the fundamental problem of computing the volume of a convex polytope given as an intersection of linear halfspaces. We implement and evaluate randomized polynomial-time algorithms for accurately approximating the polytope's volume in high dimensions (e.g., few hundreds) based onhit-andrun random walks. To carry out this efficiently, we experimentally correlate the effect of parameters, such as random walk length and number of sample points, with accuracy and runtime. Our method is based on Monte Carlo algorithms with guaranteed speed and provably high probability of success for arbitrarily high precision. We exploit the problem's features in implementing a practical rounding procedure of polytopes, in computing only partial "generations" of random points, and in designing fast polytope boundary oracles. Our publicly available software is significantly faster than exact computation and more accurate than existing approximation methods. For illustration, volume approximations of Birkhoff polytopes B-11,..., B-15 are computed, in dimensions up to 196, whereas exact methods have only computed volumes of up to B-10.

关键词： Volume approximation general dimension random walk polytope oracle algorithm engineering open source software birkhoff polytopes

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Handling Massive N-Gram Datasets Efficiently

引用

ACM TRANSACTIONS ON INFORMATION SYSTEMS 2019年第2期37卷 25-25页

作者： Pibiri, Giulio Ermanno Venturini, Rossano Univ Pisa Largo Bruno Pontecorvo 3 I-56127 Pisa Italy ISTI CNR Via Giuseppe Moruzzi 1 I-56127 Pisa Italy

Two fundamental problems concern the handling of large n-gram language models: Indexing, that is, compressing the n-grams and associated satellite values without compromising their retrieval speed, and estimation, that is, computing the probability distribution of the n-grams extracted from a large textual source. Performing these two tasks efficiently is vital for several applications in the fields of Information Retrieval, Natural Language Processing, and Machine Learning, such as auto-completion in search engines and machine translation. Regarding the problem of indexing, we describe compressed, exact, and lossless data structures that simultaneously achieve high space reductions and no time degradation with respect to the state-of-the-art solutions and related software packages. In particular, we present a compressed trie data structure in which each word of an n-gram following a context of fixed length k, that is, its preceding k words, is encoded as an integer whose value is proportional to the number of words that follow such context. Since the number of words following a given context is typically very small in natural languages, we lower the space of representation to compression levels that were never achieved before, allowing the indexing of billions of strings. Despite the significant savings in space, our technique introduces a negligible penalty at query time. Specifically, the most space-efficient competitors in the literature, which are both quantized and lossy, do not take less than our trie data structure and are up to 5 times slower. Conversely, our trie is as fast as the fastest competitor but also retains an advantage of up to 65% in absolute space. Regarding the problem of estimation, we present a novel algorithm for estimating modified Kneser-Ney language models that have emerged as the de-facto choice for language modeling in both academia and industry thanks to their relatively low perplexity performance. Estimating such models from large te

关键词： Efficiency scalability algorithm engineering

来源：评论

学校读者我要写书评

暂无评论

Improving Temporal Treemaps by Minimizing Crossings

引用

COMPUTER GRAPHICS FORUM 2024年第3期43卷 e15087-e15087页

作者： Dobler, Alexander Noellenburg, Martin TU Wien Algorithms & Complex Grp Vienna Austria

Temporal trees are trees that evolve over a discrete set of time steps. Each time step is associated with a node-weighted rooted tree and consecutive trees change by adding new nodes, removing nodes, splitting nodes, merging nodes, and changing node weights. Recently, two-dimensional visualizations of temporal trees called temporal treemaps have been proposed, representing the temporal dimension on the x-axis, and visualizing the tree modifications over time as temporal edges of varying thickness. The tree hierarchy at each time step is depicted as a vertical, one-dimensional nesting relationships, similarly to standard, non-temporal treemaps. Naturally, temporal edges can cross in the visualization, decreasing readability. Heuristics were proposed to minimize such crossings in the literature, but a formal characterization and minimization of crossings in temporal treemaps was left open. In this paper, we propose two variants of defining crossings in temporal treemaps that can be combinatorially characterized. For each variant, we propose an exact optimization algorithm based on integer linear programming and heuristics based on graph drawing techniques. In an extensive experimental evaluation, we show that on the one hand the exact algorithms reduce the number of crossings by a factor of 20 on average compared to the previous algorithms. On the other hand, our new heuristics are faster by a factor of more than 100 and still reduce the number of crossings by a factor of almost three.

关键词： Temporal treemaps crossing reduction temporal data algorithm engineering computational experiments

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：