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

Improving table compression with combinatorial optimization

JOURNAL OF THE ACM 2003年第6期50卷 825-851页

作者： Buchsbaum, AL Fowler, GS Giancarlo, R AT&T Labs Res Shannon Lab Florham Pk NJ 07932 USA Univ Palermo Dipartimento Matemat & Applicaz I-90123 Palermo Italy

We study the problem of compressing massive tables within the partition-training paradigm introduced by Buchsbaum et al. [2000], in which a table is partitioned by an off-line training procedure into disjoint intervals of columns, each of which is compressed separately by a standard, on-line compressor like gzip. We provide a new theory that unifies previous experimental observations on partitioning and heuristic observations on column permutation, all of which are used to improve compression rates. Based on this theory, we devise the first on-line training algorithms for table compression, which can be applied to individual files, not just continuously operating sources;and also a new, off-line training algorithm, based on a link to the asymmetric traveling salesman problem, which improves on prior work by rearranging columns prior to partitioning. We demonstrate these results experimentally. On various test files, the on-line algorithms provide 35-55% improvement over gzip with negligible slowdown;the off-line reordering provides up to 20% further improvement over partitioning alone. We also show that a variation of the table compression problem is MAX-SNP hard.

关键词： asymmetric traveling salesman problem dynamic programming experimental algorithmics table compression

来源：评论

学校读者我要写书评

暂无评论

A framework for scalable greedy coloring on distributed-memory parallel computers

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2008年第4期68卷 515-535页

作者： Bozdag, Doruk Gebremedhin, Assefaw H. Manne, Fredrik Boman, Erik G. Catalyurek, Umit V. Ohio State Univ Dept Biomed Informat Columbus OH 43210 USA Ohio State Univ Dept Elect & Comp Engn Columbus OH 43210 USA Old Dominion Univ Dept Comp Sci Norfolk VA 23529 USA Univ Bergen Dept Informat N-5008 Bergen Norway

We present a scalable framework for parallelizing greedy graph coloring algorithms on distributed-memory computers. The framework unifies several existing algorithms and blends a variety of techniques for creating or facilitating concurrency. The latter techniques include exploiting features of the initial data distribution, the use of speculative coloring and randomization, and a BSP-style organization of computation and communication. We experimentally study the performance of several specialized algorithms designed using the framework and implemented using MPI. The experiments are conducted on two different platforms and the test cases include large-size synthetic graphs as well as real graphs drawn from various application areas. Computational results show that implementations that yield good speedup while at the same time using about the same number of colors as a sequential greedy algorithm can be achieved by setting parameters of the framework in accordance with the size and structure of the graph being colored. Our implementation is freely available as part of the Zoltan parallel data management and load-balancing library. (C) 2007 Elsevier Inc. All rights reserved.

关键词： graph coloring parallel algorithms distributed-memory computers scientific computing experimental algorithmics

来源：评论

学校读者我要写书评

暂无评论

Milestones on the Quantum Utility Highway: Quantum Annealing Case Study

引用

ACM TRANSACTIONS ON QUANTUM COMPUTING 2024年第1期5卷 1-30页

作者： Mcgeoch, Catherine C. Farre, Pau ID Wave Syst Inc 3033 Beta Ave Burnaby BC V5G 4K4 Canada

We introduce quantum utility, a new approach to evaluating quantum performance that aims to capture the user experience by considering the overhead costs associated with a quantum computation. A demonstration of quantum utility by the quantum processing unit (QPU) shows that the QPU can outperform classical solvers at some tasks of interest to practitioners, when considering the costs of computational overheads. A milestone is a test of quantum utility that is restricted to a specific subset of overhead costs and input types. We illustrate this approach with a benchmark study of a D-Wave annealing-based QPU versus seven classical solvers for a variety of problems in heuristic optimization. We consider overhead costs that arise in standalone use of the D-Wave QPU (as opposed to a hybrid computation). We define three early milestones on the path to broad-scale quantum utility. Milestone 0 is the purely quantum computation with no overhead costs and is demonstrated implicitly by positive results on other milestones. We evaluate the performance of a D-Wave Advantage QPU with respect to milestones 1 and 2: For milestone 1, the QPU outperformed all classical solvers in 99% of our tests. For milestone 2, the QPU outperformed all classical solvers in 19% of our tests, and the scenarios in which the QPU found success correspond to cases where classical solvers most frequently failed. This approach of isolating subsets of overheads for separate analysis reveals distinct mechanisms in quantum versus classical performance, which explain the observed differences in patterns of success and failure. We present evidence-based arguments that these distinctions bode well for annealing quantum processors to support demonstrations of quantum utility on ever-expanding classes of inputs and with more challenging milestones in the very near future.

关键词： Quantum annealing quantum benchmarking quantum performance analysis quantum utility D-Wave heterogeneous computational benchmarking experimental algorithmics

来源：评论

学校读者我要写书评

暂无评论

The JAMES II framework for modeling and simulation

The JAMES II framework for modeling and simulation

引用

International Workshop on High Performance Computational Systems Biology (HiBi 2009)

作者： Himmelspach, Jan Uhrmacher, Adelinde Univ Rostock Inst Comp Sci Rostock Germany

ISBN: (纸本)9780769538099

JAMES is a general and open framework based on the "Plng'n simulate" concept, which enables developers to integrate their Modeling and simulation methodological ideas into.. and to create their applications upon an existing framework. This concept together with currently more than 400 plug-ins, and an explicit representation and storage of experiments ease developing modeling and simulation methods and contribute to a systematic experimental evaluation of methods. Modelers benefit from the flexibility that the framework provides with respect to modeling, simulation, and analysis methods, supporting effective and efficient simulation studies, and the well tested methods add to lie credibility of the results achieved.

关键词： experimental algorithmics Performance Evaluation Framework Modeling Simulation Plug-Ins Distributed Simulation

来源：评论

学校读者我要写书评

暂无评论

Performance Issues in Evaluating Models and Designing Simulation Algorithms

Performance Issues in Evaluating Models and Designing Simula...

引用

International Workshop on High Performance Computational Systems Biology (HiBi 2009)

作者： Ewald, Roland Himmelspach, Jan Jeschke, Matthias Leye, Stefan Uhrmacher, Adelinde M. Univ Rostock Inst Comp Sci Rostock Germany

ISBN: (纸本)9780769538099

The increase and diversity of simulation methods bears witness of the need for more efficient discrete event simulations in computational biology - but how efficient are those methods. and how to ensure all efficient simulation for a concrete model? As the performance of simulation methods depends oil the model, the simulator. and the infrastructure, general answers to those questions are likely to remain illusive;they have to be sought individually and experimentally instead. This requires configurable implementations of many algorithms, means to define and conduct meaningful experiments on them, and mechanisms for storing and analyzing observed performance data. In this paper, we first overview basic approaches for improving simulation performance and illustrate the challenges when comparing different methods. We then argue that providing all the aforementioned components in a single tool, in our case the open source modeling and simulation framework JAMES II, reveals many synergies in effectively pursuing both questions. This is exemplified by presenting results of recent studies and introducing a new component to swiftly evaluate simulator code changes against previous experimental data.

关键词： Stochastic Simulation experimental algorithmics Performance Evaluation Algorithm Selection Distributed Simulaton SSA Next Sub-volume Method Machine Learning

来源：评论

学校读者我要写书评

暂无评论

Benchmarking D-Wave Quantum Annealing Systems: Some Challenges 12

Benchmarking D-Wave Quantum Annealing Systems: Some Challeng...

引用

Conference on Electro-Optical and Infrared Systems - Technology and Applications XII and Quantum Information Science and Technology

作者： McGeoch, Catherine C. D Wave Syst Inc Burnaby BC Canada Amherst Coll Amherst MA 01002 USA

This short paper presents an overview of the theoretical and technological underpinnings of D-Wave quantum annealing systems and surveys some methodological challenges that arise when benchmarking these highly unusual... 详细信息

ISBN: (纸本)9781628418583

关键词： Adiabatic quantum computing quantum annealing D-Wave benchmarking experimental algorithmics

来源：评论

学校读者我要写书评

暂无评论

Clique counting in mapreduce: Algorithms and experiments

引用

ACM Journal of experimental algorithmics 2015年第1期20卷 1–20页

作者： Finocchi, Irene Finocchi, Marco Fusco, Emanuele G. Computer Science Department Sapienza University of Rome Via Salaria 113 Rome 00198 Italy Department of Computer Control and Management Engineering Antonio Ruberti Sapienza University of Rome Via Ariosto 25 Rome 00185 Italy

We tackle the problem of counting the number qk of k-cliques in large-scale graphs, for any constant k ≥ 3. Clique counting is essential in a variety of applications, including social network analysis. Our algorithms... 详细信息

We tackle the problem of counting the number q_k of k-cliques in large-scale graphs, for any constant k ≥ 3. Clique counting is essential in a variety of applications, including social network analysis. Our algorithms make it possible to compute q_k for several real-world graphs and shed light on its growth rate as a function of k. Even for small values of k, the number q_k of k-cliques can be in the order of tens or hundreds of trillions. As k increases, different graph instances show different behaviors: while on some graphs q_k+1 < qk, on other benchmarks q_k+1 蠑 q_k, up to two orders of magnitude in our observations. Graphs with steep clique growth rates represent particularly tough instances in practice. Due to the computationally intensive nature of the clique counting problem, we settle for parallel solutions in theMapReduce framework, which has become in the last few years a de facto standard for batch processing of massive datasets. We give both theoretical and experimental contributions. On the theory side, we design the first exact scalable algorithm for counting (and listing) k-cliques in MapReduce. Our algorithm uses O(m3/2) total space and O(mk/2) work, where m is the number of graph edges. This matches the best-known bounds for triangle listing when k = 3 and is work optimal in the worst case for any k, while keeping the communication cost independent of *** also design sampling-based estimators that can dramatically reduce the running time and space requirements of the exact approach, while providing very accurate solutions with high probability. We then assess the effectiveness of different clique counting approaches through an extensive experimental analysis over the Amazon EC2 platform, considering both our algorithms and their state-of-the-art competitors. The experimental results clearly highlight the algorithm of choice in different scenarios and prove our exact approach to be the mos

关键词： Clique listing MapReduce experimental algorithmics graph algorithms parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

Geometric Minimum Spanning Trees with GEOFILTERKRUSKAL

Geometric Minimum Spanning Trees with GEOFILTERKRUSKAL

引用

9th International Symposium on experimental Algorithms

作者： Chatterjee, Samidh Connor, Michael Kumar, Piyush Florida State Univ Dept Comp Sci Tallahassee FL 32306 USA

ISBN: (纸本)9783642131929

Let P be a set of points in R-d. We propose GEOFILTERKRUSKAL, an algorithm that computes the minimum spanning tree of P using well separated pair decomposition in combination with a simple modification of Kruskal's algorithm. When P is sampled from uniform random distribution, we show that our algorithm takes one parallel sort plus a linear number of additional steps, with high probability, to compute the minimum spanning tree. Experiments show that our algorithm works better in practice for most data distributions compared to the current state of the art [31]. Our algorithm is easy to parallelize and to our knowledge, is currently the best practical algorithm on multi-core machines for d > 2.

关键词： Computational Geometry experimental algorithmics Minimum spanning tree Well separated pair decomposition Morton ordering multi-core

来源：评论

学校读者我要写书评

暂无评论

Running Experiments with Confidence and Sanity 1

引用

13th International Conference on Similarity Search and Applications (SISAP)

作者： Aumuller, Martin Ceccarello, Matteo IT Univ Copenhagen Copenhagen Denmark Free Univ Bozen Bolzano Italy

ISBN: (数字)9783030609368

ISBN: (纸本)9783030609368

Analyzing data from large experimental suites is a daily task for anyone doing experimental algorithmics. In this paper we report on several approaches we tried for this seemingly mundane task in a similarity search setting, reflecting on the challenges it poses. We conclude by proposing a workflow, which can be implemented using several tools, that allows to analyze experimental data with confidence.

关键词： experimental algorithmics experimental analysis

来源：评论

学校读者我要写书评

暂无评论

The Price of Resiliency: a Case Study on Sorting with Memory Faults

引用

14th Annual European Symposium on Algorithms (ESA 2006)

作者： Ferraro-Petrillo, Umberto Finocchi, Irene Italiano, Giuseppe F. Univ Roma La Sapienza Dipartimento Stat Probabilita & Stat Applicate I-00185 Rome Italy Univ Roma La Sapienza Dipartimento Informat I-00198 Rome Italy Univ Roma Tor Vergata Dipartimento Informat Sistemi & Prod I-00133 Rome Italy

ISBN: (纸本)3540388753

We address the problem of sorting in the presence of faults that may arbitrarily corrupt memory locations, and investigate the impact of memory faults both on the correctness and on the running times of mergesort-based algorithms. To achieve this goal, we develop a software testbed that simulates different fault injection strategies, and perform a thorough experimental study using a combination of several fault parameters. Our experiments give evidence that simple-minded approaches to this problem are largely impractical, while the design of more sophisticated resilient algorithms seems really worth the effort. Another contribution of our computational study is a carefully engineered implementation of a resilient sorting algorithm, which appears robust to different memory fault patterns.

关键词： Sorting Memory faults Memory models Fault injection Computing with unreliable information experimental algorithmics

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：