Memory-Efficient GPU Volume Path Tracing of AMR Data Using the Dual Mesh

A common way to render cell-centric adaptive mesh refinement (AMR) data is to compute the dual mesh and visualize that with a standard unstructured element renderer. While the dual mesh provides a high-quality interpolator, the memory requirements of the dual mesh data structure are significantly higher than those of the original grid, which prevents rendering very large data sets. We introduce a GPU-friendly data structure and a clustering algorithm that allow for efficient AMR dual mesh rendering with a competitive memory footprint. Fundamentally, any off-the-shelf unstructured element renderer running on GPUs could be extended to support our data structure just by adding a gridlet element type in addition to the standard tetrahedra, pyramids, wedges, and hexahedra supported by default. We integrated the data structure into a volumetric path tracer to compare it to various state-of-the-art unstructured element sampling methods. We show that our data structure easily competes with these methods in terms of rendering performance, but is much more memory-efficient.     

Filter ranking in high-dimensional space

High-dimensional index structures are a means to accelerate database query processing in high-dimensional data, like multimedia feature vectors. A particular interest in many application scenarios is to rank data items with respect to a certain distance function and, thus, identifying the nearest neighbor(s) of a query item.

In this paper, we propose a novel ranking algorithm that (1) operates on arbitrary high-dimensional filter indexes, like the VA-file, the VA⁺-file, the LPC-file, or the AV-method. Our ranking algorithm (2) exhibits a nearly balanced I/O load to retrieve subsequent items. Finally, it (3) strictly obeys a predefined main memory threshold and even (4) terminates successfully when memory restrictions are very tight.     

Randomized local search,evolutionary algorithms,and the minimum spanning tree problem

Randomized search heuristics, among them randomized local search and evolutionary algorithms, are applied to problems whose structure is not well understood, as well as to problems in combinatorial optimization. The analysis of these randomized search heuristics has been started for some well-known problems, and this approach is followed here for the minimum spanning tree problem. After motivating this line of research, it is shown that randomized search heuristics find minimum spanning trees in expected polynomial time without employing the global technique of greedy algorithms.     

Rankings oder Ratings: Warum, wie und durch wen?

Für Zeitungen und Magazine ist es attraktiv, Rankings von Universitäten und Fachbereichen zu veröffentlichen, und die Studierenden lassen sich verstärkt von diesen Informationen bei der Wahl ihres Studienortes beeinflussen.     

Numerical analysis of continuous time Markov decision processes over finite horizons

Continuous time Markov decision processes (CTMDPs) with a finite state and action space have been considered for a long time. It is known that under fairly general conditions the reward gained over a finite horizon can be maximized by a so-called piecewise constant policy which changes only finitely often in a finite interval. Although this result is available for more than 30 years, numerical analysis approaches to compute the optimal policy and reward are restricted to discretization methods which are known to converge to the true solution if the discretization step goes to zero. In this paper, we present a new method that is based on uniformization of the CTMDP and allows one to compute an ε-optimal$\epsilon \text{-optimal}$ policy up to a predefined precision in a numerically stable way using adaptive time steps.     

Stability of Unstable Learning Algorithms

We introduce graphical learning algorithms and use them to produce bounds on error deviance for unstable learning algorithms which possess a partial form of stability. As an application we obtain error deviance bounds for support vector machines (SVMs) with variable offset parameter. Editor: Avrim Blum     

On compliance checking for clausal constraints in annotated process models

Compliance management is important in several industry sectors where there is a high incidence of regulatory control. It must be ensured that business practices, as reflected in business processes, comply with the rules. Such compliance checks are challenging due to (1) the different life cycles of rules and processes, and (2) their disparate representations. (1) requires retrospective checking of process models. To address (2), we herein devise a framework where processes are annotated to capture the semantics of task execution, and compliance is checked against a set of constraints posing restrictions on the desirable process states. Each constraint is a clause, i.e., a disjunction of literals. If a process can reach a state that falsifies all literals of one of the constraints, then that constraint is violated in that state, and indicates non-compliance. Naively, such compliance can be checked by enumerating all reachable states. Since long waiting times are undesirable, it is important to develop efficient (low-order polynomial time) algorithms that (a) perform exact compliance checking for restricted cases, or (b) perform approximate compliance checking for more general cases. Herein, we observe that methods of both kinds can be defined as a natural extension of our earlier work on semantic business process validation. We devise one method of type (a), and we devise two methods of type (b); both are based on similar restrictions to the processes, where the restrictions made by methods (b) are a subset of those made by method (a). The approximate methods each guarantee either of soundness (finding only non-compliances) or completeness (finding all non-compliances). We describe how one can trace the state evolution back to the process activities which caused the (potential) non-compliance, and hence provide the user with an error diagnosis.     

Image representation by complex cell responses

We present an analysis of the representation of images as the magnitudes of their transform with complex-valued Gabor wavelets. Such a representation is a model for complex cells in the early stage of visual processing and of high technical usefulness for image understanding, because it makes the representation insensitive to small local shifts. We show that if the images are band limited and of zero mean, then reconstruction from the magnitudes is unique up to the sign for almost all images.     

The Active Vertice method: a performant filtering approach to high-dimensional indexing

The problem of finding nearest neighbors has emerged as an important foundation of feature-based similarity search in multimedia databases. Most spatial index structures based on the R-tree have failed to efficiently support nearest neighbor search in arbitrarily distributed high-dimensional data sets. In contrast, the so-called filtering principle as represented by the popular VA-file has turned out to be a more promising approach. Query processing is based on a flat file of compact vector approximations. In a first stage, those approximations are sequentially scanned and filtered so that in a second stage the nearest neighbors can be determined from a relatively small fraction of the data set.

In this paper, we propose the Active Vertice method as a novel filtering approach. As opposed to the VA-file, approximation regions are arranged in a quad-tree like structure. High-dimensional feature vectors are assigned to ellipsoidal approximation regions on different levels of the tree. A compact approximation of a vector corresponds to the path within the index from the root to the respective tree node. When compared to the VA-file, our method enhances the discriminatory power of the approximations while maintaining their compactness in terms of storage consumption. To demonstrate its effectiveness, we conduct extensive experiments with synthetic as well as real-life data and show the superiority of our method over existing filtering approaches.