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

ACM India Joint International Conference on Data Science and Management of Data (CoDS-COMAD)

作者： Sarkar, Braznev Indian Inst Engn Sci & Technol Dept Informat Technol Shibpur Howrah W Bengal India

ISBN: (纸本)9781450362078

When data is received at an extreme scale, many of the problems require faster approaches to be applied involving bounded space. With the growth of streaming data in different real-life domains (e.g., social media, astronomy, etc.), the necessity of efficient algorithm design has become imperative. In this paper, we present some of our proposals toward big streaming data analysis, precisely the analysis of streaming graphs. As the graphs are used for modelling interactions, streaming graphs play a major role in modeling dynamic interactions happening in many real-world scenarios. We highlight that how the spectral analysis on streaming graphs can be useful to develop efficient algorithms for understanding their properties. In this paper, we precisely focus on the problem of estimating the clique number of a graph. We propose an approach to set an upper bound on the clique number of a streaming graph and show its possible extensions.

关键词： streaming algorithms streaming graphs spectral analysis sketching

来源：评论

学校读者我要写书评

暂无评论

Linear Space streaming Lower Bounds for Approximating CSPs 2022

Linear Space Streaming Lower Bounds for Approximating CSPs

引用

54th Annual ACM SIGACT Symposium on Theory of Computing (STOC)

作者： Chou, Chi-Ning Golovnev, Alexander Sudan, Madhu Velingker, Ameya Velusamy, Santhoshini Harvard Univ Sch Engn & Appl Sci Cambridge MA 02138 USA Georgetown Univ Dept Comp Sci Washington DC USA Google Res Mountain View CA USA

ISBN: (纸本)9781450392648

We consider the approximability of constraint satisfaction problems in the streaming setting. For every constraint satisfaction problem (CSP) on n variables taking values in {0,..., q - 1}, we prove that improving over the trivial approximability by a factor of q requires Omega(n) space even on instances with O( n) constraints. We also identify a broad subclass of problems for which any improvement over the trivial approximability requires O(n) space. The key technical core is an optimal, q-((k-1))-inapproximability for the Max k-LIN-mod q problem, which is the Max CSP problem where every constraint is given by a system of k - 1 linear equations mod q over k variables. Our work builds on and extends the breakthrough work of Kapralov and Krachun (Proc. STOC 2019) who showed a linear lower bound on any non-trivial approximation of the MaxCut problem in graphs. MaxCut corresponds roughly to the case of Max k-LIN-mod q with k = q = 2. For general CSPs in the streaming setting, prior results only yielded Omega(root n) space bounds. In particular no linear space lower bound was known for an approximation factor less than 1/2 for any CSP. Extending the work of Kapralov and Krachun to Max k-LIN- mod q to k > 2 and q > 2 (while getting optimal hardness results) is the main technical contribution of this work. Each one of these extensions provides non-trivial technical challenges that we overcome in this work.

关键词： streaming algorithms communication lower bound inapproximability constraint satisfaction problems

来源：评论

学校读者我要写书评

暂无评论

Random Projection Clustering on streaming Data 16

Random Projection Clustering on Streaming Data

引用

16th IEEE International Conference on Data Mining (ICDM)

作者： Carraher, Lee A. Wilsey, Philip A. Moitra, Anindya Dey, Sayantan Univ Cincinnati Dept EECS Cincinnati OH 45221 USA

ISBN: (纸本)9781509059102

Clustering streaming data has gained importance in recent years due to an expanding opportunity to discover knowledge in widely available data streams. As streams are potentially evolving and unbounded sequence of data objects, clustering algorithms capable of performing fast and incremental processing of data points are necessary. This paper presents a method of clustering high-dimensional data streams using approximate methods called streamingRPHash. streamingRPHash combines random projections with locality-sensitivity hashing to construct a high-performance clustering method. streamingRPHash is amenable to distributed processing frameworks such as Map-Reduce, and also has the benefits of constrained overall complexity growth. This paper describes streamingRPHash algorithm and its various configurations. The clustering performance of streamingRPHash is compared to several alternatives. Experimental results show that streamingRPHash has comparable clustering accuracy and substantially lower runtime and memory usage.

关键词： streaming algorithms clustering LSH multi-probe LSH random projection min-count sketch

来源：评论

学校读者我要写书评

暂无评论

SWR: Using Windowed Reordering to Achieve Fast and Balanced Heuristic for streaming Vertex-Cut Graph Partitioning 19th

SWR: Using Windowed Reordering to Achieve Fast and Balanced ...

引用

19th International Conference on algorithms and Architectures for Parallel Processing (ICA3PP)

作者： Wang, Jie Li, Dagang Peking Univ Sch ECE Shenzhen Grad Sch Shenzhen Peoples R China

ISBN: (纸本)9783030389918;9783030389901

Graph partitioning plays a very fundamental and important role in a distributed graph computing (DGC) framework, because it determines the communication cost and workload balance among computing nodes. Existing solutions are mainly heuristic-based but unfortunately cannot achieve partitioning quality, load balance, and speed at the same time. In this paper, we propose Sliding-Window Reordering (SWR), a streaming vertex-cut graph partitioning algorithm, that introduces a pre-partitioning window to re-order incoming edges, making it much easier for a greedy strategy to maintain balance while optimizing edge assignment at a minimal computational cost. We analytically and experimentally evaluate SWR on several real-world and synthetic graphs and show that it achieves the best overall performance. Compared with HDRF, the state-of-the-art at present, the partitioning speed is increased by 3-20 times, and the partitioning quality is increased by 15% to 30% on average when achieving balanced load among all nodes.

关键词： Graph partitioning streaming algorithms Vertex-cut Distributed graph-computing frameworks Load balancing

来源：评论

学校读者我要写书评

暂无评论

The content correlation of multiple streaming edges

The content correlation of multiple streaming edges

引用

IEEE International Conference on Big Data (Big Data)

作者： de Rougemont, Michel Vimont, Guillaume Univ Paris II CNRS IRIF Paris France

ISBN: (纸本)9781538650356

We study how to detect clusters in a graph defined by a stream of edges, without storing the entire graph. We extend the approach to dynamic graphs defined by the most recent edges of the stream and to several streams. The content correlation of two streams rho(t) is the Jaccard similarity of their clusters in the windows before time t. We propose a simple and efficient method to approximate this correlation online and show that for dynamic random graphs which follow a power law degree distribution, we can guarantee a good approximation. As an application, we follow Twitter streams and compute their content correlations online. We then propose a search by correlation where answers to sets of keywords are entirely based on the small correlations of the streams. Answers are ordered by the correlations, and explanations can be traced with the stored clusters.

关键词： streaming algorithms Dynamic graphs Clustering Approximation

来源：评论

学校读者我要写书评

暂无评论

streaming Submodular Maximization: Massive Data Summarization on the Fly 14

Streaming Submodular Maximization: Massive Data Summarizatio...

引用

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

作者： Badanidiyuru, Ashwinkumar Mirzasoleiman, Baharan Karbasi, Amin Krause, Andreas Cornell Univ Ithaca NY 14853 USA Swiss Fed Inst Technol Zurich Switzerland

ISBN: (纸本)9781450329569

How can one summarize a massive data set "on the fly", i.e., without even having seen it in its entirety? In this paper, we address the problem of extracting representative elements from a large stream of data. I.e., we would like to select a subset of say k data points from the stream that are most representative according to some objective function. Many natural notions of "representativeness" satisfy submodularity, an intuitive notion of diminishing returns. Thus, such problems can be reduced to maximizing a submodular set function subject to a cardinality constraint. Classical approaches to submodular maximization require full access to the data set. We develop the first efficient streaming algorithm with constant factor 1/2 - epsilon approximation guarantee to the optimum solution, requiring only a single pass through the data, and memory independent of data size. In our experiments, we extensively evaluate the effectiveness of our approach on several applications, including training large-scale kernel methods and exemplar-based clustering, on millions of data points. We observe that our streaming method, while achieving practically the same utility value, runs about 100 times faster than previous work.

关键词： Submodular functions streaming algorithms

来源：评论

学校读者我要写书评

暂无评论

Near-Optimal streaming Ellipsoidal Rounding for General Convex Polytopes 2024

Near-Optimal Streaming Ellipsoidal Rounding for General Conv...

引用

56th Annual ACM Symposium on Theory of Computing (STOC)

作者： Makarychev, Yury Manoj, Naren Sarayu Ovsiankin, Max Toyota Technol Inst Chicago IL 60637 USA

ISBN: (纸本)9798400703836

We give near-optimal algorithms for computing an ellipsoidal rounding of a convex polytope whose vertices are given in a stream. The approximation factor is linear in the dimension (as in John's theorem) and only loses an excess logarithmic factor in the aspect ratio of the polytope. Our algorithms are nearly optimal in two senses: first, their runtimes nearly match those of the most efficient known algorithms for the offline version of the problem. Second, their approximation factors nearly match a lower bound we show against a natural class of geometric streaming algorithms. In contrast to existing works in the streaming setting that compute ellipsoidal roundings only for centrally symmetric convex polytopes, our algorithms apply to general convex polytopes. We also show how to use our algorithms to construct coresets from a stream of points that approximately preserve both the ellipsoidal rounding and the convex hull of the original set of points.

关键词： Ellipsoidal rounding John ellipsoid Convex polytopes Convex geometry Discrete geometry streaming algorithms Coresets

来源：评论

学校读者我要写书评

暂无评论

On Regularity Lemma and Barriers in streaming and Dynamic Matching 2023

On Regularity Lemma and Barriers in Streaming and Dynamic Ma...

引用

55th Annual ACM Symposium on Theory of Computing (STOC) part of the ACM Federated Computing Research Conference (FCRC)

作者： Assadi, Sepehr Behnezhad, Soheil Khanna, Sanjeev Li, Huan Rutgers State Univ New Brunswick NJ 08903 USA Northeastern Univ Boston MA USA Univ Penn Philadelphia PA USA

ISBN: (纸本)9781450399135

We present a new approach for finding matchings in dense graphs by building on Szemeredi's celebrated Regularity Lemma. This allows us to obtain non-trivial albeit slight improvements over longstanding bounds for matchings in streaming and dynamic graphs. In particular, we establish the following results for n-vertex graphs: (i) A deterministic single-pass streaming algorithm that finds a (1 - o(1))-approximate matching in o(n2) bits of space. This constitutes the first single-pass algorithm for this problem in sublinear space that improves over the 1/2-approximation of the greedy algorithm. (ii) A randomized fully dynamic algorithm that with high probability maintains a (1 - o(1))-approximate matching in o(n) worst-case update time per each edge insertion or deletion. The algorithm works even against an adaptive adversary. This is the first o(n) update-time dynamic algorithm with approximation guarantee arbitrarily close to one. Given the use of regularity lemma, the improvement obtained by our algorithms over trivial bounds is only by some (log* n)T(1) factor. Nevertheless, in each case, they show that the "right" answer to the problem is not what is dictated by the previous bounds. Finally, in the streaming model, we also present a randomized (1o(1))-approximation algorithm whose space can be upper bounded by the density of certain Ruzsa-Szemeredi (RS) graphs. While RS graphs by now have been used extensively to prove streaming lower bounds, ours is the first to use them as an upper bound tool for desigining improved streaming algorithms.

关键词： Maximum Matching streaming algorithms Dynamic algorithms Regularity Lemma

来源：评论

学校读者我要写书评

暂无评论

A Quantum Advantage for a Natural streaming Problem 62

A Quantum Advantage for a Natural Streaming Problem

引用

62nd IEEE Annual Symposium on Foundations of Computer Science (FOCS)

作者： Kallaugher, John Univ Texas Austin Dept Comp Sci Austin TX 78712 USA

ISBN: (纸本)9781665420556

Data streaming, in which a large dataset is received as a "stream" of updates, is an important model in the study of space-bounded computation. Starting with the work of Le Gall [SPAA '06], it has been known that quantum streaming algorithms can use asymptotically less space than their classical counterparts for certain problems. However, so far, all known examples of quantum advantages in streaming are for problems that are either specially constructed for that purpose, or require many streaming passes over the input. We give a one-pass quantum streaming algorithm for one of the best-studied problems in classical graph streaming-the triangle counting problem. Almost-tight parametrized upper and lower bounds are known for this problem in the classical setting;our algorithm uses polynomially less space in certain regions of the parameter space, resolving a question posed by Jain and Nayak in 2014 on achieving quantum advantages for natural streaming problems.

关键词： streaming algorithms graph algorithms quantum computation

来源：评论

学校读者我要写书评

暂无评论

Computing k centers over streaming data for small k

引用

International Journal of Computational Geometry and Applications 2014年第2期24卷 107-123页

作者： Ahn, Hee-Kap Kim, Hyo-Sil Kim, Sang-Sub Son, Wanbin Department of Computer Science and Engineering POSTECH Pohang South Korea

In this paper, we consider the k-center problem for streaming points in Rd. More precisely, we consider the single-pass streaming model, where each point in the stream is allowed to be examined only once and a small a... 详细信息

In this paper, we consider the k-center problem for streaming points in R^d. More precisely, we consider the single-pass streaming model, where each point in the stream is allowed to be examined only once and a small amount of information can be stored in a device. Since the size of memory is much smaller than the size of the data in the streaming model, it is important to develop an algorithm whose space complexity does not depend on the number of input data. We present an approximation algorithm for k = 2 that guarantees a (2 + ε)-factor using O(d/ε) space and update time in arbitrary dimensions for any metric. We show that our algorithm can be extended to approximate an optimal k-center within factor (2 + ε) for k > 2. © 2014 World Scientific Publishing Company.

关键词： approximation algorithms k -center streaming algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：