OpenRaiser/Intern-Atlas huggingface dataset:
Sampling node group structure of social and information networks
Venue: arXiv cs.SI 2014
Year: 2014

Lately, network sampling proved as a promising tool for simplifying large real-world networks and thus providing for their faster and more efficient analysis. Still, understanding the changes of network structure and properties under different sampling methods remains incomplete. In this paper, we analyze the presence of characteristic group of nodes (i.e., communities, modules and mixtures of the two) in social and information networks. Moreover, we observe the changes of node group structure under two sampling methods, random node selection based on degree and breadth-first sampling. We show that the sampled information networks contain larger number of mixtures than original networks, while the structure of sampled social networks exhibits stronger characterization by communities. The results also reveal there exist no significant differences in the behavior of both sampling methods. Accordingly, the selection of sampling method impact on the changes of node group structure to a much smaller extent that the type and the structure of analyzed network.
Computer-Aided Proof of Erdos Discrepancy Properties
Venue: arXiv cs.DM 2014
Year: 2014

In 1930s Paul Erdos conjectured that for any positive integer $C$ in any infinite $\pm 1$ sequence $(x_n)$ there exists a subsequence $x_d, x_{2d}, x_{3d},\dots, x_{kd}$, for some positive integers $k$ and $d$, such that $\mid \sum_{i=1}^k x_{i\cdot d} \mid >C$. The conjecture has been referred to as one of the major open problems in combinatorial number theory and discrepancy theory. For the particular case of $C=1$ a human proof of the conjecture exists; for $C=2$ a bespoke computer program had generated sequences of length $1124$ of discrepancy $2$, but the status of the conjecture remained open even for such a small bound. We show that by encoding the problem into Boolean satisfiability and applying the state of the art SAT solvers, one can obtain a discrepancy $2$ sequence of length $1160$ and a proof of the Erdős discrepancy conjecture for $C=2$, claiming that no discrepancy 2 sequence of length $1161$, or more, exists. In the similar way, we obtain a precise bound of $127\,645$ on the maximal lengths of both multiplicative and completely multiplicative sequences of discrepancy $3$. We also demonstrate that unrestricted discrepancy 3 sequences can be longer than $130\,000$.
The "crisis of noosphere" as a limiting factor to achieve the point of technological singularity
Venue: arXiv cs.CY 2014
Year: 2014

One of the most significant developments in the history of human being is the invention of a way of keeping records of human knowledge, thoughts and ideas. In 1926, the work of several thinkers such as Edouard Le Roy, Vladimir Vernadsky and Teilhard de Chardin led to the concept of noosphere, thus the idea that human cognition and knowledge transforms the biosphere coming to be something like the planet's thinking layer. At present, is commonly accepted by some thinkers that the Internet is the medium that brings life to noosphere. According to Vinge and Kurzweil's technological singularity hypothesis, noosphere would be in the future the natural environment in which 'human-machine superintelligence' emerges after to reach the point of technological singularity. In this paper we show by means of a numerical model the impossibility that our civilization reaches the point of technological singularity in the near future. We propose that this point may be reached when Internet data centers are based on "computer machines" to be more effective in terms of power consumption than current ones. We speculate about what we have called 'Nooscomputer' or N-computer a hypothetical machine which would consume far less power allowing our civilization to reach the point of technological singularity.
Large Universe Attribute-Based Encryption Scheme from Lattices
Venue: arXiv cs.CR 2014
Year: 2014

We propose a large universe attribute-based encryption (ABE ) scheme from lattices. It is inspired by Brent Waters' scheme which is a large universe attribute-based encryption using bilinear map. It is a very practical scheme but this scheme may not be security with the developing quantum computer. So we extend their good idea of large universe attribute-based encryption to lattices based cryptosystem. And our scheme is the first large universe ABE scheme from lattices. In a large universe ABE system any string can be used as attribute and attributes need not be determined at system setup. This is a desirable feature. And the master private key of our scheme is too short too a matrix. Moreover, our scheme is high efficient due to the ciphertext of our scheme is divided into three parts. Finally, under Learning with Errors assumption, we prove our scheme is secure under the select attribute attack.
Efficient classification using parallel and scalable compressed model and Its application on intrusion detection
Venue: arXiv cs.LG 2014
Year: 2014

In order to achieve high efficiency of classification in intrusion detection, a compressed model is proposed in this paper which combines horizontal compression with vertical compression. OneR is utilized as horizontal com-pression for attribute reduction, and affinity propagation is employed as vertical compression to select small representative exemplars from large training data. As to be able to computationally compress the larger volume of training data with scalability, MapReduce based parallelization approach is then implemented and evaluated for each step of the model compression process abovementioned, on which common but efficient classification methods can be directly used. Experimental application study on two publicly available datasets of intrusion detection, KDD99 and CMDC2012, demonstrates that the classification using the compressed model proposed can effectively speed up the detection procedure at up to 184 times, most importantly at the cost of a minimal accuracy difference with less than 1% on average.
The Geometry of Synchronization (Long Version)
Venue: arXiv cs.LO 2014
Year: 2014

We graft synchronization onto Girard's Geometry of Interaction in its most concrete form, namely token machines. This is realized by introducing proof-nets for SMLL, an extension of multiplicative linear logic with a specific construct modeling synchronization points, and of a multi-token abstract machine model for it. Interestingly, the correctness criterion ensures the absence of deadlocks along reduction and in the underlying machine, this way linking logical and operational properties.
Developing Corpus-based Translation Methods between Informal and Formal Mathematics: Project Description
Venue: arXiv cs.AI 2014
Year: 2014

The goal of this project is to (i) accumulate annotated informal/formal mathematical corpora suitable for training semi-automated translation between informal and formal mathematics by statistical machine-translation methods, (ii) to develop such methods oriented at the formalization task, and in particular (iii) to combine such methods with learning-assisted automated reasoning that will serve as a strong semantic component. We describe these ideas, the initial set of corpora, and some initial experiments done over them.
Current Concepts in Version Control Systems
Venue: arXiv cs.SE 2014
Year: 2014

We give the reader a comprehensive overview of the state of the Version Control software engineering field, describing and analysing the concepts, architectural approaches and methods researched and included in the currently widely used version control systems and propose some possible future research directions.
Secure Data Transmission in Cooperative Modes: Relay and MAC
Venue: arXiv cs.IT 2014
Year: 2014

Cooperation in clouds provides a promising technique for 5G wireless networks, supporting higher data rates. Security of data transmission over wireless clouds could put constraints on devices; whether to cooperate or not. Therefore, our aim is to provide analytical framework for the security on the physical layer of such setup and to define the constraints embodied with cooperation in small size wireless clouds. In this paper, two legitimate transmitters Alice and John cooperate to increase the reliable transmission rate received by their common legitimate receiver Bob, where one eavesdropper, Eve exists. We provide the achievable secure data transmission rates with cooperative relaying and when no cooperation exists creating a Multiple Access Channel (MAC). The paper considers the analysis of different cooperative scenarios: a cooperative scenario with two relaying devices, a cooperative scenario without relaying, a non-cooperative scenario, and cooperation from one side. We derive analytical expressions for the optimal power allocation that maximizes the achievable secrecy rates for the different set of scenarios where the implication of cooperation on the achievable secrecy rates was analyzed. We propose a distributed algorithm that allows the devices to select whether to cooperate or not and to choose their optimal power allocation based on the cooperation framework selected. Moreover, we defined distance constraints to enforce the benefits of cooperation between devices in a wireless cloud.
Fast Dynamic Pointer Following via Link-Cut Trees
Venue: arXiv cs.DS 2014
Year: 2014

In this paper, we study the problem of fast dynamic pointer following: given a directed graph $G$ where each vertex has outdegree $1$, efficiently support the operations of i) changing the outgoing edge of any vertex, and ii) find the vertex $k$ vertices `after' a given vertex. We exhibit a solution to this problem based on link-cut trees that requires $O(\lg n)$ time per operation, and prove that this is optimal in the cell-probe complexity model.
Search Interfaces for Mathematicians
Venue: arXiv cs.HC 2014
Year: 2014

Access to mathematical knowledge has changed dramatically in recent years, therefore changing mathematical search practices. Our aim with this study is to scrutinize professional mathematicians' search behavior. With this understanding we want to be able to reason why mathematicians use which tool for what search problem in what phase of the search process. To gain these insights we conducted 24 repertory grid interviews with mathematically inclined people (ranging from senior professional mathematicians to non-mathematicians). From the interview data we elicited patterns for the user group "mathematicians" that can be applied when understanding design issues or creating new designs for mathematical search interfaces.
Properties of Stable Model Semantics Extensions
Venue: arXiv cs.AI 2014
Year: 2014

The stable model (SM) semantics lacks the properties of existence, relevance and cumulativity. If we prospectively consider the class of conservative extensions of SM semantics (i.e., semantics that for each normal logic program P retrieve a superset of the set of stable models of P), one may wander how do the semantics of this class behave in what concerns the aforementioned properties. That is the type of issue dealt with in this paper. We define a large class of conservative extensions of the SM semantics, dubbed affix stable model semantics, ASM, and study the above referred properties into two non-disjoint subfamilies of the class ASM, here dubbed ASMh and ASMm. From this study a number of results stem which facilitate the assessment of semantics in the class ASMh U ASMm with respect to the properties of existence, relevance and cumulativity, whilst unveiling relations among these properties. As a result of the approach taken in our work, light is shed on the characterization of the SM semantics, as we show that the properties of (lack of) existence and (lack of) cautious monotony are equivalent, which opposes statements on this issue that may be found in the literature; we also characterize the relevance failure of SM semantics in a more clear way than usually stated in the literature.
Pengines: Web Logic Programming Made Easy
Venue: arXiv cs.PL 2014
Year: 2014

When developing a (web) interface for a deductive database, functionality required by the client is provided by means of HTTP handlers that wrap the logical data access predicates. These handlers are responsible for converting between client and server data representations and typically include options for paginating results. Designing the web accessible API is difficult because it is hard to predict the exact requirements of clients. Pengines changes this picture. The client provides a Prolog program that selects the required data by accessing the logical API of the server. The pengine infrastructure provides general mechanisms for converting Prolog data and handling Prolog non-determinism. The Pengines library is small (2000 lines Prolog, 150 lines JavaScript). It greatly simplifies defining an AJAX based client for a Prolog program and provides non-deterministic RPC between Prolog processes as well as interaction with Prolog engines similar to Paul Tarau's engines. Pengines are available as a standard package for SWI-Prolog 7.
CDF-Intervals: A Reliable Framework to Reason about Data with Uncertainty
Venue: arXiv cs.LO 2014
Year: 2014

This research introduces a new constraint domain for reasoning about data with uncertainty. It extends convex modeling with the notion of p-box to gain additional quantifiable information on the data whereabouts. Unlike existing approaches, the p-box envelops an unknown probability instead of approximating its representation. The p-box bounds are uniform cumulative distribution functions (cdf) in order to employ linear computations in the probabilistic domain. The reasoning by means of p-box cdf-intervals is an interval computation which is exerted on the real domain then it is projected onto the cdf domain. This operation conveys additional knowledge represented by the obtained probabilistic bounds. Empirical evaluation shows that, with minimal overhead, the output solution set realizes a full enclosure of the data along with tighter bounds on its probabilistic distributions.
An ICT-Based Real-Time Surveillance System for Controlling Dengue in Sri Lanka
Venue: arXiv cs.CY 2014
Year: 2014

Dengue is a notifiable communicable disease in Sri Lanka since 1996. Dengue fever spread rapidly among people living in most of the districts of Sri Lanka. The present notification system of dengue communicable diseases which is enforced by law is a passive surveillance system carried out by the public health care professionals. The present notification of communicable disease system is manual, slow, inefficient, and repetitive all of these lead to handle the dengue related health problems ineffectively. Thus it is less effective in preventing a spreading epidemic, public health care professionals and others require an operational support system to help for managing day-to-day public health responsibilities as well as a method to effectively detect and manage health problems such as Dengue. On the other hand the Information and Communication Technology (ICT) in medical world has been widely used. To give the information technology touch, a complementary web based open source software application environment has been developed with minimum implementation and recurrent costs critical for developing countries like Sri Lanka and named as eDCS: e Dengue Control System based on the same principles of manual disease surveillance system while taking steps to provide timely, accurate information in a reliable and useable manner. The eDCS helps to manage outbreaks through early detection, rapid verification, and appropriate response to Dengue. It allows health care professionals and citizens to get early awareness about the dengue disease via Internet or mobile phone and bring them for performing Dengue prevention and controlling operation through the social media acceleration. The system is initially limited to dengue communicable disease. It can be easily expanded to other communicable diseases, and non communicable disease surveillance in future.
Unifying Causality, Diagnosis, Repairs and View-Updates in Databases
Venue: arXiv cs.DB 2014
Year: 2014

In this work we establish and point out connections between the notion of query-answer causality in databases and database repairs, model-based diagnosis in its consistency-based and abductive versions, and database updates through views. The mutual relationships among these areas of data management and knowledge representation shed light on each of them and help to share notions and results they have in common. In one way or another, these are all approaches to uncertainty management, which becomes even more relevant in the context of big data that have to be made sense of.
Leveraging Evolutionary Search to Discover Self-Adaptive and Self-Organizing Cellular Automata
Venue: arXiv cs.NE 2014
Year: 2014

Building self-adaptive and self-organizing (SASO) systems is a challenging problem, in part because SASO principles are not yet well understood and few platforms exist for exploring them. Cellular automata (CA) are a well-studied approach to exploring the principles underlying self-organization. A CA comprises a lattice of cells whose states change over time based on a discrete update function. One challenge to developing CA is that the relationship of an update function, which describes the local behavior of each cell, to the global behavior of the entire CA is often unclear. As a result, many researchers have used stochastic search techniques, such as evolutionary algorithms, to automatically discover update functions that produce a desired global behavior. However, these update functions are typically defined in a way that does not provide for self-adaptation. Here we describe an approach to discovering CA update functions that are both self-adaptive and self-organizing. Specifically, we use a novel evolutionary algorithm-based approach to discover finite state machines (FSMs) that implement update functions for CA. We show how this approach is able to evolve FSM-based update functions that perform well on the density classification task for 1-, 2-, and 3-dimensional CA. Moreover, we show that these FSMs are self-adaptive, self-organizing, and highly scalable, often performing well on CA that are orders of magnitude larger than those used to evaluate performance during the evolutionary search. These results demonstrate that CA are a viable platform for studying the integration of self-adaptation and self-organization, and strengthen the case for using evolutionary algorithms as a component of SASO systems.
Efficient Tracking of a Moving Object using Inter-Frame Coding
Venue: arXiv cs.CV 2014
Year: 2014

Video surveillance has long been in use to monitor security sensitive areas such as banks, department stores, highways, crowded public places and borders.The advance in computing power, availability of large-capacity storage devices and high speed network infrastructure paved the way for cheaper, multi-sensor video surveillance systems.Traditionally, the video outputs are processed online by human operators and are usually saved to tapes for later use only after a forensic event.The increase in the number of cameras in ordinary surveillance systems overloaded both the human operators and the storage devices with high volumes of data and made it in-feasible to ensure proper monitoring of sensitive areas for long times.
Software developers, moods, emotions, and performance
Venue: arXiv cs.SE 2014
Year: 2014

Studies show that software developers' happiness pays off when it comes to productivity.
On the saddle point problem for non-convex optimization
Venue: arXiv cs.LG 2014
Year: 2014

A central challenge to many fields of science and engineering involves minimizing non-convex error functions over continuous, high dimensional spaces. Gradient descent or quasi-Newton methods are almost ubiquitously used to perform such minimizations, and it is often thought that a main source of difficulty for the ability of these local methods to find the global minimum is the proliferation of local minima with much higher error than the global minimum. Here we argue, based on results from statistical physics, random matrix theory, and neural network theory, that a deeper and more profound difficulty originates from the proliferation of saddle points, not local minima, especially in high dimensional problems of practical interest. Such saddle points are surrounded by high error plateaus that can dramatically slow down learning, and give the illusory impression of the existence of a local minimum. Motivated by these arguments, we propose a new algorithm, the saddle-free Newton method, that can rapidly escape high dimensional saddle points, unlike gradient descent and quasi-Newton methods. We apply this algorithm to deep neural network training, and provide preliminary numerical evidence for its superior performance.
Block matching algorithm based on Differential Evolution for motion estimation
Venue: arXiv cs.MM 2014
Year: 2014

Motion estimation is one of the major problems in developing video coding applications. Among all motion estimation approaches, Block matching (BM) algorithms are the most popular methods due to their effectiveness and simplicity for both software and hardware implementations. A BM approach assumes that the movement of pixels within a defined region of the current frame (Macro-Block, MB) can be modeled as a translation of pixels contained in the previous frame. In this procedure, the motion vector is obtained by minimizing the sum of absolute differences (SAD) produced by the MB of the current frame over a determined search window from the previous frame. The SAD evaluation is computationally expensive and represents the most consuming operation in the BM process. The most straightforward BM method is the full search algorithm (FSA) which finds the most accurate motion vector, calculating exhaustively the SAD values for all elements of the search window. Over this decade, several fast BM algorithms have been proposed to reduce the number of SAD operations by calculating only a fixed subset of search locations at the price of a poor accuracy. In this paper, a new algorithm based on Differential Evolution (DE) is proposed to reduce the number of search locations in the BM process. In order to avoid computing several search locations, the algorithm estimates the SAD values (fitness) for some locations using the SAD values of previously calculated neighboring positions. Since the proposed algorithm does not consider any fixed search pattern or other different assumption, a high probability for finding the true minimum (accurate motion vector) is expected. In comparison to other fast BM algorithms, the proposed method deploys more accurate motion vectors yet delivering competitive time rates.
Multiple-Environment Markov Decision Processes
Venue: arXiv cs.LO 2014
Year: 2014

We introduce Multi-Environment Markov Decision Processes (MEMDPs) which are MDPs with a set of probabilistic transition functions. The goal in a MEMDP is to synthesize a single controller with guaranteed performances against all environments even though the environment is unknown a priori. While MEMDPs can be seen as a special class of partially observable MDPs, we show that several verification problems that are undecidable for partially observable MDPs, are decidable for MEMDPs and sometimes have even efficient solutions.