OpenRaiser/Intern-Atlas huggingface dataset:
A Modest Proposal: (Possible) Implications for Appropriation
Venue: arXiv cs.CY 2013
Year: 2013

As technologies are developed and constructed, designers may or may not be aware that they are embedding politics and values into their artifacts. Computer scientists operate and advance their field by building layers of abstraction into software and hardware to reduce the complexity of interfaces, making the artifacts they create zuhanden for others in part by imposing constraints. The increasing reliance of global populations and economies on communication mediated by many information and communications technologies (ICTs) transforms them from applications into communications infrastructure, elevating the importance of considering the values embodied in those infrastructures. I argue that the status quo bias and economic inertia of built-infrastructure requires a reevaluation of research in light of the de facto global technocracy to consider a nouveau social contract between infrastructural theorists, scientists, designers, and engineers and the current and future generations who will be constrained by that infrastructure as it is reified. The CHI community is uniquely situated to establish a norm of including a discussion of the implications of appropriation as first class topic in research output.
Discriminative Training: Learning to Describe Video with Sentences, from Video Described with Sentences
Venue: arXiv cs.CV 2013
Year: 2013

We present a method for learning word meanings from complex and realistic video clips by discriminatively training (DT) positive sentential labels against negative ones, and then use the trained word models to generate sentential descriptions for new video. This new work is inspired by recent work which adopts a maximum likelihood (ML) framework to address the same problem using only positive sentential labels. The new method, like the ML-based one, is able to automatically determine which words in the sentence correspond to which concepts in the video (i.e., ground words to meanings) in a weakly supervised fashion. While both DT and ML yield comparable results with sufficient training data, DT outperforms ML significantly with smaller training sets because it can exploit negative training labels to better constrain the learning problem.
Weight distribution of two classes of cyclic codes with respect to two distinct order elements
Venue: arXiv cs.IT 2013
Year: 2013

Cyclic codes are an interesting type of linear codes and have wide applications in communication and storage systems due to their efficient encoding and decoding algorithms. Cyclic codes have been studied for many years, but their weight distribution are known only for a few cases. In this paper, let $\Bbb F_r$ be an extension of a finite field $\Bbb F_q$ and $r=q^m$, we determine the weight distribution of the cyclic codes $\mathcal C=\{c(a, b): a, b \in \Bbb F_r\},$ $$c(a, b)=(\mbox {Tr}_{r/q}(ag_1^0+bg_2^0), \ldots, \mbox {Tr}_{r/q}(ag_1^{n-1}+bg_2^{n-1})), g_1, g_2\in \Bbb F_r,$$ in the following two cases: (1) $\ord(g_1)=n, n|r-1$ and $g_2=1$; (2) $\ord(g_1)=n$, $g_2=g_1^2$, $\ord(g_2)=\frac n 2$, $m=2$ and $\frac{2(r-1)}n|(q+1)$.
Variable and clause elimination for LTL satisfiability checking
Venue: arXiv cs.LO 2013
Year: 2013

We study preprocessing techniques for clause normal forms of LTL formulas. Applying the mechanism of labelled clauses enables us to reinterpret LTL satisfiability as a set of purely propositional problems and thus to transfer simplification ideas from SAT to LTL. We demonstrate this by adapting variable and clause elimination, a very effective preprocessing technique used by modern SAT solvers. Our experiments confirm that even in the temporal setting substantial reductions in formula size and subsequent decrease of solver runtime can be achieved.
A data mining approach using transaction patterns for card fraud detection
Venue: arXiv cs.CR 2013
Year: 2013

Credit and debit cards, rather than actual money, have become the universal payment means. With these cards, it has become possible to buy expensive items easily without an additional complex authentication procedure being conducted. However, card transaction features are targeted by criminals seeking to use a lost or stolen card and looking for a chance to replicate it. Accidents, whether caused by the negligence of users or not, that lead to a transaction being performed by a criminal rather than the authorized card user should be prevented. Therefore, card companies are providing their clients with a variety of policies and standards to cover this eventuality. Card companies must therefore be able to distinguish between the rightful user and illegal users according to these standards in order to minimize damage resulting from unauthorized transactions. However, there is a limit to applying the same fixed standards to all card users, since the transaction patterns of people differ and even individuals' transaction patterns may change frequently due to changes income and consumption preference. Therefore, when only a specific threshold is applied, it is difficult to distinguish a fraudulent card transaction from a legitimate one. In this paper, we present methods for learning the individual patterns of a card user's transaction amount and the region in which he or she uses the card, for a given period, and for determining whether the specified transaction is allowable in accordance with these learned user transaction patterns. Then, we classify legitimate transactions and fraudulent transactions by setting thresholds based on the learned individual patterns.
Expanding the expressive power of Monadic Second-Order logic on restricted graph classes
Venue: arXiv cs.DS 2013
Year: 2013

We combine integer linear programming and recent advances in Monadic Second-Order model checking to obtain two new algorithmic meta-theorems for graphs of bounded vertex-cover. The first shows that cardMSO1, an extension of the well-known Monadic Second-Order logic by the addition of cardinality constraints, can be solved in FPT time parameterized by vertex cover. The second meta-theorem shows that the MSO partitioning problems introduced by Rao can also be solved in FPT time with the same parameter. The significance of our contribution stems from the fact that these formalisms can describe problems which are W[1]-hard and even NP-hard on graphs of bounded tree-width. Additionally, our algorithms have only an elementary dependence on the parameter and formula. We also show that both results are easily extended from vertex cover to neighborhood diversity.
Creating a Relational Distributed Object Store
Venue: arXiv cs.DB 2013
Year: 2013

In and of itself, data storage has apparent business utility. But when we can convert data to information, the utility of stored data increases dramatically. It is the layering of relation atop the data mass that is the engine for such conversion. Frank relation amongst discrete objects sporadically ingested is rare, making the process of synthesizing such relation all the more challenging, but the challenge must be met if we are ever to see an equivalent business value for unstructured data as we already have with structured data. This paper describes a novel construct, referred to as a relational distributed object store (RDOS), that seeks to solve the twin problems of how to persistently and reliably store petabytes of unstructured data while simultaneously creating and persisting relations amongst billions of objects.
An Algorithm for Constructing a Smallest Register with Non-Linear Update Generating a Given Binary Sequence
Venue: arXiv cs.IT 2013
Year: 2013

Registers with Non-Linear Update (RNLUs) are a generalization of Non-Linear Feedback Shift Registers (NLFSRs) in which both, feedback and feedforward, connections are allowed and no chain connection between the stages is required. In this paper, a new algorithm for constructing RNLUs generating a given binary sequence is presented. Expected size of RNLUs constructed by the presented algorithm is proved to be O(n/log(n/p)), where n is the sequence length and p is the degree of parallelization. This is asymptotically smaller than the expected size of RNLUs constructed by previous algorithms and the expected size of LFSRs and NLFSRs generating the same sequence. The presented algorithm can potentially be useful for many applications, including testing, wireless communications, and cryptography.
OMG: How Much Should I Pay Bob in Truthful Online Mobile Crowdsourced Sensing?
Venue: arXiv cs.GT 2013
Year: 2013

Mobile crowdsourced sensing (MCS) is a new paradigm which takes advantage of the pervasive smartphones to efficiently collect data, enabling numerous novel applications. To achieve good service quality for a MCS application, incentive mechanisms are necessary to attract more user participation. Most of existing mechanisms apply only for the offline scenario where all users' information are known a priori. On the contrary, we focus on a more real scenario where users arrive one by one online in a random order. We model the problem as an online auction in which the users submit their private types to the crowdsourcer over time, and the crowdsourcer aims to select a subset of users before a specified deadline for maximizing the total value of the services provided by selected users under a budget constraint. We design two online mechanisms, OMZ and OMG, satisfying the computational efficiency, individual rationality, budget feasibility, truthfulness, consumer sovereignty and constant competitiveness under the zero arrival-departure interval case and a more general case, respectively. Through extensive simulations, we evaluate the performance and validate the theoretical properties of our online mechanisms.
A Temporal Logic of Security
Venue: arXiv cs.LO 2013
Year: 2013

A new logic for verification of security policies is proposed. The logic, HyperLTL, extends linear-time temporal logic (LTL) with connectives for explicit and simultaneous quantification over multiple execution paths, thereby enabling HyperLTL to express information-flow security policies that LTL cannot. A model-checking algorithm for a fragment of HyperLTL is given, and the algorithm is implemented in a prototype model checker. The class of security policies expressible in HyperLTL is characterized by an arithmetic hierarchy of hyperproperties.
Two-Part Reconstruction in Compressed Sensing
Venue: arXiv cs.IT 2013
Year: 2013

Two-part reconstruction is a framework for signal recovery in compressed sensing (CS), in which the advantages of two different algorithms are combined. Our framework allows to accelerate the reconstruction procedure without compromising the reconstruction quality. To illustrate the efficacy of our two-part approach, we extend the author's previous Sudocodes algorithm and make it robust to measurement noise. In a 1-bit CS setting, promising numerical results indicate that our algorithm offers both a reduction in run-time and improvement in reconstruction quality.
Distributed Heuristic Forward Search for Multi-Agent Systems
Venue: arXiv cs.AI 2013
Year: 2013

This paper describes a number of distributed forward search algorithms for solving multi-agent planning problems. We introduce a distributed formulation of non-optimal forward search, as well as an optimal version, MAD-A*. Our algorithms exploit the structure of multi-agent problems to not only distribute the work efficiently among different agents, but also to remove symmetries and reduce the overall workload. The algorithms ensure that private information is not shared among agents, yet computation is still efficient -- outperforming current state-of-the-art distributed planners, and in some cases even centralized search -- despite the fact that each agent has access only to partial information.
A Grammatical Inference Approach to Language-Based Anomaly Detection in XML
Venue: arXiv cs.CR 2013
Year: 2013

False-positives are a problem in anomaly-based intrusion detection systems. To counter this issue, we discuss anomaly detection for the eXtensible Markup Language (XML) in a language-theoretic view. We argue that many XML-based attacks target the syntactic level, i.e. the tree structure or element content, and syntax validation of XML documents reduces the attack surface. XML offers so-called schemas for validation, but in real world, schemas are often unavailable, ignored or too general. In this work-in-progress paper we describe a grammatical inference approach to learn an automaton from example XML documents for detecting documents with anomalous syntax. We discuss properties and expressiveness of XML to understand limits of learnability. Our contributions are an XML Schema compatible lexical datatype system to abstract content in XML and an algorithm to learn visibly pushdown automata (VPA) directly from a set of examples. The proposed algorithm does not require the tree representation of XML, so it can process large documents or streams. The resulting deterministic VPA then allows stream validation of documents to recognize deviations in the underlying tree structure or datatypes.
Throughput and Energy Efficiency Analysis of Small Cell Networks with Multi-antenna Base Stations
Venue: arXiv cs.IT 2013
Year: 2013

Small cell networks have recently been proposed as an important evolution path for the next-generation cellular networks. However, with more and more irregularly deployed base stations (BSs), it is becoming increasingly difficult to quantify the achievable network throughput or energy efficiency. In this paper, we develop an analytical framework for downlink performance evaluation of small cell networks, based on a random spatial network model, where BSs and users are modeled as two independent spatial Poisson point processes. A new simple expression of the outage probability is derived, which is analytically tractable and is especially useful with multi-antenna transmissions. This new result is then applied to evaluate the network throughput and energy efficiency. It is analytically shown that deploying more BSs or more BS antennas can always increase the network throughput, but the performance gain critically depends on the BS-user density ratio and the number of BS antennas. On the other hand, increasing the BS density or the number of transmit antennas will first increase and then decrease the energy efficiency if different components of BS power consumption satisfy certain conditions, and the optimal BS density and the optimal number of BS antennas can be found. Otherwise, the energy efficiency will always decrease. Simulation results shall demonstrate that our conclusions based on the random network model are general and also hold in a regular grid-based model.
Emergent Behavior in Multipartite Large Networks: Multi-virus Epidemics
Venue: arXiv cs.SI 2013
Year: 2013

Epidemics in large complete networks is well established. In contrast, we consider epidemics in non-complete networks. We establish the fluid limit macroscopic dynamics of a multi-virus spread over a multipartite network as the number of nodes at each partite or island grows large. The virus spread follows a peer-to-peer random rule of infection in line with the Harris contact process. The model conforms to an SIS (susceptible-infected-susceptible) type, where a node is either infected or it is healthy and prone to be infected. The local (at node level) random infection model induces the emergence of structured dynamics at the macroscale. Namely, we prove that, as the multipartite network grows large, the normalized Markov jump vector process $\left(\bar{\mathbf{Y}}^\mathbf{N}(t)\right) = \left(\bar{Y}_1^\mathbf{N}(t),\ldots, \bar{Y}_M^\mathbf{N}(t)\right)$ collecting the fraction of infected nodes at each island $i=1,\ldots,M$, converges weakly (with respect to the Skorokhod topology on the space of \emph{càdlàg} sample paths) to the solution of an $M$-dimensional vector nonlinear coupled ordinary differential equation. In the case of multi-virus diffusion with $K\in\mathbb{N}$ distinct strains of virus, the Markov jurmp matrix process $\left(\bar{\mathbf{Y}}^\mathbf{N}(t)\right)$, stacking the fraction of nodes infected with virus type $j$, $j=1,\ldots,K$, at each island $i=1,\ldots,M$, converges weakly as well to the solution of a $\left(K\times M\right)$-dimensional vector differential equation that is also characterized.
Towards Secure Two-Party Computation from the Wire-Tap Channel
Venue: arXiv cs.CR 2013
Year: 2013

We introduce a new protocol for secure two-party computation of linear functions in the semi-honest model, based on coding techniques. We first establish a parallel between the second version of the wire-tap channel model and secure two-party computation. This leads us to our protocol, that combines linear coset coding and oblivious transfer techniques. Our construction requires the use of binary intersecting codes or $q$-ary minimal codes, which are also studied in this paper.
Playing cooperatively with possibly treacherous partner
Venue: arXiv cs.GT 2013
Year: 2013

We investigate an alternative concept of Nash equilibrium, m-equilibrium, which slightly resembles Harsanyi-Selten risk dominant equilibrium although it is a different notion. M-equilibria provide nontrivial solutions of normal form games as shown by comparison of the Prisoner's Dilemma with the Traveler's Dilemma. They are also resistant on the deep iterated elimination of dominated strategies.
Forecasting and Event Detection in Internet Resource Dynamics using Time Series Models
Venue: arXiv cs.NI 2013
Year: 2013

At present Internet has emerged as a country's predominant and viable data communication infrastructure. The Autonomous System (AS) resources which are building blocks of the Internet are AS numbers, IPv4 and IPv6 Prefixes. AS number growth is one of Internet infrastructure development indicators. Hence understanding on long term trend and stochastic variation behaviour are essential to detect significant events during the growth. In this work, time series based approximation is considered for mathematical modelling and forecast the yearly AS growth. The AS data of five countries namely India, China, Japan, South Korea and Taiwan are extracted from APNIC archive. ARIMA models with different Auto Regressive and Moving Average parameters are identified for forecasting. Model validation, parameter estimation, point forecast and prediction intervals with 95 % confidence levels for the five countries are reported in the paper. The significant level change in variations, positive growth percentage in Inter Annual Absolute Variations (IAAV) and higher percentage of advertised ASes when compared to other countries indicate India's fast growth and wider global reachability of Internet infrastructure from 2007 onwards. The correlation between IAAV change point and GDP growth period indicates that service sector industry growth is the driving force behind significant yearly changes.
Internet Control Plane Event Identification using Model Based Change Point Detection Techniques
Venue: arXiv cs.NI 2013
Year: 2013

In the raise of many global organizations deploying their data centers and content services in India, the prefix reachability performance study from global destinations garners our attention. The events such as failures and attacks occurring in the Internet topology have impact on Autonomous System (AS) paths announced in the control plane and reachability of prefixes from spatially distributed ASes. As a consequence the customer reachability to the services in terms of increased latency and outages for a short or long time are experienced. The challenge in control plane event detection is when the data plane traffic is able to reach the intended destinations correctly. However detection of such events are crucial for the operations of content and data center industries. By monitoring the spatially distributed routing table features like AS path length distributions, spatial prefix reachability distribution and covering to overlap route ratio, we can detect the control plane events. In our work, we study prefix AS paths from the publicly available route-view data and analyze the global reachability as well as reachability to Indian AS topology. To capture the spatial events in a single temporal pattern, we propose a counting based measure using prefixes announced by x % of spatial peers. Employing statistical characteristics change point detection and temporal aberration algorithm on the time series of the proposed measure, we identify the occurrence of long and stochastic control plane events. The impact and duration of the events are also quantified. We validate the mechanisms over the proposed measure using the SEA-Me-We4 cable cut event manifestations in the control plane of Indian AS topology. The cable cut events occurred on 6th June 2012 (long term event) and 17th April 2012 (stochastic event) are considered for validation.
Next generation input-output data format for HEP using Google's protocol buffers
Venue: arXiv cs.CE 2013
Year: 2013

We propose a data format for Monte Carlo (MC) events, or any structural data, including experimental data, in a compact binary form using variable-size integer encoding as implemented in the Google's Protocol Buffers package. This approach is implemented in the so-called ProMC library which produces smaller file sizes for MC records compared to the existing input-output libraries used in high-energy physics (HEP). Other important features are a separation of abstract data layouts from concrete programming implementations, self-description and random access. Data stored in ProMC files can be written, read and manipulated in a number of programming languages, such C++, Java and Python.
Arabizi Detection and Conversion to Arabic
Venue: arXiv cs.CL 2013
Year: 2013

Arabizi is Arabic text that is written using Latin characters. Arabizi is used to present both Modern Standard Arabic (MSA) or Arabic dialects. It is commonly used in informal settings such as social networking sites and is often with mixed with English. In this paper we address the problems of: identifying Arabizi in text and converting it to Arabic characters. We used word and sequence-level features to identify Arabizi that is mixed with English. We achieved an identification accuracy of 98.5%. As for conversion, we used transliteration mining with language modeling to generate equivalent Arabic text. We achieved 88.7% conversion accuracy, with roughly a third of errors being spelling and morphological variants of the forms in ground truth.
Social Network Intelligence Analysis to Combat Street Gang Violence
Venue: arXiv cs.SI 2013
Year: 2013

In this paper we introduce the Organization, Relationship, and Contact Analyzer (ORCA) that is designed to aide intelligence analysis for law enforcement operations against violent street gangs. ORCA is designed to address several police analytical needs concerning street gangs using new techniques in social network analysis. Specifically, it can determine "degree of membership" for individuals who do not admit to membership in a street gang, quickly identify sets of influential individuals (under the tipping model), and identify criminal ecosystems by decomposing gangs into sub-groups. We describe this software and the design decisions considered in building an intelligence analysis tool created specifically for countering violent street gangs as well as provide results based on conducting analysis on real-world police data provided by a major American metropolitan police department who is partnering with us and currently deploying this system for real-world use.