OpenRaiser/Intern-Atlas huggingface dataset:
Co-primary inter-operator spectrum sharing over a limited spectrum pool using repeated games
Venue: arXiv cs.NI 2015
Year: 2015

We consider two small cell operators deployed in the same geographical area, sharing spectrum resources from a common pool. A method is investigated to coordinate the utilization of the spectrum pool without monetary transactions and without revealing operator-specific information to other parties. For this, we construct a protocol based on asking and receiving spectrum usage favors by the operators, and keeping a book of the favors. A spectrum usage favor is exchanged between the operators if one is asking for a permission to use some of the resources from the pool on an exclusive basis, and the other is willing to accept that. As a result, the proposed method does not force an operator to take action. An operator with a high load may take spectrum usage favors from an operator that has few users to serve, and it is likely to return these favors in the future to show a cooperative spirit and maintain reciprocity. We formulate the interactions between the operators as a repeated game and determine rules to decide whether to ask or grant a favor at each stage game. We illustrate that under frequent network load variations, which are expected to be prominent in small cell deployments, both operators can attain higher user rates as compared to the case of no coordination of the resource utilization.
Effects of Nonparanormal Transform on PC and GES Search Accuracies
Venue: arXiv cs.AI 2015
Year: 2015

Liu, et al., 2009 developed a transformation of a class of non-Gaussian univariate distributions into Gaussian distributions. Liu and collaborators (2012) subsequently applied the transform to search for graphical causal models for a number of empirical data sets. To our knowledge, there has been no published investigation by simulation of the conditions under which the transform aids, or harms, standard graphical model search procedures. We consider here how the transform affects the performance of two search algorithms in particular, PC (Spirtes et al., 2000; Meek 1995) and GES (Meek 1997; Chickering 2002). We find that the transform is harmless but ineffective for most cases but quite effective in very special cases for GES, namely, for moderate non-Gaussianity and moderate non-linearity. For strong-linearity, another algorithm, PC-GES (a combination of PC with GES), is equally effective.
Jointly Modeling Embedding and Translation to Bridge Video and Language
Venue: arXiv cs.CV 2015
Year: 2015

Automatically describing video content with natural language is a fundamental challenge of multimedia. Recurrent Neural Networks (RNN), which models sequence dynamics, has attracted increasing attention on visual interpretation. However, most existing approaches generate a word locally with given previous words and the visual content, while the relationship between sentence semantics and visual content is not holistically exploited. As a result, the generated sentences may be contextually correct but the semantics (e.g., subjects, verbs or objects) are not true. This paper presents a novel unified framework, named Long Short-Term Memory with visual-semantic Embedding (LSTM-E), which can simultaneously explore the learning of LSTM and visual-semantic embedding. The former aims to locally maximize the probability of generating the next word given previous words and visual content, while the latter is to create a visual-semantic embedding space for enforcing the relationship between the semantics of the entire sentence and visual content. Our proposed LSTM-E consists of three components: a 2-D and/or 3-D deep convolutional neural networks for learning powerful video representation, a deep RNN for generating sentences, and a joint embedding model for exploring the relationships between visual content and sentence semantics. The experiments on YouTube2Text dataset show that our proposed LSTM-E achieves to-date the best reported performance in generating natural sentences: 45.3% and 31.0% in terms of BLEU@4 and METEOR, respectively. We also demonstrate that LSTM-E is superior in predicting Subject-Verb-Object (SVO) triplets to several state-of-the-art techniques.
Multiplayer Games and their Need for Scalable and Secure State Management
Venue: arXiv cs.CY 2015
Year: 2015

In recent years, massively multiplayer online games (MMOGs) have become very popular by providing more entertainment, therefore millions of players now participate may interact with each other in a shared environment, even though these players may be separated by huge geographic distances. Peer to Peer (P2P) architectures become very popular in MMOG recently, due to their distributed and collaborative nature, have low infrastructure costs, achieve fast response times by creating direct connections between players and can achieve high scalability. However, P2P architectures face many challenges and tend to be vulnerable to cheating. Game distribution between peers makes maintaining control of the game becomes more complicated. Therefore, broadcasting all state changes to every player is not a viable solution to maintain a consistent game state in a MMOGs. To successfully overcome the challenge of scale, MMOGs have to employ sophisticated interest management techniques that only send relevant state changes to each player. In this paper, In order to prevent cheaters to gain unfair advantages in P2P-based MMOGs, several cheat-proof schemes have been proposed that utilize a range of techniques such as cryptographic mechanisms, Commitment and agreement protocols, and proxy architecture.
Fault Detection in C Programs using Monitoring of Range Values: Preliminary Results
Venue: arXiv cs.SE 2015
Year: 2015

This technical report presents the work done as part of the AutoSeer project. Our work in this project was to develop a source-to-source compiler, MANET, for the C language that could be used for instrumentation of critical parts of applications under testing. The intention was to guide the compilation flow and define instrumentation strategies using the Aspect-Oriented Approach provided by LARA. This allows a separation of the original target application and the instrumentation secondary concerns. One of the goals of this work was the development of a source-to-source C compiler that modifies code according to an input strategy. These modifications could provide code transformations that target performance and instrumentation for debugging, but in this work they are used to inject code that collects information about the values that certain variables take during runtime. This compiler is supported by an AOP approach that enables the definition of instrumentation strategies. We decided to extend an existing source-to-source compiler, Cetus, and couple it with LARA, an AOP language that is partially abstracted from the target programming language. We propose and evaluate an approach to detect faults in C programs by monitoring the range values of variables. We consider various monitoring strategies and use two real-life applications, the GZIP file compressor and ABS, a program provided by an industrial partner. The different strategies were specified in LARA and automatically applied using MANET. The experimental results show that our approach has potential but is hindered by not accounting for values in arrays and control variables. We achieve prediction accuracies of around 54% for ABS and 83% for GZIP, when comparing our approach to a more traditional one, where the outputs are compared to an expected result.
Data Attacks on Power Grids: Leveraging Detection
Venue: arXiv cs.CR 2015
Year: 2015

Data attacks on meter measurements in the power grid can lead to errors in state estimation. This paper presents a new data attack model where an adversary produces changes in state estimation despite failing bad-data detection checks. The adversary achieves its objective by making the estimator incorrectly identify correct measurements as bad data. The proposed attack regime's significance lies in reducing the minimum sizes of successful attacks to more than half of that of undetectable data attacks. Additionally, the attack model is able to construct attacks on systems that are resilient to undetectable attacks. The conditions governing a successful data attack of the proposed model are presented along with guarantees on its performance. The complexity of constructing an optimal attack is discussed and two polynomial time approximate algorithms for attack vector construction are developed. The performance of the proposed algorithms and efficacy of the hidden attack model are demonstrated through simulations on IEEE test systems.
Characterization of Performance Anomalies in Hadoop
Venue: arXiv cs.DC 2015
Year: 2015

With the huge variety of data and equally large-scale systems, there is not a unique execution setting for these systems which can guarantee the best performance for each query. In this project, we tried so study the impact of different execution settings on execution time of workloads by varying them one at a time. Using the data from these experiments, a decision tree was built where each internal node represents the execution parameter, each branch represents value chosen for the parameter and each leaf node represents a range for execution time in minutes. The attribute in the decision tree to split the dataset on is selected based on the maximum information gain or lowest entropy. Once the tree is trained with the training samples, this tree can be used to get approximate range for the expected execution time. When the actual execution time differs from this expected value, a performance anomaly can be detected. For a test dataset with 400 samples, 99% of samples had actual execution time in the range predicted time by the decision tree. Also on analyzing the constructed tree, an idea about what configuration can give better performance for a given workload can be obtained. Initial experiments suggest that the impact an execution parameter can have on the target attribute (here execution time) can be related to the distance of that feature node from the root of the constructed decision tree. From initial results the percent change in the values of the target attribute for various value of the feature node which is closer to the root is 6 times larger than when that same iii feature node is away from the root node. This observation will depend on how well the decision tree was trained and may not be true for every case.
Symbol Based Precoding in The Downlink of Cognitive MISO Channels
Venue: arXiv cs.IT 2015
Year: 2015

This paper proposes symbol level precoding in the downlink of a MISO cognitive system. The new scheme tries to jointly utilize the data and channel information to design a precoding that minimizes the transmit power at a cognitive base station (CBS); without violating the interference temperature constraint imposed by the primary system. In this framework, the data information is handled at symbol level which enables the characterization the intra-user interference among the cognitive users as an additional source of useful energy that should be exploited. A relation between the constructive multiuser transmissions and physical-layer multicast system is established. Extensive simulations are performed to validate the proposed technique and compare it with conventional techniques.
A Team Based Variant of CTL
Venue: arXiv cs.LO 2015
Year: 2015

We introduce two variants of computation tree logic CTL based on team semantics: an asynchronous one and a synchronous one. For both variants we investigate the computational complexity of the satisfiability as well as the model checking problem. The satisfiability problem is shown to be EXPTIME-complete. Here it does not matter which of the two semantics are considered. For model checking we prove a PSPACE-completeness for the synchronous case, and show P-completeness for the asynchronous case. Furthermore we prove several interesting fundamental properties of both semantics.
Duursma's reduced polynomial
Venue: arXiv cs.IT 2015
Year: 2015

The weight distribution of a linear code C is put in an explicit bijective correspondence with Duursma's reduced polynomial of C. We prove that the Riemann Hypothesis Analogue for a linear code C requires the formal self-duality of C and imposes an upper bound on the cardinality q of the basic field, depending on the dimension and the minimum distance of C. Duursma's reduced polynomial of the function field of a curve X of genus g over the field with q elements is shown to provide a generating function for the numbers of the effective divisors of non-negative degree degree of a virtual function field of a curve of genus g-1 over the same finite field.
DDA: Cross-Session Throughput Prediction with Applications to Video Bitrate Selection
Venue: arXiv cs.NI 2015
Year: 2015

User experience of video streaming could be greatly improved by selecting a high-yet-sustainable initial video bitrate, and it is therefore critical to accurately predict throughput before a video session starts. Inspired by previous studies that show similarity among throughput of similar sessions (e.g., those sharing same bottleneck link), we argue for a cross-session prediction approach, where throughput measured on other sessions is used to predict the throughput of a new session. In this paper, we study the challenges of cross-session throughput prediction, develop an accurate throughput predictor called DDA, and evaluate the performance of the predictor with real-world datasets. We show that DDA can predict throughput more accurately than simple predictors and conventional machine learning algorithms; e.g., DDA's 80%ile prediction error of DDA is > 50% lower than other algorithms. We also show that this improved accuracy enables video players to select a higher sustainable initial bitrate; e.g., compared to initial bitrate without prediction, DDA leads to 4x higher average bitrate.
Sensor Fault Detection, Isolation and Identification Using Multiple Model-based Hybrid Kalman Filter for Gas Turbine Engines
Venue: arXiv cs.SY 2015
Year: 2015

In this paper, a novel sensor fault detection, isolation and identification (FDII) strategy is proposed by using the multiple model (MM) approach. The scheme is based on multiple hybrid Kalman filters (HKF) which represents an integration of a nonlinear mathematical model of the system with a number of piecewise linear (PWL) models. The proposed fault detection and isolation (FDI) scheme is capable of detecting and isolating sensor faults during the entire operational regime of the system by interpolating the PWL models using a Bayesian approach. Moreover, the proposed multiple HKF-based FDI scheme is extended to identify the magnitude of a sensor fault by using a modified generalized likelihood ratio (GLR) method which relies on the healthy operational mode of the system. To illustrate the capabilities of our proposed FDII methodology, extensive simulation studies are conducted for a nonlinear gas turbine engine. Various single and concurrent sensor fault scenarios are considered to demonstrate the effectiveness of our proposed on-line hierarchical multiple HKF-based FDII scheme under different flight modes. Finally, our proposed HKF-based FDI approach is compared with various filtering methods such as the linear, extended, unscented and cubature Kalman filters (LKF, EKF, UKF and CKF, respectively) corresponding to both interacting and non-interacting multiple model (MM) based schemes. Our comparative studies confirm the superiority of our proposed HKF method in terms of promptness of the fault detection, lower false alarm rates, as well as robustness with respect to the engine health parameters degradations.
Probabilistic Cascading for Large Scale Hierarchical Classification
Venue: arXiv cs.LG 2015
Year: 2015

Hierarchies are frequently used for the organization of objects. Given a hierarchy of classes, two main approaches are used, to automatically classify new instances: flat classification and cascade classification. Flat classification ignores the hierarchy, while cascade classification greedily traverses the hierarchy from the root to the predicted leaf. In this paper we propose a new approach, which extends cascade classification to predict the right leaf by estimating the probability of each root-to-leaf path. We provide experimental results which indicate that, using the same classification algorithm, one can achieve better results with our approach, compared to the traditional flat and cascade classifications.
Computing maximal autarkies with few and simple oracle queries
Venue: arXiv cs.LO 2015
Year: 2015

We consider the algorithmic task of computing a maximal autarky for a clause-set F, i.e., a partial assignment which satisfies every clause of F it touches, and where this property is destroyed by adding any non-empty set of further assignments. We employ SAT solvers as oracles, using various capabilities. Using the standard SAT oracle, log_2(n(F)) oracle calls suffice, where n(F) is the number of variables, but the drawback is that (translated) cardinality constraints are employed, which makes this approach less efficient in practice. Using an extended SAT oracle, motivated by the capabilities of modern SAT solvers, we show how to compute maximal autarkies with 2 n(F)^{1/2} simpler oracle calls. This novel algorithm combines the previous two main approaches, based on the autarky-resolution duality and on SAT translations.
Exploiting Resolution-based Representations for MaxSAT Solving
Venue: arXiv cs.AI 2015
Year: 2015

Most recent MaxSAT algorithms rely on a succession of calls to a SAT solver in order to find an optimal solution. In particular, several algorithms take advantage of the ability of SAT solvers to identify unsatisfiable subformulas. Usually, these MaxSAT algorithms perform better when small unsatisfiable subformulas are found early. However, this is not the case in many problem instances, since the whole formula is given to the SAT solver in each call. In this paper, we propose to partition the MaxSAT formula using a resolution-based graph representation. Partitions are then iteratively joined by using a proximity measure extracted from the graph representation of the formula. The algorithm ends when only one partition remains and the optimal solution is found. Experimental results show that this new approach further enhances a state of the art MaxSAT solver to optimally solve a larger set of industrial problem instances.
EntropyWalker, a Fast Algorithm for Small Community Detection in Large Graphs
Venue: arXiv cs.SI 2015
Year: 2015

This report presents a very simple algorithm for overlaping community-detection in large graphs under constraints such as the minimum and maximum number of members allowed. The algorithm is based on the simulation of random walks and measures the entropy of each random walk to detect the discovery of a community.
DistMS: A Non-Portfolio Distributed Solver for Maximum Satisfiability
Venue: arXiv cs.LO 2015
Year: 2015

The most successful parallel SAT and MaxSAT solvers follow a portfolio approach, where each thread applies a different algorithm (or the same algorithm configured differently) to solve a given problem instance. The main goal of building a portfolio is to diversify the search process being carried out by each thread. As soon as one thread finishes, the instance can be deemed solved. In this paper we present a new open source distributed solver for MaxSAT solving that addresses two issues commonly found in multicore parallel solvers, namely memory contention and scalability. Preliminary results show that our non-portfolio distributed MaxSAT solver outperforms its sequential version and is able to solve more instances as the number of processes increases.
Aggregate Estimations over Location Based Services
Venue: arXiv cs.DB 2015
Year: 2015

Location based services (LBS) have become very popular in recent years. They range from map services (e.g., Google Maps) that store geographic locations of points of interests, to online social networks (e.g., WeChat, Sina Weibo, FourSquare) that leverage user geographic locations to enable various recommendation functions. The public query interfaces of these services may be abstractly modeled as a kNN interface over a database of two dimensional points on a plane: given an arbitrary query point, the system returns the k points in the database that are nearest to the query point. In this paper we consider the problem of obtaining approximate estimates of SUM and COUNT aggregates by only querying such databases via their restrictive public interfaces. We distinguish between interfaces that return location information of the returned tuples (e.g., Google Maps), and interfaces that do not return location information (e.g., Sina Weibo). For both types of interfaces, we develop aggregate estimation algorithms that are based on novel techniques for precisely computing or approximately estimating the Voronoi cell of tuples. We discuss a comprehensive set of real-world experiments for testing our algorithms, including experiments on Google Maps, WeChat, and Sina Weibo.
Eliminating Recursion from Monadic Datalog Programs on Trees
Venue: arXiv cs.LO 2015
Year: 2015

We study the problem of eliminating recursion from monadic datalog programs on trees with an infinite set of labels. We show that the boundedness problem, i.e., determining whether a datalog program is equivalent to some nonrecursive one is undecidable but the decidability is regained if the descendant relation is disallowed. Under similar restrictions we obtain decidability of the problem of equivalence to a given nonrecursive program. We investigate the connection between these two problems in more detail.
A Survey on Truth Discovery
Venue: arXiv cs.DB 2015
Year: 2015

Thanks to information explosion, data for the objects of interest can be collected from increasingly more sources. However, for the same object, there usually exist conflicts among the collected multi-source information. To tackle this challenge, truth discovery, which integrates multi-source noisy information by estimating the reliability of each source, has emerged as a hot topic. Several truth discovery methods have been proposed for various scenarios, and they have been successfully applied in diverse application domains. In this survey, we focus on providing a comprehensive overview of truth discovery methods, and summarizing them from different aspects. We also discuss some future directions of truth discovery research. We hope that this survey will promote a better understanding of the current progress on truth discovery, and offer some guidelines on how to apply these approaches in application domains.
Training Deeper Convolutional Networks with Deep Supervision
Venue: arXiv cs.CV 2015
Year: 2015

One of the most promising ways of improving the performance of deep convolutional neural networks is by increasing the number of convolutional layers. However, adding layers makes training more difficult and computationally expensive. In order to train deeper networks, we propose to add auxiliary supervision branches after certain intermediate layers during training. We formulate a simple rule of thumb to determine where these branches should be added. The resulting deeply supervised structure makes the training much easier and also produces better classification results on ImageNet and the recently released, larger MIT Places dataset