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

Approximate continuous querying over distributed streams

ACM TRANSACTIONS ON dataBASE SYSTEMS 2008年第2期33卷 129-167页

作者： Cormode, Graham Garofalakis, Minos AT&T Labs Res Florham Pk NJ USA Univ Calif Berkeley Berkeley CA 94720 USA

While traditional database systems optimize for performance on one-shot query processing, emerging large-scale monitoring applications require continuous tracking of complex data-analysis queries over collections of physically distributed streams. Thus, effective solutions have to be simultaneously space/time efficient (at each remote monitor site), communication efficient (across the underlying communication network), and provide continuous, guaranteed-quality approximate query answers. In this paper, we propose novel algorithmic solutions for the problem of continuously tracking a broad class of complex aggregate queries in such a distributed-streams setting. Our tracking schemes maintain approximate query answers with provable error guarantees, while simultaneously optimizing the storage space and processing time at each remote site, and the communication cost across the network. In a nutshell, our algorithms rely on tracking general-purpose randomized sketch summaries of local streams at remote sites along with concise prediction models of local site behavior in order to produce highly communication-and space/time-efficient solutions. The end result is a powerful approximate query tracking framework that readily incorporates several complex analysis queries (including distributed join and multi-join aggregates, and approximate wavelet representations), thus giving the first known low-overhead tracking solution for such queries in the distributed-streams model. Experiments with real data validate our approach, revealing significant savings over naive solutions as well as our analytical worst-case guarantees.

关键词： algorithms experimentation performance continuous distributed monitoring data stream algorithms data synopses approximate query processing

来源：评论

学校读者我要写书评

暂无评论

Polylog Space Compression, Pushdown Compression, and Lempel-Ziv Are Incomparable

引用

THEORY OF COMPUTING SYSTEMS 2011年第4期48卷 731-766页

作者： Mayordomo, Elvira Moser, Philippe Perifel, Sylvain Univ Zaragoza Dept Inform & Ingn Sistemas Inst Invest Ingn Aragon I3A Zaragoza 50018 Spain Natl Univ Ireland Maynooth Dept Comp Sci Maynooth Co Kildare Ireland Univ Paris 07 CNRS LIAFA Paris France

The pressing need for efficient compression schemes for XML documents has recently been focused on stack computation (Hariharan, S., & Shankar, P. in: Proceedings of the 2006 IEEE data compression conference, p. 453, 2006;League, C., & Eng, K. in: Proceedings of the 2007 IEEE data compression conference, pp. 272-282, 2007), and in particular calls for a formulation of information-lossless stack or pushdown compressors that allows a formal analysis of their performance and a more ambitious use of the stack in XML compression, where so far it is mainly connected to parsing mechanisms. In this paper we introduce the model of pushdown compressor, based on pushdown transducers that compute a single injective function while keeping the widest generality regarding stack computation. We also consider online compression algorithms that use at most polylogarithmic space (plogon). These algorithms correspond to compressors in the data stream model. We compare the performance of these two families of compressors with each other and with the general purpose Lempel-Ziv algorithm. This comparison is made without any a priori assumption on the data's source and considering the asymptotic compression ratio for infinite sequences. We prove that in all cases they are incomparable.

关键词： Compression algorithms Plogon Computational complexity data stream algorithms Lempel-Ziv algorithm Pushdown compression

来源：评论

学校读者我要写书评

暂无评论

An estimator for matching size in low arboricity graphs with two applications

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2023年第1期45卷 1-14页

作者： Jowhari, Hossein KN Toosi Univ Technol Fac Math Dept Comp Sci & Stat Tehran Iran

In this paper, we present a new degree-based estimator for the size of maximum matching in bounded arboricity graphs. When the arboricity of the graph is bounded by alpha, the estimator gives a alpha + 2 factor approximation of the matching size. For planar graphs, we show the estimator does better and returns a 3.5 approximation of the matching size. Using this estimator, we get new results for approximating the matching size of planar graphs in the streaming and distributed models of computation. In particular, in the vertex-arrival streams, we get a randomized O (root n/epsilon(2) log n) space algorithm for approximating the matching size of a planar graph on n vertices within (3.5+epsilon) factor. Similarly, we get a simultaneous protocol in the vertex-partition model for approximating the matching size within (3.5 + epsilon) factor using O (n(2/3)/epsilon(2) log n) communication from each player. In comparison with previous works, the estimator in this paper does not need to know the arboricity of the input graph and improves the approximation factor in the case of planar graphs.

关键词： Maximum matching Approximation algorithms data stream algorithms

来源：评论

学校读者我要写书评

暂无评论

Quantiles over data streams: experimental comparisons, new analyses, and further improvements

引用

VLDB JOURNAL 2016年第4期25卷 449-472页

作者： Luo, Ge Wang, Lu Yi, Ke Cormode, Graham HKUST Dept Compute Sci & Engn Kowloon Hong Kong Peoples R China Univ Warwick Dept Comp Sci Coventry W Midlands England

A fundamental problem in data management and analysis is to generate descriptions of the distribution of data. It is most common to give such descriptions in terms of the cumulative distribution, which is characterized by the quantiles of the data. The design and engineering of efficient methods to find these quantiles has attracted much study, especially in the case where the data are given incrementally, and we must compute the quantiles in an online, streaming fashion. While such algorithms have proved to be extremely useful in practice, there has been limited formal comparison of the competing methods, and no comprehensive study of their performance. In this paper, we remedy this deficit by providing a taxonomy of different methods and describe efficient implementations. In doing so, we propose new variants that have not been studied before, yet which outperform existing methods. To illustrate this, we provide detailed experimental comparisons demonstrating the trade-offs between space, time, and accuracy for quantile computation.

关键词： data stream algorithms Quantiles Ordinary least squares

来源：评论

学校读者我要写书评

暂无评论

Bursty and hierarchical structure in streams

引用

data MINING AND KNOWLEDGE DISCOVERY 2003年第4期7卷 373-397页

作者： Kleinberg, J Cornell Univ Dept Comp Sci Ithaca NY 14853 USA

A fundamental problem in text data mining is to extract meaningful structure from document streams that arrive continuously over time. E-mail and news articles are two natural examples of such streams, each characterized by topics that appear, grow in intensity for a period of time, and then fade away. The published literature in a particular research field can be seen to exhibit similar phenomena over a much longer time scale. Underlying much of the text mining work in this area is the following intuitive premise-that the appearance of a topic in a document stream is signaled by a "burst of activity," with certain features rising sharply in frequency as the topic emerges. The goal of the present work is to develop a formal approach for modeling such " bursts," in such a way that they can be robustly and efficiently identified, and can provide an organizational framework for analyzing the underlying content. The approach is based on modeling the stream using an infinite-state automaton, in which bursts appear naturally as state transitions;it can be viewed as drawing an analogy with models from queueing theory for bursty network traffic. The resulting algorithms are highly efficient, and yield a nested representation of the set of bursts that imposes a hierarchical structure on the overall stream. Experiments with e-mail and research paper archives suggest that the resulting structures have a natural meaning in terms of the content that gave rise to them.

关键词： data stream algorithms text mining Markov source models

来源：评论

学校读者我要写书评

暂无评论

Near-Optimal Private Approximation Protocols via a Black Box Transformation 11

Near-Optimal Private Approximation Protocols via a Black Box...

引用

43rd ACM Symposium on Theory of Computing

作者： Woodruff, David P. IBM Research-Almaden San Jose CA USA

ISBN: (纸本)9781450306911

We show the following transformation: any two-party protocol for outputting a (1 + epsilon)-approximation to f(x, y) = Sigma(n)(j=1)g(x(j), y(j)) with probability at least 2/3, for any non-negative efficienty computable function g, can be transformed into a two-party private approximation protocol with only a polylogarithmic factor loss in communication, computation, and round complexity. In general it is insufficient to use secure function evaluation or fully homomorphic encryption on a standard, non-private protocol for approximating f. This is because the approximation may reveal information about x and y that does not follow from f(x,y). Applying our transformation and variations of it, we obtain near-optimal private approximation protocols for a wide range of problems in the data stream literature for which previously nothing was known. We give near-optimal private approximation protocols for the l(p)-distance for every p >= 0, for the heavy hitters and importance sampling problems with respect to any l(p)-norm, for the max-dominance and other dominant l(p)-norms, for the distinct summation problem, for entropy, for cascaded frequency moments, for subspace approximation and block sampling, and for measuring independence of datasets. Using a result for data streams, we obtain private approximation protocols with polylogarithmic communication for every non-decreasing and symmetric function g(x(j), y(j)) = h(x(j) - y(j)) with at most quadratic growth. If the original (non-private) protocol is a simultaneous protocol, e.g., a sketching algorithm, then our only cryptographic assumption is efficient symmetric computationally-private information retrieval;otherwise it is fully homomorphic encryption. For all but one of these problems, the original protocol is a sketching algorithm. Our protocols generalize straightforwardly to more than two parties.

关键词： approximation algorithms communication complexity cryptography data stream algorithms

来源：评论

学校读者我要写书评

暂无评论

A Resource-minimalist Flow Size Histogram Estimator

A Resource-minimalist Flow Size Histogram Estimator

引用

8th ACM SIGCOMM Internet Measurement Conference

作者： Ribeiro, Bruno Ye, Tao Towsley, Don Univ Massachusetts Dept Comp Sci Amherst MA 01003 USA

ISBN: (纸本)9781605583341

The histogram of network flow sizes is an important yet difficult metric to estimate in network monitoring. It is important because it characterizes traffic compositions and is a crucial component of anomaly detection methods. It is difficult to estimate because of its high memory and computational requirements. Existing algorithms compute fine grained estimates for each flow size, i.e. 1, 2,... up to the maximum number observed over a finite time interval. Our approach instead relies on the insight that, while many applications require fine grained estimates of small flow sizes, i.e. {1, 2,..., k} with a small k, network operators are often only interested in coarse grained estimates of larger flow sizes. Thus, we propose ail estimator that outputs a binned histogram of size distributions. Our estimator computes this histogram in O(k(3) + log W) operations, where W is the largest flow size of interest to the network operator, while requiring only a few bits of memory per measured flow. This translates into more than 4 fold memory savings and an exponential speedup in the estimator as compared to previous works, greatly increasing the possibility of performing online estimation inside a router.

关键词： Monitoring Systems Sampling Methods data stream algorithms Flow Size Histogram

来源：评论

学校读者我要写书评

暂无评论

Subspace Embeddings for the L1-norm with Applications 11

Subspace Embeddings for the L1-norm with Applications

引用

43rd ACM Symposium on Theory of Computing

作者： Sohler, Christian Woodruff, David P. Tech Univ Dortmund Dept Comp Sci Dortmund Germany

ISBN: (纸本)9781450306911

We show there is a distribution over linear mappings R : l(1)(n) -> l(1)(O(d log d)) such that with arbitrarily large constant probability, for any fixed d-dimensional subspace L, for all x is an element of L we have parallel to x parallel to(1) <= parallel to Rx parallel to(1) = O(d log d)parallel to x parallel to(1). This provides the first analogue of the ubiquitous subspace Johnson-Lindenstrauss embedding for the l(1)-norm. Importantly, the target dimension and distortion are independent of the ambient dimension n. We give several applications of this result. First, we give a faster algorithm for computing well-conditioned bases. Our algorithm is simple, avoiding the linear programming machinery required of previous algorithms. We also give faster algorithms for least absolute deviation regression and l(1)-norm best fit hyperplane problems, as well as the first single pass streaming algorithms with low space for these problems. These results are motivated by practical problems in image analysis, spam detection, and statistics, where the l(1)-norm is used in studies where outliers may be safely and effectively ignored. This is because the l(1)-norm is more robust to outliers than the l(2)-norm.

关键词： data stream algorithms hyperplane fitting regression well-conditioned basis

来源：评论

学校读者我要写书评

暂无评论

Lower Bounds for Randomized Read/Write stream algorithms 07

Lower Bounds for Randomized Read/Write Stream Algorithms

引用

39th Annual ACM Symposium on Theory of Computing

作者： Beame, Paul Jayram, T. S. Rudra, Atri Univ Washington Seattle WA 98195 USA

ISBN: (纸本)9781595936318

Motivated by the capabilities of modern storage architectures, we consider the following generalization of the data stream model where the algorithm has sequential access to multiple streams. Unlike the data stream model, where the stream is read only, in this new model (introduced in [8, 9]) the algorithms can also write onto streams. There is no limit on the size of the streams but the number of passes made on the streams is restricted. On the other hand, the amount of internal memory used by the algorithm is scarce, similar to data stream model. We resolve the main open problem in [7] of proving lower bounds in this model for algorithms that are allowed to have 2-sided error. Previously, such lower bounds were Shown only for deterministic and I-sided error randomized algorithms [9, 7]. We consider the classical set disjointness problem that has proved to be invaluable for deriving lower bounds for many other problems involving data streams and other randomized models of computation. For this problem, we show a near-linear lower bound on the size of the internal memory used by a randomized algorithm with 2-sided error that is allowed to have o(log N/log log N) passes over the streams. This bound is almost optimal since there is a simple algorithm that can solve this problem using logarithmic memory if the number of passes over the streams is allowed to be O(log N). Applications include near-linear lower bounds on the internal memory for well-known problems in the literature: (1) approximately counting the number of distinct elements in the input (F(0));(2) approximating the frequency of the mode of an input sequence (F(infinity)*);(3) computing the join of two relations;and (4) deciding if some node of an XML document matches an XQuery (or XPath) query. Our techniques involve a novel direct-sum type of argument that yields lower bounds for many other problems. Our results asymptotically improve previously known bounds for any problem even in deterministic and I-si

关键词： data stream algorithms communication complexity

来源：评论

学校读者我要写书评

暂无评论

Fast Moment Estimation in data streams in Optimal Space 11

Fast Moment Estimation in Data Streams in Optimal Space

引用

43rd ACM Symposium on Theory of Computing

作者： Kane, Daniel M. Nelson, Jelani Porat, Ely Woodruff, David P. Harvard Univ Dept Math Cambridge MA 02138 USA

ISBN: (纸本)9781450306911

We give a space-optimal streaming algorithm with update time O(log(2)(1/epsilon) log log(1/epsilon)) for approximating the pth frequency moment, 0 < p < 2, of a length-n vector updated in a data stream up to a factor of 1 +/- epsilon. This provides a nearly exponential improvement over the previous space-optimal algorithm of [Kane-Nelson-Woodruff, SODA 2010], which had update time Omega(1/epsilon(2)). When combined with the work of [Harvey-Nelson-Onak, FOCS 2008], we also obtain the first algorithm for entropy estimation in turnstile streams which simultaneously achieves near-optimal space and fast update time.

关键词： data stream algorithms frequency moments

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：