OpenRaiser/Intern-Atlas huggingface dataset:
The Unit-Demand Envy-Free Pricing Problem
Venue: arXiv cs.GT 2013
Year: 2013

We consider the unit-demand envy-free pricing problem, which is a unit-demand auction where each bidder receives an item that maximizes his utility, and the goal is to maximize the auctioneer's profit. This problem is NP-hard and unlikely to be in APX. We present four new MIP formulations for it and experimentally compare them to a previous one due to Shioda, Tunçel, and Myklebust. We describe three models to generate different random instances for general unit-demand auctions, that we designed for the computational experiments. Each model has a nice economic interpretation. Aiming approximation results, we consider the variant of the problem where the item prices are restricted to be chosen from a geometric series, and prove that an optimal solution for this variant has value that is a fraction (depending on the series used) of the optimal value of the original problem. So this variant is also unlikely to be in APX.
An information measure for comparing top $k$ lists
Venue: arXiv cs.IT 2013
Year: 2013

Comparing the top $k$ elements between two or more ranked results is a common task in many contexts and settings. A few measures have been proposed to compare top $k$ lists with attractive mathematical properties, but they face a number of pitfalls and shortcomings in practice. This work introduces a new measure to compare any two top k lists based on measuring the information these lists convey. Our method investigates the compressibility of the lists, and the length of the message to losslessly encode them gives a natural and robust measure of their variability. This information-theoretic measure objectively reconciles all the main considerations that arise when measuring (dis-)similarity between lists: the extent of their non-overlapping elements in each of the lists; the amount of disarray among overlapping elements between the lists; the measurement of displacement of actual ranks of their overlapping elements.
Exact counting of Euler Tours for Graphs of Bounded Treewidth
Venue: arXiv cs.DM 2013
Year: 2013

In this paper we give a simple polynomial-time algorithm to exactly count the number of Euler Tours (ETs) of any Eulerian graph of bounded treewidth. The problems of counting ETs are known to be #P-complete for general graphs (Brightwell and Winkler, (Brightwell and Winkler, 2005). To date, no polynomial-time algorithm for counting Euler tours of any class of graphs is known except for the very special case of series-parallel graphs (which have treewidth 2).
Filtering for More Accurate Dense Tissue Segmentation in Digitized Mammograms
Venue: arXiv cs.CV 2013
Year: 2013

Breast tissue segmentation into dense and fat tissue is important for determining the breast density in mammograms. Knowing the breast density is important both in diagnostic and computer-aided detection applications. There are many different ways to express the density of a breast and good quality segmentation should provide the possibility to perform accurate classification no matter which classification rule is being used. Knowing the right breast density and having the knowledge of changes in the breast density could give a hint of a process which started to happen within a patient. Mammograms generally suffer from a problem of different tissue overlapping which results in the possibility of inaccurate detection of tissue types. Fibroglandular tissue presents rather high attenuation of X-rays and is visible as brighter in the resulting image but overlapping fibrous tissue and blood vessels could easily be replaced with fibroglandular tissue in automatic segmentation algorithms. Small blood vessels and microcalcifications are also shown as bright objects with similar intensities as dense tissue but do have some properties which makes possible to suppress them from the final results. In this paper we try to divide dense and fat tissue by suppressing the scattered structures which do not represent glandular or dense tissue in order to divide mammograms more accurately in the two major tissue types. For suppressing blood vessels and microcalcifications we have used Gabor filters of different size and orientation and a combination of morphological operations on filtered image with enhanced contrast.
Computer Vision Systems in Road Vehicles: A Review
Venue: arXiv cs.CV 2013
Year: 2013

The number of road vehicles significantly increased in recent decades. This trend accompanied a build-up of road infrastructure and development of various control systems to increase road traffic safety, road capacity and travel comfort. In traffic safety significant development has been made and today's systems more and more include cameras and computer vision methods. Cameras are used as part of the road infrastructure or in vehicles. In this paper a review on computer vision systems in vehicles from the stand point of traffic engineering is given. Safety problems of road vehicles are presented, current state of the art in-vehicle vision systems is described and open problems with future research directions are discussed.
The complex-valued encoding for dicision-making based on aliasing data
Venue: arXiv cs.CV 2013
Year: 2013

It is proposed a complex valued channel encoding for multidimensional data. The basic approach contains overlapping of complex nonlinear mappings. Its development leads to sparse representation of multi-channel data, increasing their dimensions and the distance between the images.
Incentive Design for Direct Load Control Programs
Venue: arXiv cs.SY 2013
Year: 2013

We study the problem of optimal incentive design for voluntary participation of electricity customers in a Direct Load Scheduling (DLS) program, a new form of Direct Load Control (DLC) based on a three way communication protocol between customers, embedded controls in flexible appliances, and the central entity in charge of the program. Participation decisions are made in real-time on an event-based basis, with every customer that needs to use a flexible appliance considering whether to join the program given current incentives. Customers have different interpretations of the level of risk associated with committing to pass over the control over the consumption schedule of their devices to an operator, and these risk levels are only privately known. The operator maximizes his expected profit of operating the DLS program by posting the right participation incentives for different appliance types, in a publicly available and dynamically updated table. Customers are then faced with the dynamic decision making problem of whether to take the incentives and participate or not. We define an optimization framework to determine the profit-maximizing incentives for the operator. In doing so, we also investigate the utility that the operator expects to gain from recruiting different types of devices. These utilities also provide an upper-bound on the benefits that can be attained from any type of demand response program.
Near-Capacity Adaptive Analog Fountain Codes for Wireless Channels
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, we propose a capacity-approaching analog fountain code (AFC) for wireless channels. In AFC, the number of generated coded symbols is potentially limitless. In contrast to the conventional binary rateless codes, each coded symbol in AFC is a real-valued symbol, generated as a weighted sum of $d$ randomly selected information bits, where $d$ and the weight coefficients are randomly selected from predefined probability mass functions. The coded symbols are then directly transmitted through wireless channels. We analyze the error probability of AFC and design the weight set to minimize the error probability. Simulation results show that AFC achieves the capacity of the Gaussian channel in a wide range of signal to noise ratio (SNR).
Design of Generic Framework for Botnet Detection in Network Forensics
Venue: arXiv cs.CR 2013
Year: 2013

With the raise in practice of Internet, in social, personal, commercial and other aspects of life, the cybercrime is as well escalating at an alarming rate. Such usage of Internet in diversified areas also augmented the illegal activities, which in turn, bids many network attacks and threats. Network forensics is used to detect the network attacks. This can be viewed as the extension of network security. It is the technology, which detects and also suggests prevention of the various network attacks. Botnet is one of the most common attacks and is regarded as a network of hacked computers. It captures the network packet, store it and then analyze and correlate to find the source of attack. Various methods based on this approach for botnet detection are in literature, but a generalized method is lacking. So, there is a requirement to design a generic framework that can be used by any botnet detection. This framework is of use for researchers, in the development of their own method of botnet detection, by means of providing methodology and guidelines. In this paper, various prevalent methods of botnet detection are studied, commonalities among them are established and then a generalized model for the detection of botnet is proposed. The proposed framework is described as UML diagrams.
On the Delay Scaling Laws of Cache Networks
Venue: arXiv cs.NI 2013
Year: 2013

The Internet is becoming more and more content-oriented, where one of main components in content-oriented Internet architectures is network caching. Despite a surge of extensive use of network cashing in the current and future Internet architectures, analysis on the performance of general cache networks are still quite limited due to complex inter-plays among various components and thus analytical intractability. We study asymptotic delay performance of cache networks, in particular, focusing on the impact of heterogeneous content popularities and nodes' geometric `importances' in caching policies. Our theoretical findings provide useful engineering implications such as when and how various factors have impact on caching performance, and we provide extensive simulation results on the real Internet topology.
Real-time Optimization and Adaptation of the Crosswind Flight of Tethered Wings for Airborne Wind Energy
Venue: arXiv cs.SY 2013
Year: 2013

Airborne wind energy systems aim to generate renewable energy by means of the aerodynamic lift produced by a wing tethered to the ground and controlled to fly crosswind paths. The problem of maximizing the average power developed by the generator, in presence of limited information on wind speed and direction, is considered. At constant tether speed operation, the power is related to the traction force generated by the wing. First, a study of the traction force is presented for a general path parametrization. In particular, the sensitivity of the traction force on the path parameters is analyzed. Then, the results of this analysis are exploited to design an algorithm to maximize the force, hence the power, in real-time. The algorithm uses only the measured traction force on the tether and it is able to adapt the system's operation to maximize the average force with uncertain and time-varying wind. The influence of inaccurate sensor readings and turbulent wind are also discussed. The presented algorithm is not dependent on a specific hardware setup and can act as an extension of existing control structures. Both numerical simulations and experimental results are presented to highlight the effectiveness of the approach.
Secrecy Rate Study in Two-Hop Relay Channel with Finite Constellations
Venue: arXiv cs.IT 2013
Year: 2013

Two-hop security communication with an eavesdropper in wireless environment is a hot research direction. The basic idea is that the destination, simultaneously with the source, sends a jamming signal to interfere the eavesdropper near to or co-located with the relay. Similar as physical layer network coding, the friendly jamming signal will prevent the eavesdropper from detecting the useful information originated from the source and will not affect the destination on detecting the source information with the presence of the known jamming signal. However, existing investigations are confined to Gaussian distributed signals, which are seldom used in real systems. When finite constellation signals are applied, the behavior of the secrecy rate becomes very different. For example, the secrecy rate depends on phase difference between the input signals with finite constellations, which is not observed with Gaussian signals. In this paper, we investigate the secrecy capacity and derive its upper bound for the two-hop relay model, by assuming an eavesdropper near the relay and the widely used M-PSK modulation. With our upper bound, the best and worst phase differences in high SNR region are then given. Numerical studies verify our analysis and show that the derived upper bound is relatively tight.
DVB-S2 Spectrum Efficiency Improvement with Hierarchical Modulation
Venue: arXiv cs.NI 2013
Year: 2013

We study the design of a DVB-S2 system in order to maximise spectrum efficiency. This task is usually challenging due to channel variability. Modern satellite communications systems such as DVB-SH and DVB-S2 rely mainly on a time sharing strategy to optimise the spectrum efficiency. Recently, we showed that combining time sharing with hierarchical modulation can provide significant gains (in terms of spectrum efficiency) compared to the best time sharing strategy. However, our previous design does not improve the DVB-S2 performance when all the receivers experience low or large signal-to-noise ratios. In this article, we introduce and study a hierarchical QPSK and a hierarchical 32-APSK to overcome the previous limitations.We show in a realistic case based on DVB-S2 that the hierarchical QPSK provides an improvement when the receivers experience poor channel condition, while the 32-APSK increases the spectrum efficiency when the receivers experience good channel condition.
Stemmers for Tamil Language: Performance Analysis
Venue: arXiv cs.CL 2013
Year: 2013

Stemming is the process of extracting root word from the given inflection word and also plays significant role in numerous application of Natural Language Processing (NLP). Tamil Language raises several challenges to NLP, since it has rich morphological patterns than other languages. The rule based approach light-stemmer is proposed in this paper, to find stem word for given inflection Tamil word. The performance of proposed approach is compared to a rule based suffix removal stemmer based on correctly and incorrectly predicted. The experimental result clearly show that the proposed approach light stemmer for Tamil language perform better than suffix removal stemmer and also more effective in Information Retrieval System (IRS).
Link Performance Abstraction for Interference-Aware Communications (IAC)
Venue: arXiv cs.IT 2013
Year: 2013

Advanced co-channel interference aware signal detection has drawn research attention during the recent development of Long Term Evolution-Advanced (LTE-A) systems and the interference-aware communications (IAC) is currently being studied by 3GPP. This paper investigates link performance abstraction for the IAC systems employing maximum-likelihood detector (MLD). The link performance of MLD can be estimated by combining two performance bounds, namely, linear receiver and genie-aided maximum-likelihood (ML) receiver. It is shown that the conventional static approach based on static parameterization, while working well under moderate and weak interference conditions, fails to generate a well-behaved solution in the strong interference case. Inspired by this observation, we propose a new adaptive approach where the combining parameter is adaptively adjusted according to instantaneous interference-to-signal ratio (ISR). The basic idea is to exploit the probabilistic behavior of the optimal combining ratio over the ISR. The link-level simulation results are provided to verify the prediction accuracy of the proposed link abstraction method. Moreover, we use the proposed link abstraction model as a link-to-system interface mapping in system-level simulations to demonstrate the performance of the IAC receiver in interference-limited LTE systems
Scalable Protein Sequence Similarity Search using Locality-Sensitive Hashing and MapReduce
Venue: arXiv cs.DC 2013
Year: 2013

Metagenomics is the study of environments through genetic sampling of their microbiota. Metagenomic studies produce large datasets that are estimated to grow at a faster rate than the available computational capacity. A key step in the study of metagenome data is sequence similarity searching which is computationally intensive over large datasets. Tools such as BLAST require large dedicated computing infrastructure to perform such analysis and may not be available to every researcher. In this paper, we propose a novel approach called ScalLoPS that performs searching on protein sequence datasets using LSH (Locality-Sensitive Hashing) that is implemented using the MapReduce distributed framework. ScalLoPS is designed to scale across computing resources sourced from cloud computing providers. We present the design and implementation of ScalLoPS followed by evaluation with datasets derived from both traditional as well as metagenomic studies. Our experiments show that with this method approximates the quality of BLAST results while improving the scalability of protein sequence search.
Differential Data Analysis for Recommender Systems
Venue: arXiv cs.IR 2013
Year: 2013

We present techniques to characterize which data is important to a recommender system and which is not. Important data is data that contributes most to the accuracy of the recommendation algorithm, while less important data contributes less to the accuracy or even decreases it. Characterizing the importance of data has two potential direct benefits: (1) increased privacy and (2) reduced data management costs, including storage. For privacy, we enable increased recommendation accuracy for comparable privacy levels using existing data obfuscation techniques. For storage, our results indicate that we can achieve large reductions in recommendation data and yet maintain recommendation accuracy. Our main technique is called differential data analysis. The name is inspired by other sorts of differential analysis, such as differential power analysis and differential cryptanalysis, where insight comes through analysis of slightly differing inputs. In differential data analysis we chunk the data and compare results in the presence or absence of each chunk. We present results applying differential data analysis to two datasets and three different kinds of attributes. The first attribute is called user hardship. This is a novel attribute, particularly relevant to location datasets, that indicates how burdensome a data point was to achieve. The second and third attributes are more standard: timestamp and user rating. For user rating, we confirm previous work concerning the increased importance to the recommender of data corresponding to high and low user ratings.
The failure tolerance of mechatronic software systems to random and targeted attacks
Venue: arXiv cs.DC 2013
Year: 2013

This paper describes a complex networks approach to study the failure tolerance of mechatronic software systems under various types of hardware and/or software failures. We produce synthetic system architectures based on evidence of modular and hierarchical modular product architectures and known motifs for the interconnection of physical components to software. The system architectures are then subject to various forms of attack. The attacks simulate failure of critical hardware or software. Four types of attack are investigated: degree centrality, betweenness centrality, closeness centrality and random attack. Failure tolerance of the system is measured by a 'robustness coefficient', a topological 'size' metric of the connectedness of the attacked network. We find that the betweenness centrality attack results in the most significant reduction in the robustness coefficient, confirming betweenness centrality, rather than the number of connections (i.e. degree), as the most conservative metric of component importance. A counter-intuitive finding is that "designed" system architectures, including a bus, ring, and star architecture, are not significantly more failure-tolerant than interconnections with no prescribed architecture, that is, a random architecture. Our research provides a data-driven approach to engineer the architecture of mechatronic software systems for failure tolerance.
Identifying Correlated Heavy-Hitters in a Two-Dimensional Data Stream
Venue: arXiv cs.DB 2013
Year: 2013

We consider online mining of correlated heavy-hitters from a data stream. Given a stream of two-dimensional data, a correlated aggregate query first extracts a substream by applying a predicate along a primary dimension, and then computes an aggregate along a secondary dimension. Prior work on identifying heavy-hitters in streams has almost exclusively focused on identifying heavy-hitters on a single dimensional stream, and these yield little insight into the properties of heavy-hitters along other dimensions. In typical applications however, an analyst is interested not only in identifying heavy-hitters, but also in understanding further properties such as: what other items appear frequently along with a heavy-hitter, or what is the frequency distribution of items that appear along with the heavy-hitters. We consider queries of the following form: In a stream S of (x, y) tuples, on the substream H of all x values that are heavy-hitters, maintain those y values that occur frequently with the x values in H. We call this problem as Correlated Heavy-Hitters (CHH). We formulate an approximate formulation of CHH identification, and present an algorithm for tracking CHHs on a data stream. The algorithm is easy to implement and uses workspace which is orders of magnitude smaller than the stream itself. We present provable guarantees on the maximum error, as well as detailed experimental results that demonstrate the space-accuracy trade-off.
Analysis of Errors: A Support System for Teachers to Analyse the Error Occurring to a Novice Programmer
Venue: arXiv cs.CY 2013
Year: 2013

For a novice programmer, coding is equivalent to a nightmare. A novice programmer tries to replicate steps provided by the faculty and on compilation gets a number of errors which the novice programmer is not able to resolve. This system provides support to the faculty about the coding ability of the students and their ability to solve those errors. Also, the faculty can provide a solution to the errors which are occurring to the students and the solution is displayed accordingly. The emphasis of this paper is on developing this system within JAVA and making use of Online Compilers. Moreover, we focus on a new system which is able to provide online code management and these codes get compiled using an online compiler and these programs can be viewed by the respective faculty for cross verification. This paper takes into account the syntactic errors, runtime and semantic errors.
Second order scattering descriptors predict fMRI activity due to visual textures
Venue: arXiv cs.CV 2013
Year: 2013

Second layer scattering descriptors are known to provide good classification performance on natural quasi-stationary processes such as visual textures due to their sensitivity to higher order moments and continuity with respect to small deformations. In a functional Magnetic Resonance Imaging (fMRI) experiment we present visual textures to subjects and evaluate the predictive power of these descriptors with respect to the predictive power of simple contour energy - the first scattering layer. We are able to conclude not only that invariant second layer scattering coefficients better encode voxel activity, but also that well predicted voxels need not necessarily lie in known retinotopic regions.