OpenRaiser/Intern-Atlas huggingface dataset:
Flexible SQLf query based on fuzzy linguistic summaries
Venue: arXiv cs.DB 2014
Year: 2014

Data is often partially known, vague or ambiguous in many real world applications. To deal with such imprecise information, fuzziness is introduced in the classical model. SQLf is one of the practical language to deal with flexible fuzzy querying in Fuzzy DataBases (FDB). However, with a huge amount of fuzzy data, the necessity to work with synthetic views became a challenge for many DB community researchers. The present work deals with Flexible SQLf query based on fuzzy linguistic summaries. We use the fuzzy summaries produced by our Fuzzy-SaintEtiq approach. It provides a description of objects depending on the fuzzy linguistic labels specified as selection criteria.
Space-Efficient String Indexing for Wildcard Pattern Matching
Venue: arXiv cs.DS 2014
Year: 2014

In this paper we describe compressed indexes that support pattern matching queries for strings with wildcards. For a constant size alphabet our data structure uses $O(n\log^{\varepsilon}n)$ bits for any $\varepsilon>0$ and reports all $\mathrm{occ}$ occurrences of a wildcard string in $O(m+σ^g \cdotμ(n) + \mathrm{occ})$ time, where $μ(n)=o(\log\log\log n)$, $σ$ is the alphabet size, $m$ is the number of alphabet symbols and $g$ is the number of wildcard symbols in the query string. We also present an $O(n)$-bit index with $O((m+σ^g+\mathrm{occ})\log^{\varepsilon}n)$ query time and an $O(n(\log\log n)^2)$-bit index with $O((m+σ^g+\mathrm{occ})\log\log n)$ query time. These are the first non-trivial data structures for this problem that need $o(n\log n)$ bits of space.
Multi-Topic Multi-Document Summarizer
Venue: arXiv cs.CL 2014
Year: 2014

Current multi-document summarization systems can successfully extract summary sentences, however with many limitations including: low coverage, inaccurate extraction to important sentences, redundancy and poor coherence among the selected sentences. The present study introduces a new concept of centroid approach and reports new techniques for extracting summary sentences for multi-document. In both techniques keyphrases are used to weigh sentences and documents. The first summarization technique (Sen-Rich) prefers maximum richness sentences. While the second (Doc-Rich), prefers sentences from centroid document. To demonstrate the new summarization system application to extract summaries of Arabic documents we performed two experiments. First, we applied Rouge measure to compare the new techniques among systems presented at TAC2011. The results show that Sen-Rich outperformed all systems in ROUGE-S. Second, the system was applied to summarize multi-topic documents. Using human evaluators, the results show that Doc-Rich is the superior, where summary sentences characterized by extra coverage and more cohesion.
Plurals: individuals and sets in a richly typed semantics
Venue: arXiv cs.CL 2014
Year: 2014

We developed a type-theoretical framework for natural lan- guage semantics that, in addition to the usual Montagovian treatment of compositional semantics, includes a treatment of some phenomena of lex- ical semantic: coercions, meaning, transfers, (in)felicitous co-predication. In this setting we see how the various readings of plurals (collective, dis- tributive, coverings,...) can be modelled.
Quantitative methods for Phylogenetic Inference in Historical Linguistics: An experimental case study of South Central Dravidian
Venue: arXiv cs.CL 2014
Year: 2014

In this paper we examine the usefulness of two classes of algorithms Distance Methods, Discrete Character Methods (Felsenstein and Felsenstein 2003) widely used in genetics, for predicting the family relationships among a set of related languages and therefore, diachronic language change. Applying these algorithms to the data on the numbers of shared cognates- with-change and changed as well as unchanged cognates for a group of six languages belonging to a Dravidian language sub-family given in Krishnamurti et al. (1983), we observed that the resultant phylogenetic trees are largely in agreement with the linguistic family tree constructed using the comparative method of reconstruction with only a few minor differences. Furthermore, we studied these minor differences and found that they were cases of genuine ambiguity even for a well-trained historical linguist. We evaluated the trees obtained through our experiments using a well-defined criterion and report the results here. We finally conclude that quantitative methods like the ones we examined are quite useful in predicting family relationships among languages. In addition, we conclude that a modest degree of confidence attached to the intuition that there could indeed exist a parallelism between the processes of linguistic and genetic change is not totally misplaced.
Graph Isomorphism and the Lasserre Hierarchy
Venue: arXiv cs.CC 2014
Year: 2014

In this paper we show lower bounds for a certain large class of algorithms solving the Graph Isomorphism problem, even on expander graph instances. Spielman [25] shows an algorithm for isomorphism of strongly regular expander graphs that runs in time exp(O(n^(1/3)) (this bound was recently improved to expf O(n^(1/5) [5]). It has since been an open question to remove the requirement that the graph be strongly regular. Recent algorithmic results show that for many problems the Lasserre hierarchy works surprisingly well when the underlying graph has expansion properties. Moreover, recent work of Atserias and Maneva [3] shows that k rounds of the Lasserre hierarchy is a generalization of the k-dimensional Weisfeiler-Lehman algorithm for Graph Isomorphism. These two facts combined make the Lasserre hierarchy a good candidate for solving graph isomorphism on expander graphs. Our main result rules out this promising direction by showing that even Omega(n) rounds of the Lasserre semidefinite program hierarchy fail to solve the Graph Isomorphism problem even on expander graphs.
A Study of Successive Over-relaxation Method Parallelization Over Modern HPC Languages
Venue: arXiv cs.DC 2014
Year: 2014

Successive over-relaxation (SOR) is a computationally intensive, yet extremely important iterative solver for solving linear systems. Due to recent trends of exponential growth in amount of data generated and increasing problem sizes, serial platforms have proved to be insufficient in providing the required computational power. In this paper, we present parallel implementations of red-black SOR method using three modern programming languages namely Chapel, D and Go. We employ SOR method for solving 2D steady-state heat conduction problem. We discuss the optimizations incorporated and the features of these languages which are crucial for improving the program performance. Experiments have been performed using 2, 4, and 8 threads and performance results are compared with serial execution. The analysis of results provides important insights into working of SOR method.
From Kernel Machines to Ensemble Learning
Venue: arXiv cs.LG 2014
Year: 2014

Ensemble methods such as boosting combine multiple learners to obtain better prediction than could be obtained from any individual learner. Here we propose a principled framework for directly constructing ensemble learning methods from kernel methods. Unlike previous studies showing the equivalence between boosting and support vector machines (SVMs), which needs a translation procedure, we show that it is possible to design boosting-like procedure to solve the SVM optimization problems. In other words, it is possible to design ensemble methods directly from SVM without any middle procedure. This finding not only enables us to design new ensemble learning methods directly from kernel methods, but also makes it possible to take advantage of those highly-optimized fast linear SVM solvers for ensemble learning. We exemplify this framework for designing binary ensemble learning as well as a new multi-class ensemble learning methods. Experimental results demonstrate the flexibility and usefulness of the proposed framework.
Intuitionistic Fuzzy Linear Transformations
Venue: arXiv cs.DM 2014
Year: 2014

In this paper, we discussed about the intuitionistic fuzzy linear transformations (IFLT) and shown that the set of all linear transformations L(V) defined over an intuitionistic fuzzy vector space V does not form an vector space. Here we determine the unique intuitionistic fuzzy matrix associated with an intuitionistic fuzzy linear transformation with respect to an ordered standard basis for an intuitionistic fuzzy vector space. We introduced the concept of the inverse of an IFLT.
Optimal Competitive Auctions
Venue: arXiv cs.GT 2014
Year: 2014

We study the design of truthful auctions for selling identical items in unlimited supply (e.g., digital goods) to n unit demand buyers. This classic problem stands out from profit-maximizing auction design literature as it requires no probabilistic assumptions on buyers' valuations and employs the framework of competitive analysis. Our objective is to optimize the worst-case performance of an auction, measured by the ratio between a given benchmark and revenue generated by the auction. We establish a sufficient and necessary condition that characterizes competitive ratios for all monotone benchmarks. The characterization identifies the worst-case distribution of instances and reveals intrinsic relations between competitive ratios and benchmarks in the competitive analysis. With the characterization at hand, we show optimal competitive auctions for two natural benchmarks. The most well-studied benchmark $\mathcal{F}^{(2)}(\cdot)$ measures the envy-free optimal revenue where at least two buyers win. Goldberg et al. [13] showed a sequence of lower bounds on the competitive ratio for each number of buyers n. They conjectured that all these bounds are tight. We show that optimal competitive auctions match these bounds. Thus, we confirm the conjecture and settle a central open problem in the design of digital goods auctions. As one more application we examine another economically meaningful benchmark, which measures the optimal revenue across all limited-supply Vickrey auctions. We identify the optimal competitive ratios to be $(\frac{n}{n-1})^{n-1}-1$ for each number of buyers n, that is $e-1$ as $n$ approaches infinity.
Knowledge Spaces and the Completeness of Learning Strategies
Venue: arXiv cs.LO 2014
Year: 2014

We propose a theory of learning aimed to formalize some ideas underlying Coquand's game semantics and Krivine's realizability of classical logic. We introduce a notion of knowledge state together with a new topology, capturing finite positive and negative information that guides a learning strategy. We use a leading example to illustrate how non-constructive proofs lead to continuous and effective learning strategies over knowledge spaces, and prove that our learning semantics is sound and complete w.r.t. classical truth, as it is the case for Coquand's and Krivine's approaches.
Fluent Logic Workflow Analyser: A Tool for The Verification of Workflow Properties
Venue: arXiv cs.SE 2014
Year: 2014

In this paper we present the design and implementation, as well as a use case, of a tool for workflow analysis. The tool provides an assistant for the specification of properties of a workflow model. The specification language for property description is Fluent Linear Time Temporal Logic. Fluents provide an adequate flexibility for capturing properties of workflows. Both the model and the properties are encoded, in an automated way, as Labelled Transition Systems, and the analysis is reduced to model checking.
HeteroGenius: A Framework for Hybrid Analysis of Heterogeneous Software Specifications
Venue: arXiv cs.SE 2014
Year: 2014

Nowadays, software artifacts are ubiquitous in our lives being an essential part of home appliances, cars, cell phones, and even in more critical activities like aeronautics and health sciences. In this context software failures may produce enormous losses, either economical or, in the worst case, in human lives. Software analysis is an area in software engineering concerned with the application of diverse techniques in order to prove the absence of errors in software pieces. In many cases different analysis techniques are applied by following specific methodological combinations that ensure better results. These interactions between tools are usually carried out at the user level and it is not supported by the tools. In this work we present HeteroGenius, a framework conceived to develop tools that allow users to perform hybrid analysis of heterogeneous software specifications. HeteroGenius was designed prioritising the possibility of adding new specification languages and analysis tools and enabling a synergic relation of the techniques under a graphical interface satisfying several well-known usability enhancement criteria. As a case-study we implemented the functionality of Dynamite on top of HeteroGenius.
Progress on Polynomial Identity Testing - II
Venue: arXiv cs.CC 2014
Year: 2014

We survey the area of algebraic complexity theory; with the focus being on the problem of polynomial identity testing (PIT). We discuss the key ideas that have gone into the results of the last few years.
Performance Comparison of the RPL and LOADng Routing Protocols in a Home Automation Scenario
Venue: arXiv cs.NI 2014
Year: 2014

RPL, the routing protocol proposed by IETF for IPv6/6LoWPAN Low Power and Lossy Networks has significant complexity. Another protocol called LOADng, a lightweight variant of AODV, emerges as an alternative solution. In this paper, we compare the performance of the two protocols in a Home Automation scenario with heterogenous traffic patterns including a mix of multipoint-to-point and point-to-multipoint routes in realistic dense non-uniform network topologies. We use Contiki OS and Cooja simulator to evaluate the behavior of the ContikiRPL implementation and a basic non-optimized implementation of LOADng. Unlike previous studies, our results show that RPL provides shorter delays, less control overhead, and requires less memory than LOADng. Nevertheless, enhancing LOADng with more efficient flooding and a better route storage algorithm may improve its performance.
On the biological and cultural evolution of shame: Using internet search tools to weight values in many cultures
Venue: arXiv cs.CY 2014
Year: 2014

Shame has clear biological roots and its precise form of expression affects social cohesion and cultural characteristics. Here we explore the relative importance between shame and guilt by using Google Translate to produce translation for the words shame, guilt, pain, embarrassment and fear to the 64 languages covered. We also explore the meanings of these concepts among the Yanomami, a horticulturist hunter-gatherer tribe in the Orinoquia. Results show that societies previously described as 'guilt societies' have more words for guilt than for shame, but the large majority, including the societies previously described as 'shame societies', have more words for shame than for guilt. Results are consistent with evolutionary models of shame which predict a wide scatter in the relative importance between guilt and shame, suggesting that cultural evolution of shame has continued the work of biological evolution, and that neither provides a strong adaptive advantage to either shame or guilt. We propose that the study of shame will improve our understanding of the interaction between biological and cultural evolution in the evolution of cognition and emotions.
A binary differential evolution algorithm learning from explored solutions
Venue: arXiv cs.NE 2014
Year: 2014

Although real-coded differential evolution (DE) algorithms can perform well on continuous optimization problems (CoOPs), it is still a challenging task to design an efficient binary-coded DE algorithm. Inspired by the learning mechanism of particle swarm optimization (PSO) algorithms, we propose a binary learning differential evolution (BLDE) algorithm that can efficiently locate the global optimal solutions by learning from the last population. Then, we theoretically prove the global convergence of BLDE, and compare it with some existing binary-coded evolutionary algorithms (EAs) via numerical experiments. Numerical results show that BLDE is competitive to the compared EAs, and meanwhile, further study is performed via the change curves of a renewal metric and a refinement metric to investigate why BLDE cannot outperform some compared EAs for several selected benchmark problems. Finally, we employ BLDE solving the unit commitment problem (UCP) in power systems to show its applicability in practical problems.
On Symmetric Circuits and Fixed-Point Logics
Venue: arXiv cs.CC 2014
Year: 2014

We study properties of relational structures such as graphs that are decided by families of Boolean circuits. Circuits that decide such properties are necessarily invariant to permutations of the elements of the input structures. We focus on families of circuits that are symmetric, i.e., circuits whose invariance is witnessed by automorphisms of the circuit induced by the permutation of the input structure. We show that the expressive power of such families is closely tied to definability in logic. In particular, we show that the queries defined on structures by uniform families of symmetric Boolean circuits with majority gates are exactly those definable in fixed-point logic with counting. This shows that inexpressibility results in the latter logic lead to lower bounds against polynomial-size families of symmetric circuits.
Towards Breaking the Curse of Dimensionality for High-Dimensional Privacy: An Extended Version
Venue: arXiv cs.DB 2014
Year: 2014

The curse of dimensionality has remained a challenge for a wide variety of algorithms in data mining, clustering, classification and privacy. Recently, it was shown that an increasing dimensionality makes the data resistant to effective privacy. The theoretical results seem to suggest that the dimensionality curse is a fundamental barrier to privacy preservation. However, in practice, we show that some of the common properties of real data can be leveraged in order to greatly ameliorate the negative effects of the curse of dimensionality. In real data sets, many dimensions contain high levels of inter-attribute correlations. Such correlations enable the use of a process known as vertical fragmentation in order to decompose the data into vertical subsets of smaller dimensionality. An information-theoretic criterion of mutual information is used in the vertical decomposition process. This allows the use of an anonymization process, which is based on combining results from multiple independent fragments. We present a general approach which can be applied to the k-anonymity, l-diversity, and t-closeness models. In the presence of inter-attribute correlations, such an approach continues to be much more robust in higher dimensionality, without losing accuracy. We present experimental results illustrating the effectiveness of the approach. This approach is resilient enough to prevent identity, attribute, and membership disclosure attack.
OSCAR: A Collaborative Bandwidth Aggregation System
Venue: arXiv cs.NI 2014
Year: 2014

The exponential increase in mobile data demand, coupled with growing user expectation to be connected in all places at all times, have introduced novel challenges for researchers to address. Fortunately, the wide spread deployment of various network technologies and the increased adoption of multi-interface enabled devices have enabled researchers to develop solutions for those challenges. Such solutions aim to exploit available interfaces on such devices in both solitary and collaborative forms. These solutions, however, have faced a steep deployment barrier. In this paper, we present OSCAR, a multi-objective, incentive-based, collaborative, and deployable bandwidth aggregation system. We present the OSCAR architecture that does not introduce any intermediate hardware nor require changes to current applications or legacy servers. The OSCAR architecture is designed to automatically estimate the system's context, dynamically schedule various connections and/or packets to different interfaces, be backwards compatible with the current Internet architecture, and provide the user with incentives for collaboration. We also formulate the OSCAR scheduler as a multi-objective, multi-modal scheduler that maximizes system throughput while minimizing energy consumption or financial cost. We evaluate OSCAR via implementation on Linux, as well as via simulation, and compare our results to the current optimal achievable throughput, cost, and energy consumption. Our evaluation shows that, in the throughput maximization mode, we provide up to 150% enhancement in throughput compared to current operating systems, without any changes to legacy servers. Moreover, this performance gain further increases with the availability of connection resume-supporting, or OSCAR-enabled servers, reaching the maximum achievable upper-bound throughput.
1-bit Compressive Data Gathering for Wireless Sensor Networks
Venue: arXiv cs.NI 2014
Year: 2014

Compressive sensing (CS) has been widely used for the data gathering in wireless sensor networks for the purpose of reducing the communication overhead recent years. In this paper, we first show that with simple modification, 1-bit compressive sensing can also been used for the data gathering in wireless sensor networks to further reduce the communication overhead. We also propose a novel blind 1-bit CS reconstruction algorithm which outperforms other state of the art blind 1-bit CS reconstruction algorithms. Experimental results on real sensor datasets demonstrate the efficiency of our method.
Quadrature Compressive Sampling for Radar Signals
Venue: arXiv cs.IT 2014
Year: 2014

Quadrature sampling has been widely applied in coherent radar systems to extract in-phase and quadrature (I and Q) components in the received radar signal. However, the sampling is inefficient because the received signal contains only a small number of significant target signals. This paper incorporates the compressive sampling (CS) theory into the design of the quadrature sampling system, and develops a quadrature compressive sampling (QuadCS) system to acquire the I and Q components with low sampling rate. The QuadCS system first randomly projects the received signal into a compressive bandpass signal and then utilizes the quadrature sampling to output compressive I and Q components. The compressive outputs are used to reconstruct the I and Q components. To understand the system performance, we establish the frequency domain representation of the QuadCS system. With the waveform-matched dictionary, we prove that the QuadCS system satisfies the restricted isometry property with overwhelming probability. For K target signals in the observation interval T, simulations show that the QuadCS requires just O(Klog(BT/K)) samples to stably reconstruct the signal, where B is the signal bandwidth. The reconstructed signal-to-noise ratio decreases by 3dB for every octave increase in the target number K and increases by 3dB for every octave increase in the compressive bandwidth. Theoretical analyses and simulations verify that the proposed QuadCS is a valid system to acquire the I and Q components in the received radar signals.