OpenRaiser/Intern-Atlas huggingface dataset:
Truth Finding on the Deep Web: Is the Problem Solved?
Venue: arXiv cs.DB 2015
Year: 2015

The amount of useful information available on the Web has been growing at a dramatic pace in recent years and people rely more and more on the Web to fulfill their information needs. In this paper, we study truthfulness of Deep Web data in two domains where we believed data are fairly clean and data quality is important to people's lives: {\em Stock} and {\em Flight}. To our surprise, we observed a large amount of inconsistency on data from different sources and also some sources with quite low accuracy. We further applied on these two data sets state-of-the-art {\em data fusion} methods that aim at resolving conflicts and finding the truth, analyzed their strengths and limitations, and suggested promising research directions. We wish our study can increase awareness of the seriousness of conflicting data on the Web and in turn inspire more research in our community to tackle this problem.
Reducing ADC Sampling Rate with Compressive Sensing
Venue: arXiv cs.IT 2015
Year: 2015

Many communication systems involve high bandwidth, while sparse, radio frequency (RF) signals. Working with high frequency signals requires appropriate system-level components such as high-speed analog-to-digital converters (ADC). In particular, an analog signal should be sampled at rates that meet the Nyquist requirements to avoid aliasing. However, implementing high-speed ADC devices can be a limiting factor as well as expensive. To mitigate the caveats with high-speed ADC, the solution space can be explored in several dimensions such as utilizing the compressive sensing (CS) framework in order to reduce the sampling rate to the order of information rate of the signal rather than a rate dictated by the Nyquist. In this note, we review the compressive sensing structure and its extensions for continuous-time signals, which is ultimately used to reduce the sampling rate of high-speed ADC devices. Moreover, we consider the application of the compressive sensing framework in wireless sensor networks to save power by reducing the transmission rate of sensor nodes. We propose an alternative solution for the CS minimization problem that can be solved using gradient descent methods. The modified minimization problem is potentially faster and simpler to implement at the hardware level.
Computing in continuous space with self-assembling polygonal tiles
Venue: arXiv cs.CG 2015
Year: 2015

In this paper we investigate the computational power of the polygonal tile assembly model (polygonal TAM) at temperature 1, i.e. in non-cooperative systems. The polygonal TAM is an extension of Winfree's abstract tile assembly model (aTAM) which not only allows for square tiles (as in the aTAM) but also allows for tile shapes that are polygons. Although a number of self-assembly results have shown computational universality at temperature 1, these are the first results to do so by fundamentally relying on tile placements in continuous, rather than discrete, space. With the square tiles of the aTAM, it is conjectured that the class of temperature 1 systems is not computationally universal. Here we show that the class of systems whose tiles are composed of a regular polygon P with n > 6 sides is computationally universal. On the other hand, we show that the class of systems whose tiles consist of a regular polygon P with n <= 6 cannot compute using any known techniques. In addition, we show a number of classes of systems whose tiles consist of a non-regular polygon with n >= 3 sides are computationally universal.
NEXP-completeness and Universal Hardness Results for Justification Logic
Venue: arXiv cs.LO 2015
Year: 2015

We provide a lower complexity bound for the satisfiability problem of a multi-agent justification logic, establishing that the general NEXP upper bound from our previous work is tight. We then use a simple modification of the corresponding reduction to prove that satisfiability for all multi-agent justification logics from there is hard for the Sigma 2 p class of the second level of the polynomial hierarchy - given certain reasonable conditions. Our methods improve on these required conditions for the same lower bound for the single-agent justification logics, proven by Buss and Kuznets in 2009, thus answering one of their open questions.
A New Chaos-Based Cryptosystem for Secure Transmitted Images
Venue: arXiv cs.CR 2015
Year: 2015

This paper presents a novel and robust chaos-based cryptosystem for secure transmitted images and four other versions. In the proposed block encryption/decryption algorithm, a 2D chaotic map is used to shuffle the image pixel positions. Then, substitution (confusion) and permutation (diffusion) operations on every block, with multiple rounds, are combined using two perturbed chaotic PWLCM maps. The perturbing orbit technique improves the statistical properties of encrypted images. The obtained error propagation in various standard cipher block modes demonstrates that the proposed cryptosystem is suitable to transmit cipher data over a corrupted digital channel. Finally, to quantify the security level of the proposed cryptosystem, many tests are performed and experimental results show that the suggested cryptosystem has a high security level.
Phylogenetic incongruence through the lens of Monadic Second Order logic
Venue: arXiv cs.DS 2015
Year: 2015

Within the field of phylogenetics there is growing interest in measures for summarising the dissimilarity, or 'incongruence', of two or more phylogenetic trees. Many of these measures are NP-hard to compute and this has stimulated a considerable volume of research into fixed parameter tractable algorithms. In this article we use Monadic Second Order logic (MSOL) to give alternative, compact proofs of fixed parameter tractability for several well-known incongruency measures. In doing so we wish to demonstrate the considerable potential of MSOL - machinery still largely unknown outside the algorithmic graph theory community - within phylogenetics. A crucial component of this work is the observation that many of these measures, when bounded, imply the existence of an 'agreement forest' of bounded size, which in turn implies that an auxiliary graph structure, the display graph, has bounded treewidth. It is this bound on treewidth that makes the machinery of MSOL available for proving fixed parameter tractability. We give a variety of different MSOL formulations. Some are based on explicitly encoding agreement forests, while some only use them implicitly to generate the treewidth bound. Our formulations introduce a number of "phylogenetics MSOL primitives" which will hopefully be of use to other researchers.
Gridless Quadrature Compressive Sampling with Interpolated Array Technique
Venue: arXiv cs.IT 2015
Year: 2015

Quadrature compressive sampling (QuadCS) is a sub-Nyquist sampling scheme for acquiring in-phase and quadrature (I/Q) components in radar. In this scheme, the received intermediate frequency (IF) signals are expressed as a linear combination of time-delayed and scaled replicas of the transmitted waveforms. For sparse IF signals on discrete grids of time-delay space, the QuadCS can efficiently reconstruct the I/Q components from sub-Nyquist samples. In practice, the signals are characterized by a set of unknown time-delay parameters in a continuous space. Then conventional sparse signal reconstruction will deteriorate the QuadCS reconstruction performance. This paper focuses on the reconstruction of the I/Q components with continuous delay parameters. A parametric spectrum-matched dictionary is defined, which sparsely describes the IF signals in the frequency domain by delay parameters and gain coefficients, and the QuadCS system is reexamined under the new dictionary. With the inherent structure of the QuadCS system, it is found that the estimation of delay parameters can be decoupled from that of sparse gain coefficients, yielding a beamspace direction-of-arrival (DOA) estimation formulation with a time-varying beamforming matrix. Then an interpolated beamspace DOA method is developed to perform the DOA estimation. An optimal interpolated array is established and sufficient conditions to guarantee the successful estimation of the delay parameters are derived. With the estimated delays, the gain coefficients can be conveniently determined by solving a linear least-squares problem. Extensive simulations demonstrate the superior performance of the proposed algorithm in reconstructing the sparse signals with continuous delay parameters.
A Novel Framework for Intelligent Information Retrieval in Wireless Sensor Networks
Venue: arXiv cs.IR 2015
Year: 2015

Recent advances in the development of the low-cost, power-efficient embedded devices, coupled with the rising need for support of new information processing paradigms such as smart spaces and military surveillance systems, have led to active research in large-scale, highly distributed sensor networks of small, wireless, low-power, unattended sensors and actuators. While applications keep diversifying, one common property they share is the need for an efficient network architecture tailored towards information retrieval in sensor networks. Previous solutions designed for traditional networks serve as good references; however, due to the vast differences between previous paradigms and needs of sensor networks, a framework is required to gather and impart only the required information .To achieve this goal in this paper we have proposed a framework for intelligent information retrieval and dissemination to desired destination node. The proposed frame work combines three major concern areas in WSNs i.e. data aggregation, information retrieval and data dissemination in a single scenario. In the proposed framework data aggregation is responsible for combining information from all nodes and removing the redundant data. Information retrieval filters the processed data to obtain final information termed as intelligent data to be disseminated to the required destination node.
Real-Time Model Checking Support for AADL
Venue: arXiv cs.SE 2015
Year: 2015

We describe a model-checking toolchain for the behavioral verification of AADL models that takes into account the realtime semantics of the language and that is compatible with the AADL Behavioral Annex. We give a high-level view of the tools and transformations involved in the verification process and focus on the support offered by our framework for checking user-defined properties. We also describe the experimental results obtained on a significant avionic demonstrator, that models a network protocol in charge of data communications between an airplane and ground stations.
Switching control for tracking of a hybrid position-force trajectory
Venue: arXiv cs.RO 2015
Year: 2015

This work proposes a control law for a manipulator with the aim of realizing desired time-varying motion-force profiles in the presence of a stiff environment. In many cases, the interaction with the environment affects only one degree of freedom of the end-effector of the manipulator. Therefore, the focus is on this contact degree of freedom, and a switching position-force controller is proposed to perform the hybrid position-force tracking task. Sufficient conditions are presented to guarantee input-to-state stability of the switching closed-loop system with respect to perturbations related to the time-varying desired motion-force profile. The switching occurs when the manipulator makes or breaks contact with the environment. The analysis shows that to guarantee closed-loop stability while tracking arbitrary time-varying motion-force profiles, the controller should implement a considerable (and often unrealistic) amount of damping, resulting in inferior tracking performance. Therefore, we propose to redesign the manipulator with a compliant wrist. Guidelines are provided for the design of the compliant wrist while employing the designed switching control strategy, such that stable tracking of a motion-force reference trajectory can be achieved and bouncing of the manipulator while making contact with the stiff environment can be avoided. Finally, numerical simulations are presented to illustrate the effectiveness of the approach.
Robust Group Linkage
Venue: arXiv cs.DB 2015
Year: 2015

We study the problem of group linkage: linking records that refer to entities in the same group. Applications for group linkage include finding businesses in the same chain, finding conference attendees from the same affiliation, finding players from the same team, etc. Group linkage faces challenges not present for traditional record linkage. First, although different members in the same group can share some similar global values of an attribute, they represent different entities so can also have distinct local values for the same or different attributes, requiring a high tolerance for value diversity. Second, groups can be huge (with tens of thousands of records), requiring high scalability even after using good blocking strategies. We present a two-stage algorithm: the first stage identifies cores containing records that are very likely to belong to the same group, while being robust to possible erroneous values; the second stage collects strong evidence from the cores and leverages it for merging more records into the same group, while being tolerant to differences in local values of an attribute. Experimental results show the high effectiveness and efficiency of our algorithm on various real-world data sets.
Sampling and reconstruction of operators
Venue: arXiv cs.IT 2015
Year: 2015

We study the recovery of operators with bandlimited Kohn-Nirenberg symbol from the action of such operators on a weighted impulse train, a procedure we refer to as operator sampling. Kailath, and later Kozek and the authors have shown that operator sampling is possible if the symbol of the operator is bandlimited to a set with area less than one. In this paper we develop explicit reconstruction formulas for operator sampling that generalize reconstruction formulas for bandlimited functions. We give necessary and sufficient conditions on the sampling rate that depend on size and geometry of the bandlimiting set. Moreover, we show that under mild geometric conditions, classes of operators bandlimited to an unknown set of area less than one-half permit sampling and reconstruction. A similar result considering unknown sets of area less than one was independently achieved by Heckel and Boelcskei. Operators with bandlimited symbols have been used to model doubly dispersive communication channels with slowly-time-varying impulse response. The results in this paper are rooted in work by Bello and Kailath in the 1960s.
Consistent Answers of Conjunctive Queries on Graphs
Venue: arXiv cs.DB 2015
Year: 2015

During the past decade, there has been an extensive investigation of the computational complexity of the consistent answers of Boolean conjunctive queries under primary key constraints. Much of this investigation has focused on self-join-free Boolean conjunctive queries. In this paper, we study the consistent answers of Boolean conjunctive queries involving a single binary relation, i.e., we consider arbitrary Boolean conjunctive queries on directed graphs. In the presence of a single key constraint, we show that for each such Boolean conjunctive query, either the problem of computing its consistent answers is expressible in first-order logic, or it is polynomial-time solvable, but not expressible in first-order logic.
Photoplethysmography-Based Heart Rate Monitoring in Physical Activities via Joint Sparse Spectrum Reconstruction
Venue: arXiv cs.OH 2015
Year: 2015

Goal: A new method for heart rate monitoring using photoplethysmography (PPG) during physical activities is proposed. Methods: It jointly estimates spectra of PPG signals and simultaneous acceleration signals, utilizing the multiple measurement vector model in sparse signal recovery. Due to a common sparsity constraint on spectral coefficients, the method can easily identify and remove spectral peaks of motion artifact (MA) in PPG spectra. Thus, it does not need any extra signal processing modular to remove MA as in some other algorithms. Furthermore, seeking spectral peaks associated with heart rate is simplified. Results: Experimental results on 12 PPG datasets sampled at 25 Hz and recorded during subjects' fast running showed that it had high performance. The average absolute estimation error was 1.28 beat per minute and the standard deviation was 2.61 beat per minute. Conclusion and Significance: These results show that the method has great potential to be used for PPG-based heart rate monitoring in wearable devices for fitness tracking and health monitoring.
Smelling out Code Clones: Clone Detection Tool Evaluation and Corresponding Challenges
Venue: arXiv cs.SE 2015
Year: 2015

Software clones have been an active area of research for the past two decades. However, although numerous clone detection tools are now available, only a small fraction of the literature has focused on tool evaluation, and this is in fact still an open problem. This is mostly due to the fact that standard information retrieval metrics such as recall and precision require a priori knowledge of clones already in the system. Detection tools also typically have a large number of parameters which are difficult to fine-tune for optimal performance on a particular software system, and different outputs produced by different tools add to the complexity of comparing one tool to another. In this review, we further explore the reasons why tool evaluation is still an open challenge, and present the current tools and frameworks targeted at mitigating these problems, focusing on the current standard benchmarks used to evaluate modern clone detection tools, and also presenting a recent method aimed at finding optimal tool configurations.
Stable Cluster Core Detection in Correlated Hashtag Graph
Venue: arXiv cs.SI 2015
Year: 2015

Hashtags in twitter are used to track events, topics and activities. Correlated hashtag graph represents contextual relationships among these hashtags. Maximum clusters in the correlated hashtag graph can be contextually meaningful hashtag groups. In order to track the changes of the clusters and understand these hashtag groups, the hashtags in a cluster are categorized into two types: stable core and temporary members which are subject to change. Some initial studies are done in this project and 3 algorithms are designed, implemented and experimented to test them.
A Survey On Video Forgery Detection
Venue: arXiv cs.MM 2015
Year: 2015

The Digital Forgeries though not visibly identifiable to human perception it may alter or meddle with underlying natural statistics of digital content. Tampering involves fiddling with video content in order to cause damage or make unauthorized alteration/modification. Tampering detection in video is cumbersome compared to image when considering the properties of the video. Tampering impacts need to be studied and the applied technique/method is used to establish the factual information for legal course in judiciary. In this paper we give an overview of the prior literature and challenges involved in video forgery detection where passive approach is found.
Efficiently intertwining widening and narrowing
Venue: arXiv cs.PL 2015
Year: 2015

Non-trivial analysis problems require posets with infinite ascending and descending chains. In order to compute reasonably precise post-fixpoints of the resulting systems of equations, Cousot and Cousot have suggested accelerated fixpoint iteration by means of widening and narrowing. The strict separation into phases, however, may unnecessarily give up precision that cannot be recovered later, as over-approximated interim results have to be fully propagated through the equation the system. Additionally, classical two-phased approach is not suitable for equation systems with infinitely many unknowns---where demand driven solving must be used. Construction of an intertwined approach must be able to answer when it is safe to apply narrowing---or when widening must be applied. In general, this is a difficult problem. In case the right-hand sides of equations are monotonic, however, we can always apply narrowing whenever we have reached a post-fixpoint for an equation. The assumption of monotonicity, though, is not met in presence of widening. It is also not met by equation systems corresponding to context-sensitive inter-procedural analysis, possibly combining context-sensitive analysis of local information with flow-insensitive analysis of globals. As a remedy, we present a novel operator that combines a given widening operator with a given narrowing operator. We present adapted versions of round-robin as well as of worklist iteration, local and side-effecting solving algorithms for the combined operator and prove that the resulting solvers always return sound results and are guaranteed to terminate for monotonic systems whenever only finitely many unknowns (constraint variables) are encountered. Practical remedies are proposed for termination in the non-monotonic case.
An Ant Colony Optimization Algorithm for Partitioning Graphs with Supply and Demand
Venue: arXiv cs.AI 2015
Year: 2015

In this paper we focus on finding high quality solutions for the problem of maximum partitioning of graphs with supply and demand (MPGSD). There is a growing interest for the MPGSD due to its close connection to problems appearing in the field of electrical distribution systems, especially for the optimization of self-adequacy of interconnected microgrids. We propose an ant colony optimization algorithm for the problem. With the goal of further improving the algorithm we combine it with a previously developed correction procedure. In our computational experiments we evaluate the performance of the proposed algorithm on both trees and general graphs. The tests show that the method manages to find optimal solutions in more than 50% of the problem instances, and has an average relative error of less than 0.5% when compared to known optimal solutions.
DoF Analysis of the K-user MISO Broadcast Channel with Hybrid CSIT
Venue: arXiv cs.IT 2015
Year: 2015

We consider a $K$-user multiple-input single-output (MISO) broadcast channel (BC) where the channel state information (CSI) of user $i(i=1,2,\ldots,K)$ may be either instantaneously perfect (P), delayed (D) or not known (N) at the transmitter with probabilities $λ_P^i$, $λ_D^i$ and $λ_N^i$, respectively. In this setting, according to the three possible CSIT for each user, knowledge of the joint CSIT of the $K$ users could have at most $3^K$ states. Although the results by Tandon et al. show that for the symmetric two user MISO BC (i.e., $λ_Q^i=λ_Q,\ \forall i\in \{1,2\}, Q\in \{P,D,N\}$), the Degrees of Freedom (DoF) region depends only on the marginal probabilities, we show that this interesting result does not hold in general when $K\geq3$. In other words, the DoF region is a function of all the joint probabilities. In this paper, given the marginal probabilities of CSIT, we derive an outer bound for the DoF region of the $K$-user MISO BC. Subsequently, we investigate the achievability of the outer bound in some scenarios. Finally, we show the dependence of the DoF region on the joint probabilities.
Hilbert-Post completeness for the state and the exception effects
Venue: arXiv cs.LO 2015
Year: 2015

In this paper, we present a novel framework for studying the syntactic completeness of computational effects and we apply it to the exception effect. When applied to the states effect, our framework can be seen as a generalization of Pretnar's work on this subject. We first introduce a relative notion of Hilbert-Post completeness, well-suited to the composition of effects. Then we prove that the exception effect is relatively Hilbert-Post complete, as well as the "core" language which may be used for implementing it; these proofs have been formalized and checked with the proof assistant Coq.