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

CoCoS: Fast and Accurate Distributed Triangle Counting in Graph Streams

ACM TRANSACTIONS ON KNOWLEDGE DISCOVERY FROM DATA 2021年第3期15卷 38-38页

作者： Shin, Kijung Lee, Euiwoong Oh, Jinoh Hammoud, Mohammad Faloutsos, Christos Korea Adv Inst Sci & Technol 291 Daehak Ro Daejeon 34141 South Korea Univ Michigan 500 S State St Ann Arbor MI 48109 USA Carnegie Mellon Univ 5000 Forbes Ave Pittsburgh PA 15213 USA Carnegie Mellon Univ Qatar Doha 24866 Qatar

Given a graph stream, how can we estimate the number of triangles in it using multiple machines with limited storage? Specifically, how should edges be processed and sampled across the machines for rapid and accurate estimation? The count of triangles (i.e., cliques of size three) has proven useful in numerous applications, including anomaly detection, community detection, and link recommendation. For triangle counting in large and dynamic graphs, recent work has focused largely on streaming algorithms and distributed algorithms but little on their combinations for "the best of both worlds." In this work, we propose CoCoS, a fast and accurate distributed streaming algorithm for estimating the counts of global triangles (i.e., all triangles) and local triangles incident to each node. Making one pass over the input stream, CoCoS carefully processes and stores the edges across multiple machines so that the redundant use of computational and storage resources is minimized. Compared to baselines, CoCoS is: (a) accurate: giving up to 39x smaller estimation error;(b) fast: up to 10.4x faster, scaling linearly with the size of the input stream;and (c) theoretically sound: yielding unbiased estimates.

关键词： Graph stream triangle counting sampling streaming algorithms distributed algorithms

来源：评论

学校读者我要写书评

暂无评论

Deterministic Sampling and Range Counting in Geometric Data Streams

引用

ACM TRANSACTIONS ON algorithms 2007年第2期3卷 16–es页

作者： Bagchi, Amitabha Chaudhary, Amitabh Eppstein, David Goodrich, Michael T. Indian Inst Technol Dept Comp Sci & Engn Hauz Khas New Delhi 110016 India Notre Dame Univ Dept Comp Sci & Engn Notre Dame IN 46556 USA Univ Calif Irvine Sch Informat & Comp Sci Irvine CA 92697 USA

We present memory-efficient deterministic algorithms for constructing epsilon-nets and epsilon-approximations of streams of geometric data. Unlike probabilistic approaches, these deterministic samples provide guaranteed bounds on their approximation factors. We show how our deterministic samples can be used to answer approximate online iceberg geometric queries on data streams. We use these techniques to approximate several robust statistics of geometric data streams, including Tukey depth, simplicial depth, regression depth, the Thiel-Sen estimator, and the least median of squares. Our algorithms use only a polylogarithmic amount of memory, provided the desired approximation factors are at least inverse-polylogarithmic. We also include a lower bound for noniceberg geometric queries.

关键词： Data streams streaming algorithms geometric data sampling robust statistics epsilon nets iceberg queries range counting

来源：评论

学校读者我要写书评

暂无评论

Space-Constrained Interval Selection

引用

ACM TRANSACTIONS ON algorithms 2016年第4期12卷 51-51页

作者： Emek, Yuval Halldorsson, Magnus M. Rosen, Adi Technion Israel Inst Technol Fac Ind Engn & Management IL-3200003 Haifa Israel Reykjavik Univ Sch Comp Sci ICE TCS Reykjavik Iceland Univ Paris Diderot IRIF Case 7014 F-75205 Paris 13 France

We study streaming algorithms for the interval selection problem: finding a maximum cardinality subset of disjoint intervals on the line. A deterministic 2-approximation streaming algorithm for this problem is developed, together with an algorithm for the special case of proper intervals, achieving improved approximation ratio of 3/2. We complement these upper bounds by proving that they are essentially the best possible in the streaming setting: It is shown that an approximation ratio of 2 - epsilon (or 3/2 - epsilon for proper intervals) cannot be achieved unless the space is linear in the input size. In passing, we also answer an open question of Adler and Azar (J. Scheduling 2003) regarding the space complexity of constant-competitive randomized preemptive online algorithms for the same problem.

关键词： streaming algorithms interval selection online algorithms lower bounds

来源：评论

学校读者我要写书评

暂无评论

Model Counting Meets F0 Estimation

引用

ACM TRANSACTIONS ON DATABASE SYSTEMS 2023年第3期48卷 7-7页

作者： Pavan, A. Vinodchandran, N. V. Bhattacharyya, Arnab Meel, Kuldeep S. Iowa State Univ Dept Comp Sci Ames IA 50011 USA Univ Nebraska Lincoln Dept Comp Sci & Engn Lincoln NE 68588 USA Natl Univ Singapore NUS Sch Comp 13 Comp Dr Singapore 117417 Singapore

Constraint satisfaction problems (CSPs) and data stream models are two powerful abstractions to capture a wide variety of problems arising in different domains of computer science. Developments in the two communities have mostly occurred independently and with little interaction between them. In this work, we seek to investigate whether bridging the seeming communication gap between the two communities may pave the way to richer fundamental insights. To this end, we focus on two foundational problems: model counting for CSP's and computation of zeroth frequency moments (F-0) for data streams. Our investigations lead us to observe a striking similarity in the core techniques employed in the algorithmic frameworks that have evolved separately for model counting and F-0 computation. We design a recipe for translating algorithms developed for F-0 estimation to model counting, resulting in new algorithms for model counting. We also provide a recipe for transforming sampling algorithm over streams to constraint sampling algorithms. We then observe that algorithms in the context of distributed streaming can be transformed into distributed algorithms for model counting. We next turn our attention to viewing streaming from the lens of counting and show that framing F-0 estimation as a special case of #DNF counting allows us to obtain a general recipe for a rich class of streaming problems, which had been subjected to case-specific analysis in prior works. In particular, our view yields an algorithm for multidimensional range efficient F-0 estimation with a simpler analysis.

关键词： Model counting streaming algorithms F-0-computation DNF counting

来源：评论

学校读者我要写书评

暂无评论

Randomized counter-based algorithms for frequency estimation over data streams in O (log log N) space

引用

THEORETICAL COMPUTER SCIENCE 2024年 984卷

作者： Kakimura, Naonori Nitta, Riku Keio Univ Yokohama 2238522 Japan IBM Japan Ltd Chuo Japan

This note studies the problem of estimating frequencies of items over data streams. We propose a simple streaming algorithm for the problem in small space complexity. Our algorithm is a counter-based algorithm with the aid of probabilistic counting. We show that our algorithm with k counters computes, with probability at least 1 -.., the estimation with relative error at most (1+epsilon)N/k, taking O (k log log N/k +k log (epsilon(-1)delta(-1)k) + k log l) space in expectation, where N is the total number of items and l is the number of different items.

关键词： Frequent items streaming algorithms Probabilistic counting

来源：评论

学校读者我要写书评

暂无评论

UDDSketch: Accurate Tracking of Quantiles in Data Streams

引用

IEEE ACCESS 2020年 8卷 147604-147617页

作者： Epicoco, Italo Melle, Catiuscia Cafaro, Massimo Pulimeno, Marco Morleo, Giuseppe Univ Salento Dept Engn Innovat I-73100 Lecce Italy

We present UDDSketch (Uniform DDSketch), a novel sketch for fast and accurate tracking of quantiles in data streams. This sketch is heavily inspired by the recently introduced DDSketch, and is based on a novel bucket collapsing procedure that allows overcoming the intrinsic limits of the corresponding DDSketch procedures. Indeed, the DDSketch bucket collapsing procedure does not allow the derivation of formal guarantees on the accuracy of quantile estimation for data which does not follow a sub-exponential distribution. On the contrary, UDDSketch is designed so that accuracy guarantees can be given over the full range of quantiles and for arbitrary distribution in input. Moreover, our algorithm fully exploits the budgeted memory adaptively in order to guarantee the best possible accuracy over the full range of quantiles. Extensive experimental results on both synthetic and real datasets confirm the validity of our approach.

关键词： Histograms Approximation algorithms Estimation Databases Data structures Memory management Measurement Sketches quantiles streaming algorithms

来源：评论

学校读者我要写书评

暂无评论

The Power of Subsampling in Submodular Maximization

引用

MATHEMATICS OF OPERATIONS RESEARCH 2022年第2期47卷 1365-1393页

作者： Harshaw, Christopher Kazemi, Ehsan Feldman, Moran Karbasi, Amin Yale Univ Dept Comp Sci New Haven CT 06520 USA Google CH-8002 Zurich Switzerland Univ Haifa Dept Comp Sci IL-3498838 Haifa Israel Yale Univ Dept Elect Engn New Haven CT 06520 USA Yale Univ Dept Stat & Data Sci New Haven CT 06520 USA

We propose subsampling as a unified algorithmic technique for submodular maximization in centralized and online settings. The idea is simple: independently sample elements from the ground set and use simple combinatorial techniques (such as greedy or local search) on these sampled elements. We show that this approach leads to optimal/state-of-the-art results despite being much simpler than existing methods. In the usual off-line setting, we present SAMPLEGREEDY, which obtains a (p + 2 + o(1))-approximation for maximizing a submodular function subject to a p-extendible system using O(n + nk/p) evaluation and feasibility queries, where k is the size of the largest feasible set. The approximation ratio improves to p + 1 and p for monotone submodular and linear objectives, respectively. In the streaming setting, we present Sample-streaming, which obtains a (4p + 2 - o(1))-approximation for maximizing a submodular function subject to a p-matchoid using O(k) memory and O(km/p) evaluation and feasibility queries per element, and m is the number of matroids defining the p-matchoid. The approximation ratio improves to 4p for monotone submodular objectives. We empirically demonstrate the effectiveness of our algorithms on video summarization, location summarization, and movie recommendation tasks.

关键词： submodular maximization subsampling streaming algorithms approximation algorithms p-extendible systems p-matchoids

来源：评论

学校读者我要写书评

暂无评论

Persistent Summaries

引用

ACM TRANSACTIONS ON DATABASE SYSTEMS 2022年第3期47卷 11-11页

作者： Zeng, Tianjing Wei, Zhewei Luo, Ge Yi, Ke Du, Xiaoyong Wen, Ji-Rong Renmin Univ China Gaoling Sch Artificial Intelligence 59 Zhongguancun St Beijing Peoples R China Huatai Secur Shanghai Asset Management 18 Dongfang Rd Shanghai Peoples R China Hong Kong Univ Sci & Technol Clear Water Bay Kowloon Hong Kong Peoples R China Renmin Univ China Sch Informat Beijing Peoples R China

A persistent data structure, also known as a multiversion data structure in the database literature, is a data structure that preserves all its previous versions as it is updated over time. Every update (inserting, deleting, or changing a data record) to the data structure creates a new version, while all the versions are kept in the data structure so that any previous version can still be queried. Persistent data structures aim at recording all versions accurately, which results in a space requirement that is at least linear to the number of updates. In many of today's big data applications, in particular, for highspeed streaming data, the volume and velocity of the data are so high that we cannot afford to store everything. Therefore, streaming algorithms have received a lot of attention in the research community, which uses only sublinear space by sacrificing slightly on accuracy. All streaming algorithms work by maintaining a small data structure in memory, which is usually called a sketch, summary, or synopsis. The summary is updated upon the arrival of every element in the stream, thus it is ephemeral, meaning that it can only answer queries about the current status of the stream. In this article, we aim at designing persistent summaries, thereby giving streaming algorithms the ability to answer queries about the stream at any prior time.

关键词： Summaries streaming algorithms sketches

来源：评论

学校读者我要写书评

暂无评论

Comparison-Based Time-Space Lower Bounds for Selection

引用

ACM TRANSACTIONS ON algorithms 2010年第2期6卷 1–16页

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

We establish the first nontrivial lower bounds on time-space trade-offs for the selection problem. We prove that any comparison-based randomized algorithm for finding the median requires Omega (n log log(S) n) expected time in the RAM model (or more generally in the comparison branching program model), if we have S bits of extra space besides the read-only input array. This bound is tight for all S >> log n, and remains true even if the array is given in a random order. Our result thus answers a 16-year-old question of Munro and Raman [1996], and also complements recent lower bounds that are restricted to sequential access, as in the multipass streaming model [Chakrabarti et al. 2008b]. We also prove that any comparison-based, deterministic, multipass streaming algorithm for finding the median requires Omega (n log*(n/s) + n log(s) n) worst-case time (in scanning plus comparisons), if we have s cells of space. This bound is also tight for all s >> log(2) n. We get deterministic lower bounds for I/O-efficient algorithms as well. The proofs in this article are self-contained and do not rely on communication complexity techniques.

关键词： algorithms Theory Adversary arguments lower bounds median finding RAM randomized algorithms streaming algorithms time-space trade-offs

来源：评论

学校读者我要写书评

暂无评论

Sparser Johnson-Lindenstrauss Transforms

引用

JOURNAL OF THE ACM 2014年第1期61卷 4-4页

作者： Kane, Daniel M. Nelson, Jelani Stanford Univ Dept Math Stanford CA 94305 USA Harvard Univ Sch Engn & Appl Sci Cambridge MA 02138 USA

We give two different and simple constructions for dimensionality reduction in l(2) via linear mappings that are sparse: only an O(epsilon)- fraction of entries in each column of our embedding matrices are non-zero to achieve distortion 1+epsilon with high probability, while still achieving the asymptotically optimal number of rows. These are the first constructions to provide subconstant sparsity for all values of parameters, improving upon previous works of Achlioptas [2003] and Dasgupta et al. [2010]. Such distributions can be used to speed up applications where l(2) dimensionality reduction is used.

关键词： algorithms Theory Dimensionality reduction Johnson-Lindenstrauss numerical linear algebra streaming algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：