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

Distance-preserving approximations of polygonal paths

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 2007年第3期36卷 183-196页

作者： Gudmundsson, Joachim Narasimhan, Giri Smid, Michiel Florida Int Univ Sch Comp Sci Miami FL 33199 USA Carleton Univ Sch Comp Sci Ottawa ON K1S 5B6 Canada

Given a polygonal path P with vertices p(1), p(2),..., p(n) is an element of R-d and a real number t >= 1, a path Q = (p(i1), p(i2),...,P-ik) is a t-distance-preserving approximation of P if 1 = i(1) < i(2) < ... < i(k) = n and each straight-line edge (p(ij), p(ij+1)) of Q approximates the distance between pi(j) and pi(j+1) along the path P within a factor of t. We present exact and approximation algorithms that compute Such a path Q that minimizes k (when given t) or t (when given k). We also present some experimental results. (c) 2006 Elsevier B.V. All rights reserved.

关键词： path simplification t-spanners well-separated pair decomposition experimental algorithms

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Fast-search: A new efficient variant of the Boyer-Moore string matching algorithm 1

引用

2nd International Workshop on experimental and Efficient algorithms

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

ISBN: (数字)9783540448679

ISBN: (纸本)3540402055

We present a new variant of the Boyer-Moore string matching algorithm which, though not linear, is very fast in practice. We compare our algorithm with the Horspool, Quick Search, Mined Boyer-Moore, and Reverse Factor algorithms, which are among the fastest string matching algorithms for I practical uses. It turns out that our algorithm achieve very good results in terms of both time efficiency and number of character inspections, especially in the cases in which the patterns are very short.

关键词： string matching experimental algorithms text processing

来源：评论

学校读者我要写书评

暂无评论

Sampling strategies for mining in data-scarce domains

引用

COMPUTING IN SCIENCE & ENGINEERING 2002年第4期4卷 31-43页

作者： Ramakrishnan, N Bailey-Kellogg, C Virginia Polytech Inst & State Univ Dept Comp Sci Blacksburg VA 24061 USA Purdue Univ Dept Comp Sci W Lafayette IN 47907 USA

A novel framework leverages physical properties for mining in data-scarce domains. It interleaves bottom-up data mining with top-down data collection, leading to effective and explainable sampling strategies.

关键词： Data Mining Sampling Experiment Design Qualitative Reasoning experimental algorithms

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Engineering Quicksort

引用

COMPUTER LANGUAGES 1996年第1期22卷 39-47页

作者： Sarwar, SM Sarwar, SA Jaragh, MHA Brandeburg, J NEW YORK INST TECHNOL ACAD COMP LABSOLD WESTBURYNY 11568 KUWAIT UNIV FAC ENGN & PETRDEPT ELECT & COMP ENGNSAFAT 13060KUWAIT

This paper describes the results of a large empirical study to measure the run-time behavior of Quicksort by using various methods of computing the pivot element for medium to large size randomly generated integer data. The results of our study contradict the common notion that Quicksort gives best performance if median of three scheme is used to compute the pivot element and array partitions having <10 elements are sorted by using insertion sort. It was found that Quicksort performs best when median of three scheme is used to decide the pivot element and arrays with <4 elements are hand sorted. Our method gives an average speedup of >9% when compared to the method with a cutoff of 10 and sub-arrays with <10 elements insertion sorted for 1000 less than or equal to N less than or equal to 1.5 x 10(6). Our study shows that advanced hardware features allow for implementation of very fast codes for sorting small arrays, and using such codes instead of insertion sort can lead to substantial improvements for Quicksort, as conjectured by Sedgewick many years ago. Copyright (C) 1996 Elsevier Science Ltd

关键词： experimental algorithms sorting algorithms Quicksort

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：