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

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

来源：评论

学校读者我要写书评

暂无评论

From approximate balls to approximate ellipses

引用

JOURNAL OF GLOBAL OPTIMIZATION 2013年第1期56卷 27-42页

作者： Mukhopadhyay, Asish Greene, Eugene Sarker, Animesh Switzer, Tom Univ Windsor Windsor ON N9B 3P4 Canada

A ball spans a set of n points when none of the points lie outside it. In Zarrabi-Zadeh and Chan (Proceedings of the 18th Canadian conference on computational geometry (CCCG'06), pp 139-142, 2006) proposed an algorithm to compute an approximate spanning ball in the streaming model of computation, and showed that the radius of the approximate ball is within 3/2 of the minimum. Spurred by this, in this paper we consider the 2-dimensional extension of this result: computation of spanning ellipses. The ball algorithm is simple to the point of being trivial, but the extension of the algorithm to ellipses is non-trivial. Surprisingly, the area of the approximate ellipse computed by this approach is not within a constant factor of the minimum and we provide an elegant proof of this. We have implemented this algorithm, and experiments with a variety of inputs, except for a very pathological one, show that it can nevertheless serve as a good heuristic for computing an approximate ellipse.

关键词： Computational geometry streaming algorithms Approximation schemes Approximate ellipses

来源：评论

学校读者我要写书评

暂无评论

Small Vertex Cover Helps in Fixed-Parameter Tractability of Graph Deletion Problems over Data Streams

引用

THEORY OF COMPUTING SYSTEMS 2023年第6期67卷 1241-1267页

作者： Bishnu, Arijit Ghosh, Arijit Kolay, Sudeshna Mishra, Gopinath Saurabh, Saket Indian Stat Inst Kolkata India Indian Inst Technol Kharagpur Kharagpur India Univ Warwick Coventry England HBNI Inst Math Sci Chennai India

In the study of parameterized streaming complexity on graph problems, the main goal is to design streaming algorithms for parameterized problems such that O(f (k) log(O(1)) n) space is enough, where f is an arbitrary computable function depending only on the parameter k. However, in the past few years very few positive results have been established. Most of the graph problems that do have streaming algorithms of the above nature are ones where localized checking is required, like Vertex Cover or Maximum Matching parameterized by the size k of the solution we are seeking. Chitnis et al. (SODA'16) have shown that many important parameterized problems that form the backbone of traditional parameterized complexity are known to require Omega (n) bits of storage for any streaming algorithm;e.g. Feedback Vertex Set, Even Cycle Transversal, Odd Cycle Transversal, Triangle Deletion or the more general F-Subgraph Deletion when parameterized by solution size k. Our contribution lies in overcoming the obstacles to efficient parameterized streaming algorithms in graph deletion problems by utilizing the power of parameterization. We focus on the vertex cover size K as the parameter for the parameterized graph deletion problems we consider. In this work, we consider the four most well-studied streaming models: the Ea, Dea, Va (vertex arrival) and Al (adjacency list) models. Surprisingly, the consideration of vertex cover size K in the different models leads to a classification of positive and negative results for problems like F-Subgraph Deletion and F-Minor Deletion.

关键词： FPT streaming algorithms Vertex cover Subgraph deletion problems Minor deletion problems

来源：评论

学校读者我要写书评

暂无评论

Approximation algorithms for wavelet transform coding of data stream.

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2008年第2期54卷 811-830页

作者： Guha, Sudipto Harb, Boulos Univ Penn Dept Comp Informat Sci Philadelphia PA 19104 USA Google Inc New York NY 10011 USA

This paper addresses the problem of finding a B-term wavelet representation of a given discrete function f is an element of R-n whose distance from f is minimized. The problem is well understood when we seek to minimize the Euclidean distance between f and its representation. The first-known algorithms for finding provably approximate representations minimizing general f, distances (including l(infinity)) under a wide variety of compactly supported wavelet bases are presented in this paper. For the Haar basis, a polynomial time approximation scheme is demonstrated. These algorithms are applicable in the one-pass sublinear-space data stream model of computation. They generalize naturally to multiple dimensions and weighted norms. A universal representation that provides a provable approximation guarantee under all p-norms simultaneously;and the first approximation algorithms for bit-budget versions of the problem, known as adaptive quantization, are also presented. Further, it is shown that the algorithms presented here can be used to select a basis from a tree-structured dictionary of bases and find a B-term representation of the given function that provably approximates its best dictionary-basis representation.

关键词： adaptive quantization best basis selection compactly supported wavelets nonlinear approximation sparse representation streaming algorithms transform coding universal representation

来源：评论

学校读者我要写书评

暂无评论

GRAPHZEPPELIN: How to Find Connected Components (Even When Graphs Are Dense, Dynamic, and Massive)

引用

ACM TRANSACTIONS ON DATABASE SYSTEMS 2024年第3期49卷 1-31页

作者： Tench, David West, Evan Zhang, Victor Bender, Michael A. Chowdhury, Abiyaz Delayo, Daniel Dellas, J. Ahmed Farach-colton, Martin Seip, Tyler Zhang, Kenny Rutgers State Univ 57 US Highway 1 New Brunswick NJ 08901 USA SUNY Stony Brook 100 Nicolls Rd Stony Brook NY 11794 USA MongoDB 1633 Broad Way New York NY 10019 USA

Finding the connected components of a graph is a fundamental problem with uses throughout computer science and engineering. The task of computing connected components becomes more difficult when graphs are very large, or when they are dynamic, meaning the edge set changes over time subject to a stream of edge insertions and deletions. A natural approach to computing the connected components problem on a large, dynamic graph stream is to buy enough RAM to store the entire graph. However, the requirement that the graph fit in RAM is an inherent limitation of this approach and is prohibitive for very large graphs. Thus, there is an unmet need for systems that can process dense dynamic graphs, especially when those graphs are larger than available RAM. We present a new high-performance streaming graph-processing system for computing the connected components of a graph. This system, which we call GRAPHZEPPELIN, uses new linear sketching data structures (CUBESKETCH) to solve the streaming connected components problem and as a result requires space asymptotically smaller than the space required for a lossless representation of the graph. GRAPHZEPPELIN is optimized for massive dense graphs: GRAPHZEPPELIN can process millions of edge updates (both insertions and deletions) per second, even when the underlying graph is far too large to fit in available RAM. As a result GRAPHZEPPELIN vastly increases the scale of graphs that can be processed.

关键词： Linear sketching streaming algorithms external memory

来源：评论

学校读者我要写书评

暂无评论

Derandomization for Sliding Window algorithms with Strict Correctness*

引用

THEORY OF COMPUTING SYSTEMS 2021年第3期65卷 444-461页

作者： Ganardi, Moses Hucke, Danny Lohrey, Markus Univ Siegen Holderlinstr 3 D-57076 Siegen Germany

In the sliding window streaming model the goal is to compute an output value that only depends on the lastnsymbols from the data stream. Thereby, only space sublinear in the window sizenshould be used. Quite often randomization is used in order to achieve this goal. In the literature, one finds two different correctness criteria for randomized sliding window algorithms: (i) one can require that for every data stream and every time instantt, the algorithm computes a correct output value with high probability, or (ii) one can require that for every data stream the probability that the algorithm computes at every time instant a correct output value is high. Condition (ii) is stronger than (i) and is called "strict correctness" in this paper. The main result of this paper states that every strictly correct randomized sliding window algorithm can be derandomized without increasing the worst-case space consumption.

关键词： streaming algorithms Sliding window algorithms Randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

Sketching Approximability of All Finite CSPs

引用

JOURNAL OF THE ACM 2024年第2期71卷 1-74页

作者： Chou, Chi-Ning Golovnev, Alexander Sudan, Madhu Velusamy, Santhoshini Harvard Univ Sch Engn & Appl Sci Cambridge MA 02138 USA Georgetown Univ Dept Comp Sci Washington DC USA Toyota Technol Inst Chicago IL USA

A constraint satisfaction problem (CSP), Max-CSP(F), is specified by a finite set of constraints F subset of {[q](k) -> {0, 1}} for positive integers q and k. An instance of the problem on n variables is given bym applications of constraints from F to subsequences of the n variables, and the goal is to find an assignment to the variables that satisfies the maximum number of constraints. In the (gamma , beta)-approximation version of the problem for parameters 0 <= beta < gamma <= 1, the goal is to distinguish instances where at least. fraction of the constraints can be satisfied from instances where at most beta fraction of the constraints can be satisfied. In this work, we consider the approximability of this problem in the context of sketching algorithms and give a dichotomy result. Specifically, for every family F and every beta < gamma, we show that either a linear sketching algorithm solves the problem in polylogarithmic space or the problem is not solvable by any sketching algorithm in o(root n) space. In particular, we give non-trivial approximation algorithms using polylogarithmic space for infinitely many constraint satisfaction problems. We also extend previously known lower bounds for general streaming algorithms to a wide variety of problems, and in particular the case of q = k = 2, where we get a dichotomy, and the case when the satisfying assignments of the constraints of F support a distribution on [q](k) with uniform marginals. Prior to this work, other than sporadic examples, the only systematic classes of CSPs that were analyzed considered the setting of Boolean variables q = 2, binary constraints k = 2, and singleton families vertical bar|F vertical bar| = 1 and only considered the setting where constraints are placed on literals rather than variables. Our positive results show wide applicability of bias-based algorithms used previously by [47] and [41], which we extend to include richer norm estimation algorithms, by giving a systematic way to di

关键词： streaming algorithms communication lower bound inapproximability constraint satisfaction problem

来源：评论

学校读者我要写书评

暂无评论

Triangle Counting in Dynamic Graph Streams

引用

ALGORITHMICA 2016年第1期76卷 259-278页

作者： Bulteau, Laurent Froese, Vincent Kutzkov, Konstantin Pagh, Rasmus Tech Univ Berlin Berlin Germany NEC Labs Europe Heidelberg Germany IT Univ Copenhagen Copenhagen Denmark Univ Lyon 1 Inria LBBE Lyon France

Estimating the number of triangles in graph streams using a limited amount of memory has become a popular topic in the last decade. Different variations of the problem have been studied, depending on whether the graph edges are provided in an arbitrary order or as incidence lists. However, with a few exceptions, the algorithms have considered insert-only streams. We present a new algorithm estimating the number of triangles in dynamic graph streams where edges can be both inserted and deleted. We show that our algorithm achieves better time and space complexity than previous solutions for various graph classes, for example sparse graphs with a relatively small number of triangles. Also, for graphs with constant transitivity coefficient, a common situation in real graphs, this is the first algorithm achieving constant processing time per edge. The result is achieved by a novel approach combining sampling of vertex triples and sparsification of the input graph. In the course of the analysis of the algorithm we present a lower bound on the number of pairwise independent 2-paths in general graphs which might be of independent interest. At the end of the paper we discuss lower bounds on the space complexity of triangle counting algorithms that make no assumptions on the structure of the graph.

关键词： Randomized approximation algorithms streaming algorithms Triangle counting

来源：评论

学校读者我要写书评

暂无评论

JACC-FPGA: A hardware accelerator for Jaccard similarity estimation using FPGAs in the cloud

引用

FUTURE GENERATION COMPUTER SYSTEMS-THE INTERNATIONAL JOURNAL OF ESCIENCE 2023年 138卷 26-42页

作者： Soto, Javier E. Hernandez, Cecilia Figueroa, Miguel Univ Concepcion Elect Engn Dept Concepcion Chile Univ Concepcion Comp Sci Dept Concepcion Chile Ctr Biotechnol & Bioengn CeBiB Santiago Chile

Genomic similarity is a key metric in genomics, used in important tasks such as genome clustering and metagenomic profiling. One commonly-used approach is to treat each genome as a set of k-mers and to compute the Jaccard coefficient between each genome pair. However, computing the Jaccard coefficient between genomes in a large dataset is a computationally-challenging task. In this paper, we present an algorithm and accelerator architecture that uses an FPGA-as-a-service paradigm to compute the Jaccard similarity between pairs of genomes in large datasets using sketches and hardware acceleration in the cloud. The algorithm can compute the similarity between all genome pairs in the dataset, or it can use a selection criterion to reduce the amount of computation when only genome pairs with a Jaccard coefficient above a user-supplied threshold are of interest. After building the sketches, our heterogeneous accelerator can compute more than 96 million Jaccard coefficients per second running on an AWS EC2 f1.2xlarge instance with a Xilinx XCVU9P FPGA, which is 58 times faster than a state-of-the art software implementation that exploits SIMD instructions and thread-level parallelism on a compute-optimized EC2 c5.9xlarge instance with 36 hardware threads. The accelerator also computes similarities 27 times faster than a straightforward GPU-accelerated implementation of the Jaccard coefficient using sketches, and 4 times faster than an optimized GPU implementation of our algorithm, both running on an EC2 g5.4xlarge instance tailored with an NVIDIA A10G GPU. Furthermore, using a Jaccard coefficient threshold of 0.8 reduces the execution time of similarity computation to approximately one third in the hardware-accelerated and parallel software implementations, compared to computing the complete similarity matrix.(C) 2022 Elsevier B.V. All rights reserved.

关键词： Hardware acceleration Cloud computing Field-programmable gate arrays streaming algorithms Sketches Genomics

来源：评论

学校读者我要写书评

暂无评论

An improved data stream algorithm for clustering

引用

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 2015年第9期48卷 635-645页

作者： Kim, Sang-Sub Ahn, Hee-Kap

In the k-center problem for streaming points in d-dimensional metric space, input points are given in a data stream and the goal is to find the k smallest congruent balls whose union covers all input points by examining them. In the single-pass streaming model, input points are allowed to be examined only once and the amount of space that can be used to store relative information is limited. In this paper, we present a single-pass, (1.8 + epsilon)-factor, 0 (d/epsilon)-space data stream algorithm for the Euclidean 2-center problem for any d >= 1. This is the first result with an approximation factor below 2 using O (d/epsilon) space for any d. Our algorithm naturally extends to the Euclidean k-center problem with k > 2. We present a single-pass (1.8 + epsilon)-factor data stream algorithm for the Euclidean k-center problem for any d > 1, which uses O (2(k)(k + 3)!d/epsilon) space and O (2k(k + 2)!d/epsilon) update time. (C) 2015 Elsevier B.V. All rights reserved.

关键词： Euclidean k-clustering Euclidean k-center streaming algorithms Computational geometry

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：