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

Bipartite Matching in the Semi-streaming Model

ALGORITHMICA 2012年第1-2期63卷 490-508页

作者： Eggert, Sebastian Kliemann, Lasse Munstermann, Peter Srivastav, Anand Univ Kiel Dept Comp Sci D-24098 Kiel Germany

We present the first deterministic 1+epsilon approximation algorithm for finding a large matching in a bipartite graph in the semi-streaming model which requires only O((1/epsilon)(5)) passes over the input stream. In this model, the input graph G = (V, E) is given as a stream of its edges in some arbitrary order, and storage of the algorithm is bounded by O(npolylog n) bits, where n = | V |. The only previously known arbitrarily good approximation for general graphs is achieved by the randomized algorithm of McGregor (Proceedings of the InternationalWorkshop on Approximation algorithms for Combinatorial Optimization Problems and Randomization and Computation, Berkeley, CA, USA, pp. 170-181, 2005), which uses Omega((1/epsilon) 1/epsilon) passes. We show that even for bipartite graphs, McGregor's algorithm needs Omega(1/epsilon)(Omega(1/epsilon)) passes, thus it is necessarily exponential in the approximation parameter. The design as well as the analysis of our algorithm require the introduction of some new techniques. A novelty of our algorithm is a new deterministic assignment of matching edges to augmenting paths which is responsible for the complexity reduction, and gets rid of randomization. We repeatedly grow an initial matching using augmenting paths up to a length of 2k + 1 for k = [2/epsilon]. We terminate when the number of augmenting paths found in one iteration falls below a certain threshold also depending on k, that guarantees a 1 + epsilon approximation. The main challenge is to find those augmenting paths without requiring an excessive number of passes. In each iteration, using multiple passes, we grow a set of alternating paths in parallel, considering each edge as a possible extension as it comes along in the stream. Backtracking is used on paths that fail to grow any further. Crucial are the so-called position limits: when a matching edge is the ith matching edge in a path and it is then removed by backtracking, it will only be inserted into a path

关键词： Bipartite graph matching streaming algorithms Approximation schemes Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

streaming Principal Component Analysis From Incomplete Data

引用

JOURNAL OF MACHINE LEARNING RESEARCH 2019年第1期20卷 1-62页

作者： Eftekhari, Armin Ongie, Gregory Balzano, Laura Wakin, Michael B. Ecole Polytech Fed Lausanne Inst Elect Engn CH-1015 Lausanne VD Switzerland Univ Chicago Dept Stat Chicago IL 60637 USA Univ Michigan Dept Elect Engn & Comp Sci Ann Arbor MI 48109 USA Colorado Sch Mines Dept Elect Engn Golden CO 80401 USA

Linear subspace models are pervasive in computational sciences and particularly used for large datasets which are often incomplete due to privacy issues or sampling constraints. Therefore, a critical problem is developing an efficient algorithm for detecting low-dimensional linear structure from incomplete data efficiently, in terms of both computational complexity and storage. In this paper we propose a streaming subspace estimation algorithm called Subspace Navigation via Interpolation from Partial Entries (SNIPE) that efficiently processes blocks of incomplete data to estimate the underlying subspace model. In every iteration, SNIPE finds the subspace that best fits the new data block but remains close to the previous estimate. We show that SNIPE is a streaming solver for the underlying nonconvex matrix completion problem, that it converges globally to a stationary point of this program regardless of initialization, and that the convergence is locally linear with high probability. We also find that SNIPE shows state-of-the-art performance in our numerical simulations.

关键词： Principal component analysis Subspace identification Matrix completion streaming algorithms Nonconvex optimization Global convergence

来源：评论

学校读者我要写书评

暂无评论

PES: Priority Edge Sampling in streaming Triangle Estimation

引用

IEEE TRANSACTIONS ON BIG DATA 2022年第2期8卷 470-481页

作者： Etemadi, Roohollah Lu, Jianguo Univ Windsor Sch Comp Sci Windsor ON N9B 3P4 Canada

The number of triangles (hereafter denoted by Delta) is an important metric to analyze massive graphs. It is also used to compute clustering coefficient in networks. This paper proposes a new algorithm called PES (Priority Edge Sampling) to estimate the number of triangles in the streaming model where we need to minimize the memory window. PES combines edge sampling and reservoir sampling. Compared with the state-of-the-art streaming algorithms, PES outperforms consistently. The results are verified extensively in 48 large real-world networks in different domains and structures. The performance ratio can be as large as 11. More importantly, the ratio grows with data size almost exponentially. This is especially important in the era of big data-while we can tolerate existing algorithms for smaller datasets, our method is indispensable when sampling very large data. In addition to empirical comparisons, we also proved that the estimator is unbiased, and derived the variance.

关键词： Graph sampling triangles streaming algorithms variance

来源：评论

学校读者我要写书评

暂无评论

streaming with minimum space: An algorithm for covering by two congruent balls

引用

THEORETICAL COMPUTER SCIENCE 2013年 507卷 72-82页

作者： Poon, Chung Keung Zhu, Binhai City Univ Hong Kong Hong Kong Hong Kong Peoples R China Montana State Univ Bozeman MT 59717 USA

In this paper we design a simple streaming algorithm for maintaining two smallest balls (of equal radius) in d-dimension to cover a set of points in an on-line fashion. Different from most of the traditional streaming models, at any step we use the minimum amount of space by only storing the locations and the (common) radius of the balls. Previously, such a geometric algorithm is only investigated for covering with one ball (one-center) by Zarrabi-Zadeh and Chan (2006)116]. We give an analysis of our algorithm, which is significantly different from the one-center algorithm due to the obvious possibility of grouping points wrongly under this streaming model. We show that our algorithm has an approximation ratio 2 for d = 1 and at most 5.611 for any fixed d > 1. We also present lower bounds of 1.5 and 1.604 for the problem in the d = 1 and d > 1 cases respectively. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Two-center covering streaming algorithms Approximation ratio

来源：评论

学校读者我要写书评

暂无评论

Small stretch (α, β)-spanners in the streaming model

引用

THEORETICAL COMPUTER SCIENCE 2009年第36期410卷 3406-3413页

作者： Ausiello, Giorgio Franciosa, Paolo G. Italiano, Giuseppe F. Univ Roma La Sapienza Dipartimento Stat Probabilita & Stat Applcate I-00185 Rome Italy Univ Roma La Sapienza Dipartimento Informat & Sistemist I-00185 Rome Italy Univ Roma Tor Vergata Dipartimento Informat Sistemi & Produz I-00133 Rome Italy

We present algorithms for computing small stretch (alpha, beta)-spanners in the streaming model. An (alpha, beta)-spanner of a graph G is a subgraph S subset of G such that for each pair of vertices the distance in S is at most alpha times the distance in G plus beta. We assume that the graph is given as a stream of edges and vertices, and that only one pass over the data is allowed. Furthermore, the number of vertices and edges are not known in advance. We denote by m the current number of scanned edges and by n the current number of discovered vertices. In this model we show how to compute a (k, k - 1)-spanner of an unweighted undirected graph, for k = 2, 3, in O(1) amortized processing time per edge/vertex. The computed (k, k - 1)-spanners have O(n(1+1/k)) edges and our algorithms use only O(n(1+1/k)) words of memory space. In case only H(n) internal memory is available, the same spanners can be computed using O(n(1+1/k)/B) external memory blocks, each of size B. Each edge/vertex is processed in O(1) amortized time, plus O(1/B) amortized block transfers. (C) 2008 Elsevier B.V. All rights reserved.

关键词： Graph algorithms Graph spanners streaming algorithms External memory

来源：评论

学校读者我要写书评

暂无评论

MOSES: A streaming Algorithm for Linear Dimensionality Reduction

引用

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE 2020年第11期42卷 2901-2911页

作者： Eftekhari, Armin Hauser, Raphael A. Grammenos, Andreas Ecole Polytech Fed Lausanne Inst Elect Engn CH-1015 Lausanne Switzerland Univ Oxford Math Inst Oxford OX1 2JD England Alan Turing Inst London London NW1 2DB England Univ Cambridge Dept Comp Sci Cambridge CB2 1TN England Alan Turing Inst London London NW1 2DB England

This paper introduces Memory-limited Online Subspace Estimation Scheme (MOSES) for both estimating the principal components of streaming data and reducing its dimension. More specifically, in various applications such as sensor networks, the data vectors are presented sequentially to a user who has limited storage and processing time available. Applied to such problems, MOSES can provide a running estimate of leading principal components of the data that has arrived so far and also reduce its dimension. MOSES generalises the popular incremental Singular Vale Decomposition (iSVD) to handle thin blocks of data, rather than just vectors. This minor generalisation in part allows us to complement MOSES with a comprehensive statistical analysis, thus providing the first theoretically-sound variant of iSVD, which has been lacking despite the empirical success of this method. This generalisation also enables us to concretely interpret MOSES as an approximate solver for the underlying non-convex optimisation program. We find that MOSES consistently surpasses the state of the art in our numerical experiments with both synthetic and real-world datasets, while being computationally inexpensive.

关键词： Dimensionality reduction Estimation Optimization Approximation algorithms Principal component analysis Ear Principal component analysis linear dimensionality reduction subspace identification streaming algorithms non-convex optimisation

来源：评论

学校读者我要写书评

暂无评论

streaming Dictionary Matching with Mismatches

引用

ALGORITHMICA 2022年第4期84卷 896-916页

作者： Gawrychowski, Pawel Starikovskaya, Tatiana Univ Wroclaw PL-50137 Wroclaw Poland PSL Res Univ Ecole Normale Super DIENS F-75005 Paris France

In the k-mismatch problem we are given a pattern of length n and a text and must find all locations where the Hamming distance between the pattern and the text is at most k. A series of recent breakthroughs have resulted in an ultra-efficient streaming algorithm for this problem that requires only O(k log n/k) space and O(log n/k (root k log k + log(3) n)) time per letter (Clifford, Kociumaka, Porat, SODA 2019). In this work, we consider a strictly harder problem called dictionary matching with k mismatches. In this problem, we are given a dictionary of d patterns, where the length of each pattern is at most n, and must find all substrings of the text that are within Hamming distance k from one of the patterns. We develop a streaming algorithm for this problem with O(kd log(k) d polylog n) space and O(k log(k) d polylog n +vertical bar output vertical bar) time per position of the text. The algorithm is randomised and outputs correct answers with high probability. On the lower bound side, we show that any streaming algorithm for dictionary matching with k mismatches requires Omega(kd) bits of space.

关键词： streaming algorithms Pattern matching Hamming distance

来源：评论

学校读者我要写书评

暂无评论

Optimal per-edge processing times in the semi-streaming model

引用

INFORMATION PROCESSING LETTERS 2007年第3期104卷 106-112页

作者： Zelke, Mariano Humboldt Univ Inst Informat D-10099 Berlin Germany

We present semi-streaming algorithms for basic graph problems that have optimal per-edge processing times and therefore surpass all previous semi-streaming algorithms for these tasks. The semi-streaming model, which is appropriate when dealing with massive graphs, forbids random access to the input and restricts the memory to O(n center dot polylog n) bits. Particularly, the formerly best per-edge processing times for finding the connected components and a bipartition are O(alpha(n)), for determining k-vertex and k-edge connectivity O(k(2)n) and O(n center dot logn) respectively for any constant k and for computing a minimum spanning forest O(log n). All these time bounds we reduce to O(1). Every presented algorithm determines a solution asymptotically as fast as the best corresponding algorithm up to date in the classical RAM model, which therefore cannot convert the advantage of unlimited memory and random access into superior computing times for these problems. (c) 2007 Elsevier B.V. All rights reserved.

关键词： graph algorithms streaming algorithms per-edge processing time

来源：评论

学校读者我要写书评

暂无评论

Fast shared-memory streaming multilevel graph partitioning

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2021年 147卷 140-151页

作者： Jafari, Nazanin Selvitopi, Oguz Aykanat, Cevdet UMass Amherst Coll Informat & Comp Sci Amherst MA 01002 USA Lawrence Berkeley Natl Lab Computat Res Div 1 Cyclotron Rd Berkeley CA 94720 USA Bilkent Univ Dept Comp Engn TR-06800 Ankara Turkey

A fast parallel graph partitioner can benefit many applications by reducing data transfers. The online methods for partitioning graphs have to be fast and they often rely on simple one-pass streaming algorithms, while the offline methods for partitioning graphs contain more involved algorithms and the most successful methods in this category belong to the multilevel approaches. In this work, we assess the feasibility of using streaming graph partitioning algorithms within the multilevel framework. Our end goal is to come up with a fast parallel offline multilevel partitioner that can produce competitive cutsize quality. We rely on a simple but fast and flexible streaming algorithm throughout the entire multilevel framework. This streaming algorithm serves multiple purposes in the partitioning process: a clustering algorithm in the coarsening, an effective algorithm for the initial partitioning, and a fast refinement algorithm in the uncoarsening. Its simple nature also lends itself easily for parallelization. The experiments on various graphs show that our approach is on the average up to 5.1x faster than the multi-threaded MeTiS, which comes at the expense of only 2x worse cutsize. Published by Elsevier Inc.

关键词： streaming algorithms Graph partitioning Multilevel graph partitioning Parallel graph partitioning

来源：评论

学校读者我要写书评

暂无评论

A general streaming algorithm for pattern discovery

引用

KNOWLEDGE AND INFORMATION SYSTEMS 2013年第3期37卷 585-610页

作者： Patnaik, Debprakash Laxman, Srivatsan Chandramouli, Badrish Ramakrishnan, Naren Amazon Com Search & Discovery Grp Seattle WA 98109 USA Microsoft Res Bangalore 560080 Karnataka India Microsoft Res Redmond WA USA Virginia Tech Dept Comp Sci Blacksburg VA 24061 USA

Discovering frequent patterns over event sequences is an important data mining problem. Existing methods typically require multiple passes over the data, rendering them unsuitable for streaming contexts. We present the first streaming algorithm for mining frequent patterns over a window of recent events in the stream. We derive approximation guarantees for our algorithm in terms of: (i) the separation of frequent patterns from the infrequent ones, and (ii) the rate of change of stream characteristics. Our parameterization of the problem provides a new sweet spot in the tradeoff between making distributional assumptions over the stream and algorithmic efficiencies of mining. We illustrate how this yields significant benefits when mining practical streams from neuroscience and telecommunications logs.

关键词： Event sequences Data streams Frequent patterns Pattern discovery streaming algorithms Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：