OpenRaiser/Intern-Atlas huggingface dataset:
From Cooperative Scans to Predictive Buffer Management
Venue: arXiv cs.DB 2012
Year: 2012

In analytical applications, database systems often need to sustain workloads with multiple concurrent scans hitting the same table. The Cooperative Scans (CScans) framework, which introduces an Active Buffer Manager (ABM) component into the database architecture, has been the most effective and elaborate response to this problem, and was initially developed in the X100 research prototype. We now report on the the experiences of integrating Cooperative Scans into its industrial-strength successor, the Vectorwise database product. During this implementation we invented a simpler optimization of concurrent scan buffer management, called Predictive Buffer Management (PBM). PBM is based on the observation that in a workload with long-running scans, the buffer manager has quite a bit of information on the workload in the immediate future, such that an approximation of the ideal OPT algorithm becomes feasible. In the evaluation on both synthetic benchmarks as well as a TPC-H throughput run we compare the benefits of naive buffer management (LRU) versus CScans, PBM and OPT; showing that PBM achieves benefits close to Cooperative Scans, while incurring much lower architectural impact.
The Unified Logging Infrastructure for Data Analytics at Twitter
Venue: arXiv cs.DB 2012
Year: 2012

In recent years, there has been a substantial amount of work on large-scale data analytics using Hadoop-based platforms running on large clusters of commodity machines. A less-explored topic is how those data, dominated by application logs, are collected and structured to begin with. In this paper, we present Twitter's production logging infrastructure and its evolution from application-specific logging to a unified "client events" log format, where messages are captured in common, well-formatted, flexible Thrift messages. Since most analytics tasks consider the user session as the basic unit of analysis, we pre-materialize "session sequences", which are compact summaries that can answer a large class of common queries quickly. The development of this infrastructure has streamlined log collection and data analysis, thereby improving our ability to rapidly experiment and iterate on various aspects of the service.
The Vertica Analytic Database: C-Store 7 Years Later
Venue: arXiv cs.DB 2012
Year: 2012

This paper describes the system architecture of the Vertica Analytic Database (Vertica), a commercialization of the design of the C-Store research prototype. Vertica demonstrates a modern commercial RDBMS system that presents a classical relational interface while at the same time achieving the high performance expected from modern "web scale" analytic systems by making appropriate architectural choices. Vertica is also an instructive lesson in how academic systems research can be directly commercialized into a successful product.
Interactive Analytical Processing in Big Data Systems: A Cross-Industry Study of MapReduce Workloads
Venue: arXiv cs.DB 2012
Year: 2012

Within the past few years, organizations in diverse industries have adopted MapReduce-based systems for large-scale data processing. Along with these new users, important new workloads have emerged which feature many small, short, and increasingly interactive jobs in addition to the large, long-running batch jobs for which MapReduce was originally designed. As interactive, large-scale query processing is a strength of the RDBMS community, it is important that lessons from that field be carried over and applied where possible in this new domain. However, these new workloads have not yet been described in the literature. We fill this gap with an empirical analysis of MapReduce traces from six separate business-critical deployments inside Facebook and at Cloudera customers in e-commerce, telecommunications, media, and retail. Our key contribution is a characterization of new MapReduce workloads which are driven in part by interactive analysis, and which make heavy use of query-like programming frameworks on top of MapReduce. These workloads display diverse behaviors which invalidate prior assumptions about MapReduce such as uniform data access, regular diurnal patterns, and prevalence of large jobs. A secondary contribution is a first step towards creating a TPC-like data processing benchmark for MapReduce.
Building User-defined Runtime Adaptation Routines for Stream Processing Applications
Venue: arXiv cs.DB 2012
Year: 2012

Stream processing applications are deployed as continuous queries that run from the time of their submission until their cancellation. This deployment mode limits developers who need their applications to perform runtime adaptation, such as algorithmic adjustments, incremental job deployment, and application-specific failure recovery. Currently, developers do runtime adaptation by using external scripts and/or by inserting operators into the stream processing graph that are unrelated to the data processing logic. In this paper, we describe a component called orchestrator that allows users to write routines for automatically adapting the application to runtime conditions. Developers build an orchestrator by registering and handling events as well as specifying actuations. Events can be generated due to changes in the system state (e.g., application component failures), built-in system metrics (e.g., throughput of a connection), or custom application metrics (e.g., quality score). Once the orchestrator receives an event, users can take adaptation actions by using the orchestrator actuation APIs. We demonstrate the use of the orchestrator in IBM's System S in the context of three different applications, illustrating application adaptation to changes on the incoming data distribution, to application failures, and on-demand dynamic composition.
Spreaders in the Network SIR Model: An Empirical Study
Venue: arXiv cs.SI 2012
Year: 2012

We use the susceptible-infected-recovered (SIR) model for disease spread over a network, and empirically study how well various centrality measures perform at identifying which nodes in a network will be the best spreaders of disease on 10 real-world networks. We find that the relative performance of degree, shell number and other centrality measures can be sensitive to B, the probability that an infected node will transmit the disease to a susceptible node. We also find that eigenvector centrality performs very well in general for values of B above the epidemic threshold.
A Unified Approach for Modeling and Recognition of Individual Actions and Group Activities
Venue: arXiv cs.CV 2012
Year: 2012

Recognizing group activities is challenging due to the difficulties in isolating individual entities, finding the respective roles played by the individuals and representing the complex interactions among the participants. Individual actions and group activities in videos can be represented in a common framework as they share the following common feature: both are composed of a set of low-level features describing motions, e.g., optical flow for each pixel or a trajectory for each feature point, according to a set of composition constraints in both temporal and spatial dimensions. In this paper, we present a unified model to assess the similarity between two given individual or group activities. Our approach avoids explicit extraction of individual actors, identifying and representing the inter-person interactions. With the proposed approach, retrieval from a video database can be performed through Query-by-Example; and activities can be recognized by querying videos containing known activities. The suggested video matching process can be performed in an unsupervised manner. We demonstrate the performance of our approach by recognizing a set of human actions and football plays.
Delay-Doppler Channel Estimation with Almost Linear Complexity
Venue: arXiv cs.IT 2012
Year: 2012

A fundamental task in wireless communication is Channel Estimation: Compute the channel parameters a signal undergoes while traveling from a transmitter to a receiver. In the case of delay-Doppler channel, a widely used method is the Matched Filter algorithm. It uses a pseudo-random sequence of length N, and, in case of non-trivial relative velocity between transmitter and receiver, its computational complexity is O(N^{2}log(N)). In this paper we introduce a novel approach of designing sequences that allow faster channel estimation. Using group representation techniques we construct sequences, which enable us to introduce a new algorithm, called the flag method, that significantly improves the matched filter algorithm. The flag method finds the channel parameters in O(mNlog(N)) operations, for channel of sparsity m. We discuss applications of the flag method to GPS, radar system, and mobile communication as well.
Radio Frequency Energy Harvesting and Management for Wireless Sensor Networks
Venue: arXiv cs.NI 2012
Year: 2012

Radio Frequency (RF) Energy Harvesting holds a promising future for generating a small amount of electrical power to drive partial circuits in wirelessly communicating electronics devices. Reducing power consumption has become a major challenge in wireless sensor networks. As a vital factor affecting system cost and lifetime, energy consumption in wireless sensor networks is an emerging and active research area. This chapter presents a practical approach for RF Energy harvesting and management of the harvested and available energy for wireless sensor networks using the Improved Energy Efficient Ant Based Routing Algorithm (IEEABR) as our proposed algorithm. The chapter looks at measurement of the RF power density, calculation of the received power, storage of the harvested power, and management of the power in wireless sensor networks. The routing uses IEEABR technique for energy management. Practical and real-time implementations of the RF Energy using Powercast harvesters and simulations using the energy model of our Libelium Waspmote to verify the approach were performed. The chapter concludes with performance analysis of the harvested energy, comparison of IEEABR and other traditional energy management techniques, while also looking at open research areas of energy harvesting and management for wireless sensor networks.
Finding a maximum induced degenerate subgraph faster than 2^n
Venue: arXiv cs.DS 2012
Year: 2012

In this paper we study the problem of finding a maximum induced d-degenerate subgraph in a given n-vertex graph from the point of view of exact algorithms. We show that for any fixed d one can find a maximum induced d-degenerate subgraph in randomized (2-eps_d)^n n^O(1) time, for some constant eps_d>0 depending only on d. Moreover, our algorithm can be used to sample inclusion-wise maximal induced d-degenerate subgraphs in such a manner that every such subgraph is output with probability at least (2-eps_d)^-n; hence, we prove that their number is bounded by (2-eps_d)^n.
On The Secrecy of the Cognitive Interference Channel with Channel State
Venue: arXiv cs.IT 2012
Year: 2012

In this paper the secrecy problem in the cognitive statedependent interference channel is considered. In this scenario we have a primary and a cognitive transmitter-receiver pairs. The cognitive transmitter has the message of the primary sender as side information. In addition, the state of the channel is known at the cognitive encoder. So, the cognitive encoder uses this side information to cooperate with the primary transmitter and sends its individual message confidentially. An achievable rate region and an outer bound for the rate region in this channel are derived. The results are extended to the previous works as special cases.
A novel Hopfield neural network approach for minimizing total weighted tardiness of jobs scheduled on identical machines
Venue: arXiv cs.NE 2012
Year: 2012

This paper explores fast, polynomial time heuristic approximate solutions to the NP-hard problem of scheduling jobs on N identical machines. The jobs are independent and are allowed to be stopped and restarted on another machine at a later time. They have well-defined deadlines, and relative priorities quantified by non-negative real weights. The objective is to find schedules which minimize the total weighted tardiness (TWT) of all jobs. We show how this problem can be mapped into quadratic form and present a polynomial time heuristic solution based on the Hopfield Neural Network (HNN) approach. It is demonstrated, through the results of extensive numerical simulations, that this solution outperforms other popular heuristic methods. The proposed heuristic is both theoretically and empirically shown to be scalable to large problem sizes (over 100 jobs to be scheduled), which makes it applicable to grid computing scheduling, arising in fields such as computational biology, chemistry and finance.
Road Pricing for Spreading Peak Travel: Modeling and Design
Venue: arXiv cs.GT 2012
Year: 2012

A case study of the Singapore road network provides empirical evidence that road pricing can significantly affect commuter trip timing behaviors. In this paper, we propose a model of trip timing decisions that reasonably matches the observed commuters' behaviors. Our model explicitly captures the difference in individuals' sensitivity to price, travel time and early or late arrival at destination. New pricing schemes are suggested to better spread peak travel and reduce traffic congestion. Simulation results based on the proposed model are provided in comparison with the real data for the Singapore case study.
Typical $l_1$-recovery limit of sparse vectors represented by concatenations of random orthogonal matrices
Venue: arXiv cs.IT 2012
Year: 2012

We consider the problem of recovering an $N$-dimensional sparse vector $\vm{x}$ from its linear transformation $\vm{y}=\vm{D} \vm{x}$ of $M(< N)$ dimension. Minimizing the $l_{1}$-norm of $\vm{x}$ under the constraint $\vm{y} = \vm{D} \vm{x}$ is a standard approach for the recovery problem, and earlier studies report that the critical condition for typically successful $l_1$-recovery is universal over a variety of randomly constructed matrices $\vm{D}$. For examining the extent of the universality, we focus on the case in which $\vm{D}$ is provided by concatenating $\nb=N/M$ matrices $\vm{O}_{1}, \vm{O}_{2},..., \vm{O}_\nb$ drawn uniformly according to the Haar measure on the $M \times M$ orthogonal matrices. By using the replica method in conjunction with the development of an integral formula for handling the random orthogonal matrices, we show that the concatenated matrices can result in better recovery performance than what the universality predicts when the density of non-zero signals is not uniform among the $\nb$ matrix modules. The universal condition is reproduced for the special case of uniform non-zero signal densities. Extensive numerical experiments support the theoretical predictions.
Implementing Access Control Markov Decision Processes with GLPK/GMPL
Venue: arXiv cs.CR 2012
Year: 2012

In a recent approach, we proposed to model an access control mechanism as a Markov Decision Process, thus claiming that in order to make an access control decision, one can use well-defined mechanisms from decision theory. We present in this paper an implementation of such mechanism, using the open-source solver GLPK, and we model the problem in the GMPL language. We illustrate our approach with a simple, yet expressive example, and we show how the variation of some parameters can change the final outcome. In particular, we show that in addition to returning a decision, we can also calculate the value of each decision.
Comparing N-Node Set Importance Representative results with Node Importance Representative results for Categorical Clustering: An exploratory study
Venue: arXiv cs.DB 2012
Year: 2012

The proportionate increase in the size of the data with increase in space implies that clustering a very large data set becomes difficult and is a time consuming process.Sampling is one important technique to scale down the size of dataset and to improve the efficiency of clustering. After sampling allocating unlabeled objects into proper clusters is impossible in the categorical domain.To address the problem, Chen employed a method called MAximal Representative Data Labeling to allocate each unlabeled data point to the appropriate cluster based on Node Importance Representative and N-Node Importance Representative algorithms. This paper took off from Chen s investigation and analyzed and compared the results of NIR and NNIR leading to the conclusion that the two processes contradict each other when it comes to finding the resemblance between an unlabeled data point and a cluster.A new and better way of solving the problem was arrived at that finds resemblance between unlabeled data point within all clusters, while also providing maximal resemblance for allocation of data in the required cluster.
Broadcast Gossip Algorithms for Consensus on Strongly Connected Digraphs
Venue: arXiv cs.SY 2012
Year: 2012

We study a general framework for broadcast gossip algorithms which use companion variables to solve the average consensus problem. Each node maintains an initial state and a companion variable. Iterative updates are performed asynchronously whereby one random node broadcasts its current state and companion variable and all other nodes receiving the broadcast update their state and companion variable. We provide conditions under which this scheme is guaranteed to converge to a consensus solution, where all nodes have the same limiting values, on any strongly connected directed graph. Under stronger conditions, which are reasonable when the underlying communication graph is undirected, we guarantee that the consensus value is equal to the average, both in expectation and in the mean-squared sense. Our analysis uses tools from non-negative matrix theory and perturbation theory. The perturbation results rely on a parameter being sufficiently small. We characterize the allowable upper bound as well as the optimal setting for the perturbation parameter as a function of the network topology, and this allows us to characterize the worst-case rate of convergence. Simulations illustrate that, in comparison to existing broadcast gossip algorithms, the approaches proposed in this paper have the advantage that they simultaneously can be guaranteed to converge to the average consensus and they converge in a small number of broadcasts.
WESD - Weighted Spectral Distance for Measuring Shape Dissimilarity
Venue: arXiv cs.CV 2012
Year: 2012

This article presents a new distance for measuring shape dissimilarity between objects. Recent publications introduced the use of eigenvalues of the Laplace operator as compact shape descriptors. Here, we revisit the eigenvalues to define a proper distance, called Weighted Spectral Distance (WESD), for quantifying shape dissimilarity. The definition of WESD is derived through analysing the heat-trace. This analysis provides the proposed distance an intuitive meaning and mathematically links it to the intrinsic geometry of objects. We analyse the resulting distance definition, present and prove its important theoretical properties. Some of these properties include: i) WESD is defined over the entire sequence of eigenvalues yet it is guaranteed to converge, ii) it is a pseudometric, iii) it is accurately approximated with a finite number of eigenvalues, and iv) it can be mapped to the [0,1) interval. Lastly, experiments conducted on synthetic and real objects are presented. These experiments highlight the practical benefits of WESD for applications in vision and medical image analysis.
Opinion Dynamics in Social Networks: A Local Interaction Game with Stubborn Agents
Venue: arXiv cs.GT 2012
Year: 2012

The process by which new ideas, innovations, and behaviors spread through a large social network can be thought of as a networked interaction game: Each agent obtains information from certain number of agents in his friendship neighborhood, and adapts his idea or behavior to increase his benefit. In this paper, we are interested in how opinions, about a certain topic, form in social networks. We model opinions as continuous scalars ranging from 0 to 1 with 1(0) representing extremely positive(negative) opinion. Each agent has an initial opinion and incurs some cost depending on the opinions of his neighbors, his initial opinion, and his stubbornness about his initial opinion. Agents iteratively update their opinions based on their own initial opinions and observing the opinions of their neighbors. The iterative update of an agent can be viewed as a myopic cost-minimization response (i.e., the so-called best response) to the others' actions. We study whether an equilibrium can emerge as a result of such local interactions and how such equilibrium possibly depends on the network structure, initial opinions of the agents, and the location of stubborn agents and the extent of their stubbornness. We also study the convergence speed to such equilibrium and characterize the convergence time as a function of aforementioned factors. We also discuss the implications of such results in a few well-known graphs such as Erdos-Renyi random graphs and small-world graphs.
An Optimized Signature Verification System for Vehicle Ad hoc NETwork
Venue: arXiv cs.CR 2012
Year: 2012

This paper1 presents an efficient approach to an existing batch verification system on Identity based group signature (IBGS) which can be applied to any Mobile ad hoc network device including Vehicle Ad hoc Networks (VANET). We propose an optimized way to batch signatures in order to get maximum throughput from a device in runtime environment. In addition, we minimize the number of pairing computations in batch verification proposed by B. Qin et al. for large scale VANET. We introduce a batch scheduling algorithm for batch verification targeting further minimization the batch computation time.
How Non-linearity will Transform Information Systems
Venue: arXiv cs.CE 2012
Year: 2012

One 'problem' with the 21st century world, particularly the economic and business worlds, is the phenomenal and increasing number of interconnections between economic agents (consumers, firms, banks, markets, national economies). This implies that such agents are all interacting and consequently giving raise to enormous degrees of non-linearity, a.k.a. complexity. Complexity often brings with it unexpected phenomena, such as chaos and emerging behaviour, that can become challenges for the survival of economic agents and systems. Developing econophysics approaches are beginning to apply, to the 'economic web', methods and models that have been used in physics and/or systems theory to tackle non-linear domains. The paper gives an account of the research in progress in this field and shows its implications for enteprise information systems, anticipating the emergence of software that will allow to reflect the complexity of the business world, as holistic risk management becomes a mandate for financial institutions and business organizations.
New results of ant algorithms for the Linear Ordering Problem
Venue: arXiv cs.AI 2012
Year: 2012

Ant-based algorithms are successful tools for solving complex problems. One of these problems is the Linear Ordering Problem (LOP). The paper shows new results on some LOP instances, using Ant Colony System (ACS) and the Step-Back Sensitive Ant Model (SB-SAM).