OpenRaiser/Intern-Atlas huggingface dataset:
Efficient Machine Learning for Big Data: A Review
Venue: arXiv cs.LG 2015
Year: 2015

With the emerging technologies and all associated devices, it is predicted that massive amount of data will be created in the next few years, in fact, as much as 90% of current data were created in the last couple of years,a trend that will continue for the foreseeable future. Sustainable computing studies the process by which computer engineer/scientist designs computers and associated subsystems efficiently and effectively with minimal impact on the environment. However, current intelligent machine-learning systems are performance driven, the focus is on the predictive/classification accuracy, based on known properties learned from the training samples. For instance, most machine-learning-based nonparametric models are known to require high computational cost in order to find the global optima. With the learning task in a large dataset, the number of hidden nodes within the network will therefore increase significantly, which eventually leads to an exponential rise in computational complexity. This paper thus reviews the theoretical and experimental data-modeling literature, in large-scale data-intensive fields, relating to: (1) model efficiency, including computational requirements in learning, and data-intensive areas structure and design, and introduces (2) new algorithmic approaches with the least memory requirements and processing to minimize computational cost, while maintaining/improving its predictive/classification accuracy and stability.
Caching at the Edge: a Green Perspective for 5G Networks
Venue: arXiv cs.IT 2015
Year: 2015

Endowed with context-awareness and proactive capabilities, caching users' content locally at the edge of the network is able to cope with increasing data traffic demand in 5G wireless networks. In this work, we focus on the energy consumption aspects of cache-enabled wireless cellular networks, specifically in terms of area power consumption (APC) and energy efficiency (EE). We assume that both base stations (BSs) and mobile users are distributed according to homogeneous Poisson point processes (PPPs) and we introduce a detailed power model that takes into account caching. We study the conditions under which the area power consumption is minimized with respect to BS transmit power, while ensuring a certain quality of service (QoS) in terms of coverage probability. Furthermore, we provide the optimal BS transmit power that maximizes the area spectral efficiency per unit total power spent. The main takeaway of this paper is that caching seems to be an energy efficient solution.
The Application of MIMO to Non-Orthogonal Multiple Access
Venue: arXiv cs.IT 2015
Year: 2015

This paper considers the application of multiple-input multiple-output (MIMO) techniques to non-orthogonal multiple access (NOMA) systems. A new design of precoding and detection matrices for MIMO-NOMA is proposed and its performance is analyzed for the case with a fixed set of power allocation coefficients. To further improve the performance gap between MIMO-NOMA and conventional orthogonal multiple access schemes, user pairing is applied to NOMA and its impact on the system performance is characterized. More sophisticated choices of power allocation coefficients are also proposed to meet various quality of service requirements. Finally computer simulation results are provided to facilitate the performance evaluation of MIMO-NOMA and also demonstrate the accuracy of the developed analytical results.
Does "Like" Really Mean Like? A Study of the Facebook Fake Like Phenomenon and an Efficient Countermeasure
Venue: arXiv cs.SI 2015
Year: 2015

Social networks help to bond people who share similar interests all over the world. As a complement, the Facebook "Like" button is an efficient tool that bonds people with the online information. People click on the "Like" button to express their fondness of a particular piece of information and in turn tend to visit webpages with high "Like" count. The important fact of the Like count is that it reflects the number of actual users who "liked" this information. However, according to our study, one can easily exploit the defects of the "Like" button to counterfeit a high "Like" count. We provide a proof-of-concept implementation of these exploits, and manage to generate 100 fake Likes in 5 minutes with a single account. We also reveal existing counterfeiting techniques used by some online sellers to achieve unfair advantage for promoting their products. To address this fake Like problem, we study the varying patterns of Like count and propose an innovative fake Like detection method based on clustering. To evaluate the effectiveness of our algorithm, we collect the Like count history of more than 9,000 websites. Our experiments successfully uncover 16 suspicious fake Like buyers that show abnormal Like count increase patterns.
Rank logic is dead, long live rank logic!
Venue: arXiv cs.LO 2015
Year: 2015

Motivated by the search for a logic for polynomial time, we study rank logic (FPR) which extends fixed-point logic with counting (FPC) by operators that determine the rank of matrices over finite fields. While FPR can express most of the known queries that separate FPC from PTIME, nearly nothing was known about the limitations of its expressive power. In our first main result we show that the extensions of FPC by rank operators over different prime fields are incomparable. This solves an open question posed by Dawar and Holm and also implies that rank logic, in its original definition with a distinct rank operator for every field, fails to capture polynomial time. In particular we show that the variant of rank logic FPR* with an operator that uniformly expresses the matrix rank over finite fields is more expressive than FPR. One important step in our proof is to consider solvability logic FPS which is the analogous extension of FPC by quantifiers which express the solvability problem for linear equation systems over finite fields. Solvability logic can easily be embedded into rank logic, but it is open whether it is a strict fragment. In our second main result we give a partial answer to this question: in the absence of counting, rank operators are strictly more expressive than solvability quantifiers.
Minimum distance of Symplectic Grassmann codes
Venue: arXiv cs.IT 2015
Year: 2015

We introduce the Symplectic Grassmann codes as projective codes defined by symplectic Grassmannians, in analogy with the orthogonal Grassmann codes introduced in [4]. Note that the Lagrangian-Grassmannian codes are a special class of Symplectic Grassmann codes. We describe the weight enumerator of the Lagrangian--Grassmannian codes of rank $2$ and $3$ and we determine the minimum distance of the line Symplectic Grassmann codes.
A distributed-memory package for dense Hierarchically Semi-Separable matrix computations using randomization
Venue: arXiv cs.MS 2015
Year: 2015

We present a distributed-memory library for computations with dense structured matrices. A matrix is considered structured if its off-diagonal blocks can be approximated by a rank-deficient matrix with low numerical rank. Here, we use Hierarchically Semi-Separable representations (HSS). Such matrices appear in many applications, e.g., finite element methods, boundary element methods, etc. Exploiting this structure allows for fast solution of linear systems and/or fast computation of matrix-vector products, which are the two main building blocks of matrix computations. The compression algorithm that we use, that computes the HSS form of an input dense matrix, relies on randomized sampling with a novel adaptive sampling mechanism. We discuss the parallelization of this algorithm and also present the parallelization of structured matrix-vector product, structured factorization and solution routines. The efficiency of the approach is demonstrated on large problems from different academic and industrial applications, on up to 8,000 cores. This work is part of a more global effort, the STRUMPACK (STRUctured Matrices PACKage) software package for computations with sparse and dense structured matrices. Hence, although useful on their own right, the routines also represent a step in the direction of a distributed-memory sparse solver.
Nonparametric Detection of Nonlinearly Mixed Pixels and Endmember Estimation in Hyperspectral Images
Venue: arXiv cs.CV 2015
Year: 2015

Mixing phenomena in hyperspectral images depend on a variety of factors such as the resolution of observation devices, the properties of materials, and how these materials interact with incident light in the scene. Different parametric and nonparametric models have been considered to address hyperspectral unmixing problems. The simplest one is the linear mixing model. Nevertheless, it has been recognized that mixing phenomena can also be nonlinear. The corresponding nonlinear analysis techniques are necessarily more challenging and complex than those employed for linear unmixing. Within this context, it makes sense to detect the nonlinearly mixed pixels in an image prior to its analysis, and then employ the simplest possible unmixing technique to analyze each pixel. In this paper, we propose a technique for detecting nonlinearly mixed pixels. The detection approach is based on the comparison of the reconstruction errors using both a Gaussian process regression model and a linear regression model. The two errors are combined into a detection statistics for which a probability density function can be reasonably approximated. We also propose an iterative endmember extraction algorithm to be employed in combination with the detection algorithm. The proposed Detect-then-Unmix strategy, which consists of extracting endmembers, detecting nonlinearly mixed pixels and unmixing, is tested with synthetic and real images.
Memantic: A Medical Knowledge Discovery Engine
Venue: arXiv cs.IR 2015
Year: 2015

We present a system that constructs and maintains an up-to-date co-occurrence network of medical concepts based on continuously mining the latest biomedical literature. Users can explore this network visually via a concise online interface to quickly discover important and novel relationships between medical entities. This enables users to rapidly gain contextual understanding of their medical topics of interest, and we believe this constitutes a significant user experience improvement over contemporary search engines operating in the biomedical literature domain.
Hypercomputation, Frege, Deleuze: Solving Thomson's Lamp
Venue: arXiv cs.LO 2015
Year: 2015

We present the first known solution to the original supertask, the Thomson Lamp Paradox. We also offer preliminary resources for classifying computational complexity of various supertasks. In so doing we consider a newly apparent paradox between the metrical limit and the ordinal limit. We use this distinction between the metrical and ordinal limits to explain the shortcomings both of Thomson's original formulation of the Lamp Paradox and Benacerraf's consequent critique. We resolve this paradox through a careful consideration of transfinite ordinals and locate its ambiguity as inherent to the identity relation under logic with a close reading of Frege's Begriffsschrift. With this close reading in hand we expose how the identity relation is counter-intuitively polyvalent and, with supertasks, how the logico-mathematical field operates on the basis of Deleuzian point-folds. Our results combine resources from philosophy, mathematics, and computer science to ground the field of hypercomputation for logically rigorous study.
ADS 2.0: new architecture, API and services
Venue: arXiv cs.DL 2015
Year: 2015

The ADS platform is undergoing the biggest rewrite of its 20-year history. While several components have been added to its architecture over the past couple of years, this talk will concentrate on the underpinnings of ADS's search layer and its API. To illustrate the design of the components in the new system, we will show how the new ADS user interface is built exclusively on top of the API using RESTful web services. Taking one step further, we will discuss how we plan to expose the treasure trove of information hosted by ADS (10 million records and fulltext for much of the Astronomy and Physics refereed literature) to partners interested in using this API. This will provide you (and your intelligent applications) with access to ADS's underlying data to enable the extraction of new knowledge and the ingestion of these results back into the ADS. Using this framework, researchers could run controlled experiments with content extraction, machine learning, natural language processing, etc. In this talk, we will discuss what is already implemented, what will be available soon, and where we are going next.
The Human Body and Millimeter-Wave Wireless Communication Systems: Interactions and Implications
Venue: arXiv cs.ET 2015
Year: 2015

With increasing interest in millimeter wave wireless communications, investigations on interactions between the human body and millimeter wave devices are becoming important. This paper gives examples of current regulatory requirements, and provides an example for a 60 GHz transceiver. Also, the propagation characteristics of millimeter-waves in the presence of the human body are studied, and four models representing different body parts are considered to evaluate thermal effects of millimeter-wave radiation on the body. Simulation results show that about 34% to 42% of the incident power is reflected at the skin surface at 60 GHz. This paper shows that power density is not suitable to determine exposure compliance when millimeter wave devices are used very close to the body. A temperature-based technique for the evaluation of safety compliance is proposed in this paper.
Human Computation and Convergence
Venue: arXiv cs.HC 2015
Year: 2015

Humans are the most effective integrators and producers of information, directly and through the use of information-processing inventions. As these inventions become increasingly sophisticated, the substantive role of humans in processing information will tend toward capabilities that derive from our most complex cognitive processes, e.g., abstraction, creativity, and applied world knowledge. Through the advancement of human computation - methods that leverage the respective strengths of humans and machines in distributed information-processing systems - formerly discrete processes will combine synergistically into increasingly integrated and complex information processing systems. These new, collective systems will exhibit an unprecedented degree of predictive accuracy in modeling physical and techno-social processes, and may ultimately coalesce into a single unified predictive organism, with the capacity to address societies most wicked problems and achieve planetary homeostasis.
Dynamic Data Structures for Document Collections and Graphs
Venue: arXiv cs.DS 2015
Year: 2015

In the dynamic indexing problem, we must maintain a changing collection of text documents so that we can efficiently support insertions, deletions, and pattern matching queries. We are especially interested in developing efficient data structures that store and query the documents in compressed form. All previous compressed solutions to this problem rely on answering rank and select queries on a dynamic sequence of symbols. Because of the lower bound in [Fredman and Saks, 1989], answering rank queries presents a bottleneck in compressed dynamic indexing. In this paper we show how this lower bound can be circumvented using our new framework. We demonstrate that the gap between static and dynamic variants of the indexing problem can be almost closed. Our method is based on a novel framework for adding dynamism to static compressed data structures. Our framework also applies more generally to dynamizing other problems. We show, for example, how our framework can be applied to develop compressed representations of dynamic graphs and binary relations.
Application Security framework for Mobile App Development in Enterprise setup
Venue: arXiv cs.CR 2015
Year: 2015

Enterprise Mobility has been increasing the reach over the years. Initially Mobile devices were adopted as consumer devices. However, the enterprises world over have rightly taken the leap and started using the ubiquitous technology for managing its employees as well as to reach out to the customers. While the Mobile ecosystem has been evolving over the years, the increased exposure of mobility in Enterprise framework have caused major focus on the security aspects of it. While a significant focus have been put on network security, this paper discusses on the approach that can be taken at Mobile application layer, which would reduce the risk to the enterprises.
Massively Parallel Construction of the Cell Graph
Venue: arXiv cs.DC 2015
Year: 2015

Motion planning is an important and well-studied field of robotics. A typical approach to finding a route is to construct a {\em cell graph} representing a scene and then to find a path in such a graph. In this paper we present and analyze parallel algorithms for constructing the cell graph on a SIMD-like GPU processor. Additionally, we present a new implementation of the dictionary data type on a GPU device. In the contrary to hash tables, which are common in GPU algorithms, it uses a search tree in which all values are kept in leaves. With such a structure we can effectively perform dictionary operations on a set of long vectors over a limited alphabet.
On the Complexity of Exchanging
Venue: arXiv cs.GT 2015
Year: 2015

We analyze the computational complexity of the problem of deciding whether, for a given simple game, there exists the possibility of rearranging the participants in a set of $j$ given losing coalitions into a set of $j$ winning coalitions. We also look at the problem of turning winning coalitions into losing coalitions. We analyze the problem when the simple game is represented by a list of wining, losing, minimal winning or maximal loosing coalitions.
Enumeration formulæ in neutral sets
Venue: arXiv cs.DM 2015
Year: 2015

We present several enumeration results holding in sets of words called neutral and which satisfy restrictive conditions on the set of possible extensions of nonempty words. These formulae concern return words and bifix codes. They generalize formulae previously known for Sturmian sets or more generally for tree sets. We also give a geometric example of this class of sets, namely the natural coding of some interval exchange transformations.
The Next 700 Challenge Problems for Reasoning with Higher-Order Abstract Syntax Representations: Part 1-A Common Infrastructure for Benchmarks
Venue: arXiv cs.LO 2015
Year: 2015

A variety of logical frameworks support the use of higher-order abstract syntax (HOAS) in representing formal systems. Although these systems seem superficially the same, they differ in a variety of ways; for example, how they handle a context of assumptions and which theorems about a given formal system can be concisely expressed and proved. Our contributions in this paper are three-fold: 1) we develop a common infrastructure for representing benchmarks for systems supporting reasoning with binders, 2) we present several concrete benchmarks, which highlight a variety of different aspects of reasoning within a context of assumptions, and 3) we design an open repository ORBI, (Open challenge problem Repository for systems supporting reasoning with BInders). Our work sets the stage for providing a basis for qualitative comparison of different systems. This allows us to review and survey the state of the art, which we do in great detail for four systems in Part 2 of this paper (Felty et al, 2015). It also allows us to outline future fundamental research questions regarding the design and implementation of meta-reasoning systems.
On measuring linguistic intelligence
Venue: arXiv cs.CL 2015
Year: 2015

This work addresses the problem of measuring how many languages a person "effectively" speaks given that some of the languages are close to each other. In other words, to assign a meaningful number to her language portfolio. Intuition says that someone who speaks fluently Spanish and Portuguese is linguistically less proficient compared to someone who speaks fluently Spanish and Chinese since it takes more effort for a native Spanish speaker to learn Chinese than Portuguese. As the number of languages grows and their proficiency levels vary, it gets even more complicated to assign a score to a language portfolio. In this article we propose such a measure ("linguistic quotient" - LQ) that can account for these effects. We define the properties that such a measure should have. They are based on the idea of coherent risk measures from the mathematical finance. Having laid down the foundation, we propose one such a measure together with the algorithm that works on languages classification tree as input. The algorithm together with the input is available online at lingvometer.com
Block-Wise MAP Inference for Determinantal Point Processes with Application to Change-Point Detection
Venue: arXiv cs.LG 2015
Year: 2015

Existing MAP inference algorithms for determinantal point processes (DPPs) need to calculate determinants or conduct eigenvalue decomposition generally at the scale of the full kernel, which presents a great challenge for real-world applications. In this paper, we introduce a class of DPPs, called BwDPPs, that are characterized by an almost block diagonal kernel matrix and thus can allow efficient block-wise MAP inference. Furthermore, BwDPPs are successfully applied to address the difficulty of selecting change-points in the problem of change-point detection (CPD), which results in a new BwDPP-based CPD method, named BwDppCpd. In BwDppCpd, a preliminary set of change-point candidates is first created based on existing well-studied metrics. Then, these change-point candidates are treated as DPP items, and DPP-based subset selection is conducted to give the final estimate of the change-points that favours both quality and diversity. The effectiveness of BwDppCpd is demonstrated through extensive experiments on five real-world datasets.
Complex Networks, Communities and Clustering: A survey
Venue: arXiv cs.SI 2015
Year: 2015

This paper is an extensive survey of literature on complex network communities and clustering. Complex networks describe a widespread variety of systems in nature and society especially systems composed by a large number of highly interconnected dynamical entities. Complex networks like real networks can also have community structure. There are several types of methods and algorithms for detection and identification of communities in complex networks. Several complex networks have the property of clustering or network transitivity. Some of the important concepts in the field of complex networks are small-world and scale-robustness, degree distributions, clustering, network correlations, random graph models, models of network growth, dynamical processes on networks, etc. Some current areas of research on complex network communities are those on community evolution, overlapping communities, communities in directed networks, community characterization and interpretation, etc. Many of the algorithms or methods proposed for network community detection through clustering are modified versions of or inspired from the concepts of minimum-cut based algorithms, hierarchical connectivity based algorithms, the original GirvanNewman algorithm, concepts of modularity maximization, algorithms utilizing metrics from information and coding theory, and clique based algorithms.