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

40th IEEE International Conference on Distributed Computing Systems (ICDCS)

作者： Eguchi, Ryota Kitamura, Naoki Izumi, Taisuke Nagoya Inst Technol Dept Comp Sci Nagoya Aichi Japan

ISBN: (纸本)9781728170022

In the rendezvous problem, two computing entities (called agents) located at different vertices in a graph have to meet at the same vertex. In this paper, we consider the synchronous neighborhood rendezvous problem, where the agents are initially located at two adjacent vertices. While this problem can be trivially solved in O(Delta) rounds (Delta is the maximum degree of the graph), it is highly challenging to reveal whether that problem can be solved in o(Delta) rounds, even assuming the rich computational capability of agents. The only known result is that the time complexity of O(root n) rounds is achievable if the graph is complete and agents are probabilistic, asymmetric, and can use whiteboards placed at vertices. Our main contribution is to clarify the situation (with respect to computational models and graph classes) admitting such a sublinear-time rendezvous algorithm. More precisely, we present two algorithms achieving fast rendezvous additionally assuming bounded minimum degree, unique vertex identifier, and accessibility to neighborhood IDs. The first algorithm runs within (O) over tilde(root n Delta/delta + n/delta) rounds for graphs of the minimum degree larger than root n, where n is the number of vertices in the graph, and delta is the minimum degree of the graph. The second algorithm assumes that the largest vertex ID is O(n), and achieves (O) over tilde (n/root delta)-round time complexity without using whiteboards. These algorithms attain o(Delta)-round complexity in the case of delta = omega(root nlogn) and delta = omega(n(2/3) log(4/3) n) respectively. We also prove that three unconventional assumptions of our algorithm, bounded minimum degree, accessibility to neighborhood IDs, and initial distance one, are all inherently necessary for attaining fast rendezvous. That is, one can obtain the Omega(n)-round lower bound if either one of them is removed.

关键词： rendezvous randomized algorithm sublinear-time algorithm whiteboards

来源：评论

学校读者我要写书评

暂无评论

DConstructor: Efficient and Robust Network Construction with Polylogarithmic Overhead 20

DConstructor: Efficient and Robust Network Construction with...

引用

39th Symposium on Principles of Distributed Computing

作者： Gilbert, Seth Pandurangan, Gopal Robinson, Peter Trehan, Amitabh Natl Univ Singapore Dept Comp Sci Singapore Singapore Univ Houston Dept Comp Sci Houston TX 77004 USA City Univ Hong Kong Dept Comp Sci Hong Kong Peoples R China Loughborough Univ Dept Comp Sci Loughborough Leics England

ISBN: (纸本)9781450375825

With the rise of dynamic reconfigurable networks such as Peer-to-Peer (P2P) networks, overlay networks, ad hoc wireless and mesh networks, it has become important to construct and maintain topologies with various desirable properties (such as connectivity, low diameter, expansion, low degree etc.) in an efficient decentralized manner. The main result of this paper is a distributed protocol called DConstructor that given any (connected) network topology will "converge" to a given (desired) target topology such as an expander, hypercube, or Chord, with high probability. Our protocol is efficient, lightweight, and scalable, and it incurs only O (polylog(n)) overhead (where.. is the network size) for topology construction and maintenance: only polylogarithmic (in n) bits need to be processed and sent by each node per round, the convergence time is polylogarithmic rounds and any node's computation cost per round is also polylogarithmic. Our protocol is robust and self-repairing in the sense that it will converge to the desired topology in polylogarithmic rounds and polylogarithmic communication cost under dynamic topology changes and arbitrary insertions and deletions of nodes.

关键词： Distributed Protocol Peer-to-Peer Network randomized algorithm Self-repairing Network Expander

来源：评论

学校读者我要写书评

暂无评论

A randomized balanced proper orthogonal decomposition technique

引用

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS 2020年 368卷 112540-000页

作者： Yu, Dan Chakravorty, Suman Nanjing Univ Aeronaut & Astronaut Coll Astronaut Nanjing 210016 Jiangsu Peoples R China Texas A&M Univ Dept Aerosp Engn College Stn TX 77840 USA

In this paper, we consider the model reduction problem of large-scale linear systems, such as systems obtained through the discretization of partial differential equations. We propose a randomized proper orthogonal decomposition (RPOD*) technique to obtain the reduced order model by perturbing the primal and adjoint system using Gaussian white noise. We show that computations required by RPOD* algorithm is orders of magnitude lower while its performance is much better than other state of the art algorithms. We also relate the RPOD* algorithm to Krylov subspace methods and show that it constitutes a randomized approach to computational linear algebra problems that utilize Krylov subspace methods. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Model reduction Proper orthogonal decomposition (POD) Krylov subspace methods randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

A consistency theorem for randomized singular value decomposition

引用

STATISTICS & PROBABILITY LETTERS 2020年第0期161卷 108743-000页

作者： Chen, Ting-Li Huang, Su-Yun Wang, Weichung Acad Sinica Inst Stat Sci Taipei 11529 Taiwan Natl Taiwan Univ Inst Appl Math Sci Taipei 10617 Taiwan

The singular value decomposition (SVD) and the principal component analysis are fundamental tools and probably the most popular methods for data dimension reduction. The rapid growth in the size of data matrices has lead to a need for developing efficient large-scale SVD algorithms. randomized SVD was proposed, and its potential was demonstrated for computing a low-rank SVD (Rokhlin et al., 2009). In this article, we introduce a consistency notion for random projections used in randomized SVD and provide a consistency theorem for it. We also present a numerical example to show how the random projections to low dimension affect the consistency. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Consistency randomized algorithm Singular value decomposition Principal component analysis

来源：评论

学校读者我要写书评

暂无评论

Zip Trees

引用

ACM TRANSACTIONS ON algorithmS 2021年第4期17卷 34-34页

作者： Tarjan, Robert E. Levy, Caleb C. Timmel, Stephen Princeton Univ Dept Comp Sci 35 Olden St Princeton NJ 08544 USA Intertrust Technol Sunnyvale CA 94085 USA Sunshine 165 Univ AveSuite 5 Palo Alto CA USA Virginia Tech Dept Math 225 Stanger St Blacksburg VA 24061 USA

We introduce the zip tree,(1) a form of randomized binary search tree that integrates previous ideas into one practical, performant, and pleasant-to-implement package. A zip tree is a binary search tree in which each node has a numeric rank and the tree is (max)-heap-ordered with respect to ranks, with rank ties broken in favor of smaller keys. Zip trees are essentially treaps [8], except that ranks are drawn from a geometric distribution instead of a uniform distribution, and we allow rank ties. These changes enable us to use fewer random bits per node. We perform insertions and deletions by unmerging and merging paths (unzipping and zipping) rather than by doing rotations, which avoids some pointer changes and improves efficiency. The methods of zipping and unzipping take inspiration from previous top-down approaches to insertion and deletion by Stephenson [10], Martinez and Roura [5], and Sprugnoli [9]. From a theoretical standpoint, this work provides two main results. First, zip trees require onlyO(log logn) bits (with high probability) to represent the largest rank in an n-node binary search tree;previous data structures require O(logn) bits for the largest rank. Second, zip trees are naturally isomorphic to skip lists [7], and simplify Dean and Jones' mapping between skip lists

关键词： Zip tree randomized algorithm binary search tree treap skip list

来源：评论

学校读者我要写书评

暂无评论

randomized estimation of functional covariance operator via subsampling

引用

STAT 2020年第1期9卷

作者： He, Shiyuan Yan, Xiaomeng Renmin Univ China Inst Stat & Big Data 59 Zhongguancun St Beijing 100872 Peoples R China Texas A&M Univ Dept Stat College Stn TX 77843 USA

Covariance operators are fundamental concepts and modelling tools for many functional data analysis methods, such as functional principal component analysis. However, the empirical (or estimated) covariance operator becomes too costly to compute when the functional dataset gets big. This paper studies a randomized algorithm for covariance operator estimation. The algorithm works by sampling and rescaling observations from the large functional data collection to form a sketch of much smaller size and performs computation on the sketch to obtain the subsampled empirical covariance operator. The proposed algorithm is theoretically justified via nonasymptotic bounds between the subsampled and the full-sample empirical covariance operator in terms of the Hilbert-Schmidt norm and the operator norm. It is shown that the optimal sampling probability that minimizes the expected squared Hilbert-Schmidt norm of the subsampling error is determined by the norm of each function. Simulated and real data examples are used to illustrate the effectiveness of the proposed algorithm.

关键词： covariance operator functional data analysis randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

A randomized Reputation System in the Presence of Unfair Ratings

引用

ACM TRANSACTIONS ON MANAGEMENT INFORMATION SYSTEMS 2020年第1期11卷 2-2页

作者： Rezvani, Mohsen Rezvani, Mojtaba Shahrood Univ Technol Fac Comp Engn Shahrood *** Iran Australian Natl Univ Coll Engn & Comp Sci Canberra ACT 2601 Australia

With the increasing popularity of online shopping markets, a significant number of consumers rely on these venues to meet their demands while choosing different products based on the ratings provided by others. Simultaneously, consumers feel confident in expressing their opinions through ratings. As a result, millions of ratings are generated on the web for different products, services, and dealers. Nonetheless, a noticeable number of users post unfair feedback. Recent studies have shown that reputation escalation is emerging as a new service, by which dealers pay to receive good feedback and escalate their ratings in online shopping markets. Therefore, finding robust and reliable ways to distinguish between fake and trustworthy ratings from users is a crucial task for every online shopping market. Moreover, with the dramatic increase in the number of ratings provided by consumers, scalability has arisen as another significant issue in the existing methods of reputation systems. To tackle these issues, we propose a randomized algorithm that calculates the reputation based on a random sample of the ratings. Since the randomly selected sample has a logarithmic size, it guarantees feasible scalability for large-scale online review systems. In addition, the randomness nature of the algorithm makes it robust against unfair ratings. We provide a thorough theoretical analysis of the proposed algorithm and validate its effectiveness through extensive empirical evaluation using real-world and synthetically generated datasets. Our experimental results show that the proposed method provides a high accuracy while running much faster than the existing iterative filtering approaches.

关键词： Reputation system data aggregation randomized algorithm trust computation online rating

来源：评论

学校读者我要写书评

暂无评论

A Novel Fiber Intrusion Signal Recognition Method for OFPS Based on SCN With Dropout

引用

JOURNAL OF LIGHTWAVE TECHNOLOGY 2019年第20期37卷 5221-5230页

作者： Li, Wei Zeng, Zhiqiang Qu, Hongquan Sun, Chengbin North China Univ Technol Sch Informat Sci & Technol Beijing 100144 Peoples R China

Accurate and fast recognition of fiber intrusion signals has always been a fundamental task in the Optical Fiber Pre-warning System (OFPS). However, currently existing recognition models tend to focus on one aspect and lack a comprehensive approach. In this paper, a dropout-based Stochastic Configuration Network (SCN) optical fiber intrusion signal recognition model is first proposed, which is named DropoutSCN. By combining dropout with randomized algorithm models, it not only enhances the fast learning ability, but also improves the generalization performance of the recognition model. In the experiment, compared with traditional Artificial Neural Network (ANN), Random Vector Functional Link (RVFL), and original SCN models, the DropoutSCN model proposed in this paper has the lowest rootmean-square error (RMSE). In terms of time efficiency, it reduces the time delay by about 2.5 times compared with the traditional ANN. In addition, this paper applies dropout to SCN, which provides a feasible thinking and reference for the study of randomized algorithm models.

关键词： Dropout optical fiber pre-warning system randomized algorithm signal recognition stochastic configuration network

来源：评论

学校读者我要写书评

暂无评论

A unified framework for oscillatory integral transforms: When to use NUFFT or butterfly factorization?

引用

JOURNAL OF COMPUTATIONAL PHYSICS 2019年第0期388卷 103-122页

作者： Yang, Haizhao Natl Univ Singapore Dept Math Singapore Singapore

This paper concerns the fast evaluation of the matvec g = Kf for K is an element of C-NxN, which is the discretization of an oscillatory integral transform g(x) = integral K(x, xi) f(xi)d xi with a kernel function K(x, xi) = alpha(x, xi)e(2 pi i Phi(x, xi)), where alpha(x, xi) is a smooth amplitude function, and Phi(x, xi) is a piecewise smooth phase function with O(1) discontinuous points in x and xi. A unified framework is proposed to compute Kf with O (N log N) time and memory complexity via the non-uniform fast Fourier transform (NUFFT) or the butterfly factorization (BF), together with an O (N) fast algorithm to determine whether NUFFT or BF is more suitable. This framework works for two cases: 1) explicit formulas for the amplitude and phase functions are known;2) only indirect access of the amplitude and phase functions are available. Especially in the case of indirect access, our main contributions are: 1) an O (N log N) algorithm for recovering the amplitude and phase functions is proposed based on a new low-rank matrix recovery algorithm;2) a new stable and nearly optimal BF with amplitude and phase functions in a form of a low-rank factorization (IBF-MAT(1)) is proposed to evaluate the matvec Kf. Numerical results are provided to demonstrate the effectiveness of the proposed framework. (C) 2019 Elsevier Inc. All rights reserved.

关键词： Non-uniform fast Fourier transform Butterfly factorization randomized algorithm Matrix completion Fourier integral operator Special function transform

来源：评论

学校读者我要写书评

暂无评论

Battery sizing for PV power plants under regulations using randomized algorithms

引用

RENEWABLE ENERGY 2017年 113卷 596-607页

作者： Pflaum, Peter Alamir, M. Lamoudi, M. Y. Schneider Elect Ind 37 Quai Paul Louis Merlin F-38000 Grenoble France Univ Grenoble CNRS Gipsa Lab BP 46Domaine Univ F-38400 St Martin Dheres France

The increasing amount of PV (photo-voltaic) power plants comes along with an increased instability in the power grid due to the high uncertainty of the PV power production. As a stabilizing measure, grid operators introduce regulations on the injected power profiles comprising the obligation to declare in advance the predicted power production as well as penalties which apply in case these previously declared production profiles were not respected. In order to meet these regulations power plant owners are forced to invest into expensive storage capacities. In this work an algorithm is proposed which allows to determine the optimal battery size that maximizes the to-be-expected revenue of such an installation for a given regulative framework. Moreover the scheme explicitly takes into account the uncertainty in the PV power production and it provides guaranteed lower bounds on the to-be-expected revenue at a configurable probability. The underlying method allowing to achieve these objectives is a randomized algorithm. The principle of this method is to compute probabilistic guarantees for respecting a binary constraint, considering only a limited number of uncertainty scenarios. (C) 2017 Elsevier Ltd. All rights reserved.

关键词： PV plant Battery sizing Regulations randomized algorithm Optimization PV forecast uncertainty

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：