OpenRaiser/Intern-Atlas huggingface dataset:
A Review of the Enviro-Net Project
Venue: arXiv cs.NI 2011
Year: 2011

Ecosystems monitoring is essential to properly understand their development and the effects of events, both climatological and anthropological in nature. The amount of data used in these assessments is increasing at very high rates. This is due to increasing availability of sensing systems and the development of new techniques to analyze sensor data. The Enviro-Net Project encompasses several of such sensor system deployments across five countries in the Americas. These deployments use a few different ground-based sensor systems, installed at different heights monitoring the conditions in tropical dry forests over long periods of time. This paper presents our experience in deploying and maintaining these systems, retrieving and pre-processing the data, and describes the Web portal developed to help with data management, visualization and analysis.
Opportunistic Content Search of Smartphone Photos
Venue: arXiv cs.IR 2011
Year: 2011

Photos taken by smartphone users can accidentally contain content that is timely and valuable to others, often in real-time. We report the system design and evaluation of a distributed search system, Theia, for crowd-sourced real-time content search of smartphone photos. Because smartphones are resource-constrained, Theia incorporates two key innovations to control search cost and improve search efficiency. Incremental Search expands search scope incrementally and exploits user feedback. Partitioned Search leverages the cloud to reduce the energy consumption of search in smartphones. Through user studies, measurement studies, and field studies, we show that Theia reduces the cost per relevant photo by an average of 59%. It reduces the energy consumption of search by up to 55% and 81% compared to alternative strategies of executing entirely locally or entirely in the cloud. Search results from smartphones are obtained in seconds. Our experiments also suggest approaches to further improve these results.
A distributed service for on demand end to end optical circuits
Venue: arXiv cs.DC 2011
Year: 2011

In this paper we present a system for monitoring and controlling dynamic network circuits inside the USLHCNet network. This distributed service system provides in near real-time complete topological information for all the circuits, resource allocation and usage, accounting, detects automatically failures in the links and network equipment, generate alarms and has the functionality to take automatic actions. The system is developed based on the MonALISA framework, which provides a robust monitoring and controlling service oriented architecture, with no single points of failure.
The Swiss Board Directors Network in 2009
Venue: arXiv cs.SI 2011
Year: 2011

We study the networks formed by the directors of the most important Swiss boards and the boards themselves for the year 2009. The networks are obtained by projection from the original bipartite graph. We highlight a number of important statistical features of those networks such as degree distribution, weight distribution, and several centrality measures as well as their interrelationships. While similar statistics were already known for other board systems, and are comparable here, we have extended the study with a careful investigation of director and board centrality, a k-core analysis, and a simulation of the speed of information propagation and its relationships with the topological aspects of the network such as clustering and link weight and betweenness. The overall picture that emerges is one in which the topological structure of the Swiss board and director networks has evolved in such a way that special actors and links between actors play a fundamental role in the flow of information among distant parts of the network. This is shown in particular by the centrality measures and by the simulation of a simple epidemic process on the directors network.
Fundamentals of Inter-cell Overhead Signaling in Heterogeneous Cellular Networks
Venue: arXiv cs.IT 2011
Year: 2011

Heterogeneous base stations (e.g. picocells, microcells, femtocells and distributed antennas) will become increasingly essential for cellular network capacity and coverage. Up until now, little basic research has been done on the fundamentals of managing so much infrastructure -- much of it unplanned -- together with the carefully planned macro-cellular network. Inter-cell coordination is in principle an effective way of ensuring different infrastructure components behave in a way that increases, rather than decreases, the key quality of service (QoS) metrics. The success of such coordination depends heavily on how the overhead is shared, and the rate and delay of the overhead sharing. We develop a novel framework to quantify overhead signaling for inter-cell coordination, which is usually ignored in traditional 1-tier networks, and assumes even more importance in multi-tier heterogeneous cellular networks (HCNs). We derive the overhead quality contour for general K-tier HCNs -- the achievable set of overhead packet rate, size, delay and outage probability -- in closed-form expressions or computable integrals under general assumptions on overhead arrivals and different overhead signaling methods (backhaul and/or wireless). The overhead quality contour is further simplified for two widely used models of overhead arrivals: Poisson and deterministic arrival process. This framework can be used in the design and evaluation of any inter-cell coordination scheme. It also provides design insights on backhaul and wireless overhead channels to handle specific overhead signaling requirements.
Minimum Certificate Dispersal with Tree Structures
Venue: arXiv cs.DS 2011
Year: 2011

Given an n-vertex graph G=(V,E) and a set R \subseteq {{x,y} | x,y \in V} of requests, we consider to assign a set of edges to each vertex in G so that for every request {u, v} in R the union of the edge sets assigned to u and v contains a path from u to v. The Minimum Certificate Dispersal Problem (MCD) is defined as one to find an assignment that minimizes the sum of the cardinality of the edge set assigned to each vertex. This problem has been shown to be LOGAPX-complete for the most general setting, and APX-hard and 2-approximable in polynomial time for dense request sets, where R forms a clique. In this paper, we investigate the complexity of MCD with sparse (tree) structures. We first show that MCD is APX-hard when R is a tree, even a star. We then explore the problem from the viewpoint of the maximum degree Δof the tree: MCD for tree request set with constant Δis solvable in polynomial time, while that with Δ=Ω(n) is 2.56-approximable in polynomial time but hard to approximate within 1.01 unless P=NP. As for the structure of G itself, we show that the problem can be solved in polynomial time if G is a tree.
The Life and Death of Unwanted Bits: Towards Proactive Waste Data Management in Digital Ecosystems
Venue: arXiv cs.ET 2011
Year: 2011

Our everyday data processing activities create massive amounts of data. Like physical waste and trash, unwanted and unused data also pollutes the digital environment by degrading the performance and capacity of storage systems and requiring costly disposal. In this paper, we propose using the lessons from real life waste management in handling waste data. We show the impact of waste data on the performance and operational costs of our computing systems. To allow better waste data management, we define a waste hierarchy for digital objects and provide insights into how to identify and categorize waste data. Finally, we introduce novel ways of reusing, reducing, and recycling data and software to minimize the impact of data wastage
Understanding Code Patterns - Analysis, Interpretation & Measurement
Venue: arXiv cs.SE 2011
Year: 2011

This research paper aims to find, analyze and understand code patterns in any software system and measure its quality by defining standards and proposing a formula for the same. Every code that is written can be divided into different code segments, each having its own impact on the overall system. We can analyze these code segments to get the code quality. The measures used in this paper include Lines of Code, Number of calls made by a module, Execution time, the system knowledge of user and developers, the use of generalization, inheritance, reusability and other object-oriented concepts. The entire software code is divided into code snippets, based on the logic that they implement. Each of these code snippets has an impact. This measure is called Impact Factor and is valued by the software developer and/or other system stakeholders. Efficiency = (Code Area / Execution Time) * Qr
Effects of Compensation, Connectivity and Tau in a Computational Model of Alzheimer's Disease
Venue: arXiv cs.NE 2011
Year: 2011

This work updates an existing, simplistic computational model of Alzheimer's Disease (AD) to investigate the behaviour of synaptic compensatory mechanisms in neural networks with small-world connectivity, and varying methods of calculating compensation. It additionally introduces a method for simulating tau neurofibrillary pathology, resulting in a more dramatic damage profile. Small-world connectivity is shown to have contrasting effects on capacity, retrieval time, and robustness to damage, whilst the use of more easily-obtained remote memories rather than recent memories for synaptic compensation is found to lead to rapid network damage.
Computing trends using graphic processor in high energy physics
Venue: arXiv cs.DC 2011
Year: 2011

One of the main challenges in Heavy Energy Physics is to make fast analysis of high amount of experimental and simulated data. At LHC-CERN one p-p event is approximate 1 Mb in size. The time taken to analyze the data and obtain fast results depends on high computational power. The main advantage of using GPU(Graphic Processor Unit) programming over traditional CPU one is that graphical cards bring a lot of computing power at a very low price. Today a huge number of application(scientific, financial etc) began to be ported or developed for GPU, including Monte Carlo tools or data analysis tools for High Energy Physics. In this paper, we'll present current status and trends in HEP using GPU.
A Dynamic Elimination-Combining Stack Algorithm
Venue: arXiv cs.DC 2011
Year: 2011

Two key synchronization paradigms for the construction of scalable concurrent data-structures are software combining and elimination. Elimination-based concurrent data-structures allow operations with reverse semantics (such as push and pop stack operations) to "collide" and exchange values without having to access a central location. Software combining, on the other hand, is effective when colliding operations have identical semantics: when a pair of threads performing operations with identical semantics collide, the task of performing the combined set of operations is delegated to one of the threads and the other thread waits for its operation(s) to be performed. Applying this mechanism iteratively can reduce memory contention and increase throughput. The most highly scalable prior concurrent stack algorithm is the elimination-backoff stack. The elimination-backoff stack provides high parallelism for symmetric workloads in which the numbers of push and pop operations are roughly equal, but its performance deteriorates when workloads are asymmetric. We present DECS, a novel Dynamic Elimination-Combining Stack algorithm, that scales well for all workload types. While maintaining the simplicity and low-overhead of the elimination-bakcoff stack, DECS manages to benefit from collisions of both identical- and reverse-semantics operations. Our empirical evaluation shows that DECS scales significantly better than both blocking and non-blocking best prior stack algorithms.
External-Memory Network Analysis Algorithms for Naturally Sparse Graphs
Venue: arXiv cs.DS 2011
Year: 2011

In this paper, we present a number of network-analysis algorithms in the external-memory model. We focus on methods for large naturally sparse graphs, that is, n-vertex graphs that have O(n) edges and are structured so that this sparsity property holds for any subgraph of such a graph. We give efficient external-memory algorithms for the following problems for such graphs: - Finding an approximate d-degeneracy ordering; - Finding a cycle of length exactly c; - Enumerating all maximal cliques. Such problems are of interest, for example, in the analysis of social networks, where they are used to study network cohesion.
Flash-based Audio and Video Communication in the Cloud
Venue: arXiv cs.NI 2011
Year: 2011

Internet telephony and multimedia communication protocols have matured over the last fifteen years. Recently, the web is evolving as a popular platform for everything we do on the Internet including email, text chat, voice calls, discussions, enterprise apps and multi-party collaboration. Unfortunately, there is a disconnect between web and traditional Internet telephony protocols as they have ignored the constraints and requirements of each other. Consequently, the Flash Player is being used as a web browser plugin by many developers for web-based voice and video calls. We describe the challenges of video communication using a web browser, present a simple API using a Flash Player application, show how it supports wide range of web communication scenarios in the cloud, and describe how it can interoperate with Session Initiation Protocol (SIP)-based systems. We describe both the advantages and challenges of Flash Player based communication applications. The presented API could guide future work on communication-related web protocol extensions.
K-Implementation
Venue: arXiv cs.GT 2011
Year: 2011

This paper discusses an interested party who wishes to influence the behavior of agents in a game (multi-agent interaction), which is not under his control. The interested party cannot design a new game, cannot enforce agents' behavior, cannot enforce payments by the agents, and cannot prohibit strategies available to the agents. However, he can influence the outcome of the game by committing to non-negative monetary transfers for the different strategy profiles that may be selected by the agents. The interested party assumes that agents are rational in the commonly agreed sense that they do not use dominated strategies. Hence, a certain subset of outcomes is implemented in a given game if by adding non-negative payments, rational players will necessarily produce an outcome in this subset. Obviously, by making sufficiently big payments one can implement any desirable outcome. The question is what is the cost of implementation? In this paper we introduce the notion of k-implementation of a desired set of strategy profiles, where k stands for the amount of payment that need to be actually made in order to implement desirable outcomes. A major point in k-implementation is that monetary offers need not necessarily materialize when following desired behaviors. We define and study k-implementation in the contexts of games with complete and incomplete information. In the latter case we mainly focus on the VCG games. Our setting is later extended to deal with mixed strategies using correlation devices. Together, the paper introduces and studies the implementation of desirable outcomes by a reliable party who cannot modify game rules (i.e. provide protocols), complementing previous work in mechanism design, while making it more applicable to many realistic CS settings.
Complexity Results and Approximation Strategies for MAP Explanations
Venue: arXiv cs.AI 2011
Year: 2011

MAP is the problem of finding a most probable instantiation of a set of variables given evidence. MAP has always been perceived to be significantly harder than the related problems of computing the probability of a variable instantiation Pr, or the problem of computing the most probable explanation (MPE). This paper investigates the complexity of MAP in Bayesian networks. Specifically, we show that MAP is complete for NP^PP and provide further negative complexity results for algorithms based on variable elimination. We also show that MAP remains hard even when MPE and Pr become easy. For example, we show that MAP is NP-complete when the networks are restricted to polytrees, and even then can not be effectively approximated. Given the difficulty of computing MAP exactly, and the difficulty of approximating MAP while providing useful guarantees on the resulting approximation, we investigate best effort approximations. We introduce a generic MAP approximation framework. We provide two instantiations of the framework; one for networks which are amenable to exact inference Pr, and one for networks for which even exact inference is too hard. This allows MAP approximation on networks that are too complex to even exactly solve the easier problems, Pr and MPE. Experimental results indicate that using these approximation algorithms provides much better solutions than standard techniques, and provide accurate MAP estimates in many cases.
Generalizing Boolean Satisfiability I: Background and Survey of Existing Work
Venue: arXiv cs.AI 2011
Year: 2011

This is the first of three planned papers describing ZAP, a satisfiability engine that substantially generalizes existing tools while retaining the performance characteristics of modern high-performance solvers. The fundamental idea underlying ZAP is that many problems passed to such engines contain rich internal structure that is obscured by the Boolean representation used; our goal is to define a representation in which this structure is apparent and can easily be exploited to improve computational performance. This paper is a survey of the work underlying ZAP, and discusses previous attempts to improve the performance of the Davis-Putnam-Logemann-Loveland algorithm by exploiting the structure of the problem being solved. We examine existing ideas including extensions of the Boolean language to allow cardinality constraints, pseudo-Boolean representations, symmetry, and a limited form of quantification. While this paper is intended as a survey, our research results are contained in the two subsequent articles, with the theoretical structure of ZAP described in the second paper in this series, and ZAP's implementation described in the third.
A Maximal Tractable Class of Soft Constraints
Venue: arXiv cs.AI 2011
Year: 2011

Many researchers in artificial intelligence are beginning to explore the use of soft constraints to express a set of (possibly conflicting) problem requirements. A soft constraint is a function defined on a collection of variables which associates some measure of desirability with each possible combination of values for those variables. However, the crucial question of the computational complexity of finding the optimal solution to a collection of soft constraints has so far received very little attention. In this paper we identify a class of soft binary constraints for which the problem of finding the optimal solution is tractable. In other words, we show that for any given set of such constraints, there exists a polynomial time algorithm to determine the assignment having the best overall combined measure of desirability. This tractable class includes many commonly-occurring soft constraints, such as 'as near as possible' or 'as soon as possible after', as well as crisp constraints such as 'greater than'. Finally, we show that this tractable class is maximal, in the sense that adding any other form of soft binary constraint which is not in the class gives rise to a class of problems which is NP-hard.
Decentralized Control of Cooperative Systems: Categorization and Complexity Analysis
Venue: arXiv cs.AI 2011
Year: 2011

Decentralized control of cooperative systems captures the operation of a group of decision makers that share a single global objective. The difficulty in solving optimally such problems arises when the agents lack full observability of the global state of the system when they operate. The general problem has been shown to be NEXP-complete. In this paper, we identify classes of decentralized control problems whose complexity ranges between NEXP and P. In particular, we study problems characterized by independent transitions, independent observations, and goal-oriented objective functions. Two algorithms are shown to solve optimally useful classes of goal-oriented decentralized processes in polynomial time. This paper also studies information sharing among the decision-makers, which can improve their performance. We distinguish between three ways in which agents can exchange information: indirect communication, direct communication and sharing state features that are not controlled by the agents. Our analysis shows that for every class of problems we consider, introducing direct or indirect communication does not change the worst-case complexity. The results provide a better understanding of the complexity of decentralized control problems that arise in practice and facilitate the development of planning algorithms for these problems.
Ordered Landmarks in Planning
Venue: arXiv cs.AI 2011
Year: 2011

Many known planning tasks have inherent constraints concerning the best order in which to achieve the goals. A number of research efforts have been made to detect such constraints and to use them for guiding search, in the hope of speeding up the planning process. We go beyond the previous approaches by considering ordering constraints not only over the (top-level) goals, but also over the sub-goals that will necessarily arise during planning. Landmarks are facts that must be true at some point in every valid solution plan. We extend Koehler and Hoffmann's definition of reasonable orders between top level goals to the more general case of landmarks. We show how landmarks can be found, how their reasonable orders can be approximated, and how this information can be used to decompose a given planning task into several smaller sub-tasks. Our methodology is completely domain- and planner-independent. The implementation demonstrates that the approach can yield significant runtime performance improvements when used as a control loop around state-of-the-art sub-optimal planning systems, as exemplified by FF and LPG.
Phase Transitions and Backbones of the Asymmetric Traveling Salesman Problem
Venue: arXiv cs.AI 2011
Year: 2011

In recent years, there has been much interest in phase transitions of combinatorial problems. Phase transitions have been successfully used to analyze combinatorial optimization problems, characterize their typical-case features and locate the hardest problem instances. In this paper, we study phase transitions of the asymmetric Traveling Salesman Problem (ATSP), an NP-hard combinatorial optimization problem that has many real-world applications. Using random instances of up to 1,500 cities in which intercity distances are uniformly distributed, we empirically show that many properties of the problem, including the optimal tour cost and backbone size, experience sharp transitions as the precision of intercity distances increases across a critical value. Our experimental results on the costs of the ATSP tours and assignment problem agree with the theoretical result that the asymptotic cost of assignment problem is pi ^2 /6 the number of cities goes to infinity. In addition, we show that the average computational cost of the well-known branch-and-bound subtour elimination algorithm for the problem also exhibits a thrashing behavior, transitioning from easy to difficult as the distance precision increases. These results answer positively an open question regarding the existence of phase transitions in the ATSP, and provide guidance on how difficult ATSP problem instances should be generated.