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

Interactive Exploration and Analysis of Large-Scale Simulations Using Topology-Based Data Segmentation

IEEE TRANSACTIONS ON VISUALIZATION AND COMPUTER GRAPHICS 2011年第9期17卷 1307-1324页

作者： Bremer, Peer-Timo Weber, Gunther H. Tierny, Julien Pascucci, Valerio Day, Marcus S. Bell, John B. Lawrence Livermore Natl Lab Ctr Appl Sci Comp CASC Livermore CA 94550 USA Univ Utah Sci Comp & Imaging SCI Inst Salt Lake City UT 84112 USA Univ Calif Berkeley Lawrence Berkeley Lab Visualizat Grp Computat Res Div CRD Berkeley CA 94720 USA Univ Calif Davis Inst Data Anal & Visualizat Dept Comp Sci Davis CA 95616 USA French Natl Ctr Sci Res CNRS Paris France Telecom ParisTech Paris France Univ Utah Sci Comp & Imaging Inst Salt Lake City UT 84112 USA Univ Calif Berkeley Lawrence Berkeley Lab Ctr Computat Sci & Engn CCSE Computat Res Div CRD Berkeley CA 94720 USA

Large-scale simulations are increasingly being used to study complex scientific and engineering phenomena. As a result, advanced visualization and data analysis are also becoming an integral part of the scientific process. Often, a key step in extracting insight from these large simulations involves the definition, extraction, and evaluation of features in the space and time coordinates of the solution. However, in many applications, these features involve a range of parameters and decisions that will affect the quality and direction of the analysis. Examples include particular level sets of a specific scalar field, or local inequalities between derived quantities. A critical step in the analysis is to understand how these arbitrary parameters/decisions impact the statistical properties of the features, since such a characterization will help to evaluate the conclusions of the analysis as a whole. We present a new topological framework that in a single-pass extracts and encodes entire families of possible features definitions as well as their statistical properties. For each time step we construct a hierarchical merge tree a highly compact, yet flexible feature representation. While this data structure is more than two orders of magnitude smaller than the raw simulation data it allows us to extract a set of features for any given parameter selection in a postprocessing step. Furthermore, we augment the trees with additional attributes making it possible to gather a large number of useful global, local, as well as conditional statistic that would otherwise be extremely difficult to compile. We also use this representation to create tracking graphs that describe the temporal evolution of the features over time. Our system provides a linked-view interface to explore the time-evolution of the graph interactively alongside the segmentation, thus making it possible to perform extensive data analysis in a very efficient manner. We demonstrate our framework by extracting an

关键词： Topology Morse theory merge trees segmentation streaming algorithms combustion

来源：评论

学校读者我要写书评

暂无评论

Introduction to the special issue on foundations of adaptive networked societies of tiny artefacts

引用

COMPUTER SCIENCE REVIEW 2011年第1期5卷 4-6页

作者： Chatzigiannakis, Ioannis Spirakis, Paul RACTI Patras Greece

This special issue of Computer Science Review features seven papers on foundations of adaptive networked societies of tiny artefacts. The introduction describes the motivation for the special issue and briefly overvie... 详细信息

关键词： Wireless sensor networks Mobile networks Distributed computing Security Computation models Self-stabilization Game theory streaming algorithms Data aggregation Algorithm engineering Experimentation Ubiquitous applications

来源：评论

学校读者我要写书评

暂无评论

K-Median Clustering, Model-Based Compressive Sensing, and Sparse Recovery for Earth Mover Distance 11

K-Median Clustering, Model-Based Compressive Sensing, and Sp...

引用

43rd ACM Symposium on Theory of Computing

作者： Indyk, Piotr Price, Eric MIT CSAIL Cambridge MA 02139 USA

ISBN: (纸本)9781450306911

We initiate the study of sparse recovery problems under the Earth-Mover Distance (EMD). Specifically, we design a distribution over m x n matrices A such that for any x, given Ax, we can recover a k-sparse approximation to x under the EMD distance. One construction yields m = O(k log(n/k)) and a 1 + epsilon approximation factor, which matches the best achievable bound for other error measures, such as the l(1) norm. Our algorithms are obtained by exploiting novel connections to other problems and areas, such as streaming algorithms for k-median clustering and model-based compressive sensing. We also provide novel algorithms and results for the latter problems.

关键词： Compressive sensing Earth Mover Distance streaming algorithms Clustering

来源：评论

学校读者我要写书评

暂无评论

Finding Heavy Distinct Hitters in Data Streams 11

Finding Heavy Distinct Hitters in Data Streams

引用

23rd Annual Symposium on Parallelism in algorithms and Architectures

作者： Locher, Thomas IBM Res Zurich Zurich Switzerland

ISBN: (纸本)9781450307437

A simple indicator for an anomaly in a network is a rapid increase in the total number of distinct network connections. While it is fairly easy to maintain an accurate estimate of the current total number of distinct connections using streaming algorithms that exhibit both a low space and computational complexity, identifying the network entities that are involved in the largest number of distinct connections efficiently is considerably harder. In this paper, we study the problem of finding all entities whose number of distinct (outgoing or incoming) network connections is at least a specific fraction of the total number of distinct connections. These entities are referred to as heavy distinct hitters. Since this problem is hard in general, we focus on randomized approximation techniques and propose a sampling-based and a sketch-based streaming algorithm. Both algorithms output a list of the potential heavy distinct hitters including the estimated counts of the corresponding number of distinct connections. We prove that, depending on the required level of accuracy of the output list, the space complexities of the presented algorithms are asymptotically optimal up to small logarithmic factors. Additionally, the algorithms are evaluated and compared using real network data in order to determine their usefulness in practice.

关键词： Network Monitoring Anomaly Detection streaming algorithms Heavy Distinct Hitter Space Complexity

来源：评论

学校读者我要写书评

暂无评论

Estimating PageRank on Graph Streams

引用

JOURNAL OF THE ACM 2011年第3期58卷 13-13页

作者： Das Sarma, Atish Gollapudi, Sreenivas Panigrahy, Rina Georgia Inst Technol Atlanta GA 30332 USA Microsoft Res Mountain View CA 94043 USA

This article focuses on computations on large graphs (e.g., the web-graph) where the edges of the graph are presented as a stream. The objective in the streaming model is to use small amount of memory (preferably sub-linear in the number of nodes n) and a smaller number of passes. In the streaming model, we show how to perform several graph computations including estimating the probability distribution after a random walk of length l, the mixing time M, and other related quantities such as the conductance of the graph. By applying our algorithm for computing probability distribution on the web-graph, we can estimate the PageRank p of any node up to an additive error of root epsilon p+ epsilon in (O) over tilde(root M/alpha) passes and (O) over tilde (min(n alpha + 1/epsilon root M/alpha + (1/epsilon)M alpha, alpha n root M alpha + (1/epsilon)root M/alpha)) space, for any alpha is an element of (0, 1]. Specifically, for epsilon = M/n, alpha = M-1/2, we can compute the approximate PageRank values in (O) over tilde (nM(-1/4)) space and (O) over tilde (M-3/4) passes. In comparison, a standard implementation of the PageRank algorithm will take O(n) space and O(M) passes. We also give an approach to approximate the PageRank values in just (O) over tilde (1) passes although this requires (O) over tilde (nM) space.

关键词： algorithms Theory algorithms graph conductance mixing time PageRank random walk streaming algorithms

来源：评论

学校读者我要写书评

暂无评论

Small Space Representations for Metric Min-sum k-Clustering and Their Applications

引用

THEORY OF COMPUTING SYSTEMS 2010年第3期46卷 416-442页

作者： Czumaj, Artur Sohler, Christian Univ Warwick Dept Comp Sci Coventry CV4 7AL W Midlands England Univ Warwick Ctr Discrete Math & Applicat Coventry CV4 7AL W Midlands England TU Dortmund Dept Comp Sci D-44221 Dortmund Germany

The min-sum k-clustering problem is to partition a metric space ( P, d) into k clusters C-1,..., C-k subset of P such that Sigma(k)(i=1) Sigma(p,q is an element of Ci) d(p, q) is minimized. We show the first efficient construction of a coreset for this problem. Our coreset construction is based on a new adaptive sampling algorithm. With our construction of coresets we obtain two main algorithmic results. The first result is a sublinear-time ( 4 + epsilon)-approximation algorithm for the minsum k-clustering problem in metric spaces. The running time of this algorithm is O( n) for any constant k and epsilon, and it is o( n2) for all k = o( log n/ log log n). Since the full description size of the input is Theta(n(2)), this is sublinear in the input size. The fastest previously known o( log n)-factor approximation algorithm for k > 2 achieved a running time of Omega(nk), and no non-trivial o(n(2))-time algorithm was known before. Our second result is the first pass-efficient data streaming algorithm for min-sum k-clustering in the distance oracle model, i.e., an algorithm that uses poly( log n, k) space and makes 2 passes over the input point set, which arrives in form of a data stream in arbitrary order. It computes an implicit representation of a clustering of ( P, d) with cost at most a constant factor larger than that of an optimal partition. Using one further pass, we can assign each point to its corresponding cluster. To develop the coresets, we introduce the concept of alpha-preserving metric embeddings. Such an embedding satisfies properties that the distance between any pair of points does not decrease and the cost of an optimal solution for the considered problem on input ( P, d')is within a constant factor of the optimal solution on input ( P, d). In other words, the goal is to find a metric embedding into a ( structurally simpler) metric space that approximates the original metric up to a factor of a with respect to a given problem. We believe that this con

关键词： Sublinear-time algorithms Sublinear-space algorithms Clustering Min-sum k-clustering Balanced k-median streaming algorithms Coresets

来源：评论

学校读者我要写书评

暂无评论

streaming clustering algorithms for foreground detection in color videos

Streaming clustering algorithms for foreground detection in ...

引用

2nd International Conference on Computer Graphics Theory and Applications/2nd International Conference on Computer Vision Theory and Applications

作者： Duric, Zoran Lawson, Wallace E. Richards, Dana George Mason Univ Dept Comp Sci Fairfax VA 22030 USA

ISBN: (纸本)9789728865740

A new method is given for locating foreground objects in color *** is an essential task in many applications such as surveillance. The algorithm uses clustering techniques to permit flexibility and adaptability in the description of the background. The approach is an example of the streaming data paradigm of algorithms design, which only permits limited information to be retained about previous video frames. Experimental results show that it is an effective and robust technique.

关键词： streaming algorithms clustering backgroundmaintenance video surveillance

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Space-Optimal Heavy Hitters with Strong Error Bounds

引用

ACM TRANSACTIONS ON DATABASE SYSTEMS 2010年第4期35卷 26:1-26:28页

作者： Berinde, Radu Indyk, Piotr Cormode, Graham Strauss, Martin J. MIT Cambridge MA 02139 USA Univ Michigan Ann Arbor MI 48109 USA

The problem of finding heavy hitters and approximating the frequencies of items is at the heart of many problems in data stream analysis. It has been observed that several proposed solutions to this problem can outperform their worst-case guarantees on real data. This leads to the question of whether some stronger bounds can be guaranteed. We answer this in the positive by showing that a class of counter-based algorithms (including the popular and very space-efficient FREQUENT and SPACESAVING algorithms) provides much stronger approximation guarantees than previously known. Specifically, we show that errors in the approximation of individual elements do not depend on the frequencies of the most frequent elements, but only on the frequency of the remaining tail. This shows that counter-based methods are the most space-efficient (in fact, space-optimal) algorithms having this strong error bound. This tail guarantee allows these algorithms to solve the sparse recovery problem. Here, the goal is to recover a faithful representation of the vector of frequencies, f. We prove that using space O(k), the algorithms construct an approximation f* to the frequency vector f so that the L-1 error parallel to f - f*parallel to(1) is close to the best possible error min f' parallel to f' - f parallel to(1), where f' ranges over all vectors with at most k non-zero entries. This improves the previously best known space bound of about O(k log n) for streams without element deletions (where n is the size of the domain from which stream elements are drawn). Other consequences of the tail guarantees are results for skewed (Zipfian) data, and guarantees for accuracy of merging multiple summarized streams.

关键词： algorithms Theory Frequency estimation heavy hitters streaming algorithms

来源：评论

学校读者我要写书评

暂无评论

Space-Optimal Heavy Hitters with Strong Error Bounds 09

Space-Optimal Heavy Hitters with Strong Error Bounds

引用

28th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS)

作者： Berinde, Radu Indyk, Piotr Cormode, Graham Strauss, Martin J. MIT Cambridge MA 02139 USA Univ Michigan Ann Arbor MI 48109 USA

ISBN: (纸本)9781605585536

关键词： algorithms Theory Frequency estimation heavy hitters streaming algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：