OpenRaiser/Intern-Atlas huggingface dataset:
Heterogeneous Differential Privacy
Venue: arXiv cs.CR 2015
Year: 2015

The massive collection of personal data by personalization systems has rendered the preservation of privacy of individuals more and more difficult. Most of the proposed approaches to preserve privacy in personalization systems usually address this issue uniformly across users, thus ignoring the fact that users have different privacy attitudes and expectations (even among their own personal data). In this paper, we propose to account for this non-uniformity of privacy expectations by introducing the concept of heterogeneous differential privacy. This notion captures both the variation of privacy expectations among users as well as across different pieces of information related to the same user. We also describe an explicit mechanism achieving heterogeneous differential privacy, which is a modification of the Laplacian mechanism by Dwork, McSherry, Nissim, and Smith. In a nutshell, this mechanism achieves heterogeneous differential privacy by manipulating the sensitivity of the function using a linear transformation on the input domain. Finally, we evaluate on real datasets the impact of the proposed mechanism with respect to a semantic clustering task. The results of our experiments demonstrate that heterogeneous differential privacy can account for different privacy attitudes while sustaining a good level of utility as measured by the recall for the semantic clustering task.
Common neighbours and the local-community-paradigm for link prediction in bipartite networks
Venue: arXiv cs.SI 2015
Year: 2015

Bipartite networks are powerful descriptions of complex systems characterized by two different classes of nodes and connections allowed only across but not within the two classes. Surprisingly, current complex network theory presents a theoretical bottle-neck: a general framework for local-based link prediction directly in the bipartite domain is missing. Here, we overcome this theoretical obstacle and present a formal definition of common neighbour index (CN) and local-community-paradigm (LCP) for bipartite networks. As a consequence, we are able to introduce the first node-neighbourhood-based and LCP-based models for topological link prediction that utilize the bipartite domain. We performed link prediction evaluations in several networks of different size and of disparate origin, including technological, social and biological systems. Our models significantly improve topological prediction in many bipartite networks because they exploit local physical driving-forces that participate in the formation and organization of many real-world bipartite networks. Furthermore, we present a local-based formalism that allows to intuitively implement neighbourhood-based link prediction entirely in the bipartite domain.
Theory of Semi-Instantiation in Abstract Argumentation
Venue: arXiv cs.AI 2015
Year: 2015

We study instantiated abstract argumentation frames of the form $(S,R,I)$, where $(S,R)$ is an abstract argumentation frame and where the arguments $x$ of $S$ are instantiated by $I(x)$ as well formed formulas of a well known logic, for example as Boolean formulas or as predicate logic formulas or as modal logic formulas. We use the method of conceptual analysis to derive the properties of our proposed system. We seek to define the notion of complete extensions for such systems and provide algorithms for finding such extensions. We further develop a theory of instantiation in the abstract, using the framework of Boolean attack formations and of conjunctive and disjunctive attacks. We discuss applications and compare critically with the existing related literature.
Non-Preemptive Scheduling on Machines with Setup Times
Venue: arXiv cs.DS 2015
Year: 2015

Consider the problem in which n jobs that are classified into k types are to be scheduled on m identical machines without preemption. A machine requires a proper setup taking s time units before processing jobs of a given type. The objective is to minimize the makespan of the resulting schedule. We design and analyze an approximation algorithm that runs in time polynomial in n, m and k and computes a solution with an approximation factor that can be made arbitrarily close to 3/2.
Shape Representation and Classification through Pattern Spectrum and Local Binary Pattern - A Decision Level Fusion Approach
Venue: arXiv cs.CV 2015
Year: 2015

In this paper, we present a decision level fused local Morphological Pattern Spectrum(PS) and Local Binary Pattern (LBP) approach for an efficient shape representation and classification. This method makes use of Earth Movers Distance(EMD) as the measure in feature matching and shape retrieval process. The proposed approach has three major phases : Feature Extraction, Construction of hybrid spectrum knowledge base and Classification. In the first phase, feature extraction of the shape is done using pattern spectrum and local binary pattern method. In the second phase, the histograms of both pattern spectrum and local binary pattern are fused and stored in the knowledge base. In the third phase, the comparison and matching of the features, which are represented in the form of histograms, is done using Earth Movers Distance(EMD) as metric. The top-n shapes are retrieved for each query shape. The accuracy is tested by means of standard Bulls eye score method. The experiments are conducted on publicly available shape datasets like Kimia-99, Kimia-216 and MPEG-7. The comparative study is also provided with the well known approaches to exhibit the retrieval accuracy of the proposed approach.
Architectural Adequacy and Evolutionary Adequacy as Characteristics of a Candidate Informational Money
Venue: arXiv cs.CY 2015
Year: 2015

For money-like informational commodities the notions of architectural adequacy and evolutionary adequacy are proposed as the first two stages of a moneyness maturity hierarchy. Then three classes of informational commodities are distinguished: exclusively informational commodities, strictly informational commodities, and ownable informational commodities. For each class money-like instances of that commodity class, as well as monies of that class may exist. With the help of these classifications and making use of previous assessments of Bitcoin, it is argued that at this stage Bitcoin is unlikely ever to evolve into a money. Assessing the evolutionary adequacy of Bitcoin is perceived in terms of a search through its design hull for superior design alternatives. An extensive comparison is made between the search for superior design alternatives to Bitcoin and the search for design alternatives to a specific and unconventional view on the definition of fractions.
The DIR Net: A Distributed System for Detection, Isolation, and Recovery
Venue: arXiv cs.DC 2015
Year: 2015

This document describes the DIR net, a distributed environment which is part of the EFTOS fault tolerance framework. The DIR net is a system consisting of two components, called DIR Manager (or, shortly, the manager) and DIR Backup Agent (shortly, the backup). One manager and a set of backups is located in the system to be `guarded', one component per node. At this point the DIR net weaves a web which substantially does two things: 1) makes itself tolerant to a number of possible faults, and 2) gathers information pertaining the run of the user application. As soon as an error occurs within the DIR net, the system executes built-in recovery actions that allow itself to continue processing despite a number of hardware/software faults, possibly doing a graceful degradation of its features; when an error occurs in the user application, the DIR net, by means of custom- and user-defined detection tools, is informed of such events and runs one or more recovery strategies, both built-in and coded by the user using an ancillary compile-time tool, the rl translator. Such tools translates the user-defined strategies into a binary `R-code', i.e., a pseudo-code interpreted by a special component of the DIR net, the Recovery Interpreter, rint (in a sense, rint is a r-code virtual machine.) This document describes the generic component of the DIR net, a function which can behave either as manager or as backup.
Greening Multi-Tenant Data Center Demand Response
Venue: arXiv cs.GT 2015
Year: 2015

Data centers have emerged as promising resources for demand response, particularly for emergency demand response (EDR), which saves the power grid from incurring blackouts during emergency situations. However, currently, data centers typically participate in EDR by turning on backup (diesel) generators, which is both expensive and environmentally unfriendly. In this paper, we focus on "greening" demand response in multi-tenant data centers, i.e., colocation data centers, by designing a pricing mechanism through which the data center operator can efficiently extract load reductions from tenants during emergency periods to fulfill energy reduction requirement for EDR. In particular, we propose a pricing mechanism for both mandatory and voluntary EDR programs, ColoEDR, that is based on parameterized supply function bidding and provides provably near-optimal efficiency guarantees, both when tenants are price-taking and when they are price-anticipating. In addition to analytic results, we extend the literature on supply function mechanism design, and evaluate ColoEDR using trace-based simulation studies. These validate the efficiency analysis and conclude that the pricing mechanism is both beneficial to the environment and to the data center operator (by decreasing the need for backup diesel generation), while also aiding tenants (by providing payments for load reductions).
Faster Algorithms for Quantitative Verification in Constant Treewidth Graphs
Venue: arXiv cs.DS 2015
Year: 2015

We consider the core algorithmic problems related to verification of systems with respect to three classical quantitative properties, namely, the mean-payoff property, the ratio property, and the minimum initial credit for energy property. The algorithmic problem given a graph and a quantitative property asks to compute the optimal value (the infimum value over all traces) from every node of the graph. We consider graphs with constant treewidth, and it is well-known that the control-flow graphs of most programs have constant treewidth. Let $n$ denote the number of nodes of a graph, $m$ the number of edges (for constant treewidth graphs $m=O(n)$) and $W$ the largest absolute value of the weights. Our main theoretical results are as follows. First, for constant treewidth graphs we present an algorithm that approximates the mean-payoff value within a multiplicative factor of $ε$ in time $O(n \cdot \log (n/ε))$ and linear space, as compared to the classical algorithms that require quadratic time. Second, for the ratio property we present an algorithm that for constant treewidth graphs works in time $O(n \cdot \log (|a\cdot b|))=O(n\cdot\log (n\cdot W))$, when the output is $\frac{a}{b}$, as compared to the previously best known algorithm with running time $O(n^2 \cdot \log (n\cdot W))$. Third, for the minimum initial credit problem we show that (i) for general graphs the problem can be solved in $O(n^2\cdot m)$ time and the associated decision problem can be solved in $O(n\cdot m)$ time, improving the previous known $O(n^3\cdot m\cdot \log (n\cdot W))$ and $O(n^2 \cdot m)$ bounds, respectively; and (ii) for constant treewidth graphs we present an algorithm that requires $O(n\cdot \log n)$ time, improving the previous known $O(n^4 \cdot \log (n \cdot W))$ bound.
CommentWatcher: An Open Source Web-based platform for analyzing discussions on web forums
Venue: arXiv cs.CL 2015
Year: 2015

We present CommentWatcher, an open source tool aimed at analyzing discussions on web forums. Constructed as a web platform, CommentWatcher features automatic mass fetching of user posts from forum on multiple sites, extracting topics, visualizing the topics as an expression cloud and exploring their temporal evolution. The underlying social network of users is simultaneously constructed using the citation relations between users and visualized as a graph structure. Our platform addresses the issues of the diversity and dynamics of structures of webpages hosting the forums by implementing a parser architecture that is independent of the HTML structure of webpages. This allows easy on-the-fly adding of new websites. Two types of users are targeted: end users who seek to study the discussed topics and their temporal evolution, and researchers in need of establishing a forum benchmark dataset and comparing the performances of analysis tools.
Improving Block-level Efficiency with scsi-mq
Venue: arXiv cs.OS 2015
Year: 2015

Current generation solid-state storage devices are exposing a new bottlenecks in the SCSI and block layers of the Linux kernel, where IO throughput is limited by lock contention, inefficient interrupt handling, and poor memory locality. To address these limitations, the Linux kernel block layer underwent a major rewrite with the blk-mq project to move from a single request queue to a multi-queue model. The Linux SCSI subsystem rework to make use of this new model, known as scsi-mq, has been merged into the Linux kernel and work is underway for dm-multipath support in the upcoming Linux 4.0 kernel. These pieces were necessary to make use of the multi-queue block layer in a Lustre parallel filesystem with high availability requirements. We undertook adding support of the 3.18 kernel to Lustre with scsi-mq and dm-multipath patches to evaluate the potential of these efficiency improvements. In this paper we evaluate the block-level performance of scsi-mq with backing storage hardware representative of a HPC-targerted Lustre filesystem. Our findings show that SCSI write request latency is reduced by as much as 13.6%. Additionally, when profiling the CPU usage of our prototype Lustre filesystem, we found that CPU idle time increased by a factor of 7 with Linux 3.18 and blk-mq as compared to a standard 2.6.32 Linux kernel. Our findings demonstrate increased efficiency of the multi-queue block layer even with disk-based caching storage arrays used in existing parallel filesystems.
Networks of reader and country status: An analysis of Mendeley reader statistics
Venue: arXiv cs.DL 2015
Year: 2015

The number of papers published in journals indexed by the Web of Science core collection is steadily increasing. In recent years, nearly two million new papers were published each year; somewhat more than one million papers when primary research papers are considered only (articles and reviews are the document types where primary research is usually reported or reviewed). However, who reads these papers? More precisely, which groups of researchers from which (self-assigned) scientific disciplines and countries are reading these papers? Is it possible to visualize readership patterns for certain countries, scientific disciplines, or academic status groups? One popular method to answer these questions is a network analysis. In this study, we analyze Mendeley readership data of a set of 1,133,224 articles and 64,960 reviews with publication year 2012 to generate three different kinds of networks: (1) The network based on disciplinary affiliations of Mendeley readers contains four groups: (i) biology, (ii) social science and humanities (including relevant computer science), (iii) bio-medical sciences, and (iv) natural science and engineering. In all four groups, the category with the addition "miscellaneous" prevails. (2) The network of co-readers in terms of professional status shows that a common interest in papers is mainly shared among PhD students, Master's students, and postdocs. (3) The country network focusses on global readership patterns: a group of 53 nations is identified as core to the scientific enterprise, including Russia and China as well as two thirds of the OECD (Organisation for Economic Co-operation and Development) countries.
Synthesis of correct adaptors for protocol enhancement in component-based systems
Venue: arXiv cs.SE 2015
Year: 2015

Adaptation of software components is an important issue in Component Based Software Engineering (CBSE). Building a system from reusable or Commercial-Off-The-Shelf (COTS) components introduces a set of problems, mainly related to compatibility and communication aspects. On one hand, components may have incompatible interaction behavior. This might require to restrict the system's behavior to a subset of safe behaviors. On the other hand, it might be necessary to enhance the current communication protocol. This might require to augment the system's behavior to introduce more sophisticated interactions among components. We address these problems by enhancing our architectural approach which allows for detection and recovery of incompatible interactions by synthesizing a suitable coordinator. Taking into account the specification of the system to be assembled and the specification of the protocol enhancements, our tool (called SYNTHESIS) automatically derives, in a compositional way, the glue code for the set of components. The synthesized glue code implements a software coordinator which avoids incompatible interactions and provides a protocol-enhanced version of the composed system. By using an assume-guarantee technique, we are able to check, in a compositional way, if the protocol enhancement is consistent with respect to the restrictions applied to assure the specified safe behaviors.
Retrospective Interference Alignment for Two-Cell Uplink MIMO Cellular Networks with Delayed CSIT
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, we propose a new retrospective interference alignment for two-cell multiple-input multiple-output (MIMO) interfering multiple access channels (IMAC) with the delayed channel state information at the transmitters (CSIT). It is shown that having delayed CSIT can strictly increase the sum-DoF compared to the case of no CSIT. The key idea is to align multiple interfering signals from adjacent cells onto a small dimensional subspace over time by fully exploiting the previously received signals as side information with outdated CSIT in a distributed manner. Remarkably, we show that the retrospective interference alignment can achieve the optimal sum-DoF in the context of two-cell two-user scenario by providing a new outer bound.
On the adaptation of context-aware services
Venue: arXiv cs.SE 2015
Year: 2015

Ubiquitous networking empowered by Beyond 3G networking makes it possible for mobile users to access networked software services across heterogeneous infrastructures by resource-constrained devices. Heterogeneity and device limitedness creates serious problems for the development and deployment of mobile services that are able to run properly on the execution context and are able to ensures that users experience the "best" Quality of Service possible according to their needs and specific contexts of use. To face these problems the concept of adaptable service is increasingly emerging in the software community. In this paper we describe how CHAMELEON, a declarative framework for tailoring adaptable services, is used within the IST PLASTIC project whose goal is the rapid and easy development/deployment of self-adapting services for B3G networks.
Can Machines Truly Think
Venue: arXiv cs.AI 2015
Year: 2015

Can machines truly think? This question and its answer have many implications that depend, in large part, on any number of assumptions underlying how the issue has been addressed or considered previously. A crucial question, and one that is almost taken for granted, is the starting point for this discussion: Can "thought" be achieved or emulated by algorithmic procedures?
Dual Rate Control for Security in Cyber-physical Systems
Venue: arXiv cs.SY 2015
Year: 2015

We consider malicious attacks on actuators and sensors of a feedback system which can be modeled as additive, possibly unbounded, disturbances at the digital (cyber) part of the feedback loop. We precisely characterize the role of the unstable poles and zeros of the system in the ability to detect stealthy attacks in the context of the sampled data implementation of the controller in feedback with the continuous (physical) plant. We show that, if there is a single sensor that is guaranteed to be secure and the plant is observable from that sensor, then there exist a class of multirate sampled data controllers that ensure that all attacks remain detectable. These dual rate controllers are sampling the output faster than the zero order hold rate that operates on the control input and as such, they can even provide better nominal performance than single rate, at the price of higher sampling of the continuous output.
Nearly Optimal Deterministic Algorithm for Sparse Walsh-Hadamard Transform
Venue: arXiv cs.IT 2015
Year: 2015

For every fixed constant $α> 0$, we design an algorithm for computing the $k$-sparse Walsh-Hadamard transform of an $N$-dimensional vector $x \in \mathbb{R}^N$ in time $k^{1+α} (\log N)^{O(1)}$. Specifically, the algorithm is given query access to $x$ and computes a $k$-sparse $\tilde{x} \in \mathbb{R}^N$ satisfying $\|\tilde{x} - \hat{x}\|_1 \leq c \|\hat{x} - H_k(\hat{x})\|_1$, for an absolute constant $c > 0$, where $\hat{x}$ is the transform of $x$ and $H_k(\hat{x})$ is its best $k$-sparse approximation. Our algorithm is fully deterministic and only uses non-adaptive queries to $x$ (i.e., all queries are determined and performed in parallel when the algorithm starts). An important technical tool that we use is a construction of nearly optimal and linear lossless condensers which is a careful instantiation of the GUV condenser (Guruswami, Umans, Vadhan, JACM 2009). Moreover, we design a deterministic and non-adaptive $\ell_1/\ell_1$ compressed sensing scheme based on general lossless condensers that is equipped with a fast reconstruction algorithm running in time $k^{1+α} (\log N)^{O(1)}$ (for the GUV-based condenser) and is of independent interest. Our scheme significantly simplifies and improves an earlier expander-based construction due to Berinde, Gilbert, Indyk, Karloff, Strauss (Allerton 2008). Our methods use linear lossless condensers in a black box fashion; therefore, any future improvement on explicit constructions of such condensers would immediately translate to improved parameters in our framework (potentially leading to $k (\log N)^{O(1)}$ reconstruction time with a reduced exponent in the poly-logarithmic factor, and eliminating the extra parameter $α$). Finally, by allowing the algorithm to use randomness, while still using non-adaptive queries, the running time of the algorithm can be improved to $\tilde{O}(k \log^3 N)$.
A Characterization of Consistent Digital Line Segments in Two Dimensions
Venue: arXiv cs.CG 2015
Year: 2015

Our concern is the digitalization of line segments in two dimensions as considered by Chun et al.[Discrete Comput. Geom., 2009] and Christ et al.[Discrete Comput. Geom., 2012]. The key property that differentiates the research of Chun et al. and Christ et al. from other research in digital line segment construction is that the intersection of any two segments must be connected. Such a system of segments is called a consistent digital line segments system (CDS). Chun et al. give a construction for all segments in higher dimensions that share a common endpoint (called consistent digital rays (CDR)) that has asymptotically optimal Hausdorff distance, and Christ et al. give a complete CDS in two dimensions with optimal Hausdorff distance. Christ et al. also give a characterization of CDRs in two dimensions, and they leave open the question on how to characterize CDSes in two dimensions. In this paper, we answer the most important open question regarding CDSes in two dimensions by giving the characterization asked for by Christ et al. We obtain the characterization by giving a set of necessary and sufficient conditions that a CDS must satisfy.