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

Efficient algorithms for approximate time separation of events

SADHANA-ACADEMY PROCEEDINGS IN ENGINEERING SCIENCES 2002年第2期27卷 129-162页

作者： Chakraborty, S Dill, DL Yun, KY Indian Inst Technol Dept Comp Sci & Engn Bombay 400076 Mumbai India

Finding bounds on time separation of events is a fundamental problem in the verification and analysis of asynchronous and concurrent systems. Unfortunately, even for systems without repeated events or choice, computing exact bounds on time separation of events is an intractable problem when both min and max type timing constraints are present. In this paper, we describe a method for approximating min and max type constraints, and develop a polynomial-time algorithm for computing approximate time separation bounds in choice-free systems without repeated events. Next, we develop a pseudo-polynomial time technique for analysing a class of asynchronous systems in which events repeat over time. Unlike earlier works, our algorithms can analyse systems with both min and max type timing constraints efficiently. Although the computed bounds are conservative in the worst-case, experimental results indicate that they are fairly accurate in practice. We present formal proofs of correctness of our algorithms, and demonstrate their efficiency and accuracy by applying them to a suite of benchmarks. A complete asynchronous chip has been modelled and analysed using the proposed technique, revealing potential timing problems (already known to designers) in the datapath design.

关键词： asynchronous systems timing analysis and verification approximate algorithms convex approximation time separation of events bounded delay timing analysis

来源：评论

学校读者我要写书评

暂无评论

Efficient algorithms for approximate Smooth Selection

引用

JOURNAL OF GEOMETRIC ANALYSIS 2021年第7期31卷 6530-6600页

作者： Fefferman, Charles Guillen Pegueroles, Bernat Princeton Univ Princeton NJ 08544 USA

In this paper, we provide efficient algorithms for approximate C-m(R-n, R-D)-selection. In particular, given a set E, a constant M-0 > 0, and convex sets K(x) subset of R-D for x is an element of E, we show that an algorithm running in C(tau)N log N steps is able to solve the smooth selection problem of selecting a point y is an element of (1 + tau)lozenge K(x) for x is an element of E for an appropriate dilation of K(x), (1 + tau)lozenge K(x), and guaranteeing that a function interpolating the points (x, y) will be C-m(R-n, R-D) with norm bounded by CM.

关键词： Smooth selection approximate algorithms Efficient algorithms Partition of unity

来源：评论

学校读者我要写书评

暂无评论

A Framework for Description and Analysis of Sampling-based approximate Triangle Counting algorithms 3

A Framework for Description and Analysis of Sampling-based A...

引用

3rd IEEE/ACM International Conference on Data Science and Advanced Analytics (DSAA)

作者： Chehreghani, Mostafa Haghir KU Leaven Dept Comp Sci Celestijnenlaan 200aBox 2402 B-3001 Leuven Belgium

ISBN: (纸本)9781509052066

Counting the number of triangles in a large graph has many important applications in network analysis. Several frequently computed metrics such as the clustering coefficient and the transitivity ratio need to count the number of triangles. In this paper, we present a randomized framework for expressing and analyzing approximate triangle counting algorithms. We show that many existing approximate triangle counting algorithms can be described in terms of probability distributions given as parameters to the proposed framework. Then, we show that our proposed framework provides a quantitative measure for the quality of different approximate algorithms. Finally, we perform experiments on real-world networks from different domains and show that there is no unique sampling technique outperforming the others for all networks and the quality of sampling techniques depends on different factors such as the structure of the network, the vertex degree-triangle correlation and the number of samples.

关键词： Graphs triangle counting approximate algorithms large network analysis

来源：评论

学校读者我要写书评

暂无评论

Efficient algorithms for Finding approximate Heavy Hitters in Personalized PageRanks 18

Efficient Algorithms for Finding Approximate Heavy Hitters i...

引用

44th ACM SIGMOD International Conference on Management of Data

作者： Wang, Sibo Tao, Yufei Univ Queensland Brisbane Qld Australia Chinese Univ Hong Kong Hong Kong Peoples R China

ISBN: (纸本)9781450317436

Given a directed graph G, a source node s, and a target node t, the personalized PageRank (PPR) oft with respect to s is the probability that a random walk starting from s terminates at t. The average of the personalized PageRank score of t with respect to each source node v is an element of V is exactly the PageRank score pi(t) of node t, which denotes the overall importance of node t in the graph. A heavy hitter of node t is a node whose contribution to pi(t) is above a phi fraction, where phi is a value between 0 and 1. Finding heavy hitters has important applications in link spam detection, classification of web pages, and friend recommendations. In this paper, we propose BLOG, an efficient framework for three types of heavy hitter queries: the pairwise approximate heavy hitter (AHH), the reverse AHH, and the multi-source reverse AHH queries. For pairwise AHH queries, our algorithm combines the Monte-Carlo approach and the backward propagation approach to reduce the cost of both methods, and incorporates new techniques to deal with high in-degree nodes. For reverse AHH and multi-source reverse AHH queries, our algorithm extends the ideas behind the pairwise AHH algorithm with a new "logarithmic bucketing" technique to improve the query efficiency. Extensive experiments demonstrate that our BLOG is far more efficient than alternative solutions on the three queries.

关键词： Heavy Hitters Personalized PageRank approximate algorithms Social Recommendation

来源：评论

学校读者我要写书评

暂无评论

Sliding window-based approximate triangle counting with bounded memory usage

引用

VLDB JOURNAL 2023年第5期32卷 1087-1110页

作者： Gou, Xiangyang Zou, Lei Peking Univ Beijing Peoples R China Beijing Acad Artificial Intelligence Beijing Peoples R China

Streaming graph analysis is gaining importance in various fields due to the natural dynamicity in many real graph applications. However, approximately counting triangles in real-world streaming graphs with duplicate edges and sliding window model remains an unsolved problem. In this paper, we propose SWTC algorithm to address approximate sliding-window triangle counting problem in streaming graphs. In SWTC, we propose a fixed-length slicing strategy that addresses both sample maintaining and cardinality estimation issues with a bounded memory usage. We theoretically prove the superiority of our method in sample graph size and estimation accuracy under given memory upper bound. To further improve the performance of our algorithm, we propose two optimization techniques, vision counting to avoid computation peaks, and asynchronous grouping to stabilize the accuracy. Extensive experiments also confirm that our approach has higher accuracy compared with the baseline method under the same memory usage.

关键词： Streaming graphs approximate algorithms Triangle counting

来源：评论

学校读者我要写书评

暂无评论

Constant query time (1+ε)-approximate distance oracle for planar graphs

引用

THEORETICAL COMPUTER SCIENCE 2019年 761卷 78-88页

作者： Gu, Qian-Ping Xu, Gengchun Simon Fraser Univ Sch Comp Sci Burnaby BC V5A 1S6 Canada

We give a (1 + epsilon)-approximate distance oracle with O(1) query time for an undirected planar graph G with n vertices and non-negative edge lengths. For epsilon > 0 and any two vertices u and v in G, our oracle gives a distance (d) over bar (u, v) with stretch (1 + epsilon) in O(1) time. The oracle has size O(n log n((log n)/epsilon + f (epsilon))) and pre-processing time O(n log n((log(3) n)/epsilon(2) + f(epsilon))), where f (epsilon) = 2(O(1/epsilon)). This is the first (1 + epsilon)-approximate distance oracle with O(1) query time independent of epsilon and the size and pre-processing time nearly linear in n, and improves the query time O(1/epsilon) of previous (1 + epsilon)-approximate distance oracle with size nearly linear in n. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Distance oracle Planar graphs approximate algorithms Graph decomposition

来源：评论

学校读者我要写书评

暂无评论

An Efficient Algorithm for approximate Betweenness Centrality Computation

引用

COMPUTER JOURNAL 2014年第9期57卷 1371-1382页

作者： Chehreghani, Mostafa Haghir Katholieke Univ Leuven Dept Comp Sci B-3001 Leuven Belgium

Centrality indices are essential in network analysis and betweenness centrality, which is based on shortest paths, is one of the most important measures. It has been widely used in different areas like social network analysis, World Wide Web and route planning. However, even for mid-size networks, it is computationally expensive to compute exact betweenness scores. In this paper, we propose a generic randomized framework for unbiased estimation of betweenness scores. The proposed framework can be adapted with various sampling techniques and give algorithms with different characteristics. We discuss the conditions a promising sampling technique should satisfy to minimize the approximation error, and propose a sampling method that partially satisfies the conditions. We perform extensive experiments on synthetic networks as well as networks from the real world, and show that, compared with existing exact and inexact algorithms, our method works with higher accuracy or gives significant speedups.

关键词： graphs network analysis social networks centrality betweenness centrality approximate algorithms

来源：评论

学校读者我要写书评

暂无评论

An approximate Approach to Automatic Kernel Selection

引用

IEEE TRANSACTIONS ON CYBERNETICS 2017年第3期47卷 554-565页

作者： Ding, Lizhong Liao, Shizhong Tianjin Univ Sch Comp Sci & Technol Tianjin 300350 Peoples R China

Kernel selection is a fundamental problem of kernel-based learning algorithms. In this paper, we propose an approximate approach to automatic kernel selection for regression from the perspective of kernel matrix approximation. We first introduce multilevel circulant matrices into automatic kernel selection, and develop two approximate kernel selection algorithms by exploiting the computational virtues of multilevel circulant matrices. The complexity of the proposed algorithms is quasi-linear in the number of data points. Then, we prove an approximation error bound to measure the effect of the approximation in kernel matrices by multilevel circulant matrices on the hypothesis and further show that the approximate hypothesis produced with multilevel circulant matrices converges to the accurate hypothesis produced with kernel matrices. Experimental evaluations on benchmark datasets demonstrate the effectiveness of approximate kernel selection.

关键词： approximate algorithms kernel matrix approximation kernel selection model selection multilevel circulant matrices

来源：评论

学校读者我要写书评

暂无评论

Sublinear algorithms for (1.5+𝜖)-approximate Matching 2023

Sublinear Algorithms for (1.5+𝜖)-Approximate Matching

引用

Proceedings of the 55th Annual ACM Symposium on Theory of Computing

作者： Sayan Bhattacharya Peter Kiss Thatchaphol Saranurak University of Warwick UK University of Warwick UK / MPI-INF Germany University of Michigan USA

ISBN: (纸本)9781450399135

We study sublinear time algorithms for estimating the size of maximum matching. After a long line of research, the problem was finally settled by Behnezhad [FOCS’22], in the regime where one is willing to pay an approximation factor of 2. Very recently, Behnezhad et al. [SODA’23] improved the approximation factor to (2−1/2O(1/γ)) using n1+γ time. This improvement over the factor 2 is, however, minuscule and they asked if even 1.99-approximation is possible in n2−Ω(1) time. We give a strong affirmative answer to this open problem by showing (1.5+є)-approximation algorithms that run in n2−Θ(є2) time. Our approach is conceptually simple and diverges from all previous sublinear-time matching algorithms: we show a sublinear time algorithm for computing a variant of the edge-degree constrained subgraph (EDCS), a concept that has previously been exploited in dynamic [Bernstein Stein ICALP’15, SODA’16], distributed [Assadi et al. SODA’19] and streaming [Bernstein ICALP’20] settings, but never before in the sublinear setting.

关键词： Matching Sub-linear algorithms approximate algorithms Sparsification

来源：评论

学校读者我要写书评

暂无评论

An approximate binary search algorithm for the multiple-choice knapsack problem

引用

INFORMATION PROCESSING LETTERS 1998年第5期67卷 261-265页

作者： Gens, G Levner, E Ctr Technol Educ Dept Comp Sci IL-58102 Holon Israel Inst Automat Moscow Russia

A fast approximation algorithm for the multiple-choice knapsack problem is proposed whose solution is guaranteed to be 4/5-bounded. The algorithm is based on binary search and runs in O(n log m) time, n being the total number of items and m the number of multiple-choice classes in the knapsack problem. (C) 1998 Elsevier Science B.V. All rights reserved.

关键词： knapsack problem approximate algorithms approximate binary search algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：