The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
Both explicit usable and implicit transparent parallelism is nothing really new in processor technology but has been restricted to high-end computer systems accessible to only a few developers. In recent years, however, parallelism on all levels has found its way into even the cheapest desktop and notebook system and thus every algorithm being developed today should reflect this change to optimally...
I present the cache-oblivious streaming B-tree, a high performance alternative to the traditional B-tree. Modern databases and file systems are based on B-trees. As a result, they can exhibit performance cliffs and unpredictable run times. Replacing B-trees with cache-oblivious streaming B-trees can remove some of these performance deficiencies. I explain some of the technical issues that we...
In this paper, the performances of the quasi-Newton BFGS algorithm, the NEWUOA derivative free optimizer, the Covariance Matrix Adaptation Evolution Strategy (CMA-ES), the Differential Evolution (DE) algorithm and Particle Swarm Optimizers (PSO) are compared experimentally on benchmark functions reflecting important challenges encountered in real-world optimization problems. Dependence of the performances...
Flash memory-based solid-state disks are fast becoming the dominant form of end-user storage devices, partly even replacing the traditional hard-disks. Existing two-level memory hierarchy models fail to realize the full potential of flash-based storage devices. We propose two new computation models, the general flash model and the unit-cost model, for memory hierarchies involving these devices. Our...
We study a variant of Naor’s [23] online packet buffering model: We are given a (non-preemptive) fifo buffer (e.g., in a network switch or a router) and packets that request transmission arrive over time. Any packet has an intrinsic value R and we have to decide whether to accept or reject it. In each time-step, the first packet in the buffer (if any) is transmitted and our benefit of it is equal...
We present an algorithm that certifies the feasibility of a linear program while using rational arithmetic as little as possible. Our approach relies on computing a feasible solution of the linear program that is as far as possible from satisfying an inequality at equality. To realize such an approach, we have to detect the set of inequalities that can only be satisfied at equality. Compared...
A dynamic shortest-path algorithm is called a batch algorithm if it is able to handle graph changes that consist of multiple edge updates at a time. In this paper we focus on fully-dynamic batch algorithms for single-source shortest paths in directed graphs with positive edge weights. We give an extensive experimental study of the existing algorithms for the single-edge and the batch case, including...
We introduce a new type of bounding-volume hierarchy, the c-oriented rotated-box tree, or c-rb-tree for short. A c-rb-tree uses boxes as bounding volumes, whose orientations come from a fixed set of predefined box orientations. We theoretically and experimentally compare our new c-rb-tree to two existing bounding-volumes hierarchies, namely c-dop-tree and box-trees.
psort was the fastest sorting software in 2008 according to the Pennysort benchmark, sorting 181GB of data for 0.01$ of computer time. This paper details its internals, and the careful fitting of its architecture to the structure of modern PCs-class platforms, allowing it to outperform state-of-the-art sorting software such as GNUsort or STXXL.
The configuration of network resources greatly impacts the communication overhead for data intensive tasks and constitutes a critical problem in the design and maintenance of networks. To address the issue of resource placement, we analyze and implement a semidefinite programming-based heuristic for solving a known NP-complete graph optimization problem called Maximum Size Bounded Capacity Cut. Experimental...
What does it mean for two geometric graphs to be similar? We propose a distance for geometric graphs that we show to be a metric, and that can be computed by solving an integer linear program. We also present experiments using a heuristic distance function.
We present a contraction-based algorithm for computing the strongly connected components of large graphs. While the worst-case complexity of the algorithm can be terrible (essentially the cost of running a DFS-based internal-memory algorithm on the entire graph), our experiments confirm that the algorithm performs remarkably well in practice. The strongest competitor is the algorithm by Sibeyn et...
Up to now, research on speed-up techniques for Dijkstra’s algorithm focused on single-criteria scenarios. The goal was to find the quickest route within a transportation network. However, the quickest route is often not the best one. A user might be willing to accept slightly longer travel times if the cost of the journey is less. A common approach to cope with such a situation is to find Pareto-optimal...
List update algorithms have been widely used as subroutines in compression schemas, most notably as part of Burrows-Wheeler compression. The Burrows-Wheeler transform (BWT), which is the basis of many state-of-the-art general purpose compressors applies a compression algorithm to a permuted version of the original text. List update algorithms are a common choice for this second stage of BWT-based...
Every train schedule entails a certain risk of delay. When adding a new train to an existing timetable, planners have to take the expected risk of delay of the trains into account. Typically, this can be a very laborious task involving detailed simulations. We propose to predict the risk of a planned train using a series of linear regression models on the basis of extensive real world delay data of...
The suffix array of a string s of length n over the alphabet Σ is the permutation that gives us the lexicographic order of all suffixes of s. This popular index can be used to solve many problems in sequence analysis. In practice, one limitation of this data structure is its size of n logn bits, while the size of the text is n log|Σ| bits. For this reason compressed suffix arrays (CSAs) were introduced...
Recently, many speed-up techniques were developed for the computation of shortest paths in networks with rather static edge latencies. Very little is known about dealing with problems which rely on the computation of shortest paths in highly dynamic networks. However, with an increasing amount of traffic, static models of networks rather sparsely reflect realistic scenarios. In the framework of network...
We consider the b-matching problem in a hypergraph on n vertices and edge cardinality bounded by ℓ. Oblivious greedy algorithms achieve approximations of $(\sqrt{n}+1)^{-1}$ and (ℓ + 1)− 1 independently of b (Krysta 2005). Randomized rounding achieves constant-factor approximations of 1 − ε for large b, namely b = Ω(ε− 2, ln n), (Srivastav and Stangier 1997). Hardness of approximation...
We present initial results from the first empirical evaluation of a graph partitioning algorithm inspired by the Arora-Rao-Vazirani algorithm of [5], which combines spectral and flow methods in a novel way. We have studied the parameter space of this new algorithm, e.g., examining the extent to which different parameter settings interpolate between a more spectral and a more flow-based approach, and...
We present a cgal-based univariate algebraic kernel, which provides certified real-root isolation of univariate polynomials with integer coefficients and standard functionalities such as basic arithmetic operations, greatest common divisor (gcd) and square-free factorization, as well as comparison and sign evaluations of real algebraic numbers. We compare our kernel with other comparable kernels,...
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.