OpenRaiser/Intern-Atlas huggingface dataset:
A supervised clustering approach for fMRI-based inference of brain states
Venue: arXiv cs.CV 2011
Year: 2011

We propose a method that combines signals from many brain regions observed in functional Magnetic Resonance Imaging (fMRI) to predict the subject's behavior during a scanning session. Such predictions suffer from the huge number of brain regions sampled on the voxel grid of standard fMRI data sets: the curse of dimensionality. Dimensionality reduction is thus needed, but it is often performed using a univariate feature selection procedure, that handles neither the spatial structure of the images, nor the multivariate nature of the signal. By introducing a hierarchical clustering of the brain volume that incorporates connectivity constraints, we reduce the span of the possible spatial configurations to a single tree of nested regions tailored to the signal. We then prune the tree in a supervised setting, hence the name supervised clustering, in order to extract a parcellation (division of the volume) such that parcel-based signal averages best predict the target information. Dimensionality reduction is thus achieved by feature agglomeration, and the constructed features now provide a multi-scale representation of the signal. Comparisons with reference methods on both simulated and real data show that our approach yields higher prediction accuracy than standard voxel-based approaches. Moreover, the method infers an explicit weighting of the regions involved in the regression or classification task.
On Reachability for Hybrid Automata over Bounded Time
Venue: arXiv cs.LO 2011
Year: 2011

This paper investigates the time-bounded version of the reachability problem for hybrid automata. This problem asks whether a given hybrid automaton can reach a given target location within T time units, where T is a constant rational value. We show that, in contrast to the classical (unbounded) reachability problem, the timed-bounded version is decidable for rectangular hybrid automata provided only non-negative rates are allowed. This class of systems is of practical interest and subsumes, among others, the class of stopwatch automata. We also show that the problem becomes undecidable if either diagonal constraints or both negative and positive rates are allowed.
Maximum Metric Spanning Tree made Byzantine Tolerant
Venue: arXiv cs.DC 2011
Year: 2011

Self-stabilization is a versatile approach to fault-tolerance since it permits a distributed system to recover from any transient fault that arbitrarily corrupts the contents of all memories in the system. Byzantine tolerance is an attractive feature of distributed systems that permits to cope with arbitrary malicious behaviors. This paper focus on systems that are both self-stabilizing and Byzantine tolerant. We consider the well known problem of constructing a maximum metric tree in this context. Combining these two properties is known to induce many impossibility results. In this paper, we provide first two impossibility results about the construction of maximum metric tree in presence of transients and (permanent) Byzantine faults. Then, we provide a new self-stabilizing protocol that provides optimal containment of an arbitrary number of Byzantine faults.
Limits of Preprocessing
Venue: arXiv cs.AI 2011
Year: 2011

We present a first theoretical analysis of the power of polynomial-time preprocessing for important combinatorial problems from various areas in AI. We consider problems from Constraint Satisfaction, Global Constraints, Satisfiability, Nonmonotonic and Bayesian Reasoning. We show that, subject to a complexity theoretic assumption, none of the considered problems can be reduced by polynomial-time preprocessing to a problem kernel whose size is polynomial in a structural problem parameter of the input, such as induced width or backdoor size. Our results provide a firm theoretical boundary for the performance of polynomial-time preprocessing algorithms for the considered problems.
Optimal Power Control for Concurrent Transmissions of Location-aware Mobile Cognitive Radio Ad Hoc Networks
Venue: arXiv cs.IT 2011
Year: 2011

In a cognitive radio (CR) network, CR users intend to operate over the same spectrum band licensed to legacy networks. A tradeoff exists between protecting the communications in legacy networks and maximizing the throughput of CR transmissions, especially when CR links are unstable due to the mobility of CR users. Because of the non-zero probability of false detection and implementation complexity of spectrum sensing, in this paper, we investigate a sensing-free spectrum sharing scenario for mobile CR ad hoc networks to improve the frequency reuse by incorporating the location awareness capability in CR networks. We propose an optimal power control algorithm for the CR transmitter to maximize the concurrent transmission region of CR users especially in mobile scenarios. Under the proposed power control algorithm, the mobile CR network achieves maximized throughput without causing harmful interference to primary users in the legacy network. Simulation results show that the proposed optimal power control algorithm outperforms the algorithm with the fixed power policy in terms of increasing the packet delivery ratio in the network.
Impact of the Optimum Routing and Least Overhead Routing Approaches on Minimum Hop Routes and Connected Dominating Sets in Mobile Ad Hoc Networks I
Venue: arXiv cs.NI 2011
Year: 2011

Communication protocols for mobile ad hoc networks (MANETs) follow either an Optimum Routing Approach (ORA) or the Least Overhead Routing Approach (LORA): With ORA, protocols tend to determine and use the optimal communication structure at every time instant; whereas with LORA, a protocol tends to use a chosen communication structure as long as it exists. In this paper, we study the impact of the ORA and LORA strategies on minimum hop routes and minimum connected dominating sets (MCDS) in MANETs. Our primary hypothesis is that the LORA strategy could yield routes with a larger time-averaged hop count and MCDS node size when compared to the minimum hop count of routes and the node size of the MCDS determined using the ORA strategy. Our secondary hypothesis is that the impact of ORA vs. LORA also depends on how long the communication structure is being used. Our hypotheses are evaluated using extensive simulations under diverse conditions of network density, node mobility and mobility models such as the Random Waypoint model, City Section model and the Manhattan model. In the case of minimum hop routes, which exist for relatively a much longer time compared to the MCDS, the hop count of routes maintained according to LORA, even though not dramatically high, is appreciably larger (6-12%) than those maintained according to ORA; on the other hand, the number of nodes constituting a MCDS maintained according to LORA is only at most 6% larger than the node size of a MCDS maintained under the ORA strategy.
Integration of an RFID Reader to a Wireless Sensor Network and using it to Identify an Individual Carrying RFID Tags
Venue: arXiv cs.NI 2011
Year: 2011

The objective of this research is to integrate an RFID (Radio Frequency Identification) reader into a Wireless Sensor Network (WSN) to authorize or keep track of people carrying RFID tags. The objective was accomplished by integrating hardware and software. The hardware consisted of two WSN nodes - the RFID node connected to one of the WSN nodes, and a computer connected to the other WSN node. For the RFID equipment, we used the SM130-EK kit, which included the RFID reader and the RFID tags; and for the WSN, we used the Synapse Network Evaluation kit, which included the two sensor nodes. The software consisted of a program module developed in Python to control the microprocessors of the nodes; and a database controlled by a simple program to manage the tag IDs of people wearing them. The WSN and RFID nodes were connected through I2C interfacing. Also, the work of sending commands to the RFID node, to make it read a tag and send it back to the computer, was accomplished by the Python code developed which also controls the data signals. At the computer, the received tag ID is evaluated with other existing tag IDs on the database, to check if that tag has authorization or not to be in the covered area. Our research has the potential of being adapted for use with secure real-time access control applications involving WSN and RFID technologies.
An Automated Size Recognition Technique for Acetabular Implant in Total Hip Replacement
Venue: arXiv cs.CV 2011
Year: 2011

Preoperative templating in Total Hip Replacement (THR) is a method to estimate the optimal size and position of the implant. Today, observational (manual) size recognition techniques are still used to find a suitable implant for the patient. Therefore, a digital and automated technique should be developed so that the implant size recognition process can be effectively implemented. For this purpose, we have introduced the new technique for acetabular implant size recognition in THR preoperative planning based on the diameter of acetabulum size. This technique enables the surgeon to recognise a digital acetabular implant size automatically. Ten randomly selected X-rays of unidentified patients were used to test the accuracy and utility of an automated implant size recognition technique. Based on the testing result, the new technique yielded very close results to those obtained by the observational method in nine studies (90%).
Optimal Relay Power Allocation for Amplify-and-Forward Relay Networks with Non-linear Power Amplifiers
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, we propose an optimal relay power allocation of an Amplify-and-Forward relay networks with non-linear power amplifiers. Based on Bussgang Linearization Theory, we depict the non-linear amplifying process into a linear system, which lets analyzing system performance easier. To obtain spatial diversity, we design a complete practical framework of a non-linear distortion aware receiver. Consider a total relay power constraint, we propose an optimal power allocation scheme to maximum the receiver signal-to-noise ratio. Simulation results show that proposed optimal relay power allocation indeed can improve the system capacity and resist the non-linear distortion. It is also verified that the proposed transmission scheme outperforms other transmission schemes without considering non-linear distortion.
Decision Support Tools for Cloud Migration in the Enterprise
Venue: arXiv cs.DC 2011
Year: 2011

This paper describes two tools that aim to support decision making during the migration of IT systems to the cloud. The first is a modeling tool that produces cost estimates of using public IaaS clouds. The tool enables IT architects to model their applications, data and infrastructure requirements in addition to their computational resource usage patterns. The tool can be used to compare the cost of different cloud providers, deployment options and usage scenarios. The second tool is a spreadsheet that outlines the benefits and risks of using IaaS clouds from an enterprise perspective; this tool provides a starting point for risk assessment. Two case studies were used to evaluate the tools. The tools were useful as they informed decision makers about the costs, benefits and risks of using the cloud.
Optimal Function Computation in Directed and Undirected Graphs
Venue: arXiv cs.IT 2011
Year: 2011

We consider the problem of information aggregation in sensor networks, where one is interested in computing a function of the sensor measurements. We allow for block processing and study in-network function computation in directed graphs and undirected graphs. We study how the structure of the function affects the encoding strategies, and the effect of interactive information exchange. We begin by considering a directed graph G = (V, E) on the sensor nodes, where the goal is to determine the optimal encoders on each edge which achieve function computation at the collector node. Our goal is to characterize the rate region in R^{|E|}, i.e., the set of points for which there exist feasible encoders with given rates which achieve zero-error computation for asymptotically large block length. We determine the solution for directed trees, specifying the optimal encoder and decoder for each edge. For general directed acyclic graphs, we provide an outer bound on the rate region by finding the disambiguation requirements for each cut, and describe examples where this outer bound is tight. Next, we address the scenario where nodes are connected in an undirected tree network, and every node wishes to compute a given symmetric Boolean function of the sensor data. Undirected edges permit interactive computation, and we therefore study the effect of interaction on the aggregation and communication strategies. We focus on sum-threshold functions, and determine the minimum worst-case total number of bits to be exchanged on each edge. The optimal strategy involves recursive in-network aggregation which is reminiscent of message passing. In the case of general graphs, we present a cutset lower bound, and an achievable scheme based on aggregation along trees. For complete graphs, we prove that the complexity of this scheme is no more than twice that of the optimal scheme.
Splitting and Updating Hybrid Knowledge Bases (Extended Version)
Venue: arXiv cs.AI 2011
Year: 2011

Over the years, nonmonotonic rules have proven to be a very expressive and useful knowledge representation paradigm. They have recently been used to complement the expressive power of Description Logics (DLs), leading to the study of integrative formal frameworks, generally referred to as hybrid knowledge bases, where both DL axioms and rules can be used to represent knowledge. The need to use these hybrid knowledge bases in dynamic domains has called for the development of update operators, which, given the substantially different way Description Logics and rules are usually updated, has turned out to be an extremely difficult task. In [SL10], a first step towards addressing this problem was taken, and an update operator for hybrid knowledge bases was proposed. Despite its significance -- not only for being the first update operator for hybrid knowledge bases in the literature, but also because it has some applications - this operator was defined for a restricted class of problems where only the ABox was allowed to change, which considerably diminished its applicability. Many applications that use hybrid knowledge bases in dynamic scenarios require both DL axioms and rules to be updated. In this paper, motivated by real world applications, we introduce an update operator for a large class of hybrid knowledge bases where both the DL component as well as the rule component are allowed to dynamically change. We introduce splitting sequences and splitting theorem for hybrid knowledge bases, use them to define a modular update semantics, investigate its basic properties, and illustrate its use on a realistic example about cargo imports.
Using a smart phone for information rendering in Computer-Aided Surgery
Venue: arXiv cs.HC 2011
Year: 2011

Computer-aided surgery intensively uses the concept of navigation: after having collected CT data from a patient and transferred them to the operating room coordinate system, the surgical instrument (a puncture needle for instance) is localized and its position is visualized with respect to the patient organs which are not directly visible. This approach is very similar to the GPS paradigm. Traditionally, three orthogonal slices in the patient data are presented on a distant screen. Sometimes a 3D representation is also added. In this study we evaluated the potential of adding a smart phone as a man-machine interaction device. Different experiments involving operators puncturing a phantom are reported in this paper.
Voting in a Stochastic Environment: The Case of Two Groups
Venue: arXiv cs.MA 2011
Year: 2011

Social dynamics determined by voting in a stochastic environment is analyzed for a society composed of two cohesive groups of similar size. Within the model of random walks determined by voting, explicit formulas are derived for the capital increments of the groups against the parameters of the environment and "claim thresholds" of the groups. The "unanimous acceptance" and "unanimous rejection" group rules are considered as the voting procedures. Claim thresholds are evaluated that are most beneficial to the participants of the groups and to the society as a whole.
Coupled Graphical Models and Their Thresholds
Venue: arXiv cs.IT 2011
Year: 2011

The excellent performance of convolutional low-density parity-check codes is the result of the spatial coupling of individual underlying codes across a window of growing size, but much smaller than the length of the individual codes. Remarkably, the belief-propagation threshold of the coupled ensemble is boosted to the maximum-a-posteriori one of the individual system. We investigate the generality of this phenomenon beyond coding theory: we couple general graphical models into a one-dimensional chain of large individual systems. For the later we take the Curie-Weiss, random field Curie-Weiss, $K$-satisfiability, and $Q$-coloring models. We always find, based on analytical as well as numerical calculations, that the message passing thresholds of the coupled systems come very close to the static ones of the individual models. The remarkable properties of convolutional low-density parity-check codes are a manifestation of this very general phenomenon.
Chains of Mean Field Models
Venue: arXiv cs.DM 2011
Year: 2011

We consider a collection of Curie-Weiss (CW) spin systems, possibly with a random field, each of which is placed along the positions of a one-dimensional chain. The CW systems are coupled together by a Kac-type interaction in the longitudinal direction of the chain and by an infinite range interaction in the direction transverse to the chain. Our motivations for studying this model come from recent findings in the theory of error correcting codes based on spatially coupled graphs. We find that, although much simpler than the codes, the model studied here already displays similar behaviors. We are interested in the van der Waals curve in a regime where the size of each Curie-Weiss model tends to infinity, and the length of the chain and range of the Kac interaction are large but finite. Below the critical temperature, and with appropriate boundary conditions, there appears a series of equilibrium states representing kink-like interfaces between the two equilibrium states of the individual system. The van der Waals curve oscillates periodically around the Maxwell plateau. These oscillations have a period inversely proportional to the chain length and an amplitude exponentially small in the range of the interaction; in other words the spinodal points of the chain model lie exponentially close to the phase transition threshold. The amplitude of the oscillations is closely related to a Peierls-Nabarro free energy barrier for the motion of the kink along the chain. Analogies to similar phenomena and their possible algorithmic significance for graphical models of interest in coding theory and theoretical computer science are pointed out.
Considerations and Results in Multimedia and DVB Application Development on Philips Nexperia Platform
Venue: arXiv cs.CV 2011
Year: 2011

This paper presents some experiments regarding applications development on high performance media processors included in Philips Nexperia Family. The PNX1302 dedicated DVB-T kit used has some limitations. Our work has succeeded to overcome these limitations and to make possible a general-purpose use of this kit. For exemplification two typical applications, important both for multimedia and DVB, are analyzed: MPEG2 video stream decoding and MP3 audio decoding. These original implementations are compared (in speed, memory requirements and costs) with Philips Nexperia Library.
A resource analysis of the pi-calculus
Venue: arXiv cs.PL 2011
Year: 2011

We give a new treatment of the pi-calculus based on the semantic theory of separation logic, continuing a research program begun by Hoare and O'Hearn. Using a novel resource model that distinguishes between public and private ownership, we refactor the operational semantics so that sending, receiving, and allocating are commands that influence owned resources. These ideas lead naturally to two denotational models: one for safety and one for liveness. Both models are fully abstract for the corresponding observables, but more importantly both are very simple. The close connections with the model theory of separation logic (in particular, with Brookes's action trace model) give rise to a logic of processes and resources.
Pruned Continuous Haar Transform of 2D Polygonal Patterns with Application to VLSI Layouts
Venue: arXiv cs.CE 2011
Year: 2011

We introduce an algorithm for the efficient computation of the continuous Haar transform of 2D patterns that can be described by polygons. These patterns are ubiquitous in VLSI processes where they are used to describe design and mask layouts. There, speed is of paramount importance due to the magnitude of the problems to be solved and hence very fast algorithms are needed. We show that by techniques borrowed from computational geometry we are not only able to compute the continuous Haar transform directly, but also to do it quickly. This is achieved by massively pruning the transform tree and thus dramatically decreasing the computational load when the number of vertices is small, as is the case for VLSI layouts. We call this new algorithm the pruned continuous Haar transform. We implement this algorithm and show that for patterns found in VLSI layouts the proposed algorithm was in the worst case as fast as its discrete counterpart and up to 12 times faster.
DNA Circuits Based on Isothermal Constrained Loop Extension DNA Amplification
Venue: arXiv cs.ET 2011
Year: 2011

In this paper, we first describe the isothermal constrained loop extension DNA amplification (ICLEDA), which is a new variant of amplification combining the advantages of rolling circle amplification (RCA) and of strand displacement amplification (SDA). Then, we formalize this process in terms of the theory of formal languages and show, on the basis of this formulation, how to manage OR and AND gates. We then explain how to introduce negation, which allows us to prove that, in principle, it is possible to implement the computation of any boolean function on DNA strands using ICLEDA.
Management of Multiple Mobility Protocols and Tools in Dynamically Configurable Networks
Venue: arXiv cs.NI 2011
Year: 2011

Solutions for mobility management in wireless networks have been investigated and proposed in various research projects and standardization bodies. With the continuing deployment of different access networks, the wider range of applications tailored for a mobile environment, and a larger diversity of wireless end systems, it emerged that a single mobility protocol (such as Mobile IP) is not sufficient to handle the different requirements adequately. Thus a solution is needed to manage multiple mobility protocols in end systems and network nodes, to detect and select the required protocols, versions and optional features, and enable control on running daemons. For this purpose a mobility toolbox has been developed as part of the EU funded Ambient Networks project. This paper describes this modular management approach and illustrates the additional benefits a mobility protocol can gain by using state transfer as an example.