OpenRaiser/Intern-Atlas huggingface dataset:
Solving Big Data Challenges for Enterprise Application Performance Management
Venue: arXiv cs.DB 2012
Year: 2012

As the complexity of enterprise systems increases, the need for monitoring and analyzing such systems also grows. A number of companies have built sophisticated monitoring tools that go far beyond simple resource utilization reports. For example, based on instrumentation and specialized APIs, it is now possible to monitor single method invocations and trace individual transactions across geographically distributed systems. This high-level of detail enables more precise forms of analysis and prediction but comes at the price of high data rates (i.e., big data). To maximize the benefit of data monitoring, the data has to be stored for an extended period of time for ulterior analysis. This new wave of big data analytics imposes new challenges especially for the application performance monitoring systems. The monitoring data has to be stored in a system that can sustain the high data rates and at the same time enable an up-to-date view of the underlying infrastructure. With the advent of modern key-value stores, a variety of data storage systems have emerged that are built with a focus on scalability and high data rates as predominant in this monitoring use case. In this work, we present our experience and a comprehensive performance evaluation of six modern (open-source) data stores in the context of application performance monitoring as part of CA Technologies initiative. We evaluated these systems with data and workloads that can be found in application performance monitoring, as well as, on-line advertisement, power monitoring, and many other use cases. We present our insights not only as performance results but also as lessons learned and our experience relating to the setup and configuration complexity of these data stores in an industry setting.
A Storage Advisor for Hybrid-Store Databases
Venue: arXiv cs.DB 2012
Year: 2012

With the SAP HANA database, SAP offers a high-performance in-memory hybrid-store database. Hybrid-store databases---that is, databases supporting row- and column-oriented data management---are getting more and more prominent. While the columnar management offers high-performance capabilities for analyzing large quantities of data, the row-oriented store can handle transactional point queries as well as inserts and updates more efficiently. To effectively take advantage of both stores at the same time the novel question whether to store the given data row- or column-oriented arises. We tackle this problem with a storage advisor tool that supports database administrators at this decision. Our proposed storage advisor recommends the optimal store based on data and query characteristics; its core is a cost model to estimate and compare query execution times for the different stores. Besides a per-table decision, our tool also considers to horizontally and vertically partition the data and manage the partitions on different stores. We evaluated the storage advisor for the use in the SAP HANA database; we show the recommendation quality as well as the benefit of having the data in the optimal store with respect to increased query performance.
MOIST: A Scalable and Parallel Moving Object Indexer with School Tracking
Venue: arXiv cs.DB 2012
Year: 2012

Location-Based Service (LBS) is rapidly becoming the next ubiquitous technology for a wide range of mobile applications. To support applications that demand nearest-neighbor and history queries, an LBS spatial indexer must be able to efficiently update, query, archive and mine location records, which can be in contention with each other. In this work, we propose MOIST, whose baseline is a recursive spatial partitioning indexer built upon BigTable. To reduce update and query contention, MOIST groups nearby objects of similar trajectory into the same school, and keeps track of only the history of school leaders. This dynamic clustering scheme can eliminate redundant updates and hence reduce update latency. To improve history query processing, MOIST keeps some history data in memory, while it flushes aged data onto parallel disks in a locality-preserving way. Through experimental studies, we show that MOIST can support highly efficient nearest-neighbor and history queries and can scale well with an increasing number of users and update frequency.
The Chief Security Officer Problem
Venue: arXiv cs.CR 2012
Year: 2012

This paper presents the chief security officer (CSO) problem, defines its scope, and investigates several important research questions related within the scope. The CSO problem is defined based on the concept of secrecy capacity of wireless communication channels. It is also related to the chief Estimation/Executive Officer (CEO) problem that has been well studied in information theory. The CSO problem consists of a CSO, several agents capable of having two-way communication with the CSO, and a group of eavesdroppers. There are two scenarios in the CSO problem; one in which agents are not allowed to cooperate with one another and the other in which agents are allowed to cooperate with one another. While there are several research questions relevant to the CSO problem, this paper focusses on the following and provides answers: (1) How much information can be exchanged back and forth between the CSO and the agents without leaking any information to the eavesdroppers? (2) What is the power allocation strategy that the CSO needs to follow so as to maximize the secrecy capacity? (3) How can agents cooperate with one another in order to increase the overall secrecy capacity?.
A Novel Architecture for Antenna Arrangement in Wireless Cellular CDMA Systems
Venue: arXiv cs.NI 2012
Year: 2012

Wise arrangement of antennas is critical in wireless cellular systems for both reduction of co-channel interference (CCI) and increase the quality of service (QoS). In this paper, a novel architecture for antenna arrangement in CDMA wireless cellular systems is presented. In this architecture that we called microzone, every cell is divided into three (or more) zones and information transmission in downlink channel is done by an antenna which is placed at the outer region of the related zone. Also, the transmitting signal by the mobile station (MS) in uplink channel is received by all antennas of the related cell. Analytical calculations of the received signal to noise ratio (SIR) and outage probability for both microzone and used architectures show that proposed architecture has better performance in compared with the used architecture. Also, simulation results confirm lower outage probability in uplink channel for microzone architecture.
Efficient transmission of measurement data from FPGA to embedded system via Ethernet link
Venue: arXiv cs.NI 2012
Year: 2012

This paper presents a system consisting of the FPGA IP core, the simple network protocol and the Linux device driver, capable of efficient and reliable data transmission from a low resources FPGA chip to the Linux-based embedded computer system, via a private Ethernet network (consisting of a single segment or a few segments connected via an Ethernet switch). The embedded system may optionally process the acquired data, and distribute them further, using standard network protocols. Proposed design targets cost-efficient multichannel data acquisition systems, in which multiple FPGA based front end boards (FEB) should transmit the stream of acquired data to the computer network, responsible for their final processing and archiving. The presented solution allows to minimize the cost of data concentration due to use of inexpensive Ethernet network infrastructure. The work is mainly focused on minimization of resources consumption in the FPGA, and minimization of acknowledge latency in the Linux based system - which allows to achieve high throughput in spite of use of inexpensive FPGA chips with small internal memory.
Network-based information filtering algorithms: ranking and recommendation
Venue: arXiv cs.SI 2012
Year: 2012

After the Internet and the World Wide Web have become popular and widely-available, the electronically stored online interactions of individuals have fast emerged as a challenge for researchers and, perhaps even faster, as a source of valuable information for entrepreneurs. We now have detailed records of informal friendship relations in social networks, purchases on e-commerce sites, various sorts of information being sent from one user to another, online collections of web bookmarks, and many other data sets that allow us to pose questions that are of interest from both academical and commercial point of view. For example, which other users of a social network you might want to be friend with? Which other items you might be interested to purchase? Who are the most influential users in a network? Which web page you might want to visit next? All these questions are not only interesting per se but the answers to them may help entrepreneurs provide better service to their customers and, ultimately, increase their profits.
A Type-Safe Model of Adaptive Object Groups
Venue: arXiv cs.PL 2012
Year: 2012

Services are autonomous, self-describing, technology-neutral software units that can be described, published, discovered, and composed into software applications at runtime. Designing software services and composing services in order to form applications or composite services requires abstractions beyond those found in typical object-oriented programming languages. This paper explores service-oriented abstractions such as service adaptation, discovery, and querying in an object-oriented setting. We develop a formal model of adaptive object-oriented groups which offer services to their environment. These groups fit directly into the object-oriented paradigm in the sense that they can be dynamically created, they have an identity, and they can receive method calls. In contrast to objects, groups are not used for structuring code. A group exports its services through interfaces and relies on objects to implement these services. Objects may join or leave different groups. Groups may dynamically export new interfaces, they support service discovery, and they can be queried at runtime for the interfaces they support. We define an operational semantics and a static type system for this model of adaptive object groups, and show that well-typed programs do not cause method-not-understood errors at runtime.
A Case Study on Formal Verification of Self-Adaptive Behaviors in a Decentralized System
Venue: arXiv cs.SE 2012
Year: 2012

Self-adaptation is a promising approach to manage the complexity of modern software systems. A self-adaptive system is able to adapt autonomously to internal dynamics and changing conditions in the environment to achieve particular quality goals. Our particular interest is in decentralized self-adaptive systems, in which central control of adaptation is not an option. One important challenge in self-adaptive systems, in particular those with decentralized control of adaptation, is to provide guarantees about the intended runtime qualities. In this paper, we present a case study in which we use model checking to verify behavioral properties of a decentralized self-adaptive system. Concretely, we contribute with a formalized architecture model of a decentralized traffic monitoring system and prove a number of self-adaptation properties for flexibility and robustness. To model the main processes in the system we use timed automata, and for the specification of the required properties we use timed computation tree logic. We use the Uppaal tool to specify the system and verify the flexibility and robustness properties.
Parameter-independent Iterative Approximate Byzantine Consensus
Venue: arXiv cs.DC 2012
Year: 2012

In this work, we explore iterative approximate Byzantine consensus algorithms that do not make explicit use of the global parameter of the graph, i.e., the upper-bound on the number of faults, f.
PIRATTE: Proxy-based Immediate Revocation of ATTribute-based Encryption
Venue: arXiv cs.CR 2012
Year: 2012

Access control to data in traditional enterprises is typically enforced through reference monitors. However, as more and more enterprise data is outsourced, trusting third party storage servers is getting challenging. As a result, cryptography, specifically Attribute-based encryption (ABE) is getting popular for its expressiveness. The challenge of ABE is revocation. To address this challenge, we propose PIRATTE, an architecture that supports fine-grained access control policies and dynamic group membership. PIRATTE is built using attribute-based encryption; a key and novel feature of our architecture, however, is that it is possible to remove access from a user without issuing new keys to other users or re-encrypting existing ciphertexts. We achieve this by introducing a proxy that participates in the decryption process and enforces revocation constraints. The proxy is minimally trusted and cannot decrypt ciphertexts or provide access to previously revoked users. We describe the PIRATTE construction and provide a security analysis along with performance evaluation.We also describe an architecture for online social network that can use PIRATTE, and prototype application of PIRATTE on Facebook.
Efficient Private Distributed Computation on Unbounded Input Streams
Venue: arXiv cs.DC 2012
Year: 2012

In the problem of swarm computing, $n$ agents wish to securely and distributively perform a computation on common inputs, in such a way that even if the entire memory contents of some of them are exposed, no information is revealed about the state of the computation. Recently, Dolev, Garay, Gilboa and Kolesnikov [ICS 2011] considered this problem in the setting of information-theoretic security, showing how to perform such computations on input streams of unbounded length. The cost of their solution, however, is exponential in the size of the Finite State Automaton (FSA) computing the function. In this work we are interested in efficient computation in the above model, at the expense of minimal additional assumptions. Relying on the existence of one-way functions, we show how to process a priori unbounded inputs (but of course, polynomial in the security parameter) at a cost linear in $m$, the number of FSA states. In particular, our algorithms achieve the following: * In the case of $(n,n)$-reconstruction (i.e. in which all $n$ agents participate in reconstruction of the distributed computation) and at most $n-1$ agents are corrupted, the agent storage, the time required to process each input symbol and the time complexity for reconstruction are all $O(mn)$. * In the case of $(t+1,n)$-reconstruction (where only $t+1$ agents take part in the reconstruction) and at most $t$ agents are corrupted, the agents' storage and time required to process each input symbol are $O(m{n-1 \choose t-1})$. The complexity of reconstruction is $O(m(t+1))$.
Parallel ACO with a Ring Neighborhood for Dynamic TSP
Venue: arXiv cs.AI 2012
Year: 2012

The current paper introduces a new parallel computing technique based on ant colony optimization for a dynamic routing problem. In the dynamic traveling salesman problem the distances between cities as travel times are no longer fixed. The new technique uses a parallel model for a problem variant that allows a slight movement of nodes within their Neighborhoods. The algorithm is tested with success on several large data sets.
On Bringer-Chabanne EPIR Protocol for Polynomial Evaluation
Venue: arXiv cs.CR 2012
Year: 2012

Extended private information retrieval (EPIR) was defined by \cite{BCPT07} at CANS'07 and generalized by \cite{BC09} at AFRICACRYPT'09. In the generalized setting, EPIR allows a user to evaluate a function on a database block such that the database can learn neither which function has been evaluated nor on which block the function has been evaluated and the user learns no more information on the database blocks except for the expected result. An EPIR protocol for evaluating polynomials over a finite field $L$ was proposed by Bringer and Chabanne in \cite{BC09}. We show that the protocol does not satisfy the correctness requirement as they have claimed. In particular, we show that it does not give the user the expected result with large probability if one of the coefficients of the polynomial to be evaluated is primitive in $L$ and the others belong to the prime subfield of $L$.
Faster Clustering via Preprocessing
Venue: arXiv cs.DS 2012
Year: 2012

We examine the efficiency of clustering a set of points, when the encompassing metric space may be preprocessed in advance. In computational problems of this genre, there is a first stage of preprocessing, whose input is a collection of points $M$; the next stage receives as input a query set $Q\subset M$, and should report a clustering of $Q$ according to some objective, such as 1-median, in which case the answer is a point $a\in M$ minimizing $\sum_{q\in Q} d_M(a,q)$. We design fast algorithms that approximately solve such problems under standard clustering objectives like $p$-center and $p$-median, when the metric $M$ has low doubling dimension. By leveraging the preprocessing stage, our algorithms achieve query time that is near-linear in the query size $n=|Q|$, and is (almost) independent of the total number of points $m=|M|$.
Dependence and Independence
Venue: arXiv cs.LO 2012
Year: 2012

We introduce an atomic formula intuitively saying that given variables are independent from given other variables if a third set of variables is kept constant. We contrast this with dependence logic. We show that our independence atom gives rise to a natural logic capable of formalizing basic intuitions about independence and dependence.
Support Recovery with Sparsely Sampled Free Random Matrices
Venue: arXiv cs.IT 2012
Year: 2012

Consider a Bernoulli-Gaussian complex $n$-vector whose components are $V_i = X_i B_i$, with $X_i \sim \Cc\Nc(0,\Pc_x)$ and binary $B_i$ mutually independent and iid across $i$. This random $q$-sparse vector is multiplied by a square random matrix $\Um$, and a randomly chosen subset, of average size $n p$, $p \in [0,1]$, of the resulting vector components is then observed in additive Gaussian noise. We extend the scope of conventional noisy compressive sampling models where $\Um$ is typically %A16 the identity or a matrix with iid components, to allow $\Um$ satisfying a certain freeness condition. This class of matrices encompasses Haar matrices and other unitarily invariant matrices. We use the replica method and the decoupling principle of Guo and Verdú, as well as a number of information theoretic bounds, to study the input-output mutual information and the support recovery error rate in the limit of $n \to \infty$. We also extend the scope of the large deviation approach of Rangan, Fletcher and Goyal and characterize the performance of a class of estimators encompassing thresholded linear MMSE and $\ell_1$ relaxation.
On the Peak-to-Average Power Ratio Reduction Problem for Orthogonal Transmission Schemes
Venue: arXiv cs.IT 2012
Year: 2012

High peak values of transmission signals in wireless communication systems lead to wasteful energy consumption and out-of-band radiation. However, reducing peak values generally comes at the cost some other resource. We provide a theoretical contribution towards understanding the relationship between peak value reduction and the resulting cost in information rates. In particular, we address the relationship between peak values and the proportion of transmission signals allocated for information transmission when using a strategy known as tone reservation. We show that when using tone reservation in both OFDM and DS-CDMA systems, if a Peak-to-Average Power Ratio criterion is always satisfied, then the proportion of transmission signals that may be allocated for information transmission must tend to zero. We investigate properties of these two systems for sets of both finite and infinite cardinalities. We present properties that OFDM and DS-CDMA share in common as well as ways in which they fundamentally differ.
Data mining the MNC like internal co-opetition duality in a university context
Venue: arXiv cs.SI 2012
Year: 2012

The goal of the paper is to quantify the simultaneous competition and cooperation that takes place in organizations. As the concepts seem to be dichotomous opposites at first, the term internal coopetition duality is put forth. Parallels are drawn between coopetitive processes in big multinational corporations (MNCs) and these taking place in universities, also the structural solutions used in both are analyzed. Data mining is used while looking at how specializations inside the university are in competition for better students. We look at the profiles that students have and find natural divisions between the specializations, by applying graph theory and modularity algorithms for community detection. The competitive position of the specializations is evident in the average grades of the detected communities. The ratio of intercommunity ties to intracommunity ties (conductance) quantifies the cooperative stance, though, as students with similar profiles express linkages in the curricula; and the choices regarding career development undertaken become evident. Managerial implications discussed include the imperative for actively managing and financially rewarding the outcomes of the coopetitive duality.
Are You Imitating Me? Unsupervised Sparse Modeling for Group Activity Analysis from a Single Video
Venue: arXiv cs.CV 2012
Year: 2012

A framework for unsupervised group activity analysis from a single video is here presented. Our working hypothesis is that human actions lie on a union of low-dimensional subspaces, and thus can be efficiently modeled as sparse linear combinations of atoms from a learned dictionary representing the action's primitives. Contrary to prior art, and with the primary goal of spatio-temporal action grouping, in this work only one single video segment is available for both unsupervised learning and analysis without any prior training information. After extracting simple features at a single spatio-temporal scale, we learn a dictionary for each individual in the video during each short time lapse. These dictionaries allow us to compare the individuals' actions by producing an affinity matrix which contains sufficient discriminative information about the actions in the scene leading to grouping with simple and efficient tools. With diverse publicly available real videos, we demonstrate the effectiveness of the proposed framework and its robustness to cluttered backgrounds, changes of human appearance, and action variability.
Coded Path Protection Part 1: Efficient Conversion of Sharing to Coding
Venue: arXiv cs.NI 2012
Year: 2012

Link failures in wide area networks are common and cause significant data losses. Mesh-based protection schemes offer high capacity efficiency but they are slow and require complex signaling. Additionally, real-time reconfigurations of cross-connects threaten their transmission integrity. On the other hand, there are other schemes that are proactive. Proactivity results in higher restoration speed, lower signaling complexity, and higher transmission integrity. This paper introduces a coding-based proactive protection scheme, named Coded Path Protection (CPP). In CPP, a backup stream of the primary data is encoded with other data streams, resulting in capacity savings. In addition to a systematic approach of building valid coding structures, this paper presents an optimal and simple capacity placement and coding group formation algorithm. The algorithm converts the sharing structure of any solution of a Shared Path Protection (SPP) technique into a coding structure with minimum extra capacity. We conducted quantitative and qualitative comparisons of our technique with the SPP. Simulation results confirm that CPP provides faster link failure recovery than SPP while it incurs marginal extra capacity beyond that of SPP. In this Part 1 of the paper, we describe the theory and an algorithm for converting a given SPP solution into a CPP solution.