OpenRaiser/Intern-Atlas huggingface dataset:
On Exact Learning Monotone DNF from Membership Queries
Venue: arXiv cs.LG 2014
Year: 2014

In this paper, we study the problem of learning a monotone DNF with at most $s$ terms of size (number of variables in each term) at most $r$ ($s$ term $r$-MDNF) from membership queries. This problem is equivalent to the problem of learning a general hypergraph using hyperedge-detecting queries, a problem motivated by applications arising in chemical reactions and genome sequencing. We first present new lower bounds for this problem and then present deterministic and randomized adaptive algorithms with query complexities that are almost optimal. All the algorithms we present in this paper run in time linear in the query complexity and the number of variables $n$. In addition, all of the algorithms we present in this paper are asymptotically tight for fixed $r$ and/or $s$.
Virtual Windshields: Merging Reality and Digital Content to Improve the Driving Experience
Venue: arXiv cs.HC 2014
Year: 2014

In recent years, the use of the automobile as the primary mode of transportation has been increasing and driving has become an important part of daily life. Driving is a multi-sensory experience as drivers rely on their senses to provide them with important information. In a vehicular context human senses are all too often limited and obstructed. Today, road accidents constitute the eighth leading cause of death. The escalation of technology has propelled new ways in which driver's senses may be augmented. The enclosed aspect of a car, allied with the configuration of the controls and displays directed towards the driver, offer significant advantages for augmented reality (AR) systems when considering the amount of immersion it can provide to the user. In addition, the inherent mobility and virtually unlimited power autonomy transform cars into perfect mobile computing platforms. However, automobiles currently present limited network connectivity and thus the created augmented objects are merely providing information captured by in-vehicle sensors, cameras and other databases. By combining the new paradigm of Vehicular Ad Hoc Networking (VANET) with AR human machine interfaces, we show that it is possible to design novel cooperative Advanced Driver Assistance Systems (ADAS), that base the creation of AR content on the information collected from neighbouring vehicles or roadside infrastructures. As such we implement prototypes of both visual and acoustic AR systems, which can significantly improve the driving experience. We believe our results contribute to the formulation of a vision where the vehicle is perceived as an extension of the body which permeates the human senses to the world outside the vessel, where the car is used as a better, multi-sensory immersive version of a mobile phone that integrates touch, vision and sound enhancements, leveraging unique properties of VANET.
The Discrete Logarithm problem in the ElGamal cryptosystem over the abelian group U(n) Where n= p^m,or 2p^m
Venue: arXiv cs.CR 2014
Year: 2014

This study is mainly about the discrete logarithm problem in the ElGamal cryptosystem over the abelian group U(n) where n is one of the following forms p^m, or 2p^m where p is an odd large prime and m is a positive integer. It is another good way to deal with the ElGamal Cryptosystem using that abelian group U(n)={x: x is a positive integer such that x<n and gcd(n,x)=1} in the setting of the discrete logarithm problem . Since I show in this paper that this new study maintains equivalent (or better) security with the original ElGamal cryptosystem(invented by Taher ElGamal in 1985)[1], that works over the finite cyclic group of the finite field. It gives a better security because theoretically ElGamal Cryptosystem with U(p^m) or with U(2p^m) is much more secure since the possible solutions for the discrete logarithm will be increased, and that would make this cryptosystem is hard to broken even with thousands of years.
Scale Congestion Control to Ultra-High Speed Ethernet
Venue: arXiv cs.NI 2014
Year: 2014

Currently, Ethernet is broadly used in LAN, datacenter and enterprise networks, storage networks, high performance computing networks and so on. Along with the popularity of Ethernet comes the requirement of enhancing Ethernet with congestion control. On the other hand, Ethernet speed extends to 40Gbps and 100Gbps recently, and even 400Gbps in the near future. The ultra-high speed requires congestion control algorithms to adapt to the broad changes of bandwidth, and highlights the impacts of small delay by enlarging the bandwidth delay product. The state-of-art standard QCN is heuristically designed for the 1Gbps and 10Gbps Ethernet, and unaware of the challenges accompanying the ultra-high speed. To scale congestion control to ultra-high speed Ethernet, we propose the Adaptive Sliding Mode (ASM) congestion control algorithm, which is simple, stable, has fast and smooth convergence process, can tolerate the impacts of delay and adapt to the wide changes of bandwidth. Real experiments and simulations confirm these good properties and show that ASM outperforms QCN. Designing ASM, we find that the derivative of queue length is helpful to rate adjustment because it reflects the difference between bandwidth and aggregated sending rate. We also argue for enforcing congestion control system staying at the congestion boundary line, along which it automatically slides to stable point. These insights are also valuable to develop other congestion control algorithms in ultra-high speed networks.
Some thoughts about benchmarks for NMR
Venue: arXiv cs.AI 2014
Year: 2014

The NMR community would like to build a repository of benchmarks to push forward the design of systems implementing NMR as it has been the case for many other areas in AI. There are a number of lessons which can be learned from the experience of other communi- ties. Here are a few thoughts about the requirements and choices to make before building such a repository.
Finding Largest Rectangles in Convex Polygons
Venue: arXiv cs.CG 2014
Year: 2014

We consider the following geometric optimization problem: find a maximum-area rectangle and a maximum-perimeter rectangle contained in a given convex polygon with $n$ vertices. We give exact algorithms that solve these problems in time $O(n^3)$. We also give $(1-\varepsilon)$-approximation algorithms that take time $O(\varepsilon^{-3/2}+ \varepsilon^{-1/2} \log n)$.
Streaming Kernelization
Venue: arXiv cs.DS 2014
Year: 2014

Kernelization is a formalization of preprocessing for combinatorially hard problems. We modify the standard definition for kernelization, which allows any polynomial-time algorithm for the preprocessing, by requiring instead that the preprocessing runs in a streaming setting and uses $\mathcal{O}(poly(k)\log|x|)$ bits of memory on instances $(x,k)$. We obtain several results in this new setting, depending on the number of passes over the input that such a streaming kernelization is allowed to make. Edge Dominating Set turns out as an interesting example because it has no single-pass kernelization but two passes over the input suffice to match the bounds of the best standard kernelization.
Assessing the statistical significance of association rules
Venue: arXiv cs.DB 2014
Year: 2014

An association rule is statistically significant, if it has a small probability to occur by chance. It is well-known that the traditional frequency-confidence framework does not produce statistically significant rules. It can both accept spurious rules (type 1 error) and reject significant rules (type 2 error). The same problem concerns other commonly used interestingness measures and pruning heuristics. In this paper, we inspect the most common measure functions - frequency, confidence, degree of dependence, $χ^2$, correlation coefficient, and $J$-measure - and redundancy reduction techniques. For each technique, we analyze whether it can make type 1 or type 2 error and the conditions under which the error occurs. In addition, we give new theoretical results which can be use to guide the search for statistically significant association rules.
Design and Optimization of a Speech Recognition Front-End for Distant-Talking Control of a Music Playback Device
Venue: arXiv cs.SD 2014
Year: 2014

This paper addresses the challenging scenario for the distant-talking control of a music playback device, a common portable speaker with four small loudspeakers in close proximity to one microphone. The user controls the device through voice, where the speech-to-music ratio can be as low as -30 dB during music playback. We propose a speech enhancement front-end that relies on known robust methods for echo cancellation, double-talk detection, and noise suppression, as well as a novel adaptive quasi-binary mask that is well suited for speech recognition. The optimization of the system is then formulated as a large scale nonlinear programming problem where the recognition rate is maximized and the optimal values for the system parameters are found through a genetic algorithm. We validate our methodology by testing over the TIMIT database for different music playback levels and noise types. Finally, we show that the proposed front-end allows a natural interaction with the device for limited-vocabulary voice commands.
From Tweets to Events: Exploring a Scalable Solution for Twitter Streams
Venue: arXiv cs.SI 2014
Year: 2014

The unprecedented use of social media through smartphones and other web-enabled mobile devices has enabled the rapid adoption of platforms like Twitter. Event detection has found many applications on the web, including breaking news identification and summarization. The recent increase in the usage of Twitter during crises has attracted researchers to focus on detecting events in tweets. However, current solutions have focused on static Twitter data. The necessity to detect events in a streaming environment during fast paced events such as a crisis presents new opportunities and challenges. In this paper, we investigate event detection in the context of real-time Twitter streams as observed in real-world crises. We highlight the key challenges in this problem: the informal nature of text, and the high volume and high velocity characteristics of Twitter streams. We present a novel approach to address these challenges using single-pass clustering and the compression distance to efficiently detect events in Twitter streams. Through experiments on large Twitter datasets, we demonstrate that the proposed framework is able to detect events in near real-time and can scale to large and noisy Twitter streams.
Analysis Tool for UNL-Based Knowledge Representation
Venue: arXiv cs.AI 2014
Year: 2014

The fundamental issue in knowledge representation is to provide a precise definition of the knowledge that they possess in a manner that is independent of procedural considerations, context free and easy to manipulate, exchange and reason about. Knowledge must be accessible to everyone regardless of their native languages. Universal Networking Language (UNL) is a declarative formal language and a generalized form of human language in a machine independent digital platform for defining, recapitulating, amending, storing and dissipating knowledge among people of different affiliations. UNL extracts semantic data from a native language for Interlingua machine translation. This paper presents the development of a graphical tool that incorporates UNL to provide a visual mean to represent the semantic data available in a native text. UNL represents the semantics of a sentence as a conceptual hyper-graph. We translate this information into XML format and create a graph from XML, representing the actual concepts available in the native language
Training Restricted Boltzmann Machine by Perturbation
Venue: arXiv cs.NE 2014
Year: 2014

A new approach to maximum likelihood learning of discrete graphical models and RBM in particular is introduced. Our method, Perturb and Descend (PD) is inspired by two ideas (I) perturb and MAP method for sampling (II) learning by Contrastive Divergence minimization. In contrast to perturb and MAP, PD leverages training data to learn the models that do not allow efficient MAP estimation. During the learning, to produce a sample from the current model, we start from a training data and descend in the energy landscape of the "perturbed model", for a fixed number of steps, or until a local optima is reached. For RBM, this involves linear calculations and thresholding which can be very fast. Furthermore we show that the amount of perturbation is closely related to the temperature parameter and it can regularize the model by producing robust features resulting in sparse hidden layer activation.
Revisit Behavior in Social Media: The Phoenix-R Model and Discoveries
Venue: arXiv cs.SI 2014
Year: 2014

How many listens will an artist receive on a online radio? How about plays on a YouTube video? How many of these visits are new or returning users? Modeling and mining popularity dynamics of social activity has important implications for researchers, content creators and providers. We here investigate the effect of revisits (successive visits from a single user) on content popularity. Using four datasets of social activity, with up to tens of millions media objects (e.g., YouTube videos, Twitter hashtags or LastFM artists), we show the effect of revisits in the popularity evolution of such objects. Secondly, we propose the Phoenix-R model which captures the popularity dynamics of individual objects. Phoenix-R has the desired properties of being: (1) parsimonious, being based on the minimum description length principle, and achieving lower root mean squared error than state-of-the-art baselines; (2) applicable, the model is effective for predicting future popularity values of objects.
Robust iterative hard thresholding for compressed sensing
Venue: arXiv cs.IT 2014
Year: 2014

Compressed sensing (CS) or sparse signal reconstruction (SSR) is a signal processing technique that exploits the fact that acquired data can have a sparse representation in some basis. One popular technique to reconstruct or approximate the unknown sparse signal is the iterative hard thresholding (IHT) which however performs very poorly under non-Gaussian noise conditions or in the face of outliers (gross errors). In this paper, we propose a robust IHT method based on ideas from $M$-estimation that estimates the sparse signal and the scale of the error distribution simultaneously. The method has a negligible performance loss compared to IHT under Gaussian noise, but superior performance under heavy-tailed non-Gaussian noise conditions.
Stream processing components: Isabelle/HOL formalisation and case studies
Venue: arXiv cs.SE 2014
Year: 2014

This set of theories presents an Isabelle/HOL+Isar formalisation of stream processing components introduces in Focus, a framework for formal specification and development of interactive systems. This is an extended and updated version of the formalisation, which was elaborated within the methodology 'Focus on Isabelle'. In addition, we also applied the formalisation on three case studies that cover different application areas: process control (Steam Boiler System), data transmission (FlexRay communication protocol), memory and processing components (Automotive-Gateway System).
Compliant motion control for handling a single object by two similar industrial robots
Venue: arXiv cs.RO 2014
Year: 2014

In this paper, we propose a compliant motion control strategy for handling a single object by two similar industrial robots. The dynamics of the object carried by the two robots is assimilated to the dynamics of a mass-spring-damper system described by a piecewise linear model (PWA). The coordination of the two robots is accomplished using a master slave synchronization approach dedicated for PWA systems, based on the Lyapunov theory, and solved via Linear Matrix Inequalities (LMIs). The performances of the proposed approach are proved by simulation results and compared to a related approach.
Modelling Delegation and Revocation Schemes in IDP
Venue: arXiv cs.LO 2014
Year: 2014

In ownership-based access control frameworks with the possibility of delegating permissions and administrative rights, chains of delegated accesses will form. There are different ways to treat these delegation chains when revoking rights, which give rise to different revocation schemes. In this paper, we show how IDP - a knowledge base system that integrates technology from ASP, SAT and CP - can be used to efficiently implement executable revocation schemes for an ownership-based access control system based on a declarative specification of their properties.
Computability and Complexity over the Product Topology of Real Numbers
Venue: arXiv cs.LO 2014
Year: 2014

Kawamura and Cook have developed a framework for studying the computability and complexity theoretic problems over "large" topological spaces. This framework has been applied to study the complexity of the differential operator and the complexity of functionals over the space of continuous functions on the unit interval $C[0,1]$. In this paper we apply the ideas of Kawamura and Cook to the product space of the real numbers endowed with the product topology. We show that no computable norm can be defined over such topology. We investigate computability and complexity of total functions over the product space in two cases: (1) when the computing machine submits a uniformally bounded number of queries to the oracle and (2) when the number of queries submitted by the machine is not uniformally bounded. In the first case we show that the function over the product space can be reduced to a function over a finite-dimensional space. However, in general there exists functions whose computing machines must submit a non-uniform number of queries to the oracle indicating that computing over the product topology can not in general be reduced to computing over finite-dimensional spaces.
Evaluation of A Resilience Embedded System Using Probabilistic Model-Checking
Venue: arXiv cs.SE 2014
Year: 2014

If a Micro Processor Unit (MPU) receives an external electric signal as noise, the system function will freeze or malfunction easily. A new resilience strategy is implemented in order to reset the MPU automatically and stop the MPU from freezing or malfunctioning. The technique is useful for embedded systems which work in non-human environments. However, evaluating resilience strategies is difficult because their effectiveness depends on numerous, complex, interacting factors. In this paper, we use probabilistic model checking to evaluate the embedded systems installed with the above mentioned new resilience strategy. Qualitative evaluations are implemented with 6 PCTL formulas, and quantitative evaluations use two kinds of evaluation. One is system failure reduction, and the other is ADT (Average Down Time), the industry standard. Our work demonstrates the benefits brought by the resilience strategy. Experimental results indicate that our evaluation is cost-effective and reliable.
Logic and Constraint Logic Programming for Distributed Constraint Optimization
Venue: arXiv cs.MA 2014
Year: 2014

The field of Distributed Constraint Optimization Problems (DCOPs) has gained momentum, thanks to its suitability in capturing complex problems (e.g., multi-agent coordination and resource allocation problems) that are naturally distributed and cannot be realistically addressed in a centralized manner. The state of the art in solving DCOPs relies on the use of ad-hoc infrastructures and ad-hoc constraint solving procedures. This paper investigates an infrastructure for solving DCOPs that is completely built on logic programming technologies. In particular, the paper explores the use of a general constraint solver (a constraint logic programming system in this context) to handle the agent-level constraint solving. The preliminary experiments show that logic programming provides benefits over a state-of-the-art DCOP system, in terms of performance and scalability, opening the doors to the use of more advanced technology (e.g., search strategies and complex constraints) for solving DCOPs.
Opportunities in a Federated Cloud Marketplace
Venue: arXiv cs.NI 2014
Year: 2014

Recent measurement studies show that there are massively distributed hosting and computing infrastructures deployed in the Internet. Such infrastructures include large data centers and organizations' computing clusters. When idle, these resources can readily serve local users. Such users can be smartphone or tablet users wishing to access services such as remote desktop or CPU/bandwidth intensive activities. Particularly, when they are likely to have high latency to access, or may have no access at all to, centralized cloud providers. Today, however, there is no global marketplace where sellers and buyers of available resources can trade. The recently introduced marketplaces of Amazon and other cloud infrastructures are limited by the network footprint of their own infrastructures and availability of such services in the target country and region. In this article we discuss the potentials for a federated cloud marketplace where sellers and buyers of a number of resources, including storage, computing, and network bandwidth, can freely trade. This ecosystem can be regulated through brokers who act as service level monitors and auctioneers. We conclude by discussing the challenges and opportunities in this space.
A Retrieval Mechanism for Multi-versioned Digital Collection Using TAG
Venue: arXiv cs.IR 2014
Year: 2014

As the marvellous growth of the digital library in each year, the problems with indexing and searching a digital library is increased in a high rate. When the researchers search for the earlier versions, only a few recent versions in the back volumes can be retrieved soon. It is unpredictable that researchers require the earlier versions in a specific boundary. In order to facilitate the researchers, who may access any version at any time, we propose a VTAG technique for indexing. Our experiments indicate that the proposed retrieval technique, VTAG, effectively retrieves any version in considerable amount of time than the existing method.
Asymptotic and Numerical Analysis of Multiserver Retrial Queue with Guard Channel for Cellular Networks
Venue: arXiv cs.PF 2014
Year: 2014

This paper considers a retrial queueing model for a base station in cellular networks where fresh calls and handover calls are available. Fresh calls are initiated from the cell of the base station. On the other hand, a handover call has been connecting to a base station and moves to another one. In order to keep the continuation of the communication, it is desired that an available channel in the new base station is immediately assigned to the handover call. To this end, a channel is reserved as the guard channel for handover calls in base stations. Blocked fresh and handover calls join a virtual orbit and repeat their attempts in a later time. We assume that a base station can recognize retrial calls and give them the same priority as that of handover calls. We model a base station by a multiserver retrial queue with priority customers for which a level-dependent QBD process is formulated. We obtain Taylor series expansion for the nonzero elements of the rate matrices of the level-dependent QBD. Using the expansion results, we obtain an asymptotic upper bound for the joint stationary distribution of the number of busy channels and that of customers in the orbit. Furthermore, we derive an efficient numerical algorithm to calculate the joint stationary distribution.