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

Towards a Realistic analysis of the QuickSelect Algorithm

THEORY OF COMPUTING SYSTEMS 2016年第4期58卷 528-578页

作者： Clement, Julien Fill, James Allen Thu Hien Nguyen Thi Vallee, Brigitte Univ Caen ENSICAEN GREYC CNRS UMR 6072 F-14032 Caen France Johns Hopkins Univ Dept Appl Math & Stat Baltimore MD 21218 USA

We revisit the analysis of the classical QuickSelect algorithm. Usually, the analysis deals with the mean number of key comparisons, but here we view keys as words produced by a source, and words are compared via their symbols in lexicographic order. Our probabilistic models belong to a broad category of information sources that encompasses memoryless (i.e., independent-symbols) and Markov sources, as well as many unbounded-correlation sources. The "realistic" cost of the algorithm is here the total number of symbol comparisons performed by the algorithm, and, in this context, the average-case analysis aims to provide estimates for the mean number of symbol comparisons. For the QuickSort algorithm, known average-case complexity results are of in the case of key comparisons, and for symbol comparisons. For QuickSelect algorithms, and with respect to key comparisons, the average-case complexity is I similar to(n). In this present article, we prove that, with respect to symbol comparisons, QuickSelect's average-case complexity remains I similar to(n). In each case, we provide explicit expressions for the dominant constants, closely related to the probabilistic behaviour of the source. We began investigating this research topic with Philippe Flajolet, and the short version of the present paper (the ICALP'2009 paper) was written with him. As usual, Philippe played a central role, notably on the following points: introduction of the QuickVal algorithm, tameness of sources, and use of Rice's method. He also made many experiments exhibiting the asymptotic slope rho(alpha) and plotted nice graphs, which are reproduced in this paper. Even though the extended abstract does not provide any proof of the analysis of the algorithm QuickQuant, Philippe also devised with us a precise plan for this proof which has now completely been written. For all these reasons, we could have added (and certainly would have liked to add) Philippe as a co-author of this paper. On the other hand, Ph

关键词： probabilistic analysis of algorithms Sorting and searching algorithms Selection problem Pattern matching Permutations Information theory Rice's method Asymptotic estimates Quickselect

来源：评论

学校读者我要写书评

暂无评论

Selection by rank in K-dimensional binary search trees

引用

RANDOM STRUCTURES & algorithms 2014年第1期45卷 14-37页

作者： Duch, Amalia Jimenez, Rosa M. Martinez, Conrado Univ Politecn Cataluna Dept Llenguatges & Sistemes Informat E-08034 Barcelona Spain

In this work we show how to augment general purpose multidimensional data structures, such as K-d trees, to efficiently support search by rank (that is, to locate the i-th smallest element along the j-th coordinate, for given i and j) and to find the rank of a given item along a given coordinate. To do so, we introduce two simple, practical and very flexible algorithms - Select-by-Rank and Find-Rank - with very little overhead. Both algorithms can be easily implemented and adapted to several spatial indexes, although their analysis is far from trivial. We are able to show that for random K-d trees of size n the expected number of nodes visited by Find-Rank is Pn,i=(n1-1/K) for i=o(n) or i=n-o(n), and Pn,i=fK(i/n)center dot n+o(n) for i=xn+o(n) (with 0algorithms. As a byproduct of the analysis of our algorithms, but no less important, we give the average-case analysis of a partial match search in random K-d trees when the query is not random. (c) 2012 Wiley Periodicals, Inc. Random Struct. Alg., 45, 14-37, 2014

关键词： Multidimensional data structures selection K-dimensional search trees partial match probabilistic analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

ON TAIL BOUNDS FOR RANDOM RECURSIVE TREES

引用

JOURNAL OF APPLIED PROBABILITY 2012年第2期49卷 566-581页

作者： Munsonius, Goetz Olaf Goethe Univ Frankfurt Inst Math D-60054 Frankfurt Germany

We consider a multivariate distributional recursion of sum type, as arises in the probabilistic analysis of algorithms and random trees. We prove an upper tail bound for the solution using Chernoff's bounding technique by estimating the Laplace transform. The problem is traced back to the corresponding problem for binary search trees by stochastic domination. The result obtained is applied to the internal path length and Wiener index of random b-ary recursive trees with weighted edges and random linear recursive trees. Finally, lower tail bounds for the Wiener index of these trees are given.

关键词： Random tree probabilistic analysis of algorithms tail bound path length Wiener index

来源：评论

学校读者我要写书评

暂无评论

Distances Between Pairs of Vertices and Vertical Profile in Conditioned Galton-Watson Trees

引用

RANDOM STRUCTURES & algorithms 2011年第4期38卷 381-395页

作者： Devroye, Luc Janson, Svante Uppsala Univ Dept Math SE-75106 Uppsala Sweden McGill Univ Sch Comp Sci Montreal PQ H3A 2K6 Canada

We consider a conditioned Galton-Watson tree and prove an estimate of the number of pairs of vertices with a given distance, or, equivalently, the number of paths of a given length. We give two proofs of this result, one probabilistic and the other using generating functions and singularity analysis. Moreover, the latter proof yields a more general estimate for generating functions, which is used to prove a conjecture by Bousquet-Melou and Janson (Bousquet-Melou and Janson, Ann Appl Probab 16 (2006) 1597-1632), saying that the vertical profile of a randomly labelled conditioned Galton-Watson tree converges in distribution, after suitable normalization, to the density of ISE (Integrated Superbrownian Excursion). (C) 2010 Wiley Periodicals, Inc. Random Struct. Alg., 38, 381-395, 2011

关键词： random Galton-Watson tree paths of given length vertical profile probabilistic analysis of algorithms branching process

来源：评论

学校读者我要写书评

暂无评论

A note on the probability of cutting a Galton-Watson tree

引用

ELECTRONIC JOURNAL OF PROBABILITY 2011年第none期16卷 2001-2019页

作者： Devroye, Luc McGill Univ Sch Comp Sci Montreal PQ H3A 2K6 Canada

The structure of Galton-Watson trees conditioned to be of a given size is well-understood. We provide yet another embedding theorem that permits us to obtain asymptotic probabilities of events that are determined by what happens near the root of these trees. As an example, we derive the probability that a Galton-Watson tree is cut when each node is independently removed with probability p, where by cutting a tree we mean that every path from root to leaf must have at least one removed node.

关键词： Random Galton-Watson tree probabilistic analysis of algorithms branching process

来源：评论

学校读者我要写书评

暂无评论

On the asymptotic internal path length and the asymptotic Wiener index of random split trees

引用

ELECTRONIC JOURNAL OF PROBABILITY 2011年第none期16卷 1020-1047页

作者： Munsonius, Goetz Olaf Goethe Univ Frankfurt Inst Math D-60054 Frankfurt Germany

The random split tree introduced by Devroye (1999) is considered. We derive a second order expansion for the mean of its internal path length and furthermore obtain a limit law by the contraction method. As an assumption we need the splitter having a Lebesgue density and mass in every neighborhood of 1. We use properly stopped homogeneous Markov chains, for which limit results in total variation distance as well as renewal theory are used. Furthermore, we extend this method to obtain the corresponding results for the Wiener index.

关键词： random trees probabilistic analysis of algorithms internal path length Wiener index

来源：评论

学校读者我要写书评

暂无评论

On the k-orientability of random graphs

引用

DISCRETE MATHEMATICS 2009年第6期309卷 1476-1490页

作者： Devroye, Luc Malalla, Ebrahim King Fahd Univ Petr & Minerals Dept Informat & Comp Sci Dhahran 31261 Saudi Arabia McGill Univ Sch Comp Sci Montreal PQ H3A 2K6 Canada

Let G(n, m) be an undirected random graph with n vertices and m multiedges that may include loops, where each edge is realized by choosing its two vertices independently and uniformly at random with replacement from the set of all n vertices. The random graph G(n, m) is said to be k-orientable, where k >= 2 is an integer, if there exists an orientation of the edges such that the maximum out-degree is at most k. Let c(k) = sup {c : G(n, cn) is k-orientable w.h.p.}. We prove that for k large enough, 1 - 2(k) exp (-k + 1 + e(-k/4)) < c(k)/k < 1 - exp (-2k (1 - e(-2k))), and the time c(k)n is a threshold for the emergence of a giant subgraph of size (-)(n) whose edges are more than k times its vertices. Other results are presented. (C) 2008 Elsevier B.V. All rights reserved.

关键词： Random graphs k-orientability k-core Maximum density Static two-way chaining Off-line load balancing Competitive analysis probabilistic analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

Formal verification of tail distribution bounds in the HOL theorem prover

引用

MATHEMATICAL METHODS IN THE APPLIED SCIENCES 2009年第4期32卷 480-504页

作者： Hasan, Osman Tahar, Sofiene Concordia Univ Montreal PQ H3G 1M8 Canada

Tail distribution bounds play a major role in the estimation of failure probabilities in performance and reliability analysis of systems. They are usually estimated using Markov's and Chebyshev's inequalities, which represent tail distribution bounds for a random variable in terms of its mean or variance. This paper presents the formal verification of Markov's and Chebyshev's inequalities for discrete random variables using a higher-order-logic theorem prover. The paper also provides the formal verification of mean and variance relations for some of the widely used discrete random variables, such as Uniform(m), Bernoulli(p), Geometric(p) and Binomial(m, p) random variables. This infrastructure allows us to precisely reason about the tail distribution properties and thus turns out to be quite useful for the analysis of systems used in safety-critical domains, such as space, medicine or transportation. For illustration purposes, we present the performance analysis of the coupon collector's problem, a well-known commercially used algorithm. Copyright (C) 2008 John Wiley & Sons, Ltd.

关键词： higher-order logic mechanization of proofs probabilistic analysis of algorithms probability theory theorem proving

来源：评论

学校读者我要写书评

暂无评论

DYNAMIC PROGRAMMING OPTIMIZATION OVER RANDOM DATA: THE SCALING EXPONENT FOR NEAR-OPTIMAL SOLUTIONS

引用

SIAM JOURNAL ON COMPUTING 2009年第6期38卷 2382-2410页

作者： Aldous, David J. Bordenave, Charles Lelarge, Marc Univ Calif Berkeley Dept Stat Berkeley CA 94270 USA Univ Toulouse F-31062 Toulouse France CNRS Inst Math Toulouse F-31062 Toulouse France INRIA ENS F-75005 Paris France

A very simple example of an algorithmic problem solvable by dynamic programming is to maximize, over A subset of {1, 2,..., n}, the objective function |A|-Sigma(i)xi(i)1(i is an element of A, i + 1 is an element of A) for given xi(i) > 0. This problem, with random (xi(i)), provides a test example for studying the relationship between optimal and near-optimal solutions of combinatorial optimization problems. We show that, amongst solutions differing from the optimal solution in a small proportion delta of places, we can find near-optimal solutions whose objective function value differs from the optimum by a factor of order delta(2) but not of smaller order. We conjecture this relationship holds widely in the context of dynamic programming over random data, and Monte Carlo simulations for the Kauffman-Levin NK model are consistent with the conjecture. This work is a technical contribution to a broad program initiated in [D. J. Aldous and A. G. Percus, Proc. Natl. Acad. Sci. USA, 100 (2003), pp. 11211-11215] of relating such scaling exponents to the algorithmic difficulty of optimization problems.

关键词： dynamic programming local weak convergence Markov chain near-optimal solutions optimization probabilistic analysis of algorithms scaling exponent

来源：评论

学校读者我要写书评

暂无评论

Multiple Choice Tries and Distributed Hash Tables

引用

RANDOM STRUCTURES & algorithms 2009年第3期34卷 337-367页

作者： Devroye, Luc Lugosi, Gabor Park, Gahyun Szpankowski, Wojciech McGill Univ Sch Comp Sci Montreal PQ H3A 2K6 Canada Univ Pompeu Fabra ICREA Barcelona Spain Univ Pompeu Fabra Dept Econ Barcelona Spain Purdue Univ Dept Comp Sci W Lafayette IN 47907 USA

In this article we consider tries built from n strings such that each string can be chosen from a pool of k strings, each of them generated by a discrete i.i.d. source. Three cases are considered: k = 2, k is large but fixed, and k similar to c log n. The goal in each case is to obtain tries as balanced as possible. Various parameters such as height and fill-up level are analyzed. It is shown that for two-choice tries a 50% reduction in height is achieved when compared with ordinary tries. In a greedy online construction when the string that minimizes the depth of insertion for every pair is inserted, the height is only reduced by 25%. To further reduce the height by another 25%, we design a more refined online algorithm. The total computation time of the algorithm is O(n log n). Furthermore, when we choose the best among k >= 2 strings, then for large but fixed k the height is asymptotically equal to the typical depth in a trie. Finally, we show that further improvement can be achieved if the number of choices for each string is proportional to log n. In this case highly balanced trees can be constructed by a simple greedy algorithm for which the difference between the height and the fill-up level is bounded by a constant with high probability. This, in turn, has implications for distributed hash tables, leading to a randomized ID management algorithm in peer-to-peer networks such that, with high probability, the ratio between the maximum and the minimum load of a processor is O(1). (C) 2008 Wiley Periodicals, Inc. Random Struct. Mg.. 34, 337-367, 2009

关键词： random tries random data structures probabilistic analysis of algorithms algorithms on sequences distributed hash tables

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：