Refine
Document Type
- Article (6)
- Book (2)
- Conference Proceeding (1)
- Working Paper (1)
Has Fulltext
- yes (10)
Is part of the Bibliography
- no (10)
Keywords
- External Memory (2)
- Randomization (2)
- Agitation (1)
- Algorithmus (1)
- BFS (1)
- Connected Components (1)
- Dynamic Graph Algorithms (1)
- Experimental Evaluation (1)
- Flash Memories (1)
- GPU algorithms (1)
Network graphs have become a popular tool to represent complex systems composed of many interacting subunits; especially in neuroscience, network graphs are increasingly used to represent and analyze functional interactions between multiple neural sources. Interactions are often reconstructed using pairwise bivariate analyses, overlooking the multivariate nature of interactions: it is neglected that investigating the effect of one source on a target necessitates to take all other sources as potential nuisance variables into account; also combinations of sources may act jointly on a given target. Bivariate analyses produce networks that may contain spurious interactions, which reduce the interpretability of the network and its graph metrics. A truly multivariate reconstruction, however, is computationally intractable because of the combinatorial explosion in the number of potential interactions. Thus, we have to resort to approximative methods to handle the intractability of multivariate interaction reconstruction, and thereby enable the use of networks in neuroscience. Here, we suggest such an approximative approach in the form of an algorithm that extends fast bivariate interaction reconstruction by identifying potentially spurious interactions post-hoc: the algorithm uses interaction delays reconstructed for directed bivariate interactions to tag potentially spurious edges on the basis of their timing signatures in the context of the surrounding network. Such tagged interactions may then be pruned, which produces a statistically conservative network approximation that is guaranteed to contain non-spurious interactions only. We describe the algorithm and present a reference implementation in MATLAB to test the algorithm’s performance on simulated networks as well as networks derived from magnetoencephalographic data. We discuss the algorithm in relation to other approximative multivariate methods and highlight suitable application scenarios. Our approach is a tractable and data-efficient way of reconstructing approximative networks of multivariate interactions. It is preferable if available data are limited or if fully multivariate approaches are computationally infeasible.
We provide the first non-trivial result on dynamic breadth-first search (BFS) in external-memory: For general sparse undirected graphs of initially $n$ nodes and O(n) edges and monotone update sequences of either $\Theta(n)$ edge insertions or $\Theta(n)$ edge deletions, we prove an amortized high-probability bound of $O(n/B^{2/3}+\sort(n)\cdot \log B)$ I/Os per update. In contrast, the currently best approach for static BFS on sparse undirected graphs requires $\Omega(n/B^{1/2}+\sort(n))$ I/Os. 1998 ACM Subject Classification: F.2.2. Key words and phrases: External Memory, Dynamic Graph Algorithms, BFS, Randomization.
Data structures and advanced models of computation on big data : report from Dagstuhl seminar 14091
(2014)
This report documents the program and the outcomes of Dagstuhl Seminar 14091 "Data Structures and Advanced Models of Computation on Big Data". In today's computing environment vast amounts of data are processed, exchanged and analyzed. The manner in which information is stored profoundly influences the efficiency of these operations over the data. In spite of the maturity of the field many data structuring problems are still open, while new ones arise due to technological advances.
The seminar covered both recent advances in the "classical" data structuring topics as well as new models of computation adapted to modern architectures, scientific studies that reveal the need for such models, applications where large data sets play a central role, modern computing platforms for very large data, and new data structures for large data in modern architectures.
The extended abstracts included in this report contain both recent state of the art advances and lay the foundation for new directions within data structures research.
We propose a variation of online paging in two-level memory systems where pages in the fast cache get modified and therefore have to be explicitly written back to the slow memory upon evictions. For increased performance, up to alpha arbitrary pages can be moved from the cache to the slow memory within a single joint eviction, whereas fetching pages from the slow memory is still performed on a one-by-one basis. The main objective in this new alpha-paging scenario is to bound the number of evictions. After providing experimental evidence that alpha-paging can adequately model flash-memory devices in the context of translation layers we turn to the theoretical connections between alpha-paging and standard paging. We give lower bounds for deterministic and randomized alpha-paging algorithms. For deterministic algorithms, we show that an adaptation of LRU is strongly competitive, while for the randomized case we show that by adapting the classical Mark algorithm we get an algorithm with a competitive ratio larger than the lower bound by a multiplicative factor of approximately 1.7.
Background Titanium and titanium alloys are widely used for fabrication of dental implants. Since the material composition and the surface topography of a biomaterial play a fundamental role in osseointegration, various chemical and physical surface modifications have been developed to improve osseous healing. Zirconia-based implants were introduced into dental implantology as an altenative to titanium implants. Zirconia seems to be a suitable implant material because of its tooth-like colour, its mechanical properties and its biocompatibility. As the osseointegration of zirconia implants has not been extensively investigated, the aim of this study was to compare the osseous healing of zirconia implants with titanium implants which have a roughened surface but otherwise similar implant geometries. Methods Forty-eight zirconia and titanium implants were introduced into the tibia of 12 minipigs. After 1, 4 or 12 weeks, animals were sacrificed and specimens containing the implants were examined in terms of histological and ultrastructural techniques. Results Histological results showed direct bone contact on the zirconia and titanium surfaces. Bone implant contact as measured by histomorphometry was slightly better on titanium than on zirconia surfaces. However, a statistically significant difference between the two groups was not observed. Conclusion The results demonstrated that zirconia implants with modified surfaces result in an osseointegration which is comparable with that of titanium implants.
Background The successful use of zirconia ceramics in orthopedic surgery led to a demand for dental zirconium-based implant systems. Because of its excellent biomechanical characteristics, biocompatibility, and bright tooth-like color, zirconia (zirconium dioxide, ZrO2) has the potential to become a substitute for titanium as dental implant material. The present study aimed at investigating the osseointegration of zirconia implants with modified ablative surface at an ultrastructural level. Methods A total of 24 zirconia implants with modified ablative surfaces and 24 titanium implants all of similar shape and surface structure were inserted into the tibia of 12 Gottinger minipigs. Block biopsies were harvested 1 week, 4 weeks or 12 weeks (four animals each) after surgery. Scanning electron microscopy (SEM) analysis was performed at the bone implant interface. Results Remarkable bone attachment was already seen after 1 week which increased further to intimate bone contact after 4 weeks, observed on both zirconia and titanium implant surfaces. After 12 weeks, osseointegration without interposition of an interfacial layer was detected. At the ultrastructural level, there was no obvious difference between the osseointegration of zirconia implants with modified ablative surfaces and titanium implants with a similar surface topography. Conclusion The results of this study indicate similar osseointegration of zirconia and titanium implants at the ultrastructural level.
Background Osseointegration is crucial for the long-term success of dental implants and depends on the tissue reaction at the tissue-implant interface. Mechanical properties and biocompatibility make zirconia a suitable material for dental implants, although surface processings are still problematic. The aim of the present study was to compare osteoblast behavior on structured zirconia and titanium surfaces under standardized conditions. Methods The surface characteristics were determined by scanning electron microscopy (SEM). In primary bovine osteoblasts attachment kinetics, proliferation rate and synthesis of bone-associated proteins were tested on different surfaces. Results The results demonstrated that the proliferation rate of cells was significantly higher on zirconia surfaces than on titanium surfaces (p < 0.05; Student's t-test). In contrast, attachment and adhesion strength of the primary cells was significant higher on titanium surfaces (p < 0.05; U test). No significant differences were found in the synthesis of bone-specific proteins. Ultrastructural analysis revealed phenotypic features of osteoblast-like cells on both zirconia and titanium surfaces. Conclusion The study demonstrates distinct effects of the surface composition on osteoblasts in culture. Zirconia improves cell proliferation significantly during the first days of culture, but it does not improve attachment and adhesion strength. Both materials do not differ with respect to protein synthesis or ultrastructural appearance of osteoblasts. Zirconium oxide may therefore be a suitable material for dental implants.
We empirically investigate algorithms for solving Connected Components in the external memory model. In particular, we study whether the randomized O(Sort(E)) algorithm by Karger, Klein, and Tarjan can be implemented to compete with practically promising and simpler algorithms having only slightly worse theoretical cost, namely Borůvka’s algorithm and the algorithm by Sibeyn and collaborators. For all algorithms, we develop and test a number of tuning options. Our experiments are executed on a large set of different graph classes including random graphs, grids, geometric graphs, and hyperbolic graphs. Among our findings are: The Sibeyn algorithm is a very strong contender due to its simplicity and due to an added degree of freedom in its internal workings when used in the Connected Components setting. With the right tunings, the Karger-Klein-Tarjan algorithm can be implemented to be competitive in many cases. Higher graph density seems to benefit Karger-Klein-Tarjan relative to Sibeyn. Borůvka’s algorithm is not competitive with the two others.