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

SRDS 2015 34th Symposium on Reliable Distributed Systems

作者： Kruber, Nico Lange, Maik Schintke, Florian Zuse Inst Berlin Berlin Germany

ISBN: (纸本)9781467393027

The objective comparison of hash-based set reconciliation algorithms for distributed replica repair is challenging. Each algorithm's behaviour can be tuned for a given use case, e.g. low bandwidth or computational overhead, using different sets of parameters. Changes on these parameters, however, often also influence the algorithm's accuracy in recognising differences between replicas and thus hinder objective comparisons. We develop models to deduce parameters for equally accurate set reconciliation algorithms for replica repair in a distributed system and compare equally accurate instances of two trivial hash-based algorithms, an algorithm using Bloom filters and a Merkle tree based algorithm. Instead of using a large fixed hash size for Merkle trees we propose to use dynamic hash sizes to align the transfer overhead with the desired accuracy. We evaluate (a) the transferred volume of data with respect to different entropy levels, data and failure distributions on the set of items, and (b) the scalability in the number of items. Our results allow to easily choose an efficient algorithm for practical set reconciliation tasks based on the required level of accuracy. Our way to find equally accurate configuration parameters for different algorithms can also be adopted to other set reconciliation algorithms and allows to rate their respective performance in an objective manner.

关键词： Set Reconciliation Distributed Systems approximate algorithms Accuracy Models Merkle Tree Bloom Filter Replication Synchronisation

来源：评论

学校读者我要写书评

暂无评论

Randomization of approximate bilinear computation for matrix multiplication

引用

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS- COMPUTER SYSTEMS THEORY 2021年第1期6卷 54-93页

作者： Malik, Osman Asif Becker, Stephen Univ Colorado Boulder Dept Appl Math Boulder CO USA

We present a method for randomizing formulas for bilinear computation of matrix products which does not increase the leading order complexity of the computation. We consider the implications of such randomization when there are two sources of error. The first source is due to the computation formula itself only being approximately correct. Such formulas come up when numerically searching for faster matrix multiplication algorithms. The second source is due to using floating point arithmetic. This kind of error is especially important when computing on low precision hardware like GPUs. Our theoretical results and numerical experiments indicate that our method can improve performance when the two kinds of error are present individually, as well as when they are present at the same time.

关键词： Randomized algorithms approximate algorithms matrix multiplication Strassen's algorithm

来源：评论

学校读者我要写书评

暂无评论

approximate k-Closest-Pairs in large high-dimensional data sets

引用

Journal of Mathematical Modelling and algorithms 2005年第2期4卷 149-179页

作者： Angiulli, Fabrizio Pizzuti, Clara ICAR-CNR Università della Calabria 87036 Rende (CS) Via Pietro Bucci 41C Italy

An approximate algorithm to efficiently solve the k-Closest-Pairs problem on large high-dimensional data sets is presented. The algorithm runs, for a suitable choice of the input parameters, in $\mathcal{O}(d^{2}nk) $ time, where d is the dimensionality and n is the number of points of the input data set, and requires linear space in the input size. It performs at most d+1 iterations. At each iteration a shifted version of the data set is sequentially scanned according to the order induced on it by the Hilbert space filling curve and points whose contribution to the solution has already been analyzed are detected and eliminated. The pruning is lossless, in fact the remaining points along with the approximate solution found can be used for the computation of the exact solution. If the data set is entirely pruned, then the algorithm returns the exact solution. We prove that the pruning ability of the algorithm is related to the nearest neighbor distance distribution of the data set and show that there exists a class of data sets for which the method, augmented with a final step that applies an exact method to the reduced data set, calculates the exact solution with the same time requirements. Although we are able to guarantee a $\mathcal{O}(d^{1+approximate/{t}})$ approximation to the solution, where t {1,2,.∈.∈.,∞} identifies the Minkowski (L _t) metric of interest, experimental results give the exact k closest pairs for all the large high-dimensional synthetic and real data sets considered and show that the pruning of the search space is effective. We present a thorough scaling analysis of the algorithm for in-memory and disk-resident data sets showing that the algorithm scales well in both cases. © Springer 2005.

关键词： approximate algorithms k-Closest-Pairs problem Space Filling Curves

来源：评论

学校读者我要写书评

暂无评论

approximate Proximal-Gradient Methods 10

Approximate Proximal-Gradient Methods

引用

10th Conference of the Sensor-Signal-Processing-for-Defence (SSPD)

作者： Hamadouche, Anis Wu, Yun Wallace, Andrew M. Mota, Joao F. C. Heriot Watt Univ Sch Engn & Phys Sci Edinburgh EH14 4AS Scotland

ISBN: (纸本)9781665433143

We study the convergence of the Proximal-Gradient algorithm for convex composite problems when both the gradient and the proximal mapping are computed approximately. This scenario occurs when the gradient is computationally expensive and the proximal operator is not available in closed form and may be computed only up to a certain fixed precision. We establish tight deterministic bounds and propose new probabilistic upper bounds on the suboptimality of the function values along the iterations under some statistical assumptions on the perturbed iterates. We use the Proximal-Gradient algorithm to solve randomly generated LASSO problems while varying the fixed-point machine representation and the proximal computation precision.

关键词： Convex Optimization Proximal Gradient approximate algorithms

来源：评论

学校读者我要写书评

暂无评论

On the approximate bilinear complexity of matrix multiplication

引用

Moscow University Computational Mathematics and Cybernetics 2014年第4期38卷 177-180页

作者： Trefilov, A.P. Department of Computational Mathematics and Cybernetics Moscow State University Moscow 119991 Russian Federation

It is shown that the approximate bilinear complexity of multiplying matrices of the order 2 × 2 by a matrix of the order 2 × 6 does not exceed 19. An approximate bilinear algorithm of complexity 19 is presen... 详细信息

关键词： approximate algorithms Bilinear algorithms matrix multiplication matrix tensors

来源：评论

学校读者我要写书评

暂无评论

Finding Probabilistic Prevalent Colocations in Spatially Uncertain Data Sets

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2013年第4期25卷 790-804页

作者： Wang, Lizhen Wu, Pinping Chen, Hongmei Yunnan Univ Sch Informat Sci & Engn Dept Comp Sci & Engn Kunming 650091 Yunnan Province Peoples R China

A spatial colocation pattern is a group of spatial features whose instances are frequently located together in geographic space. Discovering colocations has many useful applications. For example, colocated plant species discovered from plant distribution data sets can contribute to the analysis of plant geography, phytosociology studies, and plant protection recommendations. In this paper, we study the colocation mining problem in the context of uncertain data, as the data generated from a wide range of data sources are inherently uncertain. One straightforward method to mine the prevalent colocations in a spatially uncertain data set is to simply compute the expected participation index of a candidate and decide if it exceeds a minimum prevalence threshold. Although this definition has been widely adopted, it misses important information about the confidence which can be associated with the participation index of a colocation. We propose another definition, probabilistic prevalent colocations, trying to find all the colocations that are likely to be prevalent in a randomly generated possible world. Finding probabilistic prevalent colocations (PPCs) turn out to be difficult. First, we propose pruning strategies for candidates to reduce the amount of computation of the probabilistic participation index values. Next, we design an improved dynamic programming algorithm for identifying candidates. This algorithm is suitable for parallel computation, and approximate computation. Finally, the effectiveness and efficiency of the methods proposed as well as the pruning strategies and the optimization techniques are verified by extensive experiments with "real + synthetic" spatially uncertain data sets.

关键词： Spatial colocations spatially uncertain data set possible worlds probabilistic prevalent colocations (PPCs) dynamic programming approximate algorithms

来源：评论

学校读者我要写书评

暂无评论

Chromatic kernel and its applications

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2016年第3期31卷 1298-1315页

作者： Ding, Hu Stojkovic, Branislav Chen, Zihe Hughes, Andrew Xu, Lei Fritz, Andrew Sehgal, Nitasha Berezney, Ronald Xu, Jinhui SUNY Buffalo Dept Comp Sci & Engn Buffalo NY 14260 USA SUNY Buffalo Dept Biol Sci Buffalo NY 14260 USA

In this paper, we study the following Chromatic kernel (CK) problem: given an -partite graph (called a chromatic correlation graph) with and each partite set containing a constant number of vertices, compute a subgraph of with exactly one vertex from each partite set and the maximum number of edges or the maximum total edge weight, if is edge-weighted (among all such subgraphs). CK is a new problem motivated by several applications and no existing algorithm directly solves it. In this paper, we first show that CK is NP-hard even if , and cannot be approximated within a factor of unless P = NP. Then, we present a random-sampling-based PTAS for dense CK. As its application, we show that CK can be used to determine the pattern of chromosome associations in the nucleus for a population of cells. We test our approach by using random and real biological data;experimental results suggest that our approach yields near optimal solutions, and significantly outperforms existing approaches.

关键词： Graph theory approximate algorithms Random sampling Biomedical applications

来源：评论

学校读者我要写书评

暂无评论

Parallel frequent set counting

引用

PARALLEL COMPUTING 2002年第5期28卷 815-825页

作者： Skillicorn, DB Queens Univ Dept Comp & Informat Sci Kingston ON K7L 3N6 Canada

Computing the frequent subsets of large multi-attribute data is a key component of local pattern detection data mining algorithms. It is both computation- and data-intensive. The standard parallel algorithms require multiple passes through the data. The cost of data access may easily outweigh any performance gained by parallelizing the computational part. We address two opportunities for performance improvement: using a parallel approximate algorithm that requires only a single pass over the data;and using a probabilistic technique to avoid generating most of the lattice of subsets implied by each object's data. The computation required is only slightly greater than levelwise algorithms, but the amount of data access is much smaller. (C) 2002 Published by Elsevier Science B.V.

关键词： association rules parallel algorithms approximate algorithms sampling hotlists

来源：评论

学校读者我要写书评

暂无评论

Ant colony optimization theory: A survey

引用

THEORETICAL COMPUTER SCIENCE 2005年第2-3期344卷 243-278页

作者： Dorigo, M Blum, C Free Univ Brussels IRIDIA B-1050 Brussels Belgium Univ Politecn Cataluna LSI ALBCOM ES-08034 Barcelona Spain

Research on a new metaheuristic for optimization is often initially focused on proof-of-concept applications. It is only after experimental work has shown the practical interest of the method that researchers try to deepen their understanding of the method's functioning not only through more and more sophisticated experiments but also by means of an effort to build a theory. Tackling questions such as "how and why the method works" is important, because finding an answer may help in improving its applicability. Ant colony optimization, which was introduced in the early 1990s as a novel technique for solving hard combinatorial optimization problems, finds itself currently at this point of its life cycle. With this article we provide a survey on theoretical results on ant colony optimization. First, we review some convergence results. Then we discuss relations between ant colony optimization algorithms and other approximate methods for optimization. Finally, we focus on some research efforts directed at gaining a deeper understanding of the behavior of ant colony optimization algorithms. Throughout the paper we identify some open questions with a certain interest of being solved in the near future. (c) 2005 Elsevier B.V. All rights reserved.

关键词： ant colony optimization metaheuristics combinatorial optimization convergence stochastic gradient descent model-based search approximate algorithms

来源：评论

学校读者我要写书评

暂无评论

Discovering Newsworthy Themes from Sequenced Data: A Step Towards Computational Journalism

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2017年第7期29卷 1398-1411页

作者： Fan, Qi Li, Yuchen Zhang, Dongxiang Tan, Kian-Lee NUS NUS Grad Sch Integrat Sci & Engn NGS Singapore 119077 Singapore Natl Univ Singapore Sch Comp Singapore 119077 Singapore Univ Elect Sci & Technol China Chengdu 610051 Sichuan Sheng Peoples R China Natl Univ Singapore NGS Sch Comp Singapore 119077 Singapore

Automatic discovery of newsworthy themes from sequenced data can relieve journalists from manually poring over a large amount of data in order to find interesting news. In this paper, we propose a novel k-Sketch query that aims to find k striking streaks to best summarize a subject. Our scoring function takes into account streak strikingness and streak coverage at the same time. We study the k-Sketch query processing in both offline and online scenarios, and propose various streak-level pruning techniques to find striking candidates. Among those candidates, we then develop approximate methods to discover the k most representative streaks with theoretical bounds. We conduct experiments on four real datasets, and the results demonstrate the efficiency and effectiveness of our proposed algorithms: the running time achieves up to 500 times speedup and the quality of the generated summaries is endorsed by the anonymous users from Amazon Mechanical Turk.

关键词： Computational journalism news theme discovery sequenced data approximate algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：