OpenRaiser/Intern-Atlas huggingface dataset:
CUR Algorithm with Incomplete Matrix Observation
Venue: arXiv cs.LG 2014
Year: 2014

CUR matrix decomposition is a randomized algorithm that can efficiently compute the low rank approximation for a given rectangle matrix. One limitation with the existing CUR algorithms is that they require an access to the full matrix A for computing U. In this work, we aim to alleviate this limitation. In particular, we assume that besides having an access to randomly sampled d rows and d columns from A, we only observe a subset of randomly sampled entries from A. Our goal is to develop a low rank approximation algorithm, similar to CUR, based on (i) randomly sampled rows and columns from A, and (ii) randomly sampled entries from A. The proposed algorithm is able to perfectly recover the target matrix A with only O(rn log n) number of observed entries. In addition, instead of having to solve an optimization problem involved trace norm regularization, the proposed algorithm only needs to solve a standard regression problem. Finally, unlike most matrix completion theories that hold only when the target matrix is of low rank, we show a strong guarantee for the proposed algorithm even when the target matrix is not low rank.
A Novel Method to Calculate Click Through Rate for Sponsored Search
Venue: arXiv cs.IR 2014
Year: 2014

Sponsored search adopts generalized second price (GSP) auction mechanism which works on the concept of pay per click which is most commonly used for the allocation of slots in the searched page. Two main aspects associated with GSP are the bidding amount and the click through rate (CTR). The CTR learning algorithms currently being used works on the basic principle of (#clicks_i/ #impressions_i) under a fixed window of clicks or impressions or time. CTR are prone to fraudulent clicks, resulting in sudden increase of CTR. The current algorithms are unable to find the solutions to stop this, although with the use of machine learning algorithms it can be detected that fraudulent clicks are being generated. In our paper, we have used the concept of relative ranking which works on the basic principle of (#clicks_i /#clicks_t). In this algorithm, both the numerator and the denominator are linked. As #clicks_t is higher than previous algorithms and is linked to the #clicks_i, the small change in the clicks which occurs in the normal scenario have a very small change in the result but in case of fraudulent clicks the number of clicks increases or decreases rapidly which will add up with the normal clicks to increase the denominator, thereby decreasing the CTR.
Parallel Implementations of the Jacobi Linear Algebraic Systems Solve
Venue: arXiv cs.DC 2014
Year: 2014

The objective of this research is to construct parallel implementations of the Jacobi algorithm used for the solution of linear algebraic systems, to measure their speedup with respect to the serial case and to compare each other, regarding their efficiency. The programming paradigm used in this implementation is the message passing model, while, the used MPI implementation is the MPICH implementation of the Argonne National Laboratory.
The Mason Test: A Defense Against Sybil Attacks in Wireless Networks Without Trusted Authorities
Venue: arXiv cs.CR 2014
Year: 2014

Wireless networks are vulnerable to Sybil attacks, in which a malicious node poses as many identities in order to gain disproportionate influence. Many defenses based on spatial variability of wireless channels exist, but depend either on detailed, multi-tap channel estimation - something not exposed on commodity 802.11 devices - or valid RSSI observations from multiple trusted sources, e.g., corporate access points - something not directly available in ad hoc and delay-tolerant networks with potentially malicious neighbors. We extend these techniques to be practical for wireless ad hoc networks of commodity 802.11 devices. Specifically, we propose two efficient methods for separating the valid RSSI observations of behaving nodes from those falsified by malicious participants. Further, we note that prior signalprint methods are easily defeated by mobile attackers and develop an appropriate challenge-response defense. Finally, we present the Mason test, the first implementation of these techniques for ad hoc and delay-tolerant networks of commodity 802.11 devices. We illustrate its performance in several real-world scenarios.
Viewing the Welch bound inequality from the kernel trick viewpoint
Venue: arXiv cs.IT 2014
Year: 2014

This brief note views to the Welch bound inequality using the idea of the kernel trick from the machine learning research area. From this angle, some novel insights of the inequality are obtained.
Metadata for Energy Disaggregation
Venue: arXiv cs.DB 2014
Year: 2014

Energy disaggregation is the process of estimating the energy consumed by individual electrical appliances given only a time series of the whole-home power demand. Energy disaggregation researchers require datasets of the power demand from individual appliances and the whole-home power demand. Multiple such datasets have been released over the last few years but provide metadata in a disparate array of formats including CSV files and plain-text README files. At best, the lack of a standard metadata schema makes it unnecessarily time-consuming to write software to process multiple datasets and, at worse, the lack of a standard means that crucial information is simply absent from some datasets. We propose a metadata schema for representing appliances, meters, buildings, datasets, prior knowledge about appliances and appliance models. The schema is relational and provides a simple but powerful inheritance mechanism.
Adaptive MCMC-Based Inference in Probabilistic Logic Programs
Venue: arXiv cs.AI 2014
Year: 2014

Probabilistic Logic Programming (PLP) languages enable programmers to specify systems that combine logical models with statistical knowledge. The inference problem, to determine the probability of query answers in PLP, is intractable in general, thereby motivating the need for approximate techniques. In this paper, we present a technique for approximate inference of conditional probabilities for PLP queries. It is an Adaptive Markov Chain Monte Carlo (MCMC) technique, where the distribution from which samples are drawn is modified as the Markov Chain is explored. In particular, the distribution is progressively modified to increase the likelihood that a generated sample is consistent with evidence. In our context, each sample is uniquely characterized by the outcomes of a set of random variables. Inspired by reinforcement learning, our technique propagates rewards to random variable/outcome pairs used in a sample based on whether the sample was consistent or not. The cumulative rewards of each outcome is used to derive a new "adapted distribution" for each random variable. For a sequence of samples, the distributions are progressively adapted after each sample. For a query with "Markovian evaluation structure", we show that the adapted distribution of samples converges to the query's conditional probability distribution. For Markovian queries, we present a modified adaptation process that can be used in adaptive MCMC as well as adaptive independent sampling. We empirically evaluate the effectiveness of the adaptive sampling methods for queries with and without Markovian evaluation structure.
Exact correct-decoding exponent of the wiretap channel decoder
Venue: arXiv cs.IT 2014
Year: 2014

The security level of the achievability scheme for Wyner's wiretap channel model is examined from the perspective of the probability of correct decoding, $P_c$, at the wiretap channel decoder. In particular, for finite-alphabet memoryless channels, the exact random coding exponent of $P_c$ is derived as a function of the total coding rate $R_1$ and the rate of each sub-code $R_2$. Two different representations are given for this function and its basic properties are provided. We also characterize the region of pairs of rates $(R_1,R_2)$ of full security in the sense of the random coding exponent of $P_c$, in other words, the region where the exponent of this achievability scheme is the same as that of blind guessing at the eavesdropper side. Finally, an analogous derivation of the correct-decoding exponent is outlined for the case of the Gaussian channel.
Predicting Successful Memes using Network and Community Structure
Venue: arXiv cs.SI 2014
Year: 2014

We investigate the predictability of successful memes using their early spreading patterns in the underlying social networks. We propose and analyze a comprehensive set of features and develop an accurate model to predict future popularity of a meme given its early spreading patterns. Our paper provides the first comprehensive comparison of existing predictive frameworks. We categorize our features into three groups: influence of early adopters, community concentration, and characteristics of adoption time series. We find that features based on community structure are the most powerful predictors of future success. We also find that early popularity of a meme is not a good predictor of its future popularity, contrary to common belief. Our methods outperform other approaches, particularly in the task of detecting very popular or unpopular memes.
K-Position, Follow, Equation and K-C-Continuation Tree Automata Constructions
Venue: arXiv cs.FL 2014
Year: 2014

There exist several methods of computing an automaton recognizing the language denoted by a given regular expression: In the case of words, the position automaton P due to Glushkov, the c-continuation automaton C due to Champarnaud and Ziadi, the follow automaton F due to Ilie and Yu and the equation automaton E due to Antimirov. It has been shown that P and C are isomorphic and that E (resp. F) is a quotient of C (resp. of P). In this paper, we define from a given regular tree expression the k-position tree automaton P and the follow tree automaton F . Using the definition of the equation tree automaton E of Kuske and Meinecke and our previously defined k-C-continuation tree automaton C, we show that the previous morphic relations are still valid on tree expressions.
On the Excess Bandwidth Allocation in ISP Traffic Control for Shared Access Networks
Venue: arXiv cs.NI 2014
Year: 2014

Current practice of shaping subscriber traffic based on token bucket by Internet service provider (ISP) allows short-term fluctuations in its shaped rate and thereby enables a subscriber to transmit traffic at a higher rate than a negotiated long-term average. The traffic shaping, however, results in significant waste of network resources, especially when there are only a few active subscribers, because it cannot allocate excess bandwidth to active subscribers in the long term. In this letter we investigate the long-term aspect of resource sharing in ISP traffic control for shared access networks. We discuss major requirements for the excess bandwidth allocation in shared access networks and propose ISP traffic control schemes based on core-stateless fair queueing (CSFQ) and token bucket meters. Simulation results demonstrate that the proposed schemes allocate excess bandwidth among active subscribers in a fair and efficient way, while not compromising the service contracts specified by token bucket for conformant subscribers.
On the Computational Complexity of Vertex Integrity and Component Order Connectivity
Venue: arXiv cs.DS 2014
Year: 2014

The Weighted Vertex Integrity (wVI) problem takes as input an $n$-vertex graph $G$, a weight function $w:V(G)\to\mathbb{N}$, and an integer $p$. The task is to decide if there exists a set $X\subseteq V(G)$ such that the weight of $X$ plus the weight of a heaviest component of $G-X$ is at most $p$. Among other results, we prove that: (1) wVI is NP-complete on co-comparability graphs, even if each vertex has weight $1$; (2) wVI can be solved in $O(p^{p+1}n)$ time; (3) wVI admits a kernel with at most $p^3$ vertices. Result (1) refutes a conjecture by Ray and Deogun and answers an open question by Ray et al. It also complements a result by Kratsch et al., stating that the unweighted version of the problem can be solved in polynomial time on co-comparability graphs of bounded dimension, provided that an intersection model of the input graph is given as part of the input. An instance of the Weighted Component Order Connectivity (wCOC) problem consists of an $n$-vertex graph $G$, a weight function $w:V(G)\to \mathbb{N}$, and two integers $k$ and $l$, and the task is to decide if there exists a set $X\subseteq V(G)$ such that the weight of $X$ is at most $k$ and the weight of a heaviest component of $G-X$ is at most $l$. In some sense, the wCOC problem can be seen as a refined version of the wVI problem. We prove, among other results, that: (4) wCOC can be solved in $O(\min\{k,l\}\cdot n^3)$ time on interval graphs, while the unweighted version can be solved in $O(n^2)$ time on this graph class; (5) wCOC is W[1]-hard on split graphs when parameterized by $k$ or by $l$; (6) wCOC can be solved in $2^{O(k\log l)} n$ time; (7) wCOC admits a kernel with at most $kl(k+l)+k$ vertices. We also show that result (6) is essentially tight by proving that wCOC cannot be solved in $2^{o(k \log l)}n^{O(1)}$ time, unless the ETH fails.
Knightian Analysis of the VCG Mechanism in Unrestricted Combinatorial Auctions
Venue: arXiv cs.GT 2014
Year: 2014

We consider auctions in which the players have very limited knowledge about their own valuations. Specifically, the only information that a Knightian player $i$ has about the profile of true valuations, $θ^*$, consists of a set of distributions, from one of which $θ_i^*$ has been drawn. The VCG mechanism guarantees very high social welfare both in single- and multi-good auctions, so long as Knightian players do not select strategies that are dominated. With such Knightian players, however, we prove that the VCG mechanism guarantees very poor social welfare in unrestricted combinatorial auctions.
Languages of lossless seeds
Venue: arXiv cs.DM 2014
Year: 2014

Several algorithms for similarity search employ seeding techniques to quickly discard very dissimilar regions. In this paper, we study theoretical properties of lossless seeds, i.e., spaced seeds having full sensitivity. We prove that lossless seeds coincide with languages of certain sofic subshifts, hence they can be recognized by finite automata. Moreover, we show that these subshifts are fully given by the number of allowed errors k and the seed margin l. We also show that for a fixed k, optimal seeds must asymptotically satisfy l ~ m^(k/(k+1)).
Havannah and TwixT are PSPACE-complete
Venue: arXiv cs.CC 2014
Year: 2014

Numerous popular abstract strategy games ranging from Hex and Havannah to Lines of Action belong to the class of connection games. Still, very few complexity results on such games have been obtained since Hex was proved PSPACE-complete in the early eighties. We study the complexity of two connection games among the most widely played. Namely, we prove that Havannah and TwixT are PSPACE-complete. The proof for Havannah involves a reduction from Generalized Geography and is based solely on ring-threats to represent the input graph. On the other hand, the reduction for TwixT builds up on previous work as it is a straightforward encoding of Hex.
On Equivalence of Infinitary Formulas under the Stable Model Semantics
Venue: arXiv cs.LO 2014
Year: 2014

Propositional formulas that are equivalent in intuitionistic logic, or in its extension known as the logic of here-and-there, have the same stable models. We extend this theorem to propositional formulas with infinitely long conjunctions and disjunctions and show how to apply this generalization to proving properties of aggregates in answer set programming. To appear in Theory and Practice of Logic Programming (TPLP).
Towards the Asymptotic Sum Capacity of the MIMO Cellular Two-Way Relay Channel
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we consider the transceiver and relay design for multiple-input multiple-output (MIMO) cellular two-way relay channel (cTWRC), where a multi-antenna base station (BS) exchanges information with multiple multi-antenna mobile stations via a multi-antenna relay station (RS). We propose a novel two-way relaying scheme to approach the sum capacity of the MIMO cTWRC.
Facility Location in Evolving Metrics
Venue: arXiv cs.SI 2014
Year: 2014

Understanding the dynamics of evolving social or infrastructure networks is a challenge in applied areas such as epidemiology, viral marketing, or urban planning. During the past decade, data has been collected on such networks but has yet to be fully analyzed. We propose to use information on the dynamics of the data to find stable partitions of the network into groups. For that purpose, we introduce a time-dependent, dynamic version of the facility location problem, that includes a switching cost when a client's assignment changes from one facility to another. This might provide a better representation of an evolving network, emphasizing the abrupt change of relationships between subjects rather than the continuous evolution of the underlying network. We show that in realistic examples this model yields indeed better fitting solutions than optimizing every snapshot independently. We present an $O(\log nT)$-approximation algorithm and a matching hardness result, where $n$ is the number of clients and $T$ the number of time steps. We also give an other algorithms with approximation ratio $O(\log nT)$ for the variant where one pays at each time step (leasing) for each open facility.
KPCA Spatio-temporal trajectory point cloud classifier for recognizing human actions in a CBVR system
Venue: arXiv cs.IR 2014
Year: 2014

We describe a content based video retrieval (CBVR) software system for identifying specific locations of a human action within a full length film, and retrieving similar video shots from a query. For this, we introduce the concept of a trajectory point cloud for classifying unique actions, encoded in a spatio-temporal covariant eigenspace, where each point is characterized by its spatial location, local Frenet-Serret vector basis, time averaged curvature and torsion and the mean osculating hyperplane. Since each action can be distinguished by their unique trajectories within this space, the trajectory point cloud is used to define an adaptive distance metric for classifying queries against stored actions. Depending upon the distance to other trajectories, the distance metric uses either large scale structure of the trajectory point cloud, such as the mean distance between cloud centroids or the difference in hyperplane orientation, or small structure such as the time averaged curvature and torsion, to classify individual points in a fuzzy-KNN. Our system can function in real-time and has an accuracy greater than 93% for multiple action recognition within video repositories. We demonstrate the use of our CBVR system in two situations: by locating specific frame positions of trained actions in two full featured films, and video shot retrieval from a database with a web search application.
Relational Mathematics Continued
Venue: arXiv cs.DM 2014
Year: 2014

This is in some sense an addendum to the book Relational Mathematics by the first-named author. It originated from work on diverse other topics during which a lot of purely relational results with broad applicability have been produced. These include results on domain construction with novel formulae for existential and inverse image, a relational calculus for binary mappings, and the development of a formally derived relational calculus of Kronecker-, strict fork-, and strict join-operators. The many visualizations in this report make it also a scrap- and picture book for examples.
LINVIEW: Incremental View Maintenance for Complex Analytical Queries
Venue: arXiv cs.DB 2014
Year: 2014

Many analytics tasks and machine learning problems can be naturally expressed by iterative linear algebra programs. In this paper, we study the incremental view maintenance problem for such complex analytical queries. We develop a framework, called LINVIEW, for capturing deltas of linear algebra programs and understanding their computational cost. Linear algebra operations tend to cause an avalanche effect where even very local changes to the input matrices spread out and infect all of the intermediate results and the final view, causing incremental view maintenance to lose its performance benefit over re-evaluation. We develop techniques based on matrix factorizations to contain such epidemics of change. As a consequence, our techniques make incremental view maintenance of linear algebra practical and usually substantially cheaper than re-evaluation. We show, both analytically and experimentally, the usefulness of these techniques when applied to standard analytics tasks. Our evaluation demonstrates the efficiency of LINVIEW in generating parallel incremental programs that outperform re-evaluation techniques by more than an order of magnitude.
A Fast Minimal Infrequent Itemset Mining Algorithm
Venue: arXiv cs.DB 2014
Year: 2014

A novel fast algorithm for finding quasi identifiers in large datasets is presented. Performance measurements on a broad range of datasets demonstrate substantial reductions in run-time relative to the state of the art and the scalability of the algorithm to realistically-sized datasets up to several million records.
Building Secure and Anonymous Communication Channel: Formal Model and its Prototype Implementation
Venue: arXiv cs.NI 2014
Year: 2014

Various techniques need to be combined to realize anonymously authenticated communication. Cryptographic tools enable anonymous user authentication while anonymous communication protocols hide users' IP addresses from service providers. One simple approach for realizing anonymously authenticated communication is their simple combination, but this gives rise to another issue; how to build a secure channel. The current public key infrastructure cannot be used since the user's public key identifies the user. To cope with this issue, we propose a protocol that uses identity-based encryption for packet encryption without sacrificing anonymity, and group signature for anonymous user authentication. Communications in the protocol take place through proxy entities that conceal users' IP addresses from service providers. The underlying group signature is customized to meet our objective and improve its efficiency. We also introduce a proof-of-concept implementation to demonstrate the protocol's feasibility. We compare its performance to SSL communication and demonstrate its practicality, and conclude that the protocol realizes secure, anonymous, and authenticated communication between users and service providers with practical performance.
Information Retrieval (IR) through Semantic Web (SW): An Overview
Venue: arXiv cs.IR 2014
Year: 2014

A large amount of data is present on the web. It contains huge number of web pages and to find suitable information from them is very cumbersome task. There is need to organize data in formal manner so that user can easily access and use them. To retrieve information from documents, we have many Information Retrieval (IR) techniques. Current IR techniques are not so advanced that they can be able to exploit semantic knowledge within documents and give precise results. IR technology is major factor responsible for handling annotations in Semantic Web (SW) languages and in the present paper knowledgeable representation languages used for retrieving information are discussed.