OpenRaiser/Intern-Atlas huggingface dataset:
Mejora de la exploracion y la explotacion de las heuristicas constructivas para el MLSTP
Venue: arXiv cs.DM 2014
Year: 2014

This paper studies constructive heuristics for the minimum labelling spanning tree (MLST) problem. The purpose is to find a spanning tree that uses edges that are as similar as possible. Given an undirected labeled connected graph (i.e., with a label or color for each edge), the minimum labeling spanning tree problem seeks a spanning tree whose edges have the smallest possible number of distinct labels. The model can represent many real-world problems in telecommunication networks, electric networks, and multimodal transportation networks, among others, and the problem has been shown to be NP-complete even for complete graphs. A primary heuristic, named the maximum vertex covering algorithm has been proposed. Several versions of this constructive heuristic have been proposed to improve its efficiency. Here we describe the problem, review the literature and compare some variants of this algorithm.
Learning Alternative Name Spellings
Venue: arXiv cs.IR 2014
Year: 2014

Name matching is a key component of systems for entity resolution or record linkage. Alternative spellings of the same names are a com- mon occurrence in many applications. We use the largest collection of genealogy person records in the world together with user search query logs to build name matching models. The procedure for building a crowd-sourced training set is outlined together with the presentation of our method. We cast the problem of learning alternative spellings as a machine translation problem at the character level. We use in- formation retrieval evaluation methodology to show that this method substantially outperforms on our data a number of standard well known phonetic and string similarity methods in terms of precision and re- call. Additionally, we rigorously compare the performance of standard methods when compared with each other. Our result can lead to a significant practical impact in entity resolution applications.
Empirical Bayes and Full Bayes for Signal Estimation
Venue: arXiv cs.IT 2014
Year: 2014

We consider signals that follow a parametric distribution where the parameter values are unknown. To estimate such signals from noisy measurements in scalar channels, we study the empirical performance of an empirical Bayes (EB) approach and a full Bayes (FB) approach. We then apply EB and FB to solve compressed sensing (CS) signal estimation problems by successively denoising a scalar Gaussian channel within an approximate message passing (AMP) framework. Our numerical results show that FB achieves better performance than EB in scalar channel denoising problems when the signal dimension is small. In the CS setting, the signal dimension must be large enough for AMP to work well; for large signal dimensions, AMP has similar performance with FB and EB.
Evaluating the retrieval effectiveness of Web search engines using a representative query sample
Venue: arXiv cs.IR 2014
Year: 2014

Search engine retrieval effectiveness studies are usually small-scale, using only limited query samples. Furthermore, queries are selected by the researchers. We address these issues by taking a random representative sample of 1,000 informational and 1,000 navigational queries from a major German search engine and comparing Google's and Bing's results based on this sample. Jurors were found through crowdsourcing, data was collected using specialised software, the Relevance Assessment Tool (RAT). We found that while Google outperforms Bing in both query types, the difference in the performance for informational queries was rather low. However, for navigational queries, Google found the correct answer in 95.3 per cent of cases whereas Bing only found the correct answer 76.6 per cent of the time. We conclude that search engine performance on navigational queries is of great importance, as users in this case can clearly identify queries that have returned correct results. So, performance on this query type may contribute to explaining user satisfaction with search engines.
Why we need an independent index of the Web
Venue: arXiv cs.IR 2014
Year: 2014

The path to greater diversity, as we have seen, cannot be achieved by merely hoping for a new search engine nor will government support for a single alternative achieve this goal. What is instead required is to create the conditions that will make establishing such a search engine possible in the first place. I describe how building and maintaining a proprietary index is the greatest deterrent to such an undertaking. We must first overcome this obstacle. Doing so will still not solve the problem of the lack of diversity in the search engine marketplace. But it may establish the conditions necessary to achieve that desired end.
Going Towards Discretized Spectrum Space: Quantification of Spectrum Consumption Spaces and a Quantified Spectrum Access Paradigm
Venue: arXiv cs.NI 2014
Year: 2014

Dynamic spectrum sharing approach is a paradigm shift from the conventional static and exclusive approach to spectrum allocation. The existing methodologies to define use of the spectrum and quantify its efficiency are based on the static spectrum assignment paradigm and not suitable for the dynamic spectrum sharing paradigm. There is a need to separately quantify the spectrum consumed by the individual transmitters and receivers when multiple heterogeneous wireless networks are sharing the spectrum in time, space, and frequency dimensions. By discretizing the spectrum dimensions, we define a methodology for quantifying the spectrum consumption spaces. This is an attempt to adopt the discretized signal processing principle and apply it to spectrum management functions that would bring in simplicity, flexibility, and precision among other advantages.
Hellinger Distance Trees for Imbalanced Streams
Venue: arXiv cs.LG 2014
Year: 2014

Classifiers trained on data sets possessing an imbalanced class distribution are known to exhibit poor generalisation performance. This is known as the imbalanced learning problem. The problem becomes particularly acute when we consider incremental classifiers operating on imbalanced data streams, especially when the learning objective is rare class identification. As accuracy may provide a misleading impression of performance on imbalanced data, existing stream classifiers based on accuracy can suffer poor minority class performance on imbalanced streams, with the result being low minority class recall rates. In this paper we address this deficiency by proposing the use of the Hellinger distance measure, as a very fast decision tree split criterion. We demonstrate that by using Hellinger a statistically significant improvement in recall rates on imbalanced data streams can be achieved, with an acceptable increase in the false positive rate.
Image Segmentation Using Frequency Locking of Coupled Oscillators
Venue: arXiv cs.CV 2014
Year: 2014

Synchronization of coupled oscillators is observed at multiple levels of neural systems, and has been shown to play an important function in visual perception. We propose a computing system based on locally coupled oscillator networks for image segmentation. The system can serve as the preprocessing front-end of an image processing pipeline where the common frequencies of clusters of oscillators reflect the segmentation results. To demonstrate the feasibility of our design, the system is simulated and tested on a human face image dataset and its performance is compared with traditional intensity threshold based algorithms. Our system shows both better performance and higher noise tolerance than traditional methods.
Mechanism Design for Crowdsourcing: An Optimal 1-1/e Competitive Budget-Feasible Mechanism for Large Markets
Venue: arXiv cs.GT 2014
Year: 2014

In this paper we consider a mechanism design problem in the context of large-scale crowdsourcing markets such as Amazon's Mechanical Turk, ClickWorker, CrowdFlower. In these markets, there is a requester who wants to hire workers to accomplish some tasks. Each worker is assumed to give some utility to the requester. Moreover each worker has a minimum cost that he wants to get paid for getting hired. This minimum cost is assumed to be private information of the workers. The question then is - if the requester has a limited budget, how to design a direct revelation mechanism that picks the right set of workers to hire in order to maximize the requester's utility. We note that although the previous work has studied this problem, a crucial difference in which we deviate from earlier work is the notion of large-scale markets that we introduce in our model. Without the large market assumption, it is known that no mechanism can achieve an approximation factor better than 0.414 and 0.5 for deterministic and randomized mechanisms respectively (while the best known deterministic and randomized mechanisms achieve an approximation ratio of 0.292 and 0.33 respectively). In this paper, we design a budget-feasible mechanism for large markets that achieves an approximation factor of 1-1/e (i.e. almost 0.63). Our mechanism can be seen as a generalization of an alternate way to look at the proportional share mechanism which is used in all the previous works so far on this problem. Interestingly, we also show that our mechanism is optimal by showing that no truthful mechanism can achieve a factor better than 1-1/e; thus, fully resolving this setting. Finally we consider the more general case of submodular utility functions and give new and improved mechanisms for the case when the markets are large.
Quasi-linear Network Coding
Venue: arXiv cs.IT 2014
Year: 2014

We present a heuristic for designing vector non-linear network codes for non-multicast networks, which we call quasi-linear network codes. The method presented has two phases: finding an approximate linear network code over the reals, and then quantizing it to a vector non-linear network code using a fixed-point representation. Apart from describing the method, we draw some links between some network parameters and the rate of the resulting code.
Estimation of Overspread Scattering Functions
Venue: arXiv cs.IT 2014
Year: 2014

In many radar scenarios, the radar target or the medium is assumed to possess randomly varying parts. The properties of a target are described by a random process known as the spreading function. Its second order statistics under the WSSUS assumption are given by the scattering function. Recent developments in operator sampling theory suggest novel channel sounding procedures that allow for the determination of the spreading function given complete statistical knowledge of the operator echo from a single sounding by a weighted pulse train. We construct and analyze a novel estimator for the scattering function based on these findings. Our results apply whenever the scattering function is supported on a compact subset of the time-frequency plane. We do not make any restrictions either on the geometry of this support set, or on its area. Our estimator can be seen as a generalization of an averaged periodogram estimator for the case of a non-rectangular geometry of the support set of the scattering function.
The Zen of Graduate-level Programming
Venue: arXiv cs.CY 2014
Year: 2014

The ubiquity of technology in our daily lives and the economic stability of the technology sector in recent years, especially in areas with a computer science footing, has led to an increase in computer science enrollment in many parts of the world. To keep up with this trend, the undergraduate computer science curriculum has undergone many revisions, analysis, and discussion. Unfortunately, the graduate level curriculum is lagging far behind in computer science education literature and research. To remedy this, we present the blueprint and execution of a graduate level course in programming, designed specifically to cater to the needs of graduate students with a diverse background both in CS and other fields. To this end, the course is divided into two halves. In the first half, students are introduced to different programming concepts, such as multi-paradigm programming, data structures, concurrency, and security to bring them up to speed and provide a level playing field. In the second half, all of these concepts are employed as building blocks to solve real-world problems from data mining, natural language processing, computer vision, and other fields. In addition, the paper also discusses in detail the evaluation instruments employed for the course. Moreover, we also share anecdotal information around student feedback, course design, and grading that may be useful for others who wish to replicate our curriculum or sketch a similar course.
A Measure of Arbitrariness in Abductive Explanations
Venue: arXiv cs.LO 2014
Year: 2014

We study the framework of abductive logic programming extended with integrity constraints. For this framework, we introduce a new measure of the simplicity of an explanation based on its degree of \emph{arbitrariness}: the more arbitrary the explanation, the less appealing it is, with explanations having no arbitrariness - they are called constrained - being the preferred ones. In the paper, we study basic properties of constrained explanations. For the case when programs in abductive theories are stratified we establish results providing a detailed picture of the complexity of the problem to decide whether constrained explanations exist. (To appear in Theory and Practice of Logic Programming (TPLP).)
Anomaly-Sensitive Dictionary Learning for Unsupervised Diagnostics of Solid Media
Venue: arXiv cs.CV 2014
Year: 2014

This paper proposes a strategy for the detection and triangulation of structural anomalies in solid media. The method revolves around the construction of sparse representations of the medium's dynamic response, obtained by learning instructive dictionaries which form a suitable basis for the response data. The resulting sparse coding problem is recast as a modified dictionary learning task with additional spatial sparsity constraints enforced on the atoms of the learned dictionaries, which provides them with a prescribed spatial topology that is designed to unveil anomalous regions in the physical domain. The proposed methodology is model agnostic, i.e., it forsakes the need for a physical model and requires virtually no a priori knowledge of the structure's material properties, as all the inferences are exclusively informed by the data through the layers of information that are available in the intrinsic salient structure of the material's dynamic response. This characteristic makes the approach powerful for anomaly identification in systems with unknown or heterogeneous property distribution, for which a model is unsuitable or unreliable. The method is validated using both synthetically
Using Tabled Logic Programming to Solve the Petrobras Planning Problem
Venue: arXiv cs.AI 2014
Year: 2014

Tabling has been used for some time to improve efficiency of Prolog programs by memorizing answered queries. The same idea can be naturally used to memorize visited states during search for planning. In this paper we present a planner developed in the Picat language to solve the Petrobras planning problem. Picat is a novel Prolog-like language that provides pattern matching, deterministic and non-deterministic rules, and tabling as its core modelling and solving features. We demonstrate these capabilities using the Petrobras problem, where the goal is to plan transport of cargo items from ports to platforms using vessels with limited capacity. Monte Carlo Tree Search has been so far the best technique to tackle this problem and we will show that by using tabling we can achieve much better runtime efficiency and better plan quality.
Sentiment Analysis: A Survey
Venue: arXiv cs.IR 2014
Year: 2014

Sentiment analysis (also known as opinion mining) refers to the use of natural language processing, text analysis and computational linguistics to identify and extract subjective information in source materials. Mining opinions expressed in the user generated content is a challenging yet practically very useful problem. This survey would cover various approaches and methodology used in Sentiment Analysis and Opinion Mining in general. The focus would be on Internet text like, Product review, tweets and other social media.
Efficient Computation of the Well-Founded Semantics over Big Data
Venue: arXiv cs.AI 2014
Year: 2014

Data originating from the Web, sensor readings and social media result in increasingly huge datasets. The so called Big Data comes with new scientific and technological challenges while creating new opportunities, hence the increasing interest in academia and industry. Traditionally, logic programming has focused on complex knowledge structures/programs, so the question arises whether and how it can work in the face of Big Data. In this paper, we examine how the well-founded semantics can process huge amounts of data through mass parallelization. More specifically, we propose and evaluate a parallel approach using the MapReduce framework. Our experimental results indicate that our approach is scalable and that well-founded semantics can be applied to billions of facts. To the best of our knowledge, this is the first work that addresses large scale nonmonotonic reasoning without the restriction of stratification for predicates of arbitrary arity. To appear in Theory and Practice of Logic Programming (TPLP).
Self-dual cyclic codes over finite chain rings
Venue: arXiv cs.IT 2014
Year: 2014

Let $R$ be a finite commutative chain ring with unique maximal ideal $\langle γ\rangle$, and let $n$ be a positive integer coprime with the characteristic of $R/\langle γ\rangle$. In this paper, the algebraic structure of cyclic codes of length $n$ over $R$ is investigated. Some new necessary and sufficient conditions for the existence of nontrivial self-dual cyclic codes are provided. An enumeration formula for the self-dual cyclic codes is also studied.
News-Based Group Modeling and Forecasting
Venue: arXiv cs.SI 2014
Year: 2014

In this paper, we study news group modeling and forecasting methods using quantitative data generated by our large-scale natural language processing (NLP) text analysis system. A news group is a set of news entities, like top U.S. cities, governors, senators, golfers, or movie actors. Our fame distribution analysis of news groups shows that log-normal and power-law distributions generally could describe news groups in many aspects. We use several real news groups including cities, politicians, and CS professors, to evaluate our news group models in terms of time series data distribution analysis, group-fame probability analysis, and fame-changing analysis over long time. We also build a practical news generation model using a HMM (Hidden Markov Model) based approach. Most importantly, our analysis shows the future entity fame distribution has a power-law tail. That is, only a small number of news entities in a group could become famous in the future. Based on these analysis we are able to answer some interesting forecasting problems - for example, what is the future average fame (or maximum fame) of a specific news group? And what is the probability that some news entity become very famous within a certain future time range? We also give concrete examples to illustrate our forecasting approaches.
On Orthogonal Band Allocation for Multi-User Multi-Band Cognitive Radio Networks: Stability Analysis
Venue: arXiv cs.IT 2014
Year: 2014

In this work, we study the problem of band allocation of $M_s$ buffered secondary users (SUs) to $M_p$ primary bands licensed to (owned by) $M_p$ buffered primary users (PUs). The bands are assigned to SUs in an orthogonal (one-to-one) fashion such that neither band sharing nor multi-band allocations are permitted. In order to study the stability region of the secondary network, the optimization problem used to obtain the stability region's envelope (closure) is established and is shown to be a linear program which can be solved efficiently and reliably. We compare our orthogonal allocation system with two typical low-complexity and intuitive band allocation systems. In one system, each cognitive user chooses a band randomly in each time slot with some assignment probability designed such that the system maintained stable, while in the other system fixed (deterministic) band assignment is adopted throughout the lifetime of the network. We derive the stability regions of these two systems. We prove mathematically, as well as through numerical results, the advantages of our proposed orthogonal system over the other two systems.
A Layered Modeling and Simulation Approach to investigate Resource-aware Computing in MPSoCs
Venue: arXiv cs.OH 2014
Year: 2014

Increasing complexity of modern multi-processor system on chip (MPSoC) and the decreasing feature size have introduced new challenges. System designers have to consider now aspects which were not part of the design process in past times. Resource-aware Computing is one of such emerging design concerns which can help to improve performance, dependability and resource utilization of overall system. Resource-aware execution takes into account the resource status when executing tasks on MPSoCs. Exploration of resource-aware computing at early design stages of complex systems is mandatory and appropriate methodologies to do this in an efficient manner are thus required. In this paper, we present a modular approach which provides modeling and simulation support for investigation of resource-aware execution in MPSoCs. The proposed methodology enables rapid exploration of the design space by modeling and simulating the resource-awareness in a separate layer while widely reusing the legacy system model in the other layer. Our experiments illustrate the benefits of our approach for the exploration of resource-aware execution on MPSoCs.
Correlating power consumption and network traffic for improving data centers resiliency
Venue: arXiv cs.NI 2014
Year: 2014

The deployment of business critical applications and information infrastructures are moving to the cloud. This means they are hosted in large scale data centers with other business applications and infrastructures with less (or none) mission critical constraints. This mixed and complex environment makes very challenging the process of monitoring critical applications and handling (detecting and recovering) possible failures of servers' data center that could affect responsiveness and/or reliability of mission critical applications. Monitoring mechanisms used in data center are usually intrusive in the sense that they need to install agents on each single server. This has considerable drawbacks: huge usage of human resources to install and patch the system and interference with the critical application because agents share application resources. In order to detect (and possibly predict) failures in data centers the paper does a first attempt in showing the correlation between network traffic and servers' power consumption. This is an important step in deriving non-intrusive monitoring systems, as both network traffic and power consumption can be captured without installing any software at the servers. This will improve in its turn the overall resiliency of the data center and its self-managing capacity.