OpenRaiser/Intern-Atlas huggingface dataset:
A neural circuit for navigation inspired by C. elegans Chemotaxis
Venue: arXiv cs.NE 2014
Year: 2014

We develop an artificial neural circuit for contour tracking and navigation inspired by the chemotaxis of the nematode Caenorhabditis elegans. In order to harness the computational advantages spiking neural networks promise over their non-spiking counterparts, we develop a network comprising 7-spiking neurons with non-plastic synapses which we show is extremely robust in tracking a range of concentrations. Our worm uses information regarding local temporal gradients in sodium chloride concentration to decide the instantaneous path for foraging, exploration and tracking. A key neuron pair in the C. elegans chemotaxis network is the ASEL & ASER neuron pair, which capture the gradient of concentration sensed by the worm in their graded membrane potentials. The primary sensory neurons for our network are a pair of artificial spiking neurons that function as gradient detectors whose design is adapted from a computational model of the ASE neuron pair in C. elegans. Simulations show that our worm is able to detect the set-point with approximately four times higher probability than the optimal memoryless Levy foraging model. We also show that our spiking neural network is much more efficient and noise-resilient while navigating and tracking a contour, as compared to an equivalent non-spiking network. We demonstrate that our model is extremely robust to noise and with slight modifications can be used for other practical applications such as obstacle avoidance. Our network model could also be extended for use in three-dimensional contour tracking or obstacle avoidance.
Health Information Search Behavior on the Web: A Pilot Study
Venue: arXiv cs.IR 2014
Year: 2014

Searching health information on web has become an integral part of today's world, and many people turn to the Web for healthcare information and healthcare assessment. Our pilot study investigates users' preferences for the type of search results (image, news, video, etc.), and investigates users' ability to accurately interpret online health information for the purpose of self diagnosis. The preliminary results reveal that blog and news articles are most sought by users when searching online information and there exist challenges in the use of online health information for self-diagnosis.
On finding orientations with fewest number of vartices with small out-degree
Venue: arXiv cs.DM 2014
Year: 2014

Given an undirected graph, each of the two end-vertices of an edge can own the edge. Call a vertex poor, if it owns at most one edge. We give a polynomial time algorithm for the problem of finding an assignment of owners to the edges which minimizes the number of poor vertices. In the terminology of graph orientation, this means finding an orientation for the edges of a graph minimizing the number of edges with out-degree at most 1, and answers a question of Asahiro Jansson, Miyano, Ono (2014).
Randomized Rumor Spreading in Poorly Connected Small-World Networks
Venue: arXiv cs.SI 2014
Year: 2014

Push-Pull is a well-studied round-robin rumor spreading protocol defined as follows: initially a node knows a rumor and wants to spread it to all nodes in a network quickly. In each round, every informed node sends the rumor to a random neighbor, and every uninformed node contacts a random neighbor and gets the rumor from her if she knows it. We analyze this protocol on random $k$-trees, a class of power law graphs, which are small-world and have large clustering coefficients, built as follows: initially we have a $k$-clique. In every step a new node is born, a random $k$-clique of the current graph is chosen, and the new node is joined to all nodes of the $k$-clique. When $k>1$ is fixed, we show that if initially a random node is aware of the rumor, then with probability $1-o(1)$ after $O\left((\log n)^{1+2/k}\cdot\log\log n\cdot f(n)\right)$ rounds the rumor propagates to $n-o(n)$ nodes, where $n$ is the number of nodes and $f(n)$ is any slowly growing function. Since these graphs have polynomially small conductance, vertex expansion $O(1/n)$ and constant treewidth, these results demonstrate that Push-Pull can be efficient even on poorly connected networks. On the negative side, we prove that with probability $1-o(1)$ the protocol needs at least $Ω\left(n^{(k-1)/(k^2+k-1)}/f^2(n)\right)$ rounds to inform all nodes. This exponential dichotomy between time required for informing almost all and all nodes is striking. Our main contribution is to present, for the first time, a natural class of random graphs in which such a phenomenon can be observed. Our technique for proving the upper bound carries over to a closely related class of graphs, random $k$-Apollonian networks, for which we prove an upper bound of $O\left((\log n)^{c_k}\cdot\log\log n\cdot f(n)\right)$ rounds for informing $n-o(n)$ nodes with probability $1-o(1)$ when $k>2$ is fixed. Here, $c_k=(k^2-3)/(k-1)^2<1 + 2/k$.
Team size matters: Collaboration and scientific impact since 1900
Venue: arXiv cs.DL 2014
Year: 2014

This paper provides the first historical analysis of the relationship between collaboration and scientific impact, using three indicators of collaboration (number of authors, number of addresses, and number of countries) and including articles published between 1900 and 2011. The results demonstrate that an increase in the number of authors leads to an increase in impact--from the beginning of the last century onwards--and that this is not simply due to self-citations. A similar trend is also observed for the number of addresses and number of countries represented in the byline of an article. However, the constant inflation of collaboration since 1900 has resulted in diminishing citation returns: larger and more diverse (in terms of institutional and country affiliation) teams are necessary to realize higher impact. The paper concludes with a discussion of the potential causes of the impact gain in citations of collaborative papers.
An ensemble-based system for automatic screening of diabetic retinopathy
Venue: arXiv cs.CV 2014
Year: 2014

In this paper, an ensemble-based method for the screening of diabetic retinopathy (DR) is proposed. This approach is based on features extracted from the output of several retinal image processing algorithms, such as image-level (quality assessment, pre-screening, AM/FM), lesion-specific (microaneurysms, exudates) and anatomical (macula, optic disc) components. The actual decision about the presence of the disease is then made by an ensemble of machine learning classifiers. We have tested our approach on the publicly available Messidor database, where 90% sensitivity, 91% specificity and 90% accuracy and 0.989 AUC are achieved in a disease/no-disease setting. These results are highly competitive in this field and suggest that retinal image processing is a valid approach for automatic DR screening.
Semi-Automatic Construction of a Domain Ontology for Wind Energy Using Wikipedia Articles
Venue: arXiv cs.CL 2014
Year: 2014

Domain ontologies are important information sources for knowledge-based systems. Yet, building domain ontologies from scratch is known to be a very labor-intensive process. In this study, we present our semi-automatic approach to building an ontology for the domain of wind energy which is an important type of renewable energy with a growing share in electricity generation all over the world. Related Wikipedia articles are first processed in an automated manner to determine the basic concepts of the domain together with their properties and next the concepts, properties, and relationships are organized to arrive at the ultimate ontology. We also provide pointers to other engineering ontologies which could be utilized together with the proposed wind energy ontology in addition to its prospective application areas. The current study is significant as, to the best of our knowledge, it proposes the first considerably wide-coverage ontology for the wind energy domain and the ontology is built through a semi-automatic process which makes use of the related Web resources, thereby reducing the overall cost of the ontology building process.
Data Driven Prognosis: A multi-physics approach verified via balloon burst experiment
Venue: arXiv cs.CE 2014
Year: 2014

A multi-physics formulation for Data Driven Prognosis (DDP) is developed. Unlike traditional predictive strategies that require controlled off-line measurements or training for determination of constitutive parameters to derive the transitional statistics, the proposed DDP algorithm relies solely on in situ measurements. It utilizes a deterministic mechanics framework, but the stochastic nature of the solution arises naturally from the underlying assumptions regarding the order of the conservation potential as well as the number of dimensions involved. The proposed DDP scheme is capable of predicting onset of instabilities. Since the need for off-line testing (or training) is obviated, it can be easily implemented for systems where such a priori testing is difficult or even impossible to conduct. The prognosis capability is demonstrated here via a balloon burst experiment where the instability is predicted utilizing only on-line visual observations. The DDP scheme never failed to predict the incipient failure, and no false positives were issued. The DDP algorithm is applicable to others types of datasets. Time horizons of DDP predictions can be adjusted by using memory over different time windows. Thus, a big dataset can be parsed in time to make a range of predictions over varying time horizons.
Communication-Free Multi-Agent Control under Local Temporal Tasks and Relative-Distance Constraints
Venue: arXiv cs.MA 2014
Year: 2014

We propose a distributed control and coordination strategy for multi-agent systems where each agent has a local task specified as a Linear Temporal Logic (LTL) formula and at the same time is subject to relative-distance constraints with its neighboring agents. The local tasks capture the temporal requirements on individual agents' behaviors, while the relative-distance constraints impose requirements on the collective motion of the whole team. The proposed solution relies only on relative-state measurements among the neighboring agents without the need for explicit information exchange. It is guaranteed that the local tasks given as syntactically co-safe or general LTL formulas are fulfilled and the relative-distance constraints are satisfied at all time. The approach is demonstrated with computer simulations.
Lattice polytopes in coding theory
Venue: arXiv cs.IT 2014
Year: 2014

In this paper we discuss combinatorial questions about lattice polytopes motivated by recent results on minimum distance estimation for toric codes. We also prove a new inductive bound for the minimum distance of generalized toric codes. As an application, we give new formulas for the minimum distance of generalized toric codes for special lattice point configurations.
Cognitive image processing: the time is right to recognize that the world does not rest more on turtles and elephants
Venue: arXiv cs.CY 2014
Year: 2014

Traditional image processing is a field of science and technology developed to facilitate human-centered image management. But today, when huge volumes of visual data inundate our surroundings (due to the explosive growth of image-capturing devices, proliferation of Internet communication means and video sharing services over the World Wide Web), human-centered handling of Big-data flows is impossible anymore. Therefore, it has to be replaced with a machine (computer) supported counterpart. Of course, such an artificial counterpart must be equipped with some cognitive abilities, usually characteristic for a human being. Indeed, in the past decade, a new computer design trend - Cognitive Computer development - is become visible. Cognitive image processing definitely will be one of its main duties. It must be specially mentioned that this trend is a particular case of a much more general movement - the transition from a "computational data-processing paradigm" to a "cognitive information-processing paradigm", which affects today many fields of science, technology, and engineering. This transition is a blessed novelty, but its success is hampered by the lack of a clear delimitation between the notion of data and the notion of information. Elaborating the case of cognitive image processing, the paper intends to clarify these important research issues.
ALID: Scalable Dominant Cluster Detection
Venue: arXiv cs.DB 2014
Year: 2014

Detecting dominant clusters is important in many analytic applications. The state-of-the-art methods find dense subgraphs on the affinity graph as the dominant clusters. However, the time and space complexity of those methods are dominated by the construction of the affinity graph, which is quadratic with respect to the number of data points, and thus impractical on large data sets. To tackle the challenge, in this paper, we apply Evolutionary Game Theory (EGT) and develop a scalable algorithm, Approximate Localized Infection Immunization Dynamics (ALID). The major idea is to perform Localized Infection Immunization Dynamics (LID) to find dense subgraph within local range of the affinity graph. LID is further scaled up with guaranteed high efficiency and detection quality by an estimated Region of Interest (ROI) and a carefully designed Candidate Infective Vertex Search method (CIVS). ALID only constructs small local affinity graphs and has a time complexity of O(C(a^*+ δ)n) and a space complexity of O(a^*(a^*+ δ)), where a^* is the size of the largest dominant cluster and C << n and δ << n are small constants. We demonstrate by extensive experiments on both synthetic data and real world data that ALID achieves state-of-the-art detection quality with much lower time and space cost on single machine. We also demonstrate the encouraging parallelization performance of ALID by implementing the Parallel ALID (PALID) on Apache Spark. PALID processes 50 million SIFT data points in 2.29 hours, achieving a speedup ratio of 7.51 with 8 executors.
Outage Analysis of Multi-Relay Selection for Cognitive Radio with Imperfect Spectrum Sensing
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we examine the outage performance of a cognitive relay network, which is comprised of a secondary transmitter (ST), multiple decode-and-forward (DF) relays and a secondary destination (SD). We propose a multi-relay selection scheme for the cognitive relay network, where multiple relays are selected and used to participate in forwarding the secondary transmission from ST to SD. A closed-form expression of the outage probability for the proposed multi-relay selection under imperfect spectrum sensing is derived in Rayleigh fading environments. For comparison purposes, the conventional direct transmission and the best-relay selection are also considered as benchmarks. Numerical results show that as the spectrum sensing performance improves with an increasing detection probability and/or a decreasing false alarm probability, the outage probabilities of the proposed multi-relay selection as well as the direct transmission and the best-relay selection schemes all decrease accordingly. It is also demonstrated that the proposed multi-relay selection significantly outperforms the conventional approaches in terms of the outage probability.
SALT. A unified framework for all shortest-path query variants on road networks
Venue: arXiv cs.DS 2014
Year: 2014

Although recent scientific output focuses on multiple shortest-path problem definitions for road networks, none of the existing solutions does efficiently answer all different types of SP queries. This work proposes SALT, a novel framework that not only efficiently answers SP related queries but also k-nearest neighbor queries not handled by previous approaches. Our solution offers all the benefits needed for practical use-cases, including excellent query performance and very short preprocessing times, thus making it also a viable option for dynamic road networks, i.e., edge weights changing frequently due to traffic updates. The proposed SALT framework is a deployable software solution capturing a range of network-related query problems under one "algorithmic hood".
Synthesis from Formal Partial Abstractions
Venue: arXiv cs.SE 2014
Year: 2014

Developing complex software systems is costly, time-consuming and error-prone. Model- driven development (MDD) promises to improve software productivity, timeliness, quality and cost through the transformation of abstract application models to code-level implementations. However, it remains unreasonably difficult to build the modeling languages and translators required for software synthesis. This difficulty, in turns, limits the applicability of MDD, and makes it hard to achieve reliability in MDD tools. This dissertation research seeks to reduce the cost, broaden the applicability, and increase the quality of model-driven development systems by embedding modeling languages within established formal languages and by using the analyzers provided with such languages for synthesis purposes to reduce the need for hand coding of translators. This dissertation, in particular, explores the proposed approach using relational logic as expressed in Alloy as the general specification language, and the Alloy Analyzer as the general-purpose analyzer. Synthesis is thus driven by finite-domain constraint satisfaction. One important aspect of this work is its focus on partial specifications of particular aspects of the system, such as application architectures and target platforms, and synthesis of partial code bases from such specifications. Contributions of this work include novel insights, methods and tools for (1) synthesizing architectural models from abstract application models; (2) synthesizing partial, platform-specific application frameworks from application architectures; and (3) synthesizing object-relational mapping tradeoff spaces and database schemas for database-backed object-oriented applications.
Distributed Community Detection with the WCC Metric
Venue: arXiv cs.SI 2014
Year: 2014

Community detection has become an extremely active area of research in recent years, with researchers proposing various new metrics and algorithms to address the problem. Recently, the Weighted Community Clustering (WCC) metric was proposed as a novel way to judge the quality of a community partitioning based on the distribution of triangles in the graph, and was demonstrated to yield superior results over other commonly used metrics like modularity. The same authors later presented a parallel algorithm for optimizing WCC on large graphs. In this paper, we propose a new distributed, vertex-centric algorithm for community detection using the WCC metric. Results are presented that demonstrate the algorithm's performance and scalability on up to 32 worker machines and real graphs of up to 1.8 billion vertices. The algorithm scales best with the largest graphs, and to our knowledge, it is the first distributed algorithm for optimizing the WCC metric.
On Detecting Noun-Adjective Agreement Errors in Bulgarian Language Using GATE
Venue: arXiv cs.CL 2014
Year: 2014

In this article, we describe an approach for automatic detection of noun-adjective agreement errors in Bulgarian texts by explaining the necessary steps required to develop a simple Java-based language processing application. For this purpose, we use the GATE language processing framework, which is capable of analyzing texts in Bulgarian language and can be embedded in software applications, accessed through a set of Java APIs. In our example application we also demonstrate how to use the functionality of GATE to perform regular expressions over annotations for detecting agreement errors in simple noun phrases formed by two words - attributive adjective and a noun, where the attributive adjective precedes the noun. The provided code samples can also be used as a starting point for implementing natural language processing functionalities in software applications related to language processing tasks like detection, annotation and retrieval of word groups meeting a specific set of criteria.
Clustering memes in social media streams
Venue: arXiv cs.SI 2014
Year: 2014

The problem of clustering content in social media has pervasive applications, including the identification of discussion topics, event detection, and content recommendation. Here we describe a streaming framework for online detection and clustering of memes in social media, specifically Twitter. A pre-clustering procedure, namely protomeme detection, first isolates atomic tokens of information carried by the tweets. Protomemes are thereafter aggregated, based on multiple similarity measures, to obtain memes as cohesive groups of tweets reflecting actual concepts or topics of discussion. The clustering algorithm takes into account various dimensions of the data and metadata, including natural language, the social network, and the patterns of information diffusion. As a result, our system can build clusters of semantically, structurally, and topically related tweets. The clustering process is based on a variant of Online K-means that incorporates a memory mechanism, used to "forget" old memes and replace them over time with the new ones. The evaluation of our framework is carried out by using a dataset of Twitter trending topics. Over a one-week period, we systematically determined whether our algorithm was able to recover the trending hashtags. We show that the proposed method outperforms baseline algorithms that only use content features, as well as a state-of-the-art event detection method that assumes full knowledge of the underlying follower network. We finally show that our online learning framework is flexible, due to its independence of the adopted clustering algorithm, and best suited to work in a streaming scenario.
An Intuitive Procedure for Converting PDA to CFG, by Construction of Single State PDA
Venue: arXiv cs.FL 2014
Year: 2014

We present here the proof for an alternative procedure to convert a Push Down Automata (PDA) into a Context Free Grammar (CFG). The procedure involves intermediate conversion to a single state PDA. In view of the authors, this conversion is conceptually intuitive and can serve as a teaching aid for the relevant topics.
NP-hardness of hypercube 2-segmentation
Venue: arXiv cs.CC 2014
Year: 2014

The hypercube 2-segmentation problem is a certain biclustering problem that was previously claimed to be NP-hard, but for which there does not appear to be a publicly available proof of NP-hardness. This manuscript provides such a proof.
Variations on the Stochastic Shortest Path Problem
Venue: arXiv cs.LO 2014
Year: 2014

In this invited contribution, we revisit the stochastic shortest path problem, and show how recent results allow one to improve over the classical solutions: we present algorithms to synthesize strategies with multiple guarantees on the distribution of the length of paths reaching a given target, rather than simply minimizing its expected value. The concepts and algorithms that we propose here are applications of more general results that have been obtained recently for Markov decision processes and that are described in a series of recent papers.