OpenRaiser/Intern-Atlas huggingface dataset:
Data classification using the Dempster-Shafer method
Venue: arXiv cs.LG 2014
Year: 2014

In this paper, the Dempster-Shafer method is employed as the theoretical basis for creating data classification systems. Testing is carried out using three popular (multiple attribute) benchmark datasets that have two, three and four classes. In each case, a subset of the available data is used for training to establish thresholds, limits or likelihoods of class membership for each attribute, and hence create mass functions that establish probability of class membership for each attribute of the test data. Classification of each data item is achieved by combination of these probabilities via Dempster's Rule of Combination. Results for the first two datasets show extremely high classification accuracy that is competitive with other popular methods. The third dataset is non-numerical and difficult to classify, but good results can be achieved provided the system and mass functions are designed carefully and the right attributes are chosen for combination. In all cases the Dempster-Shafer method provides comparable performance to other more popular algorithms, but the overhead of generating accurate mass functions increases the complexity with the addition of new attributes. Overall, the results suggest that the D-S approach provides a suitable framework for the design of classification systems and that automating the mass function design and calculation would increase the viability of the algorithm for complex classification problems.
Characterizing and Subsetting Big Data Workloads
Venue: arXiv cs.PF 2014
Year: 2014

Big data benchmark suites must include a diversity of data and workloads to be useful in fairly evaluating big data systems and architectures. However, using truly comprehensive benchmarks poses great challenges for the architecture community. First, we need to thoroughly understand the behaviors of a variety of workloads. Second, our usual simulation-based research methods become prohibitively expensive for big data. As big data is an emerging field, more and more software stacks are being proposed to facilitate the development of big data applications, which aggravates hese challenges. In this paper, we first use Principle Component Analysis (PCA) to identify the most important characteristics from 45 metrics to characterize big data workloads from BigDataBench, a comprehensive big data benchmark suite. Second, we apply a clustering technique to the principle components obtained from the PCA to investigate the similarity among big data workloads, and we verify the importance of including different software stacks for big data benchmarking. Third, we select seven representative big data workloads by removing redundant ones and release the BigDataBench simulation version, which is publicly available from http://prof.ict.ac.cn/BigDataBench/simulatorversion/.
Verification of Information Flow Properties under Rational Observation
Venue: arXiv cs.CR 2014
Year: 2014

Information flow properties express the capability for an agent to infer information about secret behaviours of a partially observable system. In a language-theoretic setting, where the system behaviour is described by a language, we define the class of rational information flow properties (RIFP), where observers are modeled by finite transducers, acting on languages in a given family $\mathcal{L}$. This leads to a general decidability criterion for the verification problem of RIFPs on $\mathcal{L}$, implying PSPACE-completeness for this problem on regular languages. We show that most trace-based information flow properties studied up to now are RIFPs, including those related to selective declassification and conditional anonymity. As a consequence, we retrieve several existing decidability results that were obtained by ad-hoc proofs.
A Graph-based Perspective to Total Carbon Footprint Assessment of Non-marginal Technology-driven Projects - Use case of OTT/IPTV
Venue: arXiv cs.NI 2014
Year: 2014

Life Cycle Assessment (LCA) of green and sustainable projects has been found to be a necessary analysis in order to include all upstream, downstream, and indirect impacts. Because of the complexity of interactions, the differential impacts with respect to a baseline, i.e., a business-as-usual (BAU) scenario, are commonly considered to relatively compare various projects. However, as the degree of penetration of a project in the baseline increases, the popular marginal assumption does no longer hold, and the differential impacts may become inconsistent. Although various mythologies have been successfully proposed and used to contain such a side effect, the bottom-up nature, which initiates the assessment from the project itself and ultimately widens the scope, could easily fail to acknowledge critical modifications to the baseline. This is highly relevant in terms of ICT's disruptive and dynamic technologies which push the baseline to become a marginal legacy. In this work, an analytic formalism is presented to provide a means of comparison of such technologies and projects. The core idea behind the proposed methodology is a magnitude-insensitive graph-based distance function to differentially compare a project with a baseline. The applicability of the proposed methodology is then evaluated in a use case of OTT/IPTV online media distribution services.
Dimensionality Invariant Similarity Measure
Venue: arXiv cs.LG 2014
Year: 2014

This paper presents a new similarity measure to be used for general tasks including supervised learning, which is represented by the K-nearest neighbor classifier (KNN). The proposed similarity measure is invariant to large differences in some dimensions in the feature space. The proposed metric is proved mathematically to be a metric. To test its viability for different applications, the KNN used the proposed metric for classifying test examples chosen from a number of real datasets. Compared to some other well known metrics, the experimental results show that the proposed metric is a promising distance measure for the KNN classifier with strong potential for a wide range of applications.
Continuous Gait Velocity Estimation using Houseohld Motion Detectors
Venue: arXiv cs.SY 2014
Year: 2014

Gait velocity has been consistently shown to be an important indicator and predictor of health status, especially in older adults. Gait velocity is often assessed clinically, but the assessments occur infrequently and thus do not allow optimal detection of key health changes when they occur. In this paper, we show the time it takes a person to move between rooms in their home denoted 'transition times' can predict gait velocity when estimated from passive infrared motion detectors installed in a patient's own home. Using a support vector regression approach to model the relationship between transition times and gait velocities, we show that velocity can be predicted with an average error less than 2.5 cm/sec. This is demonstrated with data collected over a 5 year period from 74 older adults monitored in their own homes. This method is simple and cost effective, and has advantages over competing approaches such as: obtaining 20 to100x more gait velocity measurements per day, and offering the fusion of location specific information with time stamped gait estimates. These advantages allow stable estimates of gait parameters (maximum or average speed, variability) at shorter time scales than current approaches. This also provides a pervasive in home method for context aware gait velocity sensing that allows for monitoring of gait trajectories in space and time.
Constructing a Non-Negative Low Rank and Sparse Graph with Data-Adaptive Features
Venue: arXiv cs.CV 2014
Year: 2014

This paper aims at constructing a good graph for discovering intrinsic data structures in a semi-supervised learning setting. Firstly, we propose to build a non-negative low-rank and sparse (referred to as NNLRS) graph for the given data representation. Specifically, the weights of edges in the graph are obtained by seeking a nonnegative low-rank and sparse matrix that represents each data sample as a linear combination of others. The so-obtained NNLRS-graph can capture both the global mixture of subspaces structure (by the low rankness) and the locally linear structure (by the sparseness) of the data, hence is both generative and discriminative. Secondly, as good features are extremely important for constructing a good graph, we propose to learn the data embedding matrix and construct the graph jointly within one framework, which is termed as NNLRS with embedded features (referred to as NNLRS-EF). Extensive experiments on three publicly available datasets demonstrate that the proposed method outperforms the state-of-the-art graph construction method by a large margin for both semi-supervised classification and discriminative analysis, which verifies the effectiveness of our proposed method.
Tactical communication systems based on civil standards: Modeling in the MiXiM framework
Venue: arXiv cs.NI 2014
Year: 2014

In this paper, new work is presented belonging to an ongoing study, which evaluates civil communication standards as potential candidates for the future military Wide Band Waveforms (WBWFs). After an evaluation process of possible candidates presented in [2], the selection process in [1] showed that the IEEE 802.11n OFDM could be a possible military WBWF candidate, but it should be further investigated first in order to enhance or even replace critical modules. According to this, some critical modules of the physical layer has been further analyzed in [3] regarding the susceptibility of the OFDM signal under jammer influences. However, the critical modules of the MAC layer (e.g., probabilistic medium access CSMA/CA) have not been analysed. In fact, it was only suggested in [2] to replace this medium access by the better suited Unified Slot Allocation Protocol - Multiple Access (USAP-MA) [4]. In this regard, the present contribution describes the design paradigms of the new MAC layer and explains how the proposed WBWF candidate has been modelled within the MiXiM Framework of the OMNeT++ simulator.
Detecting adverse drug reactions for the drug Simvastatin
Venue: arXiv cs.CE 2014
Year: 2014

Adverse drug reactions (ADR) are widely concerning for public health issue. In this study we propose an original approach to detect ADRs using a feature matrix and feature selection. The experiments are carried out on the drug Simvastatin. Major side effects for the drug are detected and better performance is achieved compared to other computerized methods. Because currently the detected ADRs are based solely on computerized methods, further expert investigation is needed.
Weak and Nested Class Memory Automata
Venue: arXiv cs.FL 2014
Year: 2014

Automata over infinite alphabets have recently come to be studied extensively as potentially useful tools for solving problems in verification and database theory. One popular model of automata studied is the Class Memory Automata (CMA), for which the emptiness problem is equivalent to Petri Net Reachability. We identify a restriction - which we call weakness - of CMA, and show that their emptiness problem is equivalent to Petri Net Coverability. Further, we show that in the deterministic case they are closed under all Boolean operations. We clarify the connections between weak CMA and existing automata over data languages. We also extend CMA to operate over multiple levels of nested data values, and show that while these have undecidable emptiness in general, adding the weakness constraint recovers decidability of emptiness, via reduction to coverability in well-structured transition systems. We also examine connections with existing automata over nested data.
A variant of the Hadwiger-Debrunner (p,q)-problem in the plane
Venue: arXiv cs.CG 2014
Year: 2014

Let $X$ be a convex curve in the plane (say, the unit circle), and let $\mathcal S$ be a family of planar convex bodies, such that every two of them meet at a point of $X$. Then $\mathcal S$ has a transversal $N\subset\mathbb R^2$ of size at most $1.75\cdot 10^9$. Suppose instead that $\mathcal S$ only satisfies the following "$(p,2)$-condition": Among every $p$ elements of $\mathcal S$ there are two that meet at a common point of $X$. Then $\mathcal S$ has a transversal of size $O(p^8)$. For comparison, the best known bound for the Hadwiger--Debrunner $(p, q)$-problem in the plane, with $q=3$, is $O(p^6)$. Our result generalizes appropriately for $\mathbb R^d$ if $X\subset \mathbb R^d$ is, for example, the moment curve.
Finding Patterns in a Knowledge Base using Keywords to Compose Table Answers
Venue: arXiv cs.DB 2014
Year: 2014

We aim to provide table answers to keyword queries against knowledge bases. For queries referring to multiple entities, like "Washington cities population" and "Mel Gibson movies", it is better to represent each relevant answer as a table which aggregates a set of entities or entity-joins within the same table scheme or pattern. In this paper, we study how to find highly relevant patterns in a knowledge base for user-given keyword queries to compose table answers. A knowledge base can be modeled as a directed graph called knowledge graph, where nodes represent entities in the knowledge base and edges represent the relationships among them. Each node/edge is labeled with type and text. A pattern is an aggregation of subtrees which contain all keywords in the texts and have the same structure and types on node/edges. We propose efficient algorithms to find patterns that are relevant to the query for a class of scoring functions. We show the hardness of the problem in theory, and propose path-based indexes that are affordable in memory. Two query-processing algorithms are proposed: one is fast in practice for small queries (with small patterns as answers) by utilizing the indexes; and the other one is better in theory, with running time linear in the sizes of indexes and answers, which can handle large queries better. We also conduct extensive experimental study to compare our approaches with a naive adaption of known techniques.
Large induced forests in planar graphs with girth 4 or 5
Venue: arXiv cs.DM 2014
Year: 2014

We give here some new lower bounds on the order of a largest induced forest in planar graphs with girth $4$ and $5$. In particular we prove that a triangle-free planar graph of order $n$ admits an induced forest of order at least $\frac{6n+7}{11}$ , improving the lower bound of Salavatipour [M. R. Salavatipour, Large induced forests in triangle-free planar graphs, Graphs and Combinatorics, 22:113-126, 2006]. We also prove that a planar graph of order $n$ and girth at least $5$ admits an induced forest of order at least $\frac{44n+50}{69}$.
Well-dominated graphs without cycles of lengths 4 and 5
Venue: arXiv cs.DM 2014
Year: 2014

Let $G$ be a graph. A set $S$ of vertices in $G$ dominates the graph if every vertex of $G$ is either in $S$ or a neighbor of a vertex in $S$. Finding a minimal cardinality set which dominates the graph is an NP-complete problem. The graph $G$ is well-dominated if all its minimal dominating sets are of the same cardinality. The complexity status of recognizing well-dominated graphs is not known. We show that recognizing well-dominated graphs can be done polynomially for graphs without cycles of lengths $4$ and $5$, by proving that a graph belonging to this family is well-dominated if and only if it is well-covered. Assume that a weight function $w$ is defined on the vertices of $G$. Then $G$ is $w$-well-dominated} if all its minimal dominating sets are of the same weight. We prove that the set of weight functions $w$ such that $G$ is $w$-well-dominated is a vector space, and denote that vector space by $WWD(G)$. We prove that $WWD(G)$ is a subspace of $WCW(G)$, the vector space of weight functions $w$ such that $G$ is $w$-well-covered. We provide a polynomial characterization of $WWD(G)$ for the case that $G$ does not contain cycles of lengths $4$, $5$, and $6$.
HISQ inverter on Intel Xeon Phi and NVIDIA GPUs
Venue: arXiv cs.DC 2014
Year: 2014

The runtime of a Lattice QCD simulation is dominated by a small kernel, which calculates the product of a vector by a sparse matrix known as the "Dslash" operator. Therefore, this kernel is frequently optimized for various HPC architectures. In this contribution we compare the performance of the Intel Xeon Phi to current Kepler-based NVIDIA Tesla GPUs running a conjugate gradient solver. By exposing more parallelism to the accelerator through inverting multiple vectors at the same time we obtain a performance 250 GFlop/s on both architectures. This more than doubles the performance of the inversions. We give a short overview of both architectures, discuss some details of the implementation and the effort required to obtain the achieved performance.
Multiple Access for Small Packets Based on Precoding and Sparsity-Aware Detection
Venue: arXiv cs.IT 2014
Year: 2014

Modern mobile terminals often produce a large number of small data packets. For these packets, it is inefficient to follow the conventional medium access control protocols because of poor utilization of service resources. We propose a novel multiple access scheme that employs block-spreading based precoding at the transmitters and sparsity-aware detection schemes at the base station. The proposed scheme is well suited for the emerging massive multiple-input multiple-output (MIMO) systems, as well as conventional cellular systems with a small number of base-station antennas. The transmitters employ precoding in time domain to enable the simultaneous transmissions of many users, which could be even more than the number of receive antennas at the base station. The system is modeled as a linear system of equations with block-sparse unknowns. We first adopt the block orthogonal matching pursuit (BOMP) algorithm to recover the transmitted signals. We then develop an improved algorithm, named interference cancellation BOMP (ICBOMP), which takes advantage of error correction and detection coding to perform perfect interference cancellation during each iteration of BOMP algorithm. Conditions for guaranteed data recovery are identified. The simulation results demonstrate that the proposed scheme can accommodate more simultaneous transmissions than conventional schemes in typical small-packet transmission scenarios.
Semantic clustering of Russian web search results: possibilities and problems
Venue: arXiv cs.CL 2014
Year: 2014

The paper deals with word sense induction from lexical co-occurrence graphs. We construct such graphs on large Russian corpora and then apply this data to cluster Mail.ru Search results according to meanings of the query. We compare different methods of performing such clustering and different source corpora. Models of applying distributional semantics to big linguistic data are described.
Two-level Data Staging ETL for Transaction Data
Venue: arXiv cs.DB 2014
Year: 2014

In data warehousing, Extract-Transform-Load (ETL) extracts the data from data sources into a central data warehouse regularly for the support of business decision-makings. The data from transaction processing systems are featured with the high frequent changes of insertion, update, and deletion. It is challenging for ETL to propagate the changes to the data warehouse, and maintain the change history. Moreover, ETL jobs typically run in a sequential order when processing the data with dependencies, which is not optimal, \eg, when processing early-arriving data. In this paper, we propose a two-level data staging ETL for handling transaction data. The proposed method detects the changes of the data from transactional processing systems, identifies the corresponding operation codes for the changes, and uses two staging databases to facilitate the data processing in an ETL process. The proposed ETL provides the "one-stop" method for fast-changing, slowly-changing and early-arriving data processing.
Prolonging the Hide-and-Seek Game: Optimal Trajectory Privacy for Location-Based Services
Venue: arXiv cs.CR 2014
Year: 2014

Human mobility is highly predictable. Individuals tend to only visit a few locations with high frequency, and to move among them in a certain sequence reflecting their habits and daily routine. This predictability has to be taken into account in the design of location privacy preserving mechanisms (LPPMs) in order to effectively protect users when they continuously expose their position to location-based services (LBSs). In this paper, we describe a method for creating LPPMs that are customized for a user's mobility profile taking into account privacy and quality of service requirements. By construction, our LPPMs take into account the sequential correlation across the user's exposed locations, providing the maximum possible trajectory privacy, i.e., privacy for the user's present location, as well as past and expected future locations. Moreover, our LPPMs are optimal against a strategic adversary, i.e., an attacker that implements the strongest inference attack knowing both the LPPM operation and the user's mobility profile. The optimality of the LPPMs in the context of trajectory privacy is a novel contribution, and it is achieved by formulating the LPPM design problem as a Bayesian Stackelberg game between the user and the adversary. An additional benefit of our formal approach is that the design parameters of the LPPM are chosen by the optimization algorithm.
Using the distribution of cells by dimension in a cylindrical algebraic decomposition
Venue: arXiv cs.SC 2014
Year: 2014

We investigate the distribution of cells by dimension in cylindrical algebraic decompositions (CADs). We find that they follow a standard distribution which seems largely independent of the underlying problem or CAD algorithm used. Rather, the distribution is inherent to the cylindrical structure and determined mostly by the number of variables. This insight is then combined with an algorithm that produces only full-dimensional cells to give an accurate method of predicting the number of cells in a complete CAD. Since constructing only full-dimensional cells is relatively inexpensive (involving no costly algebraic number calculations) this leads to heuristics for helping with various questions of problem formulation for CAD, such as choosing an optimal variable ordering. Our experiments demonstrate that this approach can be highly effective.
Zero-determinant strategies in iterated multi-strategy games
Venue: arXiv cs.GT 2014
Year: 2014

Self-serving, rational agents sometimes cooperate to their mutual benefit. The two-player iterated prisoner's dilemma game is a model for including the emergence of cooperation. It is generally believed that there is no simple ultimatum strategy which a player can control the return of the other participants. The recent discovery of the powerful class of zero-determinant strategies in the iterated prisoner's dilemma dramatically expands our understanding of the classic game by uncovering strategies that provide a unilateral advantage to sentient players pitted against unwitting opponents. However, strategies in the prisoner's dilemma game are only two strategies. Are there these results for general multi-strategy games? To address this question, the paper develops a theory for zero-determinant strategies for multi-strategy games, with any number of strategies. The analytical results exhibit a similar yet different scenario to the case of two-strategy games. Zero-determinant strategies in iterated prisoner's dilemma can be seen as degenerate case of our results. The results are also applied to the snowdrift game, the hawk-dove game and the chicken game.