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

Maintaining a topological order under edge insertions

INFORMATION PROCESSING LETTERS 1996年第1期59卷 53-58页

作者： MarchettiSpaccamela, A Nanni, U Rohnert, H ICSI BERKELEYCA

A topological order of the vertices of a directed acyclic graph G = (V,E) is any total order ord such that if (x, y) is an element of E, then x precedes y in ord. In this paper we consider the dynamic version of this problem, and provide simple algorithms and data structures achieving O(n) amortized time per edge insertion starting from an empty graph, which favorably compares to the trivial O(m+n) time bound per operation obtained applying the off-line algorithm. The additional space requirement, beside the representation of the graph itself, is O(n). Experimental results show that our algorithm performs in practice orders of magnitude faster than the off-line algorithm.

关键词： algorithms dynamic graphs incremental algorithms amortized analysis

来源：评论

学校读者我要写书评

暂无评论

Efficient Maintenance of Shortest Distances in Dynamic Graphs

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2018年第3期30卷 474-487页

作者： Greco, Sergio Molinaro, Cristian Pulice, Chiara Univ Calabria DIMES Dept Via P Bucci 42C I-87036 Arcavacata Di Rende CS Italy Dartmouth Coll Dept Comp Sci Hanover NH 03755 USA

Computing shortest distances is a central task in many domains. The growing number of applications dealing with dynamic graphs calls for incremental algorithms, as it is impractical to recompute shortest distances from scratch every time updates occur. In this paper, we address the problem of maintaining all-pairs shortest distances in dynamic graphs. We propose efficient incremental algorithms to process sequences of edge deletions/insertions/updates and vertex deletions/insertions. The proposed approach relies on some general operators that can be easily "instantiated" both in main memory and on top of different underlying DBMSs. We provide complexity analyses of the proposed algorithms. Experimental results on several real-world datasets show that current main-memory algorithms become soon impractical, disk-based ones are needed for larger graphs, and our approach significantly outperforms state-of-the-art algorithms.

关键词： Shortest distances incremental algorithms

来源：评论

学校读者我要写书评

暂无评论

Dynamical algorithms for data mining and machine learning over dynamic graphs

引用

WILEY INTERDISCIPLINARY REVIEWS-DATA MINING AND KNOWLEDGE DISCOVERY 2021年第2期11卷 e1393-e1393页

作者： Haghir Chehreghani, Mostafa Amirkabir Univ Technol Tehran Polytech Dept Comp Engn Tehran Iran

In many modern applications, the generated data is a dynamic networks. The networks are graphs that change over time by a sequence of update operations (node addition, node deletion, edge addition, edge deletion, and edge weight change). In these networks, it is inefficient to compute from scratch the solution of a data mining/machine learning task, after any update operation. Therefore in recent years, several so-called dynamical algorithms have been proposed that update the solution, instead of computing it from scratch. In this paper, first we formulate this emerging setting and discuss its high-level algorithmic aspects. Then, we review state of the art dynamical algorithms proposed for several data mining and machine learning tasks, including frequent pattern discovery, betweenness/closeness/PageRank centralities, clustering, classification, and regression. This article is categorized under: Technologies > Structure Discovery and Clustering Technologies > Machine Learning Fundamental Concepts of Data and Knowledge > Big Data Mining

关键词： data mining decremental algorithms dynamic graphs dynamical algorithms incremental algorithms machine learning social network analysis update time

来源：评论

学校读者我要写书评

暂无评论

Computing and Updating Hypervolume Contributions in Up to Four Dimensions

引用

IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION 2018年第3期22卷 449-463页

作者： Guerreiro, Andreia P. Fonseca, Carlos M. Univ Coimbra Ctr Informat & Syst Dept Informat Engn P-3030290 Coimbra Portugal

Arising in connection with multiobjective selection and archiving, the hypervolume subset selection problem (HSSP) consists in finding a subset of size k = 3. The decremental greedy counterpart has no known approximat... 详细信息

Arising in connection with multiobjective selection and archiving, the hypervolume subset selection problem (HSSP) consists in finding a subset of size k <= n of a set X. R-d of n nondominated points in d-dimensional space that maximizes the hypervolume indicator. The incremental greedy approximation to the HSSP has an approximation guarantee of 1 - 1/e, and is polynomial in n and k, while no polynomial exact algorithms are known for d >= 3. The decremental greedy counterpart has no known approximation guarantee, but is potentially faster for large k, and still leads to good approximations in practice. The computation and update of individual hypervolume contributions are at the core of the implementation of this greedy strategy. In this paper, new algorithms for the computation and update of hypervolume contributions are developed. In three dimensions, updating the total hypervolume and all individual contributions under single-point changes is performed in linear time, while in the 4-D case all contributions are computed in O(n(2)) time. As a consequence, the decremental greedy approximation to the HSSP can now be obtained in O(n(n - k) + n log n) and O(n(2)(n - k)) time for d = 3 and d = 4, respectively. Experimental results show that the proposed algorithms significantly outperform existing ones.

关键词： Hypervolume contributions hypervolume indicator hypervolume subset selection problem (HSSP) incremental algorithms

来源：评论

学校读者我要写书评

暂无评论

Walk for Learning: A Random Walk Approach for Federated Learning From Heterogeneous Data

引用

IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS 2023年第4期41卷 929-940页

作者： Ayache, Ghadir Dassari, Venkat El Rouayheb, Salim Rutgers State Univ Elect & Comp Engn Dept Piscataway NJ 08854 USA US Army Res Lab White Oak MD 20783 USA

We consider the problem of a Parameter Server (PS) that wishes to learn a model that fits data distributed on the nodes of a graph. We focus on Federated Learning (FL) as a canonical application. One of the main challenges of FL is the communication bottleneck between the nodes and the parameter server. A popular solution in the literature is to allow each node to do several local updates on the model in each iteration before sending it back to the PS. While this mitigates the communication bottleneck, the statistical heterogeneity of the data owned by the different nodes has proven to delay convergence and bias the model. In this work, we study random walk (RW) learning algorithms for tackling the communication and data heterogeneity problems. The main idea is to leverage available direct connections among the nodes themselves, which are typically "cheaper" than the communication to the PS. In a random walk, the model is thought of as a "baton" that is passed from a node to one of its neighbors after being updated in each iteration. The challenge in designing the RW is the data hetErogeneity and the uncertainty about the data distributions. Ideally, we would want to visit more often nodes that hold more informative data. We cast this problem as a sleeping multi-armed bandit (MAB) to design near-optimal node sampling strategy that achieves a variance reduced gradient estimates and approaches sub-linearly the optimal sampling strategy. Based on this framework, we present an adaptive random walk learning algorithm. We provide theoretical guarantees on its convergence. Our numerical results validate our theoretical findings and show that our algorithm outperforms existing random walk algorithms.

关键词： Convergence Data models Signal processing algorithms Costs Adaptation models Numerical models Computational modeling Decentralized learning distributed learning random walk incremental algorithms multi-armed bandit

来源：评论

学校读者我要写书评

暂无评论

Learning in environments with unknown dynamics:: Towards more robust concept learners

引用

JOURNAL OF MACHINE LEARNING RESEARCH 2007年第11期8卷 2595-2628页

作者： Nunez, Marlon Fidalgo, Raul Morales, Rafael Univ Malaga Dept Lenguajes & Ciencias Comp ETSI Informat E-29071 Malaga Spain

In the process of concept learning, target concepts may have portions with short-term changes, other portions may support long-term changes, and yet others may not change at all. For this reason several local windows need to be handled. We suggest facing this problem, which naturally exists in the field of concept learning, by allocating windows which can adapt their size to portions of the target concept. We propose an incremental decision tree that is updated with incoming examples. Each leaf of the decision tree holds a time window and a local performance measure as the main parameter to be controlled. When the performance of a leaf decreases, the size of its local window is reduced. This learning algorithm, called OnlineTree2, automatically adjusts its internal parameters in order to face the current dynamics of the data stream. Results show that it is comparable to other batch algorithms when facing problems with no concept change, and it is better than evaluated methods in its ability to deal with concept drift when dealing with problems in which: concept change occurs at different speeds, noise may be present and, examples may arrive from different areas of the problem domain ( virtual drift).

关键词： incremental algorithms online learning concept drift decision trees robust learners

来源：评论

学校读者我要写书评

暂无评论

Error stability properties of generalized gradient-type algorithms

引用

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 1998年第3期98卷 663-680页

作者： Solodov, MV Zavriev, SK Inst Matemat Pura & Aplicada Rio De Janeiro Brazil Moscow State Univ Dept Operat Res Fac Computat Math & Cybernet Moscow Russia

We present a unified framework for convergence analysis of generalized subgradient-type algorithms in the presence of perturbations. A principal novel feature of our analysis is that perturbations need not tend to zero in the limit. It is established that the iterates of the algorithms are attracted, in a certain sense, to an epsilon-stationary set of the problem, where epsilon depends on the magnitude of perturbations. Characterization of the attraction sets is given in the general (nonsmooth and nonconvex) case. The results are further strengthened for convex, weakly sharp, and strongly convex problems. Our analysis extends and unifies previously known results on convergence and stability properties of gradient and subgradient methods, including their incremental, parallel, and heavy ball modifications.

关键词： error stability perturbation analysis gradient-type methods incremental algorithms approximate solutions

来源：评论

学校读者我要写书评

暂无评论

A linear-time algorithm for finding a maximal planar subgraph

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2006年第2期20卷 444-462页

作者： Djidjev, Hristo N. Los Alamos Natl Lab Los Alamos NM 87545 USA

We construct an optimal linear-time algorithm for the maximal planar subgraph problem: given a graph G, find a planar subgraph G' of G such that adding to G' an extra edge of G results in a nonplanar graph. Our solution is based on a fast data structure for incremental planarity testing of triconnected graphs and a dynamic graph search procedure. Our algorithm can be transformed into a new optimal planarity testing algorithm.

关键词： planar graphs planarity testing incremental algorithms graph planarization data structures triconnectivity

来源：评论

学校读者我要写书评

暂无评论

ACQUIRING AND COMBINING OVERLAPPING CONCEPTS

引用

MACHINE LEARNING 1994年第1-2期16卷 121-155页

作者： MARTIN, JD BILLMAN, DO GEORGIA INST TECHNOL DEPT PSYCHOLATLANTAGA 30332

This article presents OLOC, an incremental concept formation system that learns and uses overlapping concepts. OLOC learns probabilistic concepts that have overlapping extensions and does so to maximize expected predi... 详细信息

关键词： CONCEPT FORMATION OVERLAPPING CONCEPTS CONCEPTUAL COMBINATION incremental algorithms

来源：评论

学校读者我要写书评

暂无评论

Parallel algorithms for arrangements

引用

ALGORITHMICA 1996年第2期15卷 104-125页

作者： Anderson, R Beame, P Brisson, E Department of Computer Science and Engineering FR-35 University of Washington Seattle USA

We give the first efficient parallel algorithms for solving the arrangement problem. We give a deterministic algorithm for the CREW PRAM which runs in nearly optimal bounds of O (log n log* n) time and n(2)/log n processors. We generalize this to obtain an O (log n log* n)-time algorithm using n(d)/log n processors for solving the problem in d dimensions. We also give a randomized algorithm for the EREW PRAM that constructs an arrangement of n lines on-line, in which each insertion is done in optimal O (log n) time using n/log n processors. Our algorithms develop new parallel data structures and new methods for traversing an arrangement.

关键词： parallel algorithms computational geometry arrangement problem incremental algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：