OpenRaiser/Intern-Atlas huggingface dataset:
Panel dataset description for econometric analysis of the ISP-OTT relationship in the years 2008-2013
Venue: arXiv cs.NI 2016
Year: 2016

The latest technological advancements in the telecommunications domain (e.g., widespread adoption of mobile devices, introduction of 5G wireless communications, etc.) have brought new stakeholders into the spotlight. More specifically, Over-the-Top (OTT) providers have recently appeared, offering their services over the existing deployed telecommunication networks. The entry of the new players has changed the dynamics in the domain, as it creates conflicting situations with the Internet Service Providers (ISPs), who traditionally dominate the area, motivating the necessity for novel analytical studies for this relationship. However, despite the importance of accessing real observational data, there is no database with the aggregate information that can serve as a solid base for this research. To that end, this document provides a detailed summary report for financial and statistic data for the period 2008-2013 that can be exploited for realistic econometric models that will provide useful insights on this topic. The document summarizes data from various sources with regard to the ISP revenues and Capital Expenditures (CAPEX), the OTT revenues, the Internet penetration and the Gross Domestic Product (GDP), taking into account three big OTT providers (i.e., Facebook, Skype, WhatsApp) and ten major ISPs that operate in seven different countries.
Stateology: State-Level Interactive Charting of Language, Feelings, and Values
Venue: arXiv cs.CL 2016
Year: 2016

People's personality and motivations are manifest in their everyday language usage. With the emergence of social media, ample examples of such usage are procurable. In this paper, we aim to analyze the vocabulary used by close to 200,000 Blogger users in the U.S. with the purpose of geographically portraying various demographic, linguistic, and psychological dimensions at the state level. We give a description of a web-based tool for viewing maps that depict various characteristics of the social media users as derived from this large blog dataset of over two billion words.
CannyFS: Opportunistically Maximizing I/O Throughput Exploiting the Transactional Nature of Batch-Mode Data Processing
Venue: arXiv cs.OS 2016
Year: 2016

We introduce a user mode file system, CannyFS, that hides latency by assuming all I/O operations will succeed. The user mode process will in turn report errors, allowing proper cleanup and a repeated attempt to take place. We demonstrate benefits for the model tasks of extracting archives and removing directory trees in a real-life HPC environment, giving typical reductions in time use of over 80%. This approach can be considered a view of HPC jobs and their I/O activity as transactions. In general, file systems lack clearly defined transaction semantics. Over time, the competing trends to add cache and maintain data integrity have resulted in different practical tradeoffs. High-performance computing is a special case where overall throughput demands are high. Latency can also be high, with non-local storage. In addition, a theoretically possible I/O error (like permission denied, loss of connection, exceeding disk quota) will frequently warrant the resubmission of a full job or task, rather than traditional error reporting or handling. Therefore, opportunistically treating each I/O operation as successful, and part of a larger transaction, can speed up some applications that do not leverage asynchronous I/O.
A Statistical Approach to Continuous Self-Calibrating Eye Gaze Tracking for Head-Mounted Virtual Reality Systems
Venue: arXiv cs.CV 2016
Year: 2016

We present a novel, automatic eye gaze tracking scheme inspired by smooth pursuit eye motion while playing mobile games or watching virtual reality contents. Our algorithm continuously calibrates an eye tracking system for a head mounted display. This eliminates the need for an explicit calibration step and automatically compensates for small movements of the headset with respect to the head. The algorithm finds correspondences between corneal motion and screen space motion, and uses these to generate Gaussian Process Regression models. A combination of those models provides a continuous mapping from corneal position to screen space position. Accuracy is nearly as good as achieved with an explicit calibration step.
Trilaminar Multiway Reconstruction Tree for Efficient Large Scale Structure from Motion
Venue: arXiv cs.CV 2016
Year: 2016

Accuracy and efficiency are two key problems in large scale incremental Structure from Motion (SfM). In this paper, we propose a unified framework to divide the image set into clusters suitable for reconstruction as well as find multiple reliable and stable starting points. Image partitioning performs in two steps. First, some small image groups are selected at places with high image density, and then all the images are clustered according to their optimal reconstruction paths to these image groups. This promises that the scene is always reconstructed from dense places to sparse areas, which can reduce error accumulation when images have weak overlap. To enable faster speed, images outside the selected group in each cluster are further divided to achieve a greater degree of parallelism. Experiments show that our method achieves significant speedup, higher accuracy and better completeness.
Pseudo Sequence based 2-D hierarchical reference structure for Light-Field Image Compression
Venue: arXiv cs.MM 2016
Year: 2016

In this paper, we present a novel pseudo sequence based 2-D hierarchical reference structure for light-field image compression. In the proposed scheme, we first decompose the light-field image into multiple views and organize them into a 2-D coding structure according to the spatial coordinates of the corresponding microlens. Then we mainly develop three technologies to optimize the 2-D coding structure. First, we divide all the views into four quadrants, and all the views are encoded one quadrant after another to reduce the reference buffer size as much as possible. Inside each quadrant, all the views are encoded hierarchically to fully exploit the correlations between different views. Second, we propose to use the distance between the current view and its reference views as the criteria for selecting better reference frames for each inter view. Third, we propose to use the spatial relative positions between different views to achieve more accurate motion vector scaling. The whole scheme is implemented in the reference software of High Efficiency Video Coding. The experimental results demonstrate that the proposed novel pseudo-sequence based 2-D hierarchical structure can achieve maximum 14.2% bit-rate savings compared with the state-of-the-art light-field image compression method.
Practical linear-space Approximate Near Neighbors in high dimension
Venue: arXiv cs.CG 2016
Year: 2016

The $c$-approximate Near Neighbor problem in high dimensional spaces has been mainly addressed by Locality Sensitive Hashing (LSH), which offers polynomial dependence on the dimension, query time sublinear in the size of the dataset, and subquadratic space requirement. For practical applications, linear space is typically imperative. Most previous work in the linear space regime focuses on the case that $c$ exceeds $1$ by a constant term. In a recently accepted paper, optimal bounds have been achieved for any $c>1$ \cite{ALRW17}. Towards practicality, we present a new and simple data structure using linear space and sublinear query time for any $c>1$ including $c\to 1^+$. Given an LSH family of functions for some metric space, we randomly project points to the Hamming cube of dimension $\log n$, where $n$ is the number of input points. The projected space contains strings which serve as keys for buckets containing the input points. The query algorithm simply projects the query point, then examines points which are assigned to the same or nearby vertices on the Hamming cube. We analyze in detail the query time for some standard LSH families. To illustrate our claim of practicality, we offer an open-source implementation in {\tt C++}, and report on several experiments in dimension up to 1000 and $n$ up to $10^6$. Our algorithm is one to two orders of magnitude faster than brute force search. Experiments confirm the sublinear dependence on $n$ and the linear dependence on the dimension. We have compared against state-of-the-art LSH-based library {\tt FALCONN}: our search is somewhat slower, but memory usage and preprocessing time are significantly smaller.
Deep Blind Compressed Sensing
Venue: arXiv cs.CV 2016
Year: 2016

This work addresses the problem of extracting deeply learned features directly from compressive measurements. There has been no work in this area. Existing deep learning tools only give good results when applied on the full signal, that too usually after preprocessing. These techniques require the signal to be reconstructed first. In this work we show that by learning directly from the compressed domain, considerably better results can be obtained. This work extends the recently proposed framework of deep matrix factorization in combination with blind compressed sensing; hence the term deep blind compressed sensing. Simulation experiments have been carried out on imaging via single pixel camera, under-sampled biomedical signals, arising in wireless body area network and compressive hyperspectral imaging. In all cases, the superiority of our proposed deep blind compressed sensing can be envisaged.
Science, AskScience, and BadScience: On the Coexistence of Highly Related Communities
Venue: arXiv cs.SI 2016
Year: 2016

When large social-media platforms allow users to easily form and self-organize into interest groups, highly related communities can arise. For example, the Reddit site hosts not just a group called food, but also HealthyFood, foodhacks, foodporn, and cooking, among others. Are these highly related communities created for similar classes of reasons (e.g., to focus on a subtopic, to create a place for allegedly more "high-minded" discourse, etc.)? How do users allocate attention between such close alternatives when they are available or emerge over time? Are there different types of relations between close alternatives such as sharing many users vs. a new community drawing away members of an older one vs. a splinter group failing to cohere into a viable separate community? We investigate the interactions between highly related communities using data from reddit.com consisting of 975M posts and comments spanning an 8-year period. We identify a set of typical affixes that users adopt to create highly related communities and build a taxonomy of affixes. One interesting finding regarding users' behavior is: after a newer community is created, for several types of highly-related community pairs, users that engage in a newer community tend to be more active in their original community than users that do not explore, even when controlling for previous level of engagement.
Simultaneous encodings for range and next/previous larger/smaller value queries
Venue: arXiv cs.DS 2016
Year: 2016

Given an array of $n$ elements from a total order, we propose encodings that support various range queries (range minimum, range maximum and their variants), and previous and next smaller/larger value queries. When query time is not of concern, we obtain a $4.088n + o(n)$-bit encoding that supports all these queries. For the case when we need to support all these queries in constant time, we give an encoding that takes $4.585n + o(n)$ bits, where $n$ is the length of input array. This improves the $5.08n+o(n)$-bit encoding obtained by encoding the colored $2d$-Min and Max heaps proposed by Fischer~[TCS, 2011]. We first extend the original DFUDS [Algorithmica, 2005] encoding of the colored 2d-Min (Max) heap that supports the queries in constant time. Then, we combine the extended DFUDS of $2d$-Min heap and $2d$-Max heap using the Min-Max encoding of Gawrychowski and Nicholson [ICALP, 2015] with some modifications. We also obtain encodings that take lesser space and support a subset of these queries.
An efficient hybrid tridiagonal divide-and-conquer algorithm on distributed memory architectures
Venue: arXiv cs.MS 2016
Year: 2016

In this paper, an efficient divide-and-conquer (DC) algorithm is proposed for the symmetric tridiagonal matrices based on ScaLAPACK and the hierarchically semiseparable (HSS) matrices. HSS is an important type of rank-structured matrices.Most time of the DC algorithm is cost by computing the eigenvectors via the matrix-matrix multiplications (MMM). In our parallel hybrid DC (PHDC) algorithm, MMM is accelerated by using the HSS matrix techniques when the intermediate matrix is large. All the HSS algorithms are done via the package STRUMPACK. PHDC has been tested by using many different matrices. Compared with the DC implementation in MKL, PHDC can be faster for some matrices with few deflations when using hundreds of processes. However, the gains decrease as the number of processes increases. The comparisons of PHDC with ELPA (the Eigenvalue soLvers for Petascale Applications library) are similar. PHDC is usually slower than MKL and ELPA when using 300 or more processes on Tianhe-2 supercomputer.
Solving Set Optimization Problems by Cardinality Optimization via Weak Constraints with an Application to Argumentation
Venue: arXiv cs.AI 2016
Year: 2016

Optimization - minimization or maximization - in the lattice of subsets is a frequent operation in Artificial Intelligence tasks. Examples are subset-minimal model-based diagnosis, nonmonotonic reasoning by means of circumscription, or preferred extensions in abstract argumentation. Finding the optimum among many admissible solutions is often harder than finding admissible solutions with respect to both computational complexity and methodology. This paper addresses the former issue by means of an effective method for finding subset-optimal solutions. It is based on the relationship between cardinality-optimal and subset-optimal solutions, and the fact that many logic-based declarative programming systems provide constructs for finding cardinality-optimal solutions, for example maximum satisfiability (MaxSAT) or weak constraints in Answer Set Programming (ASP). Clearly each cardinality-optimal solution is also a subset-optimal one, and if the language also allows for the addition of particular restricting constructs (both MaxSAT and ASP do) then all subset-optimal solutions can be found by an iterative computation of cardinality-optimal solutions. As a showcase, the computation of preferred extensions of abstract argumentation frameworks using the proposed method is studied.
ScienceWISE: Topic Modeling over Scientific Literature Networks
Venue: arXiv cs.DL 2016
Year: 2016

We provide an up-to-date view on the knowledge management system ScienceWISE (SW) and address issues related to the automatic assignment of articles to research topics. So far, SW has been proven to be an effective platform for managing large volumes of technical articles by means of ontological concept-based browsing. However, as the publication of research articles accelerates, the expressivity and the richness of the SW ontology turns into a double-edged sword: a more fine-grained characterization of articles is possible, but at the cost of introducing more spurious relations among them. In this context, the challenge of continuously recommending relevant articles to users lies in tackling a network partitioning problem, where nodes represent articles and co-occurring concepts create edges between them. In this paper, we discuss the three research directions we have taken for solving this issue: i) the identification of generic concepts to reinforce inter-article similarities; ii) the adoption of a bipartite network representation to improve scalability; iii) the design of a clustering algorithm to identify concepts for cross-disciplinary articles and obtain fine-grained topics for all articles.
Pot: Deterministic transactional execution
Venue: arXiv cs.DC 2016
Year: 2016

This paper presents Pot, a system that leverages the concept of preordered transactions to achieve deterministic multithreaded execution of programs that use Transactional Memory. Preordered transactions eliminate the root cause of nondeterminism in transactional execution: they provide the illusion of executing in a deterministic serial order, unlike traditional transactions which appear to execute in a nondeterministic order that can change from execution to execution. Pot uses a new concurrency control protocol that exploits the serialization order to distinguish between fast and speculative transaction execution modes in order to mitigate the overhead of imposing a deterministic order. We build two Pot prototypes: one using STM and another using off-the-shelf HTM. To the best of our knowledge, Pot enables deterministic execution of programs using off-the-shelf HTM for the first time. An experimental evaluation shows that Pot achieves deterministic execution of TM programs with low overhead, sometimes even outperforming nondeterministic executions, and clearly outperforming the state of the art.
Understanding Tree: a tool to estimate one's understanding of knowledge
Venue: arXiv cs.HC 2016
Year: 2016

People learn whenever and wherever possible, and whatever they like or encounter--Mathematics, Drama, Art, Languages, Physics, Philosophy, and so on. With the bursting of knowledge, evaluation of one's possession of knowledge becomes increasingly difficult. There are a lot of demands to evaluate one's understanding of a piece of knowledge. Assessment of understanding of knowledge is conventionally through tests or interviews, but they have some limitations such as low-efficiency and not-comprehensive. This paper proposes a method called Understanding Tree to estimate one's understanding of knowledge, by keeping track of his/her learning activities. It overcomes some limitations of traditional methods, hence complements traditional methods.
Complexity of Rainbow Vertex Connectivity Problems for Restricted Graph Classes
Venue: arXiv cs.CC 2016
Year: 2016

A path in a vertex-colored graph $G$ is \emph{vertex rainbow} if all of its internal vertices have a distinct color. The graph $G$ is said to be \emph{rainbow vertex connected} if there is a vertex rainbow path between every pair of its vertices. Similarly, the graph $G$ is \emph{strongly rainbow vertex connected} if there is a shortest path which is vertex rainbow between every pair of its vertices. We consider the complexity of deciding if a given vertex-colored graph is rainbow or strongly rainbow vertex connected. We call these problems \probRvc and \probSrvc, respectively. We prove both problems remain NP-complete on very restricted graph classes including bipartite planar graphs of maximum degree 3, interval graphs, and $k$-regular graphs for $k \geq 3$. We settle precisely the complexity of both problems from the viewpoint of two width parameters: pathwidth and tree-depth. More precisely, we show both problems remain NP-complete for bounded pathwidth graphs, while being fixed-parameter tractable parameterized by tree-depth. Moreover, we show both problems are solvable in polynomial time for block graphs, while \probSrvc is tractable for cactus graphs and split graphs.
Optimal Resource Allocation for Cellular Networks with MATLAB Instructions
Venue: arXiv cs.NI 2016
Year: 2016

This report presents a more detailed description of the algorithm and simulations published in papers [1, 2]. It includes a step by step description of the algorithm and included the corresponding flow chart. In addition, detailed instructions of the MATLAB code used to simulate the proposed allocation algorithm in [1, 2] is presented. The report starts with a brief motivation of resource allocation problem in wireless networks. Then, some of the prior related work on the subject are mentioned. Finally, we provide the details instructions on MATLAB functions used in our algorithm. More rigorous analysis and proofs of the problem and algorithm are present in [1, 2] and further discussions presented in [3, 4].
Supervised Opinion Aspect Extraction by Exploiting Past Extraction Results
Venue: arXiv cs.CL 2016
Year: 2016

One of the key tasks of sentiment analysis of product reviews is to extract product aspects or features that users have expressed opinions on. In this work, we focus on using supervised sequence labeling as the base approach to performing the task. Although several extraction methods using sequence labeling methods such as Conditional Random Fields (CRF) and Hidden Markov Models (HMM) have been proposed, we show that this supervised approach can be significantly improved by exploiting the idea of concept sharing across multiple domains. For example, "screen" is an aspect in iPhone, but not only iPhone has a screen, many electronic devices have screens too. When "screen" appears in a review of a new domain (or product), it is likely to be an aspect too. Knowing this information enables us to do much better extraction in the new domain. This paper proposes a novel extraction method exploiting this idea in the context of supervised sequence labeling. Experimental results show that it produces markedly better results than without using the past information.
Dimensional Confluence Algebra of Information Space Modulo Quotient Abstraction Relations in Automated Problem Solving Paradigm
Venue: arXiv cs.LO 2016
Year: 2016

Confluence in abstract parallel category systems is established for net class-rewriting in iterative closed multilevel quotient graph structures with uncountable node arities by multi-dimensional transducer operations in topological metrics defined by alphabetically abstracting net block homomorphism. We obtain minimum prerequisites for the comprehensive connector pairs in a multitude dimensional rewriting closure generating confluence in Participatory algebra for different horizontal and vertical level projections modulo abstraction relations constituting formal semantics for confluence in information space. Participatory algebra with formal automata syntax in its entirety representing automated problem solving paradigm generates rich variety of multitude confluence harmonizers under each fundamental abstraction relation set, horizontal structure mapping and vertical process iteration cardinality.
A Secure Multiple-Access Scheme for Rechargeable Wireless Sensors in the Presence of an Eavesdropper
Venue: arXiv cs.NI 2016
Year: 2016

We propose a simple yet efficient scheme for a set of energy-harvesting sensors to establish secure communication with a common destination (a master node). An eavesdropper attempts to decode the data sent from the sensors to their common destination. We assume a single modulation scheme that can be implemented efficiently for energy-limited applications. We design a multiple-access scheme for the sensors under secrecy and limited-energy constraints. In a given time slot, each energy-harvesting sensor chooses between sending its packet or remaining idle. The destination assigns a set of data time slots to each sensor. The optimization problem is formulated to maximize the secrecy sum-throughput.