OpenRaiser/Intern-Atlas huggingface dataset:
DANCo: Dimensionality from Angle and Norm Concentration
Venue: arXiv cs.LG 2012
Year: 2012

In the last decades the estimation of the intrinsic dimensionality of a dataset has gained considerable importance. Despite the great deal of research work devoted to this task, most of the proposed solutions prove to be unreliable when the intrinsic dimensionality of the input dataset is high and the manifold where the points lie is nonlinearly embedded in a higher dimensional space. In this paper we propose a novel robust intrinsic dimensionality estimator that exploits the twofold complementary information conveyed both by the normalized nearest neighbor distances and by the angles computed on couples of neighboring points, providing also closed-forms for the Kullback-Leibler divergences of the respective distributions. Experiments performed on both synthetic and real datasets highlight the robustness and the effectiveness of the proposed algorithm when compared to state of the art methodologies.
Compiling Finite Domain Constraints to SAT with BEE
Venue: arXiv cs.LO 2012
Year: 2012

We present BEE, a compiler which enables to encode finite domain constraint problems to CNF. Using BEE both eases the encoding process for the user and also performs transformations to simplify constraints and optimize their encoding to CNF. These optimizations are based primarily on equi-propagation and on partial evaluation, and also on the idea that a given constraint may have various possible CNF encodings. Often, the better encoding choice is made after constraint simplification. BEE is written in Prolog and integrates directly with a SAT solver through a suitable Prolog interface. We demonstrate that constraint simplification is often highly beneficial when solving hard finite domain constraint problems. A BEE implementation is available with this paper.
Visualizing Streaming Text Data with Dynamic Maps
Venue: arXiv cs.DM 2012
Year: 2012

The many endless rivers of text now available present a serious challenge in the task of gleaning, analyzing and discovering useful information. In this paper, we describe a methodology for visualizing text streams in real time. The approach automatically groups similar messages into "countries," with keyword summaries, using semantic analysis, graph clustering and map generation techniques. It handles the need for visual stability across time by dynamic graph layout and Procrustes projection techniques, enhanced with a novel stable component packing algorithm. The result provides a continuous, succinct view of evolving topics of interest. It can be used in passive mode for overviews and situational awareness, or as an interactive data exploration tool. To make these ideas concrete, we describe their application to an online service called TwitterScope.
The Stability of Convergence of Curve Evolutions in Vector Fields
Venue: arXiv cs.CV 2012
Year: 2012

Curve evolution is often used to solve computer vision problems. If the curve evolution fails to converge, we would not be able to solve the targeted problem in a lifetime. This paper studies the theoretical aspect of the convergence of a type of general curve evolutions. We establish a theory for analyzing and improving the stability of the convergence of the general curve evolutions. Based on this theory, we ascertain that the convergence of a known curve evolution is marginal stable. We propose a way of modifying the original curve evolution equation to improve the stability of the convergence according to our theory. Numerical experiments show that the modification improves the convergence of the curve evolution, which validates our theory.
Experience on Re-engineering Applying with Software Product Line
Venue: arXiv cs.SE 2012
Year: 2012

In this paper, we present our experience based on a reengineering project. The software project is to re-engineer the original system of a company to answer the new requirements and changed business functions. Reengineering is a process that involves not only the software system, but also underlying business model. Particularly, the new business model is designed along with new technologies to support the new system. This paper presents our experience that applies with software product line approach to develop the new system supporting original business functions and new ones.
Image based Cryptography from a distance
Venue: arXiv cs.CR 2012
Year: 2012

An information is a message which is received and understood. Information can be sent one person to another over a long range but the process of sending information must be done in a secure way especially in case of a private message. Mathematicians and Engineers have historically relied on different algorithmic techniques to secure messages and signals. Cryptography, to most people, is concerned with keeping communications private. Indeed, the protection of sensitive communications has been the emphasis of cryptography throughout much of its history. Sometimes it is safer to send a message using an image and thus cryptography can also be done using images during an emergency. The need to extract information from images and interpret their contents has been one of the driving factors in the development of image processing and cryptography during the past decades. In this paper, a simple cryptographic method was used to decode a message which was in an image and it was done using a popular computational software.
Clustered Network Coding for Maintenance in Practical Storage Systems
Venue: arXiv cs.DC 2012
Year: 2012

Classical erasure codes, e.g. Reed-Solomon codes, have been acknowledged as an efficient alternative to plain replication to reduce the storage overhead in reliable distributed storage systems. Yet, such codes experience high overhead during the maintenance process. In this paper we propose a novel erasure-coded framework especially tailored for networked storage systems. Our approach relies on the use of random codes coupled with a clustered placement strategy, enabling the maintenance of a failed machine at the granularity of multiple files. Our repair protocol leverages network coding techniques to reduce by half the amount of data transferred during maintenance, as several files can be repaired simultaneously. This approach, as formally proven and demonstrated by our evaluation on a public experimental testbed, enables to dramatically decrease the bandwidth overhead during the maintenance process, as well as the time to repair a failure. In addition, the implementation is made as simple as possible, aiming at a deployment into practical systems.
Correlating Pedestrian Flows and Search Engine Queries
Venue: arXiv cs.HC 2012
Year: 2012

An important challenge for ubiquitous computing is the development of techniques that can characterize a location vis-a-vis the richness and diversity of urban settings. In this paper we report our work on correlating urban pedestrian flows with Google search queries. Using longitudinal data we show pedestrian flows at particular locations can be correlated with the frequency of Google search terms that are semantically relevant to those locations. Our approach can identify relevant content, media, and advertisements for particular locations.
On Lossless Universal Compression of Distributed Identical Sources
Venue: arXiv cs.IT 2012
Year: 2012

Slepian-Wolf theorem is a well-known framework that targets almost lossless compression of (two) data streams with symbol-by-symbol correlation between the outputs of (two) distributed sources. However, this paper considers a different scenario which does not fit in the Slepian-Wolf framework. We consider two identical but spatially separated sources. We wish to study the universal compression of a sequence of length $n$ from one of the sources provided that the decoder has access to (i.e., memorized) a sequence of length $m$ from the other source. Such a scenario occurs, for example, in the universal compression of data from multiple mirrors of the same server. In this setup, the correlation does not arise from symbol-by-symbol dependency of two outputs from the two sources. Instead, the sequences are correlated through the information that they contain about the unknown source parameter. We show that the finite-length nature of the compression problem at hand requires considering a notion of almost lossless source coding, where coding incurs an error probability $p_e(n)$ that vanishes with sequence length $n$. We obtain a lower bound on the average minimax redundancy of almost lossless codes as a function of the sequence length $n$ and the permissible error probability $p_e$ when the decoder has a memory of length $m$ and the encoders do not communicate. Our results demonstrate that a strict performance loss is incurred when the two encoders do not communicate even when the decoder knows the unknown parameter vector (i.e., $m \to \infty$).
Quasi-Succinct Indices
Venue: arXiv cs.IR 2012
Year: 2012

Compressed inverted indices in use today are based on the idea of gap compression: documents pointers are stored in increasing order, and the gaps between successive document pointers are stored using suitable codes which represent smaller gaps using less bits. Additional data such as counts and positions is stored using similar techniques. A large body of research has been built in the last 30 years around gap compression, including theoretical modeling of the gap distribution, specialized instantaneous codes suitable for gap encoding, and ad hoc document reorderings which increase the efficiency of instantaneous codes. This paper proposes to represent an index using a different architecture based on quasi-succinct representation of monotone sequences. We show that, besides being theoretically elegant and simple, the new index provides expected constant-time operations and, in practice, significant performance improvements on conjunctive, phrasal and proximity queries.
Social Influence in Social Advertising: Evidence from Field Experiments
Venue: arXiv cs.SI 2012
Year: 2012

Social advertising uses information about consumers' peers, including peer affiliations with a brand, product, organization, etc., to target ads and contextualize their display. This approach can increase ad efficacy for two main reasons: peers' affiliations reflect unobserved consumer characteristics, which are correlated along the social network; and the inclusion of social cues (i.e., peers' association with a brand) alongside ads affect responses via social influence processes. For these reasons, responses may be increased when multiple social signals are presented with ads, and when ads are affiliated with peers who are strong, rather than weak, ties. We conduct two very large field experiments that identify the effect of social cues on consumer responses to ads, measured in terms of ad clicks and the formation of connections with the advertised entity. In the first experiment, we randomize the number of social cues present in word-of-mouth advertising, and measure how responses increase as a function of the number of cues. The second experiment examines the effect of augmenting traditional ad units with a minimal social cue (i.e., displaying a peer's affiliation below an ad in light grey text). On average, this cue causes significant increases in ad performance. Using a measurement of tie strength based on the total amount of communication between subjects and their peers, we show that these influence effects are greatest for strong ties. Our work has implications for ad optimization, user interface design, and central questions in social science research.
Upper and Lower Bounds on the Cost of a Map-Reduce Computation
Venue: arXiv cs.DC 2012
Year: 2012

In this paper we study the tradeoff between parallelism and communication cost in a map-reduce computation. For any problem that is not "embarrassingly parallel," the finer we partition the work of the reducers so that more parallelism can be extracted, the greater will be the total communication between mappers and reducers. We introduce a model of problems that can be solved in a single round of map-reduce computation. This model enables a generic recipe for discovering lower bounds on communication cost as a function of the maximum number of inputs that can be assigned to one reducer. We use the model to analyze the tradeoff for three problems: finding pairs of strings at Hamming distance $d$, finding triangles and other patterns in a larger graph, and matrix multiplication. For finding strings of Hamming distance 1, we have upper and lower bounds that match exactly. For triangles and many other graphs, we have upper and lower bounds that are the same to within a constant factor. For the problem of matrix multiplication, we have matching upper and lower bounds for one-round map-reduce algorithms. We are also able to explore two-round map-reduce algorithms for matrix multiplication and show that these never have more communication, for a given reducer size, than the best one-round algorithm, and often have significantly less.
Inverse Modeling of Climate Responses of Monumental Buildings
Venue: arXiv cs.CE 2012
Year: 2012

The indoor climate conditions of monumental buildings are very important for the conservation of these objects. Simplified models with physical meaning are desired that are capable of simulating temperature and relative humidity. In this paper we research state-space models as methodology for the inverse modeling of climate responses of unheated monumental buildings. It is concluded that this approach is very promising for obtaining physical models and parameters of indoor climate responses. Furthermore state space models can be simulated very efficiently: the simulation duration time of a 100 year hourly based period take less than a second on an ordinary computer.
Parsimonious Mahalanobis Kernel for the Classification of High Dimensional Data
Venue: arXiv cs.NA 2012
Year: 2012

The classification of high dimensional data with kernel methods is considered in this article. Exploit- ing the emptiness property of high dimensional spaces, a kernel based on the Mahalanobis distance is proposed. The computation of the Mahalanobis distance requires the inversion of a covariance matrix. In high dimensional spaces, the estimated covariance matrix is ill-conditioned and its inversion is unstable or impossible. Using a parsimonious statistical model, namely the High Dimensional Discriminant Analysis model, the specific signal and noise subspaces are estimated for each considered class making the inverse of the class specific covariance matrix explicit and stable, leading to the definition of a parsimonious Mahalanobis kernel. A SVM based framework is used for selecting the hyperparameters of the parsimonious Mahalanobis kernel by optimizing the so-called radius-margin bound. Experimental results on three high dimensional data sets show that the proposed kernel is suitable for classifying high dimensional data, providing better classification accuracies than the conventional Gaussian kernel.
Decentralized Estimation of Laplacian Eigenvalues in Multi-Agent Systems
Venue: arXiv cs.SY 2012
Year: 2012

In this paper we present a decentralized algorithm to estimate the eigenvalues of the Laplacian matrix that encodes the network topology of a multi-agent system. We consider network topologies modeled by undirected graphs. The basic idea is to provide a local interaction rule among agents so that their state trajectory is a linear combination of sinusoids oscillating only at frequencies function of the eigenvalues of the Laplacian matrix. In this way, the problem of decentralized estimation of the eigenvalues is mapped into a standard signal processing problem in which the unknowns are the finite number of frequencies at which the signal oscillates.
Effective Digital Image Watermarking in YCbCr Color Space Accompanied by Presenting a Novel Technique Using DWT
Venue: arXiv cs.CR 2012
Year: 2012

In this paper, a quantization based watermark casting and blind watermark retrieval algorithm operating in YCbCr color space using discrete wavelet transform (DWT), for ownership verification and image authentication applications is implemented. This method uses implicit visual masking by inserting watermark bits into only the wavelet coefficients of high magnitude, in Y channel of YCbCr color space. A blind watermark retrieval technique that can detect the embedded watermark without the help from the original uncorrupted image is devised which is computationally efficient. The new watermarking algorithm combines and adapts various aspects from existing watermarking methods. Experimental results show that the proposed technique to embed watermark provides extra imperceptibility and robustness against various signal processing attacks in comparison with the same technique in RGB color space.
On the Distributed Construction of a Collision-Free Schedule in Multi-Hop Packet Radio Networks
Venue: arXiv cs.NI 2012
Year: 2012

This paper introduces a protocol that distributively constructs a collision-free schedule for multi-hop packet radio networks in the presence of hidden terminals. As a preliminary step, each wireless station computes the schedule length after gathering information about the number of flows in its neighbourhood. Then, a combination of deterministic and random backoffs are used to reach a collision-free schedule. A deterministic backoff is used after successful transmissions and a random backoff is used otherwise. It is explained that the short acknowledgement control packets can easily result in channel time fragmentation and, to avoid this, the use of link layer delayed acknowledgements is advocated and implemented. The performance results show that a collision-free protocol easily outperforms a collision-prone protocol such as Aloha. The time that is required for the network to converge to a collision-free schedule is assessed by means of simulation.
Computational Aspects of Dependence Logic
Venue: arXiv cs.LO 2012
Year: 2012

In this thesis (modal) dependence logic is investigated. It was introduced in 2007 by Jouko Vääanänen as an extension of first-order (resp. modal) logic by the dependence operator =(). For first-order (resp. propositional) variables x_1,...,x_n, =(x_1,...,x_n) intuitively states that the value of x_n is determined by those of x_1,...,x_n-1. We consider fragments of modal dependence logic obtained by restricting the set of allowed modal and propositional connectives. We classify these fragments with respect to the complexity of their satisfiability and model-checking problems. For satisfiability we obtain complexity degrees from P over NP, Sigma_P^2 and PSPACE up to NEXP, while for model-checking we only classify the fragments with respect to their tractability, i.e. we either show NP-completeness or containment in P. We then study the extension of modal dependence logic by intuitionistic implication. For this extension we again classify the complexity of the model-checking problem for its fragments. Here we obtain complexity degrees from P over NP and coNP up to PSPACE. Finally, we analyze first-order dependence logic, independence-friendly logic and their two-variable fragments. We prove that satisfiability for two-variable dependence logic is NEXP-complete, whereas for two-variable independence-friendly logic it is undecidable; and use this to prove that the latter is also more expressive than the former.
Latent Collaborative Retrieval
Venue: arXiv cs.IR 2012
Year: 2012

Retrieval tasks typically require a ranking of items given a query. Collaborative filtering tasks, on the other hand, learn to model user's preferences over items. In this paper we study the joint problem of recommending items to a user with respect to a given query, which is a surprisingly common task. This setup differs from the standard collaborative filtering one in that we are given a query x user x item tensor for training instead of the more traditional user x item matrix. Compared to document retrieval we do have a query, but we may or may not have content features (we will consider both cases) and we can also take account of the user's profile. We introduce a factorized model for this new task that optimizes the top-ranked items returned for the given query and user. We report empirical results where it outperforms several baselines.
Manifold Relevance Determination
Venue: arXiv cs.LG 2012
Year: 2012

In this paper we present a fully Bayesian latent variable model which exploits conditional nonlinear(in)-dependence structures to learn an efficient latent representation. The latent space is factorized to represent shared and private information from multiple views of the data. In contrast to previous approaches, we introduce a relaxation to the discrete segmentation and allow for a "softly" shared latent space. Further, Bayesian techniques allow us to automatically estimate the dimensionality of the latent spaces. The model is capable of capturing structure underlying extremely high dimensional spaces. This is illustrated by modelling unprocessed images with tenths of thousands of pixels. This also allows us to directly generate novel images from the trained model by sampling from the discovered latent spaces. We also demonstrate the model by prediction of human pose in an ambiguous setting. Our Bayesian framework allows us to perform disambiguation in a principled manner by including latent space priors which incorporate the dynamic nature of the data.
Total Variation and Euler's Elastica for Supervised Learning
Venue: arXiv cs.LG 2012
Year: 2012

In recent years, total variation (TV) and Euler's elastica (EE) have been successfully applied to image processing tasks such as denoising and inpainting. This paper investigates how to extend TV and EE to the supervised learning settings on high dimensional data. The supervised learning problem can be formulated as an energy functional minimization under Tikhonov regularization scheme, where the energy is composed of a squared loss and a total variation smoothing (or Euler's elastica smoothing). Its solution via variational principles leads to an Euler-Lagrange PDE. However, the PDE is always high-dimensional and cannot be directly solved by common methods. Instead, radial basis functions are utilized to approximate the target function, reducing the problem to finding the linear coefficients of basis functions. We apply the proposed methods to supervised learning tasks (including binary classification, multi-class classification, and regression) on benchmark data sets. Extensive experiments have demonstrated promising results of the proposed methods.
Downlink Coverage Analysis in a Heterogeneous Cellular Network
Venue: arXiv cs.IT 2012
Year: 2012

In this paper, we consider the downlink signal-to-interference-plus-noise ratio (SINR) analysis in a heterogeneous cellular network with K tiers. Each tier is characterized by a base-station (BS) arrangement according to a homogeneous Poisson point process with certain BS density, transmission power, random shadow fading factors with arbitrary distribution, arbitrary path-loss exponent and a certain bias towards admitting the mobile-station (MS). The MS associates with the BS that has the maximum SINR under the open access cell association scheme. For such a general setting, we provide an analytical characterization of the coverage probability at the MS.