OpenRaiser/Intern-Atlas huggingface dataset:
Shape Expressions Schemas
Venue: arXiv cs.DB 2015
Year: 2015

We present Shape Expressions (ShEx), an expressive schema language for RDF designed to provide a high-level, user friendly syntax with intuitive semantics. ShEx allows to describe the vocabulary and the structure of an RDF graph, and to constrain the allowed values for the properties of a node. It includes an algebraic grouping operator, a choice operator, cardinalitiy constraints for the number of allowed occurrences of a property, and negation. We define the semantics of the language and illustrate it with examples. We then present a validation algorithm that, given a node in an RDF graph and a constraint defined by the ShEx schema, allows to check whether the node satisfies that constraint. The algorithm outputs a proof that contains trivially verifiable associations of nodes and the constraints that they satisfy. The structure can be used for complex post-processing tasks, such as transforming the RDF graph to other graph or tree structures, verifying more complex constraints, or debugging (w.r.t. the schema). We also show the inherent difficulty of error identification of ShEx.
Saddle Point Approximation for Outage Probability Using Cumulant Generating Functions
Venue: arXiv cs.IT 2015
Year: 2015

This letter proposes the use of saddle point approximation (SPA) to evaluate the outage probability of wireless cellular networks. Unlike traditional numerical integration-based approaches, the SPA approach relies on cumulant generating functions (CGFs) and eliminates the need for explicit numerical integration. The approach is generic and can be applied to a wide variety of distributions, given that their CGFs exist. We illustrate the usefulness of SPA on channel fading distributions such as Nakagami-$m$, Nakagami-$q$ (Hoyt), and Rician distributions. Numerical results validate the accuracy of the proposed SPA approach.
Inversion Complexity of Functions of Multi-Valued Logic
Venue: arXiv cs.DM 2015
Year: 2015

The minimum number of NOT gates in a logic circuit computing a Boolean function is called the inversion complexity of the function. In 1957, A. A. Markov determined the inversion complexity of every Boolean function and proved that $\lceil\log_{2}(d(f)+1)\rceil$ NOT gates are necessary and sufficient to compute any Boolean function $f$ (where $d(f)$ is the maximum number of value changes from greater to smaller over all increasing chains of tuples of variables values). This result is extended to $k$-valued functions computing in this paper. Thereupon one can use monotone functions "for free" like in the Boolean case. It is shown that the minimum sufficient number of non-monotone gates for the realization of the arbitrary $k$-valued logic function $f$ is equal to $\lceil\log_{2}(d(f)+1)\rceil$ if Post negation (function $x+1 \pmod{k}$) is used in NOT nodes and is also equal to $\lceil\log_{k}(d(f)+1)\rceil$, if Łukasiewicz negation (function $k-1-x$) is used in NOT nodes. Similar extension for another classical result of A. A. Markov for the inversion complexity of a system of Boolean functions to $k$-valued logic functions has been obtained.
Energy Efficiency in Relay-Assisted mmWave Cellular Networks
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, energy efficiency of relay-assisted millimeter wave (mmWave) cellular networks with Poisson Point Process (PPP) distributed base stations (BSs) and relay stations (RSs) is analyzed using tools from stochastic geometry. The distinguishing features of mmWave communications such as directional beamforming and having different path loss laws for line-of-sight (LOS) and non-line-of-sight (NLOS) links are incorporated into the energy efficiency analysis. Following the description of the system model for mmWave cellular networks, coverage probabilities are computed for each link. Subsequently, average power consumption of BSs and RSs are modeled and energy efficiency is determined in terms of system parameters. Energy efficiency in the presence of beamforming alignment errors is also investigated to get insight on the performance in practical scenarios. Finally, the impact of BS and RS densities, antenna gains, main lobe beam widths, LOS interference range, and alignment errors on the energy efficiency is analyzed via numerical results.
A lower bound on the performance of dynamic curing policies for epidemics on graphs
Venue: arXiv cs.SI 2015
Year: 2015

We consider an SIS-type epidemic process that evolves on a known graph. We assume that a fixed curing budget can be allocated at each instant to the nodes of the graph, towards the objective of minimizing the expected extinction time of the epidemic. We provide a lower bound on the optimal expected extinction time as a function of the available budget, the epidemic parameters, the maximum degree, and the CutWidth of the graph. For graphs with large CutWidth (close to the largest possible), and under a budget which is sublinear in the number of nodes, our lower bound scales exponentially with the size of the graph.
Creating Scalable and Interactive Web Applications Using High Performance Latent Variable Models
Venue: arXiv cs.AI 2015
Year: 2015

In this project we outline a modularized, scalable system for comparing Amazon products in an interactive and informative way using efficient latent variable models and dynamic visualization. We demonstrate how our system can build on the structure and rich review information of Amazon products in order to provide a fast, multifaceted, and intuitive comparison. By providing a condensed per-topic comparison visualization to the user, we are able to display aggregate information from the entire set of reviews while providing an interface that is at least as compact as the "most helpful reviews" currently displayed by Amazon, yet far more informative.
Switchability and collapsibility of Gap Algebras
Venue: arXiv cs.LO 2015
Year: 2015

Let A be an idempotent algebra on a 3-element domain D that omits a G-set for a factor. Suppose A is not αβ-projective (for some alpha, beta subsets of D) and is not collapsible. It follows that A is switchable. We prove that, for every finite subset Delta of Inv(A), Pol(Delta) is collapsible. We also exhibit an algebra that is collapsible from a non-singleton source but is not collapsible from any singleton source.
Prevalence and recoverability of syntactic parameters in sparse distributed memories
Venue: arXiv cs.CL 2015
Year: 2015

We propose a new method, based on Sparse Distributed Memory (Kanerva Networks), for studying dependency relations between different syntactic parameters in the Principles and Parameters model of Syntax. We store data of syntactic parameters of world languages in a Kanerva Network and we check the recoverability of corrupted parameter data from the network. We find that different syntactic parameters have different degrees of recoverability. We identify two different effects: an overall underlying relation between the prevalence of parameters across languages and their degree of recoverability, and a finer effect that makes some parameters more easily recoverable beyond what their prevalence would indicate. We interpret a higher recoverability for a syntactic parameter as an indication of the existence of a dependency relation, through which the given parameter can be determined using the remaining uncorrupted data.
Robust Satisfaction of Temporal Logic Specifications via Reinforcement Learning
Venue: arXiv cs.SY 2015
Year: 2015

We consider the problem of steering a system with unknown, stochastic dynamics to satisfy a rich, temporally layered task given as a signal temporal logic formula. We represent the system as a Markov decision process in which the states are built from a partition of the state space and the transition probabilities are unknown. We present provably convergent reinforcement learning algorithms to maximize the probability of satisfying a given formula and to maximize the average expected robustness, i.e., a measure of how strongly the formula is satisfied. We demonstrate via a pair of robot navigation simulation case studies that reinforcement learning with robustness maximization performs better than probability maximization in terms of both probability of satisfaction and expected robustness.
Big Data Analytics-Enhanced Cloud Computing: Challenges, Architectural Elements, and Future Directions
Venue: arXiv cs.DC 2015
Year: 2015

The emergence of cloud computing has made dynamic provisioning of elastic capacity to applications on-demand. Cloud data centers contain thousands of physical servers hosting orders of magnitude more virtual machines that can be allocated on demand to users in a pay-as-you-go model. However, not all systems are able to scale up by just adding more virtual machines. Therefore, it is essential, even for scalable systems, to project workloads in advance rather than using a purely reactive approach. Given the scale of modern cloud infrastructures generating real time monitoring information, along with all the information generated by operating systems and applications, this data poses the issues of volume, velocity, and variety that are addressed by Big Data approaches. In this paper, we investigate how utilization of Big Data analytics helps in enhancing the operation of cloud computing environments. We discuss diverse applications of Big Data analytics in clouds, open issues for enhancing cloud operations via Big Data analytics, and architecture for anomaly detection and prevention in clouds along with future research directions.
Modelling, Measuring and Compensating Color Weak Vision
Venue: arXiv cs.CV 2015
Year: 2015

We use methods from Riemann geometry to investigate transformations between the color spaces of color-normal and color weak observers. The two main applications are the simulation of the perception of a color weak observer for a color normal observer and the compensation of color images in a way that a color weak observer has approximately the same perception as a color normal observer. The metrics in the color spaces of interest are characterized with the help of ellipsoids defined by the just-noticable-differences between color which are measured with the help of color-matching experiments. The constructed mappings are isometries of Riemann spaces that preserve the perceived color-differences for both observers. Among the two approaches to build such an isometry, we introduce normal coordinates in Riemann spaces as a tool to construct a global color-weak compensation map. Compared to previously used methods this method is free from approximation errors due to local linearizations and it avoids the problem of shifting locations of the origin of the local coordinate system. We analyse the variations of the Riemann metrics for different observers obtained from new color matching experiments and describe three variations of the basic method. The performance of the methods is evaluated with the help of semantic differential (SD) tests.
Latency and Resource Utilization Analysis for V2X Communication over LTE MBSFN Transmission
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we investigate the performance of LTE Multicast-Broadcast Single-Frequency Networks (MBSFN). LTE-MBSFN is viewed as one of the most promising candidates for vehicular communications which can enhance reliability of vehicular application traffic. This is achieved due to the possibility to efficiently support message exchange in-between vehicles by multicasting information to several vehicles in parallel (point-to-multipoint transmission) employing an Multimedia Broadcast/Multicast Service (MBMS). We investigate two metrics to gauge the performance of MBMS/MBSFN transmissions in comparison with standard unicast transmissions for vehicular communications: latency of packet delivery and overhead caused by vehicular traffic, i.e., network utilization. Additionally, we present technique of prediction of system behaviour and explore the influence of transmission bandwidth and transmission rate on mentioned metrics.
Centralized Power Control in Cognitive Radio Networks Using Modulation and Coding Classification Feedback
Venue: arXiv cs.NI 2015
Year: 2015

In this paper, a centralized Power Control (PC) scheme and an interference channel learning method are jointly tackled to allow a Cognitive Radio Network (CRN) access to the frequency band of a Primary User (PU) operating based on an Adaptive Coding and Modulation (ACM) protocol. The learning process enabler is a cooperative Modulation and Coding Classification (MCC) technique which estimates the Modulation and Coding scheme (MCS) of the PU. Due to the lack of cooperation between the PU and the CRN, the CRN exploits this multilevel MCC sensing feedback as implicit channel state information (CSI) of the PU link in order to constantly monitor the impact of the aggregated interference it causes. In this paper, an algorithm is developed for maximizing the CRN throughput (the PC optimization objective) and simultaneously learning how to mitigate PU interference (the optimization problem constraint) by using only the MCC information. Ideal approaches for this problem setting with high convergence rate are the cutting plane methods (CPM). Here, we focus on the analytic center cutting plane method (ACCPM) and the center of gravity cutting plane method (CGCPM) whose effectiveness in the proposed simultaneous PC and interference channel learning algorithm is demonstrated through numerical simulations.
Random Projections through multiple optical scattering: Approximating kernels at the speed of light
Venue: arXiv cs.ET 2015
Year: 2015

Random projections have proven extremely useful in many signal processing and machine learning applications. However, they often require either to store a very large random matrix, or to use a different, structured matrix to reduce the computational and memory costs. Here, we overcome this difficulty by proposing an analog, optical device, that performs the random projections literally at the speed of light without having to store any matrix in memory. This is achieved using the physical properties of multiple coherent scattering of coherent light in random media. We use this device on a simple task of classification with a kernel machine, and we show that, on the MNIST database, the experimental results closely match the theoretical performance of the corresponding kernel. This framework can help make kernel methods practical for applications that have large training sets and/or require real-time prediction. We discuss possible extensions of the method in terms of a class of kernels, speed, memory consumption and different problems.
Balancing the Demands of Reliability and Security with Linear Network Coding in Optical Networks
Venue: arXiv cs.CR 2015
Year: 2015

Recently, physical layer security in the optical layer has gained significant traction. Security treats in optical networks generally impact the reliability of optical transmission. Linear Network Coding (LNC) can protect from both the security treats in form of eavesdropping and faulty transmission due to jamming. LNC can mix original data to become incomprehensible for an attacker and also extend original data by coding redundancy, thus protecting a data from errors injected via jamming attacks. In this paper, we study the effectiveness of LNC to balance reliable transmission and security in optical networks. To this end, we combine the coding process with data flow parallelization of the source and propose and compare optimal and randomized path selection methods for parallel transmission. The study shows that a combination of data parallelization, LNC and randomization of path selection increases security and reliability of the transmission. We analyze the so-called catastrophic security treat of the network and show that in case of conventional transmission scheme and in absence of LNC, an attacker could eavesdrop or disrupt a whole secret data by accessing only one edge in a network.
Fast Latent Variable Models for Inference and Visualization on Mobile Devices
Venue: arXiv cs.LG 2015
Year: 2015

In this project we outline Vedalia, a high performance distributed network for performing inference on latent variable models in the context of Amazon review visualization. We introduce a new model, RLDA, which extends Latent Dirichlet Allocation (LDA) [Blei et al., 2003] for the review space by incorporating auxiliary data available in online reviews to improve modeling while simultaneously remaining compatible with pre-existing fast sampling techniques such as [Yao et al., 2009; Li et al., 2014a] to achieve high performance. The network is designed such that computation is efficiently offloaded to the client devices using the Chital system [Robinson & Li, 2015], improving response times and reducing server costs. The resulting system is able to rapidly compute a large number of specialized latent variable models while requiring minimal server resources.
Asynchronous Complex Analytics in a Distributed Dataflow Architecture
Venue: arXiv cs.DB 2015
Year: 2015

Scalable distributed dataflow systems have recently experienced widespread adoption, with commodity dataflow engines such as Hadoop and Spark, and even commodity SQL engines routinely supporting increasingly sophisticated analytics tasks (e.g., support vector machines, logistic regression, collaborative filtering). However, these systems' synchronous (often Bulk Synchronous Parallel) dataflow execution model is at odds with an increasingly important trend in the machine learning community: the use of asynchrony via shared, mutable state (i.e., data races) in convex programming tasks, which has---in a single-node context---delivered noteworthy empirical performance gains and inspired new research into asynchronous algorithms. In this work, we attempt to bridge this gap by evaluating the use of lightweight, asynchronous state transfer within a commodity dataflow engine. Specifically, we investigate the use of asynchronous sideways information passing (ASIP) that presents single-stage parallel iterators with a Volcano-like intra-operator iterator that can be used for asynchronous information passing. We port two synchronous convex programming algorithms, stochastic gradient descent and the alternating direction method of multipliers (ADMM), to use ASIPs. We evaluate an implementation of ASIPs within on Apache Spark that exhibits considerable speedups as well as a rich set of performance trade-offs in the use of these asynchronous algorithms.
Supporting Window Analytics over Large-scale Dynamic Graphs
Venue: arXiv cs.DB 2015
Year: 2015

In relational DBMS, window functions have been widely used to facilitate data analytics. Surprisingly, while similar concepts have been employed for graph analytics, there has been no explicit notions of graph window analytic functions. In this paper, we formally introduce window queries for graph analytics. In such queries, for each vertex, the analysis is performed on a window of vertices defined based on the graph structure. In particular, we identify two instantiations, namely the k-hop window and the topological window. We develop two novel indices, Dense Block index (DBIndex) and Inheritance index (I-Index), to facilitate efficient processing of these two types of windows respectively. Extensive experiments are conducted over both real and synthetic datasets with hundreds of millions of vertices and edges. Experimental results indicate that our proposed index-based query processing solutions achieve four orders of magnitude of query performance gain than the non-index algorithm and are superior over EAGR wrt scalability and efficiency.
Predicting Performance of a Face Recognition System Based on Image Quality
Venue: arXiv cs.CV 2015
Year: 2015

In this dissertation, we present a generative model to capture the relation between facial image quality features (like pose, illumination direction, etc) and face recognition performance. Such a model can be used to predict the performance of a face recognition system. Since the model is based solely on image quality features, performance predictions can be done even before the actual recognition has taken place thereby facilitating many preemptive action. A practical limitation of such a data driven generative model is the limited nature of training data set. To address this limitation, we have developed a Bayesian approach to model the distribution of recognition performance measure based on the number of match and non-match scores in small regions of the image quality space. Random samples drawn from these models provide the initial data essential for training the generative model. Experiment results based on six face recognition systems operating on three independent data sets show that the proposed performance prediction model can accurately predict face recognition performance using an accurate and unbiased Image Quality Assessor (IQA). Furthermore, our results show that variability in the unaccounted quality space -- the image quality features not considered by the IQA -- is the major factor causing inaccuracies in predicted performance.
Space complexity of list H-coloring revisited: the case of oriented trees
Venue: arXiv cs.CC 2015
Year: 2015

Digraphs H for which the list homomorphism problem with template H (LHOM(H)) is in logspace (L) was characterized by Egri et al. (SODA 2014): LHOM(H) is in L if and only if H does not contain a circular N (assuming L is different from NL). Undirected graphs for which LHOM(H) is in L can be characterized in terms forbidden induced subgraphs, and also via a simple inductive construction (Egri et al., STACS 2010). As a consequence, the logspace algorithm in the undirected case is simple and easy to understand. No such forbidden subgraph or inductive characterization, and no such simple and easy-to-understand algorithm is known in the case of digraphs. In this paper, in the case of oriented trees, we refine and strengthen the results of Egri et al. (SODA 2014): we give a characterization of oriented trees T for which LHOM(T) is in L both in terms of forbidden induced subgraphs, and also via a simple inductive construction. Using this characterization, we obtain a simple and easy-to-analyze logspace algorithm for LHOM(T). We also show how these oriented trees can be recognized in time O(|V(T)|^3) (the straightforward implementation of the algorithm given in SODA 2014 runs in time O(|V(H)|^8) for oriented trees). An algebraic characterization of these trees is also provided.
Effects of Feedback Latency on P300-based Brain-computer Interface
Venue: arXiv cs.HC 2015
Year: 2015

Feedback has been shown to affect performance when using a Brain-Computer Interface (BCI) based on sensorimotor rhythms. In contrast, little is known about the influence of feedback on P300-based BCIs. There is still an open question whether feedback affects the regulation of P300 and consequently the operation of P300-based BCIs. In this paper, for the first time, the influence of feedback on the P300-based BCI speller task is systematically assessed. For this purpose, 24 healthy participants performed the classic P300-based BCI speller task, while only half of them received feedback. Importantly, the number of flashes per letter was reduced on a regular basis in order to increase the frequency of providing feedback. Experimental results showed that feedback could significantly improve the P300-based BCI speller performance, if it was provided in short time intervals (e.g. in sequences as short as 4 to 6 flashes per row/column). Moreover, our offline analysis showed that providing feedback remarkably enhanced the relevant ERP patterns and attenuated the irrelevant ERP patterns, such that the discrimination between target and nontarget EEG trials increased.