OpenRaiser/Intern-Atlas huggingface dataset:
Network-Coded Multiple Access
Venue: arXiv cs.NI 2013
Year: 2013

This paper proposes and experimentally demonstrates a first wireless local area network (WLAN) system that jointly exploits physical-layer network coding (PNC) and multiuser decoding (MUD) to boost system throughput. We refer to this multiple access mode as Network-Coded Multiple Access (NCMA). Prior studies on PNC mostly focused on relay networks. NCMA is the first realized multiple access scheme that establishes the usefulness of PNC in a non-relay setting. NCMA allows multiple nodes to transmit simultaneously to the access point (AP) to boost throughput. In the non-relay setting, when two nodes A and B transmit to the AP simultaneously, the AP aims to obtain both packet A and packet B rather than their network-coded packet. An interesting question is whether network coding, specifically PNC which extracts packet (A XOR B), can still be useful in such a setting. We provide an affirmative answer to this question with a novel two-layer decoding approach amenable to real-time implementation. Our USRP prototype indicates that NCMA can boost throughput by 100% in the medium-high SNR regime (>=10dB). We believe further throughput enhancement is possible by allowing more than two users to transmit together.
Optimal Power Allocation and User Loading for Multiuser MISO Channels with Regularized Channel Inversion
Venue: arXiv cs.IT 2013
Year: 2013

We consider a multiuser system where a single transmitter equipped with multiple antennas (the base station) communicates with multiple users each with a single antenna. Regularized channel inversion is employed as the precoding strategy at the base station. Within this scenario we are interested in the problems of power allocation and user admission control so as to maximize the system throughput, i.e., which users should we communicate with and what power should we use for each of the admitted users so as to get the highest sum rate. This is in general a very difficult problem but we do two things to allow some progress to be made. Firstly we consider the large system regime where the number of antennas at the base station is large along with the number of users. Secondly we cluster the downlink path gains of users into a finite number of groups. By doing this we are able to show that the optimal power allocation under an average transmit power constraint follows the well-known water filling scheme. We also investigate the user admission problem which reduces in the large system regime to optimization of the user loading in the system.
A Sub-block Based Image Retrieval Using Modified Integrated Region Matching
Venue: arXiv cs.IR 2013
Year: 2013

This paper proposes a content based image retrieval (CBIR) system using the local colour and texture features of selected image sub-blocks and global colour and shape features of the image. The image sub-blocks are roughly identified by segmenting the image into partitions of different configuration, finding the edge density in each partition using edge thresholding followed by morphological dilation. The colour and texture features of the identified regions are computed from the histograms of the quantized HSV colour space and Gray Level Co- occurrence Matrix (GLCM) respectively. The colour and texture feature vectors is computed for each region. The shape features are computed from the Edge Histogram Descriptor (EHD). A modified Integrated Region Matching (IRM) algorithm is used for finding the minimum distance between the sub-blocks of the query and target image. Experimental results show that the proposed method provides better retrieving result than retrieval using some of the existing methods.
Comparing Data-mining Algorithms Developed for Longitudinal Observational Databases
Venue: arXiv cs.LG 2013
Year: 2013

Longitudinal observational databases have become a recent interest in the post marketing drug surveillance community due to their ability of presenting a new perspective for detecting negative side effects. Algorithms mining longitudinal observation databases are not restricted by many of the limitations associated with the more conventional methods that have been developed for spontaneous reporting system databases. In this paper we investigate the robustness of four recently developed algorithms that mine longitudinal observational databases by applying them to The Health Improvement Network (THIN) for six drugs with well document known negative side effects. Our results show that none of the existing algorithms was able to consistently identify known adverse drug reactions above events related to the cause of the drug and no algorithm was superior.
Extending a Microsimulation of the Port of Dover
Venue: arXiv cs.CE 2013
Year: 2013

Modelling and simulating the traffic of heavily used but secure environments such as seaports and airports is of increasing importance. This paper discusses issues and problems that may arise when extending an existing microsimulation strategy. We also discuss how extensions of these simulations can aid planners with optimal physical and operational feedback. Conclusions are drawn about how microsimulations can be moved forward as a robust planning tool for the 21st century.
Supervised Learning and Anti-learning of Colorectal Cancer Classes and Survival Rates from Cellular Biology Parameters
Venue: arXiv cs.LG 2013
Year: 2013

In this paper, we describe a dataset relating to cellular and physical conditions of patients who are operated upon to remove colorectal tumours. This data provides a unique insight into immunological status at the point of tumour removal, tumour classification and post-operative survival. Attempts are made to learn relationships between attributes (physical and immunological) and the resulting tumour stage and survival. Results for conventional machine learning approaches can be considered poor, especially for predicting tumour stages for the most important types of cancer. This poor performance is further investigated and compared with a synthetic, dataset based on the logical exclusive-OR function and it is shown that there is a significant level of 'anti-learning' present in all supervised methods used and this can be explained by the highly dimensional, complex and sparsely representative dataset. For predicting the stage of cancer from the immunological attributes, anti-learning approaches outperform a range of popular algorithms.
Algorithmic Mechanisms for Reliable Internet-based Computing under Collusion
Venue: arXiv cs.DC 2013
Year: 2013

In this work, using a game-theoretic approach, cost-sensitive mechanisms that lead to reliable Internet-based computing are designed. In particular, we consider Internet-based master-worker computations, where a master processor assigns, across the Internet, a computational task to a set of potentially untrusted worker processors and collects their responses. Workers may collude in order to increase their benefit. Several game-theoretic models that capture the nature of the problem are analyzed, and algorithmic mechanisms that, for each given set of cost and system parameters, achieve high reliability are designed. Additionally, two specific realistic system scenarios are studied. These scenarios are a system of volunteer computing like SETI, and a company that buys computing cycles from Internet computers and sells them to its customers in the form of a task- computation service. Notably, under certain conditions, non redundant allocation yields the best trade-off between cost and reliability.
"The tail wags the dog": A study of anomaly detection in commercial application performance
Venue: arXiv cs.PF 2013
Year: 2013

The IT industry needs systems management models that leverage available application information to detect quality of service, scalability and health of service. Ideally this technique would be common for varying application types with different n-tier architectures under normal production conditions of varying load, user session traffic, transaction type, transaction mix, and hosting environment. This paper shows that a whole of service measurement paradigm utilizing a black box M/M/1 queuing model and auto regression curve fitting of the associated CDF are an accurate model to characterize system performance signatures. This modeling method is also used to detect application slow down events. The technique was shown to work for a diverse range of workloads ranging from 76 Tx/ 5min to 19,025 Tx/ 5min. The method did not rely on customizations specific to the n-tier architecture of the systems being analyzed and so the performance anomaly detection technique was shown to be platform and configuration agnostic.
MacWilliams type identities for some new $m$-spotty weight enumerators over finite commutative Frobenius rings
Venue: arXiv cs.IT 2013
Year: 2013

Past few years have seen an extensive use of RAM chips with wide I/O data (e.g. 16, 32, 64 bits) in computer memory systems. These chips are highly vulnerable to a special type of byte error, called an $m$-spotty byte error, which can be effectively detected or corrected using byte error-control codes. The MacWilliams identity provides the relationship between the weight distribution of a code and that of its dual. This paper introduces $m$-spotty Hamming weight enumerator, joint $m$-spotty Hamming weight enumerator and split $m$-spotty Hamming weight enumerator for byte error-control codes over finite commutative Frobenius rings as well as $m$-spotty Lee weight enumerator over an infinite family of rings. In addition, MacWilliams type identities are also derived for these enumerators.
Fuzzy Integer Linear Programming Mathematical Models for Examination Timetable Problem
Venue: arXiv cs.AI 2013
Year: 2013

ETP is NP Hard combinatorial optimization problem. It has received tremendous research attention during the past few years given its wide use in universities. In this Paper, we develop three mathematical models for NSOU, Kolkata, India using FILP technique. To deal with impreciseness and vagueness we model various allocation variables through fuzzy numbers. The solution to the problem is obtained using Fuzzy number ranking method. Each feasible solution has fuzzy number obtained by Fuzzy objective function. The different FILP technique performance are demonstrated by experimental data generated through extensive simulation from NSOU, Kolkata, India in terms of its execution times. The proposed FILP models are compared with commonly used heuristic viz. ILP approach on experimental data which gives an idea about quality of heuristic. The techniques are also compared with different Artificial Intelligence based heuristics for ETP with respect to best and mean cost as well as execution time measures on Carter benchmark datasets to illustrate its effectiveness. FILP takes an appreciable amount of time to generate satisfactory solution in comparison to other heuristics. The formulation thus serves as good benchmark for other heuristics. The experimental study presented here focuses on producing a methodology that generalizes well over spectrum of techniques that generates significant results for one or more datasets. The performance of FILP model is finally compared to the best results cited in literature for Carter benchmarks to assess its potential. The problem can be further reduced by formulating with lesser number of allocation variables it without affecting optimality of solution obtained. FLIP model for ETP can also be adapted to solve other ETP as well as combinatorial optimization problems.
Full-text Support for Publish/Subscribe Ontology Systems
Venue: arXiv cs.IR 2013
Year: 2013

We envision a publish/subscribe ontology system that is able to index millions of user subscriptions and filter them against ontology data that arrive in a streaming fashion. In this work, we propose a SPARQL extension appropriate for a publish/subscribe setting; our extension builds on the natural semantic graph matching of the language and supports the creation of full-text subscriptions. Subsequently, we propose a main-memory subscription indexing algorithm which performs both semantic and full-text matching at low complexity and minimal filtering time. Thus, when ontology data are published matching subscriptions are identified and notifications are forwarded to users.
Mixed Compressed Sensing Based on Random Graphs
Venue: arXiv cs.IT 2013
Year: 2013

Finding a suitable measurement matrix is an important topic in compressed sensing. Though the known random matrix, whose entries are drawn independently from a certain probability distribution, can be used as a measurement matrix and recover signal well, in most cases, we hope the measurement matrix imposed with some special structure. In this paper, based on random graph models, we show that the mixed symmetric random matrices, whose diagonal entries obey a distribution and non-diagonal entries obey another distribution, can be used to recover signal successfully with high probability.
TDOA assisted RSSD based localization using UWB and directional antennas
Venue: arXiv cs.IT 2013
Year: 2013

This paper studies the use of directional antennas for received signal strength difference (RSSD) based localization using ultra-wideband and demonstrates the achievable accuracy with this localization method applied to UWB. As introduced in our previous work the RSSD localization is assisted with one Time Difference of Arrival (TDOA) estimation. The use of directional receiving antennas and an omni-directional transmitting antenna is assumed. Localization is performed in 2D. Two localization approaches are considered: RSSD using statistical channel model and fingerprinting approach. In the case of statistical channel model simulations are performed using Matlab. In the case of fingerprinting approach localization is done based on real indoor-measurements.
Dynamic Partial Cooperative MIMO System for Delay-Sensitive Applications with Limited Backhaul Capacity
Venue: arXiv cs.IT 2013
Year: 2013

Considering backhaul consumption in practical systems, it may not be the best choice to engage all the time in full cooperative MIMO for interference mitigation. In this paper, we propose a novel downlink partial cooperative MIMO (Pco-MIMO) physical layer (PHY) scheme, which allows flexible tradeoff between the partial data cooperation level and the backhaul consumption. Based on this Pco-MIMO scheme, we consider dynamic transmit power and rate allocation according to the imperfect channel state information at transmitters (CSIT) and the queue state information (QSI) to minimize the average delay cost subject to average backhaul consumption constraints and average power constraints. The delay-optimal control problem is formulated as an infinite horizon average cost constrained partially observed Markov decision process (CPOMDP). By exploiting the special structure in our problem, we derive an equivalent Bellman Equation to solve the CPOMDP. To reduce computational complexity and facilitate distributed implementation, we propose a distributed online learning algorithm to estimate the per-flow potential functions and Lagrange multipliers (LMs) and a distributed online stochastic partial gradient algorithm to obtain the power and rate control policy. The proposed low-complexity distributed solution is based on local observations of the system states at the BSs and is very robust against model variations. We also prove the convergence and the asymptotic optimality of the proposed solution.
A Taxonomy of Performance Prediction Systems in the Parallel and Distributed Computing Grids
Venue: arXiv cs.DC 2013
Year: 2013

As Grids are loosely-coupled congregations of geographically distributed heterogeneous resources, the efficient utilization of the resources requires the support of a sound Performance Prediction System (PPS). The performance prediction of grid resources is helpful for both Resource Management Systems and grid users to make optimized resource usage decisions. There have been many PPS projects that span over several grid resources in several dimensions. In this paper the taxonomy for describing the PPS architecture is discussed. The taxonomy is used to categorize and identify approaches which are followed in the implementation of the existing PPSs for Grids. The taxonomy and the survey results are used to identify approaches and issues that have not been fully explored in research.
Local Mode Dependent Decentralized $H_{\infty}$ Control of Uncertain Markovian Jump Large-scale Systems
Venue: arXiv cs.SY 2013
Year: 2013

This paper considers the problem of robust $H_{\infty}$ control using decentralized state feedback controllers for a class of large-scale systems with Markov jump parameters. A sufficient condition is developed to design controllers using local system states and local system operation modes. The sufficient condition is given in terms of rank constrained linear matrix inequalities. An illustrative numerical example is given to demonstrate the developed theory.
Iterative Byzantine Vector Consensus in Incomplete Graphs
Venue: arXiv cs.DC 2013
Year: 2013

This work addresses Byzantine vector consensus (BVC), wherein the input at each process is a d-dimensional vector of reals, and each process is expected to decide on a decision vector that is in the convex hull of the input vectors at the fault-free processes [3, 8]. The input vector at each process may also be viewed as a point in the d-dimensional Euclidean space R^d, where d > 0 is a finite integer. Recent work [3, 8] has addressed Byzantine vector consensus in systems that can be modeled by a complete graph. This paper considers Byzantine vector consensus in incomplete graphs. In particular, we address a particular class of iterative algorithms in incomplete graphs, and prove a necessary condition, and a sufficient condition, for the graphs to be able to solve the vector consensus problem iteratively. We present an iterative Byzantine vector consensus algorithm, and prove it correct under the sufficient condition. The necessary condition presented in this paper for vector consensus does not match with the sufficient condition for d > 1; thus, a weaker condition may potentially suffice for Byzantine vector consensus.
Better Approximation Bounds for the Joint Replenishment Problem
Venue: arXiv cs.DS 2013
Year: 2013

The Joint Replenishment Problem (JRP) deals with optimizing shipments of goods from a supplier to retailers through a shared warehouse. Each shipment involves transporting goods from the supplier to the warehouse, at a fixed cost C, followed by a redistribution of these goods from the warehouse to the retailers that ordered them, where transporting goods to a retailer $ρ$ has a fixed cost $c_ρ$. In addition, retailers incur waiting costs for each order. The objective is to minimize the overall cost of satisfying all orders, namely the sum of all shipping and waiting costs. JRP has been well studied in Operations Research and, more recently, in the area of approximation algorithms. For arbitrary waiting cost functions, the best known approximation ratio is 1.8. This ratio can be reduced to 1.574 for the JRP-D model, where there is no cost for waiting but orders have deadlines. As for hardness results, it is known that the problem is APX-hard and that the natural linear program for JRP has integrality gap at least 1.245. Both results hold even for JRP-D. In the online scenario, the best lower and upper bounds on the competitive ratio are 2.64 and 3, respectively. The lower bound of 2.64 applies even to the restricted version of JRP, denoted JRP-L, where the waiting cost function is linear. We provide several new approximation results for JRP. In the offline case, we give an algorithm with ratio 1.791, breaking the barrier of 1.8. In the online case, we show a lower bound of 2.754 on the competitive ratio for JRP-L (and thus JRP as well), improving the previous bound of 2.64. We also study the online version of JRP-D, for which we prove that the optimal competitive ratio is 2.
Geospatial Narratives and their Spatio-Temporal Dynamics: Commonsense Reasoning for High-level Analyses in Geographic Information Systems
Venue: arXiv cs.AI 2013
Year: 2013

The modelling, analysis, and visualisation of dynamic geospatial phenomena has been identified as a key developmental challenge for next-generation Geographic Information Systems (GIS). In this context, the envisaged paradigmatic extensions to contemporary foundational GIS technology raises fundamental questions concerning the ontological, formal representational, and (analytical) computational methods that would underlie their spatial information theoretic underpinnings. We present the conceptual overview and architecture for the development of high-level semantic and qualitative analytical capabilities for dynamic geospatial domains. Building on formal methods in the areas of commonsense reasoning, qualitative reasoning, spatial and temporal representation and reasoning, reasoning about actions and change, and computational models of narrative, we identify concrete theoretical and practical challenges that accrue in the context of formal reasoning about `space, events, actions, and change'. With this as a basis, and within the backdrop of an illustrated scenario involving the spatio-temporal dynamics of urban narratives, we address specific problems and solutions techniques chiefly involving `qualitative abstraction', `data integration and spatial consistency', and `practical geospatial abduction'. From a broad topical viewpoint, we propose that next-generation dynamic GIS technology demands a transdisciplinary scientific perspective that brings together Geography, Artificial Intelligence, and Cognitive Science. Keywords: artificial intelligence; cognitive systems; human-computer interaction; geographic information systems; spatio-temporal dynamics; computational models of narrative; geospatial analysis; geospatial modelling; ontology; qualitative spatial modelling and reasoning; spatial assistance systems
Tuned Models of Peer Assessment in MOOCs
Venue: arXiv cs.LG 2013
Year: 2013

In massive open online courses (MOOCs), peer grading serves as a critical tool for scaling the grading of complex, open-ended assignments to courses with tens or hundreds of thousands of students. But despite promising initial trials, it does not always deliver accurate results compared to human experts. In this paper, we develop algorithms for estimating and correcting for grader biases and reliabilities, showing significant improvement in peer grading accuracy on real data with 63,199 peer grades from Coursera's HCI course offerings --- the largest peer grading networks analysed to date. We relate grader biases and reliabilities to other student factors such as student engagement, performance as well as commenting style. We also show that our model can lead to more intelligent assignment of graders to gradees.
Rising tides or rising stars?: Dynamics of shared attention on Twitter during media events
Venue: arXiv cs.SI 2013
Year: 2013

"Media events" such as political debates generate conditions of shared attention as many users simultaneously tune in with the dual screens of broadcast and social media to view and participate. Are collective patterns of user behavior under conditions of shared attention distinct from other "bursts" of activity like breaking news events? Using data from a population of approximately 200,000 politically-active Twitter users, we compare features of their behavior during eight major events during the 2012 U.S. presidential election to examine (1) the impact of "media events" have on patterns of social media use compared to "typical" time and (2) whether changes during media events are attributable to changes in behavior across the entire population or an artifact of changes in elite users' behavior. Our findings suggest that while this population became more active during media events, this additional activity reflects concentrated attention to a handful of users, hashtags, and tweets. Our work is the first study on distinguishing patterns of large-scale social behavior under condition of uncertainty and shared attention, suggesting new ways of mining information from social media to support collective sensemaking following major events.