OpenRaiser/Intern-Atlas huggingface dataset:
Light-Hierarchy: The Optimal Structure for Multicast Routing in WDM Mesh Networks
Venue: arXiv cs.NI 2010
Year: 2010

Based on the false assumption that multicast incapable (MI) nodes could not be traversed twice on the same wavelength, the light-tree structure was always thought to be optimal for multicast routing in sparse splitting Wavelength Division Multiplexing (WDM) networks. In fact, for establishing a multicast session, an MI node could be crosswise visited more than once to switch a light signal towards several destinations with only one wavelength through different input and output pairs. This is called Cross Pair Switching (CPS). Thus, a new multicast routing structure light-hierarchy is proposed for all-optical multicast routing, which permits the cycles introduced by the CPS capability of MI nodes. We proved that the optimal structure for minimizing the cost of multicast routing is a set of light-hierarchies rather than the light-trees in sparse splitting WDM networks. Integer linear programming (ILP) formulations are developed to search the optimal light-hierarchies. Numerical results verified that the light-hierarchy structure could save more cost than the light-tree structure.
Molecular communication in fluid media: The additive inverse Gaussian noise channel
Venue: arXiv cs.IT 2010
Year: 2010

We consider molecular communication, with information conveyed in the time of release of molecules. The main contribution of this paper is the development of a theoretical foundation for such a communication system. Specifically, we develop the additive inverse Gaussian (IG) noise channel model: a channel in which the information is corrupted by noise with an inverse Gaussian distribution. We show that such a channel model is appropriate for molecular communication in fluid media - when propagation between transmitter and receiver is governed by Brownian motion and when there is positive drift from transmitter to receiver. Taking advantage of the available literature on the IG distribution, upper and lower bounds on channel capacity are developed, and a maximum likelihood receiver is derived. Theory and simulation results are presented which show that such a channel does not have a single quality measure analogous to signal-to-noise ratio in the AWGN channel. It is also shown that the use of multiple molecules leads to reduced error rate in a manner akin to diversity order in wireless communications. Finally, we discuss some open problems in molecular communications that arise from the IG system model.
Channel Estimation And Multiuser Detection In Asynchronous Satellite Communications
Venue: arXiv cs.NI 2010
Year: 2010

In this paper, we propose a new method of channel estimation for asynchronous additive white Gaussian noise channels in satellite communications. This method is based on signals correlation and multiuser interference cancellation which adopts a successive structure. Propagation delays and signals amplitudes are jointly estimated in order to be used for data detection at the receiver. As, a multiuser detector, a single stage successive interference cancellation (SIC) architecture is analyzed and integrated to the channel estimation technique and the whole system is evaluated. The satellite access method adopted is the direct sequence code division multiple access (DS CDMA) one. To evaluate the channel estimation and the detection technique, we have simulated a satellite uplink with an asynchronous multiuser access.
An Algorithm for the Graph Crossing Number Problem
Venue: arXiv cs.DS 2010
Year: 2010

We study the Minimum Crossing Number problem: given an $n$-vertex graph $G$, the goal is to find a drawing of $G$ in the plane with minimum number of edge crossings. This is one of the central problems in topological graph theory, that has been studied extensively over the past three decades. The first non-trivial efficient algorithm for the problem, due to Leighton and Rao, achieved an $O(n\log^4n)$-approximation for bounded degree graphs. This algorithm has since been improved by poly-logarithmic factors, with the best current approximation ratio standing on $O(n \poly(d) \log^{3/2}n)$ for graphs with maximum degree $d$. In contrast, only APX-hardness is known on the negative side. In this paper we present an efficient randomized algorithm to find a drawing of any $n$-vertex graph $G$ in the plane with $O(OPT^{10}\cdot \poly(d \log n))$ crossings, where $OPT$ is the number of crossings in the optimal solution, and $d$ is the maximum vertex degree in $G$. This result implies an $\tilde{O}(n^{9/10} \poly(d))$-approximation for Minimum Crossing Number, thus breaking the long-standing $\tilde{O}(n)$-approximation barrier for bounded-degree graphs.
Towards a Spiking Neural P Systems OS
Venue: arXiv cs.OH 2010
Year: 2010

This paper is an attempt to incorporate the idea of spiking neural P systems as an early seed into the area of Operating System Design, regarding their capability to solve some classical computer science problems. It is reflecting the power of such systems to simulate well known parallel computational models, like logic gates, arithmetic operation, and sorting. In these devices, the time (when the neurons fire and/or spike) plays an essential role. For instance, the result of a computation is the time between the moments when a specified neuron spikes. Seen as number computing devices, SN P systems are shown to be computationally complete, and with such capabilities, arithmetic operations, logic, and timing, some first steps could be taken towards an OS design.
Universal polar coding and sparse recovery
Venue: arXiv cs.IT 2010
Year: 2010

This paper investigates universal polar coding schemes. In particular, a notion of ordering (called convolutional path) is introduced between probability distributions to determine when a polar compression (or communication) scheme designed for one distribution can also succeed for another one. The original polar decoding algorithm is also generalized to an algorithm allowing to learn information about the source distribution using the idea of checkers. These tools are used to construct a universal compression algorithm for binary sources, operating at the lowest achievable rate (entropy), with low complexity and with guaranteed small error probability. In a second part of the paper, the problem of sketching high dimensional discrete signals which are sparse is approached via the polarization technique. It is shown that the number of measurements required for perfect recovery is competitive with the $O(k \log (n/k))$ bound (with optimal constant for binary signals), meanwhile affording a deterministic low complexity measurement matrix.
Some Important Aspects of Source Location Protection in Globally Attacked Sensor Networks
Venue: arXiv cs.CR 2010
Year: 2010

In the problem of location anonymity of the events exposed to a global eavesdropper, we highlight and analyze some aspects that are missing in the prior work, which is especially relevant for the quality of secure sensing in delay-intolerant applications monitoring rare and spatially sparse events, and deployed as large wireless sensor networks with single data collector. We propose an efficient scheme for generating fake network traffic to disguise the real event notification. The efficiency of the scheme that provides statistical source location anonymity is achieved by partitioning network nodes randomly into several dummy source groups. Members of the same group collectively emulate both temporal and spatial distribution of the event. Under such dummy-traffic framework of the source anonymity protection, we aim to better model the global eavesdropper, especially her way of using statistical tests to detect the real event, and to present the quality of the location protection as relative to the adversary's strength. In addition, our approach aims to reduce the per-event work spent to generate the fake traffic while, most importantly, providing a guaranteed latency in reporting the event. The latency is controlled by decoupling the routing from the fake-traffic schedule. A good dummy source group design also provides a robust protection of event bursts. This is achieved at the expense of the significant overhead as the number of dummy source groups must be increased to the reciprocal value of the false alarm parameter used in the statistical test. We believe that the proposed source anonymity protection strategy, and the evaluation framework, are well justified by the abundance of the applications that monitor a rare event with known temporal statistics, and uniform spatial distribution.
Adaptive Set Observers Design for Nonlinear Continuous-Time Systems: Application to Fault Detection and Diagnosis
Venue: arXiv cs.SY 2010
Year: 2010

The paper deals with joint state and parameter estimation for nonlinear continuous-time systems. Based on a guaranteed LPV approximation, the set adaptive observers design problem is solved avoiding the exponential complexity obstruction usually met in the set-membership parameter estimation. Potential application to fault diagnosis is considered. The efficacy of the proposed set adaptive observers is demonstrated on several examples.
Border Algorithms for Computing Hasse Diagrams of Arbitrary Lattices
Venue: arXiv cs.AI 2010
Year: 2010

The Border algorithm and the iPred algorithm find the Hasse diagrams of FCA lattices. We show that they can be generalized to arbitrary lattices. In the case of iPred, this requires the identification of a join-semilattice homomorphism into a distributive lattice.
Semantic Content Filtering with Wikipedia and Ontologies
Venue: arXiv cs.IR 2010
Year: 2010

The use of domain knowledge is generally found to improve query efficiency in content filtering applications. In particular, tangible benefits have been achieved when using knowledge-based approaches within more specialized fields, such as medical free texts or legal documents. However, the problem is that sources of domain knowledge are time-consuming to build and equally costly to maintain. As a potential remedy, recent studies on Wikipedia suggest that this large body of socially constructed knowledge can be effectively harnessed to provide not only facts but also accurate information about semantic concept-similarities. This paper describes a framework for document filtering, where Wikipedia's concept-relatedness information is combined with a domain ontology to produce semantic content classifiers. The approach is evaluated using Reuters RCV1 corpus and TREC-11 filtering task definitions. In a comparative study, the approach shows robust performance and appears to outperform content classifiers based on Support Vector Machines (SVM) and C4.5 algorithm.
Weighted random generation of context-free languages: Analysis of collisions in random urn occupancy models
Venue: arXiv cs.DS 2010
Year: 2010

The present work analyzes the redundancy of sets of combinatorial objects produced by a weighted random generation algorithm proposed by Denise et al. This scheme associates weights to the terminals symbols of a weighted context-free grammar, extends this weight definition multiplicatively on words, and draws words of length $n$ with probability proportional their weight. We investigate the level of redundancy within a sample of $k$ word, the proportion of the total probability covered by $k$ words (coverage), the time (number of generations) of the first collision, and the time of the full collection. For these four questions, we use an analytic urn analogy to derive asymptotic estimates and/or polynomially computable exact forms. We illustrate these tools by an analysis of an RNA secondary structure statistical sampling algorithm introduced by Ding et al.
Automatic Image Segmentation by Dynamic Region Merging
Venue: arXiv cs.CV 2010
Year: 2010

This paper addresses the automatic image segmentation problem in a region merging style. With an initially over-segmented image, in which the many regions (or super-pixels) with homogeneous color are detected, image segmentation is performed by iteratively merging the regions according to a statistical test. There are two essential issues in a region merging algorithm: order of merging and the stopping criterion. In the proposed algorithm, these two issues are solved by a novel predicate, which is defined by the sequential probability ratio test (SPRT) and the maximum likelihood criterion. Starting from an over-segmented image, neighboring regions are progressively merged if there is an evidence for merging according to this predicate. We show that the merging order follows the principle of dynamic programming. This formulates image segmentation as an inference problem, where the final segmentation is established based on the observed image. We also prove that the produced segmentation satisfies certain global properties. In addition, a faster algorithm is developed to accelerate the region merging process, which maintains a nearest neighbor graph in each iteration. Experiments on real natural images are conducted to demonstrate the performance of the proposed dynamic region merging algorithm.
Construction of $μ$-Limit Sets
Venue: arXiv cs.DM 2010
Year: 2010

The $μ$-limit set of a cellular automaton is a subshift whose forbidden patterns are exactly those, whose probabilities tend to zero as time tends to in- finity. In this article, for a given subshift in a large class of subshifts, we propose the construction of a cellular automaton which realizes this subshift as $μ$-limit set where $μ$ is the uniform Bernoulli measure.
Building conceptual spaces for exploring and linking biomedical resources
Venue: arXiv cs.IR 2010
Year: 2010

The establishment of links between data (e.g., patient records) and Web resources (e.g., literature) and the proper visualization of such discovered knowledge is still a challenge in most Life Science domains (e.g., biomedicine). In this paper we present our contribution to the community in the form of an infrastructure to annotate information resources, to discover relationships among them, and to represent and visualize the new discovered knowledge. Furthermore, we have also implemented a Web-based prototype tool which integrates the proposed infrastructure.
Argudas: arguing with gene expression information
Venue: arXiv cs.CE 2010
Year: 2010

In situ hybridisation gene expression information helps biologists identify where a gene is expressed. However, the databases that republish the experimental information are often both incomplete and inconsistent. This paper examines a system, Argudas, designed to help tackle these issues. Argudas is an evolution of an existing system, and so that system is reviewed as a means of both explaining and justifying the behaviour of Argudas. Throughout the discussion of Argudas a number of issues will be raised including the appropriateness of argumentation in biology and the challenges faced when integrating apparently similar online biological databases.
YeastMed: an XML-Based System for Biological Data Integration of Yeast
Venue: arXiv cs.DB 2010
Year: 2010

A key goal of bioinformatics is to create database systems and software platforms capable of storing and analysing large sets of biological data. Hundreds of biological databases are now available and provide access to huge amount of biological data. SGD, Yeastract, CYGD-MIPS, BioGrid and PhosphoGrid are five of the most visited databases by the yeast community. These sources provide complementary data on biological entities. Biologists are brought systematically to query these data sources in order to analyse the results of their experiments. Because of the heterogeneity of these sources, querying them separately and then manually combining the returned result is a complex and laborious task. To provide transparent and simultaneous access to these sources, we have developed a mediator-based system called YeastMed. In this paper, we present YeastMed focusing on its architecture.
A study on the relation between linguistics-oriented and domain-specific semantics
Venue: arXiv cs.AI 2010
Year: 2010

In this paper we dealt with the comparison and linking between lexical resources with domain knowledge provided by ontologies. It is one of the issues for the combination of the Semantic Web Ontologies and Text Mining. We investigated the relations between the linguistics oriented and domain-specific semantics, by associating the GO biological process concepts to the FrameNet semantic frames. The result shows the gaps between the linguistics-oriented and domain-specific semantics on the classification of events and the grouping of target words. The result provides valuable information for the improvement of domain ontologies supporting for text mining systems. And also, it will result in benefits to language understanding technology.
Ontology and Knowledge Management System on Epilepsy and Epileptic Seizures
Venue: arXiv cs.DL 2010
Year: 2010

A Knowledge Management System developed for supporting creation, capture, storage and dissemination of information about Epilepsy and Epileptic Seizures is presented. We present an Ontology on Epilepsy and a Web-based prototype that together create the KMS.
Constraint-Guided Workflow Composition Based on the EDAM Ontology
Venue: arXiv cs.SE 2010
Year: 2010

Methods for the automatic composition of services into executable workflows need detailed knowledge about the application domain,in particular about the available services and their behavior in terms of input/output data descriptions. In this paper we discuss how the EMBRACE data and methods ontology (EDAM) can be used as background knowledge for the composition of bioinformatics workflows. We show by means of a small example domain that the EDAM knowledge facilitates finding possible workflows, but that additional knowledge is required to guide the search towards actually adequate solutions. We illustrate how the ability to flexibly formulate domain-specific and problem-specific constraints supports the work ow development process.
The CALBC RDF Triple Store: retrieval over large literature content
Venue: arXiv cs.DL 2010
Year: 2010

Integration of the scientific literature into a biomedical research infrastructure requires the processing of the literature, identification of the contained named entities (NEs) and concepts, and to represent the content in a standardised way. The CALBC project partners (PPs) have produced a large-scale annotated biomedical corpus with four different semantic groups through the harmonisation of annotations from automatic text mining solutions (Silver Standard Corpus, SSC). The four semantic groups were chemical entities and drugs (CHED), genes and proteins (PRGE), diseases and disorders (DISO) and species (SPE). The content of the SSC has been fully integrated into RDF Triple Store (4,568,678 triples) and has been aligned with content from the GeneAtlas (182,840 triples), UniProtKb (12,552,239 triples for human) and the lexical resource LexEBI (BioLexicon). RDF Triple Store enables querying the scientific literature and bioinformatics resources at the same time for evidence of genetic causes, such as drug targets and disease involvement.
Using Semantic Wikis for Structured Argument in Medical Domain
Venue: arXiv cs.AI 2010
Year: 2010

This research applies ideas from argumentation theory in the context of semantic wikis, aiming to provide support for structured-large scale argumentation between human agents. The implemented prototype is exemplified by modelling the MMR vaccine controversy.
First steps in the logic-based assessment of post-composed phenotypic descriptions
Venue: arXiv cs.AI 2010
Year: 2010

In this paper we present a preliminary logic-based evaluation of the integration of post-composed phenotypic descriptions with domain ontologies. The evaluation has been performed using a description logic reasoner together with scalable techniques: ontology modularization and approximations of the logical difference between ontologies.
Localizing Audiences' Gaze using a Multi-touch Electronic Whiteboard with sPieMenu
Venue: arXiv cs.HC 2010
Year: 2010

Direct-touch presentation devices such as touch-sensitive electronic whiteboards have two serious problems. First, the presenter's hand movements tend to distract the audience's attention from content. Second, the presenter' s manipulation tends to obscure content. In this paper we describe a new electronic whiteboard system that supports multi-touch gestures and employs a special pie menu interface named "sPieMenu." This pie menu is displayed under the presenter's palm and is thus invisible to the audience. A series of experiments shows that the proposed system allows both novice and expert users to efficiently manipulate the electronic whiteboard, and that the proposed system decreases distraction to the audience compared to traditional approaches.
Designing Incentive Schemes Based on Intervention: The Case of Imperfect Monitoring
Venue: arXiv cs.GT 2010
Year: 2010

We propose an incentive scheme based on intervention to sustain cooperation among self-interested users. In the proposed scheme, an intervention device collects imperfect signals about the actions of the users for a test period, and then chooses the level of intervention that degrades the performance of the network for the remaining time period. We analyze the problems of designing an optimal intervention rule given a test period and choosing an optimal length of the test period. The intervention device can provide the incentive for cooperation by exerting intervention following signals that involve a high likelihood of deviation. Increasing the length of the test period has two counteracting effects on the performance: It improves the quality of signals, but at the same time it weakens the incentive for cooperation due to increased delay.
Single-Producer/Single-Consumer Queues on Shared Cache Multi-Core Systems
Venue: arXiv cs.DS 2010
Year: 2010

Using efficient point-to-point communication channels is critical for implementing fine grained parallel program on modern shared cache multi-core architectures. This report discusses in detail several implementations of wait-free Single-Producer/Single-Consumer queue (SPSC), and presents a novel and efficient algorithm for the implementation of an unbounded wait-free SPSC queue (uSPSC). The correctness proof of the new algorithm, and several performance measurements based on simple synthetic benchmark and microbenchmark, are also discussed.
On Transmit Antenna Selection for Multiuser MIMO Systems with Dirty Paper Coding
Venue: arXiv cs.IT 2010
Year: 2010

In this paper, we address the transmit antenna selection in multi-user MIMO systems with precoding. The optimum and reduced complexity sub-optimum antenna selection algorithms are introduced. QR-decomposition (QRD) based antenna selection is investigated and the reason behind its sub-optimality is analytically derived. We introduce the conventional QRD-based algorithm and propose an efficient QRD-based transmit antenna scheme (maxR) that is both implementation and performance efficient. Moreover, we derive explicit formulae for the computational complexities of the aforementioned algorithms. Simulation results and analysis demonstrate that the proposed maxR algorithm requires only 1% of the computational efforts required by the optimal algorithm for a degradation of 1dB and 0.1dB in the case of linear zero-forcing and Tomlinson-Harashima precoding schemes, respectively.
Comparative Analysis of Existing Methods and Algorithms for Automatic Assignment of Reviewers to Papers
Venue: arXiv cs.DL 2010
Year: 2010

The article focuses on the importance of the automatic assignment of reviewers to papers for increasing the assignment accuracy therefore the quality of the scientific event itself. It discusses the main aspects that influence the assignment accuracy, performs a detailed analysis of the methods of describing papers and reviewers' competences used by the existing conference management systems and suggests some improvements in the way the similarity factors are calculated.