OpenRaiser/Intern-Atlas huggingface dataset:
Dominant Resource Fairness in Cloud Computing Systems with Heterogeneous Servers
Venue: arXiv cs.DC 2013
Year: 2013

We study the multi-resource allocation problem in cloud computing systems where the resource pool is constructed from a large number of heterogeneous servers, representing different points in the configuration space of resources such as processing, memory, and storage. We design a multi-resource allocation mechanism, called DRFH, that generalizes the notion of Dominant Resource Fairness (DRF) from a single server to multiple heterogeneous servers. DRFH provides a number of highly desirable properties. With DRFH, no user prefers the allocation of another user; no one can improve its allocation without decreasing that of the others; and more importantly, no user has an incentive to lie about its resource demand. As a direct application, we design a simple heuristic that implements DRFH in real-world systems. Large-scale simulations driven by Google cluster traces show that DRFH significantly outperforms the traditional slot-based scheduler, leading to much higher resource utilization with substantially shorter job completion times.
Mutual Information-Based Planning for Informative Windowed Forecasting of Continuous-Time Linear Systems
Venue: arXiv cs.SY 2013
Year: 2013

This paper presents expression of mutual information that defines the information gain in planning of sensing resources, when the goal is to reduce the forecast uncertainty of some quantities of interest and the system dynamics is described as a continuous-time linear system. The method extends the smoother approach in [5] to handle more general notion of verification entity - continuous sequence of variables over some finite time window in the future. The expression of mutual information for this windowed forecasting case is derived and quantified, taking advantage of underlying conditional independence structure and utilizing the fixed-interval smoothing formula with correlated noises. Two numerical examples on (a) simplified weather forecasting with moving verification paths, and (b) sensor network scheduling for tracking of multiple moving targets are considered for validation of the proposed approach.
First-Class Functions for First-Order Database Engines
Venue: arXiv cs.DB 2013
Year: 2013

We describe Query Defunctionalization which enables off-the-shelf first-order database engines to process queries over first-class functions. Support for first-class functions is characterized by the ability to treat functions like regular data items that can be constructed at query runtime, passed to or returned from other (higher-order) functions, assigned to variables, and stored in persistent data structures. Query defunctionalization is a non-invasive approach that transforms such function-centric queries into the data-centric operations implemented by common query processors. Experiments with XQuery and PL/SQL database systems demonstrate that first-order database engines can faithfully and efficiently support the expressive "functions as data" paradigm.
On the Verification of a WiMax Design Using Symbolic Simulation
Venue: arXiv cs.LO 2013
Year: 2013

In top-down multi-level design methodologies, design descriptions at higher levels of abstraction are incrementally refined to the final realizations. Simulation based techniques have traditionally been used to verify that such model refinements do not change the design functionality. Unfortunately, with computer simulations it is not possible to completely check that a design transformation is correct in a reasonable amount of time, as the number of test patterns required to do so increase exponentially with the number of system state variables. In this paper, we propose a methodology for the verification of conformance of models generated at higher levels of abstraction in the design process to the design specifications. We model the system behavior using sequence of recurrence equations. We then use symbolic simulation together with equivalence checking and property checking techniques for design verification. Using our proposed method, we have verified the equivalence of three WiMax system models at different levels of design abstraction, and the correctness of various system properties on those models. Our symbolic modeling and verification experiments show that the proposed verification methodology provides performance advantage over its numerical counterpart.
On Kolmogorov Complexity of Random Very Long Braided Words
Venue: arXiv cs.CC 2013
Year: 2013

Any positive word comprised of random sequence of tokens form a finite alphabet can be reduced (without change of length) using an appropriate size Braid group relationships. Surprisingly the Braid relations dramatically reduce the Kolmogorov Complexity of the original random word and do so in distinct bands of (rate of change) values with gaps in between. Distribution of these bands are estimated and empirical statistics collected by actually coding approximations to the Kolmogorov Complexity (in Mathematica 9.0). Lempel-Ziv-Welch lossless compression algorithm techniques used to estimate the distribution for gaped bands. Evidence provided that such distributions of reduction in Kolmogorov Complexity based upon Braid groups are universal i.e. they can model more general algebraic structures other than Braid groups.
Applications of continuous functions in topological CAD data
Venue: arXiv cs.CG 2013
Year: 2013

Most CAD or other spatial data models, in particular boundary representation models, are called "topological" and represent spatial data by a structured collection of "topological primitives" like edges, vertices, faces, and volumes. These then represent spatial objects in geo-information- (GIS) or CAD systems or in building information models (BIM). Volume objects may then either be represented by their 2D boundary or by a dedicated 3D-element, the "solid". The latter may share common boundary elements with other solids, just as 2D-polygon topologies in GIS share common boundary edges. Despite the frequent reference to "topology" in publications on spatial modelling the formal link between mathematical topology and these "topological" models is hardly described in the literature. Such link, for example, cannot be established by the often cited nine-intersections model which is too elementary for that purpose. Mathematically, the link between spatial data and the modelled "real world" entities is established by a chain of "continuous functions" - a very important topological notion, yet often overlooked by spatial data modellers. This article investigates how spatial data can actually be considered topological spaces, how continuous functions between them are defined, and how CAD systems can make use of them. Having found examples of applications of continuity in CAD data models it turns out that of continuity has much practical relevance for CAD systems.
MAS for video objects segmentation and tracking based on active contours and SURF descriptor
Venue: arXiv cs.MM 2013
Year: 2013

In computer vision, video segmentation and tracking is an important challenging issue. In this paper, we describe a new video sequences segmentation and tracking algorithm based on MAS "multi-agent systems" and SURF "Speeded Up Robust Features". Our approach consists in modelling a multi-agent system for segmenting the first image from a video sequence and tracking objects in the video sequences. The used agents are supervisor and explorator agents, they are communicating between them and they inspire in their behavior from active contours approaches. The tracking of objects is based on SURF descriptors "Speed Up Robust Features". We used the DIMA platform and "API Ateji PX" (an extension of the Java language to facilitate parallel programming on heterogeneous architectures) to implement this algorithm. The experimental results indicate that the proposed algorithm is more robust and faster than previous approaches.
Using Incomplete Information for Complete Weight Annotation of Road Networks -- Extended Version
Venue: arXiv cs.LG 2013
Year: 2013

We are witnessing increasing interests in the effective use of road networks. For example, to enable effective vehicle routing, weighted-graph models of transportation networks are used, where the weight of an edge captures some cost associated with traversing the edge, e.g., greenhouse gas (GHG) emissions or travel time. It is a precondition to using a graph model for routing that all edges have weights. Weights that capture travel times and GHG emissions can be extracted from GPS trajectory data collected from the network. However, GPS trajectory data typically lack the coverage needed to assign weights to all edges. This paper formulates and addresses the problem of annotating all edges in a road network with travel cost based weights from a set of trips in the network that cover only a small fraction of the edges, each with an associated ground-truth travel cost. A general framework is proposed to solve the problem. Specifically, the problem is modeled as a regression problem and solved by minimizing a judiciously designed objective function that takes into account the topology of the road network. In particular, the use of weighted PageRank values of edges is explored for assigning appropriate weights to all edges, and the property of directional adjacency of edges is also taken into account to assign weights. Empirical studies with weights capturing travel time and GHG emissions on two road networks (Skagen, Denmark, and North Jutland, Denmark) offer insight into the design properties of the proposed techniques and offer evidence that the techniques are effective.
Verification of Sequential Circuits by Tests-As-Proofs Paradigm
Venue: arXiv cs.LO 2013
Year: 2013

We introduce an algorithm for detection of bugs in sequential circuits. This algorithm is incomplete i.e. its failure to find a bug breaking a property P does not imply that P holds. The appeal of incomplete algorithms is that they scale better than their complete counterparts. However, to make an incomplete algorithm effective one needs to guarantee that the probability of finding a bug is reasonably high. We try to achieve such effectiveness by employing the Test-As-Proofs (TAP) paradigm. In our TAP based approach, a counterexample is built as a sequence of states extracted from proofs that some local variations of property P hold. This increases the probability that a) a representative set of states is examined and that b) the considered states are relevant to property P. We describe an algorithm of test generation based on the TAP paradigm and give preliminary experimental results.
TCP-Aware Backpressure Routing and Scheduling
Venue: arXiv cs.NI 2013
Year: 2013

In this work, we explore the performance of backpressure routing and scheduling for TCP flows over wireless networks. TCP and backpressure are not compatible due to a mismatch between the congestion control mechanism of TCP and the queue size based routing and scheduling of the backpressure framework. We propose a TCP-aware backpressure routing and scheduling that takes into account the behavior of TCP flows. TCP-aware backpressure (i) provides throughput optimality guarantees in the Lyapunov optimization framework, (ii) gracefully combines TCP and backpressure without making any changes to the TCP protocol, (iii) improves the throughput of TCP flows significantly, and (iv) provides fairness across competing TCP flows.
Image Integrity Authentication Scheme Based On Fixed Point Theory
Venue: arXiv cs.CR 2013
Year: 2013

Based on fixed point theory, this paper proposes a new scheme for image integrity authentication, which is different from Digital Signature and Fragile Watermarking. A realization of the new scheme is given based on Gaussian Convolution and Deconvolution (GCD) functions. For a given image, if it is invariant under a GCD function, we call it GCD fixed point image. An existence theorem of fixed points for GCD functions is proved and an iterative algorithm is presented for finding fixed points. Experiments show that GCD fixed point images perform well in transparence, fragility, security and tampering localization.
Universal Empathy and Ethical Bias for Artificial General Intelligence
Venue: arXiv cs.AI 2013
Year: 2013

Rational agents are usually built to maximize rewards. However, AGI agents can find undesirable ways of maximizing any prior reward function. Therefore value learning is crucial for safe AGI. We assume that generalized states of the world are valuable - not rewards themselves, and propose an extension of AIXI, in which rewards are used only to bootstrap hierarchical value learning. The modified AIXI agent is considered in the multi-agent environment, where other agents can be either humans or other "mature" agents, which values should be revealed and adopted by the "infant" AGI agent. General framework for designing such empathic agent with ethical bias is proposed also as an extension of the universal intelligence model. Moreover, we perform experiments in the simple Markov environment, which demonstrate feasibility of our approach to value learning in safe AGI.
High-Speed Visible Light Indoor Networks Based on Optical Orthogonal Codes and Combinatorial Designs
Venue: arXiv cs.IT 2013
Year: 2013

Interconnecting devices in an indoor environment using the illumination system and white light emitting diodes (LED) requires adaptive networking techniques that can provide network access for multiple users. Two techniques based on multilevel signaling and optical orthogonal codes (OOC) are explored in this paper in order to provide simultaneous multiple access in an indoor multiuser network. Balanced incomplete block designs (BIBD) are used to construct multilevel symbols for M-ary signaling. Using these multilevel symbols we are able to control the optical peak to average power ratio (PAPR) in the system, and hereby control the dimming level. In the first technique, the M-ary data of each user is first encoded using the OOC codeword that is assigned to that user, and then it is fed into a BIBD encoder to generate a multilevel signal. The second multiple access method uses sub-sets of a BIBD code to apply multilevel expurgated pulse-position modulation (MEPPM) to the data of each user. While the first approach has a larger Hamming distance between the symbols of each user, the latter can provide higher bit-rates for users in VLC systems with bandwidth-limited LEDs.
MonoStream: A Minimal-Hardware High Accuracy Device-free WLAN Localization System
Venue: arXiv cs.NI 2013
Year: 2013

Device-free (DF) localization is an emerging technology that allows the detection and tracking of entities that do not carry any devices nor participate actively in the localization process. Typically, DF systems require a large number of transmitters and receivers to achieve acceptable accuracy, which is not available in many scenarios such as homes and small businesses. In this paper, we introduce MonoStream as an accurate single-stream DF localization system that leverages the rich Channel State Information (CSI) as well as MIMO information from the physical layer to provide accurate DF localization with only one stream. To boost its accuracy and attain low computational requirements, MonoStream models the DF localization problem as an object recognition problem and uses a novel set of CSI-context features and techniques with proven accuracy and efficiency. Experimental evaluation in two typical testbeds, with a side-by-side comparison with the state-of-the-art, shows that MonoStream can achieve an accuracy of 0.95m with at least 26% enhancement in median distance error using a single stream only. This enhancement in accuracy comes with an efficient execution of less than 23ms per location update on a typical laptop. This highlights the potential of MonoStream usage for real-time DF tracking applications.
H-Infinity-Optimal Fractional Delay Filters
Venue: arXiv cs.IT 2013
Year: 2013

Fractional delay filters are digital filters to delay discrete-time signals by a fraction of the sampling period. Since the delay is fractional, the intersample behavior of the original analog signal becomes crucial. In contrast to the conventional designs based on the Shannon sampling theorem with the band-limiting hypothesis, the present paper proposes a new approach based on the modern sampled-data H-infinity optimization that aims at restoring the intersample behavior beyond the Nyquist frequency. By using the lifting transform or continuous-time blocking the design problem is equivalently reduced to a discrete-time H-infinity optimization, which can be effectively solved by numerical computation softwares. Moreover, a closed-form solution is obtained under an assumption on the original analog signals. Design examples are given to illustrate the advantage of the proposed method.
A Survey of Spline-based Volumetric Data Modeling Framework and Its Applications
Venue: arXiv cs.GR 2013
Year: 2013

The rapid advances in 3D scanning and acquisition techniques have given rise to the explosive increase of volumetric digital models in recent years. This dissertation systematically trailblazes a novel volumetric modeling framework to represent 3D solids. The need to explore more efficient and robust 3D modeling framework has gained the prominence. Although the traditional surface representation (e.g., triangle mesh) has many attractive properties, it is incapable of expressing the interior space and materials. Such a serious drawback overshadows many potential modeling and analysis applications. Consequently volumetric modeling techniques become the well-known solution to this problem. Nevertheless, many unsolved research issues remain when developing an efficient modeling paradigm for existing 3D models: complex geometry (fine details and extreme concaveness), arbitrary topology, heterogenous materials, large-scale data storage and processing, etc.
The complexity of resolving conflicts on MAC
Venue: arXiv cs.DS 2013
Year: 2013

We consider the fundamental problem of multiple stations competing to transmit on a multiple access channel (MAC). We are given $n$ stations out of which at most $d$ are active and intend to transmit a message to other stations using MAC. All stations are assumed to be synchronized according to a time clock. If $l$ stations node transmit in the same round, then the MAC provides the feedback whether $l=0$, $l=2$ (collision occurred) or $l=1$. When $l=1$, then a single station is indeed able to successfully transmit a message, which is received by all other nodes. For the above problem the active stations have to schedule their transmissions so that they can singly, transmit their messages on MAC, based only on the feedback received from the MAC in previous round. For the above problem it was shown in [Greenberg, Winograd, {\em A Lower bound on the Time Needed in the Worst Case to Resolve Conflicts Deterministically in Multiple Access Channels}, Journal of ACM 1985] that every deterministic adaptive algorithm should take $Ω(d (\lg n)/(\lg d))$ rounds in the worst case. The fastest known deterministic adaptive algorithm requires $O(d \lg n)$ rounds. The gap between the upper and lower bound is $O(\lg d)$ round. It is substantial for most values of $d$: When $d = $ constant and $d \in O(n^ε)$ (for any constant $ε\leq 1$, the lower bound is respectively $O(\lg n)$ and O(n), which is trivial in both cases. Nevertheless, the above lower bound is interesting indeed when $d \in$ poly($\lg n$). In this work, we present a novel counting argument to prove a tight lower bound of $Ω(d \lg n)$ rounds for all deterministic, adaptive algorithms, closing this long standing open question.}
Clustering and Community Detection in Directed Networks: A Survey
Venue: arXiv cs.SI 2013
Year: 2013

Networks (or graphs) appear as dominant structures in diverse domains, including sociology, biology, neuroscience and computer science. In most of the aforementioned cases graphs are directed - in the sense that there is directionality on the edges, making the semantics of the edges non symmetric. An interesting feature that real networks present is the clustering or community structure property, under which the graph topology is organized into modules commonly called communities or clusters. The essence here is that nodes of the same community are highly similar while on the contrary, nodes across communities present low similarity. Revealing the underlying community structure of directed complex networks has become a crucial and interdisciplinary topic with a plethora of applications. Therefore, naturally there is a recent wealth of research production in the area of mining directed graphs - with clustering being the primary method and tool for community detection and evaluation. The goal of this paper is to offer an in-depth review of the methods presented so far for clustering directed networks along with the relevant necessary methodological background and also related applications. The survey commences by offering a concise review of the fundamental concepts and methodological base on which graph clustering algorithms capitalize on. Then we present the relevant work along two orthogonal classifications. The first one is mostly concerned with the methodological principles of the clustering algorithms, while the second one approaches the methods from the viewpoint regarding the properties of a good cluster in a directed network. Further, we present methods and metrics for evaluating graph clustering results, demonstrate interesting application domains and provide promising future research directions.
Beyond Gamification: Implications of Purposeful Games for the Information Systems Discipline
Venue: arXiv cs.CY 2013
Year: 2013

Gamification is an emerging design principle for information systems where game design elements are applied to non-game contexts. IS researchers have suggested that the IS discipline must study this area but there are other applications such as serious games, and simulations that also use games in non-game contexts. Specifically, the management field has been using games and simulations for years and these applications are now being supported by information systems. We propose in this paper that we must think beyond gamification, towards other uses of games in non-gaming contexts, which we call purposeful gaming. In this paper we identify how the IS discipline can adapt to purposeful gaming. Specifically, we show how IT artifacts, IS design, and IS theories can be used in the purposeful gaming area. We also provide three conceptual dimensions of purposeful gaming that can aid IS practitioners and researchers to classify and understand purposeful games.
List H-Coloring a Graph by Removing Few Vertices
Venue: arXiv cs.DS 2013
Year: 2013

In the deletion version of the list homomorphism problem, we are given graphs G and H, a list L(v) that is a subset of V(H) for each vertex v of G, and an integer k. The task is to decide whether there exists a subset W of V(G) of size at most k such that there is a homomorphism from G \ W to H respecting the lists. We show that DL-Hom(H), parameterized by k and |H|, is fixed-parameter tractable for any (P6, C6)-free bipartite graph H; already for this restricted class of graphs, the problem generalizes Vertex Cover, Odd Cycle Transversal, and Vertex Multiway Cut parameterized by the size of the cutset and the number of terminals. We conjecture that DL-Hom(H) is fixed-parameter tractable for the class of graphs H for which the list homomorphism problem (without deletions) is polynomial-time solvable; by a result of Feder, Hell and Huang (1999), a graph H belongs to this class precisely if it is a bipartite graph whose complement is a circular arc graph. We show that this conjecture is equivalent to the fixed-parameter tractability of a single fairly natural satisfiability problem, Clause Deletion Chain-SAT.