OpenRaiser/Intern-Atlas huggingface dataset:
Caracterizando la Web Chilena
Venue: arXiv cs.SI 2013
Year: 2013

This article presents a characterization of the web space from Chile in 2007. The characterization shows distributions of sites and domains, analysis of document content and server configuration. In addition, the network structure of the chilean Web is analyzed, determining components based on hyperlink structure at the document and site levels. Original Abstract: En este artículo se muestra una caracterización del espacio web de Chile para el año 2007. Se muestran distribuciones de sitios y dominios, caracterización del contenido en base a tipos de documento, asi como configuración de los servidores. Se estudia la estructura de la red creada mediante hipervínculos en los documentos y cómo las diferentes componentes de esta estructura varían cuando los hipervínculos son agregados a nivel de sitios.
Complete Valuations on Finite Distributive Lattices
Venue: arXiv cs.DM 2013
Year: 2013

We characterize the finite distributive lattices which admit a complete valuation, that is bijective over a set of consecutive natural numbers, with the additional conditions of completeness (Definition 2.3). We prove that such lattices are downset lattices of finite posets of dimension at most two, and determine a realizer through a recursive relation between weights on the poset associated to valuation. The relation shows that the weights count chains in the complementary poset. Conversely, we prove that a valuation defined on a poset of dimension at most two, through the weight function which counts chains in the complementary poset, is complete.
Complexity of colouring problems restricted to unichord-free and \{square,unichord\}-free graphs
Venue: arXiv cs.DM 2013
Year: 2013

A \emph{unichord} in a graph is an edge that is the unique chord of a cycle. A \emph{square} is an induced cycle on four vertices. A graph is \emph{unichord-free} if none of its edges is a unichord. We give a slight restatement of a known structure theorem for unichord-free graphs and use it to show that, with the only exception of the complete graph $K_4$, every square-free, unichord-free graph of maximum degree~3 can be total-coloured with four colours. Our proof can be turned into a polynomial time algorithm that actually outputs the colouring. This settles the class of square-free, unichord-free graphs as a class for which edge-colouring is NP-complete but total-colouring is polynomial.
Enhancements of Multi-class Support Vector Machine Construction from Binary Learners using Generalization Performance
Venue: arXiv cs.LG 2013
Year: 2013

We propose several novel methods for enhancing the multi-class SVMs by applying the generalization performance of binary classifiers as the core idea. This concept will be applied on the existing algorithms, i.e., the Decision Directed Acyclic Graph (DDAG), the Adaptive Directed Acyclic Graphs (ADAG), and Max Wins. Although in the previous approaches there have been many attempts to use some information such as the margin size and the number of support vectors as performance estimators for binary SVMs, they may not accurately reflect the actual performance of the binary SVMs. We show that the generalization ability evaluated via a cross-validation mechanism is more suitable to directly extract the actual performance of binary SVMs. Our methods are built around this performance measure, and each of them is crafted to overcome the weakness of the previous algorithm. The proposed methods include the Reordering Adaptive Directed Acyclic Graph (RADAG), Strong Elimination of the classifiers (SE), Weak Elimination of the classifiers (WE), and Voting based Candidate Filtering (VCF). Experimental results demonstrate that our methods give significantly higher accuracy than all of the traditional ones. Especially, WE provides significantly superior results compared to Max Wins which is recognized as the state of the art algorithm in terms of both accuracy and classification speed with two times faster in average.
Mining for Spatially-Near Communities in Geo-Located Social Networks
Venue: arXiv cs.SI 2013
Year: 2013

Current approaches to community detection in social networks often ignore the spatial location of the nodes. In this paper, we look to extract spatially-near communities in a social network. We introduce a new metric to measure the quality of a community partition in a geolocated social networks called "spatially-near modularity" a value that increases based on aspects of the network structure but decreases based on the distance between nodes in the communities. We then look to find an optimal partition with respect to this measure - which should be an "ideal" community with respect to both social ties and geographic location. Though an NP-hard problem, we introduce two heuristic algorithms that attempt to maximize this measure and outperform non-geographic community finding by an order of magnitude. Applications to counter-terrorism are also discussed.
A System-Theoretic Clean Slate Approach to Provably Secure Ad Hoc Wireless Networking
Venue: arXiv cs.NI 2013
Year: 2013

Traditionally, wireless network protocols have been designed for performance. Subsequently, as attacks have been identified, patches have been developed. This has resulted in an "arms race" development process of discovering vulnerabilities and then patching them. The fundamental difficulty with this approach is that other vulnerabilities may still exist. No provable security or performance guarantees can ever be provided. We develop a system-theoretic approach to security that provides a complete protocol suite with provable guarantees, as well as proof of min-max optimality with respect to any given utility function of source-destination rates. Our approach is based on a model capturing the essential features of an adhoc wireless network that has been infiltrated with hostile nodes. We consider any collection of nodes, some good and some bad, possessing specified capabilities vis-a-vis cryptography, wireless communication and clocks. The good nodes do not know the bad nodes. The bad nodes can collaborate perfectly, and are capable of any disruptive acts ranging from simply jamming to non-cooperation with the protocols in any manner they please. The protocol suite caters to the complete life-cycle, all the way from birth of nodes, through all phases of ad hoc network formation, leading to an optimized network carrying data reliably. It provably achieves the min-max of the utility function, where the max is over all protocol suites published and followed by the good nodes, while the min is over all Byzantine behaviors of the bad nodes. Under the protocol suite, the bad nodes do not benefit from any actions other than jamming or cooperating. This approach supersedes much previous work that deals with several types of attacks.
Fitness Probability Distribution of Bit-Flip Mutation
Venue: arXiv cs.DM 2013
Year: 2013

Bit-flip mutation is a common mutation operator for evolutionary algorithms applied to optimize functions over binary strings. In this paper, we develop results from the theory of landscapes and Krawtchouk polynomials to exactly compute the probability distribution of fitness values of a binary string undergoing uniform bit-flip mutation. We prove that this probability distribution can be expressed as a polynomial in p, the probability of flipping each bit. We analyze these polynomials and provide closed-form expressions for an easy linear problem (Onemax), and an NP-hard problem, MAX-SAT. We also discuss some implications of the results for runtime analysis.
Preliminary Notes on Termination and Non-Termination Reasoning
Venue: arXiv cs.PL 2013
Year: 2013

In this preliminary note, we will illustrate our ideas on automated mechanisms for termination and non-termination reasoning.
Improved LT Codes in Low Overhead Regions for Binary Erasure Channels
Venue: arXiv cs.IT 2013
Year: 2013

We study improved degree distribution for Luby Transform (LT) codes which exhibits improved bit error rate performance particularly in low overhead regions. We construct the degree distribution by modifying Robust Soliton distribution. The performance of our proposed LT codes is evaluated and compared to the conventional LT codes via And-Or tree analysis. Then we propose a transmission scheme based on the proposed degree distribution to improve its frame error rate in full recovery regions. Furthermore, the improved degree distribution is applied to distributed multi-source relay networks and unequal error protection. It is shown that our schemes achieve better performance and reduced complexity especially in low overhead regions, compared with conventional schemes.
Inducing Honest Reporting Without Observing Outcomes: An Application to the Peer-Review Process
Venue: arXiv cs.MA 2013
Year: 2013

When eliciting opinions from a group of experts, traditional devices used to promote honest reporting assume that there is an observable future outcome. In practice, however, this assumption is not always reasonable. In this paper, we propose a scoring method built on strictly proper scoring rules to induce honest reporting without assuming observable outcomes. Our method provides scores based on pairwise comparisons between the reports made by each pair of experts in the group. For ease of exposition, we introduce our scoring method by illustrating its application to the peer-review process. In order to do so, we start by modeling the peer-review process using a Bayesian model where the uncertainty regarding the quality of the manuscript is taken into account. Thereafter, we introduce our scoring method to evaluate the reported reviews. Under the assumptions that reviewers are Bayesian decision-makers and that they cannot influence the reviews of other reviewers, we show that risk-neutral reviewers strictly maximize their expected scores by honestly disclosing their reviews. We also show how the group's scores can be used to find a consensual review. Experimental results show that encouraging honest reporting through the proposed scoring method creates more accurate reviews than the traditional peer-review process.
Blazes: Coordination Analysis for Distributed Programs
Venue: arXiv cs.DC 2013
Year: 2013

Distributed consistency is perhaps the most discussed topic in distributed systems today. Coordination protocols can ensure consistency, but in practice they cause undesirable performance unless used judiciously. Scalable distributed architectures avoid coordination whenever possible, but under-coordinated systems can exhibit behavioral anomalies under fault, which are often extremely difficult to debug. This raises significant challenges for distributed system architects and developers. In this paper we present Blazes, a cross-platform program analysis framework that (a) identifies program locations that require coordination to ensure consistent executions, and (b) automatically synthesizes application-specific coordination code that can significantly outperform general-purpose techniques. We present two case studies, one using annotated programs in the Twitter Storm system, and another using the Bloom declarative language.
A Novel Approach in detecting pose orientation of a 3D face required for face
Venue: arXiv cs.CV 2013
Year: 2013

In this paper we present a novel approach that takes as input a 3D image and gives as output its pose i.e. it tells whether the face is oriented with respect the X, Y or Z axes with angles of rotation up to 40 degree. All the experiments have been performed on the FRAV3D Database. After applying the proposed algorithm to the 3D facial surface we have obtained i.e. on 848 3D face images our method detected the pose correctly for 566 face images,thus giving an approximately 67 % of correct pose detection.
Coverage Probability Analysis for Wireless Networks Using Repulsive Point Processes
Venue: arXiv cs.NI 2013
Year: 2013

The recent witnessed evolution of cellular networks from a carefully planned deployment to more irregular, heterogeneous deployments of Macro, Pico and Femto-BSs motivates new analysis and design approaches. In this paper, we analyze the coverage probability in cellular networks assuming repulsive point processes for the base station deployment. In particular, we characterize, analytically using stochastic geometry, the downlink probability of coverage under a Matern hardcore point process to ensure minimum distance between the randomly located base stations. Assuming a mobile user connects to the nearest base station and Rayleigh fading, we derive two lower bounds expressions on the downlink probability of coverage that is within 4% from the simulated scenario. To validate our model, we compare the probability of coverage of the Matern hardcore topology against an actual base station deployment obtained from a public database. The comparison shows that the actual base station deployment can be fitted by setting the appropriate Matern point process density.
(Failure of the) Wisdom of the crowds in an endogenous opinion dynamics model with multiply biased agents
Venue: arXiv cs.SI 2013
Year: 2013

We study an endogenous opinion (or, belief) dynamics model where we endogenize the social network that models the link (`trust') weights between agents. Our network adjustment mechanism is simple: an agent increases her weight for another agent if that agent has been close to truth (whence, our adjustment criterion is `past performance'). Moreover, we consider multiply biased agents that do not learn in a fully rational manner but are subject to persuasion bias - they learn in a DeGroot manner, via a simple `rule of thumb' - and that have biased initial beliefs. In addition, we also study this setup under conformity, opposition, and homophily - which are recently suggested variants of DeGroot learning in social networks - thereby taking into account further biases agents are susceptible to. Our main focus is on crowd wisdom, that is, on the question whether the so biased agents can adequately aggregate dispersed information and, consequently, learn the true states of the topics they communicate about. In particular, we present several conditions under which wisdom fails.
Power Allocation for Distributed BLUE Estimation with Full and Limited Feedback of CSI
Venue: arXiv cs.IT 2013
Year: 2013

This paper investigates the problem of adaptive power allocation for distributed best linear unbiased estimation (BLUE) of a random parameter at the fusion center (FC) of a wireless sensor network (WSN). An optimal power-allocation scheme is proposed that minimizes the $L^2$-norm of the vector of local transmit powers, given a maximum variance for the BLUE estimator. This scheme results in the increased lifetime of the WSN compared to similar approaches that are based on the minimization of the sum of the local transmit powers. The limitation of the proposed optimal power-allocation scheme is that it requires the feedback of the instantaneous channel state information (CSI) from the FC to local sensors, which is not practical in most applications of large-scale WSNs. In this paper, a limited-feedback strategy is proposed that eliminates this requirement by designing an optimal codebook for the FC using the generalized Lloyd algorithm with modified distortion metrics. Each sensor amplifies its analog noisy observation using a quantized version of its optimal amplification gain, which is received by the FC and used to estimate the unknown parameter.
Optimizing Maximum Flow Time and Maximum Throughput in Broadcast Scheduling
Venue: arXiv cs.DS 2013
Year: 2013

We consider the pull-based broadcast scheduling model. In this model, there are n unit-sized pages of information available at the server. Requests arrive over time at the server asking for a specific page. When the server transmits a page, all outstanding requests for the page are simultaneously satisfied, and this is what distinguishes broadcast scheduling from the standard scheduling setting where each job must be processed separately by the server. Broadcast scheduling has received a considerable amount of attention due to the algorithmic challenges that it gives in addition to its applications in multicast systems and wireless and LAN networks. In this paper, we give the following new approximation results for two popular objectives: - For the objective of minimizing the maximum flow time, we give the first PTAS. Previously, it was known that the algorithm First-In-First-Out (FIFO) is a 2-approximation, and it is tight. It has been suggested as an open problem to obtain a better approximation. - For the objective of maximizing the throughput, we give a 0.7759-approximation which improves upon the previous best known 0.75-approximation. Our improved results are enabled by our novel rounding schemes and linear programming which can effectively reduce congestion in schedule which is often the main bottleneck in designing scheduling algorithms based on linear programming. We believe that our algorithmic ideas and techniques could be of potential use for other scheduling problems.
The Incidence and Cross Methods for Efficient Radar Detection
Venue: arXiv cs.IT 2013
Year: 2013

The designation of the radar system is to detect the position and velocity of targets around us. The radar transmits a waveform, which is reflected back from the targets, and echo waveform is received. In a commonly used model, the echo is a sum of a superposition of several delay-Doppler shifts of the transmitted waveform, and a noise component. The delay and Doppler parameters encode, respectively, the distances, and relative velocities, between the targets and the radar. Using standard digital-to-analog and sampling techniques, the estimation task of the delay-Doppler parameters, which involves waveforms, is reduced to a problem for complex sequences of finite length N. In these notes we introduce the Incidence and Cross methods for radar detection. One of their advantages, is robustness to inhomogeneous radar scene, i.e., for sensing small targets in the vicinity of large objects. The arithmetic complexity of the incidence and cross methods is O(NlogN + r^3) and O(NlogN + r^2), for r targets, respectively. In the case of noisy environment, these are the fastest radar detection techniques. Both methods employ chirp sequences, which are commonly used by radar systems, and hence are attractive for real world applications.
Discovery of Approximate Differential Dependencies
Venue: arXiv cs.DB 2013
Year: 2013

Differential dependencies (DDs) capture the relationships between data columns of relations. They are more general than functional dependencies (FDs) and and the difference is that DDs are defined on the distances between values of two tuples, not directly on the values. Because of this difference, the algorithms for discovering FDs from data find only special DDs, not all DDs and therefore are not applicable to DD discovery. In this paper, we propose an algorithm to discover DDs from data following the way of fixing the left hand side of a candidate DD to determine the right hand side. We also show some properties of DDs and conduct a comprehensive analysis on how sampling affects the DDs discovered from data.
Novel Repair-by-Transfer Codes and Systematic Exact-MBR Codes with Lower Complexities and Smaller Field Sizes
Venue: arXiv cs.IT 2013
Year: 2013

The $(n,k,d)$ regenerating code is a class of $(n,k)$ erasure codes with the capability to recover a lost code fragment from other $d$ existing code fragments. This paper concentrates on the design of exact regenerating codes at Minimum Bandwidth Regenerating (MBR) points. For $d=n-1$, a class of $(n,k,d=n-1)$ Exact-MBR codes, termed as repair-by-transfer codes, have been developed in prior work to avoid arithmetic operations in node repairing process. The first result of this paper presents a new class of repair-by-transfer codes via congruent transformations. As compared with the prior works, the advantages of the proposed codes include: i) The minimum of the finite field size is significantly reduced from $n \choose 2$ to $n$. ii) The encoding complexity is decreased from $n^4$ to $n^3$. As shown in simulations, the proposed repair-by-transfer codes have lower computational overhead when $n$ is greater than a specific constant. The second result of this paper presents a new form of coding matrix for product-matrix Exact-MBR codes. The proposed coding matrix includes a number of advantages: i). The minimum of the finite field size is reduced from $n-k+d$ to $n$. ii). The fast Reed-Solomon erasure coding algorithms can be applied on the Exact-MBR codes to reduce the time complexities.
Energy Saving Techniques for Phase Change Memory (PCM)
Venue: arXiv cs.AR 2013
Year: 2013

In recent years, the energy consumption of computing systems has increased and a large fraction of this energy is consumed in main memory. Towards this, researchers have proposed use of non-volatile memory, such as phase change memory (PCM), which has low read latency and power; and nearly zero leakage power. However, the write latency and power of PCM are very high and this, along with limited write endurance of PCM present significant challenges in enabling wide-spread adoption of PCM. To address this, several architecture-level techniques have been proposed. In this report, we review several techniques to manage power consumption of PCM. We also classify these techniques based on their characteristics to provide insights into them. The aim of this work is encourage researchers to propose even better techniques for improving energy efficiency of PCM based main memory.
Visual-Semantic Scene Understanding by Sharing Labels in a Context Network
Venue: arXiv cs.CV 2013
Year: 2013

We consider the problem of naming objects in complex, natural scenes containing widely varying object appearance and subtly different names. Informed by cognitive research, we propose an approach based on sharing context based object hypotheses between visual and lexical spaces. To this end, we present the Visual Semantic Integration Model (VSIM) that represents object labels as entities shared between semantic and visual contexts and infers a new image by updating labels through context switching. At the core of VSIM is a semantic Pachinko Allocation Model and a visual nearest neighbor Latent Dirichlet Allocation Model. For inference, we derive an iterative Data Augmentation algorithm that pools the label probabilities and maximizes the joint label posterior of an image. Our model surpasses the performance of state-of-art methods in several visual tasks on the challenging SUN09 dataset.
Geodesic-Preserving Polygon Simplification
Venue: arXiv cs.CG 2013
Year: 2013

Polygons are a paramount data structure in computational geometry. While the complexity of many algorithms on simple polygons or polygons with holes depends on the size of the input polygon, the intrinsic complexity of the problems these algorithms solve is often related to the reflex vertices of the polygon. In this paper, we give an easy-to-describe linear-time method to replace an input polygon $\mathcal{P}$ by a polygon $\mathcal{P}'$ such that (1) $\mathcal{P}'$ contains $\mathcal{P}$, (2) $\mathcal{P}'$ has its reflex vertices at the same positions as $\mathcal{P}$, and (3) the number of vertices of $\mathcal{P}'$ is linear in the number of reflex vertices. Since the solutions of numerous problems on polygons (including shortest paths, geodesic hulls, separating point sets, and Voronoi diagrams) are equivalent for both $\mathcal{P}$ and $\mathcal{P}'$, our algorithm can be used as a preprocessing step for several algorithms and makes their running time dependent on the number of reflex vertices rather than on the size of $\mathcal{P}$.