OpenRaiser/Intern-Atlas huggingface dataset:
Log-Lists and Their Applications to Sorting by Transpositions, Reversals and Block-Interchanges
Venue: arXiv cs.DS 2015
Year: 2015

Link-cut trees have been introduced by D.D. Sleator and R.E. Tarjan (Journal of Computer and System Sciences, 1983) with the aim of efficiently maintaining a forest of vertex-disjoint dynamic rooted trees under cut and link operations. These operations respectively disconnect a subtree from a tree, and join two trees by an edge. Additionally, link-cut trees allow to change the root of a tree and to perform a number of updates and queries on cost values defined on the arcs of the trees. All these operations are performed in $O(\log\, n)$ amortized or worst-case time, depending on the implementation, where $n$ is the total size of the forest. In this paper, we show that a list of elements implemented using link-cut trees (we call it a $\log$-list) allows us to obtain a common running time of $O(\log\, n)$ for the classical operations on lists, but also for some other essential operations that usually take linear time on lists. Such operations require to find the minimum/maximum element in a sublist defined by its endpoints, the position of a given element in the list or the element placed at a given position in the list; or they require to add a value $a$, or to multiply by $-1$, all the elements in a sublist. Furthermore, we use $\log$-lists to implement several existing algorithms for sorting permutations by transpositions and/or reversals and/or block-interchanges, and obtain $O(n\,\log\, n)$ running time for all of them. In this way, the running time of several algorithms is improved, whereas in other cases our algorithms perform as well as the best existing implementations.
DNA-Based Storage: Trends and Methods
Venue: arXiv cs.ET 2015
Year: 2015

We provide an overview of current approaches to DNA-based storage system design and accompanying synthesis, sequencing and editing methods. We also introduce and analyze a suite of new constrained coding schemes for both archival and random access DNA storage channels. The mathematical basis of our work is the construction and design of sequences over discrete alphabets that avoid pre-specified address patterns, have balanced base content, and exhibit other relevant substring constraints. These schemes adapt the stored signals to the DNA medium and thereby reduce the inherent error-rate of the system.
Periodicity Detection of Outlier Sequences Using Constraint Based Pattern Tree with MAD
Venue: arXiv cs.DB 2015
Year: 2015

Patterns that appear rarely or unusually in the data can be defined as outlier patterns. The basic idea behind detecting outlier patterns is comparison of their relative frequencies with frequent patterns. Their frequencies of appearance are less and thus have lesser support in the data. Detecting outlier patterns is an important data mining task which will reveal some interesting facts. The search for periodicity of patterns gives the behavior of these patterns across time as to when they repeat likely. This in turn helps in prediction of events. These patterns are found in Time series-data, social networks etc. In this paper, an algorithm for periodic outlier pattern detection is proposed with the usage of a Constraint Based FP (Frequent Pattern)-tree as the underlying data structure for time series data. The growth of the tree is limited by using level and monotonic constraints. The protein sequence of bacteria named E.Coli is collected and periodic outlier patterns in the sequence are identified. Further the enhancement of results is obtained by finding the Median Absolute Deviation (MAD) in defining candidate outlier patterns. The comparative results between STNR-out (Suffix Tree Noise Resilient for Outlier Detection) and proposed algorithm are illustrated. The results show the effectiveness and applicability of the proposed algorithm.
The Temp Secretary Problem
Venue: arXiv cs.DS 2015
Year: 2015

We consider a generalization of the secretary problem where contracts are temporary, and for a fixed duration. This models online hiring of temporary employees, or online auctions for re-usable resources. The problem is related to the question of Finding a large independent set in a random unit interval graph.
Mining high on-shelf utility itemsets with negative values from dynamic updated database
Venue: arXiv cs.DB 2015
Year: 2015

Utility mining emerged to overcome the limitations of frequent itemset mining by considering the utility of an item. Utility of an item is based on user's interest or preference. Recently, temporal data mining has become a core technical data processing technique to deal with changing data. On-shelf utility mining considers on-shelf time period of item and gets the accurate utility values of itemsets in temporal database. In traditional on-shelf utility mining, profits of all items in databases are considered as positive values. However, in real applications, some items may have negative profit. Most of the traditional algorithms are used to handle static database. In practical situations, temporal databases are continually appended or updated. High on-shelf utility itemsets needs to be updated. Re-running the temporal mining algorithm every time is ineffective since it neglects previously discovered itemsets. It repeats the work done previously. In this paper, an effective algorithm is proposed to find high on-shelf utility itemsets with negative values from the dynamic updated temporal database.
The Restricted Isometry Property of Subsampled Fourier Matrices
Venue: arXiv cs.DS 2015
Year: 2015

A matrix $A \in \mathbb{C}^{q \times N}$ satisfies the restricted isometry property of order $k$ with constant $\varepsilon$ if it preserves the $\ell_2$ norm of all $k$-sparse vectors up to a factor of $1\pm \varepsilon$. We prove that a matrix $A$ obtained by randomly sampling $q = O(k \cdot \log^2 k \cdot \log N)$ rows from an $N \times N$ Fourier matrix satisfies the restricted isometry property of order $k$ with a fixed $\varepsilon$ with high probability. This improves on Rudelson and Vershynin (Comm. Pure Appl. Math., 2008), its subsequent improvements, and Bourgain (GAFA Seminar Notes, 2014).
Optimum Design for Coexistence Between Matrix Completion Based MIMO Radars and a MIMO Communication System
Venue: arXiv cs.IT 2015
Year: 2015

Recently proposed multiple input multiple output radars based on matrix completion (MIMO-MC) employ sparse sampling to reduce the amount of data that need to be forwarded to the radar fusion center, and as such enable savings in communication power and bandwidth. This paper proposes designs that optimize the sharing of spectrum between a MIMO-MC radar and a communication system, so that the latter interferes minimally with the former. First, the communication system transmit covariance matrix is designed to minimize the effective interference power (EIP) to the radar receiver, while maintaining certain average capacity and transmit power for the communication system. Two approaches are proposed, namely a noncooperative and a cooperative approach, with the latter being applicable when the radar sampling scheme is known at the communication system. Second, a joint design of the communication transmit covariance matrix and the MIMO-MC radar sampling scheme is proposed, which achieves even further EIP reduction.
Generating Navigable Semantic Maps from Social Sciences Corpora
Venue: arXiv cs.CL 2015
Year: 2015

It is now commonplace to observe that we are facing a deluge of online information. Researchers have of course long acknowledged the potential value of this information since digital traces make it possible to directly observe, describe and analyze social facts, and above all the co-evolution of ideas and communities over time. However, most online information is expressed through text, which means it is not directly usable by machines, since computers require structured, organized and typed information in order to be able to manipulate it. Our goal is thus twofold: 1. Provide new natural language processing techniques aiming at automatically extracting relevant information from texts, especially in the context of social sciences, and connect these pieces of information so as to obtain relevant socio-semantic networks; 2. Provide new ways of exploring these socio-semantic networks, thanks to tools allowing one to dynamically navigate these networks, de-construct and re-construct them interactively, from different points of view following the needs expressed by domain experts.
Future Large-Scale Memristive Device Crossbar Arrays: Limits Imposed by Sneak-Path Currents on Read Operations
Venue: arXiv cs.ET 2015
Year: 2015

Passive crossbar arrays based upon memristive devices, at crosspoints, hold great promise for the future high-density and non-volatile memories. The most significant challenge facing memristive device based crossbars today is the problem of sneak-path currents. In this paper, we investigate a memristive device with intrinsic rectification behavior to suppress the sneak-path currents in crossbar arrays. The device model is implemented in Verilog-A language and is simulated to match device characteristics readily available in the literature. Then, we systematically evaluate the read operation performance of large-scale crossbar arrays utilizing our proposed model in terms of read margin and power consumption while considering different crossbar sizes, interconnect resistance values, HRS/LRS (High Resistance State/Low Resistance State) values, rectification ratios and different read-schemes. The outcomes of this study are understanding the trade-offs among read margin, power consumption, read-schemes and most importantly providing a guideline for circuit designers to improve the performance of a memory based crossbar structure. In addition, read operation performance comparison of the intrinsic rectifying memristive device model with other memristive device models are studied.
Do Mendeley readership counts help to filter highly cited WoS publications better than average citation impact of journals (JCS)?
Venue: arXiv cs.DL 2015
Year: 2015

In this study, the academic status of users of scientific publications in Mendeley is explored in order to analyse the usage pattern of Mendeley users in terms of subject fields, citation and readership impact. The main focus of this study is on studying the filtering capacity of Mendeley readership counts compared to journal citation scores in detecting highly cited WoS publications. Main finding suggests a faster reception of Mendeley readerships as compared to citations across 5 major field of science. The higher correlations of scientific users with citations indicate the similarity between reading and citation behaviour among these users. It is confirmed that Mendeley readership counts filter highly cited publications (PPtop 10%) better than journal citation scores in all subject fields and by most of user types. This result reinforces the potential role that Mendeley readerships could play for informing scientific and alternative impacts.
How well developed are Altmetrics? Cross-disciplinary analysis of the presence of alternative metrics in scientific publications?
Venue: arXiv cs.DL 2015
Year: 2015

In this paper an analysis of the presence and possibilities of altmetrics for bibliometric and performance analysis is carried out. Using the web based tool Impact Story, we have collected metrics for 20,000 random publications from the Web of Science. We studied the presence and frequency of altmetrics in the set of publications, across fields, document types and also through the years. The main result of the study is that less than 50% of the publications have some kind of altmetrics. The source that provides most metrics is Mendeley, with metrics on readerships for around 37% of all the publications studied. Other sources only provide marginal information. Possibilities and limitations of these indicators are discussed and future research lines are outlined. We also assessed the accuracy of the data retrieved through Impact Story by focusing on the analysis of the accuracy of data from Mendeley; in a follow up study, the accuracy and validity of other data sources not included here will be assessed.
Who to Trust for Truthfully Maximizing Welfare?
Venue: arXiv cs.GT 2015
Year: 2015

We introduce a general approach based on \emph{selective verification} and obtain approximate mechanisms without money for maximizing the social welfare in the general domain of utilitarian voting. Having a good allocation in mind, a mechanism with verification selects few critical agents and detects, using a verification oracle, whether they have reported truthfully. If yes, the mechanism produces the desired allocation. Otherwise, the mechanism ignores any misreports and proceeds with the remaining agents. We obtain randomized truthful (or almost truthful) mechanisms without money that verify only $O(\ln m / ε)$ agents, where $m$ is the number of outcomes, independently of the total number of agents, and are $(1-ε)$-approximate for the social welfare. We also show that any truthful mechanism with a constant approximation ratio needs to verify $Ω(\log m)$ agents. A remarkable property of our mechanisms is \emph{robustness}, namely that their outcome depends only on the reports of the truthful agents.
A Convex Approach to Sparse H infinity Analysis & Synthesis
Venue: arXiv cs.SY 2015
Year: 2015

In this paper, we propose a new robust analysis tool motivated by large-scale systems. The H infinity norm of a system measures its robustness by quantifying the worst-case behavior of a system perturbed by a unit-energy disturbance. However, the disturbance that induces such worst-case behavior requires perfect coordination among all disturbance channels. Given that many systems of interest, such as the power grid, the internet and automated vehicle platoons, are large-scale and spatially distributed, such coordination may not be possible, and hence the H infinity norm, used as a measure of robustness, may be too conservative. We therefore propose a cardinality constrained variant of the H infinity norm in which an adversarial disturbance can use only a limited number of channels. As this problem is inherently combinatorial, we present a semidefinite programming (SDP) relaxation based on the l1 norm that yields an upper bound on the cardinality constrained robustness problem. We further propose a simple rounding heuristic based on the optimal solution of SDP relaxation which provides a lower bound. Motivated by privacy in large-scale systems, we also extend these relaxations to computing the minimum gain of a system subject to a limited number of inputs. Finally, we also present a SDP based optimal controller synthesis method for minimizing the SDP relaxation of our novel robustness measure. The effectiveness of our semidefinite relaxation is demonstrated through numerical examples.
Achieving Synergy in Cognitive Behavior of Humanoids via Deep Learning of Dynamic Visuo-Motor-Attentional Coordination
Venue: arXiv cs.AI 2015
Year: 2015

The current study examines how adequate coordination among different cognitive processes including visual recognition, attention switching, action preparation and generation can be developed via learning of robots by introducing a novel model, the Visuo-Motor Deep Dynamic Neural Network (VMDNN). The proposed model is built on coupling of a dynamic vision network, a motor generation network, and a higher level network allocated on top of these two. The simulation experiments using the iCub simulator were conducted for cognitive tasks including visual object manipulation responding to human gestures. The results showed that synergetic coordination can be developed via iterative learning through the whole network when spatio-temporal hierarchy and temporal one can be self-organized in the visual pathway and in the motor pathway, respectively, such that the higher level can manipulate them with abstraction.
Extending Basic Block Versioning with Typed Object Shapes
Venue: arXiv cs.PL 2015
Year: 2015

Typical JavaScript (JS) programs feature a large number of object property accesses. Hence, fast property reads and writes are crucial for good performance. Unfortunately, many (often redundant) dynamic checks are implied in each property access and the semantic complexity of JS makes it difficult to optimize away these tests through program analysis. We introduce two techniques to effectively eliminate a large proportion of dynamic checks related to object property accesses. Typed shapes enable code specialization based on object property types without potentially complex and expensive analyses. Shape propagation allows the elimination of redundant shape checks in inline caches. These two techniques combine particularly well with Basic Block Versioning (BBV), but should be easily adaptable to tracing Just-In-Time (JIT) compilers and method JITs with type feedback. To assess the effectiveness of the techniques presented, we have implemented them in Higgs, a type-specializing JIT compiler for JS. The techniques are compared to a baseline using polymorphic Inline Caches (PICs), as well as commercial JS implementations. Empirical results show that across the 26 benchmarks tested, these techniques eliminate on average 48% of type tests, reduce code size by 17% and reduce execution time by 25%. On several benchmarks, Higgs performs better than current production JS virtual machines
Automated Matchmaking to Improve Accuracy of Applicant Selection for University Education System
Venue: arXiv cs.AI 2015
Year: 2015

The accurate applicant selection for university education is imperative to ensure fairness and optimal use of institutional resources. Although various approaches are operational in tertiary educational institutions for selecting applicants, a novel method of automated matchmaking is explored in the current study. The method functions by matching a prospective students skills profile to a programmes requisites profile. Empirical comparisons of the results, calculated by automated matchmaking and two other selection methods, show matchmaking to be a viable alternative for accurate selection of applicants. Matchmaking offers a unique advantage that it neither requires data from other applicants nor compares applicants with each other. Instead, it emphasises norms that define admissibility to a programme. We have proposed the use of technology to minimize the gap between students aspirations, skill sets and course requirements. It is a solution to minimize the number of students who get frustrated because of mismatched course selection.
Compressive Identification of Active OFDM Subcarriers in Presence of Timing Offset
Venue: arXiv cs.IT 2015
Year: 2015

In this paper we study the problem of identifying active subcarriers in an OFDM signal from compressive measurements sampled at sub-Nyquist rate. The problem is of importance in Cognitive Radio systems when secondary users (SUs) are looking for available spectrum opportunities to communicate over them while sensing at Nyquist rate sampling can be costly or even impractical in case of very wide bandwidth. We first study the effect of timing offset and derive the necessary and sufficient conditions for signal recovery in the oracle-assisted case when the true active sub-carriers are assumed known. Then we propose an Orthogonal Matching Pursuit (OMP)-based joint sparse recovery method for identifying active subcarriers when the timing offset is known. Finally we extend the problem to the case of unknown timing offset and develop a joint dictionary learning and sparse approximation algorithm, where in the dictionary learning phase the timing offset is estimated and in the sparse approximation phase active subcarriers are identified. The obtained results demonstrate that active subcarrier identification can be carried out reliably, by using the developed framework.
An extremal problem in proper $(r,p)$-coloring of hypergraphs
Venue: arXiv cs.DM 2015
Year: 2015

Let $G(V,E)$ be a $k$-uniform hypergraph. A hyperedge $e \in E$ is said to be properly $(r,p)$ colored by an $r$-coloring of vertices in $V$ if $e$ contains vertices of at least $p$ distinct colors in the $r$-coloring. An $r$-coloring of vertices in $V$ is called a {\it strong $(r,p)$ coloring} if every hyperedge $e \in E$ is properly $(r,p)$ colored by the $r$-coloring. We study the maximum number of hyperedges that can be properly $(r,p)$ colored by a single $r$-coloring and the structures that maximizes number of properly $(r,p)$ colored hyperedges.
Cooperative Reactive Synthesis
Venue: arXiv cs.LO 2015
Year: 2015

A modern approach to engineering correct-by-construction systems is to synthesize them automatically from formal specifications. Oftentimes, a system can only satisfy its guarantees if certain environment assumptions hold, which motivates their inclusion in the system specification. Experience with modern synthesis approaches shows that synthesized systems tend to satisfy their specifications by actively working towards the violation of the assumptions rather than satisfying assumptions and guarantees together. Such uncooperative behavior is undesirable because it violates the aim of synthesis: the system should try to satisfy its guarantees and use the assumptions only when needed. Also, the assumptions often describe the valid behavior of other components in a bigger system, which should not be obstructed unnecessarily. In this paper, we present a hierarchy of cooperation levels between system and environment. Each level describes how well the system enforces both the assumptions and guarantees. We show how to synthesize systems that achieve the highest possible cooperation level for a given specification in Linear Temporal Logic (LTL). The synthesized systems can also exploit cooperative environment behavior during operation to reach a higher cooperation level that is not enforceable by the system initially. The worst-case time complexity of our synthesis procedure is doubly-exponential, which matches the complexity of standard LTL synthesis. This is an extended version of [7] that features an additional appendix.
Maximizing Profit of Cloud Brokers under Quantized Billing Cycles: a Dynamic Pricing Strategy based on Ski-Rental Problem
Venue: arXiv cs.DC 2015
Year: 2015

In cloud computing, users scale their resources (computational) based on their need. There is massive literature dealing with such resource scaling algorithms. These works ignore a fundamental constrain imposed by all Cloud Service Providers (CSP), i.e. one has to pay for a fixed minimum duration irrespective of their usage. Such quantization in billing cycles poses problem for users with sporadic workload. In recent literature, Cloud Broker (CB) has been introduced for the benefit of such users. A CB rents resources from CSP and in turn provides service to users to generate profit. Contract between CB and user is that of pay-what-you-use/pay-per-use. However CB faces the challenge of Quantized Billing Cycles as it negotiates with CSP. We design two algorithms, one fully online and the other partially online, which maximizes the profit of the CB. The key idea is to regulate users demand using dynamic pricing. Our algorithm is inspired by the Ski-Rental problem. We derive competitive ratio of these algorithms and also conduct simulations using real world traces to prove the efficiency of our algorithm.