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

A randomized approximate nearest neighbors algorithm

APPLIED AND COMPUTATIONAL HARMONIC ANALYSIS 2013年第3期34卷 415-444页

作者： Jones, Peter W. Osipov, Andrei Rokhlin, Vladimir Yale Univ Dept Math & Comp Sci New Haven CT 06511 USA

We present a randomized algorithm for the approximate nearest neighbor problem in d-dimensional Euclidean space. Given N points {x(j)} in R-d, the algorithm attempts to find k nearest neighbors for each of x(j), where k is a user-specified integer parameter. The algorithm is iterative, and its CPU time requirements are proportional to T . N . (d . (log d) + k . (d + logk) . (log N)) + N . k(2) . (d + logk), with T the number of iterations performed. The memory requirements of the procedure are of the order N . (d + k). A byproduct of the scheme is a data structure, permitting a rapid search for the k nearest neighbors among {x(j)} for an arbitrary point x is an element of R-d. The cost of each such query is proportional to T . (d . (log d) + log(N/k) . k . (d + logk)), and the memory requirements for the requisite data structure are of the order N . (d + k) + T . (d + N). The algorithm utilizes random rotations and a basic divide-and-conquer scheme, followed by a local graph search. We analyze the scheme's behavior for normally distributed points {x(j)}, and illustrate its performance via several numerical examples. (C) 2012 Elsevier Inc. All rights reserved.

关键词： Approximate nearest neighbors randomized algorithms Fast random rotations

来源：评论

学校读者我要写书评

暂无评论

A sequentially optimal randomized algorithm for robust feasibility problems

引用

REVISTA IBEROAMERICANA DE AUTOMATICA E INFORMATICA INDUSTRIAL 2013年第1期10卷 50-61页

作者： Alamo, T. Tempo, R. Ramirez, D. R. Luque, A. Camacho, E. F. Univ Seville Escuela Tecn Super Ingn Dpto Ingn Sistemas & Automat Seville 41092 Spain Politecn Torino IEIIT CNR I-10129 Turin Italy

This paper proposes a randomized algorithm for feasibility of uncertain LMIs. The algorithm is based on the solution of a sequence of semidefinite optimization problems involving a reduced number of constraints. A bound of the maximum number of iterations required by the algorithm is given. Finally, the performance and behaviour of the algorithm are illustrated by means of a numerical example.

关键词： robust feasibility linear matrix inequalities randomized algorithms robust control

来源：评论

学校读者我要写书评

暂无评论

A randomized Partitioning Approach for CBR-Based Autonomic Systems to Improve Retrieval Performance

引用

COMPUTER JOURNAL 2013年第2期56卷 175-183页

作者： Khan, Malik Jahan Awais, Mian Muhammad Shamail, Shafay Lahore Univ Management Sci Dept Comp Sci Lahore Pakistan

Autonomic systems exhibit self-managing behavior using various algorithms. Case-based reasoning is one the techniques that enable the autonomic manager to learn from past experience. Case-base is partitioned into some clusters in order to improve the retrieval efficiency. Deciding an appropriate number of clusters for a case-base is not a trivial problem. This paper proposes a randomized algorithm for determining the number of clusters to be formed of the case-base. Subsequently, a binary search-based case retrieval strategy has been applied to ensure enhanced retrieval time performance. The paper presents two versions of the randomized algorithm. The first version guarantees success but its computational cost is a function of random variable;the other guarantees a deterministic computational cost but success is not guaranteed. The performance of the proposed algorithms has been reported on a simulated case study of the Autonomic Forest Fire Application.

关键词： autonomic systems case-based reasoning clustering randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

A lower-variance randomized algorithm for approximate string matching

引用

INFORMATION PROCESSING LETTERS 2013年第18期113卷 690-692页

作者： Atallah, Mikhail J. Grigorescu, Elena Wu, Yi Purdue Univ Dept Comp Sci W Lafayette IN 47907 USA

Several randomized algorithms make use of convolution to estimate the score vector of matches between a text string of length N and a pattern string of length M, i.e., the vector obtained when the pattern is slid along the text, and the number of matches is counted for each position. These algorithms run in deterministic time O (kN log M), and find an unbiased estimator of the scores whose variance is (M - c)(2)/k where c is the actual score;here k is an adjustable parameter that provides a tradeoff between computation time and lower variance. This paper provides an algorithm that also runs in deterministic time O (kN log M) but achieves a lower variance of min(M/k, M - c)(M - c)/k. For all score values c that are less than M - (M/k), our variance is essentially a factor of k smaller than in previous work, and for M - (M/k) < c <= M it matches the previous work's variance. As in the previous work, our estimator is unbiased, and we make no assumption about the probabilistic characteristics of the input, or about the size of the alphabet, and our solution extends to string matching with classes, class complements, "never match" and "always match" symbols, to the weighted case and to higher dimensions. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Convolution FFT Approximate string matching randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Proofs of randomized algorithms in COQ

引用

8th International Conference on Mathematics of Program Construction

作者： Audebaud, Philippe Paulin-Mohring, Christine INRIA Saclay Ile France F-91893 Orsay France Ecole Normale Super Lyon LIP F-69437 Lyon France CNRS F-91405 Orsay France Univ Paris Sud LRI F-91405 Orsay France

ISBN: (纸本)3540356312

randomized algorithms are widely used for finding efficiently approximated solutions to complex problems, for instance primality testing and for obtaining good average behavior. Proving properties of such algorithms requires subtle reasoning both on algorithmic and probabilistic aspects of programs. Thus, providing tools for the mechanization of reasoning is an important issue. This paper presents a new method for proving properties of randomized algorithms in a proof assistant based on higher-order logic. It is based on the monadic interpretation of randomized programs as probabilistic distributions (Giry, Ramsey and Pfeffer). It does not require the definition of an operational semantics for the language nor the development of a complex formalization of measure theory. Instead it uses functional and algebraic properties of unit interval. Using this model, we show the validity of general rules for estimating the probability for a randomized algorithm to satisfy specified properties. This approach addresses only discrete distributions and gives rules for analyzing general recursive functions. We apply this theory to the formal proof of a program implementing a Bernoulli distribution from a coin flip and to the (partial) termination of several programs. All the theories and results presented in this paper have been fully formalized and proved in the CoQ proof assistant. (C) 2009 Elsevier B.V. All rights reserved.

关键词： randomized algorithms Proof of partial and total correctness Functional language Axiomatic semantics Probability framing Call-by-value Monadic interpretation

来源：评论

学校读者我要写书评

暂无评论

Discontinuous information in the worst case and randomized settings

引用

MATHEMATISCHE NACHRICHTEN 2013年第7期286卷 679-690页

作者： Hinrichs, Aicke Novak, Erich Wozniakowski, Henryk Univ Jena Math Inst D-07737 Jena Germany Columbia Univ Dept Comp Sci New York NY 10027 USA Univ Warsaw Inst Appl Math PL-02097 Warsaw Poland

We believe that discontinuous linear information is never more powerful than continuous linear information for approximating continuous operators. We prove such a result in the worst case setting. In the randomized setting we consider compact linear operators defined between Hilbert spaces. In this case, the use of discontinuous linear information in the randomized setting cannot be much more powerful than continuous linear information in the worst case setting. These results can be applied when function evaluations are used even if function values are defined only almost everywhere. (C) 2012 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim

关键词： Discontinuous information randomized algorithms information-based complexity

来源：评论

学校读者我要写书评

暂无评论

Finding orthogonal vectors in discrete structures 14

Finding orthogonal vectors in discrete structures

引用

Annual ACM-Society for Industrial and Applied Mathmatics Symposium on Discrete algorithms

作者： Ryan Williams Huacheng Yu Computer Science Department Stanford University

ISBN: (纸本)9781611973389

Hopcroft's problem in d dimensions asks: given n points and n hyperplanes in R~d, does any point lie on any hyperplane? Equivalently, if we are given two sets of n vectors each in R~(d+1), is there a pair of vectors (one from each set) that are orthogonal? This problem has a long history and a multitude of applications. It is widely believed that for large d, the problem is subject to the curse of dimensionality: all known algorithms need at least f(d) · n~(2-1/O(d)) time for fast-growing functions f, and at the present time there is little hope that a n-2ε, poly(d) time algorithm will be found. We consider Hopcroft's problem over finite fields and integers modulo composites, leading to both surprising algorithms and hardness reductions. The algorithms arise from studying the communication problem of determining whether two lists of vectors (one list held by Alice, one by Bob) contain an orthogonal pair of vectors over a discrete structure (one from each list). We show the randomized communication complexity of the problem is closely related to the sizes of matching vector families, which have been studied in the design of locally decodable codes. Letting HOPCROFT_R denote Hopcroft's problem over a ring R, we give randomized algorithms and almost matching lower bounds (modulo a breakthrough in SAT algorithms) for HOPCROFT_R, when R is the ring of integers modulo m or a finite field. Building on the ideas developed here, we give a very simple and efficient output-sensitive algorithm for matrix multiplication that works over any field.

关键词： orthogonal vector Matrix multiplication R-RING Galois fields algorithms Modulo able to communicate Integer PDE6B gene communication complexity randomized algorithms Curse of Dimensionality Hyperplane Cloning Vectors Pairing

来源：评论

学校读者我要写书评

暂无评论

Four Soviets Walk the Dog - with an Application to Alt's Conjecture 14

Four Soviets Walk the Dog - with an Application to Alt's Con...

引用

Annual ACM-SIAM Symposium on Discrete algorithms

作者： Kevin Buchin Maike Buchin Wouter Meulemans Wolfgang Mulzer TU Eindhoven The Netherlands Ruhr Universität Bochum Germany Freie Universität Berlin Germany

ISBN: (纸本)9781611973389

Given two polygonal curves in the plane, there are many ways to define a notion of similarity between them. One measure that is extremely popular is the Frechet distance. Since it has been proposed by Alt and Godau in 1992, many variants and extensions have been studied. Nonetheless, even more than 20 years later, the original O(n~2log n) algorithm by Alt and Godau for computing the Frechet distance remains the state of the art (here n denotes the number of vertices on each curve). This has led Helmut Alt to conjecture that the associated decision problem is 3SUM-hard. In recent work, Agarwal et al. show how to break the quadratic barrier for the discrete version of the Frechet distance, where one considers sequences of points instead of polygonal curves. Building on their work, we give a randomized algorithm to compute the Frechet distance between two polygonal curves in time O(n~2(log n)~(1/2)(log log n)~(3/2)) on a pointer machine and in time O(n~2(log log n)~2) on a word RAM. Furthermore, we show that there exists an algebraic decision tree for the decision problem of depth O(n~(2-ε)), for some ε > 0. This provides evidence that the decision problem may not be 3SUM-hard after all and reveals an intriguing new aspect of this well-studied problem.

关键词： Decision problem Conjecture state of the art Canis familiaris randomized algorithms Decision Trees

来源：评论

学校读者我要写书评

暂无评论

(Nearly) Sample-Optimal Sparse Fourier Transform 14

(Nearly) Sample-Optimal Sparse Fourier Transform

引用

Annual ACM-Society for Industrial and Applied Mathmatics Symposium on Discrete algorithms

作者： Piotr Indyk Michael Kapralov Eric Price MIT

ISBN: (纸本)9781611973389

We consider the problem of computing a k-sparse approximation to the discrete Fourier transform of an n-dimensional signal. Our main result is a randomized algorithm that computes such an approximation using O(k log n(log log n)~(O(1))) signal samples in time O(k log~2 n(log log n)~(O(1))), assuming that the entries of the signal are polynomially bounded. The sampling complexity improves over the recent bound of O(k log n log(n=k)) given in [15], and matches the lower bound of Ω(k log(n=k)= log log n) from the same paper up to poly(log log n) factors when k = O(n~(1-δ)) for a constant δ > 0.

关键词： Fourier Transform logs logarithm (log) randomized algorithms discrete Fourier transform

来源：评论

学校读者我要写书评

暂无评论

A Cubic Algorithm for Computing Gaussian Volume 14

A Cubic Algorithm for Computing Gaussian Volume

引用

Annual ACM-Society for Industrial and Applied Mathmatics Symposium on Discrete algorithms

作者： Ben Cousins Santosh Vempala Georgia Tech.

ISBN: (纸本)9781611973389

We present randomized algorithms for sampling the standard Gaussian distribution restricted to a convex set and for estimating the Gaussian measure of a convex set, in the general membership oracle model. The complexity of the integration algorithm is O*(n~3) while the complexity of the sampling algorithm is O*(n~3) for the first sample and O*(n~2) for every subsequent sample. These bounds improve on the corresponding state-of-the-art by a factor of n. Our improvement comes from several aspects: better isoperimetry, smoother annealing, avoiding trans-formation to isotropic position and the use of the "speedy walk" in the analysis.

关键词： integral algorithm randomized algorithms Convexity Gaussian distribution Gauss Cubic Corresponding states algorithms Information retrieval systems-Teletext and videotex

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：