OpenRaiser/Intern-Atlas huggingface dataset:
Odysseus/DFS: Integration of DBMS and Distributed File System for Transaction Processing of Big Data
Venue: arXiv cs.DB 2014
Year: 2014

The relational DBMS (RDBMS) has been widely used since it supports various high-level functionalities such as SQL, schemas, indexes, and transactions that do not exist in the O/S file system. But, a recent advent of big data technology facilitates development of new systems that sacrifice the DBMS functionality in order to efficiently manage large-scale data. Those so-called NoSQL systems use a distributed file system, which support scalability and reliability. They support scalability of the system by storing data into a large number of low-cost commodity hardware and support reliability by storing the data in replica. However, they have a drawback that they do not adequately support high-level DBMS functionality. In this paper, we propose an architecture of a DBMS that uses the DFS as storage. With this novel architecture, the DBMS is capable of supporting scalability and reliability of the DFS as well as high-level functionality of DBMS. Thus, a DBMS can utilize a virtually unlimited storage space provided by the DFS, rendering it to be suitable for big data analytics. As part of the architecture of the DBMS, we propose the notion of the meta DFS file, which allows the DBMS to use the DFS as the storage, and an efficient transaction management method including recovery and concurrency control. We implement this architecture in Odysseus/DFS, an integration of the Odysseus relational DBMS, that has been being developed at KAIST for over 24 years, with the DFS. Our experiments on transaction processing show that, due to the high-level functionality of Odysseus/DFS, it outperforms Hbase, which is a representative open-source NoSQL system. We also show that, compared with an RDBMS with local storage, the performance of Odysseus/DFS is comparable or marginally degraded, showing that the overhead of Odysseus/DFS for supporting scalability by using the DFS as the storage is not significant.
A Tiling Perspective for Register Optimization
Venue: arXiv cs.PL 2014
Year: 2014

Register allocation is a much studied problem. A particularly important context for optimizing register allocation is within loops, since a significant fraction of the execution time of programs is often inside loop code. A variety of algorithms have been proposed in the past for register allocation, but the complexity of the problem has resulted in a decoupling of several important aspects, including loop unrolling, register promotion, and instruction reordering. In this paper, we develop an approach to register allocation and promotion in a unified optimization framework that simultaneously considers the impact of loop unrolling and instruction scheduling. This is done via a novel instruction tiling approach where instructions within a loop are represented along one dimension and innermost loop iterations along the other dimension. By exploiting the regularity along the loop dimension, and imposing essential dependence based constraints on intra-tile execution order, the problem of optimizing register pressure is cast in a constraint programming formalism. Experimental results are provided from thousands of innermost loops extracted from the SPEC benchmarks, demonstrating improvements over the current state-of-the-art.
Identification of parameterized gray-box state-space systems: from a black-box linear time-invariant representation to a structured one: detailed derivation of the gradients involved in the cost functions
Venue: arXiv cs.SY 2014
Year: 2014

Estimating consistent parameters of a structured state-space representation requires a reliable initialization when the vector of parameters is computed by using a gradient-based algorithm. In the eponymous companion paper accepted for publication in IEEE Transactions on Automatic Control, the problem of supplying a reliable initial vector of parameters is tackled. More precisely, by assuming that a reliable initial fully-parameterized state-space model of the system is available, the aforementioned paper addresses the challenging problem of transforming this initial fully-parameterized model into the structured state-space parameterization satisfied by the system to be identified. Two solutions to solve such a parameterization problem are more precisely introduced in the IEEE TAC paper. First, a solution based on a null-space-based reformulation of a set of equations arising from the aforementioned similarity transformation problem is considered. Second, an algorithm dedicated to non-convex optimization is presented in order to transform the initial fully-parameterized model into the structured state-space parameterization of the system to be identified. In this technical report, a specific attention is paid to the gradient computation required by the optimization algorithms used in aforementioned to solve the aforementioned problem. These gradient formulations are indeed necessary to apply the quasi-Newton Broyden-Fletcher-Goldfarb-Shanno (BFGS) methods used for the null-space based as well as the least-squares-formulated optimization techniques introduced in the IEEE TAC paper. For the sake of conciseness, we only focus on the smooth version of the optimization problem introduced in aforementioned paper. Interested readers can easily extend the following results by using the chain rule as well as the sub-gradient computation techniques.
Enabling Disaster Resilient 4G Mobile Communication Networks
Venue: arXiv cs.NI 2014
Year: 2014

The 4G Long Term Evolution (LTE) is the cellular technology expected to outperform the previous generations and to some extent revolutionize the experience of the users by taking advantage of the most advanced radio access techniques (i.e. OFDMA, SC-FDMA, MIMO). However, the strong dependencies between user equipments (UEs), base stations (eNBs) and the Evolved Packet Core (EPC) limit the flexibility, manageability and resiliency in such networks. In case the communication links between UEs-eNB or eNB-EPC are disrupted, UEs are in fact unable to communicate. In this article, we reshape the 4G mobile network to move towards more virtual and distributed architectures for improving disaster resilience, drastically reducing the dependency between UEs, eNBs and EPC. The contribution of this work is twofold. We firstly present the Flexible Management Entity (FME), a distributed entity which leverages on virtualized EPC functionalities in 4G cellular systems. Second, we introduce a simple and novel device-todevice (D2D) communication scheme allowing the UEs in physical proximity to communicate directly without resorting to the coordination with an eNB.
Latent Kullback Leibler Control for Continuous-State Systems using Probabilistic Graphical Models
Venue: arXiv cs.SY 2014
Year: 2014

Kullback Leibler (KL) control problems allow for efficient computation of optimal control by solving a principal eigenvector problem. However, direct applicability of such framework to continuous state-action systems is limited. In this paper, we propose to embed a KL control problem in a probabilistic graphical model where observed variables correspond to the continuous (possibly high-dimensional) state of the system and latent variables correspond to a discrete (low-dimensional) representation of the state amenable for KL control computation. We present two examples of this approach. The first one uses standard hidden Markov models (HMMs) and computes exact optimal control, but is only applicable to low-dimensional systems. The second one uses factorial HMMs, it is scalable to higher dimensional problems, but control computation is approximate. We illustrate both examples in several robot motor control tasks.
Navigating in a sea of repeats in RNA-seq without drowning
Venue: arXiv cs.DS 2014
Year: 2014

The main challenge in de novo assembly of NGS data is certainly to deal with repeats that are longer than the reads. This is particularly true for RNA- seq data, since coverage information cannot be used to flag repeated sequences, of which transposable elements are one of the main examples. Most transcriptome assemblers are based on de Bruijn graphs and have no clear and explicit model for repeats in RNA-seq data, relying instead on heuristics to deal with them. The results of this work are twofold. First, we introduce a formal model for repre- senting high copy number repeats in RNA-seq data and exploit its properties for inferring a combinatorial characteristic of repeat-associated subgraphs. We show that the problem of identifying in a de Bruijn graph a subgraph with this charac- teristic is NP-complete. In a second step, we show that in the specific case of a local assembly of alternative splicing (AS) events, we can implicitly avoid such subgraphs. In particular, we designed and implemented an algorithm to efficiently identify AS events that are not included in repeated regions. Finally, we validate our results using synthetic data. We also give an indication of the usefulness of our method on real data.
Don't Believe Everything You Hear; Preserving Relevant Information by Discarding Social Information
Venue: arXiv cs.MA 2014
Year: 2014

Integrating information gained by observing others via Social Bayesian Learning can be beneficial for an agent's performance, but can also enable population wide information cascades that perpetuate false beliefs through the agent population. We show how agents can influence the observation network by changing their probability of observing others, and demonstrate the existence of a population-wide equilibrium, where the advantages and disadvantages of the Social Bayesian update are balanced. We also use the formalism of relevant information to illustrate how negative information cascades are characterized by processing increasing amounts of non-relevant information.
Throughput Optimized Multi-Source Cooperative Networks With Compute-and-Forward
Venue: arXiv cs.IT 2014
Year: 2014

In this work, we investigate a multi-source multi-cast network with the aid of an arbitrary number of relays, where it is assumed that no direct link is available at each S-D pair. The aim is to find the fundamental limit on the maximal common multicast throughput of all source nodes if resource allocations are available. A transmission protocol employing the relaying strategy, namely, compute-and-forward (CPF), is proposed. {We also adjust the methods in the literature to obtain the integer network-constructed coefficient matrix (a naive method, a local optimal method as well as a global optimal method) to fit for the general topology with an arbitrary number of relays. Two transmission scenarios are addressed. The first scenario is delay-stringent transmission where each message must be delivered within one slot. The second scenario is delay-tolerant transmission where no delay constraint is imposed. The associated optimization problems to maximize the short-term and long-term common multicast throughput are formulated and solved, and the optimal allocation of power and time slots are presented. Performance comparisons show that the CPF strategy outperforms conventional decode-and-forward (DF) strategy. It is also shown that with more relays, the CPF strategy performs even better due to the increased diversity. Finally, by simulation, it is observed that for a large network in relatively high SNR regime, CPF with the local optimal method for the network-constructed matrix can perform close to that with the global optimal method.
Crowds on Wall Street: Extracting Value from Social Investing Platforms
Venue: arXiv cs.SI 2014
Year: 2014

For decades, the world of financial advisors has been dominated by large investment banks such as Goldman Sachs. In recent years, user-contributed investment services such as SeekingAlpha and StockTwits have grown to millions of users. In this paper, we seek to understand the quality and impact of content on social investment platforms, by empirically analyzing complete datasets of SeekingAlpha articles (9 years) and StockTwits messages (4 years). We develop sentiment analysis tools and correlate contributed content to the historical performance of relevant stocks. While SeekingAlpha articles and StockTwits messages provide minimal correlation to stock performance in aggregate, a subset of authors contribute more valuable (predictive) content. We show that these authors can be identified via both empirical methods or by user interactions, and investments using their analysis significantly outperform broader markets. Finally, we conduct a user survey that sheds light on users views of SeekingAlpha content and stock manipulation.
A Semantic Approach to Summarization
Venue: arXiv cs.CL 2014
Year: 2014

Sentence extraction based summarization methods has some limitations as it doesn't go into the semantics of the document. Also, it lacks the capability of sentence generation which is intuitive to humans. Here we present a novel method to summarize text documents taking the process to semantic levels with the use of WordNet and other resources, and using a technique for sentence generation. We involve semantic role labeling to get the semantic representation of text and use of segmentation to form clusters of the related pieces of text. Picking out the centroids and sentence generation completes the task. We evaluate our system against human composed summaries and also present an evaluation done by humans to measure the quality attributes of our summaries.
Statistical Intercell Interference Modeling for Capacity-Coverage Tradeoff Analysis in Downlink Cellular Networks
Venue: arXiv cs.IT 2014
Year: 2014

Interference shapes the interplay between capacity and coverage in cellular networks. However, interference is non-deterministic and depends on various system and channel parameters including user scheduling, frequency reuse, and fading variations. We present an analytical approach for modeling the distribution of intercell interference in the downlink of cellular networks as a function of generic fading channel models and various scheduling schemes. We demonstrate the usefulness of the derived expressions in calculating location-based and average-based data rates in addition to capturing practical tradeoffs between cell capacity and coverage in downlink cellular networks.
The Best Templates Match Technique For Example Based Machine Translation
Venue: arXiv cs.CL 2014
Year: 2014

It has been proved that large scale realistic Knowledge Based Machine Translation applications require acquisition of huge knowledge about language and about the world. This knowledge is encoded in computational grammars, lexicons and domain models. Another approach which avoids the need for collecting and analyzing massive knowledge, is the Example Based approach, which is the topic of this paper. We show through the paper that using Example Based in its native form is not suitable for translating into Arabic. Therefore a modification to the basic approach is presented to improve the accuracy of the translation process. The basic idea of the new approach is to improve the technique by which template-based approaches select the appropriate templates.
Flow Level QoE of Video Streaming in Wireless Networks
Venue: arXiv cs.NI 2014
Year: 2014

The Quality of Experience (QoE) of streaming service is often degraded by frequent playback interruptions. To mitigate the interruptions, the media player prefetches streaming contents before starting playback, at a cost of delay. We study the QoE of streaming from the perspective of flow dynamics. First, a framework is developed for QoE when streaming users join the network randomly and leave after downloading completion. We compute the distribution of prefetching delay using partial differential equations (PDEs), and the probability generating function of playout buffer starvations using ordinary differential equations (ODEs) for CBR streaming. Second, we extend our framework to characterize the throughput variation caused by opportunistic scheduling at the base station, and the playback variation of VBR streaming. Our study reveals that the flow dynamics is the fundamental reason of playback starvation. The QoE of streaming service is dominated by the first moments such as the average throughput of opportunistic scheduling and the mean playback rate. While the variances of throughput and playback rate have very limited impact on starvation behavior.
Sensing and Link Model for Wireless Sensor Network: Coverage and Connectivity Analysis
Venue: arXiv cs.IT 2014
Year: 2014

Coverage and connectivity both are important in wireless sensor network (WSN). Coverage means how well an area of interest is being monitored by the deployed network. It depends on sensing model that has been used to design the network model. Connectivity ensures the establishment of a wireless link between two nodes. A link model studies the connectivity between two nodes. The probability of establishing a wireless link between two nodes is a probabilistic phenomenon. The connectivity between two nodes plays an important role in the determination of network connectivity. In this paper, we investigate the impact of sensing model of nodes on the network coverage. Also, we investigate the dependency of the connectivity and coverage on the shadow fading parameters. It has been observed that shadowing effect reduces the network coverage while it enhances connectivity in a multi-hop wireless network.
Interclausal Logic Variables
Venue: arXiv cs.PL 2014
Year: 2014

Unification of logic variables instantly connects present and future observations of their value, independently of their location in the data areas of the runtime system. The paper extends this property to "interclausal logic variables", an easy to implement Prolog extension that supports instant global information exchanges without dynamic database updates. We illustrate their usefulness with two of algorithms, {\em graph coloring} and {\em minimum spanning tree}. Implementations of interclausal variables as source-level transformations and as abstract machine adaptations are given. To address the need for globally visible chained transitions of logic variables we describe a DCG-based program transformation that extends the functionality of interclausal variables.
An LTL Semantics of Business Workflows with Recovery
Venue: arXiv cs.SE 2014
Year: 2014

We describe a business workflow case study with abnormal behavior management (i.e. recovery) and demonstrate how temporal logics and model checking can provide a methodology to iteratively revise the design and obtain a correct-by construction system. To do so we define a formal semantics by giving a compilation of generic workflow patterns into LTL and we use the bound model checker Zot to prove specific properties and requirements validity. The working assumption is that such a lightweight approach would easily fit into processes that are already in place without the need for a radical change of procedures, tools and people's attitudes. The complexity of formalisms and invasiveness of methods have been demonstrated to be one of the major drawback and obstacle for deployment of formal engineering techniques into mundane projects.
Subgraph covers -- An information theoretic approach to motif analysis in networks
Venue: arXiv cs.SI 2014
Year: 2014

Many real world networks contain a statistically surprising number of certain subgraphs, called network motifs. In the prevalent approach to motif analysis, network motifs are detected by comparing subgraph frequencies in the original network with a statistical null model. In this paper we propose an alternative approach to motif analysis where network motifs are defined to be connectivity patterns that occur in a subgraph cover that represents the network using minimal total information. A subgraph cover is defined to be a set of subgraphs such that every edge of the graph is contained in at least one of the subgraphs in the cover. Some recently introduced random graph models that can incorporate significant densities of motifs have natural formulations in terms of subgraph covers and the presented approach can be used to match networks with such models. To prove the practical value of our approach we also present a heuristic for the resulting NP-hard optimization problem and give results for several real world networks.
Reconfiguring Independent Sets in Cographs
Venue: arXiv cs.DM 2014
Year: 2014

Two independent sets of a graph are adjacent if they differ on exactly one vertex (i.e. we can transform one into the other by adding or deleting a vertex). Let $k$ be an integer. We consider the reconfiguration graph $TAR_k(G)$ on the set of independent sets of size at least $k$ in a graph $G$, with the above notion of adjacency. Here we provide a cubic-time algorithm to decide whether $TAR_k(G)$ is connected when $G$ is a cograph, thus solving an open question of~[Bonsma 2014]. As a by-product, we also describe a linear-time algorithm which decides whether two elements of $TAR_k(G)$ are in the same connected component.
Towards building a Crowd-Sourced Sky Map
Venue: arXiv cs.CV 2014
Year: 2014

We describe a system that builds a high dynamic-range and wide-angle image of the night sky by combining a large set of input images. The method makes use of pixel-rank information in the individual input images to improve a "consensus" pixel rank in the combined image. Because it only makes use of ranks and the complexity of the algorithm is linear in the number of images, the method is useful for large sets of uncalibrated images that might have undergone unknown non-linear tone mapping transformations for visualization or aesthetic reasons. We apply the method to images of the night sky (of unknown provenance) discovered on the Web. The method permits discovery of astronomical objects or features that are not visible in any of the input images taken individually. More importantly, however, it permits scientific exploitation of a huge source of astronomical images that would not be available to astronomical research without our automatic system.
Fuzzy clustering of web documents using equivalence relations and fuzzy hierarchical clustering
Venue: arXiv cs.IR 2014
Year: 2014

The conventional clustering algorithms have difficulties in handling the challenges posed by the collection of natural data which is often vague and uncertain. Fuzzy clustering methods have the potential to manage such situations efficiently. Fuzzy clustering method is offered to construct clusters with uncertain boundaries and allows that one object belongs to one or more clusters with some membership degree. In this paper, an algorithm and experimental results are presented for fuzzy clustering of web documents using equivalence relations and fuzzy hierarchical clustering.
Tsallis information dimension of complex networks
Venue: arXiv cs.SI 2014
Year: 2014

The fractal and self-similarity properties are revealed in many complex networks. In order to show the influence of different part in the complex networks to the information dimension, we have proposed a new information dimension based on Tsallis entropy namely Tsallis information dimension. The Tsallis information dimension can show the fractal property from different perspective by set different value of q.
Eigenvalues and Transduction of Morphic Sequences: Extended Version
Venue: arXiv cs.FL 2014
Year: 2014

We study finite state transduction of automatic and morphic sequences. Dekking proved that morphic sequences are closed under transduction and in particular morphic images. We present a simple proof of this fact, and use the construction in the proof to show that non-erasing transductions preserve a condition called alpha-substitutivity. Roughly, a sequence is alpha-substitutive if the sequence can be obtained as the limit of iterating a substitution with dominant eigenvalue alpha. Our results culminate in the following fact: for multiplicatively independent real numbers alpha and beta, if v is an alpha-substitutive sequence and w is a beta-substitutive sequence, then v and w have no common non-erasing transducts except for the ultimately periodic sequences. We rely on Cobham's theorem for substitutions, a recent result of Durand.