OpenRaiser/Intern-Atlas huggingface dataset:
Towards a Graph-Based Approach for Web Services Composition
Venue: arXiv cs.SE 2013
Year: 2013

Nowadays, Web services (WS) remain a main actor in the implementation of distributed applications. They represent a new promising paradigm for the development, deployment and integration of Internet applications. The aim of Web services composition is to use the skills of several departments to resolve any problem that cannot be solved individually. The result of this composition is a compound of Web services that define how they will be used. In this paper, we propose an approach for automatic web services composition based on the concepts of directed graphs for the representation and description of Web services, and the ordering of web services compound execution. In this context, the user query, defined by a set of inputs and outputs, can be viewed as a directed graph composed of Web services.
Succinct data structures for representing equivalence classes
Venue: arXiv cs.DS 2013
Year: 2013

Given a partition of an n element set into equivalence classes, we consider time-space tradeoffs for representing it to support the query that asks whether two given elements are in the same equivalence class. This has various applications including for testing whether two vertices are in the same component in an undirected graph or in the same strongly connected component in a directed graph. We consider the problem in several models. -- Concerning labeling schemes where we assign labels to elements and the query is to be answered just by examining the labels of the queried elements (without any extra space): if each vertex is required to have a unique label, then we show that a label space of (\sum_{i=1}^n \lfloor {n \over i} \rfloor) is necessary and sufficient. In other words, \lg n + \lg \lg n + O(1) bits of space are necessary and sufficient for representing each of the labels. This slightly strengthens the known lower bound and is in contrast to the known necessary and sufficient bound of \lceil \lg n \rceil for the label length, if each vertex need not get a unique label. --Concerning succinct data structures for the problem when the n elements are to be uniquely assigned labels from label set {1, 2, ...n}, we first show that Θ(\sqrt n) bits are necessary and sufficient to represent the equivalence class information. This space includes the space for implicitly encoding the vertex labels. We can support the query in such a structure in O(\lg n) time in the standard word RAM model. We then develop structures resulting in one where the queries can be supported in constant time using O({\sqrt n} \lg n) bits of space. We also develop space efficient structures where union operation along with the equivalence query can be answered fast.
Network bargaining with general capacities
Venue: arXiv cs.GT 2013
Year: 2013

We study balanced solutions for network bargaining games with general capacities, where agents can participate in a fixed but arbitrary number of contracts. We provide the first polynomial time algorithm for computing balanced solutions for these games. In addition, we prove that an instance has a balanced solution if and only if it has a stable one. Our methods use a new idea of reducing an instance with general capacities to a network bargaining game with unit capacities defined on an auxiliary graph. This represents a departure from previous approaches, which rely on computing an allocation in the intersection of the core and prekernel of a corresponding cooperative game, and then proving that the solution corresponding to this allocation is balanced. In fact, we show that such cooperative game methods do not extend to general capacity games, since contrary to the case of unit capacities, there exist allocations in the intersection of the core and prekernel with no corresponding balanced solution. Finally, we identify two sufficient conditions under which the set of balanced solutions corresponds to the intersection of the core and prekernel, thereby extending the class of games for which this result was previously known.
Social Network Dynamics in a Massive Online Game: Network Turnover, Non-densification, and Team Engagement in Halo Reach
Venue: arXiv cs.SI 2013
Year: 2013

Online multiplayer games are a popular form of social interaction, used by hundreds of millions of individuals. However, little is known about the social networks within these online games, or how they evolve over time. Understanding human social dynamics within massive online games can shed new light on social interactions in general and inform the development of more engaging systems. Here, we study a novel, large friendship network, inferred from nearly 18 billion social interactions over 44 weeks between 17 million individuals in the popular online game Halo: Reach. This network is one of the largest, most detailed temporal interaction networks studied to date, and provides a novel perspective on the dynamics of online friendship networks, as opposed to mere interaction graphs. Initially, this network exhibits strong structural turnover and decays rapidly from a peak size. In the following period, however, both network size and turnover stabilize, producing a dynamic structural equilibrium. In contrast to other studies, we find that the Halo friendship network is non-densifying: both the mean degree and the average pairwise distance are stable, suggesting that densification cannot occur when maintaining friendships is costly. Finally, players with greater long-term engagement exhibit stronger local clustering, suggesting a group-level social engagement process. These results demonstrate the utility of online games for studying social networks, shed new light on empirical temporal graph patterns, and clarify the claims of universality of network densification.
Table of Content detection using Machine Learning
Venue: arXiv cs.LG 2013
Year: 2013

Table of content (TOC) detection has drawn attention now a day because it plays an important role in digitization of multipage document. Generally book document is multipage document. So it becomes necessary to detect Table of Content page for easy navigation of multipage document and also to make information retrieval faster for desirable data from the multipage document. All the Table of content pages follow the different layout, different way of presenting the contents of the document like chapter, section, subsection etc. This paper introduces a new method to detect Table of content using machine learning technique with different features. With the main aim to detect Table of Content pages is to structure the document according to their contents.
Effective Translation of LTL to Deterministic Rabin Automata: Beyond the (F,G)-Fragment
Venue: arXiv cs.FL 2013
Year: 2013

Some applications of linear temporal logic (LTL) require to translate formulae of the logic to deterministic omega-automata. There are currently two translators producing deterministic automata: ltl2dstar working for the whole LTL and Rabinizer applicable to LTL(F,G) which is the LTL fragment using only modalities F and G. We present a new translation to deterministic Rabin automata via alternating automata and deterministic transition-based generalized Rabin automata. Our translation applies to a fragment that is strictly larger than LTL(F,G). Experimental results show that our algorithm can produce significantly smaller automata compared to Rabinizer and ltl2dstar, especially for more complex LTL formulae.
Multiarmed Bandits With Limited Expert Advice
Venue: arXiv cs.LG 2013
Year: 2013

We solve the COLT 2013 open problem of \citet{SCB} on minimizing regret in the setting of advice-efficient multiarmed bandits with expert advice. We give an algorithm for the setting of K arms and N experts out of which we are allowed to query and use only M experts' advices in each round, which has a regret bound of \tilde{O}\bigP{\sqrt{\frac{\min\{K, M\} N}{M} T}} after T rounds. We also prove that any algorithm for this problem must have expected regret at least \tildeΩ\bigP{\sqrt{\frac{\min\{K, M\} N}{M}T}}, thus showing that our upper bound is nearly tight.
Efficient Two-Stage Group Testing Algorithms for Genetic Screening
Venue: arXiv cs.DS 2013
Year: 2013

Efficient two-stage group testing algorithms that are particularly suited for rapid and less-expensive DNA library screening and other large scale biological group testing efforts are investigated in this paper. The main focus is on novel combinatorial constructions in order to minimize the number of individual tests at the second stage of a two-stage disjunctive testing procedure. Building on recent work by Levenshtein (2003) and Tonchev (2008), several new infinite classes of such combinatorial designs are presented.
On Finite Block-Length Quantization Distortion
Venue: arXiv cs.IT 2013
Year: 2013

We investigate the upper and lower bounds on the quantization distortions for independent and identically distributed sources in the finite block-length regime. Based on the convex optimization framework of the rate-distortion theory, we derive a lower bound on the quantization distortion under finite block-length, which is shown to be greater than the asymptotic distortion given by the rate-distortion theory. We also derive two upper bounds on the quantization distortion based on random quantization codebooks, which can achieve any distortion above the asymptotic one. Moreover, we apply the new upper and lower bounds to two types of sources, the discrete binary symmetric source and the continuous Gaussian source. For the binary symmetric source, we obtain the closed-form expressions of the upper and lower bounds. For the Gaussian source, we propose a computational tractable method to numerically compute the upper and lower bounds, for both bounded and unbounded quantization codebooks.Numerical results show that the gap between the upper and lower bounds is small for reasonable block length and hence the bounds are tight.
Hybrid Group Decoding for Scalable Video over MIMO-OFDM Downlink Systems
Venue: arXiv cs.IT 2013
Year: 2013

We propose a scalable video broadcasting scheme over MIMO-OFDM systems. The scalable video source layers are channel encoded and modulated into independent signal streams, which are then transmitted from the allocated antennas in certain time-frequency blocks. Each receiver employs the successive group decoder to decode the signal streams of interest by treating other signal streams as interference. The transmitter performs adaptive coding and modulation, and transmission antenna and subcarrier allocation, based on the rate feedback from the receivers. We also propose a hybrid receiver that switches between the successive group decoder and the MMSE decoder depending on the rate. Extensive simulations are provided to demonstrate the performance gain of the proposed group-decoding-based scalable video broadcasting scheme over the one based on the conventional MMSE decoding.
Fault-Tolerant Control of a 2 DOF Helicopter (TRMS System) Based on H_infinity
Venue: arXiv cs.SY 2013
Year: 2013

In this paper, a Fault-Tolerant control of 2 DOF Helicopter (TRMS System) Based on H-infinity is presented. In particular, the introductory part of the paper presents a Fault-Tolerant Control (FTC), the first part of this paper presents a description of the mathematical model of TRMS, and the last part of the paper presented and a polytypic Unknown Input Observer (UIO) is synthesized using equalities and LMIs. This UIO is used to observe the faults and then compensate them, in this part the shown how to design a fault-tolerant control strategy for this particular class of non-linear systems.
Supervised Topical Key Phrase Extraction of News Stories using Crowdsourcing, Light Filtering and Co-reference Normalization
Venue: arXiv cs.CL 2013
Year: 2013

Fast and effective automated indexing is critical for search and personalized services. Key phrases that consist of one or more words and represent the main concepts of the document are often used for the purpose of indexing. In this paper, we investigate the use of additional semantic features and pre-processing steps to improve automatic key phrase extraction. These features include the use of signal words and freebase categories. Some of these features lead to significant improvements in the accuracy of the results. We also experimented with 2 forms of document pre-processing that we call light filtering and co-reference normalization. Light filtering removes sentences from the document, which are judged peripheral to its main content. Co-reference normalization unifies several written forms of the same named entity into a unique form. We also needed a "Gold Standard" - a set of labeled documents for training and evaluation. While the subjective nature of key phrase selection precludes a true "Gold Standard", we used Amazon's Mechanical Turk service to obtain a useful approximation. Our data indicates that the biggest improvements in performance were due to shallow semantic features, news categories, and rhetorical signals (nDCG 78.47% vs. 68.93%). The inclusion of deeper semantic features such as Freebase sub-categories was not beneficial by itself, but in combination with pre-processing, did cause slight improvements in the nDCG scores.
Survey on Instruction Selection: An Extensive and Modern Literature Review
Venue: arXiv cs.PL 2013
Year: 2013

Instruction selection is one of three optimisation problems involved in the code generator backend of a compiler. The instruction selector is responsible of transforming an input program from its target-independent representation into a target-specific form by making best use of the available machine instructions. Hence instruction selection is a crucial part of efficient code generation. Despite on-going research since the late 1960s, the last, comprehensive survey on the field was written more than 30 years ago. As new approaches and techniques have appeared since its publication, this brings forth a need for a new, up-to-date review of the current body of literature. This report addresses that need by performing an extensive review and categorisation of existing research. The report therefore supersedes and extends the previous surveys, and also attempts to identify where future research should be directed.
From-Below Approximations in Boolean Matrix Factorization: Geometry and New Algorithm
Venue: arXiv cs.NA 2013
Year: 2013

We present new results on Boolean matrix factorization and a new algorithm based on these results. The results emphasize the significance of factorizations that provide from-below approximations of the input matrix. While the previously proposed algorithms do not consider the possibly different significance of different matrix entries, our results help measure such significance and suggest where to focus when computing factors. An experimental evaluation of the new algorithm on both synthetic and real data demonstrates its good performance in terms of good coverage by the first k factors as well as a small number of factors needed for exact decomposition and indicates that the algorithm outperforms the available ones in these terms. We also propose future research topics.
Determining Points on Handwritten Mathematical Symbols
Venue: arXiv cs.CV 2013
Year: 2013

In a variety of applications, such as handwritten mathematics and diagram labelling, it is common to have symbols of many different sizes in use and for the writing not to follow simple baselines. In order to understand the scale and relative positioning of individual characters, it is necessary to identify the location of certain expected features. These are typically identified by particular points in the symbols, for example, the baseline of a lower case "p" would be identified by the lowest part of the bowl, ignoring the descender. We investigate how to find these special points automatically so they may be used in a number of problems, such as improving two-dimensional mathematical recognition and in handwriting neatening, while preserving the original style.
Harvesting Resource Allocation in Energy Harvesting Wireless Sensor Networks
Venue: arXiv cs.NI 2013
Year: 2013

Considering an energy harvesting sensor network, the overall probability of event loss is derived. Based on this result, a variety of harvesting resource allocation schemes (sizing the energy storages and the harvesting devices, under a total cost constraint) are provided. Their performances are verified and compared through simulations.
A Local Computation Approximation Scheme to Maximum Matching
Venue: arXiv cs.DS 2013
Year: 2013

We present a polylogarithmic local computation matching algorithm which guarantees a $(1-\eps)$-approximation to the maximum matching in graphs of bounded degree.
Optimal Color Range Reporting in One Dimension
Venue: arXiv cs.DS 2013
Year: 2013

Color (or categorical) range reporting is a variant of the orthogonal range reporting problem in which every point in the input is assigned a \emph{color}. While the answer to an orthogonal point reporting query contains all points in the query range $Q$, the answer to a color reporting query contains only distinct colors of points in $Q$. In this paper we describe an O(N)-space data structure that answers one-dimensional color reporting queries in optimal $O(k+1)$ time, where $k$ is the number of colors in the answer and $N$ is the number of points in the data structure. Our result can be also dynamized and extended to the external memory model.
Performance Analysis and Design of Maximum Ratio Combining in Channel-Aware MIMO Decision Fusion
Venue: arXiv cs.IT 2013
Year: 2013

In this paper we present a theoretical performance analysis of the maximum ratio combining (MRC) rule for channel-aware decision fusion over multiple-input multiple-output (MIMO) channels for (conditionally) dependent and independent local decisions. The system probabilities of false alarm and detection conditioned on the channel realization are derived in closed form and an approximated threshold choice is given. Furthermore, the channel-averaged (CA) performances are evaluated in terms of the CA system probabilities of false alarm and detection and the area under the receiver operating characteristic (ROC) through the closed form of the conditional moment generating function (MGF) of the MRC statistic, along with Gauss-Chebyshev (GC) quadrature rules. Furthermore, we derive the deflection coefficients in closed form, which are used for sensor threshold design. Finally, all the results are confirmed through Monte Carlo simulations.
Fine-Grained Visual Classification of Aircraft
Venue: arXiv cs.CV 2013
Year: 2013

This paper introduces FGVC-Aircraft, a new dataset containing 10,000 images of aircraft spanning 100 aircraft models, organised in a three-level hierarchy. At the finer level, differences between models are often subtle but always visually measurable, making visual recognition challenging but possible. A benchmark is obtained by defining corresponding classification tasks and evaluation protocols, and baseline results are presented. The construction of this dataset was made possible by the work of aircraft enthusiasts, a strategy that can extend to the study of number of other object classes. Compared to the domains usually considered in fine-grained visual classification (FGVC), for example animals, aircraft are rigid and hence less deformable. They, however, present other interesting modes of variation, including purpose, size, designation, structure, historical style, and branding.
Clinical Relationships Extraction Techniques from Patient Narratives
Venue: arXiv cs.IR 2013
Year: 2013

The Clinical E-Science Framework (CLEF) project was used to extract important information from medical texts by building a system for the purpose of clinical research, evidence-based healthcare and genotype-meets-phenotype informatics. The system is divided into two parts, one part concerns with the identification of relationships between clinically important entities in the text. The full parses and domain-specific grammars had been used to apply many approaches to extract the relationship. In the second part of the system, statistical machine learning (ML) approaches are applied to extract relationship. A corpus of oncology narratives that hand annotated with clinical relationships can be used to train and test a system that has been designed and implemented by supervised machine learning (ML) approaches. Many features can be extracted from these texts that are used to build a model by the classifier. Multiple supervised machine learning algorithms can be applied for relationship extraction. Effects of adding the features, changing the size of the corpus, and changing the type of the algorithm on relationship extraction are examined. Keywords: Text mining; information extraction; NLP; entities; and relations.
Epistemology of Modeling and Simulation: How can we gain Knowledge from Simulations?
Venue: arXiv cs.GL 2013
Year: 2013

Epistemology is the branch of philosophy that deals with gaining knowledge. It is closely related to ontology. The branch that deals with questions like "What is real?" and "What do we know?" as it provides these components. When using modeling and simulation, we usually imply that we are doing so to either apply knowledge, in particular when we are using them for training and teaching, or that we want to gain new knowledge, for example when doing analysis or conducting virtual experiments. This paper looks at the history of science to give a context to better cope with the question, how we can gain knowledge from simulation. It addresses aspects of computability and the general underlying mathematics, and applies the findings to validation and verification and development of federations. As simulations are understood as computable executable hypotheses, validation can be understood as hypothesis testing and theory building. The mathematical framework allows furthermore addressing some challenges when developing federations and the potential introduction of contradictions when composing different theories, as they are represented by the federated simulation systems.
Euclidean Greedy Drawings of Trees
Venue: arXiv cs.CG 2013
Year: 2013

Greedy embedding (or drawing) is a simple and efficient strategy to route messages in wireless sensor networks. For each source-destination pair of nodes s, t in a greedy embedding there is always a neighbor u of s that is closer to t according to some distance metric. The existence of greedy embeddings in the Euclidean plane R^2 is known for certain graph classes such as 3-connected planar graphs. We completely characterize the trees that admit a greedy embedding in R^2. This answers a question by Angelini et al. (Graph Drawing 2009) and is a further step in characterizing the graphs that admit Euclidean greedy embeddings.