OpenRaiser/Intern-Atlas huggingface dataset:
Substring Suffix Selection
Venue: arXiv cs.DS 2013
Year: 2013

We study the following substring suffix selection problem: given a substring of a string T of length n, compute its k-th lexicographically smallest suffix. This a natural generalization of the well-known question of computing the maximal suffix of a string, which is a basic ingredient in many other problems. We first revisit two special cases of the problem, introduced by Babenko, Kolesnichenko and Starikovskaya [CPM'13], in which we are asked to compute the minimal non-empty and the maximal suffixes of a substring. For the maximal suffixes problem, we give a linear-space structure with O(1) query time and linear preprocessing time, i.e., we manage to achieve optimal construction and optimal query time simultaneously. For the minimal suffix problem, we give a linear-space data structure with O(τ) query time and O(n log n / τ) preprocessing time, where 1 <= τ<= log n is a parameter of the data structure. As a sample application, we show that this data structure can be used to compute the Lyndon decomposition of any substring of T in O(k τ) time, where k is the number of distinct factors in the decomposition. Finally, we move to the general case of the substring suffix selection problem, where using any combinatorial properties seems more difficult. Nevertheless, we develop a linear-space data structure with O(log^{2+ε} n) query time.
A Cache-Coloring Based Technique for Saving Leakage Energy In Multitasking Systems
Venue: arXiv cs.AR 2013
Year: 2013

There has been a significant increase in leakage energy dissipation of CMOS circuits with each technology generation. Further, due to their large size, last level caches (LLCs) spend a large fraction of their energy in the form of leakage energy and hence, addressing this has become extremely important to meet the challenges of chip power budget. For addressing this, several techniques have been proposed. However, most of these techniques require offline profiling and hence cannot be used for real-life systems which usually run multitasking programs, with possible pre-emptions. In this paper, we propose a dynamic profiling based technique for saving cache leakage energy in multitasking systems. Our technique uses a small coloring-based profiling cache, to estimate performance and energy consumption of multiple cache configurations and then selects the best (least-energy) configuration among them. Our technique uses non-intrusive profiling and saves energy despite intra-task and inter-task variations; thus, it is suitable for multitasking systems. Simulations performed using workloads from SPEC2006 suite show the superiority of our technique over an existing cache energy saving technique. With a 2MB baseline cache, the average saving in memory sub-system energy is 22.8%.
A Hybrid Algorithm for Matching Arabic Names
Venue: arXiv cs.CL 2013
Year: 2013

In this paper, a new hybrid algorithm which combines both of token-based and character-based approaches is presented. The basic Levenshtein approach has been extended to token-based distance metric. The distance metric is enhanced to set the proper granularity level behavior of the algorithm. It smoothly maps a threshold of misspellings differences at the character level, and the importance of token level errors in terms of token's position and frequency. Using a large Arabic dataset, the experimental results show that the proposed algorithm overcomes successfully many types of errors such as: typographical errors, omission or insertion of middle name components, omission of non-significant popular name components, and different writing styles character variations. When compared the results with other classical algorithms, using the same dataset, the proposed algorithm was found to increase the minimum success level of best tested algorithms, while achieving higher upper limits .
Pseudorandomness for Multilinear Read-Once Algebraic Branching Programs, in any Order
Venue: arXiv cs.CC 2013
Year: 2013

We give deterministic black-box polynomial identity testing algorithms for multilinear read-once oblivious algebraic branching programs (ROABPs), in n^(lg^2 n) time. Further, our algorithm is oblivious to the order of the variables. This is the first sub-exponential time algorithm for this model. Furthermore, our result has no known analogue in the model of read-once oblivious boolean branching programs with unknown order, as despite recent work there is no known pseudorandom generator for this model with sub-polynomial seed-length (for unbounded-width branching programs). This result extends and generalizes the result of Forbes and Shpilka that obtained a n^(lg n)-time algorithm when given the order. We also extend and strengthen the work of Agrawal, Saha and Saxena that gave a black-box algorithm running in time exp((lg n)^d) for set-multilinear formulas of depth d. We note that the model of multilinear ROABPs contains the model of set-multilinear algebraic branching programs, which itself contains the model of set-multilinear formulas of arbitrary depth. We obtain our results by recasting, and improving upon, the ideas of Agrawal, Saha and Saxena. We phrase the ideas in terms of rank condensers and Wronskians, and show that our results improve upon the classical multivariate Wronskian, which may be of independent interest. In addition, we give the first n^(lglg n) black-box polynomial identity testing algorithm for the so called model of diagonal circuits. This model, introduced by Saxena has recently found applications in the work of Mulmuley, as well as in the work of Gupta, Kamath, Kayal, Saptharishi. Previously work had given n^(lg n)-time algorithms for this class. More generally, our result holds for any model computing polynomials whose partial derivatives (of all orders) span a low dimensional linear space.
Checkerboard Problem to Topology Optimization of Continuum Structures
Venue: arXiv cs.CE 2013
Year: 2013

The area of topology optimization of continuum structures of which is allowed to change in order to improve the performance is now dominated by methods that employ the material distribution concept. The typical methods of the topology optimization based on the structural optimization of two phase composites are the so-called variable density ones, like the SIMP (Solid Isotropic Material with Penalization) and the BESO (Bi-directional Evolutional Structure Optimization). The topology optimization problem refers to the saddle-point variation one as well as the so-called Stokes flow problem of the compressive fluid. The checkerboard patterns often appear in the results computed by the SIMP and the BESO in which the Q1-P0 element is used for FEM (Finite Element Method), since these patterns are more favourable than uniform density regions. Computational experiments of SIMP and BESO have shown that filtering of sensitivity information of the optimization problem is a highly efficient way that the checkerboard patterns disappeared and to ensure mesh-independency. SIn this paper, we discuss the theoretical basis for the filtering method of the SIMP and the BESO and as a result, the filtering method can be understood by the theorem of partition of unity and the convolution operator of low-pass filter.
The Dilworth Number of Auto-Chordal-Bipartite Graphs
Venue: arXiv cs.DM 2013
Year: 2013

The mirror (or bipartite complement) mir(B) of a bipartite graph B=(X,Y,E) has the same color classes X and Y as B, and two vertices x in X and y in Y are adjacent in mir(B) if and only if xy is not in E. A bipartite graph is chordal bipartite if none of its induced subgraphs is a chordless cycle with at least six vertices. In this paper, we deal with chordal bipartite graphs whose mirror is chordal bipartite as well; we call these graphs auto-chordal bipartite graphs (ACB graphs for short). We describe the relationship to some known graph classes such as interval and strongly chordal graphs and we present several characterizations of ACB graphs. We show that ACB graphs have unbounded Dilworth number, and we characterize ACB graphs with Dilworth number k.
Scalable Anomaly Detection in Large Homogenous Populations
Venue: arXiv cs.LG 2013
Year: 2013

Anomaly detection in large populations is a challenging but highly relevant problem. The problem is essentially a multi-hypothesis problem, with a hypothesis for every division of the systems into normal and anomal systems. The number of hypothesis grows rapidly with the number of systems and approximate solutions become a necessity for any problems of practical interests. In the current paper we take an optimization approach to this multi-hypothesis problem. We first observe that the problem is equivalent to a non-convex combinatorial optimization problem. We then relax the problem to a convex problem that can be solved distributively on the systems and that stays computationally tractable as the number of systems increase. An interesting property of the proposed method is that it can under certain conditions be shown to give exactly the same result as the combinatorial multi-hypothesis problem and the relaxation is hence tight.
Undefined By Data: A Survey of Big Data Definitions
Venue: arXiv cs.DB 2013
Year: 2013

The term big data has become ubiquitous. Owing to a shared origin between academia, industry and the media there is no single unified definition, and various stakeholders provide diverse and often contradictory definitions. The lack of a consistent definition introduces ambiguity and hampers discourse relating to big data. This short paper attempts to collate the various definitions which have gained some degree of traction and to furnish a clear and concise definition of an otherwise ambiguous term.
From Once Upon a Time to Happily Ever After: Tracking Emotions in Novels and Fairy Tales
Venue: arXiv cs.CL 2013
Year: 2013

Today we have access to unprecedented amounts of literary texts. However, search still relies heavily on key words. In this paper, we show how sentiment analysis can be used in tandem with effective visualizations to quantify and track emotions in both individual books and across very large collections. We introduce the concept of emotion word density, and using the Brothers Grimm fairy tales as example, we show how collections of text can be organized for better search. Using the Google Books Corpus we show how to determine an entity's emotion associations from co-occurring words. Finally, we compare emotion words in fairy tales and novels, to show that fairy tales have a much wider range of emotion word densities than novels.
Colourful Language: Measuring Word-Colour Associations
Venue: arXiv cs.CL 2013
Year: 2013

Since many real-world concepts are associated with colour, for example danger with red, linguistic information is often complimented with the use of appropriate colours in information visualization and product marketing. Yet, there is no comprehensive resource that captures concept-colour associations. We present a method to create a large word-colour association lexicon by crowdsourcing. We focus especially on abstract concepts and emotions to show that even though they cannot be physically visualized, they too tend to have strong colour associations. Finally, we show how word-colour associations manifest themselves in language, and quantify usefulness of co-occurrence and polarity cues in automatically detecting colour associations.
JRC-Names: A freely available, highly multilingual named entity resource
Venue: arXiv cs.CL 2013
Year: 2013

This paper describes a new, freely available, highly multilingual named entity resource for person and organisation names that has been compiled over seven years of large-scale multilingual news analysis combined with Wikipedia mining, resulting in 205,000 per-son and organisation names plus about the same number of spelling variants written in over 20 different scripts and in many more languages. This resource, produced as part of the Europe Media Monitor activity (EMM, http://emm.newsbrief.eu/overview.html), can be used for a number of purposes. These include improving name search in databases or on the internet, seeding machine learning systems to learn named entity recognition rules, improve machine translation results, and more. We describe here how this resource was created; we give statistics on its current size; we address the issue of morphological inflection; and we give details regarding its functionality. Updates to this resource will be made available daily.
Using Nuances of Emotion to Identify Personality
Venue: arXiv cs.CL 2013
Year: 2013

Past work on personality detection has shown that frequency of lexical categories such as first person pronouns, past tense verbs, and sentiment words have significant correlations with personality traits. In this paper, for the first time, we show that fine affect (emotion) categories such as that of excitement, guilt, yearning, and admiration are significant indicators of personality. Additionally, we perform experiments to show that the gains provided by the fine affect categories are not obtained by using coarse affect categories alone or with specificity features alone. We employ these features in five SVM classifiers for detecting five personality traits through essays. We find that the use of fine emotion features leads to statistically significant improvement over a competitive baseline, whereas the use of coarse affect and specificity features does not.
Software Defined Radio Architecture Survey for Cognitive Testbeds
Venue: arXiv cs.NI 2013
Year: 2013

In this paper we present a survey of existing prototypes dedicated to software defined radio. We propose a classification related to the architectural organization of the pro- totypes and provide some conclusions about the most promising architectures. This study should be useful for cognitive radio testbed designers who have to choose between many possible computing platforms. We also introduce a new cognitive radio testbed currently under construction and explain how this study have influenced the test-bed designers choices.
The Computational Complexity of the Game of Set and its Theoretical Applications
Venue: arXiv cs.CC 2013
Year: 2013

The game of SET is a popular card game in which the objective is to form Sets using cards from a special deck. In this paper we study single- and multi-round variations of this game from the computational complexity point of view and establish interesting connections with other classical computational problems. Specifically, we first show that a natural generalization of the problem of finding a single Set, parameterized by the size of the sought Set is W-hard; our reduction applies also to a natural parameterization of Perfect Multi-Dimensional Matching, a result which may be of independent interest. Second, we observe that a version of the game where one seeks to find the largest possible number of disjoint Sets from a given set of cards is a special case of 3-Set Packing; we establish that this restriction remains NP-complete. Similarly, the version where one seeks to find the smallest number of disjoint Sets that overlap all possible Sets is shown to be NP-complete, through a close connection to the Independent Edge Dominating Set problem. Finally, we study a 2-player version of the game, for which we show a close connection to Arc Kayles, as well as fixed-parameter tractability when parameterized by the number of rounds played.
An Inter-lingual Reference Approach For Multi-Lingual Ontology Matching
Venue: arXiv cs.CL 2013
Year: 2013

Ontologies are considered as the backbone of the Semantic Web. With the rising success of the Semantic Web, the number of participating communities from different countries is constantly increasing. The growing number of ontologies available in different natural languages leads to an interoperability problem. In this paper, we discuss several approaches for ontology matching; examine similarities and differences, identify weaknesses, and compare the existing automated approaches with the manual approaches for integrating multilingual ontologies. In addition to that, we propose a new architecture for a multilingual ontology matching service. As a case study we used an example of two multilingual enterprise ontologies - the university ontology of Freie Universitaet Berlin and the ontology for Fayoum University in Egypt.
Inside the clustering threshold for random linear equations
Venue: arXiv cs.DM 2013
Year: 2013

We study a random system of $cn$ linear equations over $n$ variables in GF(2), where each equation contains exactly $r$ variables; this is equivalent to $r$-XORSAT. \cite{ikkm,amxor} determined the clustering threshold, $c^*_r$: if $c=c^*_r+\e$ for any constant $\e>0$, then \aas the solutions partition into well-connected, well-separated {\em clusters} (with probability tending to 1 as $n\rightarrow\infty$). This is part of a general clustering phenomenon which is hypothesized to arise in most of the commonly studied models of random constraint satisfaction problems, via sophisticated but mostly non-rigorous techniques from statistical physics. We extend that study to the range $c=c^*_r+o(1)$, showing that if $c=c^*_r+n^{-\d}, \d>0$, then the connectivity parameter of each $r$-XORSAT cluster is $n^{Θ(\d)}$, as compared to $O(\log n)$ when $c=c^*_r+\e$. This means that one can move between any two solutions in the same cluster via a sequence of solutions where consecutive solutions differ on at most $n^{Θ(\d)}$ variables; this is tight up to the implicit constant. In contrast, moving to a solution in another cluster requires that some pair of consecutive solutions differ in at least $n^{1-O(\d)}$ variables. Along the way, we prove that in a random $r$-uniform hypergraph with edge-density $n^{-\d}$ above the $k$-core threshold, \aas every vertex not in the $k$-core can be removed by a sequence of $n^{Θ(\d)}$ vertex-deletions in which the deleted vertex has degree less than $k$; again, this is tight up to the implicit constant.
Dynamic Structural Equation Models for Social Network Topology Inference
Venue: arXiv cs.SI 2013
Year: 2013

Many real-world processes evolve in cascades over complex networks, whose topologies are often unobservable and change over time. However, the so-termed adoption times when blogs mention popular news items, individuals in a community catch an infectious disease, or consumers adopt a trendy electronics product are typically known, and are implicitly dependent on the underlying network. To infer the network topology, a \textit{dynamic} structural equation model is adopted to capture the relationship between observed adoption times and the unknown edge weights. Assuming a slowly time-varying topology and leveraging the sparse connectivity inherent to social networks, edge weights are estimated by minimizing a sparsity-regularized exponentially-weighted least-squares criterion. To this end, solvers with complementary strengths are developed by leveraging (pseudo) real-time sparsity-promoting proximal gradient iterations, the improved convergence rate of accelerated variants, or reduced computational complexity of stochastic gradient descent. Numerical tests with both synthetic and real data demonstrate the effectiveness of the novel algorithms in unveiling sparse dynamically-evolving topologies, while accounting for external influences in the adoption times. Key events in the recent succession of political leadership in North Korea, explain connectivity changes observed in the associated network inferred from global cascades of online media.
Outage Capacity of Opportunistic Beamforming with Random User Locations
Venue: arXiv cs.IT 2013
Year: 2013

This paper studies the outage capacity of a network consisting of a multitude of heterogenous mobile users, and operating according to the classical opportunistic beamforming framework. The base station is located at the center of the cell, which is modeled as a disk of finite radius. The random user locations are modeled using a homogenous spatial Poisson point process. The received signals are impaired by both fading and location dependent path loss. For this system, we first derive an expression for the beam outage probability. This expression holds for all path loss models that satisfy some mild conditions. Then, we focus on two specific path loss models (i.e., an unbounded model and a more realistic bounded one) to illustrate the applications of our results. In the large system limit where the cell radius tends to infinity, the beam outage capacity and its scaling behavior are derived for the selected specific path loss models. It is shown that the beam outage capacity scales logarithmically for the unbounded model. On the other hand, this scaling behavior becomes double logarithmic for the bounded model. Intuitive explanations are provided as to why we observe different scaling behavior for different path loss models. Numerical evaluations are performed to give further insights, and to illustrate the applicability of the outage capacity results even to a cell having a small finite radius.
Hinge-loss Markov Random Fields: Convex Inference for Structured Prediction
Venue: arXiv cs.LG 2013
Year: 2013

Graphical models for structured domains are powerful tools, but the computational complexities of combinatorial prediction spaces can force restrictions on models, or require approximate inference in order to be tractable. Instead of working in a combinatorial space, we use hinge-loss Markov random fields (HL-MRFs), an expressive class of graphical models with log-concave density functions over continuous variables, which can represent confidences in discrete predictions. This paper demonstrates that HL-MRFs are general tools for fast and accurate structured prediction. We introduce the first inference algorithm that is both scalable and applicable to the full class of HL-MRFs, and show how to train HL-MRFs with several learning algorithms. Our experiments show that HL-MRFs match or surpass the predictive performance of state-of-the-art methods, including discrete models, in four application domains.
Structured Message Passing
Venue: arXiv cs.AI 2013
Year: 2013

In this paper, we present structured message passing (SMP), a unifying framework for approximate inference algorithms that take advantage of structured representations such as algebraic decision diagrams and sparse hash tables. These representations can yield significant time and space savings over the conventional tabular representation when the message has several identical values (context-specific independence) or zeros (determinism) or both in its range. Therefore, in order to fully exploit the power of structured representations, we propose to artificially introduce context-specific independence and determinism in the messages. This yields a new class of powerful approximate inference algorithms which includes popular algorithms such as cluster-graph Belief propagation (BP), expectation propagation and particle BP as special cases. We show that our new algorithms introduce several interesting bias-variance trade-offs. We evaluate these trade-offs empirically and demonstrate that our new algorithms are more accurate and scalable than state-of-the-art techniques.