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

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

来源：评论

学校读者我要写书评

暂无评论

Linear sketching over F2 18

Linear sketching over F2

引用

Proceedings of the 33rd Computational Complexity Conference

作者： Sampath Kannan Elchanan Mossel Swagato Sanyal Grigory Yaroslavtsev University of Pennsylvania Massachusetts Institute of Technology Nanyang Technological University and National University of Singapore Singapore Indiana University Bloomington

ISBN: (纸本)9783959770699

We initiate a systematic study of linear sketching over F2. For a given Boolean function treated as f: Fn2 → F2 a randomized F2-sketch is a distribution M over d × n matrices with elements over F2 such that Mx suffices for computing f(x) with high probability. Such sketches for d ≪ n can be used to design small-space distributed and streaming *** by these applications we study a connection between F2-sketching and a two-player one-way communication game for the corresponding XOR-function. We conjecture that F2-sketching is optimal for this communication game. Our results confirm this conjecture for multiple important classes of functions: 1) low-degree F2-polynomials, 2) functions with sparse Fourier spectrum, 3) most symmetric functions, 4) recursive majority function. These results rely on a new structural theorem that shows that F2-sketching is optimal (up to constant factors) for uniformly distributed ***, we show that (non-uniform) streaming algorithms that have to process random updates over F2 can be constructed as F2-sketches for the uniform distribution. In contrast with the previous work of Li, Nguyen and Woodruff (STOC'14) who show an analogous result for linear sketches over integers in the adversarial setting our result does not require the stream length to be triply exponential in n and holds for streams of length Õ(n) constructed through uniformly random updates.

关键词： communication complexity linear sketch streaming algorithms XOR-functions

来源：评论

学校读者我要写书评

暂无评论

A Minimal Variance Estimator for the Cardinality of Big Data Set Intersection 17

A Minimal Variance Estimator for the Cardinality of Big Data...

引用

23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD)

作者： Cohen, Reuven Katzir, Liran Yehezkel, Aviv Technion Dept Comp Sci IL-32000 Haifa Israel

ISBN: (纸本)9781450348874

In recent years there has been a growing interest in developing "streaming algorithms" for efficient processing and querying of continuous data streams. These algorithms seek to provide accurate results while minimizing the required storage and the processing time, at the price of a small inaccuracy in their output. A fundamental query of interest is the intersection size of two big data streams. This problem arises in many different application areas, such as network monitoring, database systems, data integration and information retrieval. In this paper we develop a new algorithm for this problem, based on the Maximum Likelihood (ML) method. We show that this algorithm outperforms all known schemes in terms of the estimation's quality (lower variance) and that it asymptotically achieves the optimal variance.

关键词： Data mining streaming algorithms Cardinality estimation Set intersection

来源：评论

学校读者我要写书评

暂无评论

Accurate Low-Space Approximation of Metric k-Median for Insertion-Only Streams 1

引用

3rd International Conference on algorithms and Discrete Applied Mathematics (CALDAM)

作者： Braverman, Vladimir Lang, Harry Levin, Keith Johns Hopkins Univ Dept Comp Sci Baltimore MD 21218 USA Johns Hopkins Univ Dept Math Baltimore MD 21218 USA

ISBN: (数字)9783319530079

ISBN: (纸本)9783319530062;9783319530079

We present a low-constant approximation for metric k median on an insertion-only stream of n points using 0O(epsilon(-3)k log n) space. In particular, we present a streaming (0(epsilon(-3)k log n), 2 + 6)-bicriterion solution that reports cluster weights. It is well-known that running an offline algorithm on this bicriterion solution yields a (17.66 + epsilon)-approximation. Previously, there have been two lines of research that trade off between space and accuracy in the streaming k-median problem. To date, the best-known (k, 6)-coreset construction requires O (epsilon(-2) k log(4) n) space [8], while the best-known 0 (k log n)-space algorithm provides only a (0 (k log n), 1063)-bicriterion [3]. Our work narrows this gap significantly, matching the best-known space while significantly improving the accuracy from 1063 to 2 + epsilon. We also provide a matching 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 a storing an accurate summary of recent segments and a lower-space summary of older segments, our algorithm maintains a (0(epsilon(-3) k log n), 2 + epsilon)-bicriterion solution for the entire input.

关键词： streaming algorithms k-median Clustering

来源：评论

学校读者我要写书评

暂无评论

Near optimal frequent directions for sketching dense and sparse matrices

The Journal of Machine Learning Research

引用

The Journal of Machine Learning Research 2019年第1期20卷

作者： Zengfeng Huang School of Data Science Fudan University Shanghai China

Given a large matrix A ∈ ℝn×d, we consider the problem of computing a sketch matrix B ∈ ℝl×d which is significantly smaller than but still well approximates A. We consider the problems in the streaming model, where the algorithm can only make one pass over the input with limited working space, and we are interested in minimizing the covariance error ║ATA - BTB║2: The popular Frequent Directions algorithm of Liberty (2013) and its variants achieve optimal space-error tradeoffs. However, whether the running time can be improved remains an unanswered question. In this paper, we almost settle the question by proving that the time complexity of this problem is equivalent to that of matrix multiplication up to lower order terms. Specifically, we provide new space-optimal algorithms with faster running times and also show that the running times of our algorithms can be improved if and only if the state-of-the-art running time of matrix multiplication can be improved significantly.

关键词： frequent directions matrix sketching streaming algorithms

来源：评论

学校读者我要写书评

暂无评论

Submodular Optimization Over Sliding Windows 17

Submodular Optimization Over Sliding Windows

引用

26th International Conference on World Wide Web (WWW)

作者： Epasto, Alessandro Lattanzi, Silvio Vassilvitskii, Sergei Zadimoghaddam, Morteza Google New York NY 10011 USA

ISBN: (纸本)9781450349130

Maximizing submodular functions under cardinality constraints lies at the core of numerous data mining and machine learning applications, including data diversification, data summarization, and coverage problems. In this work, we study this question in the context of data streams, where elements arrive one at a time, and we want to design low-memory and fast update-time algorithms that maintain a good solution. Specifically, we focus on the sliding window model, where we are asked to maintain a solution that considers only the last W items. In this context, we provide the first non-trivial algorithm that maintains a provable approximation of the optimum using space sublinear in the size of the window. In particular we give a 1/3 - epsilon approximation algorithm that uses space polylogarithmic in the spread of the values of the elements, Phi, and linear in the solution size k for any constant epsilon > 0. At the same time, processing each element only requires a polylogarithmic number of evaluations of the function itself. When a better approximation is desired, we show a different algorithm that, at the cost of using more memory, provides a 1/2-epsilon approximation, and allows a tunable trade-off between average update time and space. This algorithm matches the best known approximation guarantees for submodular optimization in insertion-only streams, a less general formulation of the problem. We demonstrate the efficacy of the algorithms on a number of real world datasets, showing that their practical performance far exceeds the theoretical bounds. The algorithms preserve high quality solutions in streams with millions of items, while storing a negligible fraction of them.

关键词： submodular maximization sliding-window streams streaming algorithms

来源：评论

学校读者我要写书评

暂无评论

A High-Performance Algorithm for Identifying Frequent Items in Data Streams 17

A High-Performance Algorithm for Identifying Frequent Items ...

引用

ACM Internet Measurement Conference (IMC)

作者： Anderson, Daniel Bevan, Pryce Lang, Kevin Liberty, Edo Rhodes, Lee Thaler, Justin Georgetown Univ Washington DC 20057 USA Georgetown Univ Washington DC 20057 USA Amazon Washington DC 20057 USA Oath Washington DC 20057 USA

ISBN: (纸本)9781450351188

Estimating frequencies of items over data streams is a common building block in streaming data measurement and analysis. Misra and Gries introduced their seminal algorithm for the problem in 1982, and the problem has since been revisited many times due its practicality and applicability. We describe a highly optimized version of Misra and Gries' algorithm that is suitable for deployment in industrial settings. Our code is made public via an open source library called Data Sketches that is already used by several companies and production systems. Our algorithm improves on two theoretical and practical aspects of prior work. First, it handles weighted updates in amortized constant time, a common requirement in practice. Second, it uses a simple and fast method for merging summaries that asymptotically improves on prior work even for unweighted streams. We describe experiments confirming that our algorithms are more efficient than prior proposals.

关键词： streaming algorithms mergeable summaries frequent items

来源：评论

学校读者我要写书评

暂无评论

Tight Bounds for Single-Pass streaming Complexity of the Set Cover Problem 16

Tight Bounds for Single-Pass Streaming Complexity of the Set...

引用

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

作者： Assadi, Sepehr Khanna, Sanjeev Li, Yang Univ Penn Dept Comp & Informat Sci 200 S 33Rd St Philadelphia PA 19104 USA

ISBN: (纸本)9781450341325

We resolve the space complexity of single-pass streaming algorithms for approximating the classic set cover problem. For finding an alpha-approximate set cover (for alpha = o(root n)) via a single-pass streaming algorithm, we show that Theta(mn/alpha) space is both sufficient and necessary (up to an O(log n) factor);here m denotes number of the sets and n denotes size of the universe. This provides a strong negative answer to the open question posed by Indyk et al. (2015) regarding the possibility of having a single-pass algorithm with a small approximation factor that uses sub-linear space. We further study the problem of estimating the size of a minimum set cover (as opposed to finding the actual sets), and establish that an additional factor of alpha saving in the space is achievable in this case and that this is the best possible. In other words, we show that Theta(mn/alpha(2)) space is both sufficient and necessary (up to logarithmic factors) for estimating the size of a minimum set cover to within a factor of alpha. Our algorithm in fact works for the more general problem of estimating the optimal value of a covering integer program. On the other hand, our lower bound holds even for set cover instances where the sets are presented in a random order.

关键词： streaming algorithms communication complexity set cover covering integer programs

来源：评论

学校读者我要写书评

暂无评论

Concept Drift Detection via Improved Deep Belief Network

Concept Drift Detection via Improved Deep Belief Network

引用

Iranian Conference on Electrical Engineering

作者： Nafiseh Hatamikhah Morteza Barari Mohammad Reza Kangavari Mohammad Ali Keyvanrad Computer Engineering Dept. Shahid Beheshti University Tehran Iran Electrical Engineering Dept. Amirkabir University of Technology Tehran Iran Computer Engineering Dept. University of Science & Technology Tehran Iran Computer Engineering Dept. Amirkabir University of Technology Tehran Iran

One of the issues raised in streaming data is concept drift detection. In fact, the process of concept drift conies from natural tendency events in the real world to change over time. For example, in data receiving from credit card transactions, detect when transactions rise suddenly, can help in identifying the fraud. In this paper regards to the importance of concept drift in streaming data, a solution to accurate diagnosis and timely is presented. This solution is based on ensemble algorithm and "streaming ensemble algorithm" (SEA) algorithm that SEA algorithm is used as one of the most commonly stream algorithms. This approach uses a deep belief network as a basic model in the SEA algorithm. In the method which is presented in this paper, we used the change of classification error on new data for concept drift detection. Analyzing the results shows that the proposed method compared with similar algorithms, in addition to a significant reduction in the runtime, improved F_measure criteria.

关键词： streaming Data Concept Drift streaming algorithms Deep Learning Deep Belief Network

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：