OpenRaiser/Intern-Atlas huggingface dataset:
Cloud Computing Avoids Downfall of Application Service Providers
Venue: arXiv cs.DC 2015
Year: 2015

Businesses have become dependent on ever increasing amounts of electronic information and rapid transaction speeds. Experts such as Diffie speculate that the end of isolated computing is at hand, and that within the next decade most businesses will have made the shift to utility computing. In order to cut costs while still implementing increasingly complex Information Technology services, many companies turned to Application Service Providers (ASPs). Due to poor business models, over competition, and poor internet availability and bandwidth, many ASPs failed with the dot com crash. Other ASPs, however, who embraced web services architecture and true internet delivery were well placed as early cloud adopters. With the expanded penetration and bandwidth of internet services today, better business plans, and a wide divergence of offering, cloud computing is avoiding the ASP downfall, and is positioned to emerge as an enduring paradigm in computing
Decoding Hidden Markov Models Faster Than Viterbi Via Online Matrix-Vector (max, +)-Multiplication
Venue: arXiv cs.LG 2015
Year: 2015

In this paper, we present a novel algorithm for the maximum a posteriori decoding (MAPD) of time-homogeneous Hidden Markov Models (HMM), improving the worst-case running time of the classical Viterbi algorithm by a logarithmic factor. In our approach, we interpret the Viterbi algorithm as a repeated computation of matrix-vector $(\max, +)$-multiplications. On time-homogeneous HMMs, this computation is online: a matrix, known in advance, has to be multiplied with several vectors revealed one at a time. Our main contribution is an algorithm solving this version of matrix-vector $(\max,+)$-multiplication in subquadratic time, by performing a polynomial preprocessing of the matrix. Employing this fast multiplication algorithm, we solve the MAPD problem in $O(mn^2/ \log n)$ time for any time-homogeneous HMM of size $n$ and observation sequence of length $m$, with an extra polynomial preprocessing cost negligible for $m > n$. To the best of our knowledge, this is the first algorithm for the MAPD problem requiring subquadratic time per observation, under the only assumption -- usually verified in practice -- that the transition probability matrix does not change with time.
Secure Distributed Membership Tests via Secret Sharing: How to Hide Your Hostile Hosts Harnessing Shamir Secret Sharing
Venue: arXiv cs.CR 2015
Year: 2015

Data security and availability for operational use are frequently seen as conflicting goals. Research on searchable encryption and homomorphic encryption are a start, but they typically build from encryption methods that, at best, provide protections based on problems assumed to be computationally hard. By contrast, data encoding methods such as secret sharing provide information-theoretic data protections. Archives that distribute data using secret sharing can provide data protections that are resilient to malicious insiders, compromised systems, and untrusted components. In this paper, we create the Serial Interpolation Filter, a method for storing and interacting with sets of data that are secured and distributed using secret sharing. We provide the ability to operate over set-oriented data distributed across multiple repositories without exposing the original data. Furthermore, we demonstrate the security of our method under various attacker models and provide protocol extensions to handle colluding attackers. The Serial Interpolation Filter provides information-theoretic protections from a single attacker and computationally hard protections from colluding attackers.
SQL Queries for Declarative Process Mining on Event Logs of Relational Databases
Venue: arXiv cs.DB 2015
Year: 2015

Flexible business processes can often be modelled more easily using a declarative rather than a procedural modelling approach. Process mining aims at automating the discovery of business process models. Existing declarative process mining approaches either suffer performance issues with real-life event logs or limit their expressiveness to a specific set of constaint types. Lately, with RelationalXES a relational database architecture for storing event log data has been introduced. In this technical report, we introduce a mining approach that directly works on relational event data by querying the log with conventional SQL. We provide a list of SQL queries for discovering a set of commonly used and mined process constraints.
On the Energy Efficiency Prospects of Network Function Virtualization
Venue: arXiv cs.NI 2015
Year: 2015

Network Function Virtualization (NFV) has recently received significant attention as an innovative way of deploying network services. By decoupling network functions from the physical equipment on which they run, NFV has been proposed as passage towards service agility, better time-to-market, and reduced Capital Expenses (CAPEX) and Operating Expenses (OPEX). One of the main selling points of NFV is its promise for better energy efficiency resulting from consolidation of resources as well as their more dynamic utilization. However, there are currently no studies or implementations which attach values to energy savings that can be expected, which could make it hard for Telecommunication Service Providers (TSPs) to make investment decisions. In this paper, we utilize Bell Labs' GWATT tool to estimate the energy savings that could result from the three main NFV use cases Virtualized Evolved Packet Core (VEPC), Virtualized Customer Premises Equipment (VCPE) and Virtualized Radio Access Network (VRAN). We determine that the part of the mobile network with the highest energy utilization prospects is the Evolved Packet Core (EPC) where virtualization of functions leads to a 22% reduction in energy consumption and a 32% enhancement in energy efficiency.
Evaluating Morphological Computation in Muscle and DC-motor Driven Models of Human Hopping
Venue: arXiv cs.AI 2015
Year: 2015

In the context of embodied artificial intelligence, morphological computation refers to processes which are conducted by the body (and environment) that otherwise would have to be performed by the brain. Exploiting environmental and morphological properties is an important feature of embodied systems. The main reason is that it allows to significantly reduce the controller complexity. An important aspect of morphological computation is that it cannot be assigned to an embodied system per se, but that it is, as we show, behavior- and state-dependent. In this work, we evaluate two different measures of morphological computation that can be applied in robotic systems and in computer simulations of biological movement. As an example, these measures were evaluated on muscle and DC-motor driven hopping models. We show that a state-dependent analysis of the hopping behaviors provides additional insights that cannot be gained from the averaged measures alone. This work includes algorithms and computer code for the measures.
NetCodCCN: a Network Coding approach for Content-Centric Networks
Venue: arXiv cs.NI 2015
Year: 2015

Content-Centric Networking (CCN) naturally supports multi-path communication, as it allows the simultaneous use of multiple interfaces (e.g. LTE and WiFi). When multiple sources and multiple clients are considered, the optimal set of distribution trees should be determined in order to optimally use all the available interfaces. This is not a trivial task, as it is a computationally intense procedure that should be done centrally. The need for central coordination can be removed by employing network coding, which also offers improved resiliency to errors and large throughput gains. In this paper, we propose NetCodCCN, a protocol for integrating network coding in CCN. In comparison to previous works proposing to enable network coding in CCN, NetCodCCN permit Interest aggregation and Interest pipelining, which reduce the data retrieval times. The experimental evaluation shows that the proposed protocol leads to significant improvements in terms of content retrieval delay compared to the original CCN. Our results demonstrate that the use of network coding adds robustness to losses and permits to exploit more efficiently the available network resources. The performance gains are verified for content retrieval in various network scenarios.
Managing Support Requests in Open Source Software Project: The Role of Online Forums
Venue: arXiv cs.SE 2015
Year: 2015

The use of free and open source software is gaining momentum due to the ever increasing availability and use of the Internet. Organizations are also now adopting open source software, despite some reservations in particular regarding the provision and availability of support. One of the greatest concerns about free and open source software is the availability of post release support and the handling of for support. A common belief is that there is no appropriate support available for this class of software, while an alternative argument is that due to the active involvement of Internet users in online forums, there is in fact a large resource available that communicates and manages the management of support requests. The research model of this empirical investigation establishes and studies the relationship between open source software support requests and online public forums. The results of this empirical study provide evidence about the realities of support that is present in open source software projects. We used a dataset consisting of 616 open source software projects covering a broad range of categories in this investigation. The results show that online forums play a significant role in managing support requests in open source software, thus becoming a major source of assistance in maintenance of the open source projects.
Joint Group Testing of Time-varying Faulty Sensors and System State Estimation in Large Sensor Networks
Venue: arXiv cs.SY 2015
Year: 2015

The problem of faulty sensor detection is investigated in large sensor networks where the sensor faults are sparse and time-varying, such as those caused by attacks launched by an adversary. Group testing and the Kalman filter are designed jointly to perform real time system state estimation and time-varying faulty sensor detection with a small number of tests. Numerical results show that the faulty sensors are efficiently detected and removed, and the system state estimation performance is significantly improved via the proposed method. Compared with an approach that tests sensors one by one, the proposed approach reduces the number of tests significantly while maintaining a similar fault detection performance.
Joint Source Selection and Data Extrapolation in Social Sensing for Disaster Response
Venue: arXiv cs.SI 2015
Year: 2015

This paper complements the large body of social sensing literature by developing means for augmenting sensing data with inference results that "fill-in" missing pieces. It specifically explores the synergy between (i) inference techniques used for filling-in missing pieces and (ii) source selection techniques used to determine which pieces to retrieve in order to improve inference results. We focus on prediction in disaster scenarios, where disruptive trend changes occur. We first discuss our previous conference study that compared a set of prediction heuristics and developed a hybrid prediction algorithm. We then enhance the prediction scheme by considering algorithms for sensor selection that improve inference quality. Our proposed source selection and extrapolation algorithms are tested using data collected during the New York City crisis in the aftermath of Hurricane Sandy in November 2012. The evaluation results show that consistently good predictions are achieved. The work is notable for addressing the bi-modal nature of damage propagation in complex systems subjected to stress, where periods of calm are interspersed with periods of severe change. It is novel in offering a new solution to the problem that jointly leverages source selection and extrapolation components thereby improving the results.
Cell Selection in Wireless Two-Tier Networks: A Context-Aware Matching Game
Venue: arXiv cs.NI 2015
Year: 2015

The deployment of small cell networks is seen as a major feature of the next generation of wireless networks. In this paper, a novel approach for cell association in small cell networks is proposed. The proposed approach exploits new types of information extracted from the users' devices and environment to improve the way in which users are assigned to their serving base stations. Examples of such context information include the devices' screen size and the users' trajectory. The problem is formulated as a matching game with externalities and a new, distributed algorithm is proposed to solve this game. The proposed algorithm is shown to reach a stable matching whose properties are studied. Simulation results show that the proposed context-aware matching approach yields significant performance gains, in terms of the average utility per user, when compared with a classical max-SINR approach.
A connected multidimensional maximum bisection problem
Venue: arXiv cs.DM 2015
Year: 2015

The maximum graph bisection problem is a well known graph partition problem. The problem has been proven to be NP-hard. In the maximum graph bisection problem it is required that the set of vertices is divided into two partition with equal number of vertices, and the weight of the edge cut is maximal. This work introduces a connected multidimensional generalization of the maximum bisection problem. In this problem the weights on edges are vectors of positive numbers rather than numbers and partitions should be connected. A mixed integer linear programming formulation is proposed with the proof of its correctness. The MILP formulation of the problem has polynomial number of variables and constraints.
Almost quadratic gap between partition complexity and query/communication complexity
Venue: arXiv cs.CC 2015
Year: 2015

We show nearly quadratic separations between two pairs of complexity measures: 1. We show that there is a Boolean function $f$ with $D(f)=Ω((D^{sc}(f))^{2-o(1)})$ where $D(f)$ is the deterministic query complexity of $f$ and $D^{sc}$ is the subcube partition complexity of $f$; 2. As a consequence, we obtain that there is a communication task $f(x, y)$ such that $D^{cc}(f)=Ω(\log^{2-o(1)}χ(f))$ where $D^{cc}(f)$ is the deterministic 2-party communication complexity of $f$ (in the standard 2-party model of communication) and $χ(f)$ is the partition number of $f$. Both of those separations are nearly optimal: it is well known that $D(f)=O((D^{sc}(f))^{2})$ and $D^{cc}(f)=O(\log^2χ(f))$.
Querying with Łukasiewicz logic
Venue: arXiv cs.LO 2015
Year: 2015

In this paper we present, by way of case studies, a proof of concept, based on a prototype working on a automotive data set, aimed at showing the potential usefulness of using formulas of Łukasiewicz propositional logic to query databases in a fuzzy way. Our approach distinguishes itself for its stress on the purely linguistic, contraposed with numeric, formulations of queries. Our queries are expressed in the pure language of logic, and when we use (integer) numbers, these stand for shortenings of formulas on the syntactic level, and serve as linguistic hedges on the semantic one. Our case-study queries aim first at showing that each numeric-threshold fuzzy query is simulated by a Łukasiewicz formula. Then they focus on the expressing power of Łukasiewicz logic which easily allows for updating queries by clauses and for modifying them through a potentially infinite variety of linguistic hedges implemented with a uniform syntactic mechanism. Finally we shall hint how, already at propositional level, Łukasiewicz natural semantics enjoys a degree of reflection, allowing to write syntactically simple queries that semantically work as meta-queries weighing the contribution of simpler ones.
Time series analysis of temporal networks
Venue: arXiv cs.SI 2015
Year: 2015

An important feature of all real-world networks is that the network structure changes over time. Due to this dynamic nature, it becomes difficult to propose suitable growth models that can explain the various important characteristic properties of these networks. In fact, in many application oriented studies only knowing these properties is sufficient. We, in this paper show that even if the network structure at a future time point is not available one can still manage to estimate its properties. We propose a novel method to map a temporal network to a set of time series instances, analyze them and using a standard forecast model of time series, try to predict the properties of a temporal network at a later time instance. We mainly focus on the temporal network of human face- to-face contacts and observe that it represents a stochastic process with memory that can be modeled as ARIMA. We use cross validation techniques to find the percentage accuracy of our predictions. An important observation is that the frequency domain properties of the time series obtained from spectrogram analysis could be used to refine the prediction framework by identifying beforehand the cases where the error in prediction is likely to be high. This leads to an improvement of 7.96% (for error level <= 20%) in prediction accuracy on an average across all datasets. As an application we show how such prediction scheme can be used to launch targeted attacks on temporal networks.
ASIST: Automatic Semantically Invariant Scene Transformation
Venue: arXiv cs.CV 2015
Year: 2015

We present ASIST, a technique for transforming point clouds by replacing objects with their semantically equivalent counterparts. Transformations of this kind have applications in virtual reality, repair of fused scans, and robotics. ASIST is based on a unified formulation of semantic labeling and object replacement; both result from minimizing a single objective. We present numerical tools for the efficient solution of this optimization problem. The method is experimentally assessed on new datasets of both synthetic and real point clouds, and is additionally compared to two recent works on object replacement on data from the corresponding papers.
Unsupervised comparable corpora preparation and exploration for bi-lingual translation equivalents
Venue: arXiv cs.CL 2015
Year: 2015

The multilingual nature of the world makes translation a crucial requirement today. Parallel dictionaries constructed by humans are a widely-available resource, but they are limited and do not provide enough coverage for good quality translation purposes, due to out-of-vocabulary words and neologisms. This motivates the use of statistical translation systems, which are unfortunately dependent on the quantity and quality of training data. Such systems have a very limited availability especially for some languages and very narrow text domains. In this research we present our improvements to current comparable corpora mining methodologies by re- implementation of the comparison algorithms (using Needleman-Wunch algorithm), introduction of a tuning script and computation time improvement by GPU acceleration. Experiments are carried out on bilingual data extracted from the Wikipedia, on various domains. For the Wikipedia itself, additional cross-lingual comparison heuristics were introduced. The modifications made a positive impact on the quality and quantity of mined data and on the translation quality.
A Framework for Computing on Large Dynamic Graphs
Venue: arXiv cs.DC 2015
Year: 2015

This proposal presents a graph computing framework intending to support both online and offline computing on large dynamic graphs efficiently. The framework proposes a new data model to support rich evolving vertex and edge data types. It employs a replica-coherence protocol to improve data locality thus can adapt to data access patterns of different algorithms. A new computing model called protocol dataflow is proposed to implement and integrate various programming models for both online and offline computing on large dynamic graphs. A central topic of the proposal is also the analysis of large real dynamic graphs using our proposed framework. Our goal is to calculate the temporal patterns and properties which emerge when the large graphs keep evolving. Thus we can evaluate the capability of the proposed framework. Key words: Large dynamic graph, programming model, distributed computing.
Red Spider Meets a Rainworm: Conjunctive Query Finite Determinacy Is Undecidable
Venue: arXiv cs.DB 2015
Year: 2015

We solve a well known and long-standing open problem in database theory, proving that Conjunctive Query Finite Determinacy Problem is undecidable. The technique we use builds on the top of our Red Spider method which we developed in our paper [GM15] to show undecidability of the same problem in the "unrestricted case" -- when database instances are allowed to be infinite. We also show a specific instance $Q_0$, ${\cal Q}= \{Q_1, Q_2, \ldots Q_k\}$ such that the set $\cal Q$ of CQs does not determine CQ $Q_0$ but finitely determines it. Finally, we claim that while $Q_0$ is finitely determined by $\cal Q$, there is no FO-rewriting of $Q_0$, with respect to $\cal Q$, and we outline a proof of this claim
A Restricted Visual Turing Test for Deep Scene and Event Understanding
Venue: arXiv cs.CV 2015
Year: 2015

This paper presents a restricted visual Turing test (VTT) for story-line based deep understanding in long-term and multi-camera captured videos. Given a set of videos of a scene (such as a multi-room office, a garden, and a parking lot.) and a sequence of story-line based queries, the task is to provide answers either simply in binary form "true/false" (to a polar query) or in an accurate natural language description (to a non-polar query). Queries, polar or non-polar, consist of view-based queries which can be answered from a particular camera view and scene-centered queries which involves joint inference across different cameras. The story lines are collected to cover spatial, temporal and causal understanding of input videos. The data and queries distinguish our VTT from recently proposed visual question answering in images and video captioning. A vision system is proposed to perform joint video and query parsing which integrates different vision modules, a knowledge base and a query engine. The system provides unified interfaces for different modules so that individual modules can be reconfigured to test a new method. We provide a benchmark dataset and a toolkit for ontology guided story-line query generation which consists of about 93.5 hours videos captured in four different locations and 3,426 queries split into 127 story lines. We also provide a baseline implementation and result analyses.
Want Answers? A Reddit Inspired Study on How to Pose Questions
Venue: arXiv cs.CL 2015
Year: 2015

Questions form an integral part of our everyday communication, both offline and online. Getting responses to our questions from others is fundamental to satisfying our information need and in extending our knowledge boundaries. A question may be represented using various factors such as social, syntactic, semantic, etc. We hypothesize that these factors contribute with varying degrees towards getting responses from others for a given question. We perform a thorough empirical study to measure effects of these factors using a novel question and answer dataset from the website Reddit.com. To the best of our knowledge, this is the first such analysis of its kind on this important topic. We also use a sparse nonnegative matrix factorization technique to automatically induce interpretable semantic factors from the question dataset. We also document various patterns on response prediction we observe during our analysis in the data. For instance, we found that preference-probing questions are scantily answered. Our method is robust to capture such latent response factors. We hope to make our code and datasets publicly available upon publication of the paper.