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

On Approximating the Stationary Distribution of Time-Reversible Markov Chains

THEORY OF COMPUTING SYSTEMS 2020年第3期64卷 444-466页

作者： Bressan, Marco Peserico, Enoch Pretto, Luca Sapienza Univ Roma Dipartimento Informat Rome Italy Univ Padua Dipartimento Ingn Informaz Padua Italy

Approximating the stationary probability of a state in a Markov chain through Markov chain Monte Carlo techniques is, in general, inefficient. Standard random walk approaches require & xd5;(tau/pi(v))operations to approximate the probability pi(v) of a state v in a chain with mixing time tau, and even the best available techniques still have complexity & xd5;(tau 1.5/pi(v)0.5) and since these complexities depend inversely on pi(v), they can grow beyond any bound in the size of the chain or in its mixing time. In this paper we show that, for time-reversible Markov chains, there exists a simple randomized approximation algorithm that breaks this "small-pi(v) barrier".

关键词： Markov chains MCMC sampling Large graph algorithms Randomized algorithms sublinear algorithms

来源：评论

学校读者我要写书评

暂无评论

TRIGGER DETECTION FOR ADAPTIVE SCIENTIFIC WORKFLOWS USING PERCENTILE SAMPLING

引用

SIAM JOURNAL ON SCIENTIFIC COMPUTING 2016年第5期38卷 S240-S263页

作者： Bennettt, Janine C. Bhagatwala, Ankit Chen, Jacqueline H. Pinar, Ali Salloum, Maher Seshadhri, C. Sandia Natl Labs Livermore CA 94550 USA Lawrence Berkeley Natl Lab Berkeley CA 94720 USA Univ Calif Santa Cruz Dept Comp Sci Santa Cruz CA 95064 USA

The increasing complexity of both scientific simulations and high-performance computing system architectures are driving the need for adaptive workflows, in which the composition and execution of computational and data manipulation steps dynamically depend on the evolutionary state of the simulation itself. Consider, for example, the frequency of data storage. Critical phases of the simulation should be captured with high frequency and with high fidelity for postanalysis;however, we cannot afford to retain the same frequency for the full simulation due to the high cost of data movement. We can instead look for triggers, indicators that the simulation will be entering a critical phase, and adapt the workflow accordingly. In this paper, we present a methodology for detecting triggers and demonstrate its use in the context of direct numerical simulations of turbulent combustion using S3D. We show that chemical explosive mode analysis (CEMA) can be used to devise a noise-tolerant indicator for rapid increase in heat release. However, exhaustive computation of CEMA values dominates the total simulation, and thus is prohibitively expensive. To overcome this computational bottleneck, we propose a quantile sampling approach. Our sampling-based algorithm comes with provable error/confidence bounds, as a function of the number of samples. Most importantly, the number of samples is independent of the problem size, and thus our proposed sampling algorithm offers perfect scalability. Our experiments on homogeneous charge compression ignition and reactivity controlled compression ignition simulations show that the proposed method can detect rapid increases in heat release, and its computational overhead is negligible. Our results will be used to make dynamic workflow decisions regarding data storage and mesh resolution in future combustion simulations.

关键词： sublinear algorithms quantile sampling in situ data analysis chemical explosive mode analysis (CEMA) S3D adaptive workflow judicious I/O

来源：评论

学校读者我要写书评

暂无评论

Is Submodularity Testable?

引用

ALGORITHMICA 2014年第1期69卷 1-25页

作者： Seshadhri, C. Vondrak, Jan Sandia Natl Labs Livermore CA 94550 USA IBM Almaden Res Ctr San Jose CA USA

We initiate the study of property testing of submodularity on the boolean hypercube. Submodular functions come up in a variety of applications in combinatorial optimization. For a vast range of algorithms, the existence of an oracle to a submodular function is assumed. But how does one check if this oracle indeed represents a submodular function? Consider a function f:{0,1} (n) -> a"e. The distance to submodularity is the minimum fraction of values of f that need to be modified to make f submodular. If this distance is more than I mu > 0, then we say that f is I mu-far from being submodular. The aim is to have an efficient procedure that, given input f that is I mu-far from being submodular, certifies that f is not submodular. We analyze a natural tester for this problem, and prove that it runs in subexponential time. This gives the first non-trivial tester for submodularity. On the other hand, we prove an interesting lower bound (that is, unfortunately, quite far from the upper bound) suggesting that this tester cannot be efficient in terms of I mu. This involves non-trivial examples of functions which are far from submodular and yet do not exhibit too many local violations. We also provide some constructions indicating the difficulty in designing a tester for submodularity. We construct a partial function defined on exponentially many points that cannot be extended to a submodular function, but any strict subset of these values can be extended to a submodular function.

关键词： Property testing sublinear algorithms Submodular functions

来源：评论

学校读者我要写书评

暂无评论

Estimating Renyi Entropy of Discrete Distributions

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2017年第1期63卷 38-56页

作者： Acharya, Jayadev Orlitsky, Alon Suresh, Ananda Theertha Tyagi, Himanshu Cornell Univ Sch Elect & Comp Engn Ithaca NY 14853 USA Univ Calif San Diego Dept Elect & Comp Engn La Jolla CA 92093 USA Google Res 769th Ave New York NY 10011 USA Indian Inst Sci Dept Elect Commun Engn Bengaluru 560012 India

It was shown recently that estimating the Shannon entropy H(p) of a discrete k-symbol distribution p requires Theta (k/log k) samples, a number that grows near-linearly in the support size. In many applications, H(p) can be replaced by the more general Rnyi entropy of order alpha and H-alpha(p). We determine the number of samples needed to estimate H-alpha(p) for all alpha, showing that alpha < 1 requires a super-linear, roughly k(1/alpha) samples, noninteger alpha > 1 requires a near-linear k samples, but, perhaps surprisingly, integer alpha > 1 requires only Theta (k(1-1/alpha)) samples. Furthermore, developing on a recently established connection between polynomial approximation and estimation of additive functions of the form Sigma(x) f (px), we reduce the sample complexity for noninteger values of alpha by a factor of log k compared with the empirical estimator. The estimators achieving these bounds are simple and run in time linear in the number of samples. Our lower bounds provide explicit constructions of distributions with different Renyi entropies that are hard to distinguish.

关键词： Entropy estimation minimax lower bounds sample complexity sublinear algorithms

来源：评论

学校读者我要写书评

暂无评论

Tolerant property testing and distance approximation

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2006年第6期72卷 1012-1042页

作者： Parnas, Michal Ron, Dana Rubinfeld, Ronitt Acad Coll Tel Aviv Yaffo Sch Comp Sci Tel Aviv Israel Tel Aviv Univ Dept EE Syst IL-69978 Tel Aviv Israel MIT CSAIL Cambridge MA 02139 USA

In this paper we study a generalization of standard property testing where the algorithms are required to be more tolerant with respect to objects that do not have, but are close to having, the property. Specifically, a tolerant property testing algorithm is required to accept objects that are epsilon(1)-close to having a given property P and reject objects that are epsilon(2)-far from having P, for some parameters 0 <= epsilon(1) < epsilon(2) <= 1. Another related natural extension of standard property testing that we study, is distance approximation. Here the algorithm should output an estimate of the distance of the object to P, where this estimate is sufficiently close to the true distance of the object to P. We first formalize the notions of tolerant property testing and distance approximation and discuss the relationship between the two tasks, as well as their relationship to standard property testing. We then apply these new notions to the study of two problems: tolerant testing of clustering and distance approximation for monotonicity. We present and analyze algorithms whose query complexity is either polylogarithmic or independent of the size of the input. (c) 2006 Elsevier Inc. All rights reserved.

关键词： property testing sublinear algorithms approximation clustering

来源：评论

学校读者我要写书评

暂无评论

Fast-Match: Fast Affine Template Matching

引用

INTERNATIONAL JOURNAL OF COMPUTER VISION 2017年第1期121卷 111-125页

作者： Korman, Simon Reichman, Daniel Tsur, Gilad Avidan, Shai Univ Calif Los Angeles Dept Comp Sci Los Angeles CA 90024 USA Tel Aviv Univ Tel Aviv Israel Univ Calif Berkeley Inst Cognit & Brain Sci Berkeley CA 94720 USA Weizmann Inst Sci Rehovot Israel Yahoo Res Labs IL-31905 Haifa Israel Tel Aviv Univ Sch Elect Engn Tel Aviv Israel

Fast-Match is a fast algorithm for approximate template matching under 2D affine transformations that minimizes the Sum-of-Absolute-Differences (SAD) error measure. There is a huge number of transformations to consider but we prove that they can be sampled using a density that depends on the smoothness of the image. For each potential transformation, we approximate the SAD error using a sublinear algorithm that randomly examines only a small number of pixels. We further accelerate the algorithm using a branch-and-bound-like scheme. As images are known to be piecewise smooth, the result is a practical affine template matching algorithm with approximation guarantees, that takes a few seconds to run on a standard machine. We perform several experiments on three different datasets, and report very good results.

关键词： Pattern matching Template matching Image matching sublinear algorithms

来源：评论

学校读者我要写书评

暂无评论

Property-preserving data reconstruction

引用

ALGORITHMICA 2008年第2期51卷 160-182页

作者： Ailon, Nir Chazelle, Bernard Comandur, Seshadhri Liu, Ding Princeton Univ Princeton NJ 08540 USA

We initiate a new line of investigation into online property-preserving data reconstruction. Consider a dataset which is assumed to satisfy various (known) structural properties;e.g., it may consist of sorted numbers, or points on a manifold, or vectors in a polyhedral cone, or codewords from an error-correcting code. Because of noise and errors, however, an (unknown) fraction of the data is deemed unsound, i.e., in violation with the expected structural properties. Can one still query into the dataset in an online fashion and be provided data that is always sound? In other words, can one design a filter which, when given a query to any item I in the dataset, returns a sound item J that, although not necessarily in the dataset, differs from I as infrequently as possible. No preprocessing should be allowed and queries should be answered online. We consider the case of a monotone function. Specifically, the dataset encodes a function f:{1,...,n} (bar right arrow) R that is at (unknown) distance epsilon from monotone, meaning that f can-and must-be modified at epsilon n places to become monotone. Our main result is a randomized filter that can answer any query in O(log(2) n log log n) time while modifying the function f at only O(epsilon n) places. The amortized time over n function evaluations is O(log n). The filter works as stated with probability arbitrarily close to 1. We provide an alternative filter with O(log n) worst case query time and O(epsilon n log n) function modifications. For reconstructing d-dimensional monotone functions of the form f:{1,...,n}(d) (bar right arrow) R, we present a filter that takes (2(O(d))(log n)(4d-2) log log n) time per query and modifies at most O(epsilon n(d)) function values (for constant d).

关键词： sublinear algorithms monotonicity testing

来源：评论

学校读者我要写书评

暂无评论

Local algorithms for Sparse Spanning Graphs

引用

ALGORITHMICA 2020年第4期82卷 747-786页

作者： Levi, Reut Ron, Dana Rubinfeld, Ronitt Weizmann Inst Sci Rehovot Israel Tel Aviv Univ Sch Elect Engn IL-69978 Tel Aviv Israel MIT CSAIL Cambridge MA 02139 USA Tel Aviv Univ Blavatnik Sch Comp Sci IL-69978 Tel Aviv Israel

Constructing a spanning tree of a graph is one of the most basic tasks in graph theory. We consider a relaxed version of this problem in the setting of local algorithms. The relaxation is that the constructed subgraph is a sparse spanning subgraph containing at most (1+ epsilon)n edges (where n is the number of vertices and epsilon is a given approximation/sparsity parameter). In the local setting, the goal is to quickly determine whether a given edge e belongs to such a subgraph, without constructing the whole subgraph, but rather by inspecting (querying) the local neighborhood of e. The challenge is to maintain consistency. That is, to provide answers concerning different edges according to the same spanning subgraph. We first show that for general bounded-degree graphs, the query complexity of any such algorithm must be Omega (root n). This lower bound holds for constant-degree graphs that have high expansion. Next we design an algorithm for (bounded-degree) graphs with high expansion, obtaining a result that roughly matches the lower bound. We then turn to study graphs that exclude a fixed minor (and are hence non-expanding). We design an algorithm for such graphs, which may have an unbounded maximum degree. The query complexity of this algorithm is poly(1/epsilon, h) (independent of n and the maximum degree), where h is the number of vertices in the excluded minor. Though our two algorithms are designed for very different types of graphs (and have very different complexities), on a high-level there are several similarities, and we highlight both the similarities and the differences.

关键词： sublinear algorithms Local algorithms Sparse spanning subgraphs Minor-free graphs Property testing Bounded degree model

来源：评论

学校读者我要写书评

暂无评论

Approximating All-Points Furthest Pairs and Maximum Spanning Trees in Metric Spaces

引用

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 2024年第5期35卷 595-603页

作者： Chang, Ching-Lueh Chang, Chun-Wei Yuan Ze Univ Dept Comp Sci & Engn Taoyuan Taiwan

Consider the problem of finding a point furthest from x for each point x in a metric space ([n], d), where [n] = {1, 2, ... , n}. We prove this problem to have a deterministic O(n)-time 1/3-approximation algorithm. As a corollary, the maximum spanning tree problem in metric spaces has a deterministic O(n)-time 1/3-approximation algorithm. We also give a Monte Carlo O(n(1.5)vlog n)-time algorithm outputting, for each x ? [n], a point yx ? [n] satisfying d(x, y(x)) = ?/2, where ? = max(x,y?[n] )d(x, y). As a corollary, we have a Monte Carlo O(n(1.5)vlog n)-time algorithm for finding a spanning tree of weight at least (1/2 - o(1))?n in ([n], d).

关键词： Metric spaces sublinear algorithms eccentricities maximum spanning trees

来源：评论

学校读者我要写书评

暂无评论

Estimating the distance to a monotone function

引用

RANDOM STRUCTURES & algorithms 2007年第3期31卷 371-383页

作者： Ailon, Nir Chazelle, Bernard Comandur, Seshadhri Liu, Ding Princeton Univ Dept Comp Sci Princeton NJ 08544 USA

In standard property testing, the task is to distinguish between objects that have a property P and those that are epsilon-far from P, for some epsilon > 0. In this setting, it is perfectly acceptable for the tester to provide a negative answer for every input object that does not satisfy P. This implies that property testing in and of itself cannot be expected to yield any information whatsoever about the distance from the object to the property. We address this problem in this paper, restricting our attention to monotonicity testing. A function f : {1,..., n} R is at distance epsilon(f) from being monotone if it can (and must) be modified at epsilon(f)n places to become monotone. For any fixed delta > 0, we compute, with probability at least 2/3, an interval [(1/2 - delta)epsilon, epsilon] that encloses epsilon(f). The running time of our algorithm is O(epsilon(-1)(f) log log epsilon(-1)(f) log n), which is optimal within a factor of log log epsilon(-1)(f) and represents a substantial improvement over previous work. We give a second algorithm with an expected running time of O(epsilon(-1)(f) log n log log log n). Finally, we extend our results to multivariate functions. (C) 2007 Wiley Periodicals, Inc.

关键词： property testing tolerant property testing sublinear algorithms distance estimation monotone functions

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：