OpenRaiser/Intern-Atlas huggingface dataset:
Multi-Touch Attribution Based Budget Allocation in Online Advertising
Venue: arXiv cs.AI 2015
Year: 2015

Budget allocation in online advertising deals with distributing the campaign (insertion order) level budgets to different sub-campaigns which employ different targeting criteria and may perform differently in terms of return-on-investment (ROI). In this paper, we present the efforts at Turn on how to best allocate campaign budget so that the advertiser or campaign-level ROI is maximized. To do this, it is crucial to be able to correctly determine the performance of sub-campaigns. This determination is highly related to the action-attribution problem, i.e. to be able to find out the set of ads, and hence the sub-campaigns that provided them to a user, that an action should be attributed to. For this purpose, we employ both last-touch (last ad gets all credit) and multi-touch (many ads share the credit) attribution methodologies. We present the algorithms deployed at Turn for the attribution problem, as well as their parallel implementation on the large advertiser performance datasets. We conclude the paper with our empirical comparison of last-touch and multi-touch attribution-based budget allocation in a real online advertising setting.
Maximizing Friend-Making Likelihood for Social Activity Organization
Venue: arXiv cs.SI 2015
Year: 2015

The social presence theory in social psychology suggests that computer-mediated online interactions are inferior to face-to-face, in-person interactions. In this paper, we consider the scenarios of organizing in person friend-making social activities via online social networks (OSNs) and formulate a new research problem, namely, Hop-bounded Maximum Group Friending (HMGF), by modeling both existing friendships and the likelihood of new friend making. To find a set of attendees for socialization activities, HMGF is unique and challenging due to the interplay of the group size, the constraint on existing friendships and the objective function on the likelihood of friend making. We prove that HMGF is NP-Hard, and no approximation algorithm exists unless P = NP. We then propose an error-bounded approximation algorithm to efficiently obtain the solutions very close to the optimal solutions. We conduct a user study to validate our problem formulation and per- form extensive experiments on real datasets to demonstrate the efficiency and effectiveness of our proposed algorithm.
Empowering Web Service Search with Business Know-How
Venue: arXiv cs.SE 2015
Year: 2015

In this paper, we propose first to start by presenting a state of the art of existing approaches about scientific workflows (including neuroscience workflows) in order to highlight business users' needs in terms of Web Services combination. Then we discuss about intentional process modeling for scientific workflows especially to search for Web Services. Next we present our approach SATIS to provide reasoning and traceability capabilities on Web Services business combination know-how, in order to bridge the gap between workflows providers and users.
Untangling Fine-Grained Code Changes
Venue: arXiv cs.SE 2015
Year: 2015

After working for some time, developers commit their code changes to a version control system. When doing so, they often bundle unrelated changes (e.g., bug fix and refactoring) in a single commit, thus creating a so-called tangled commit. Sharing tangled commits is problematic because it makes review, reversion, and integration of these commits harder and historical analyses of the project less reliable. Researchers have worked at untangling existing commits, i.e., finding which part of a commit relates to which task. In this paper, we contribute to this line of work in two ways: (1) A publicly available dataset of untangled code changes, created with the help of two developers who accurately split their code changes into self contained tasks over a period of four months; (2) a novel approach, EpiceaUntangler, to help developers share untangled commits (aka. atomic commits) by using fine-grained code change information. EpiceaUntangler is based and tested on the publicly available dataset, and further evaluated by deploying it to 7 developers, who used it for 2 weeks. We recorded a median success rate of 91% and average one of 75%, in automatically creating clusters of untangled fine-grained code changes.
Limitations in the spectral method for graph partitioning: detectability threshold and localization of eigenvectors
Venue: arXiv cs.SI 2015
Year: 2015

Investigating the performance of different methods is a fundamental problem in graph partitioning. In this paper, we estimate the so-called detectability threshold for the spectral method with both unnormalized and normalized Laplacians in sparse graphs. The detectability threshold is the critical point at which the result of the spectral method is completely uncorrelated to the planted partition. We also analyze whether the localization of eigenvectors affects the partitioning performance in the detectable region. We use the replica method, which is often used in the field of spin-glass theory, and focus on the case of bisection. We show that the gap between the estimated threshold for the spectral method and the threshold obtained from Bayesian inference is considerable in sparse graphs, even without eigenvector localization. This gap closes in a dense limit.
A Review of Audio Features and Statistical Models Exploited for Voice Pattern Design
Venue: arXiv cs.SD 2015
Year: 2015

Audio fingerprinting, also named as audio hashing, has been well-known as a powerful technique to perform audio identification and synchronization. It basically involves two major steps: fingerprint (voice pattern) design and matching search. While the first step concerns the derivation of a robust and compact audio signature, the second step usually requires knowledge about database and quick-search algorithms. Though this technique offers a wide range of real-world applications, to the best of the authors' knowledge, a comprehensive survey of existing algorithms appeared more than eight years ago. Thus, in this paper, we present a more up-to-date review and, for emphasizing on the audio signal processing aspect, we focus our state-of-the-art survey on the fingerprint design step for which various audio features and their tractable statistical models are discussed.
Analysis of the Impact of Impulsive Noise Parameters on BER Performance of OFDM Power-Line Communications
Venue: arXiv cs.IT 2015
Year: 2015

It is well known that asynchronous impulsive noise is the main source of distortion that drastically affects the power-line communications (PLC) performance. Recently, more realistic models have been proposed in the literature which better fit the physical properties of real impulsive noise. In this paper, we consider a pulse train model and propose a thorough analysis of the impact of impulsive noise parameters, namely impulse width and amplitude as well as inter-arrival time, on the bit error rate (BER) performance of orthogonal frequency division multiplexing (OFDM) broadband PLC. A comparison with the conventional Bernoulli-Gaussian (BG) impulsive noise model exhibits the difference between the two approaches, showing the necessity of more realistic models.
CrowdGather: Entity Extraction over Structured Domains
Venue: arXiv cs.DB 2015
Year: 2015

Crowdsourced entity extraction is often used to acquire data for many applications, including recommendation systems, construction of aggregated listings and directories, and knowledge base construction. Current solutions focus on entity extraction using a single query, e.g., only using "give me another restaurant", when assembling a list of all restaurants. Due to the cost of human labor, solutions that focus on a single query can be highly impractical. In this paper, we leverage the fact that entity extraction often focuses on {\em structured domains}, i.e., domains that are described by a collection of attributes, each potentially exhibiting hierarchical structure. Given such a domain, we enable a richer space of queries, e.g., "give me another Moroccan restaurant in Manhattan that does takeout". Naturally, enabling a richer space of queries comes with a host of issues, especially since many queries return empty answers. We develop new statistical tools that enable us to reason about the gain of issuing {\em additional queries} given little to no information, and show how we can exploit the overlaps across the results of queries for different points of the data domain to obtain accurate estimates of the gain. We cast the problem of {\em budgeted entity extraction} over large domains as an adaptive optimization problem that seeks to maximize the number of extracted entities, while minimizing the overall extraction costs. We evaluate our techniques with experiments on both synthetic and real-world datasets, demonstrating a yield of up to 4X over competing approaches for the same budget.
An Optimal Bidimensional Multi-Armed Bandit Auction for Multi-unit Procurement
Venue: arXiv cs.GT 2015
Year: 2015

We study the problem of a buyer (aka auctioneer) who gains stochastic rewards by procuring multiple units of a service or item from a pool of heterogeneous strategic agents. The reward obtained for a single unit from an allocated agent depends on the inherent quality of the agent; the agent's quality is fixed but unknown. Each agent can only supply a limited number of units (capacity of the agent). The costs incurred per unit and capacities are private information of the agents. The auctioneer is required to elicit costs as well as capacities (making the mechanism design bidimensional) and further, learn the qualities of the agents as well, with a view to maximize her utility. Motivated by this, we design a bidimensional multi-armed bandit procurement auction that seeks to maximize the expected utility of the auctioneer subject to incentive compatibility and individual rationality while simultaneously learning the unknown qualities of the agents. We first assume that the qualities are known and propose an optimal, truthful mechanism 2D-OPT for the auctioneer to elicit costs and capacities. Next, in order to learn the qualities of the agents in addition, we provide sufficient conditions for a learning algorithm to be Bayesian incentive compatible and individually rational. We finally design a novel learning mechanism, 2D-UCB that is stochastic Bayesian incentive compatible and individually rational.
Bounding the Clique-Width of $H$-free Chordal Graphs
Venue: arXiv cs.DM 2015
Year: 2015

A graph is $H$-free if it has no induced subgraph isomorphic to $H$. Brandstädt, Engelfriet, Le and Lozin proved that the class of chordal graphs with independence number at most 3 has unbounded clique-width. Brandstädt, Le and Mosca erroneously claimed that the gem and the co-gem are the only two 1-vertex $P_4$-extensions $H$ for which the class of $H$-free chordal graphs has bounded clique-width. In fact we prove that bull-free chordal and co-chair-free chordal graphs have clique-width at most 3 and 4, respectively. In particular, we find four new classes of $H$-free chordal graphs of bounded clique-width. Our main result, obtained by combining new and known results, provides a classification of all but two stubborn cases, that is, with two potential exceptions we determine all graphs $H$ for which the class of $H$-free chordal graphs has bounded clique-width. We illustrate the usefulness of this classification for classifying other types of graph classes by proving that the class of $(2P_1+P_3,K_4)$-free graphs has bounded clique-width via a reduction to $K_4$-free chordal graphs. Finally, we give a complete classification of the (un)boundedness of clique-width of $H$-free weakly chordal graphs.
Degrees-of-Freedom of the K-User MISO Interference Channel with Delayed Local CSIT
Venue: arXiv cs.IT 2015
Year: 2015

This paper considers a K-user Multiple-Input-Single-Output (MISO) Interference Channel (IC), where the channel state information obtained by the transmitters (CSIT) is perfect, but completely outdated. A Retrospective Interference Alignment (RIA) using such delayed CSIT was proposed by the authors of [1] for the MISO Broadcast Channel (BC), but the extension to the MISO IC is a non-trivial step as each transmitter only has the message intended for the corresponding user. Recently, [7] focused on a Single-Input-Single-Output (SISO) IC and solved such bottleneck by inventing a distributed higher order symbol generation. Our main work is to extend [7] to the MISO case by integrating some features of the scheme proposed in [1]. The achieved sum Degrees-of-Freedom (DoF) performance is asymptotically given by 64/15 when $K\to\infty$, outperforming all the previously known results.
Breaking Sticks and Ambiguities with Adaptive Skip-gram
Venue: arXiv cs.CL 2015
Year: 2015

Recently proposed Skip-gram model is a powerful method for learning high-dimensional word representations that capture rich semantic relationships between words. However, Skip-gram as well as most prior work on learning word representations does not take into account word ambiguity and maintain only single representation per word. Although a number of Skip-gram modifications were proposed to overcome this limitation and learn multi-prototype word representations, they either require a known number of word meanings or learn them using greedy heuristic approaches. In this paper we propose the Adaptive Skip-gram model which is a nonparametric Bayesian extension of Skip-gram capable to automatically learn the required number of representations for all words at desired semantic resolution. We derive efficient online variational learning algorithm for the model and empirically demonstrate its efficiency on word-sense induction task.
Path Finding under Uncertainty through Probabilistic Inference
Venue: arXiv cs.AI 2015
Year: 2015

We introduce a new approach to solving path-finding problems under uncertainty by representing them as probabilistic models and applying domain-independent inference algorithms to the models. This approach separates problem representation from the inference algorithm and provides a framework for efficient learning of path-finding policies. We evaluate the new approach on the Canadian Traveler Problem, which we formulate as a probabilistic model, and show how probabilistic inference allows high performance stochastic policies to be obtained for this problem.
On the Griesmer bound for nonlinear codes
Venue: arXiv cs.IT 2015
Year: 2015

Most bounds on the size of codes hold for any code, whether linear or nonlinear. Notably, the Griesmer bound, holds only in the linear case. In this paper we characterize a family of systematic nonlinear codes for which the Griesmer bound holds. Moreover, we show that the Griesmer bound does not necessarily hold for a systematic code by showing explicit counterexamples. On the other hand, we are also able to provide (weaker) versions of the Griesmer bound holding for all systematic codes.
Throughput Analysis for Full-Duplex Wireless Networks with Imperfect Self-interference Cancellation
Venue: arXiv cs.IT 2015
Year: 2015

This paper investigates the throughput for wireless network with full-duplex radios using stochastic geometry. Full-duplex (FD) radios can exchange data simultaneously with each other. On the other hand, the downside of FD transmission is that it will inevitably cause extra interference to the network compared to half-duplex (HD) transmission. Moreover, the residual self-interference has negative effects on the network throughput. In this paper, we focus on a wireless network of nodes with both HD and FD capabilities and derive and optimize the throughput in such a network. Our analytical result shows that if the network is adapting an ALOHA protocol, the maximal throughput is achieved by scheduling all concurrently transmitting nodes to work in either FD mode or HD mode depending on one simple condition. Moreover, the effects of imperfect self-interference cancellation on the signal-to-interference ratio (SIR) loss and throughput are also analyzed based on our mathematical model. We rigorously quantify the impact of imperfect self-interference cancellation on the throughput gain, transmission range, and other metrics, and we establish the minimum amount of self-interference suppression needed for FD to be beneficial.
Optimal commitments in auctions with incomplete information
Venue: arXiv cs.GT 2015
Year: 2015

We are interested in the problem of optimal commitments in rank-and-bid based auctions, a general class of auctions that include first price and all-pay auctions as special cases. Our main contribution is a novel approach to solve for optimal commitment in this class of auctions, for any continuous type distributions. Applying our approach, we are able to solve optimal commitments for first-price and all-pay auctions in closed-form for fairly general distribution settings. The optimal commitments functions in these auctions reveal two surprisingly opposite insights: in the optimal commitment, the leader bids passively when he has a low type. We interpret this as a credible way to alleviate competition and to collude. In sharp contrast, when his type is high enough, the leader sometimes would go so far as to bid above his own value. We interpret this as a credible way to threat. Combing both insights, we show via concrete examples that the leader is indeed willing to do so to secure more utility when his type is in the middle. Our main approach consists of a series of nontrivial innovations. In particular we put forward a concept called equal-bid function that connects both players' strategies, as well as a concept called equal-utility curve that smooths any leader strategy into a continuous and differentiable strategy. We believe these techniques and insights are general and can be applied to similar problems.
Coercive Region-level Registration for Multi-modal Images
Venue: arXiv cs.CV 2015
Year: 2015

We propose a coercive approach to simultaneously register and segment multi-modal images which share similar spatial structure. Registration is done at the region level to facilitate data fusion while avoiding the need for interpolation. The algorithm performs alternating minimization of an objective function informed by statistical models for pixel values in different modalities. Hypothesis tests are developed to determine whether to refine segmentations by splitting regions. We demonstrate that our approach has significantly better performance than the state-of-the-art registration and segmentation methods on microscopy images.
Concept for a CMOS Image Sensor Suited for Analog Image Pre-Processing
Venue: arXiv cs.ET 2015
Year: 2015

A concept for a novel CMOS image sensor suited for analog image pre-processing is presented in this paper. As an example, an image restoration algorithm for reducing image noise is applied as image pre-processing in the analog domain. To supply low-latency data input for analog image preprocessing, the proposed concept for a CMOS image sensor offers a new sensor signal acquisition method in 2D. In comparison to image pre-processing in the digital domain, the proposed analog image pre-processing promises an improved image quality. Furthermore, the image noise at the stage of analog sensor signal acquisition can be used to select the most effective restoration algorithm applied to the analog circuit due to image processing prior to the A/D converter.
An Improved E-voting scheme using Secret Sharing based Secure Multi-party Computation
Venue: arXiv cs.CR 2015
Year: 2015

E-voting systems (EVS)are having potential advantages over many existing voting schemes.Security, transparency, accuracy and reliability are the major concern in these systems.EVS continues to grow as the technology advances.It is inexpensive and efficient as the resources become reusable.Fast and accurate computation of results with voter privacy is the added advantage.In the proposed system we make use of secret sharing technique and secure multi party computation(SMC) to achieve security and reliability.Secret sharing is an important technique used for SMC. Multi-party computation is typically accomplished using secret sharing by making shares of the input and manipulating the shares to compute a typical function of the input.The proposed system make use of bitwise representation of votes and only the shares are used for transmission and computation of result.Secure sum evaluation can be done with shares distributed using Shamir's secret sharing scheme.The scheme is hence secure and reliable and does not make any number theoretic assumptions for security.We also propose a unique method which calculates the candidates individual votes keeping the anonymity.
Comparison Issues in Large Graphs: State of the Art and Future Directions
Venue: arXiv cs.DS 2015
Year: 2015

Graph comparison is fundamentally important for many applications such as the analysis of social networks and biological data and has been a significant research area in the pattern recognition and pattern analysis domains. Nowadays, the graphs are large, they may have billions of nodes and edges. Comparison issues in such huge graphs are a challenging research problem. In this paper, we survey the research advances of comparison problems in large graphs. We review graph comparison and pattern matching approaches that focus on large graphs. We categorize the existing approaches into three classes: partition-based approaches, search space based approaches and summary based approaches. All the existing algorithms in these approaches are described in detail and analyzed according to multiple metrics such as time complexity, type of graphs or comparison concept. Finally, we identify directions for future research.
The phase transition in random regular exact cover
Venue: arXiv cs.CC 2015
Year: 2015

A $k$-uniform, $d$-regular instance of Exact Cover is a family of $m$ sets $F_{n,d,k} = \{ S_j \subseteq \{1,...,n\} \}$, where each subset has size $k$ and each $1 \le i \le n$ is contained in $d$ of the $S_j$. It is satisfiable if there is a subset $T \subseteq \{1,...,n\}$ such that $|T \cap S_j|=1$ for all $j$. Alternately, we can consider it a $d$-regular instance of Positive 1-in-$k$ SAT, i.e., a Boolean formula with $m$ clauses and $n$ variables where each clause contains $k$ variables and demands that exactly one of them is true. We determine the satisfiability threshold for random instances of this type with $k > 2$. Letting $d^\star = \frac{\ln k}{(k-1)(- \ln (1-1/k))} + 1$, we show that $F_{n,d,k}$ is satisfiable with high probability if $d < d^\star$ and unsatisfiable with high probability if $d > d^\star$. We do this with a simple application of the first and second moment methods, boosting the probability of satisfiability below $d^\star$ to $1-o(1)$ using the small subgraph conditioning method.
Aspect-oriented linearizability proofs
Venue: arXiv cs.LO 2015
Year: 2015

Linearizability of concurrent data structures is usually proved by monolithic simulation arguments relying on the identification of the so-called linearization points. Regrettably, such proofs, whether manual or automatic, are often complicated and scale poorly to advanced non-blocking concurrency patterns, such as helping and optimistic updates. In response, we propose a more modular way of checking linearizability of concurrent queue algorithms that does not involve identifying linearization points. We reduce the task of proving linearizability with respect to the queue specification to establishing four basic properties, each of which can be proved independently by simpler arguments. As a demonstration of our approach, we verify the Herlihy and Wing queue, an algorithm that is challenging to verify by a simulation proof.