OpenRaiser/Intern-Atlas huggingface dataset:
Adding Partial Functions to Constraint Logic Programming with Sets
Venue: arXiv cs.PL 2015
Year: 2015

Partial functions are common abstractions in formal specification notations such as Z, B and Alloy. Conversely, executable programming languages usually provide little or no support for them. In this paper we propose to add partial functions as a primitive feature to a Constraint Logic Programming (CLP) language, namely {log}. Although partial functions could be programmed on top of {log}, providing them as first-class citizens adds valuable flexibility and generality to the form of set-theoretic formulas that the language can safely deal with. In particular, the paper shows how the {log} constraint solver is naturally extended in order to accommodate for the new primitive constraints dealing with partial functions. Efficiency of the new version is empirically assessed by running a number of non-trivial set-theoretical goals involving partial functions, obtained from specifications written in Z.
Improving Software Effort Estimation Using Neuro-Fuzzy Model with SEER-SEM
Venue: arXiv cs.SE 2015
Year: 2015

The aims of our research are to evaluate the prediction performance of the proposed neuro-fuzzy model with System Evaluation and Estimation of Resource Software Estimation Model (SEER-SEM) in software estimation practices and to apply the proposed architecture that combines the neuro-fuzzy technique with different algorithmic models. In this paper, an approach combining the neuro-fuzzy technique and the SEER-SEM effort estimation algorithm is described. This proposed model possesses positive characteristics such as learning ability, decreased sensitivity, effective generalization, and knowledge integration for introducing the neuro-fuzzy technique. Moreover, continuous rating values and linguistic values can be inputs of the proposed model for avoiding the large estimation deviation among similar projects. The performance of the proposed model is accessed by designing and conducting evaluation with published projects and industrial data. The evaluation results indicate that estimation with our proposed neuro-fuzzy model containing SEER-SEM is improved in comparison with the estimation results that only use SEER-SEM algorithm. At the same time, the results of this research also demonstrate that the general neuro-fuzzy framework can function with various algorithmic models for improving the performance of software effort estimation.
A Logic Programming Playground for Lambda Terms, Combinators, Types and Tree-based Arithmetic Computations
Venue: arXiv cs.LO 2015
Year: 2015

With sound unification, Definite Clause Grammars and compact expression of combinatorial generation algorithms, logic programming is shown to conveniently host a declarative playground where interesting properties and behaviors emerge from the interaction of heterogenous but deeply connected computational objects. Compact combinatorial generation algorithms are given for several families of lambda terms, including open, closed, simply typed and linear terms as well as type inference and normal order reduction algorithms. We describe a Prolog-based combined lambda term generator and type-inferrer for closed well-typed terms of a given size, in de Bruijn notation. We introduce a compressed de Bruijn representation of lambda terms and define its bijections to standard representations. Our compressed terms facilitate derivation of size-proportionate ranking and unranking algorithms of lambda terms and their inferred simple types. The S and K combinator expressions form a well-known Turing-complete subset of the lambda calculus. We specify evaluation, type inference and combinatorial generation algorithms for SK-combinator trees. In the process, we unravel properties shedding new light on interesting aspects of their structure and distribution. A uniform representation, as binary trees with empty leaves, is given to expressions built with Rosser's X-combinator, natural numbers, lambda terms and simple types. Using this shared representation, ranking/unranking algorithm of lambda terms to tree-based natural numbers are described. Our algorithms, expressed as an incrementally developed literate Prolog program, implement a declarative playground for exploration of representations, encodings and computations with uniformly represented lambda terms, types, combinators and tree-based arithmetic.
Pattern-avoiding access in binary search trees
Venue: arXiv cs.DS 2015
Year: 2015

The dynamic optimality conjecture is perhaps the most fundamental open question about binary search trees (BST). It postulates the existence of an asymptotically optimal online BST, i.e. one that is constant factor competitive with any BST on any input access sequence. The two main candidates for dynamic optimality in the literature are splay trees [Sleator and Tarjan, 1985], and Greedy [Lucas, 1988; Munro, 2000; Demaine et al. 2009] [..] Dynamic optimality is trivial for almost all sequences: the optimum access cost of most length-n sequences is Theta(n log n), achievable by any balanced BST. Thus, the obvious missing step towards the conjecture is an understanding of the "easy" access sequences. [..] The difficulty of proving dynamic optimality is witnessed by highly restricted special cases that remain unresolved; one prominent example is the traversal conjecture [Sleator and Tarjan, 1985], which states that preorder sequences (whose optimum is linear) are linear-time accessed by splay trees; no online BST is known to satisfy this conjecture. In this paper, we prove two different relaxations of the traversal conjecture for Greedy: (i) Greedy is almost linear for preorder traversal, (ii) if a linear-time preprocessing is allowed, Greedy is in fact linear. These statements are corollaries of our more general results that express the complexity of access sequences in terms of a pattern avoidance parameter k. [..] To our knowledge, these are the first upper bounds for Greedy that are not known to hold for any other online BST. To obtain these results we identify an input-revealing property of Greedy. Informally, this means that the execution log partially reveals the structure of the access sequence. This property facilitates the use of rich technical tools from forbidden submatrix theory. [Abridged]
Stability of Spreading Processes over Time-Varying Large-Scale Networks
Venue: arXiv cs.SI 2015
Year: 2015

In this paper, we analyze the dynamics of spreading processes taking place over time-varying networks. A common approach to model time-varying networks is via Markovian random graph processes. This modeling approach presents the following limitation: Markovian random graphs can only replicate switching patterns with exponential inter-switching times, while in real applications these times are usually far from exponential. In this paper, we introduce a flexible and tractable extended family of processes able to replicate, with arbitrary accuracy, any distribution of inter-switching times. We then study the stability of spreading processes in this extended family. We first show that a direct analysis based on Itô's formula provides stability conditions in terms of the eigenvalues of a matrix whose size grows exponentially with the number of edges. To overcome this limitation, we derive alternative stability conditions involving the eigenvalues of a matrix whose size grows linearly with the number of nodes. Based on our results, we also show that heuristics based on aggregated static networks approximate the epidemic threshold more accurately as the number of nodes grows, or the temporal volatility of the random graph process is reduced. Finally, we illustrate our findings via numerical simulations.
String Comparison in $V$-Order: New Lexicographic Properties & On-line Applications
Venue: arXiv cs.DS 2015
Year: 2015

$V$-order is a global order on strings related to Unique Maximal Factorization Families (UMFFs), which are themselves generalizations of Lyndon words. $V$-order has recently been proposed as an alternative to lexicographical order in the computation of suffix arrays and in the suffix-sorting induced by the Burrows-Wheeler transform. Efficient $V$-ordering of strings thus becomes a matter of considerable interest. In this paper we present new and surprising results on $V$-order in strings, then go on to explore the algorithmic consequences.
A QoS-based Power Allocation for Cellular Users with Different Modulations
Venue: arXiv cs.NI 2015
Year: 2015

In this paper, we propose a novel optimal power allocation method that features a power limit function and is able to ensure more users reach the desired Quality-of-Service (QoS). In our model we use sigmoidal-like utility functions to represent the probability of successful reception of packets at user equipment (UE)s. Given that each UE has a different channel quality and different location from base station (BS), it has different CQI and modulation. For each CQI zone, we evaluate the power threshold which is required to achieve the minimum QoS for each UE and show that the higher CQI the lower power threshold is. We present a resource allocation algorithm that gives limited resources to UEs who have already reached their pre-specified minimum QoS, and provides more possible resources to UEs who can not reach it. We also compare this algorithm with the optimal power allocation algorithm in [1] to show the enhancement.
Network MIMO with Partial Cooperation between Radar and Cellular Systems
Venue: arXiv cs.IT 2015
Year: 2015

To meet the growing spectrum demands, future cellular systems are expected to share the spectrum of other services such as radar. In this paper, we consider a network multiple-input multiple-output (MIMO) with partial cooperation model where radar stations cooperate with cellular base stations (BS)s to deliver messages to intended mobile users. So the radar stations act as BSs in the cellular system. However, due to the high power transmitted by radar stations for detection of far targets, the cellular receivers could burnout when receiving these high radar powers. Therefore, we propose a new projection method called small singular values space projection (SSVSP) to mitigate these harmful high power and enable radar stations to collaborate with cellular base stations. In addition, we formulate the problem into a MIMO interference channel with general constraints (MIMO-IFC-GC). Finally, we provide a solution to minimize the weighted sum mean square error minimization problem (WSMMSE) with enforcing power constraints on both radar and cellular stations.
Spectral structure of singular spectrum decomposition for time series
Venue: arXiv cs.DS 2015
Year: 2015

Singular spectrum analysis (SSA) is a nonparametric and adaptive spectral decomposition of a time series. The singular value decomposition of the trajectory matrix and the anti-diagonal averaging leads to a time-series decomposition. In this algorithm, a single free parameter, window length $K$, is involved which is the FIR filter length for the time series. There are no generally accepted criterion for the proper choice of the window length $K$. Moreover, the proper window length depends on the specific problem which we are interested in. Thus, it is important to monitor the spectral structure of the SSA decomposition and its window length dependence in detail for the practical application. In this paper, based on the filtering interpretation of SSA, it is shown that the decomposition of the power spectrum for the original time series is possible with the filters constructed from the eigenvectors of the lagged-covariance matrix. With this, we can obtain insights into the spectral structure of the SSA decomposition and it helps us for the proper choice of the window length in the practical application of SSA.
A genetic algorithm for autonomous navigation in partially observable domain
Venue: arXiv cs.LG 2015
Year: 2015

The problem of autonomous navigation is one of the basic problems for robotics. Although, in general, it may be challenging when an autonomous vehicle is placed into partially observable domain. In this paper we consider simplistic environment model and introduce a navigation algorithm based on Learning Classifier System.
Requirements for Open-Ended Evolution in Natural and Artificial Systems
Venue: arXiv cs.NE 2015
Year: 2015

Open-ended evolutionary dynamics remains an elusive goal for artificial evolutionary systems. Many ideas exist in the biological literature beyond the basic Darwinian requirements of variation, differential reproduction and inheritance. I argue that these ideas can be seen as aspects of five fundamental requirements for open-ended evolution: (1) robustly reproductive individuals, (2) a medium allowing the possible existence of a practically unlimited diversity of individuals and interactions, (3) individuals capable of producing more complex offspring, (4) mutational pathways to other viable individuals, and (5) drive for continued evolution. I briefly discuss implications of this view for the design of artificial systems with greater evolutionary potential.
Discovery of Shared Semantic Spaces for Multi-Scene Video Query and Summarization
Venue: arXiv cs.CV 2015
Year: 2015

The growing rate of public space CCTV installations has generated a need for automated methods for exploiting video surveillance data including scene understanding, query, behaviour annotation and summarization. For this reason, extensive research has been performed on surveillance scene understanding and analysis. However, most studies have considered single scenes, or groups of adjacent scenes. The semantic similarity between different but related scenes (e.g., many different traffic scenes of similar layout) is not generally exploited to improve any automated surveillance tasks and reduce manual effort. Exploiting commonality, and sharing any supervised annotations, between different scenes is however challenging due to: Some scenes are totally un-related -- and thus any information sharing between them would be detrimental; while others may only share a subset of common activities -- and thus information sharing is only useful if it is selective. Moreover, semantically similar activities which should be modelled together and shared across scenes may have quite different pixel-level appearance in each scene. To address these issues we develop a new framework for distributed multiple-scene global understanding that clusters surveillance scenes by their ability to explain each other's behaviours; and further discovers which subset of activities are shared versus scene-specific within each cluster. We show how to use this structured representation of multiple scenes to improve common surveillance tasks including scene activity understanding, cross-scene query-by-example, behaviour classification with reduced supervised labelling requirements, and video summarization. In each case we demonstrate how our multi-scene model improves on a collection of standard single scene models and a flat model of all scenes.
A Green Perspective on Wi-Fi Offloading
Venue: arXiv cs.NI 2015
Year: 2015

Due to increased energy consumption and carbon emissions of the ICT industry, operators worldwide are focusing on reducing energy consumption of their networks from financial as well as corporate responsibility perspectives. The subject of green or energy efficient operation of cellular access network has attracted a lot of attention in the research community recently. In this regard, dynamically powering down the radio network equipment has emerged as a promising solution. In literature, research around this type of techniques has mainly focused on quantifying the energy saving potential. However, little efforts have been made towards practical realization of these energy saving concepts. On the other hand, Wi-Fi networks are undergoing a paradigm shift towards ubiquity. The main objective of this paper is to provide novel mechanisms for practically realizing the concept of improving power efficiency in the cellular access network through opportunistically offloading users to Wi- Fi networks. These mechanisms are based on the principles of cognitive network management. Performance evaluation shows the potential of proposed mechanisms as a viable solution for achieving energy efficiency in the cellular access network.
Symmetric Canonical Quincunx Tight Framelets with High Vanishing Moments and Smoothness
Venue: arXiv cs.IT 2015
Year: 2015

We propose an approach to construct a family of two-dimensional compactly supported real-valued symmetric quincunx tight framelets $\{ϕ; ψ_1,ψ_2,ψ_3\}$ in $L_2(R^2)$ with arbitrarily high orders of vanishing moments. Such symmetric quincunx tight framelets are associated with quincunx tight framelet filter banks $\{a;b_1,b_2,b_3\}$ having increasing orders of vanishing moments and enjoying the additional double canonical properties: \[ b_1(k_1,k_2)=(-1)^{1+k_1+k_2} a(1-k_1,-k_2), b_3(k_1,k_2)=(-1)^{1+k_1+k_2} b_2(1-k_1,-k_2). \] For a low-pass filter $a$ which is not a quincunx orthonormal wavelet filter, we show that a quincunx tight framelet filter bank $\{a;b_1,\ldots,b_L\}$ with $b_1$ taking the above canonical form must have $L\ge 3$ high-pass filters. Thus, our family of symmetric double canonical quincunx tight framelets has the minimum number of generators. Numerical calculation indicates that this family of symmetric double canonical quincunx tight framelets can be arbitrarily smooth. Using one-dimensional filters having linear-phase moments, in this paper we also provide a second approach to construct multiple canonical quincunx tight framelets with symmetry. In particular, the second approach yields a family of $6$-multiple canonical real-valued quincunx tight framelets in $L_2(R^2)$ and a family of double canonical complex-valued quincunx tight framelets in $L_2(R^2)$ such that both of them have symmetry and arbitrarily increasing orders of smoothness and vanishing moments. Several examples are provided to illustrate our general construction and theoretical results on canonical quincunx tight framelets in $L_2(R^2)$ with symmetry, high vanishing moments, and smoothness. Symmetric quincunx tight framelets constructed by both approaches in this paper are of particular interest for their applications in computer graphics and image processing.
ms2: A molecular simulation tool for thermodynamic properties, new version release
Venue: arXiv cs.CE 2015
Year: 2015

A new version release (2.0) of the molecular simulation tool ms2 [S. Deublein et al., Comput. Phys. Commun. 182 (2011) 2350] is presented. Version 2.0 of ms2 features a hybrid parallelization based on MPI and OpenMP for molecular dynamics simulation to achieve higher scalability. Furthermore, the formalism by Lustig [R. Lustig, Mol. Phys. 110 (2012) 3041] is implemented, allowing for a systematic sampling of Massieu potential derivatives in a single simulation run. Moreover, the Green-Kubo formalism is extended for the sampling of the electric conductivity and the residence time. To remove the restriction of the preceding version to electro-neutral molecules, Ewald summation is implemented to consider ionic long range interactions. Finally, the sampling of the radial distribution function is added.
Building an iterative heuristic solver for a quantum annealer
Venue: arXiv cs.DM 2015
Year: 2015

A quantum annealer heuristically minimizes quadratic unconstrained binary optimization (QUBO) problems, but is limited by the physical hardware in the size and density of the problems it can handle. We have developed a meta-heuristic solver that utilizes D-Wave Systems' quantum annealer (or any other QUBO problem optimizer) to solve larger or denser problems, by iteratively solving subproblems, while keeping the rest of the variables fixed. We present our algorithm, several variants, and the results for the optimization of standard QUBO problem instances from OR-Library of sizes 500 and 2500 as well as the Palubeckis instances of sizes 3000 to 7000. For practical use of the solver, we show the dependence of the time to best solution on the desired gap to the best known solution. In addition, we study the dependence of the gap and the time to best solution on the size of the problems solved by the underlying optimizer.
Converting Static Image Datasets to Spiking Neuromorphic Datasets Using Saccades
Venue: arXiv cs.DB 2015
Year: 2015

Creating datasets for Neuromorphic Vision is a challenging task. A lack of available recordings from Neuromorphic Vision sensors means that data must typically be recorded specifically for dataset creation rather than collecting and labelling existing data. The task is further complicated by a desire to simultaneously provide traditional frame-based recordings to allow for direct comparison with traditional Computer Vision algorithms. Here we propose a method for converting existing Computer Vision static image datasets into Neuromorphic Vision datasets using an actuated pan-tilt camera platform. Moving the sensor rather than the scene or image is a more biologically realistic approach to sensing and eliminates timing artifacts introduced by monitor updates when simulating motion on a computer monitor. We present conversion of two popular image datasets (MNIST and Caltech101) which have played important roles in the development of Computer Vision, and we provide performance metrics on these datasets using spike-based recognition algorithms. This work contributes datasets for future use in the field, as well as results from spike-based algorithms against which future works can compare. Furthermore, by converting datasets already popular in Computer Vision, we enable more direct comparison with frame-based approaches.
Geography of Emotion: Where in a City are People Happier?
Venue: arXiv cs.CY 2015
Year: 2015

Location-sharing services were built upon people's desire to share their activities and locations with others. By "checking-in" to a place, such as a restaurant, a park, gym, or train station, people disclose where they are, thereby providing valuable information about land use and utilization of services in urban areas. This information may, in turn, be used to design smarter, happier, more equitable cities. We use data from Foursquare location-sharing service to identify areas within a major US metropolitan area with many check-ins, i.e., areas that people like to use. We then use data from the Twitter microblogging platform to analyze the properties of these areas. Specifically, we have extracted a large corpus of geo-tagged messages, called tweets, from a major metropolitan area and linked them US Census data through their locations. This allows us to measure the sentiment expressed in tweets that are posted from a specific area, and also use that area's demographic properties in analysis. Our results reveal that areas with many check-ins are different from other areas within the metropolitan region. In particular, these areas have happier tweets, which also encourage people from other areas to commute longer distances to these places. These findings shed light on human mobility patterns, as well as how physical environment influences human emotions.
Focused Stochastic Local Search and the Lovász Local Lemma
Venue: arXiv cs.DM 2015
Year: 2015

We develop tools for analyzing focused stochastic local search algorithms. These are algorithms which search a state space probabilistically by repeatedly selecting a constraint that is violated in the current state and moving to a random nearby state which, hopefully, addresses the violation without introducing many new ones. A large class of such algorithms arise from the algorithmization of the Lovász Local Lemma, a non-constructive tool for proving the existence of satisfying states. Here we give tools that provide a unified analysis of such algorithms and of many more, expressing them as instances of a general framework.