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

Sparse Recovery Using Sparse Matrices

PROCEEDINGS OF THE IEEE 2010年第6期98卷 937-947页

作者： Gilbert, Anna Indyk, Piotr Univ Michigan Dept Math Ann Arbor MI 48109 USA MIT Dept Elect Engn & Comp Sci Cambridge MA 02139 USA

In this paper, we survey algorithms for sparse recovery problems that are based on sparse random matrices. Such matrices has several attractive properties: they support algorithms with low computational complexity, and make it easy to perform incremental updates to signals. We discuss applications to several areas, including compressive sensing, data stream computing, and group testing.

关键词： Compressive sensing expanders sparse matrices sparse recovery streaming algorithms

来源：评论

学校读者我要写书评

暂无评论

Two-way and one-way quantum and classical automata with advice for online minimization problems

引用

THEORETICAL COMPUTER SCIENCE 2022年 920卷 76-94页

作者： Khadiev, Kamil Khadieva, Aliya Ziatdinov, Mansur Mannapov, Ilnaz Kravchenko, Dmitry Rivosh, Alexander Yamilov, Ramis RAS Zavoisky Phys Tech Inst FRC Kazan Sci Ctr 10-7 Sibirsky Trakt St Kazan 420029 Russia Kazan Fed Univ Inst Computat Math & Informat Technol 18 Kremlevskaya St Kazan 420008 Russia Univ Latvia Ctr Quantum Comp Scince Fac Comp 19 Raina Bulv LV-1586 Riga Latvia Univ Latvia Fac Comp 19 Raina Bulv LV-1586 Riga Latvia Yandex Technol LLC 16 Leo Tolstoy St Moscow 119021 Russia

We consider online algorithms. Typically, the model is investigated with respect to the competitive ratio. In this paper, we explore two-way automata and one-way automata as models for online algorithms. We focus on quantum and classical online algorithms. We show that there are problems that can be solved more efficiently by two-way automata with quantum and classical states than by classical two-way automata in the case of sublogarithmic memory (sublinear size), even if classical automata get advice bits. Additionally, we show that there are problems that can be solved more efficiently by oneway quantum automata than by classical one-way automata in the case of sublogarithmic memory (resp., sublinear size) and in the case of logarithmic memory (resp., linear size) even if classical automata get advice bits. (C) 2022 Elsevier B.V. All rights reserved.

关键词： Quantum computation Online algorithms streaming algorithms Online minimization problems Two-way automata Automata

来源：评论

学校读者我要写书评

暂无评论

Metric k-median clustering in insertion-only streams

引用

DISCRETE APPLIED MATHEMATICS 2021年 304卷 164-180页

作者： Braverman, Vladimir Lang, Harry Levin, Keith Rudoy, Yevgeniy Johns Hopkins Univ Dept Comp Sci Baltimore MD 21218 USA Univ Wisconsin Dept Stat Madison WI 53706 USA MIT Comp Sci & Artificial Intelligence Lab 77 Massachusetts Ave Cambridge MA 02139 USA Johns Hopkins Univ Dept Appl Math & Stat Baltimore MD USA

We present a low-constant approximation for the metric k-median problem on insertiononly streams using O(epsilon(-3)k log n) space. In particular, we present a streaming (O(epsilon(-3)k log n), 2+epsilon)-bicriterion solution that reports cluster weights. Running the offline approximation algorithm due to Byrka et al. (2015) on this bicriterion solution yields a (17.66 + epsilon)-approximation (Guha et al., 2003;Charikar et al., 2003;Braverman et al., 2011). Our result matches the best-known space requirements for streaming k-median clustering while significantly improving the approximation accuracy. We also provide a lower bound, showing that any polylog(n)-space streaming algorithm that maintains an (alpha, beta)-bicriterion must have beta >= 2. Our technique breaks the stream into segments defined by jumps in the optimal clustering cost, which increases monotonically as the stream progresses. By storing an accurate summary of recent segments of the stream and a lower-space summary of older segments, our algorithm maintains a (O(epsilon(-3)k log n), 2 + epsilon)-bicriterion solution for the entirety of the stream. In addition to our main result, we introduce a novel construction that we call a candidate set. This is a collection of points that, with high probability, contains k points that yield a near-optimal k-median cost. We present an algorithm called monotone faraway sampling (MFS) for constructing a candidate set in a single pass over a data stream. We show that using this candidate set in tandem with a coreset speeds up the search for a solution set of k cluster centers upon termination of the data stream. While coresets of smaller asymptotic size are known, comparative simplicity of MFS makes it appealing as a practical technique. (c) 2021 Elsevier B.V. All rights reserved.

关键词： streaming algorithms k-median Clustering

来源：评论

学校读者我要写书评

暂无评论

Least-Mean-Squares Coresets for Infinite Streams

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2023年第9期35卷 8699-8712页

作者： Braverman, Vladimir Feldman, Dan Lang, Harry Rus, Daniela Statman, Adiel Johns Hopkins Univ Comp Sci Deprtment Baltimore MD 21218 USA Univ Haifa Comp Sci Dept Robot & Big Data Lab IL-349883 Haifa Israel MIT Comp Sci & Artificial Intelligence Lab Cambridge MA 02139 USA

Consider a stream of d-dimensional rows (points in R-d) arriving sequentially. An epsilon-coreset is a positively weighted subset that approximates their sum of squared distances to any linear subspace of R-d, up to a 1 +/- epsilon factor. Unlike other data summarizations, such a coreset: (1) can be used to minimize faster any optimization function that uses this sum, such as regularized or constrained regression, (2) preserves input sparsity;(3) easily interpretable;(4) avoids numerical errors;(5) applies to problems with constraints on the input, such as subspaces that are spanned by few input points. Our main result is the first algorithm that returns such an epsilon-coreset using finite and constant memory during the streaming, i.e., independent of n, the number of rows seen so far. The coreset consists of O(d log(2) d/epsilon(2)) weighted rows, which is nearly optimal according to existing lower bounds of Omega(d/epsilon(2)). We support our findings with experiments on theWikipedia dataset benchmarked against state-of-the-art algorithms.

关键词： Big data coresets optimization streaming algorithms

来源：评论

学校读者我要写书评

暂无评论

Sorting streamed multisets

引用

INFORMATION PROCESSING LETTERS 2008年第6期108卷 418-421页

作者： Gagie, Travis Univ Piemonte Orientale Dipartimento Informat Alessandria AL Italy

Sorting is a classic problem and one to which many others reduce easily. In the streaming model, however, we are allowed only one pass over the input and sublinear memory, so in general we cannot sort. In this paper we show that, to determine the sorted order of a multiset s of size If containing sigma >= 2 distinct elements using one pass and o(n log sigma) bits of memory, it is generally necessary and sufficient that its entropy H = o(log sigma). Specifically, if S = {S-1.....S-n) and S-i1.....S-in is the stable sort of s, then we can compute i(1).....i(n) in one pass using O((H + 1)n) time and O(Hn) bits of memory, with a simple combination of classic techniques. On the other hand, in the worst case it takes that much memory to compute any sorted ordering of s in one pass. (C) 2008 Elsevier B.V. All rights reserved.

关键词： algorithms On-line algorithms Sorting streaming algorithms

来源：评论

学校读者我要写书评

暂无评论

Weighted sampling without replacement from data streams

引用

INFORMATION PROCESSING LETTERS 2015年第12期115卷 923-926页

作者： Braverman, Vladimir Ostroysky, Rafail Vorsanger, Gregory Johns Hopkins Univ Dept Comp Sci Baltimore MD 21218 USA Univ Calif Los Angeles Dept Comp Sci Los Angeles CA 90024 USA Univ Calif Los Angeles Dept Math Los Angeles CA 90024 USA

Weighted sampling without replacement has proved to be a very important tool in designing new algorithms. Efraimidis and Spirakis [5] presented an algorithm for weighted sampling without replacement from data streams. Their algorithm works under the assumption of precise computations over the interval [0,1]. Cohen and Kaplan [3] used similar methods for their bottom-k sketches. Efraimidis and Spirakis ask as an open question whether using finite precision arithmetic impacts the accuracy of their algorithm. In this paper we show a method to avoid this problem by providing a precise reduction from k-sampling without replacement to k-sampling with replacement. We call the resulting method Cascade Sampling. (C) 2015 Published by Elsevier B.V.

关键词： algorithms On-line algorithms Sampling streaming algorithms

来源：评论

学校读者我要写书评

暂无评论

What to Expect When You Are Expecting on the Grassmannian

引用

IEEE SIGNAL PROCESSING LETTERS 2017年第6期24卷 872-876页

作者： Eftekhari, Armin Balzano, Laura Wakin, Michael B. Alan Turing Inst London NW1 2DB England Univ Michigan Dept Elect Engn & Comp Sci Ann Arbor MI 48105 USA Colorado Sch Mines Dept Elect Engn & Comp Sci Golden CO 80401 USA

Consider an incoming sequence of vectors, all belonging to an unknown subspace S, and each with many missing entries. In order to estimate S, it is common to partition the data into blocks and iteratively update the estimate of S with each new incoming measurement block. In this letter, we investigate a rather basic question: Is it possible to identify S by averaging the range of the partially observed incoming measurement blocks on the Grassmannian? We show that, in general, the span of the incoming blocks is in fact a biased estimator of S when data suffer from erasures, and we find an upper bound for this bias. We reach this conclusion by examining the defining optimization program for the Frechet expectation on the Grassmannian, and with the aid of a sharp perturbation bound and standard large deviation results.

关键词： Frechet expectation Grassmannian averaging matrix completion principal component analysis streaming algorithms subspace identification

来源：评论

学校读者我要写书评

暂无评论

Generating statistical insights into network behavior using SKETURE

引用

JOURNAL OF HIGH SPEED NETWORKS 2016年第1期22卷 65-76页

作者： Baddar, Sherenaz Al-Haj Merlo, Alessio Migliardi, Mauro Univ Jordan KASIT Amman 11942 Jordan Univ Genoa DIBRIS I-16145 Genoa Italy Univ Padua I-35131 Padua Italy

Tools that generate informative and efficient statistical summaries of nodes' activities in a given network have become crucial for robust behavioral anomaly detection. Yet, addressing network abnormalities and threats should not be done at the expense of users' privacy. In this study we illustrate the use of SKETURE, a packet analysis tool leveraging a sketch-based architecture, in summarizing the behavior of nodes in a real campus network for a whole month, without breaching users' privacy. Moreover, we share some insights into this network which were compiled using SKETURE.

关键词： Traffic analysis tools statistical modeling streaming algorithms sketch-based analysis

来源：评论

学校读者我要写书评

暂无评论

Order matters! Harnessing a world of orderings for reasoning over massive data

引用

SEMANTIC WEB 2013年第2期4卷 219-231页

作者： Della Valle, Emanuele Schlobach, Stefan Kroetzsch, Markus Bozzon, Alessandro Ceri, Stefano Horrocks, Ian Politecn Milan DEI I-20133 Milan Italy Vrije Univ Amsterdam Amsterdam Netherlands Univ Oxford Oxford England

More and more applications require real-time processing of massive, dynamically generated, ordered data;order is an essential factor as it reflects recency or relevance. Semantic technologies risk being unable to meet the needs of such applications, as they are not equipped with the appropriate instruments for answering queries over massive, highly dynamic, ordered data sets. In this vision paper, we argue that some data management techniques should be exported to the context of semantic technologies, by integrating ordering with reasoning, and by using methods which are inspired by stream and rank-aware data management. We systematically explore the problem space, and point both to problems which have been successfully approached and to problems which still need fundamental research, in an attempt to stimulate and guide a paradigm shift in semantic technologies.

关键词： Massive data inference ordering streaming algorithms

来源：评论

学校读者我要写书评

暂无评论

streaming approximation scheme for minimizing total completion time on parallel machines subject to varying processing capacity

引用

THEORETICAL COMPUTER SCIENCE 2023年第1期961卷

作者： Fu, Bin Huo, Yumei Zhao, Hairong Univ Texas Rio Grande Valley Dept Comp Sci Edinburg TX 78539 USA CUNY Coll Staten Isl Dept Comp Sci Staten Isl NY 10314 USA Purdue Univ Northwest Dept Comp Sci Hammond IN 46323 USA

We study the problem of minimizing total completion time on parallel machines subject to varying processing capacity. In this paper, we develop an approximation scheme for the problem under the data stream model where the input data is massive and cannot fit into memory and thus can only be scanned a few times. Our algorithm can compute an approximate value of the optimal total completion time in one pass and output the schedule with the approximate value in two passes.(c) 2023 Elsevier B.V. All rights reserved.

关键词： streaming algorithms Scheduling Parallel machines Total completion time Varying processing capacity

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：