The forgiving tree: a self-healing distributed data structure

We consider the problem of self-healing in peer-to-peer networks that are under repeated attack by an omniscient adversary. We assume that the following process continues for up to n rounds where n is the total number of nodes initially in the network: the adversary deletesan arbitrary node from the network, then the network responds by quickly adding a small number of new edges.

We present a distributed data structure that ensures two key properties. First, the diameter of the network is never more than O(log Delta) times its original diameter, where Delta is the maximum degree of the network initially. We note that for many peer-to-peer systems, Delta is polylogarithmic, so the diameter increase would be a O(loglog n) multiplicative factor. Second, the degree of any node never increases by more than 3 over its original degree. Our data structure is fully distributed, has O(1) latency per round and requires each node to send and receive O(1) messages per round. The data structure requires an initial setup phase that has latency equal to the diameter of the original network, and requires, with high probability, each node v to send O(log n) messages along every edge incident to v. Our approach is orthogonal and complementary to traditional topology-based approaches to defending against attack.

Tree-Based Adaptive Spatial Detection for Adaptive Modulated MIMO Systems

Adaptive Multiple-Input Multiple-Output (MIMO) systems achieve a much higher information rate than conventional fixed schemes due to their ability to adapt their configurations according to the wireless communications environment. However, current adaptive MIMO detection schemes exhibit either low performance (and hence low spectral efficiency) or huge computational
complexity. In particular, whilst deterministic Sphere Decoder (SD) detection schemes are well established for static MIMO systems, exhibiting deterministic parallel structure, low computational complexity and quasi-ML detection performance, there are no corresponding adaptive schemes. This paper solves
this problem, describing a hybrid tree based adaptive modulation detection scheme. Fixed Complexity Sphere Decoding (FSD) and Real-Values FSD (RFSD) are modified and combined into a hybrid scheme exploited at low and medium SNR to provide the highest possible information rate with quasi-ML Bit Error
Rate (BER) performance, while Reduced Complexity RFSD, BChase and Decision Feedback (DFE) schemes are exploited in the high SNR regions. This algorithm provides the facility to balance the detection complexity with BER performance with compatible information rate in dynamic, adaptive MIMO communications
environments.

The Forgiving Graph: a distributed data structure for low stretch under adversarial attack

We consider the problem of self-healing in peer-to-peer networks that are under repeated attack by an omniscient adversary. We assume that, over a sequence of rounds, an adversary either inserts a node with arbitrary connections or deletes an arbitrary node from the network. The network responds to each such change by quick “repairs,” which consist of adding or deleting a small number of edges. These repairs essentially preserve closeness of nodes after adversarial deletions, without increasing node degrees by too much, in the following sense. At any point in the algorithm, nodes v and w whose distance would have been l in the graph formed by considering only the adversarial insertions (not the adversarial deletions), will be at distance at most l log n in the actual graph, where n is the total number of vertices seen so far. Similarly, at any point, a node v whose degree would have been d in the graph with adversarial insertions only, will have degree at most 3d in the actual graph. Our distributed data structure, which we call the Forgiving Graph, has low latency and bandwidth requirements. The Forgiving Graph improves on the Forgiving Tree distributed data structure from Hayes et al. (2008) in the following ways: 1) it ensures low stretch over all pairs of nodes, while the Forgiving Tree only ensures low diameter increase; 2) it handles both node insertions and deletions, while the Forgiving Tree only handles deletions; 3) it requires only a very simple and minimal initialization phase, while the Forgiving Tree initially requires construction of a spanning tree of the network.

The Forgiving Graph:A distributed data structure for low stretch under adversarial attack

We consider the problem of self-healing in peer-to-peer networks that are under repeated attack by an omniscient adversary. We assume that, over a sequence of rounds, an adversary either inserts a node with arbitrary connections or deletes an arbitrary node from the network. The network responds to each such change by quick "repairs," which consist of adding or deleting a small number of edges. These repairs essentially preserve closeness of nodes after adversarial deletions,without increasing node degrees by too much, in the following sense. At any point in the algorithm, nodes v and w whose distance would have been - in the graph formed by considering only the adversarial insertions (not the adversarial deletions), will be at distance at most - log n in the actual graph, where n is the total number of vertices seen so far. Similarly, at any point, a node v whose degreewould have been d in the graph with adversarial insertions only, will have degree at most 3d in the actual graph. Our distributed data structure, which we call the Forgiving Graph, has low latency and bandwidth requirements. The Forgiving Graph improves on the Forgiving Tree distributed data structure from Hayes et al. (2008) in the following ways: 1) it ensures low stretch over all pairs of nodes, while the Forgiving Tree only ensures low diameter increase; 2) it handles both node insertions and deletions, while the Forgiving Tree only handles deletions; 3) it requires only a very simple and minimal initialization phase, while the Forgiving Tree initially requires construction of a spanning tree of the network. © Springer-Verlag 2012.

GPCR structure, function, drug discovery and crystallography: report from Academia-Industry International Conference (UK Royal Society) Chicheley Hall, 1-2 September 2014

G-protein coupled receptors (GPCRs) are the targets of over half of all prescribed drugs today. The UniProt database has records for about 800 proteins classified as GPCRs, but drugs have only been developed against 50 of these. Thus, there is huge potential in terms of the number of targets for new therapies to be designed. Several breakthroughs in GPCRs biased pharmacology, structural biology, modelling and scoring have resulted in a resurgence of interest in GPCRs as drug targets. Therefore, an international conference, sponsored by the Royal Society, with world-renowned researchers from industry and academia was recently held to discuss recent progress and highlight key areas of future research needed to accelerate GPCR drug discovery. Several key points emerged. Firstly, structures for all three major classes of GPCRs have now been solved and there is increasing coverage across the GPCR phylogenetic tree. This is likely to be substantially enhanced with data from x-ray free electron sources as they move beyond proof of concept. Secondly, the concept of biased signalling or functional selectivity is likely to be prevalent in many GPCRs, and this presents exciting new opportunities for selectivity and the control of side effects, especially when combined with increasing data regarding allosteric modulation. Thirdly, there will almost certainly be some GPCRs that will remain difficult targets because they exhibit complex ligand dependencies and have many metastable states rendering them difficult to resolve by crystallographic methods. Subtle effects within the packing of the transmembrane helices are likely to mask and contribute to this aspect, which may play a role in species dependent behaviour. This is particularly important because it has ramifications for how we interpret pre-clinical data. In summary, collaborative efforts between industry and academia have delivered significant progress in terms of structure and understanding of GPCRs and will be essential for resolving problems associated with the more difficult targets in the future.

Extended Tree Augmented Naive Classifier

This work proposes an extended version of the well-known tree-augmented naive Bayes (TAN) classifier where the structure learning step is performed without requiring features to be connected to the class. Based on a modification of Edmonds’ algorithm, our structure learning procedure explores a superset of the structures that are considered by TAN, yet achieves global optimality of the learning score function in a very efficient way (quadratic in the number of features, the same complexity as learning TANs). A range of experiments show that we obtain models with better accuracy than TAN and comparable to the accuracy of the state-of-the-art classifier averaged one-dependence estimator.

Lack of genetic structure and evidence for long-distance dispersal in ash (Fraxinus excelsior) populations under threat from an emergent fungal pathogen: implications for restorative planting

Genetic analysis on populations of European ash (Fraxinus excelsior) throughout Ireland was carried out to determine the levels and patterns of genetic diversity in naturally seeded trees in ash woodlands and hedgerows, with the aim of informing conservation and replanting strategies in the face of potential loss of trees as a result of ash dieback. Samples from 33 sites across Northern Ireland and three sites in the Republic of Ireland were genotyped for eight nuclear and ten chloroplast microsatellites. Levels of diversity were high (mean A R = 10.53; mean H O = 0.709; mean H E = 0.765) and were similar to those in Great Britain and continental Europe, whilst levels of population genetic differentiation based on nuclear microsatellites were extremely low (Φ ST = 0.0131). Levels of inbreeding (mean F IS = 0.067) were significantly lower than those reported for populations from Great Britain. Fine-scale analysis of seed dispersal indicated potential for dispersal over hundreds of metres. Our results suggest that ash woodlands across Ireland could be treated as a single management unit, and thus native material from anywhere in Ireland could be used as a source for replanting. In addition, high potential for dispersal has implications for recolonization processes post-ash dieback (Chalara fraxinea) infection, and could aid in our assessment of the capacity of ash to shift its range in response to global climate change.

Impacts of invasive browsers on demographic rates and forest structure in New Zealand

Background/Question/Methods

Assessing the large scale impact of deer populations on forest structure and composition is important because of their increasing abundance in many temperate forests. Deer are invasive animals and sometimes thought to be responsible for immense damage to New Zealand’s forests. We report demographic changes taking place among 40 widespread indigenous tree species over 20 years, following a period of record deer numbers in the 1950s and a period of extensive hunting and depletion of deer populations during the 1960s and 1970s.

Results/Conclusions

Across a network of 578 plots there was an overall 13% reduction in sapling density of our study species with most remaining constant and a few declining dramatically. The effect of suppressed recruitment when deer populations were high was evident in the small tree size class (30 – 80 mm dbh). Stem density decreased by 15% and species with the greatest annual decreases in small tree density were those which have the highest rates of sapling recovery in exclosures indicating that deer were responsible. Densities of large canopy trees have remained relatively stable. There were imbalances between mortality and recruitment rates for 23 of the 40 species, 7 increasing and 16 in decline. These changes were again linked with sapling recovery in exclosures; species which recovered most rapidly following deer exclusion had the greatest net recruitment deficit across the wider landscape, indicating recruitment suppression by deer as opposed to mortality induced by disturbance and other herbivores. Species are not declining uniformly across all populations and no species are in decline across their entire range. Therefore we predict that with continued deer presence some forests will undergo compositional changes but that none of the species tested will become nationally extinct.

Impacts of invasive browsers on demographic rates and forest structure in New Zealand. Available from: http://www.researchgate.net/publication/267285500_Impacts_of_invasive_browsers_on_demographic_rates_and_forest_structure_in_New_Zealand [accessed Oct 9, 2015].

Learning Extended Tree Augmented Naive Structures

This work proposes an extended version of the well-known tree-augmented naive Bayes (TAN) classifier where the structure learning step is performed without requiring features to be connected to the class. Based on a modification of Edmonds' algorithm, our structure learning procedure explores a superset of the structures that are considered by TAN, yet achieves global optimality of the learning score function in a very efficient way (quadratic in the number of features, the same complexity as learning TANs). We enhance our procedure with a new score function that only takes into account arcs that are relevant to predict the class, as well as an optimization over the equivalent sample size during learning. These ideas may be useful for structure learning of Bayesian networks in general. A range of experiments shows that we obtain models with better prediction accuracy than naive Bayes and TAN, and comparable to the accuracy of the state-of-the-art classifier averaged one-dependence estimator (AODE). We release our implementation of ETAN so that it can be easily installed and run within Weka.

Learning Bounded Tree-Width Bayesian Networks via Sampling

Learning Bayesian networks with bounded tree-width has attracted much attention recently, because low tree-width allows exact inference to be performed efficiently. Some existing methods [12, 14] tackle the problem by using k-trees to learn the optimal Bayesian network with tree-width up to k. In this paper, we propose a sampling method to efficiently find representative k-trees by introducing an Informative score function to characterize the quality of a k-tree. The proposed algorithm can efficiently learn a Bayesian network with tree-width at most k. Experiment results indicate that our approach is comparable with exact methods, but is much more computationally efficient.