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

Vectorizations of randomized matching for run-length coded strings

PATTERN RECOGNITION LETTERS 1997年第1期18卷 63-72页

作者： Chung, KL Yan, WM NATL TAIWAN UNIV DEPT COMP SCI & INFORMAT ENGNTAIPEI 10764TAIWAN

Matching run-length coded strings (RLCSs) is very important in the field of pattern recognition. This paper considers the design of vectorized matching algorithms that operate directly on RLCSs. We first modify the algorithm of Karp and Rabin (1987) to design a linear-time randomized matching algorithm for RLCSs. Following this algorithm, two new and fast vectorized algorithms are presented. The first one is off-line and the second one is on-line. Some experiments are carried out on a GRAY X-MP EA/116se vector supercomputer to demonstrate the good performance of our vectorized algorithms. (C) 1997 Elsevier Science B.V.

关键词： pattern matching randomized algorithms vectorized algorithms run-length coded strings error probability vector supercomputer

来源：评论

学校读者我要写书评

暂无评论

A new probabilistic analysis of Karger's randomized algorithm for minimum cut problems

引用

INFORMATION PROCESSING LETTERS 1997年第5期64卷 255-261页

作者： Dai, Y Iwano, K Katoh, N Kyoto Univ Dept Architecture & Architectural Syst Sakyo Ku Kyoto 60601 Japan Tokyo Inst Technol Dept Math & Comp Sci Meguro Ku Tokyo 152 Japan IBM Japan Ltd Tokyo Res Lab Kanagawa 242 Japan

Recently Karger proposed a new randomized algorithm for finding a minimum cut of an n-vertex graph (weighted or unweighted) with probability Omega(n(-2)). In this paper we present a new probabilistic analysis of Karger's randomized algorithm for a few classes of unweighted graphs. For random graphs whose edges are selected with a given probability p, (log n)/n less than or equal to p less than or equal to 1, we show that the expectation of success probability of the algorithm is Omega(p/n). We also investigate a class of graphs with special structure that consists of two n-cliques and gamma(n - 1) edges between the two cliques, Here gamma is a parameter satisfying 0 < gamma < 1 that makes these gamma(n - 1) edges a unique minimum cut. We show that the algorithm finds the unique minimum cut with probability n(gamma/n(gamma)). (C) 1997 Elsevier Science B.V.

关键词： randomized algorithms probabilistic analysis minimum cut minimum range cut

来源：评论

学校读者我要写书评

暂无评论

Heuristic and randomized optimization for the join ordering problem

引用

VLDB Journal 1997年第3期6卷 191-208页

作者： Steinbrunn, Michael Moerkotte, Guido Kemper, Alfons Universität Passau Fak. für Math. und Informatik D-94030 Passau Germany Universität Mannheim Lehrst. Praktische Informatik III D-68131 Mannheim Germany

Recent developments in database technology, such as deductive database systems, have given rise to the demand for new, cost-effective optimization techniques for join expressions. In this paper many different algorithms that compute approximate solutions for optimizing join orders are studied since traditional dynamic programming techniques are not appropriate for complex problems. Two possible solution spaces, the space of left-deep and bushy processing trees, are evaluated from a statistical point of view. The result is that the common limitation to left-deep processing trees is only advisable for certain join graph types. Basically, optimizers from three classes are analysed: heuristic, randomized and genetic algorithms. Each one is extensively scrutinized with respect to its working principle and its fitness for the desired application. It turns out that randomized and genetic algorithms are well suited for optimizing join expressions. They generate solutions of high quality within a reasonable running time. The benefits of heuristic optimizers, namely the short running time, are often outweighed by merely moderate optimization performance.

关键词： Genetic algorithms Heuristic algorithms Join ordering Query optimization randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Doubly logarithmic communication algorithms for optical-communication parallel computers

引用

SIAM JOURNAL ON COMPUTING 1997年第4期26卷 1100-1119页

作者： Goldberg, LA Jerrum, M Leighton, T Rao, S SANDIA NATL LABS LIVERMORE CA 94550 USA UNIV EDINBURGH DEPT COMP SCI EDINBURGH EH9 3JZ MIDLOTHIAN SCOTLAND NEC RES INST PRINCETON NJ 08540 USA MIT DEPT MATH CAMBRIDGE MA 02139 USA MIT COMP SCI LAB CAMBRIDGE MA 02139 USA

In this paper, we consider the problem of interprocessor communication on parallel computers that have optical communication networks. We consider the completely connected optical-communication parallel computer (OCPC), which has a completely connected optical network, and also the mesh-of-optical-buses parallel computer (MOB-PC), which has a mesh of optical buses as its communication network. The particular communication problem that we study is that of realizing an h-relation. In this problem, each processor has at most h messages to send and at most h messages to receive. It is clear that any 1-relation can be realized in one communication step on an OCPC. However, the best previously known p-processor OCPC algorithm for realizing an arbitrary h-relation for h > 1 requires -(h + log p) expected communication steps. (This algorithm is due to Valiant and is based on earlier work of Anderson and Miller.) Valiant's algorithm is optimal only for h = Omega(log p), and it is an open question of Gereb-Graus and Tsantilas whether there is a faster algorithm for h = Omega(log p). In this paper, we answer this question in the affirmative and we extend the range of optimality by considering the case in which h less than or equal to log p. In particular, we present a -(h + log log p)-communication-step randomized algorithm that realizes an arbitrary h-relation on a p-processor OCPC. We show that if h less than or equal to log p, then the failure probability can be made as small as p(-alpha) for any positive constant alpha. We use the OCPC algorithm as a subroutine in a -(h + log log p)communication-step randomized algorithm that realizes an arbitrary h-relation on a p x p-processor MOB-PC. Once again, we show that if h less than or equal to log p, then the failure probability can be made as small as p(-alpha) for any positive constant alpha.

关键词： parallel algorithms randomized algorithms routing optical networks

来源：评论

学校读者我要写书评

暂无评论

Parallel algorithms for the Hamiltonian cycle and Hamiltonian path problems in semicomplete bipartite digraphs

引用

ALGORITHMICA 1997年第1期17卷 67-87页

作者： BangJensen, J ElHaddad, M Manoussakis, Y Przytycka, TM UNIV PARIS 11 LRIF-91405 ORSAYFRANCE

We give an O (log(4) n)-time O(n(2))-processor CRCW PRAM algorithm to find a hamiltonian cycle in a strong semicomplete bipartite digraph, B, provided that a factor of B (i.e., a collection of vertex disjoint cycles covering the vertex set of B)is computed in a preprocessing step. The factor is found (if it exists) using a bipartite matching algorithm, hence placing the whole algorithm in the class Random-NC. We show that any parallel algorithm which can check the existence of a hamiltonian cycle in a strong semicomplete bipartite digraph in time O(r(n)) using p(n) processors can be used to check the existence of a perfect matching in a bipartite graph in time O(r(n) + n(2)/p(n)) using p(n) processors. Hence, our problem belongs to the class NC if and only if perfect matching in bipartite graphs belongs to NC. We also consider the problem of finding a hamiltonian path in a semicomplete bipartite digraph.

关键词： graph algorithms Hamilton cycle parallel algorithms semicomplete bipartite graphs randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Practical algorithms for selection on coarse-grained parallel computers

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 1997年第8期8卷 813-824页

作者： AlFuriah, I Aluru, S Goil, S Ranka, S NEW MEXICO STATE UNIV DEPT COMP SCILAS CRUCESNM 88003 NORTHWESTERN UNIV DEPT COMP SCIEVANSTONIL UNIV FLORIDA SCH COMP & INFORMAT SCI & ENGNGAINESVILLEFL

In this paper, we consider the problem of selection on coarse-grained distributed memory parallel computers. We discuss several deterministic and randomized algorithms for parallel selection. We also consider several algorithms for load balancing needed to keep a balanced distribution of data across processors during the execution of the selection algorithms. We have carried out detailed implementations of all the algorithms discussed on the CM-5 and report on the experimental results. The results clearly demonstrate the role of randomization in reducing communication overhead.

关键词： coarse-grained hypercubes load balancing median finding meshes randomized algorithms selection parallel algorithms parallel computers

来源：评论

学校读者我要写书评

暂无评论

Revisiting the COUNTER algorithms for list update

引用

INFORMATION PROCESSING LETTERS 1997年第3期64卷 155-160页

作者： Albers, S Mitzenmacher, M DIGITAL EQUIPMENT CORP SYST RES CTRPALO ALTOCA 94301

COUNTER algorithms, a family of randomized algorithms for the list update problem, were introduced by Reingold, Westbrook, and Sleator (1994). They showed that for any epsilon > 0, there exist COUNTER algorithms that achieve a competitive ratio of root 3 + epsilon. In this paper we use a mixture of two COUNTER algorithms to achieve a competitiveness of 12/7, which is less than root 3. Furthermore, we demonstrate that it is impossible to prove a competitive ratio smaller than 12/7 for any mixture of COUNTER algorithms using the type of potential function argument that has been used so far. We also provide new lower bounds for the competitiveness of COUNTER algorithms in the standard cost model, including a 1.625 lower bound for the variant BIT and a matching 12/7 lower bound for our algorithm. (C) 1997 Elsevier Science B.V.

关键词： list update on-line algorithms randomized algorithms data structures

来源：评论

学校读者我要写书评

暂无评论

A spectrum of time-space trade-offs for undirected s-t connectivity

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 1997年第2期54卷 305-316页

作者： Feige, U WEIZMANN INST SCI DEPT APPL MATH IL-76100 REHOVOT ISRAEL

We present a family of randomized algorithms that enjoys a wide range of time-space trade-offs in deciding undirected S-T-connectivity. Our trade-offs cover the whole range between breadth first search and the random walk procedure of Aleliunas at al., and achieve a time-space product of (O) over tilde(mn) (where n is the number of vertices in the graph, m is the number of edges, and (O) over tilde notation is used in order to suppress logarithmic terms). Moreover, we obtain improved time-space trade-offs of (O) over tilde(n(2)) for regular graphs. A convenient and informative way of expressing our trade-offs, that implies the trade-offs stated above, is as (O) over tilde((Sigma(i=1)(n) d(i))(Sigma(i=1)(n) 1/d(i))), where d(i) is the degree of vertex i in the input graph. In constructing our algorithms and analysing them, we build upon earlier work of Broder et al. (who achieved a time-space trade-off of (O) over tilde(m(2))), Barnes and Feige (who achieved a time-space trade-off of (O) over tilde(m(3/2)n(1/2))), and Aldous. In passing, we also improve previous results regarding the rate at which a random walk discovers new vertices in a graph. (C) 1997 Academic Press.

关键词： oxygen Spectra FULL-SCALE tradeoffs randomized algorithms wide-range vertex head breadth first search Random walk

来源：评论

学校读者我要写书评

暂无评论

Computing a single cell in the overlay of two simple polygons

引用

INFORMATION PROCESSING LETTERS 1997年第4期63卷 215-219页

作者： deBerg, M Devillers, O Dobrindt, K Schwarzkopf, O UNIV UTRECHT DEPT COMP SCINL-3508 TB UTRECHTNETHERLANDS INRIA F-06902 SOPHIA ANTIPOLISFRANCE

This note combines the lazy randomized incremental construction scheme with the technique of ''connectivity acceleration'' to obtain an O(n(log(*) n)(2)) time randomized algorithm to compute a single f... 详细信息

关键词： computational geometry randomized algorithms arrangement

来源：评论

学校读者我要写书评

暂无评论

Optimal communication algorithms for heterogeneous computing over ATM networks

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 1997年第1期46卷 62-79页

作者： Wang, XD Roychowdhury, VP Princeton Univ Dept Elect Engn Princeton NJ 08544 USA Univ Calif Los Angeles Dept Elect Engn Los Angeles CA 90095 USA

We present efficient algorithms for designing optimal collective communication primitives for cluster-based heterogeneous computing across Asynchronous Transfer Mode (ATM) networks. The virtual path (VP) concept is known to be a powerful transport mechanism for ATM networks, In many parallel processing applications, the potential communication pattern is known in advance, We then seek to find an optimal set of virtual paths to realize the communication pattern, such that the communication overhead of the parallel processing application is minimized, and at the same time, the extent to which the other data traffic in the network is affected by the data traffic generated by the parallel processing application is also minimized, We consider the following four collective communication problems that occur frequently in parallel computation: one-to-all broadcast, all-to-all broadcast, one-to-all scatter, and all-to-all scatter, We formulate these problems as combinatorial optimization problems of finding a system of virtual path routes in networks, with the objectives of minimizing the path length, the link congestion, and the node copy load, We consider two cases of data sources, namely homogeneous and heterogeneous, For the case of homogeneous sources, we present polynomial-time algorithms for the problems of one-to-all broadcast, all-to-all broadcast, and one-to-all scatter, by converting these problems to the maximum-flow problems, For the case of heterogeneous sources, we show that the problems of all-to-all broadcast, one-to-all scatter, and all-to-all scatter are all NP-complete, Finally, we present novel randomized algorithms for these problems, and show that with high probability these algorithms yield good solutions in the sense that the objective functions yield values close to the optimums. The randomized algorithms can also be used to design near-optimum multicast communication primitives, These randomized algorithms make use of linear programming and are eas

关键词： ATM networks heterogeneous computing collective communications combinatorial optimization randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：