An \(f\)-Sensitive Distance Oracle with stretch a preprocesses a graph \( G(V, E) \) and produces a small data structure that is used to answer subsequent queries. A query is a triple consisting of a set \( F \subset E \) of at most \(f\) edges, and vertices \(s\) and \(t\). The oracle answers a query \( (F,s.,t) \) by returning a value \(d\) which is equal to the length of some path between \(s\) and \(t\) in the graph \(G \setminus F\) (the graph obtained from \(G\) by discarding all edges in \(F\)). Moreover, d is at most a times the length of the shortest path between \(s\) and \(t\) in \(G \setminus F\). The oracle can also construct a path between \(s\) and \(t\) in \(G \setminus F\) of length \(d\). To the best of our knowledge we give the first nontrivial f-sensitive distance oracle with fast query time and small stretch capable of handling multiple edge failures. Specifically, for any \( \mathcalO(\frac\log n\log \log n ) \) and a fixed \( \varepsilon > 0 \) our oracle answers queries \( (F,s,t) \) in time \( \mathcalO(l) \) with \( (1 + \varepsilon) \) stretch using a data structure of size \( n^2+ \mathcalO(1) \) For comparison, the naive alternative requires \( m^f n^2 \) space for sublinear query time.

Evolutionary algorithms (EAs) perform well in settings involving uncertainty, including settings with stochastic or dynamic fitness functions. In this paper, we analyze the (1+1) EA on dynamically changing OneMax, as introduced by Droste (2003). We re-prove the known results on first hitting times using the modern tool of drift analysis. We extend these results to search spaces which allow for more than two values per dimension. Furthermore, we make an anytime analysis as suggested by Jansen and Zarges (2014), analyzing how closely the (1+1) EA can track the dynamically moving optimum over time. We get tight bounds both for the case of bit strings, as well as for the case of more than two values per position. Surprisingly, in the latter setting, the expected quality of the search point maintained by the (1+1) EA does not depend on the number of values per dimension.

In this paper, we present a 2.5D visualization technique based on the dust & magnet metaphor, which generally allows for interactively exploring and analyzing large multivariate data sets. In addition to position and color, we introduce height as additional visual variable for particles to encode extra data attributes in the 2.5D visualization, thus increasing the potential for identifying correlations between attributes. Further, we have developed a real-time collision detection algorithm as part of the particle simulation that ensures overlap-free particle positioning, thereby enabling the continuous perception of patterns, clusters, and outliers. These extensions facilitate on-the-fly validation of hypotheses through the highly dynamic configuration of magnets and visual attribute encoding, which also allows for a better integration of the user’s domain knowledge. We demonstrate the application of our visualization technique using various real-world data sets from different domains, e.g., finance and software analytics.

The question whether to use 2D or 3D for data visualization is generally difficult to decide. Two-dimensional and three-dimensional visualization techniques exhibit different advantages and disadvantages related to various perceptual and technical aspects such as occlusion, clutter, distortion, or scalability. To facilitate problem understanding and comparison of existing visualization techniques with regard to these aspects, this report introduces a systematization based on presentation characteristics. It enables a categorization with respect to combinations of static 2D and 3D presentations of attributes and their spatial reference. Further, it complements ex-isting systematizations of data in an effort to formalize a common terminology and theoretical framework for this problem domain. We demonstrate our approach by reviewing different visualization techniques of spatial data according to the presented systematization.

3D integration has the potential to improve the scalability and performance of Chip Multiprocessors (CMP). A closed form analytical solution for optimizing 3D CMP cache hierarchy is developed. It allows optimal partitioning of the cache hierarchy levels into 3D silicon layers and optimal allocation of area among cache hierarchy levels under constrained area and power budgets. The optimization framework is extended by incorporating the impact of multithreaded data sharing on the private cache miss rate. An analytical model for cache access time as a function of cache size and a number of 3D partitions is proposed and verified using CACTI simulation

This paper investigates and discusses concepts and techniques to enhance spatial knowledge transmission of 3D city model representations based on cartography-oriented design. 3D city models have evolved to important tools for urban decision processes and information systems, especially in planning, simulation, networks, and navigation. For example, planning tools analyze visibility characteristics of inner urban areas and allow planers to estimate whether a minimum amount of light is needed in intensely covered areas to avoid “Gotham city effect“, i.e., when these areas become too dark due to shadowing. For radio network planning, 3D city models are required to configure wireless network services, i.e., to calculate and analyze network coverage and connectivity features. 3D city model visualization often lacks effectiveness and expressiveness. For example, if we analyze common 3D views, large areas of the graphical presentations contain useless or even “misused” pixels with respect to information content and transfer (e.g., pixels that represent several hundreds of buildings at once or pixels that show sky). Typical avatar perspectives frequently show too many details at once and do not distinguish between areas in focus and surrounding areas. In this case the perceptual and cognitive quality of visualized virtual 3D city model could be enhanced by cartographic models and semiotic adaptations. For example, we can integrate strongly perceivable landmarks as referencing marks to the real world, which establish more effective presentations and improve efficient interaction. The referencing aspect in depictions of 3D city models is essential: Only correctly perceived elements can fulfill referencing tasks. With misleading perception, the same elements may cause false understanding. This circumstance leads to media-dependent semiotic models that aim at supporting effective transmission of spatial contents. This contribution compares different dynamic 3D visualization approaches for virtual 3D city models and demonstrates applied cartographic techniques to enhance information transfer. The underlying concept is based on a model for 3D semiotics, includes a number of pragmatic components, and presents examples of visualizations of adapted 3D city model visualizations.

Focus + context visualization facilitates the exploration of complex information spaces. This paper proposes 3D generalization lenses, a new visualization technique for virtual 3D city models that combines different levels of structural abstraction. In an automatic preprocessing step, we derive a generalized representation of a given city model. At runtime, this representation is combined with a full-detail representation within a single view based on one or more 3D lenses of arbitrary shape. Focus areas within lens volumes are shown in full detail while excluding less important details of the surrounding area. Our technique supports simultaneous use of multiple lenses associated with different abstraction levels, can handle overlapping and nested lenses, and provides interactive lens modification.

Design, implementation, and operation of services for interactive 3D geovisualization are faced with a large number of challenges including (a) processing and integration of massive amounts of heterogeneous and distributed 2D and 3D geodata such as terrain models, buildings models, and thematic georeferenced data, (b) assembling, styling, and rendering 3D map contents according to application requirements and design principles, and (c) interactive provisioning of created 3D maps on mobile devices and thin clients as well as their integration as third-party components into domainspecific web and information systems. This report presents a concept and implementation of a service-oriented platform that addresses these major requirements of 3D web mapping systems. It is based on a separation of concerns for data management, 3D rendering, application logic, and user interaction. The main idea is to divide 3D rendering process into two stages. In the first stage, at the server side, an imagebased representation of the 3D scene is created by means of multi-layered virtual 3D panoramas; in the second stage, at the client side, the 3D scene is interactively reconstructed based on these panoramas. Beside the interactive client introduced earlier, scalable variant for provisioning of virtual 3D city models is described, that utilizes the capabilities of our rendering service for data preparation.

Isocontours (also isopleths, isolines, level sets) are commonly used to visualize real-valued data defined over a 2D plane according to a set of given isovalues. To support the 3D landscape metaphor for information visualization, a 3D stepped terrain can be derived by lifting and extruding isolines to their particular isovalue, but typically requires triangulation of the resulting surface representation in a preprocessing step. We present a concept and rendering technique for triangle-based terrain models that provide interactive, adaptive generation and visualization of such stepped terrains without preprocessing. Our fully hardware-accelerated rendering technique creates additional step geometry for each triangle intersecting an iso-plane on-the-fly. Further, an additional interpolation schema facilitates smooth transition between established 3D terrain visualization and its stepped variant.

Research in cognitive sciences suggests that orientation and navigation along routes can be improved if the graphical representation is aligned with the user’s mental concepts of a route. In this paper, we analyze an existing 2D schematization approach called wayfinding choremes and present an implementation for virtual 3D urban models, transferring the approach to 3D. To create the virtual environment, we transform the junctions of a route defined for a given road network to comply with the eight sector model, that is, outgoing legs of a junction are slightly rotated to align with prototypical directions in 45° increments. Then, the adapted road network is decomposed into polygonal block cells, the individual polygons being extruded to blocks and their facades textured. For the evaluation of our 3D wayfinding choreme implementation, we present an experiment framework allowing for training and testing subjects by a route learning task. The experimental framework can be parameterized flexibly, exposing parameters to the conductor. We finally give a sketch of a user study by identifying hypotheses, indicators, and, hence, experiments to be done.

6LoWPAN is a protocol stack for seamlessly integrating 802.15.4-based wireless sensor networks with IPv6 networks. The security of 6LoWPAN widely depends on the 802.15.4 security sublayer. This sublayer also supports pairwise keys so as to mitigate node compromises. Currently, the establishment of pairwise keys is however unspecified. Moreover, broadcast keys are shared among multiple nodes, which is not compromise resilient. In this paper, we propose two energy-efficient and DoS-resilient 802.15.4 add-ons to fill these gaps: First, a pairwise key establishment scheme, which is adaptable to different 6LoWPAN networks and threat models. Second, an easy-to-implement and compromise-resilient protocol for authenticating broadcast frames. Together, our add-ons contain the effects of node compromises and provide a basis for detecting compromised nodes autonomously. We implemented both add-ons in Contiki and tested them on TelosB motes.

6LoWPAN is a protocol stack for seamlessly integrating 802.15.4-based wireless sensor networks with IPv6 networks. The security of 6LoWPAN widely depends on the 802.15.4 security sublayer. This sublayer also supports pairwise keys so as to mitigate node compromises. Currently, the establishment of pairwise keys is however unspecified. Moreover, broadcast keys are shared among multiple nodes, which is not compromise resilient. In this paper, we propose two energy-efficient and DoS-resilient 802.15.4 add-ons to fill these gaps: First, a pairwise key establishment scheme, which is adaptable to different 6LoWPAN networks and threat models. Second, an easy-to-implement and compromise-resilient protocol for authenticating broadcast frames. Together, our add-ons contain the effects of node compromises and provide a basis for detecting compromised nodes autonomously. We implemented both add-ons in Contiki and tested them on TelosB motes.

Based on the assumption that semantic relatedness between documents is reflected in the distribution of the vocabulary, topic models are a widely used technique for different analysis tasks. Their application results in concepts, the so-called topics, and a high-dimensional description of the documents. For visualization tasks, they can further be projected onto a lower-dimensional space using a dimension reduction technique. Though the quality of the resulting scatter plot mainly depends on the chosen layout technique and the choice of its hyperparameters, it is unclear which particular combinations of topic models and dimension reduction techniques are suitable for displaying the semantic relatedness between the documents. In this work, we propose a benchmark comprising various datasets, layout techniques, and quality metrics for conducting an empirical study on different such layout algorithms.

BigBench is the first proposal for an end to end big data analytics benchmark. It features a rich query set with complex, realistic queries. BigBench was developed based on the decision support benchmark TPC-DS. The first proof-of-concept implementation was built for the Teradata Aster parallel database system and the queries were formulated in the proprietary SQL-MR query language. To test other other systems, the queries have to be translated. In this paper, an alternative implementation of BigBench for the Hadoop ecosystem is presented. All 30 queries of BigBench were realized using Apache Hive, Apache Hadoop, Apache Mahout, and NLTK. We will present the different design choices we took and show a proof of concept evaluation.

The editing problem asks to transform a given graph into a disjoint union of cliques by inserting and deleting as few edges as possible. We describe and evaluate an exact branch-and-bound algorithm for cluster editing. For this, we introduce new reduction rules and adapt existing ones. Moreover, we generalize a known packing technique to obtain lower bounds and experimentally show that it contributes significantly to the performance of the solver. Our experiments further evaluate the effectiveness of the different reduction rules and examine the effects of structural properties of the input graph on solver performance. Our solver won the exact track of the 2021 PACE challenge.