@inproceedings{19932, abstract = {{#hniid 2484}}, author = {{Kortenjan, Michael and Schomaker, Gunnar}}, booktitle = {{4th International Conference on Virtual Reality, Computer Graphics, Visualization and Interaction (Afrigraph 2006)}}, title = {{{Size equivalent cluster trees (SEC-Trees) realtime rendering of large industrial scenes}}}, doi = {{10.1145/1108590.1108608}}, year = {{2006}}, } @inproceedings{24277, abstract = {{We propose a dynamic, ad-hoc communication network consisting of mobile units that can warn about traffic jams on motorways. Our goal is to provide a practical, low cost solution. Therefore we consider very simple wireless communication hardware, without collision detection, with very small bandwidth and a probabilistic model of link failure. We provide a complete system architecture. For this purpose we design and analyze solutions for size approximation, leader election and broadcasting. Our algorithms are fine-tuned for fast operation in a practical setting. We provide both a theoretical and experimental evaluation of our solutions. Our contribution is much different from the previous work, where either pure theoretical models with a pure theoretical analysis are provided or algorithms working in practical models are evaluated only through simulations.}}, author = {{Kutyłowski, Jarosław and Zagórski, Filip}}, booktitle = {{SOFSEM 2006: Theory and Practice of Computer Science}}, issn = {{0302-9743}}, title = {{{Reliable Broadcasting Without Collision Detection}}}, doi = {{10.1007/11611257_37}}, year = {{2006}}, } @inproceedings{26988, abstract = {{For most of today's IT environments, the tremendous need for storage capacity in combination with a required minimum I/O performance has become highly critical. In dynamically growing environments, a storage management solution's underlying data distribution scheme has great impact to the overall system I/O performance. The evaluation of a number of open system storage visualization solutions and volume managers has shown that all of them lack the ability to automatically adapt to changing access patterns and storage infrastructures; many of them require an error prone manual re-layout of the data blocks, or rely on a very time consuming re-striping of all available data. This paper evaluates the performance of conventional data distribution approaches compared to the adaptive virtualization solution V:DRIVE in dynamically changing storage environments. Changes of the storage infrastructure are normally not considered in benchmark results, but can have a significant impact on storage performance. Using synthetic benchmarks, V:DRIVE is compared in such changing environments with the non-adaptive Linux logical volume manager (LVM). The performance results of our tests clearly outline the necessity of adaptive data distribution schemes.}}, author = {{Brinkmann, Andre and Effert, Sascha and Heidebuer, Michael and Vodisek, Mario}}, booktitle = {{14th Euromicro International Conference on Parallel, Distributed, and Network-Based Processing (PDP'06)}}, title = {{{Influence of adaptive data layouts on performance in dynamically changing storage environments}}}, doi = {{10.1109/pdp.2006.44}}, year = {{2006}}, } @proceedings{17417, abstract = {{We present a parallel algorithm for the rendering of complex three-dimensional scenes. The algorithm runs across heterogeneous architectures of PC-clusters consisting of a visualization-node, equipped with a powerful graphics adapter, and cluster nodes requiring weaker graphics capabilities only. The visualization-node renders a mixture of scene objects and simplified meshes (Reliefboards). The cluster nodes assist the visualization-node by asynchronous computing of Reliefboards, which are used to replace and render distant parts of the scene. Our algorithm is capable of gaining significant speedups if the cluster's nodes provide weak graphics adapters only. We trade the number of cluster nodes off the scene objects' image quality.}}, editor = {{Rammig, Franz-Josef and Dangelmaier, Wilhelm and Karl, Holger and Mertsching, Bärbel and Meyer auf der Heide, Friedhelm and Trächtler, Ansgar}}, publisher = {{Verlagsschriftenreihe des Heinz Nixdorf Instituts}}, title = {{{Self-Coordinating Systems: The Next Challenge in Research on Distributed Systems}}}, year = {{2006}}, } @book{17475, author = {{Monien, Burkhard and Meyer auf der Heide, Friedhelm}}, isbn = {{978-3-939350-00-2}}, publisher = {{Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn}}, title = {{{New trends in parallel and distributed computing}}}, volume = {{181}}, year = {{2006}}, } @inproceedings{17619, author = {{Grünewald, Matthias and Meyer auf der Heide, Friedhelm and Rührup, Stefan and Schindelhauer, Christian and Volbert, Klaus}}, booktitle = {{New Trends in Parallel & Distributed Computing, 6th Int. Heinz Nixdorf Symposium}}, pages = {{225--234}}, publisher = {{Verlagsschriftenreihe des Heinz Nixdorf Instituts}}, title = {{{Directional Communication in Mobile Ad Hoc Networks}}}, year = {{2006}}, } @inproceedings{18676, abstract = {{We present random sampling algorithms that with probability at least 1 - δ compute a (1 ± ǫ)- approximation of the clustering coefficient, the transitiv ity coefficient, and of the number of bipartite cliques in a graph given as a stream of edges. Our methods can be extended to approximately count the number of occurences of fixed constant-size subgraphs. Our a lgorithms only require one pass over the input stream and their storage space depends only on structural parameters of the graphs, the approxi- mation guarantee, and the confidence probability. For examp le, the algorithms to compute the clustering and transitivity coefficient depend on that coefficient but n ot on the size of the graph. Since many large social networks have small clustering and transitivity coe fficient, our algorithms use space independent of the size of the input for these graphs. We implemented our algorithms and evaluated their performance on networks from different appli- cation domains. The sizes of the considered input graphs varied from about 8, 000 nodes and 40, 000 edges to about 135 million nodes and more than 1 billion edges. For both algorithms we run experiments with a sample set size varying from 100, 000 to 1, 000, 000 to evaluate running time and approximation guarantee. Our algorithms appear to be time efficient for the se sample sizes.}}, author = {{Sohler, Christian and Frahling, Gereon and Marchetti-Spaccamela, Alberto and Leonardi, Stefano and Buriol, Luciana}}, booktitle = {{Proceedings of the European Conference on Complex Systems (ECCS'06)}}, title = {{{Computing Clustering Coefficients in Data Streams}}}, year = {{2006}}, } @inproceedings{18745, author = {{Sohler, Christian and Frahling, Gereon and Marchetti-Spaccamela, Alberto and Leonardi, Stefano and Buriol, Luciana}}, title = {{{Counting Triangles in Data Streams}}}, year = {{2006}}, } @inproceedings{18746, abstract = {{In this paper, we present a randomized constant factor approximation algorithm for the metric minimum facility location problem with uniform costs and demands in a distributed setting, in which every point can open a facility. In particular, our distributed algorithm uses three communication rounds with message sizes bounded to O(log n) bits where n is the number of points. We also extend our algorithm to constant powers of metric spaces, where we also obtain a randomized constant factor approximation algorithm.}}, author = {{Sohler, Christian and Gehweiler, Joachim and Lammersen, Christiane}}, booktitle = {{Proceeedings of 18th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)}}, title = {{{A Distributed O(1)-Approximation Algorithm for the Uniform Facility Location Problem}}}, year = {{2006}}, } @inproceedings{18926, author = {{Dynia, Miroslaw and Korzeniowski, Miroslaw and Schindelhauer, Christian}}, booktitle = {{Architecture of Computing Systems - ARCS}}, isbn = {{9783540327653}}, issn = {{0302-9743}}, number = {{3894}}, pages = {{341----351}}, title = {{{Power-Aware Collective Tree Exploration}}}, doi = {{10.1007/11682127_24}}, year = {{2006}}, } @phdthesis{18972, author = {{Damerow, Valentina}}, isbn = {{3-939350-09-5}}, publisher = {{Verlagsschriftenreihe des Heinz Nixdorf Instituts, Paderborn}}, title = {{{Average and Smoothed Complexity of Geometric Structures}}}, volume = {{190}}, year = {{2006}}, } @inproceedings{18999, abstract = {{We present a web computing library (PUBWCL) in Java that allows to execute tightly coupled, massively parallel algorithms in the bulk-synchronous (BSP) style on PCs distributed over the internet whose owners are willing to donate their unused computation power. PUBWCL is realized as a peer-to-peer system and features migration and restoration of BSP processes executed on it. The use of Java guarantees a high level of security and makes PUBWCL platform- independent. In order to estimate the loss of efficiency inherent in such a Java-based system, we have compared it to our C-based PUB-Library. As the unused computation power of the participating PCs is unpredictable, we need novel strategies for load balancing that have no access to future changes of the computation power available for the application. We develop, analyze, and compare different load balancing strategies for PUBWCL. In order to handle the influence of the fluctuating available computation power, we classify the external work load. During our evaluation of the load balancing algorithms we simulated the external work load in order to have repeatable testing conditions. With the best performing load balancing strategy we could save 39% of the execution time on average and even up to 50% in particular cases, in our test environment. }}, author = {{Bonorden, Olaf and Meyer auf der Heide, Friedhelm and Gehweiler, Joachim}}, booktitle = {{Journal on Scalable Computing: Practice and Experience}}, pages = {{1--14}}, title = {{{A Web Computing Environment for Parallel Algorithms in Java}}}, year = {{2006}}, } @inproceedings{19001, abstract = {{We present a novel architecture for distributed computing in a peer-to-peer network. In particular, we realize the Paderborn University BSP-based Web Computing Library (PUBWCL), which formerly used a centralized client-server architecture for scheduling and load balancing, as a pure peer-to-peer system. Using distributed heterogeneous hash tables (DHHT), our architecture features scheduling and load balancing of tightly coupled, massively parallel algorithms in the bulk-synchronous (BSP) style with a minimal number of migrations. }}, author = {{Gehweiler, Joachim and Schomaker, Gunnar}}, booktitle = {{Proceeedings of 10th IEEE/ACM International Symposium on Distributed Simulation and Real Time Applications (DS-RT)}}, isbn = {{0769526977}}, pages = {{51--58}}, title = {{{Distributed Load Balancing in Heterogeneous Peer-to-Peer Networks for Web Computing Libraries}}}, doi = {{10.1109/ds-rt.2006.15}}, year = {{2006}}, } @article{23881, abstract = {{Computing a maximum weighted stable set in a bipartite graph is considered well-solved and usually approached with preflow-push, Ford–Fulkerson or network simplex algorithms. We present a combinatorial algorithm for the problem that is not based on flows. Numerical tests suggest that this algorithm performs quite well in practice and is competitive with flow based algorithms especially in the case of dense graphs.}}, author = {{Faigle, Ulrich and Frahling, Gereon}}, issn = {{0166-218X}}, journal = {{Discrete Applied Mathematics}}, pages = {{1380--1391}}, title = {{{A combinatorial algorithm for weighted stable sets in bipartite graphs}}}, doi = {{10.1016/j.dam.2005.05.037}}, year = {{2006}}, } @inproceedings{23882, abstract = {{In this paper we develop an efficient implementation for a k-means clustering algorithm. Our algorithm is a variant of KMHybrid [28, 20], i.e. it uses a combination of Lloyd-steps and random swaps, but as a novel feature it uses coresets to speed up the algorithm. A coreset is a small weighted set of points that approximates the original point set with respect to the considered problem. The main strength of the algorithm is that it can quickly determine clusterings of the same point set for many values of k. This is necessary in many applications, since, typically, one does not know a good value for k in advance. Once we have clusterings for many different values of k we can determine a good choice of k using a quality measure of clusterings that is independent of k, for example the average silhouette coefficient. The average silhouette coefficient can be approximated using coresets.To evaluate the performance of our algorithm we compare it with algorithm KMHybrid [28] on typical 3D data sets for an image compression application and on artificially created instances. Our data sets consist of 300,000 to 4.9 million points. We show that our algorithm significantly outperforms KMHybrid on most of these input instances. Additionally, the quality of the solutions computed by our algorithm deviates less than that of KMHybrid.We also computed clusterings and approximate average silhouette coefficient for k=1,…,100 for our input instances and discuss the performance of our algorithm in detail.}}, author = {{Frahling, Gereon and Sohler, Christian}}, booktitle = {{Proceedings of the twenty-second annual symposium on Computational geometry - SCG '06}}, title = {{{A fast k-means implementation using coresets}}}, doi = {{10.1145/1137856.1137879}}, year = {{2006}}, } @misc{20436, author = {{Hamann, Heiko}}, title = {{{Modeling and Investigation of Robot Swarms}}}, year = {{2006}}, } @article{17979, author = {{Schindelhauer, Christian and Volbert, Klaus and Ziegler, Martin}}, issn = {{0925-7721}}, journal = {{Computational Geometry}}, pages = {{197--214}}, title = {{{Geometric spanners with applications in wireless networks}}}, doi = {{10.1016/j.comgeo.2006.02.001}}, year = {{2006}}, } @article{17985, author = {{Ziegler, Martin}}, issn = {{0885-064X}}, journal = {{Journal of Complexity}}, pages = {{827--849}}, title = {{{Effectively open real functions}}}, doi = {{10.1016/j.jco.2006.05.002}}, year = {{2006}}, } @inbook{17987, author = {{Meer, Klaus and Ziegler, Martin}}, booktitle = {{Logical Approaches to Computational Barriers}}, isbn = {{9783540354666}}, issn = {{0302-9743}}, title = {{{Uncomputability Below the Real Halting Problem}}}, doi = {{10.1007/11780342_39}}, year = {{2006}}, } @inproceedings{18351, abstract = {{In this paper the ideas of a new research project are presented. The material flow simu- lator d3FACT insight shall manage multiple parallel and time synchronous simulations to grand the power of real-time visualization in combination with statistical analysis. This research is issued to overcome the conflict of simulation run repetition for a good statistical basis and real-time immersive visualization. A side effect will be the reduc- tion of time needed for simulation experiments. The planned simulation tool has the feature of triggered cloning, i.e., the user can decide during runtime to clone a set of simulations after changing parameters to preserve the original system. The simulations will be aggregated by visualization and statistics. The rendering is planned to overlay several simulations using effects like inking and transparency. Simulation data will be aggregated with statistical functions and diagrams.}}, author = {{Dangelmaier, Wilhelm and Huber, Daniel and Laroque, Christoph and Aufenanger, Mark and Fischer, Matthias and Krokowski, Jens and Kortenjan, Michael}}, booktitle = {{Simulation and Visualization 2006 (SimViS)}}, pages = {{79--88}}, publisher = {{SCS European Publishing House}}, title = {{{d³FACT insight goes parallel - Aggregation of multiple simulations}}}, year = {{2006}}, }