OpenRaiser/Intern-Atlas huggingface dataset:
Active Metric Learning from Relative Comparisons
Venue: arXiv cs.LG 2014
Year: 2014

This work focuses on active learning of distance metrics from relative comparison information. A relative comparison specifies, for a data point triplet $(x_i,x_j,x_k)$, that instance $x_i$ is more similar to $x_j$ than to $x_k$. Such constraints, when available, have been shown to be useful toward defining appropriate distance metrics. In real-world applications, acquiring constraints often require considerable human effort. This motivates us to study how to select and query the most useful relative comparisons to achieve effective metric learning with minimum user effort. Given an underlying class concept that is employed by the user to provide such constraints, we present an information-theoretic criterion that selects the triplet whose answer leads to the highest expected gain in information about the classes of a set of examples. Directly applying the proposed criterion requires examining $O(n^3)$ triplets with $n$ instances, which is prohibitive even for datasets of moderate size. We show that a randomized selection strategy can be used to reduce the selection pool from $O(n^3)$ to $O(n)$, allowing us to scale up to larger-size problems. Experiments show that the proposed method consistently outperforms two baseline policies.
Crowdsourcing Pareto-Optimal Object Finding by Pairwise Comparisons
Venue: arXiv cs.AI 2014
Year: 2014

This is the first study on crowdsourcing Pareto-optimal object finding, which has applications in public opinion collection, group decision making, and information exploration. Departing from prior studies on crowdsourcing skyline and ranking queries, it considers the case where objects do not have explicit attributes and preference relations on objects are strict partial orders. The partial orders are derived by aggregating crowdsourcers' responses to pairwise comparison questions. The goal is to find all Pareto-optimal objects by the fewest possible questions. It employs an iterative question-selection framework. Guided by the principle of eagerly identifying non-Pareto optimal objects, the framework only chooses candidate questions which must satisfy three conditions. This design is both sufficient and efficient, as it is proven to find a short terminal question sequence. The framework is further steered by two ideas---macro-ordering and micro-ordering. By different micro-ordering heuristics, the framework is instantiated into several algorithms with varying power in pruning questions. Experiment results using both real crowdsourcing marketplace and simulations exhibited not only orders of magnitude reductions in questions when compared with a brute-force approach, but also close-to-optimal performance from the most efficient instantiation.
Three Metrics to Explore the Openness of GitHub projects
Venue: arXiv cs.SE 2014
Year: 2014

Open source software projects evolve thanks to a group of volunteers that help in their development. Thus, the success of these projects depends on their ability to attract (and keep) developers. We believe the openness of a project, i.e., how easy is for a new user to actively contribute to it, can help to make a project more attractive. To explore the openness of a software project, we propose three metrics focused on: (1) the distribution of the project community, (2) the rate of acceptance of external contributions and (3) the time it takes to become an official collaborator of the project. We have adapted and applied these metrics to a subset of GitHub projects, thus giving some practical findings on their openness.
A Fast Quartet Tree Heuristic for Hierarchical Clustering
Venue: arXiv cs.LG 2014
Year: 2014

The Minimum Quartet Tree Cost problem is to construct an optimal weight tree from the $3{n \choose 4}$ weighted quartet topologies on $n$ objects, where optimality means that the summed weight of the embedded quartet topologies is optimal (so it can be the case that the optimal tree embeds all quartets as nonoptimal topologies). We present a Monte Carlo heuristic, based on randomized hill climbing, for approximating the optimal weight tree, given the quartet topology weights. The method repeatedly transforms a dendrogram, with all objects involved as leaves, achieving a monotonic approximation to the exact single globally optimal tree. The problem and the solution heuristic has been extensively used for general hierarchical clustering of nontree-like (non-phylogeny) data in various domains and across domains with heterogeneous data. We also present a greatly improved heuristic, reducing the running time by a factor of order a thousand to ten thousand. All this is implemented and available, as part of the CompLearn package. We compare performance and running time of the original and improved versions with those of UPGMA, BioNJ, and NJ, as implemented in the SplitsTree package on genomic data for which the latter are optimized. Keywords: Data and knowledge visualization, Pattern matching--Clustering--Algorithms/Similarity measures, Hierarchical clustering, Global optimization, Quartet tree, Randomized hill-climbing,
Matching Dynamics with Constraints
Venue: arXiv cs.GT 2014
Year: 2014

We study uncoordinated matching markets with additional local constraints that capture, e.g., restricted information, visibility, or externalities in markets. Each agent is a node in a fixed matching network and strives to be matched to another agent. Each agent has a complete preference list over all other agents it can be matched with. However, depending on the constraints and the current state of the game, not all possible partners are available for matching at all times. For correlated preferences, we propose and study a general class of hedonic coalition formation games that we call coalition formation games with constraints. This class includes and extends many recently studied variants of stable matching, such as locally stable matching, socially stable matching, or friendship matching. Perhaps surprisingly, we show that all these variants are encompassed in a class of "consistent" instances that always allow a polynomial improvement sequence to a stable state. In addition, we show that for consistent instances there always exists a polynomial sequence to every reachable state. Our characterization is tight in the sense that we provide exponential lower bounds when each of the requirements for consistency is violated. We also analyze matching with uncorrelated preferences, where we obtain a larger variety of results. While socially stable matching always allows a polynomial sequence to a stable state, for other classes different additional assumptions are sufficient to guarantee the same results. For the problem of reaching a given stable state, we show NP-hardness in almost all considered classes of matching games.
Low-High SNR Transition in Multiuser MIMO
Venue: arXiv cs.IT 2014
Year: 2014

Multiuser MIMO (MU-MIMO) plays a key role in the widely adopted 3GPP LTE standard for wireless cellular networks. While exact and asymptotic sum-rate results are well known, the problem of obtaining intuitive analytical results for medium signal-to-noise ratios (SNRs) is still not solved. In this paper, we propose the bend point, which quantifies the transition between low and high SNR; i.e., the beginning of the high SNR region. We derive the bend point for MU-MIMO with zero-forcing precoding and show that it is intimately related to the intercept of the high SNR asymptote with the zero sum-rate line. Using this result, we obtain a new approximation of the sum-rate at the bend point---providing a useful rule of thumb for the effect of increasing the number of antennas at medium SNR.
Toward Fully-Shared Access: Designing ISP Service Plans Leveraging Excess Bandwidth Allocation
Venue: arXiv cs.NI 2014
Year: 2014

Shaping subscriber traffic based on token bucket filter (TBF) by Internet service providers (ISPs) results in waste of network resources in shared access when there are few active subscribers, because it cannot allocate excess bandwidth in the long term. New traffic control schemes have been recently proposed to allocate excess bandwidth among active subscribers proportional to their token generation rates. In this paper we report the current status of our research on designing flexible yet practical service plans exploiting excess bandwidth allocation enabled by the new traffic control schemes in shared access networks, which are attractive to both ISP and its subscribers in terms of revenue and quality of service (QoS) and serve as a stepping stone to fully-shared access in the future.
A Combined Method Of Fractal And GLCM Features For MRI And CT Scan Images Classification
Venue: arXiv cs.CV 2014
Year: 2014

Fractal analysis has been shown to be useful in image processing for characterizing shape and gray-scale complexity. The fractal feature is a compact descriptor used to give a numerical measure of the degree of irregularity of the medical images. This descriptor property does not give ownership of the local image structure. In this paper, we present a combination of this parameter based on Box Counting with GLCM Features. This powerful combination has proved good results especially in classification of medical texture from MRI and CT Scan images of trabecular bone. This method has the potential to improve clinical diagnostics tests for osteoporosis pathologies.
Laboratory Test Bench for Research Network and Cloud Computing
Venue: arXiv cs.DC 2014
Year: 2014

At present moment, there is a great interest in development of information systems operating in cloud infrastructures. Generally, many of tasks remain unresolved such as tasks of optimization of large databases in a hybrid cloud infrastructure, quality of service (QoS) at different levels of cloud services, dynamic control of distribution of cloud resources in application systems and many others. Research and development of new solutions can be limited in case of using emulators or international commercial cloud services, due to the closed architecture and limited opportunities for experimentation. Article provides answers to questions on the establishment of a pilot cloud practically "at home" with the ability to adjust the width of the emulation channel and delays in data transmission. It also describes architecture and configuration of the experimental setup. The proposed modular structure can be expanded by available computing power.
Source and Channel Optimal Rate LDPC Code Design for one Sender in BE-MAC with Source Correlation
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we present an extension of the semidefinite programming formulation of the optimal rate code design in single link Binary Erasure Channel (BEC) proposed by the authors to the Binary Erasure Multiple Access Channel (BE-MAC) with two sources correlation. This new way can be easily extended to the multiple access senders. Simulation results show the efficiency and effectiveness of the new approach in practice.
Uncertainty Quantification for Integrated Circuits: Stochastic Spectral Methods
Venue: arXiv cs.CE 2014
Year: 2014

Due to significant manufacturing process variations, the performance of integrated circuits (ICs) has become increasingly uncertain. Such uncertainties must be carefully quantified with efficient stochastic circuit simulators. This paper discusses the recent advances of stochastic spectral circuit simulators based on generalized polynomial chaos (gPC). Such techniques can handle both Gaussian and non-Gaussian random parameters, showing remarkable speedup over Monte Carlo for circuits with a small or medium number of parameters. We focus on the recently developed stochastic testing and the application of conventional stochastic Galerkin and stochastic collocation schemes to nonlinear circuit problems. The uncertainty quantification algorithms for static, transient and periodic steady-state simulations are presented along with some practical simulation results. Some open problems in this field are discussed.
Is the new citation-rank approach P100' in bibliometrics really new?
Venue: arXiv cs.DL 2014
Year: 2014

The percentile-based rating scale P100 describes the citation impact in terms of the distribution of unique citation values. This approach has recently been refined by considering also the frequency of papers with the same citation counts. Here I compare the resulting P100' with P100 for an empirical dataset and a simple fictitious model dataset. It is shown that P100' is not much different from standard percentile-based ratings in terms of citation frequencies. A new indicator P100'' is introduced.
Finding Even Subgraphs Even Faster
Venue: arXiv cs.DS 2014
Year: 2014

Problems of the following kind have been the focus of much recent research in the realm of parameterized complexity: Given an input graph (digraph) on $n$ vertices and a positive integer parameter $k$, find if there exist $k$ edges (arcs) whose deletion results in a graph that satisfies some specified parity constraints. In particular, when the objective is to obtain a connected graph in which all the vertices have even degrees---where the resulting graph is \emph{Eulerian}---the problem is called Undirected Eulerian Edge Deletion. The corresponding problem in digraphs where the resulting graph should be strongly connected and every vertex should have the same in-degree as its out-degree is called Directed Eulerian Edge Deletion. Cygan et al. [\emph{Algorithmica, 2014}] showed that these problems are fixed parameter tractable (FPT), and gave algorithms with the running time $2^{O(k \log k)}n^{O(1)}$. They also asked, as an open problem, whether there exist FPT algorithms which solve these problems in time $2^{O(k)}n^{O(1)}$. In this paper we answer their question in the affirmative: using the technique of computing \emph{representative families of co-graphic matroids} we design algorithms which solve these problems in time $2^{O(k)}n^{O(1)}$. The crucial insight we bring to these problems is to view the solution as an independent set of a co-graphic matroid. We believe that this view-point/approach will be useful in other problems where one of the constraints that need to be satisfied is that of connectivity.
TCP Performance for Kurd Messenger Application Using Bio-computing
Venue: arXiv cs.NI 2014
Year: 2014

This work was conducted to design, implement, and evaluate a new model of measuring Transmission Control Protocol (TCP) performance of real time network. The proposed model Biological Kurd Messenger (BIOKM) has two main goals: First is to run the model efficiently, second is to obtain high TCP performance via real time network using bio-computing technique, especially molecular calculation because it provides wisdom results and it can exploit all facilities of phylogentic analysis. To measure TCP performance two protocols were selected Internet Relay Chat Daemon (IRCD) and File Transfer Protocol (FTP), the BIOKM model consists of two applications Kurd Messenger Server Side (KMSS) and Kurd Messenger Client Side (KMCS) written in Java programming language by implementing algorithms of BIOKM Server and Client application. The paper also includes the implementation of hybridized model algorithm based on Neighbor-Joining (NJ) method to measure TCP performance, then implementing algorithm of Little law (steady state) for single server queue as a comparison with bio-computing algorithm. The results obtained by using bio-computing and little law techniques show very good performance and the two techniques result are very close to each other this is because of local implementation. The main tools which have been used in this work can be divided into software and hardware tools. Keywords: Biological Kurd Messenger (BIOKM), Kurd Messenger Phylogenetic tree, Hybridized Model, Little Law, TCP Performance.
A Survey on Heterogeneous Face Recognition: Sketch, Infra-red, 3D and Low-resolution
Venue: arXiv cs.CV 2014
Year: 2014

Heterogeneous face recognition (HFR) refers to matching face imagery across different domains. It has received much interest from the research community as a result of its profound implications in law enforcement. A wide variety of new invariant features, cross-modality matching models and heterogeneous datasets being established in recent years. This survey provides a comprehensive review of established techniques and recent developments in HFR. Moreover, we offer a detailed account of datasets and benchmarks commonly used for evaluation. We finish by assessing the state of the field and discussing promising directions for future research.
Subspace Alignment For Domain Adaptation
Venue: arXiv cs.CV 2014
Year: 2014

In this paper, we introduce a new domain adaptation (DA) algorithm where the source and target domains are represented by subspaces spanned by eigenvectors. Our method seeks a domain invariant feature space by learning a mapping function which aligns the source subspace with the target one. We show that the solution of the corresponding optimization problem can be obtained in a simple closed form, leading to an extremely fast algorithm. We present two approaches to determine the only hyper-parameter in our method corresponding to the size of the subspaces. In the first approach we tune the size of subspaces using a theoretical bound on the stability of the obtained result. In the second approach, we use maximum likelihood estimation to determine the subspace size, which is particularly useful for high dimensional data. Apart from PCA, we propose a subspace creation method that outperform partial least squares (PLS) and linear discriminant analysis (LDA) in domain adaptation. We test our method on various datasets and show that, despite its intrinsic simplicity, it outperforms state of the art DA methods.
Sonification Aesthetics and Listening for Network Situational Awareness
Venue: arXiv cs.HC 2014
Year: 2014

This paper looks at the problem of using sonification to enable network administrators to maintaining situational awareness about their network environment. Network environments generate a lot of data and the need for continuous monitoring means that sonification systems must be designed in such a way as to maximise acceptance while minimising annoyance and listener fatigue. It will be argued that solutions based on the concept of the soundscape offer an ecological advantage over other sonification designs.
Sandboxing for Software Transactional Memory with Deferred Updates
Venue: arXiv cs.DC 2014
Year: 2014

Software transactional memory implementations which allow transactions to work on inconsistent states of shared data, risk to cause application visible errors such as memory access violations or endless loops. Hence, many implementations rely on repeated incremental validation of every read of the transaction to always guarantee for a consistent view of shared data. Because this eager validation technique generates significant processing costs several proposals have been published to establish a sandbox for transactions, which transparently prevents or suppresses those errors and thereby allows to reduce the frequency of in-flight validations. The most comprehensive sandboxing concept of transactions in software transactional memory based on deferred updates and considering unmanaged languages, integrates multiple techniques such as signal interposition, out-of-band validation and static and dynamic instrumentation. The latter comprises the insertion of a validation barrier in front of every direct write which addresses the execution stack of the thread and potentially results from unvalidated reads. This paper basically results from a review of this sandboxing approach, which revealed some improvements for sandboxing on C/C++. Based on knowledge about the runtime environment and the compiler an error model has been developed to identify critical paths to application visible errors. This analysis lead to a concept for stack protection with less frequent validation, an alternative out-of-band validation technique and revealed additional risks of so-called waivered regions without instrumentation inside transactions.
Exploratory Analysis of a Terabyte Scale Web Corpus
Venue: arXiv cs.IR 2014
Year: 2014

In this paper we present a preliminary analysis over the largest publicly accessible web dataset: the Common Crawl Corpus. We measure nine web characteristics from two levels of granularity using MapReduce and we comment on the initial observations over a fraction of it. To the best of our knowledge two of the characteristics, the language distribution and the HTML version of pages have not been analyzed in previous work, while the specific dataset has been only analyzed on page level.
Higher-Order Triangular-Distance Delaunay Graphs: Graph-Theoretical Properties
Venue: arXiv cs.CG 2014
Year: 2014

We consider an extension of the triangular-distance Delaunay graphs (TD-Delaunay) on a set $P$ of points in the plane. In TD-Delaunay, the convex distance is defined by a fixed-oriented equilateral triangle $\triangledown$, and there is an edge between two points in $P$ if and only if there is an empty homothet of $\triangledown$ having the two points on its boundary. We consider higher-order triangular-distance Delaunay graphs, namely $k$-TD, which contains an edge between two points if the interior of the homothet of $\triangledown$ having the two points on its boundary contains at most $k$ points of $P$. We consider the connectivity, Hamiltonicity and perfect-matching admissibility of $k$-TD. Finally we consider the problem of blocking the edges of $k$-TD.
Images encryption using AES and variable permutations
Venue: arXiv cs.CR 2014
Year: 2014

This work proposes a different procedure to encrypt images of 256 grey levels and colour, using the symmetric system Advanced Encryption Standard with a variable permutation in the first round, after the x-or operation. Variable permutation means using a different one for each input block of 128 bits. In this vein, an algorithm is constructed that defines a Bijective function between sets Nm = {n in N, 0 <= n < fac(m)} with n >= 2 and Pm = {pi, pi is a permutation of 0, 1, ..., m-1}. This algorithm calculates permutations on 128 positions with 127 known constants. The transcendental numbers are used to select the 127 constants in a pseudo-random way. The proposed encryption quality is evaluated by the following criteria: Correlation; horizontal, vertical and diagonal, Entropy and Discrete Fourier Transform. The latter uses the NIST standard 800-22. Also, a sensitivity analysis was performed in encrypted figures. Furthermore, an additional test is proposed which considers the distribution of 256 shades of the three colours; red, green and blue for colour images. On the other hand, it is important to mention that the images are encrypted without loss of information because many banking companies and some safety area countries do not allow the figures to go through a compression process with information loss. i.e., it is forbidden to use formats such as JPEG.
Replacing the Irreplaceable: Fast Algorithms for Team Member Recommendation
Venue: arXiv cs.SI 2014
Year: 2014

In this paper, we study the problem of Team Member Replacement: given a team of people embedded in a social network working on the same task, find a good candidate who can fit in the team after one team member becomes unavailable. We conjecture that a good team member replacement should have good skill matching as well as good structure matching. We formulate this problem using the concept of graph kernel. To tackle the computational challenges, we propose a family of fast algorithms by (a) designing effective pruning strategies, and (b) exploring the smoothness between the existing and the new team structures. We conduct extensive experimental evaluations on real world datasets to demonstrate the effectiveness and efficiency. Our algorithms (a) perform significantly better than the alternative choices in terms of both precision and recall; and (b) scale sub-linearly.