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

algorithm engineering for optimal alignment of protein structure distance matrices

OPTIMIZATION LETTERS 2011年第3期5卷 421-433页

作者： Wohlers, Inken Andonov, Rumen Klau, Gunnar W. CWI Life Sci Grp NL-1009 AB Amsterdam Netherlands INRIA Rennes Rennes France Univ Rennes 1 Rennes France

Protein structural alignment is an important problem in computational biology. In this paper, we present first successes on provably optimal pairwise alignment of protein inter-residue distance matrices, using the popular dali scoring function. We introduce the structural alignment problem formally, which enables us to express a variety of scoring functions used in previous work as special cases in a unified framework. Further, we propose the first mathematical model for computing optimal structural alignments based on dense inter-residue distance matrices. We therefore reformulate the problem as a special graph problem and give a tight integer linear programming model. We then present algorithm engineering techniques to handle the huge integer linear programs of real-life distance matrix alignment problems. Applying these techniques, we can compute provably optimal dali alignments for the very first time.

关键词： Protein structure distance matrix alignment algorithm engineering Integer linear programming Branch-and-cut Preprocessing DALI

来源：评论

学校读者我要写书评

暂无评论

The design of parallel square-root covariance Kalman filters using algorithm engineering

引用

INTEGRATION-THE VLSI JOURNAL 1995年第1期20卷 101-119页

作者： Brown, DW Gaston, FMF Control Engineering Research Group Department of Electrical and Electronic Engineering The Queen's University of Belfast Ashby Building Stranmillis Road Belfast BT9 5AH UK

Megson and Comish (1994) have defined techniques using a systematic approach to derive a parallel algorithm for Riccati type equations. In this paper these techniques will be used to derive a full three-dimensional Hierarchical Signal Flow Graph (HSFG) for the square-root covariance Kalman filter (SRCKF) algorithm. This novel flow graph involves matrix-matrix multiplication, Givens rotations and the Schur complement algorithms. Simple projection techniques detailed in (Megson, 1992;S.V. Rajopadhye and R.M. Fujimoto, 1990) are used to form two-dimensional descriptions of the algorithm. From these, parallel algorithms for the SRCKF can be generated using algorithm engineering techniques. As an extended example of algorithm engineering techniques given by Megson (1992, 1994), the parallel algorithms in the form of systolic architectures proposed by Gaston et al. (1990) and by Brown and Gaston (1994), are derived in detail.

关键词： algorithm engineering Kalman filter systolic array parallel processing

来源：评论

学校读者我要写书评

暂无评论

A case study in algorithm engineering for geometric computing

引用

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS 2001年第1期11卷 15-70页

作者： Tamassia, R Vismara, L Brown Univ Dept Comp Sci Ctr Geometr Comp Providence RI 02912 USA

The goal of this paper is to prove the applicability of algorithm engineering and software design concepts to geometric computing through a vertical case study on the implementation of planar point location algorithms. The work is presented within the framework of the GEOMLIB project, aimed at developing an easy to use, reliable, and flexible library of robust and efficient geometric algorithms. We present the criteria that have inspired the preliminary design of GEOMLIB and discuss the guidelines that we have followed in the initial implementation.

关键词： algorithm engineering geometric computing software libraries point location

来源：评论

学校读者我要写书评

暂无评论

Analysis of Evolutionary algorithms: From Computational Complexity Analysis to algorithm engineering 11

Analysis of Evolutionary Algorithms: From Computational Comp...

引用

11th Foundations of Genetic algorithms Workshop

作者： Jansen, Thomas Zarges, Christine Natl Univ Ireland Univ Coll Cork Dept Comp Sci Cork Ireland

ISBN: (纸本)9781450306331

Analyzing the computational complexity of evolutionary algorithms has become an accepted and important branch in evolutionary computation theory. This is usually done by analyzing the (expected) optimization time measured by means of the number of function evaluations and describing its growth as a. function of a measure for the size of the search space. Most often asymptotic results describing only the order of growth are derived. This corresponds to classical analysis of (randomized) algorithms in algorithmics. Recently, the emerging field of algorithm engineering has demonstrated that for practical purposes this analysis can be too coarse and more details of the algorithm and its implementation have to be taken into account in order to obtain results that are valid in practice. Using a very recent analysis of a simple evolutionary algorithm as starting point it is shown that the same holds for evolutionary algorithms. Considering this example it is demonstrated that counting function evaluations more precisely can lead to results contradicting actual run times. Motivated by these limitations of computational complexity analysis an algorithm engineering-like approach is presented.

关键词： Runtime analysis algorithm engineering performance measures

来源：评论

学校读者我要写书评

暂无评论

Special Issue on "algorithm engineering: Towards Practically Efficient Solutions to Combinatorial Problems"

引用

algorithmS 2019年第11期12卷 229-229页

作者： D'Emidio, Mattia Frigioni, Daniele Univ Aquila Dept Informat Engn Comp Sci & Math Via Vetoio I-67100 Laquila Italy

The purpose of this special issue of algorithms was to attract papers presenting original research in the area of algorithm engineering. In particular, submissions concerning the design, analysis, implementation, tuning, and experimental evaluation of discrete algorithms and data structures, and/or addressing methodological issues and standards in algorithmic experimentation were encouraged. Papers dealing with advanced models of computing, including memory hierarchies, cloud architectures, and parallel processing were also welcome. In this regard, we solicited contributions from all most prominent areas of applied algorithmic research, which include but are not limited to graphs, databases, computational geometry, big data, networking, combinatorial aspects of scientific computing, and computational problems in the natural sciences or engineering.

关键词： journey planning temporal graphs influence maximization network analysis bamboo garden trimming problem convex hull experimental algorithmics algorithm engineering computational social choice statistical analysis of algorithms scheduling approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

FREIGHT: Fast Streaming Hypergraph Partitioning

引用

algorithmICA 2025年第3期87卷 405-428页

作者： Eyubov, Kamal Faraj, Marcelo Fonseca Schulz, Christian Heidelberg Univ Inst Comp Sci D-69120 Heidelberg Baden Wurttembe Germany

Partitioning the vertices of a (hyper)graph into k roughly balanced blocks such that few (hyper)edges run between blocks is a key problem for large-scale distributed processing. A current trend for partitioning huge (hyper)graphs using low computational resources are streaming algorithms. In this work, we propose FREIGHT: a Fast stREamInG Hypergraph parTitioning algorithm which is an adaptation of the widely-known graph-based algorithm Fennel. By using an efficient data structure, we make the overall running of FREIGHT linearly dependent on the pin-count of the hypergraph and the memory consumption linearly dependent on the numbers of nets and blocks. The results of our extensive experimentation showcase the promising performance of FREIGHT as a highly efficient and effective solution for streaming hypergraph partitioning. Our algorithm demonstrates competitive running time with the Hashing algorithm, with a geometric mean runtime within a factor of four compared to the Hashing algorithm. Significantly, our findings highlight the superiority of FREIGHT over all existing (buffered) streaming algorithms and even the in-memory algorithm HYPE, with respect to both cut-net and connectivity measures. This indicates that our proposed algorithm is a promising hypergraph partitioning tool to tackle the challenge posed by large-scale and dynamic data processing.

关键词： Streaming algorithms Hypergraph partitioning Graph partitioning algorithm engineering

来源：评论

学校读者我要写书评

暂无评论

Two-level massive string dictionaries

引用

INFORMATION SYSTEMS 2025年 128卷

作者： Ferragina, Paolo Rotundo, Mariagiovanna Vinciguerra, Giorgio Univ Pisa Dept Comp Sci Lgo B Pontecorvo 3 I-56127 Pisa PI Italy

We study the problem of engineering space-time efficient data structures that support membership and rank queries on very large static dictionaries of strings. Our solution is based on a very simple approach that decouples string storage and string indexing by means of a block-wise compression of the sorted dictionary strings (to be stored in external memory) and a succinct implementation of a Patricia trie (to be stored in internal memory) built on the first string of each block. On top of this, we design an in-memory cache that, given a sample of the query workload, augments the Patricia trie with additional information to reduce the number of I/Os of future queries. Our experimental evaluation on two new datasets, which are at least one order of magnitude larger than the ones used in the literature, shows that (i) the state-of-the-art compressed string dictionaries, compared to Patricia tries, do not provide significant benefits when used in a large-scale indexing setting, and (ii) our two-level approach enables the indexing and storage of 3.5 billion strings taking 273 GB in just less than 200 MB of internal memory and 83 GB of compressed disk space, while still guaranteeing comparable or faster query performance than those offered by array-based solutions used in modern storage systems, such as RocksDB, thus possibly influencing their future design.

关键词： String dictionary problem Trie data structure String compression algorithm engineering Key-value stores

来源：评论

学校读者我要写书评

暂无评论

On Mining Dynamic Graphs for k Shortest Paths 16th

On Mining Dynamic Graphs for k Shortest Paths

引用

16th International Conference on Social Networks Analysis and Mining

作者： D'Ascenzo, Andrea D'Emidio, Mattia Luiss Univ Rome Italy Univ Aquila Laquila Italy

ISBN: (纸本)9783031785405;9783031785412

Mining graphs, upon query, for k shortest paths between vertex pairs is a prominent primitive to support several analytics tasks on complex networked datasets. The state-of-the-art method to implement this primitive is KPLL, a framework that provides very fast query answering, even for large inputs and volumes of queries, by pre-computing and exploiting an appropriate index of the graph. However, if the graph's topology undergoes changes over time, such index might become obsolete and thus yield incorrect query results. Re-building the index from scratch, upon every modification, induces unsustainable time overheads, incompatible with applications using k shortest paths for analytics purposes. Motivated by this limitation, in this paper, we introduce DECKPLL, the first dynamic algorithm to maintain a KPLL index under decremental modifications. We assess the effectiveness and scalability of our algorithm through extensive experimentation and show it updates KPLL indices orders of magnitude faster than the re-computation from scratch, while preserving its compactness and query performance. We also combine DECKPLL with INCKPLL, the only known dynamic algorithm to maintain a KPLL index under incremental modifications, and hence showcase, on real-world datasets, the first method to support fast extraction of k shortest paths from graphs that evolve by arbitrary topological changes.

关键词： Graph algorithms Dynamic Networks algorithm engineering Experimental algorithmics

来源：评论

学校读者我要写书评

暂无评论

engineering a Lightweight External Memory Suffix Array Construction algorithm

引用

MATHEMATICS IN COMPUTER SCIENCE 2017年第2期11卷 137-149页

作者： Karkkainen, Juha Kempa, Dominik Univ Helsinki Dept Comp Sci POB 68Gustaf Hallstromin Katu 2b FIN-00014 Helsinki Finland

We describe an external memory suffix array construction algorithm based on constructing suffix arrays for blocks of text and merging them into the full suffix array. The basic idea goes back over 20 years and there has been a couple of later improvements, but we describe several further improvements that make the algorithm much faster. In particular, we reduce the I/O volume of the algorithm by a factor . Our experiments show that the algorithm is the fastest suffix array construction algorithm when the size of the text is within a factor of about five from the size of the RAM in either direction, which is a common situation in practice.

关键词： Suffix array construction External memory algorithms algorithm engineering

来源：评论

学校读者我要写书评

暂无评论

Modeling and engineering Constrained Shortest Path algorithms for Battery Electric Vehicles

引用

TRANSPORTATION SCIENCE 2020年第6期54卷 1571-1600页

作者： Baum, Moritz Dibbelt, Julian Wagner, Dorothea Zundorf, Tobias Karlsruhe Inst Technol Inst Theoret Informat Grp Algorithm D-76131 Karlsruhe Germany

We study the problem of computing constrained shortest paths for battery electric vehicles. Because battery capacities are limited, fastest routes are often infeasible. Instead, users are interested in fast routes on which the energy consumption does not exceed the battery capacity. For that, drivers can deliberately reduce speed to save energy. Hence, route planning should provide both path and speed recommendations. To tackle the resulting NoP-hard optimization problem, previous work trades correctness or accuracy of the underlying model for practical running times. We present a novel framework to compute optimal constrained shortest paths (without charging stops) for electric vehicles that uses more realistic physical models, while taking speed adaptation into account. Careful algorithm engineering makes the approach practical even on large, realistic road networks: We compute optimal solutions in less than a second for typical battery capacities, matching the performance of previous inexact methods. For even faster query times, the approach can easily be extended with heuristics that provide high quality solutions within milliseconds.

关键词： route planning road networks speedup techniques algorithm engineering constrained shortest paths electric vehicles energy consumption

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：