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

Implicit Generation of Pattern-Avoiding Permutations by Using Permutation Decision Diagrams

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2014年第6期E97A卷 1171-1179页

作者： Inoue, Yuma Toda, Takahisa Minato, Shin-ichi Hokkaido Univ Grad Sch Informat Sci & Technol Sapporo Hokkaido 0600814 Japan JST ERATO MINATO Discrete Struct Manipulat Syst P Sapporo Hokkaido 0600814 Japan

Pattern-avoiding permutations are permutations where none of the subsequences matches the relative order of a given pattern. Pattern-avoiding permutations are related to practical and abstract mathematical problems and can provide simple representations for such problems. For example, some floorplans, which are used for optimizing very-large-scale integration (VLSI) circuit design, can be encoded into pattern-avoiding permutations. The generation of pattern-avoiding permutations is an important topic in efficient VLSI design and mathematical analysis of patten-avoiding permutations. In this paper, we present an algorithm for generating pattern-avoiding permutations, and extend this algorithm beyond classical patterns to generalized patterns with more restrictions. Our approach is based on the data structure pi DDs, which can represent a permutation set compactly and has useful set operations. We demonstrate the efficiency of our algorithm by computational experiments.

关键词： pattern-avoiding permutations generating algorithms decision diagrams pi DD experimental algorithms

来源：评论

学校读者我要写书评

暂无评论

Improved characters distance sampling for online and offline text searching

引用

THEORETICAL COMPUTER SCIENCE 2023年 946卷

作者： Faro, Simone Marino, Francesco Pio Pavone, Arianna Univ Catania Dept Math & Comp Sci Viale ADoria n6 I-95125 Catania Italy Univ Messina Dept Cognit Sci Via Concez n6 I-98121 Messina Italy

Sampled string matching is a very effective technique to reduce the search time for a pattern within a text at the cost of a small amount of additional memory, used for storing a partial index of the text. This approach has recently received some interest and has been applied to improve both online and offline string matching solutions, improving standard solutions by more than 50%. However, this improvement is currently only achievable in the case of texts on large-sized alphabets, and remains small (or absent) in the case of small-sized alphabets. In this article we propose an extension of the approach to text-sampling, known as Character Distance Sampling, to the case of small alphabets, obtaining an improvement of up to 98% compared to standard solutions in the case of online string matching. We also extend this approach to the case of offline string matching, introducing a sampled version of the suffix array, obtaining performances up to 5 times higher than the search obtained on the standard suffix array. Differently from what has been done by previous solutions, our idea is not based on the reduction of the number of indexed suffixes, but on the construction of the index directly on the sampled text. (c) 2022 Elsevier B.V. All rights reserved.

关键词： Text processing experimental algorithms String matching

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Improved and self-tuned occurrence heuristics

引用

JOURNAL OF DISCRETE algorithms 2014年 28卷 73-84页

作者： Cantone, Domenico Faro, Simone Univ Catania Dipartimento Matemat & Informat Catania Italy

In this note we present three efficient variations of the occurrence heuristic, adopted by many exact string matching algorithms and first introduced in the well-known Boyer-Moore algorithm. Our first heuristic, called improved-occurrence heuristic, is a simple improvement of the rule introduced by Sunday in his Quick-Search algorithm. Our second heuristic, called worst-occurrence heuristic, achieves its speed-up by selecting the relative position which yields the largest average advancement. Finally, our third heuristic, called jumping-occurrence heuristic, uses two characters for computing the next shift. Setting the distance between these two characters optimally allows one to maximize the average advancement. The worst-occurrence and jumping-occurrence heuristics tune their parameters according to the distribution of the characters in the text. experimental results show that the newly proposed heuristics achieve very good results on average, especially in the case of small alphabets. (C) 2014 Elsevier B.V. All rights reserved.

关键词： String matching experimental algorithms Text-processing Occurrence heuristics Frequency of characters Tuned-search approach

来源：评论

学校读者我要写书评

暂无评论

Fast and flexible packed string matching

引用

JOURNAL OF DISCRETE algorithms 2014年 28卷 61-72页

作者： Faro, Simone Kulekci, M. Oguzhan Univ Catania Dipartimento Matemat & Informat Catania Italy Istanbul Medipol Univ Fac Engn & Nat Sci Istanbul Turkey

Searching for all occurrences of a pattern in a text is a fundamental problem in computer science with applications in many other fields, like natural language processing, information retrieval and computational biology. In the last two decades a general trend has appeared trying to exploit the power of the word RAM model to speed-up the performances of classical string matching 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. In this paper we use specialized word-size packed string matching instructions, based on the Intel streaming SIMD extensions (SSE) technology, to design a very fast string matching algorithm. We evaluate our solution in terms of efficiency, stability and flexibility, where we propose to use the deviation in running time of an algorithm on distinct equal length patterns as a measure of stability. From our experimental results it turns out that, despite their quadratic worst case time complexity, the new presented algorithm becomes the clear winner on the average in many cases, when compared against the most recent and effective algorithms known in literature. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Exact string matching Text algorithms experimental algorithms Online searching Information retrieval

来源：评论

学校读者我要写书评

暂无评论

Scalable algorithms for adaptive statistical designs 00

Scalable algorithms for adaptive statistical designs

引用

Proceedings of the 2000 ACM/IEEE conference on Supercomputing

作者： Robert Oehmke Janis Hardwick Quentin F. Stout University of Michigan Ann Arbor Michigan

ISBN: (纸本)9780780398023

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 pratical. Further, our work applies to many other problems involing neighbor recurrences, uch as generalized string matching.

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

来源：评论

学校读者我要写书评

暂无评论

Breaking cycles for minimizing crossings

引用

ACM Journal of experimental Algorithmics 2001年 6卷 2–es页

作者： Demetrescu, Camil Finocchi, Irene Dipartimento di Informatica e Sistemistica Università di Roma la Sapienza 00198 Rome via Salaria 113 Italy Dipartimento di Informatica Sistemi e Produzione Università Degli Studi di Roma Tor Ver-gata 00133 Rome Via del Politecnico 1 Italy

We consider the one-sided crossing minimization problem (CP): given a bipartite graph G and a permutation x0 of the vertices on a layer, find a permutation x1 of the vertices on the other layer which minimizes the number of edge crossings in any straightline drawing of G where vertices are placed on two parallel lines and sorted according to x0 and x1. Solving CP represents a fundamental step in the construction of aesthetically pleasing layouts of hierarchies and directed graphs, but unfortunately this problem has been proved to be NP-complete. In this paper we address the strong relation between CP and the problem of computing minimum feedback arc sets in directed graphs and we devise a new approximation algorithm for CP, called PM, that exploits this dependency. We experimentally and visually compare the performance of PM with the performance of well-known algorithms and of recent attractive strategies. Experiments are carried out on different families of randomly generated graphs, on pathological instances, and on real test sets. Performance indicators include both number of edge crossings and running time, as well as structural measures of the problem instances. We found CP to be a very interesting and rich problem from a combinatorial point of view. Our results clearly separate the behavior of the algorithms, proving the effectiveness of PM on most test sets and showing tradeoffs between quality of the solutions and running time. However, if the visual complexity of the drawings is considered, we found no clear winner. This confirms the importance of optimizing also other aesthetic criteria such as symmetry, edge length, and angular resolution.

关键词： experimental algorithms bipartite graphs crossing minimization

来源：评论

学校读者我要写书评

暂无评论

Cache-efficient string sorting using copying

引用

ACM Journal of experimental Algorithmics 2006年 11卷 1.2–es页

作者： Sinha, Ranjan Zobel, Justin Ring, David School of Computer Science and Information Technology RMIT University GPO Box 2476V Melbourne 3001 Australia Palo Alto CA United States

Burstsort is a cache-oriented sorting technique that uses a dynamic trie to efficiently divide large sets of string keys into related subsets small enough to sort in cache. In our original burstsort, string keys sharing a common prefix were managed via a bucket of pointers represented as a list or array;this approach was found to be up to twice as fast as the previous best string sorts, mostly because of a sharp reduction in out-of-cache references. In this paper, we introduce C-burstsort, which copies the unexamined tail of each key to the bucket and discards the original key to improve data locality. On both Intel and PowerPC architectures, and on a wide range of string types, we show that sorting is typically twice as fast as our original burstsort and four to five times faster than multikey quicksort and previous radixsorts. A variant that copies both suffixes and record pointers to buckets, CP-burstsort, uses more memory, but provides stable sorting. In current computers, where performance is limited by memory access latencies, these new algorithms can dramatically reduce the time needed for internal sorting of large numbers of strings. © 2006 ACM.

关键词： algorithms Algorthims B.3.2 [Memory Structures]: Cache Memories Cache D.1.0 [Programming Techniques]: General Design E.1 [Data Structures]: Trees E.5 [Files]: Sorting experimental algorithms Experimentation F.2.2 [Analysis of algorithms]: Sorting Performance Sorting String management Tries

来源：评论

学校读者我要写书评

暂无评论

algorithms for dynamic multicast key distribution

引用

ACM Journal of experimental Algorithmics 2006年 11卷 1.4–es页

作者： Goshi, Justin Ladner, Richard E. Department of Computer Science and Engineering University of Washington Box 352350 Seattle 98195 WA United States

We study the problem of multicast key distribution for group security. Secure group communication systems typically rely on a group key, which is a secret shared among the members of the group. This key is used to provide privacy by encrypting all group communications. Because groups can be large and highly dynamic, it becomes necessary to change the group key in a scalable and secure fashion when members join and leave the group. We present a series of algorithms for solving this problem based on key trees. The algorithms attempt to minimize the worst-case communication cost of updates by maintaining balanced key tree structures. We focus on the trade-off between the communication cost because of the structure of the tree and that due to the overhead of restructuring the tree to maintain its balanced structure. The algorithms are analyzed for worst-case tree structure bounds and evaluated empirically via simulations. © 2006 ACM.

关键词： algorithms C.2.0 [Computer-Communication Networks]: General - Security and Protection Dynamic key distribution experimental algorithms Multicast Security Theory

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：