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

The Exact Online String Matching Problem: A Review of the Most Recent Results

ACM COMPUTING SURVEYS 2013年第2期45卷 13-13页

作者： Faro, Simone Lecroq, Thierry Univ Catania Dipartimento Matemat & Informat I-95125 Catania Italy Univ Rouen LITIS EA 4108 F-76821 Mont St Aignan France

This article addresses the online exact string matching problem which consists in finding all occurrences of a given pattern p in a text t. It is an extensively studied problem in computer science, mainly due to its direct applications to such diverse areas as text, image and signal processing, speech analysis and recognition, information retrieval, data compression, computational biology and chemistry. In the last decade more than 50 new algorithms have been proposed for the problem, which add up to a wide set of (almost 40) algorithms presented before 2000. In this article we review the string matching algorithms presented in the last decade and present experimental results in order to bring order among the dozens of articles published in this area.

关键词： algorithms Design Experimentation String matching experimental algorithms text processing automaton

来源：评论

学校读者我要写书评

暂无评论

Faster Betweenness Centrality Based on Data Structure Experimentation

引用

Procedia Computer Science 2013年 18卷 399-408页

作者： Oded Green David A. Bader College of Computing Georgia Institute of Technology Atlanta Georgia USA

Betweenness centrality is a graph analytic that states the importance of a vertex based on the number of shortest paths that it is on. As such, betweenness centrality is a building block for graph analysis tools and is used by many applications, including finding bottlenecks in communication networks and community detection. Computing betweenness centrality is computation- ally demanding, O ( V 2 + V · E ) (for the best known algorithm), which motivates the use of parallelism. Parallelism is especially needed for large graphs with millions of vertices and billions of edges. While the the memory requirements for computing be- tweenness are not as demanding, O ( V + E ) (for the best known sequential algorithm), these bound increase for different parallel algorithms. We show that is possible to reduce the memory requirements for computing betweenness centrality from O ( V + E ) to O ( V ) at the expense of doing additional traversals. We show that not only does this not hurt performance it actually improves performance for coarse grain parallelism. Further, we show that using the new approach allows parallel scaling that previously was not possible. One example is that the new approach is able to scale to 40 x86 cores for a graph with 32 M vertices and 2B edges, whereas the previous approach is only able to scale upto 6 cores because of memory requirements. We also do analysis of fine-grain parallel betweenness centrality on both the x86 and the Cray XMT.

关键词： Parallel algorithms Graph algorithms Betweenness Centrality Optimizations experimental algorithms

来源：评论

学校读者我要写书评

暂无评论

Computational Study on Bidimensionality Theory Based Algorithm for Longest Path Problem 1

引用

22nd International Symposium on algorithms and Computation (ISAAC)

作者： Wang, Chunhao Gu, Qian-Ping Simon Fraser Univ Sch Comp Sci Burnaby BC V5A 1S6 Canada

ISBN: (数字)9783642255915

ISBN: (纸本)9783642255908

Bidimensionality theory provides a general framework for developing subexponential fixed parameter algorithms for NP-hard problems. In this framework, to solve an optimization problem in a graph G, the branchwidth bw(G) is first computed or estimated. If bw(G) is small then the problem is solved by a branch-decomposition based algorithm which typically runs in polynomial time in the size of G but in exponential time in bw(G). Otherwise, a large bw(G) implies a large grid minor of G and the problem is computed or estimated based on the grid minor. A representative example of such algorithms is the one for the longest path problem in planar graphs. Although many subexponential fixed parameter algorithms have been developed based on bidimensionality theory, little is known on the practical performance of these algorithms. We report a computational study on the practical performance of a bidimensionality theory based algorithm for the longest path problem in planar graphs. The results show that the algorithm is practical for computing/estimating the longest path in a planar graph. The tools developed and data obtained in this study may be useful in other bidimensional algorithm studies.

关键词： experimental algorithms bidimensional algorithms branch-decomposition grid minor longest path problem

来源：评论

学校读者我要写书评

暂无评论

Experiments on Union-Find algorithms for the Disjoint-Set Data Structure

Experiments on Union-Find Algorithms for the Disjoint-Set Da...

引用

9th International Symposium on experimental algorithms

作者： Patwary, Md Mostofa Ali Blair, Jean Manne, Fredrik Univ Bergen Dept Informat N-5020 Bergen Norway US Mil Acad Dept EE & CS West Point NY 10996 USA

ISBN: (纸本)9783642131929

The disjoint-set data structure is used to maintain a collection of non-overlapping sets of elements from a finite universe. algorithms that operate on this data structure are often referred to as UNION-FIND algorithms. They are used in numerous practical applications and are also available in several software libraries. This paper presents an extensive experimental study comparing the time required to execute 55 variations of UNION-FIND algorithms. The study includes all the classical algorithms, several recently suggested enhancements, and also different combinations and optimizations of these. Our results clearly show that a somewhat forgotten simple algorithm developed by Rem in 1976 is the fastest, in spite of the fact that its worst-case time complexity is inferior to that of the commonly accepted "best" algorithms.

关键词： Union-Find Disjoint Set experimental algorithms

来源：评论

学校读者我要写书评

暂无评论

Fault Recovery in Wireless Networks: The Geometric Recolouring Approach

Fault Recovery in Wireless Networks: The Geometric Recolouri...

引用

9th International Symposium on experimental algorithms

作者： Meijer, Henk Nunez-Rodriguez, Yurai Rappaport, David Roosevelt Acad Middelburg Netherlands Queens Univ Kingston ON Canada

ISBN: (纸本)9783642131929

Duplication of information allows distributed systems to recover from data errors, or faults. If faults occur spontaneously, without notification, and disguised incorrect data blends in with correct data, their detection becomes non-trivial. Known solutions for fault recovery use monitoring mechanisms that compare the data in multiple nodes to infer the occurrence of faults. To this end, we propose a localized geometric approach to fault recovery in wireless networks. We compare our approach with a more traditional combinatorial approach that uses a majority rule. Our experiments show that our geometric approach is an improvement over the majority rule in some cases, whereas in the other cases a hybrid method that combines the best of both strategies is superior to each individual method.

关键词： fault recovery recolouring wireless networks computational geometry experimental algorithms localized algorithms

来源：评论

学校读者我要写书评

暂无评论

A Space-Efficient Implementation of the Good-Suffix Heuristic

A Space-Efficient Implementation of the Good-Suffix Heuristi...

引用

Prague Stringology Conference (PSC)

作者： Cantone, Domenico Cristofaro, Salvatore Faro, Simone Univ Catania Dipartimento Matemat & Informat I-95125 Catania Italy

We present an efficient variation of the good-suffix heuristic, firstly introduced in the well-known Boyer-Moore algorithm for the exact string matching problem. Our proposed variant uses only constant space, retainin... 详细信息

ISBN: (纸本)9788001045978

关键词： string matching experimental algorithms text-processing good-suffix rule costant-space algorithms

来源：评论

学校读者我要写书评

暂无评论

Engineering burstsort: Toward fast in-place string sorting

引用

ACM Journal of experimental Algorithmics 2010年第PP2.1–2.24期15卷 2.1–2.24页

作者： Ranjan Sinha Anthony Wirth The University of Melbourne

Burstsort is a trie-based string sorting algorithm that distributes strings into small buckets whose contents are then sorted in cache. This approach has earlier been demonstrated to be efficient on modern cache-based processors [Sinha & Zobel, JEA 2004]. In this article, we introduce improvements that reduce by a significant margin the memory requirement of Burstsort: It is now less than 1% greater than an in-place algorithm. These techniques can be applied to existing variants of Burstsort, as well as other string algorithms such as for string *** redesigned the buckets, introducing sub-buckets and an index structure for them, which resulted in an order-of-magnitude space reduction. We also show the practicality of moving some fields from the trie nodes to the insertion point (for the next string pointer) in the bucket; this technique reduces memory usage of the trie nodes by one-third. Importantly, the trade-off for the reduction in memory use is only a very slight increase in the running time of Burstsort on real-world string collections. In addition, during the bucket-sorting phase, the string suffixes are copied to a small buffer to improve their spatial locality, lowering the running time of Burstsort by up to 30%. These memory usage enhancements have enabled the copy-based approach [Sinha et al., JEA 2006] to also reduce the memory usage with negligible impact on speed.

关键词： Sorting algorithms cache experimental algorithms string management tries

来源：评论

学校读者我要写书评

暂无评论

EFFICIENT VARIANTS OF THE BACKWARD-ORACLE-MATCHING ALGORITHM

引用

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 2009年第6期20卷 967-984页

作者： Faro, Simone Lecroq, Thierry Univ Catania Dipartimento Matemat & Informat I-95125 Catania Italy Univ Rouen LITIS EA 4108 F-76821 Mont St Aignan France

In this article we present two efficient variants of the BOM string matching algorithm which are more efficient and flexible than the original algorithm. We also present bit-parallel versions of them obtaining an efficient variant of the BNDM algorithm. Then we compare the newly presented algorithms with some of the most recent and effective string matching algorithms. It turns out that the new proposed variants are very flexible and achieve very good results, especially in the case of large alphabets.

关键词： String matching experimental algorithms text processing automaton

来源：评论

学校读者我要写书评

暂无评论

An Efficient Matching Algorithm for Encoded DNA Sequences and Binary Strings

引用

20th Annual Symposium on Combinatorial Pattern Matching

作者： Faro, Simone Lecroq, Thierry Univ Catania Dipartimento Matemat & Informat I-95124 Catania Italy Univ Rouen LITIS EA 4108 F-76821 Mont St Aignan France

ISBN: (纸本)9783642024405

We present a new efficient algorithm for exact matching in encoded DNA sequences and on binary strings. Our algorithm combines a multi-pattern version of the BNDM algorithm and a simplified version of the COMMENTZ-WALTER algorithm. We performed also experimental comparisons with the most efficient algorithms presented in the literature. experimental results show that the newly presented algorithm outperforms existing solutions in most cases.

关键词： string matching binary strings DNA sequences experimental algorithms compressed text processing

来源：评论

学校读者我要写书评

暂无评论

EFFICIENT VARIANTS OF THE BACKWARD-ORACLE-MATCHING ALGORITHM

EFFICIENT VARIANTS OF THE BACKWARD-ORACLE-MATCHING ALGORITHM

引用

13th Prague Stringology Conference (PSC)

作者： Faro, Simone Lecroq, Thierry Univ Catania Dipartimento Matemat & Informat I-95125 Catania Italy Univ Rouen LITIS EA 4108 F-76821 Mont St Aignan France

ISBN: (纸本)9788001041451

关键词： String matching experimental algorithms text processing automaton

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：