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

The order-preserving pattern matching problem in practice

DISCRETE APPLIED MATHEMATICS 2020年 274卷 11-25页

作者： Cantone, Domenico Faro, Simone Kulekci, M. Oguzhan Univ Catania Dipartimento Matemat & Informat Catania Italy Istanbul Tech Univ Informat Inst Istanbul Turkey

Given a pattern x of length m and a text y of length n, both over a totally ordered alphabet, the order-preserving pattern matching (OPPM) problem consists in finding all substrings of the text with the same relative order as the pattern. The OPPM problem, which might be viewed as an approximate variant of the well-known exact pattern matching problem, has gained attention in recent years. This interesting problem finds applications in such diverse fields as time series analysis (as share prices on stock markets or weather data analysis) and musical melody matching, just to mention a few. In this paper we present two new filtering approaches which turn out to be much more effective in practice than the previously presented methods, reducing the number of false positives up to 99%. We also present a new efficient approach inspired by the well-known Skip Search algorithm for the exact string matching problem. It makes use of efficient SIMD SSE instructions for speeding up the searching phase. experimental results show that our proposed algorithms are up to twice faster than previous solutions. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Approximate text analysis experimental algorithms Filtering algorithms Text processing

来源：评论

学校读者我要写书评

暂无评论

Scalable algorithms for adaptive statistical designs

引用

Scientific Programming 2000年第3期8卷 183-193页

作者： Oehmke, R. Hardwick, J. Stout, Q.F. University of Michigan Ann Arbor MI 48109 USA

We present a scalable, high-performance solution to multidimensional recurrences that arise in adaptive statistical designs. Adaptive designs are an important class of learning algorithms for a stochastic environment, and we focus on the problem of optimally assigning patients to treatments in clinical trials. While adaptive designs have significant ethical and cost advantages, they are rarely utilized because of the complexity of optimizing and analyzing them. Computational challenges include massive memory requirements, few calculations per memory access, and multiply-nested loops with dynamic indices. We analyze the effects of various parallelization options, and while standard approaches do not work well, with effort an efficient, highly scalable program can be developed. This allows us to solve problems thousands of times more complex than those solved previously, which helps make adaptive designs practical. Further, our work applies to many other problems involving neighbor recurrences, such as gen eralized string matching.

关键词： dynamic programming computational learning theory bandit models message-passing dynamic domain decomposition memory-intensive computing load balancing sequential analysis performance analysis experimental algorithms

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

New Instances for Maximum Weight Independent Set From a Vehicle Routing Application

引用

Operations Research Forum 2021年第4期2卷 48页

作者： Dong, Yuanyuan Goldberg, Andrew V. Noe, Alexander Parotsidis, Nikos Resende, Mauricio G. C. Spaen, Quico Dallas TX United States *** East Palo Alto CA United States University of Vienna Vienna Austria Department of Computer Science University of Copenhagen Copenhagen Denmark *** and Industrial & Systems Engineering University of Washington Seattle WA United States

We present a set of new instances of the maximum weight independent set problem. These instances are derived from a real-world vehicle routing problem and are challenging to solve in part because of their large size. ... 详细信息

关键词： experimental algorithms Maximum weight independent set Problem instances

来源：评论

学校读者我要写书评

暂无评论

Efficient algorithms for the Order Preserving Pattern Matching Problem 1

引用

11th International Conference on Algorithmic Aspects in Information and Management (AAIM)

作者： Faro, Simone Kulekci, M. Oguzhan Univ Catania Dept Math & Comp Sci Catania Italy Istanbul Tech Univ Inst Informat Istanbul Turkey

ISBN: (数字)9783319411682

ISBN: (纸本)9783319411682;9783319411675

Given a pattern x of length m and a text y of length n, both over an ordered alphabet, the order-preserving pattern matching problem consists in finding all substrings of the text with the same relative order as the pattern. The OPPM, which might be viewed as an approximate variant of the well known exact pattern matching problem, has gained attention in recent years. This interesting problem finds applications in a lot of fields as from time series analysis, like share prices on stock markets or weather data analysis, to musical melody matching. In this paper we present two new filtering approaches which turn out to be much more effective in practice than the previously presented methods by reducing the number of false positives up to 99%. From our experimental results it turns out that our proposed solutions are up to 2 times faster than the previous solutions.

关键词： Approximate text analysis experimental algorithms Filtering algorithms Text processing

来源：评论

学校读者我要写书评

暂无评论

An efficient algorithm for δ-approximate matching with α-bounded gaps in musical sequences

引用

4th International Workshop on experimental and Efficient algorithms

作者： Cantone, D Cristofaro, S Faro, S Univ Catania Dipartimento Matemat & Informat I-95125 Catania Italy

ISBN: (纸本)3540259201

We present a new efficient algorithm for the delta-approximate matching problem with a-bounded gaps. The delta-approximate matching problem, recently introduced in connection with applications in music retrieval, generalizes the exact string matching problem by relaxing the notion of matching. Here we consider the case in which matchings may contain bounded gaps. An extensive comparison with the only (to our knowledge) other solution existing in the literature for the same problem, due to Crochemore et al., indicates that our algorithm is more efficient, especially in the cases of large alphabets and long patterns. In addition, our algorithm computes the total number of approximate matchings for each position of the text, requiring only O(m alpha)-space, where m, is the length of the pattern.

关键词： approximate string matching experimental algorithms musical information retrieval

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Towards a Very Fast Multiple String Matching Algorithm for Short Patterns

Towards a Very Fast Multiple String Matching Algorithm for S...

引用

8th Prague Stringology Conference (PSC)

作者： Faro, Simone Kulekci, M. Oguzhan Univ Catania Dipartimento Matemat & Informat I-95124 Catania Italy TUBTAK Natl Res Inst Elect & Cryptol Gebze Turkey

ISBN: (纸本)9788001053300

Multiple exact string matching is one of the fundamental problems in computer science and finds applications in many other fields, among which computational biology and intrusion detection. It turns out that short patterns appear in many instances of such problems and, in most cases, sensibly affect the performances of the algorithms. Recent solutions in the field of string matching try to exploit the power of the word RAM model to speed-up the performances of classical algorithms. In this model an algorithm operates on words of length w, grouping blocks of characters, and arithmetic and logic operations on the words take one unit of time. This study presents a first preliminary attempt to develop a filter based exact multiple string matching algorithm for searching set of short patterns by taking benefit from Intel's SSE (streaming SIMD extensions) technology. Our experimental results on small, medium, and large alphabet text files show that the proposed algorithm is competitive in the case of short patterns against other efficient solutions, which are known to be among the fastest in practice.

关键词： multiple string matching experimental algorithms text-processing short patterns Streaming SIMD Extensions Technology SSE

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：