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

streaming and dynamic algorithms for minimum enclosing balls in high dimensions

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 2014年第2期47卷 240-247页

作者： Chan, Timothy M. Pathak, Vinayak Univ Waterloo Sch Comp Sci Waterloo ON N2L 3G1 Canada

At SODA'1 0, Agarwal and Sharathkumar presented a streaming algorithm for approximating the minimum enclosing ball of a set of points in d-dimensional Euclidean space. Their algorithm requires one pass, uses O(d) space, and was shown to have approximation factor at most (1 + root 3)/2 + epsilon approximate to 1.3661. We prove that the same algorithm has approximation factor less than 1.22, which brings us much closer to a (1 + root 2)/2 approximate to 1.207 lower bound given by Agarwal and Sharathkumar. We also apply this technique to the dynamic version of the minimum enclosing ball problem (in the non-streaming setting). We give an O(dn)-space data structure that can maintain a 1.22-approximate minimum enclosing ball in O(d logn) expected amortized time per insertion/deletion. (C) 2013 Elsevier B.V. All rights reserved.

关键词： streaming algorithms Dynamic algorithms High dimension

来源：评论

学校读者我要写书评

暂无评论

streaming clustering algorithms for foreground detection in color videos

Streaming clustering algorithms for foreground detection in ...

引用

2nd International Conference on Computer Graphics Theory and Applications/2nd International Conference on Computer Vision Theory and Applications

作者： Duric, Zoran Lawson, Wallace E. Richards, Dana George Mason Univ Dept Comp Sci Fairfax VA 22030 USA

ISBN: (纸本)9789728865740

A new method is given for locating foreground objects in color *** is an essential task in many applications such as surveillance. The algorithm uses clustering techniques to permit flexibility and adaptability in the description of the background. The approach is an example of the streaming data paradigm of algorithms design, which only permits limited information to be retained about previous video frames. Experimental results show that it is an effective and robust technique.

关键词： streaming algorithms clustering backgroundmaintenance video surveillance

来源：评论

学校读者我要写书评

暂无评论

FREIGHT: Fast streaming Hypergraph Partitioning

引用

ALGORITHMICA 2025年第3期87卷 405-428页

作者： Eyubov, Kamal Faraj, Marcelo Fonseca Schulz, Christian Heidelberg Univ Inst Comp Sci D-69120 Heidelberg Baden Wurttembe Germany

Partitioning the vertices of a (hyper)graph into k roughly balanced blocks such that few (hyper)edges run between blocks is a key problem for large-scale distributed processing. A current trend for partitioning huge (hyper)graphs using low computational resources are streaming algorithms. In this work, we propose FREIGHT: a Fast streaming Hypergraph parTitioning algorithm which is an adaptation of the widely-known graph-based algorithm Fennel. By using an efficient data structure, we make the overall running of FREIGHT linearly dependent on the pin-count of the hypergraph and the memory consumption linearly dependent on the numbers of nets and blocks. The results of our extensive experimentation showcase the promising performance of FREIGHT as a highly efficient and effective solution for streaming hypergraph partitioning. Our algorithm demonstrates competitive running time with the Hashing algorithm, with a geometric mean runtime within a factor of four compared to the Hashing algorithm. Significantly, our findings highlight the superiority of FREIGHT over all existing (buffered) streaming algorithms and even the in-memory algorithm HYPE, with respect to both cut-net and connectivity measures. This indicates that our proposed algorithm is a promising hypergraph partitioning tool to tackle the challenge posed by large-scale and dynamic data processing.

关键词： streaming algorithms Hypergraph partitioning Graph partitioning Algorithm engineering

来源：评论

学校读者我要写书评

暂无评论

streaming Updates for Heart Rate Variability algorithms

引用

IEEE TRANSACTIONS ON BIOMEDICAL ENGINEERING 2014年第7期61卷 1931-1937页

作者： Stergiou, Stergios Balakrishnan, Rajalakshmi Yahoo Inc Sunnyvale CA 94089 USA Fujitsu Labs Amer Sunnyvale CA 94085 USA

Heart rate variability (HRV) quantifies the fluctuations of the lengths of consecutive heart beat intervals, and is a reliable descriptor of many physiological factors modulating the normal rhythm of the heart. As the heart rate signal is nonstationary, indicators deduced from it may be present at all times, but may also occur episodically at nonpredetermined time instances. The potential for real-time feedback long-term ambulatory recordings is thus apparent. Numerous methods for measuringHRVhave been standardized and are in active use, but are typically not designed to operate at real time. In this paper, we study the most popular HRV quantification methods and propose streaming algorithms that maximally utilize previously computed information without altering the output of the methods. We demonstrate speedups of more than two orders of magnitude for typical use-case scenarios. Using our algorithms on embedded systems that compute HRV leads to dramatic decreases in power consumption and in some cases allows for computation of metrics that were not previously possible at real time.

关键词： Heart rate variability streaming algorithms

来源：评论

学校读者我要写书评

暂无评论

streaming and Fully Dynamic Centralized algorithms for Constructing and Maintaining Sparse Spanners

引用

ACM TRANSACTIONS ON algorithms 2011年第2期7卷 20-20页

作者： Elkin, Michael Ben Gurion Univ Negev Dept Comp Sci IL-84105 Beer Sheva Israel

We present a streaming algorithm for constructing sparse spanners and show that our algorithm significantly outperforms the state-of-the-art algorithm for this task (due to Feigenbaum et al.). Specifically, the processing time per edge of our algorithm is O(1), and it is drastically smaller than that of the algorithm of Feigenbaum et al., and all other efficiency parameters of our algorithm are no greater (and some of them are strictly smaller) than the respective parameters of the state-of-the-art algorithm. We also devise a fully dynamic centralized algorithm maintaining sparse spanners. This algorithm has incremental update time of O(1), and a nontrivial decremental update time. To our knowledge, this is the first fully dynamic centralized algorithm for maintaining sparse spanners that provides nontrivial bounds on both incremental and decremental update time for a wide range of stretch parameter t.

关键词： Graph spanners streaming algorithms

来源：评论

学校读者我要写书评

暂无评论

A Note on Maximizing Regularized Submodular Functions Under streaming

引用

Tsinghua Science and Technology 2023年第6期28卷 1023-1029页

作者： Qinqin Gong Kaiqiao Meng Ruiqi Yang Zhenning Zhang Beijing Institute for Scientific and Engineering Computing Beijing University of TechnologyBeijing 100124China

Recent progress in maximizing submodular functions with a cardinality constraint through centralized and streaming modes has demonstrated a wide range of applications and also developed comprehensive theoretical *** submodularity was investigated to capture the diversity and representativeness of the utilities,and the monotonicity has the advantage of improving the *** submodular optimization models were developed in the latest studies(such as a house on fire),which aimed to sieve subsets with constraints to optimize regularized *** study is motivated by the setting in which the input stream is partitioned into several disjoint parts,and each part has a limited size constraint.A first threshold-based bicriteria(1/3,2/3/)-approximation for the problem is provided.

关键词： submodular optimization regular model streaming algorithms threshold technique

来源：评论

学校读者我要写书评

暂无评论

Prioritized Restreaming algorithms for Balanced Graph Partitioning 20

Prioritized Restreaming Algorithms for Balanced Graph Partit...

引用

26th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD)

作者： Awadelkarim, Amel Ugander, Johan Stanford Univ Stanford CA 94305 USA

ISBN: (纸本)9781450379984

Balanced graph partitioning is a critical step for many large-scale distributed computations with relational data. As graph datasets have grown in size and density, a range of highly-scalable balanced partitioning algorithms have appeared to meet varied demands across different domains. As the starting point for the present work, we observe that two recently introduced families of iterative partitioners-those based on restreaming and those based on balanced label propagation (including Facebook's Social Hash Partitioner)-can be viewed through a common modular framework of design decisions. With the help of this modular perspective, we find that a key combination of design decisions leads to a novel family of algorithms with notably better empirical performance than any existing highly-scalable algorithm on a broad range of real-world graphs. The resulting prioritized restreaming algorithms employ a constraint management strategy based on multiplicative weights, borrowed from the restreaming literature, while adopting notions of priority from balanced label propagation to optimize the ordering of the streaming process. Our experimental results consider a range of stream orders, where a dynamic ordering based on what we call ambivalence is broadly the most performative in terms of the cut quality of the resulting balanced partitions, with a static ordering based on degree being nearly as good.

关键词： graph partitioning label propagation streaming algorithms algorithm design

来源：评论

学校读者我要写书评

暂无评论

Heterogeneous Environment Aware streaming Graph Partitioning

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2015年第6期27卷 1560-1572页

作者： Xu, Ning Cui, Bin Chen, Lei Huang, Zi Shao, Yingxia Peking Univ Sch EECS Key Lab High Confidence Software Technol MOE Beijing 100871 Peoples R China Beihang Univ State Key Lab Software Dev Environm Beijing 100191 Peoples R China Hong Kong Univ Sci & Technol Hong Kong Hong Kong Peoples R China Univ Queensland Sch ITEE Brisbane Qld 4072 Australia

With the increasing availability of graph data and widely adopted cloud computing paradigm, graph partitioning has become an efficient pre-processing technique to balance the computing workload and cope with the large scale of input data. Since the cost of partitioning the entire graph is strictly prohibitive, there are some recent tentative works towards streaming graph partitioning which run faster, are easily parallelized, and can be incrementally updated. Most of the existing works on streaming partitioning assume that worker nodes within a cluster are homogeneous in nature. Unfortunately, this assumption does not always hold. Experiments show that these homogeneous algorithms suffer a significant performance degradation when running at heterogeneous environment. In this paper, we propose a novel adaptive streaming graph partitioning approach to cope with heterogeneous environment. We first formally model the heterogeneous computing environment with the consideration of the unbalance of computing ability (e.g., the CPU frequency) and communication ability (e.g., the network bandwidth) for each node. Based on this model, we propose a new graph partitioning objective function that aims to minimize the total execution time of the graph-processing job. We then explore some simple yet effective streaming algorithms for this objective function that can achieve balanced and efficient partitioning result. Extensive experiments are conducted on a moderate sized computing cluster with real-world web and social network graphs. The results demonstrate that the proposed approach achieves significant improvement compared with the state-of-the-art solutions.

关键词： Graph partitioning streaming algorithms heterogeneous environment BSP Model

来源：评论

学校读者我要写书评

暂无评论

Intractability of min- and max-cut in streaming graphs

引用

INFORMATION PROCESSING LETTERS 2011年第3期111卷 145-150页

作者： Zelke, Mariano Goethe Univ Frankfurt Inst Informat Frankfurt Germany

We show that the exact computation of a minimum or a maximum cut of a given graph G IS out of reach for any one-pass streaming algorithm, that is, for any algorithm that runs over the input stream of G's edges only once and has a working memory of o(n(2)) bits. This holds even if randomization is allowed. (C) 2010 Elsevier B.V. All rights reserved.

关键词： Graph algorithms streaming algorithms Intractability Min-cut Max-cut

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：