OpenRaiser/Intern-Atlas huggingface dataset:
Designing A Composite Dictionary Adaptively From Joint Examples
Venue: arXiv cs.CV 2015
Year: 2015

We study the complementary behaviors of external and internal examples in image restoration, and are motivated to formulate a composite dictionary design framework. The composite dictionary consists of the global part learned from external examples, and the sample-specific part learned from internal examples. The dictionary atoms in both parts are further adaptively weighted to emphasize their model statistics. Experiments demonstrate that the joint utilization of external and internal examples leads to substantial improvements, with successful applications in image denoising and super resolution.
From Group Recommendations to Group Formation
Venue: arXiv cs.IR 2015
Year: 2015

There has been significant recent interest in the area of group recommendations, where, given groups of users of a recommender system, one wants to recommend top-k items to a group that maximize the satisfaction of the group members, according to a chosen semantics of group satisfaction. Examples semantics of satisfaction of a recommended itemset to a group include the so-called least misery (LM) and aggregate voting (AV). We consider the complementary problem of how to form groups such that the users in the formed groups are most satisfied with the suggested top-k recommendations. We assume that the recommendations will be generated according to one of the two group recommendation semantics - LM or AV. Rather than assuming groups are given, or rely on ad hoc group formation dynamics, our framework allows a strategic approach for forming groups of users in order to maximize satisfaction. We show that the problem is NP-hard to solve optimally under both semantics. Furthermore, we develop two efficient algorithms for group formation under LM and show that they achieve bounded absolute error. We develop efficient heuristic algorithms for group formation under AV. We validate our results and demonstrate the scalability and effectiveness of our group formation algorithms on two large real data sets.
An RFID-based Clinical Information System for Identification and Monitoring of Patients
Venue: arXiv cs.CY 2015
Year: 2015

Managing health-care records and information is an imperative necessity. Most patient health records are stored in separate systems and there are still huge paper trails of records that health-care providers must keep to comply with different regulations. This paper proposes an RFID-based system, named SIMOPAC, that integrate RFID technology in health care in order to make patient emergency care as efficient and risk-free as possible, by providing doctors with as much information about a patient as quickly as possible. Every hospital could use SIMOPAC with their existing system in order to promote patient safety and optimize hospital workflow. We will concentrate on the RFID technology and how it could be used in emergency care. We describe a general purpose architecture and data model that is designed for collecting ambulatory data from various existing devices and systems, as well as for storing and presenting clinically significant information to the emergency care physician.
Local Distribution and the Symmetry Gap: Approximability of Multiway Partitioning Problems
Venue: arXiv cs.DS 2015
Year: 2015

We study the approximability of multiway partitioning problems, examples of which include Multiway Cut, Node-weighted Multiway Cut, and Hypergraph Multiway Cut. We investigate these problems from the point of view of two possible generalizations: as Min-CSPs, and as Submodular Multiway Partition problems. These two generalizations lead to two natural relaxations, the Basic LP, and the Lovasz relaxation. We show that the Lovasz relaxation gives a (2-2/k)-approximation for Submodular Multiway Partition with $k$ terminals, improving a recent 2-approximation. We prove that this factor is optimal in two senses: (1) A (2-2/k-ε)-approximation for Submodular Multiway Partition with k terminals would require exponentially many value queries. (2) For Hypergraph Multiway Cut and Node-weighted Multiway Cut with k terminals, both special cases of Submodular Multiway Partition, we prove that a (2-2/k-ε)-approximation is NP-hard, assuming the Unique Games Conjecture. Both our hardness results are more general: (1) We show that the notion of symmetry gap, previously used for submodular maximization problems, also implies hardness results for submodular minimization problems. (2) Assuming the Unique Games Conjecture, we show that the Basic LP gives an optimal approximation for every Min-CSP that includes the Not-Equal predicate. Finally, we connect the two hardness techniques by proving that the integrality gap of the Basic LP coincides with the symmetry gap of the multilinear relaxation (for a related instance). This shows that the appearance of the same hardness threshold for a Min-CSP and the related submodular minimization problem is not a coincidence.
A Switched Dynamical System Framework for Analysis of Massively Parallel Asynchronous Numerical Algorithms
Venue: arXiv cs.SY 2015
Year: 2015

In the near future, massively parallel computing systems will be necessary to solve computation intensive applications. The key bottleneck in massively parallel implementation of numerical algorithms is the synchronization of data across processing elements (PEs) after each iteration, which results in significant idle time. Thus, there is a trend towards relaxing the synchronization and adopting an asynchronous model of computation to reduce idle time. However, it is not clear what is the effect of this relaxation on the stability and accuracy of the numerical algorithm. In this paper we present a new framework to analyze such algorithms. We treat the computation in each PE as a dynamical system and model the asynchrony as stochastic switching. The overall system is then analyzed as a switched dynamical system. However, modeling of massively parallel numerical algorithms as switched dynamical systems results in a very large number of modes, which makes current analysis tools available for such systems computationally intractable. We develop new techniques that circumvent this scalability issue. The framework is presented on a one-dimensional heat equation as a case study and the proposed analysis framework is verified by solving the partial differential equation (PDE) in a $\mathtt{nVIDIA\: Tesla^{\scriptsize{TM}}}$ GPU machine, with asynchronous communication between cores.
Full-Duplex Cognitive Radio: A New Design Paradigm for Enhancing Spectrum Usage
Venue: arXiv cs.NI 2015
Year: 2015

With the rapid growth of demand for ever-increasing data rate, spectrum resources have become more and more scarce. As a promising technique to increase the efficiency of the spectrum utilization, cognitive radio (CR) technique has the great potential to meet such a requirement by allowing un-licensed users to coexist in licensed bands. In conventional CR systems, the spectrum sensing is performed at the beginning of each time slot before the data transmission. This unfortunately results in two major problems: 1) transmission time reduction due to sensing, and 2) sensing accuracy impairment due to data transmission. To tackle these problems, in this paper we present a new design paradigm for future CR by exploring the full-duplex (FD) techniques to achieve the simultaneous spectrum sensing and data transmission. With FD radios equipped at the secondary users (SUs), SUs can simultaneously sense and access the vacant spectrum, and thus, significantly improve sensing performances and meanwhile increase data transmission efficiency. The aim of this article is to transform the promising conceptual framework into the practical wireless network design by addressing a diverse set of challenges such as protocol design and theoretical analysis. Several application scenarios with FD enabled CR are elaborated, and key open research directions and novel algorithms in these systems are discussed.
Interactive Restless Multi-armed Bandit Game and Swarm Intelligence Effect
Venue: arXiv cs.AI 2015
Year: 2015

We obtain the conditions for the emergence of the swarm intelligence effect in an interactive game of restless multi-armed bandit (rMAB). A player competes with multiple agents. Each bandit has a payoff that changes with a probability $p_{c}$ per round. The agents and player choose one of three options: (1) Exploit (a good bandit), (2) Innovate (asocial learning for a good bandit among $n_{I}$ randomly chosen bandits), and (3) Observe (social learning for a good bandit). Each agent has two parameters $(c,p_{obs})$ to specify the decision: (i) $c$, the threshold value for Exploit, and (ii) $p_{obs}$, the probability for Observe in learning. The parameters $(c,p_{obs})$ are uniformly distributed. We determine the optimal strategies for the player using complete knowledge about the rMAB. We show whether or not social or asocial learning is more optimal in the $(p_{c},n_{I})$ space and define the swarm intelligence effect. We conduct a laboratory experiment (67 subjects) and observe the swarm intelligence effect only if $(p_{c},n_{I})$ are chosen so that social learning is far more optimal than asocial learning.
Totally Distributed Energy-Efficient Transmission in MIMO Interference Channels
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we consider the problem of maximizing the energy efficiency (EE) for multi-input multi-output (MIMO) interference channels, subject to the per-link power constraint. To avoid extensive information exchange among all links, the optimization problem is formulated as a noncooperative game, where each link maximizes its own EE. We show that this game always admits a Nash equilibrium (NE) and the sufficient condition for the uniqueness of the NE is derived for the case of arbitrary channel matrices, which can be checked in practice. To reach the NE of this game, we develop a totally distributed EE algorithm, in which each link updates its own transmit covariance matrix in a completely distributed and asynchronous way: Some players may update their solutions more frequently than others or even use the outdated interference information. The sufficient conditions that guarantee the global convergence of the proposed algorithm to the NE of the game have been given as well. We also study the impact of the circuit power consumption on the sum-EE performance of the proposed algorithm in the case when the links are separated sufficiently far away. Moreover, the tradeoff between the sum-EE and the sum-spectral efficiency (SE) is investigated with the proposed algorithm under two special cases: 1) low transmit power constraint regime; 2) high transmit power constraint regime. Finally, extensive simulations are conducted to evaluate the impact of various system parameters on the system performance.
Some Comments on the Stochastic Eulerian Tour Problem
Venue: arXiv cs.DS 2015
Year: 2015

The Stochastic Eulerian Tour Problem was introduced in 2008 as a stochastic variant of the well-known Eulerian Tour Problem. In a follow-up paper the same authors investigated some heuristics for solving the Stochastic Eulerian Tour Problem. After a thorough study of these two publications a few issues emerged. In this short research commentary we would like to discuss these issues.
Novel Super-Resolution Method Based on High Order Nonlocal-Means
Venue: arXiv cs.IT 2015
Year: 2015

Super-resolution without explicit sub-pixel motion estimation is a very active subject of image reconstruction containing general motion. The Non-Local Means (NLM) method is a simple image reconstruction method without explicit motion estimation. In this paper we generalize NLM method to higher orders using kernel regression can apply to super-resolution reconstruction. The performance of the generalized method is compared with other methods.
ICT and RFID in Education: Some Practical Aspects in Campus Life
Venue: arXiv cs.CY 2015
Year: 2015

The paper summarizes our preliminary findings regarding the development and implementation of a newly proposed system based on ICT and RFID (Radio Frequency Identification) technologies for campus access and facility usage. It is generally acknowledged that any educational environment is highly dependent upon a wide range of resources or variables such as teaching staff, research and study areas, meeting and accommodation facilities, library services, restaurant and leisure facilities, etc. The system we have devised using ICT and RFID technologies supports not only authentic transactions among all university departments, but also interconnects all levels of academic life and activity. Thus, the utility of the system ranges from access control (student/ staff/ visitor identification), attendance tracking, library check-out services and voting to grade book consulting, inventory, cashless vending, parking, laundry and copying services. Physically, the system consists of several RFID gates/readers, a data server and some network stations, all of them requiring specific structuring and integration solutions. The system is quite different from already existing ones in that it proposes an innovative access solution. Thus, the search of the ID card holder in a database has been replaced by local processing. Since one and the same card is employed to perform a variety of operations, the system has immediate and numerous utilizations.
Learning Mixed Membership Community Models in Social Tagging Networks through Tensor Methods
Venue: arXiv cs.LG 2015
Year: 2015

Community detection in graphs has been extensively studied both in theory and in applications. However, detecting communities in hypergraphs is more challenging. In this paper, we propose a tensor decomposition approach for guaranteed learning of communities in a special class of hypergraphs modeling social tagging systems or folksonomies. A folksonomy is a tripartite 3-uniform hypergraph consisting of (user, tag, resource) hyperedges. We posit a probabilistic mixed membership community model, and prove that the tensor method consistently learns the communities under efficient sample complexity and separation requirements.
Variability Abstractions: Trading Precision for Speed in Family-Based Analyses (Extended Version)
Venue: arXiv cs.PL 2015
Year: 2015

Family-based (lifted) data-flow analysis for Software Product Lines (SPLs) is capable of analyzing all valid products (variants) without generating any of them explicitly. It takes as input only the common code base, which encodes all variants of a SPL, and produces analysis results corresponding to all variants. However, the computational cost of the lifted analysis still depends inherently on the number of variants (which is exponential in the number of features, in the worst case). For a large number of features, the lifted analysis may be too costly or even infeasible. In this paper, we introduce variability abstractions defined as Galois connections and use abstract interpretation as a formal method for the calculational-based derivation of approximate (abstracted) lifted analyses of SPL programs, which are sound by construction. Moreover, given an abstraction we define a syntactic transformation that translates any SPL program into an abstracted version of it, such that the analysis of the abstracted SPL coincides with the corresponding abstracted analysis of the original SPL. We implement the transformation in a tool, reconfigurator that works on Object-Oriented Java program families, and evaluate the practicality of this approach on three Java SPL benchmarks.
Minimum Equivalent Precedence Relation Systems
Venue: arXiv cs.DS 2015
Year: 2015

In this paper two related simplification problems for systems of linear inequalities describing precedence relation systems are considered. Given a precedence relation system, the first problem seeks a minimum subset of the precedence relations (i.e., inequalities) which has the same solution set as that of the original system. The second problem is the same as the first one except that the ``subset restriction'' in the first problem is removed. This paper establishes that the first problem is NP-hard. However, a sufficient condition is provided under which the first problem is solvable in polynomial-time. In addition, a decomposition of the first problem into independent tractable and intractable subproblems is derived. The second problem is shown to be solvable in polynomial-time, with a full parameterization of all solutions described. The results in this paper generalize those in [Moyles and Thompson 1969, Aho, Garey, and Ullman 1972] for the minimum equivalent graph problem and transitive reduction problem, which are applicable to unweighted directed graphs.
A Context-Based Semantics for SPARQL Property Paths over the Web (Extended Version)
Venue: arXiv cs.DB 2015
Year: 2015

As of today, there exists no standard language for querying Linked Data on the Web, where navigation across distributed data sources is a key feature. A natural candidate seems to be SPARQL, which recently has been enhanced with navigational capabilities thanks to the introduction of property paths (PPs). However, the semantics of SPARQL restricts the scope of navigation via PPs to single RDF graphs. This restriction limits the applicability of PPs on the Web. To fill this gap, in this paper we provide formal foundations for evaluating PPs on the Web, thus contributing to the definition of a query language for Linked Data. In particular, we introduce a query semantics for PPs that couples navigation at the data level with navigation on the Web graph. Given this semantics we find that for some PP-based SPARQL queries a complete evaluation on the Web is not feasible. To enable systems to identify queries that can be evaluated completely, we establish a decidable syntactic property of such queries.
Use of Effective Audio in E-learning Courseware
Venue: arXiv cs.CY 2015
Year: 2015

E-Learning uses electronic media, information & communication technologies to provide education to the masses. E-learning deliver hypertext, text, audio, images, animation and videos using desktop standalone computer, local area network based intranet and internet based contents. While producing an e-learning content or course-ware, a major decision making factor is whether to use audio for the benefit of the end users. Generally, three types of audio can be used in e-learning: narration, music and sound effect. This paper shows that the use of proper audio based on contents type and subject can make the content more interesting as well as help the end users to better understand the contents.
GeomRDF: A Geodata Converter with a Fine-Grained Structured Representation of Geometry in the Web
Venue: arXiv cs.DB 2015
Year: 2015

In recent years, with the advent of the web of data, a growing number of national mapping agencies tend to publish their geospatial data as Linked Data. However, differences between traditional GIS data models and Linked Data model can make the publication process more complicated. Besides, it may require, to be done, the setting of several parameters and some expertise in the semantic web technologies. In addition, the use of standards like GeoSPARQL (or ad hoc predicates) is mandatory to perform spatial queries on published geospatial data. In this paper, we present GeomRDF, a tool that helps users to convert spatial data from traditional GIS formats to RDF model easily. It generates geometries represented as GeoSPARQL WKT literal but also as structured geometries that can be exploited by using only the RDF query language, SPARQL. GeomRDF was implemented as a module in the RDF publication platform Datalift. A validation of GeomRDF has been realized against the French administrative units dataset (provided by IGN France).
Identifying a Criminal's Network of Trust
Venue: arXiv cs.SI 2015
Year: 2015

Tracing criminal ties and mining evidence from a large network to begin a crime case analysis has been difficult for criminal investigators due to large numbers of nodes and their complex relationships. In this paper, trust networks using blind carbon copy (BCC) emails were formed. We show that our new shortest paths network search algorithm combining shortest paths and network centrality measures can isolate and identify criminals' connections within a trust network. A group of BCC emails out of 1,887,305 Enron email transactions were isolated for this purpose. The algorithm uses two central nodes, most influential and middle man, to extract a shortest paths trust network.
Liquid Intersection Types
Venue: arXiv cs.PL 2015
Year: 2015

We present a new type system combining refinement types and the expressiveness of intersection type discipline. The use of such features makes it possible to derive more precise types than in the original refinement system. We have been able to prove several interesting properties for our system (including subject reduction) and developed an inference algorithm, which we proved to be sound.
A Model of Layered Architectures
Venue: arXiv cs.SE 2015
Year: 2015

Architectural styles and patterns play an important role in software engineering. One of the most known ones is the layered architecture style. However, this style is usually only stated informally, which may cause problems such as ambiguity, wrong conclusions, and difficulty when checking the conformance of a system to the style. We address these problems by providing a formal, denotational semantics of the layered architecture style. Mainly, we present a sufficiently abstract and rigorous description of layered architectures. Loosely speaking, a layered architecture consists of a hierarchy of layers, in which services communicate via ports. A layer is modeled as a relation between used and provided services, and layer composition is defined by means of relational composition. Furthermore, we provide a formal definition for the notions of syntactic and semantic dependency between the layers. We show that these dependencies are not comparable in general. Moreover, we identify sufficient conditions under which, in an intuitive sense which we make precise in our treatment, the semantic dependency implies, is implied by, or even coincides with the reflexive-transitive closure of the syntactic dependency. Our results provide a technology-independent characterization of the layered architecture style, which may be used by software architects to ensure that a system is indeed built according to that style.
Molecular MIMO Communication Link
Venue: arXiv cs.ET 2015
Year: 2015

In this demonstration, we will present the world's first molecular multiple-input multiple-output (MIMO) communication link to deliver two data streams in a spatial domain. We show that chemical signals such as concentration gradients could be used in MIMO fashion to transfer sequential data. Until now it was unclear whether MIMO techniques, which are used extensively in modern radio communication, could be applied to molecular communication. In the demonstration, using our devised MIMO apparatus and carefully designed detection algorithm, we will show that we can achieve about 1.7 times higher data rate than single input single output (SISO) molecular communication systems.