OpenRaiser/Intern-Atlas huggingface dataset:
A Resource Allocation Mechanism for Video Mixing as a Cloud Computing Service in Multimedia Conferencing Applications
Venue: arXiv cs.MM 2015
Year: 2015

Multimedia conferencing is the conversational exchange of multimedia content between multiple parties. It has a wide range of applications (e.g. Massively Multiplayer Online Games (MMOGs) and distance learning). Many multimedia conferencing applications use video extensively, thus video mixing in conferencing settings is of critical importance. Cloud computing is a technology that can solve the scalability issue in multimedia conferencing, while bringing other benefits, such as, elasticity, efficient use of resources, rapid development, and introduction of new applications. However, proposed cloud-based multimedia conferencing approaches so far have several deficiencies when it comes to efficient resource usage while meeting Quality of Service (QoS) requirements. We propose a solution to optimize resource allocation for cloud-based video mixing service in multimedia conferencing applications, which can support scalability in terms of number of users, while guaranteeing QoS. We formulate the resource allocation problem mathematically as an Integer Linear Programming (ILP) problem and design a heuristic for it. Simulation results show that our resource allocation model can support more participants compared to the state-of-the-art, while honoring QoS, with respect to end-to-end delay.
A Framework to Explore the Knowledge Structure of Multidisciplinary Research Fields
Venue: arXiv cs.DL 2015
Year: 2015

Understanding emerging areas of a multidisciplinary research field is crucial for researchers,policymakers and other stakeholders. For them a knowledge structure based on longitudinal bibliographic data can be an effective instrument. But with the vast amount of available online information it is often hard to understand the knowledge structure for data. In this paper, we present a novel approach for retrieving online bibliographic data and propose a framework for exploring knowledge structure. We also present several longitudinal analyses to interpret and visualize the last 20 years of published obesity research data.
A Feature-Based Comparison of Evolutionary Computing Techniques for Constrained Continuous Optimisation
Venue: arXiv cs.AI 2015
Year: 2015

Evolutionary algorithms have been frequently applied to constrained continuous optimisation problems. We carry out feature based comparisons of different types of evolutionary algorithms such as evolution strategies, differential evolution and particle swarm optimisation for constrained continuous optimisation. In our study, we examine how sets of constraints influence the difficulty of obtaining close to optimal solutions. Using a multi-objective approach, we evolve constrained continuous problems having a set of linear and/or quadratic constraints where the different evolutionary approaches show a significant difference in performance. Afterwards, we discuss the features of the constraints that exhibit a difference in performance of the different evolutionary approaches under consideration.
On throughput capacity for a class of buffer-limited MANETs
Venue: arXiv cs.IT 2015
Year: 2015

Available throughput performance studies for mobile ad hoc networks (MANETs) suffer from two major limitations: they mainly focus on the scaling law study of throughput, while the exact throughput of such networks remains largely unknown; they usually consider the infinite buffer scenarios, which are not applicable to the practical networks with limited buffer. As a step to address these limitations, this paper develops a general framework for the exact throughput capacity study of a class of buffer-limited MANETs with the two-hop relay. We first provide analysis to reveal how the throughput capacity of such a MANET is determined by its relay-buffer blocking probability (RBP). Based on the Embedded Markov Chain Theory and Queuing Theory, a novel theoretical framework is then developed to enable the RBP and closed-form expression for exact throughput capacity to be derived. We further conduct case studies under two typical transmission scheduling schemes to illustrate the applicability of our framework and to explore the corresponding capacity optimization as well as capacity scaling law. Finally, extensive simulation and numerical results are provided to validate the efficiency of our framework and to show the impacts brought by the buffer constraint.
End-to-end delay modeling in buffer-limited MANETs: a general theoretical framework
Venue: arXiv cs.IT 2015
Year: 2015

This paper focuses on a class of important two-hop relay mobile ad hoc networks (MANETs) with limited-buffer constraint and any mobility model that leads to the uniform distribution of the locations of nodes in steady state, and develops a general theoretical framework for the end-to-end (E2E) delay modeling there. We first combine the theories of Fixed-Point, Quasi-Birth-and-Death process and embedded Markov chain to model the limiting distribution of the occupancy states of a relay buffer, and then apply the absorbing Markov chain theory to characterize the packet delivery process, such that a complete theoretical framework is developed for the E2E delay analysis. With the help of this framework, we derive a general and exact expression for the E2E delay based on the modeling of both packet queuing delay and delivery delay. To demonstrate the application of our framework, case studies are further provided under two network scenarios with different MAC protocols to show how the E2E delay can be analytically determined for a given network scenario. Finally, we present extensive simulation and numerical results to illustrate the efficiency of our delay analysis as well as the impacts of network parameters on delay performance.
Techniques for the Cograph Editing Problem: Module Merge is equivalent to Editing P4s
Venue: arXiv cs.DM 2015
Year: 2015

Cographs are graphs in which no four vertices induce a simple connected path $P_4$. Cograph editing is to find for a given graph $G = (V,E)$ a set of at most $k$ edge additions and deletions that transform $G$ into a cograph. This combinatorial optimization problem is NP-hard. It has, recently found applications in the context of phylogenetics, hence good heuristics are of practical importance. It is well-known that the cograph editing problem can be solved independently on the so-called strong prime modules of the modular decomposition of $G$. We show here that editing the induced $P_4$'s of a given graph is equivalent to resolving strong prime modules by means of a newly defined merge operation on the submodules. This observation leads to a new exact algorithm for the cograph editing problem that can be used as a starting point for the construction of novel heuristics.
The Global Packing Number for an Optical Network
Venue: arXiv cs.DM 2015
Year: 2015

The global packing number problem arises from the investigation of optimal wavelength allocation in an optical network that employs Wavelength Division Multiplexing (WDM). Consider an optical network that is represented by a connected, simple graph $G$. We assume all communication channels are bidirectional, so that all links and paths are undirected. It follows that there are ${|G|\choose 2}$ distinct node pairs associated with $G$, where $|G|$ is the number of nodes in $G$. A path system $\mathcal{P}$ of $G$ consists of ${|G|\choose 2}$ paths, one path to connect each of the node pairs. The global packing number of a path system $\mathcal{P}$, denoted by $Φ(G,\mathcal{P})$, is the minimum integer $k$ to guarantee the existence of a mapping $ω:\mathcal{P}\to\{1,2,\ldots,k\}$, such that $ω(P)\neqω(P')$ if $P$ and $P'$ have common edge(s). The global packing number of $G$, denoted by $Φ(G)$, is defined to be the minimum $Φ(G,\mathcal{P})$ among all possible path systems $\mathcal{P}$. If there is no wavelength conversion along any optical transmission path for any node pair in the network, the global packing number signifies the minimum number of wavelengths required to support simultaneous communication for all pairs in the network. In this paper, the focus is on ring networks, so that $G$ is a cycle. Explicit formulas for the global packing number of a cycle is derived. The investigation is further extended to chain networks. A path system, $\mathcal{P}$, that enjoys $Φ(G,\mathcal{P})=Φ(G)$ is called ideal. A characterization of ideal path systems is also presented. We also describe an efficient heuristic algorithm to assign wavelengths that can be applied to a general network with more complicated traffic load.
Reachability Analysis of Reversal-bounded Automata on Series-Parallel Graphs
Venue: arXiv cs.FL 2015
Year: 2015

Extensions to finite-state automata on strings, such as multi-head automata or multi-counter automata, have been successfully used to encode many infinite-state non-regular verification problems. In this paper, we consider a generalization of automata-theoretic infinite-state verification from strings to labeled series-parallel graphs. We define a model of non-deterministic, 2-way, concurrent automata working on series-parallel graphs and communicating through shared registers on the nodes of the graph. We consider the following verification problem: given a family of series-parallel graphs described by a context-free graph transformation system (GTS), and a concurrent automaton over series-parallel graphs, is some graph generated by the GTS accepted by the automaton? The general problem is undecidable already for (one-way) multi-head automata over strings. We show that a bounded version, where the automata make a fixed number of reversals along the graph and use a fixed number of shared registers is decidable, even though there is no bound on the sizes of series-parallel graphs generated by the GTS. Our decidability result is based on establishing that the number of context switches is bounded and on an encoding of the computation of bounded concurrent automata to reduce the emptiness problem to the emptiness problem for pushdown automata.
Improvement in Small Progress Measures
Venue: arXiv cs.LO 2015
Year: 2015

Small Progress Measures is one of the classical parity game solving algorithms. For games with n vertices, m edges and d different priorities, the original algorithm computes the winning regions and a winning strategy for one of the players in O(dm.(n/floor(d/2))^floor(d/2)) time. Computing a winning strategy for the other player requires a re-run of the algorithm on that player's winning region, thus increasing the runtime complexity to O(dm.(n/ceil(d/2))^ceil(d/2)) for computing the winning regions and winning strategies for both players. We modify the algorithm so that it derives the winning strategy for both players in one pass. This reduces the upper bound on strategy derivation for SPM to O(dm.(n/floor(d/2))^floor(d/2)). At the basis of our modification is a novel operational interpretation of the least progress measure that we provide.
ATLsc with partial observation
Venue: arXiv cs.LO 2015
Year: 2015

Alternating-time temporal logic with strategy contexts (ATLsc) is a powerful formalism for expressing properties of multi-agent systems: it extends CTL with strategy quantifiers, offering a convenient way of expressing both collaboration and antagonism between several agents. Incomplete observation of the state space is a desirable feature in such a framework, but it quickly leads to undecidable verification problems. In this paper, we prove that uniform incomplete observation (where all players have the same observation) preserves decidability of the model-checking problem, even for very expressive logics such as ATLsc.
Multi-Region Probabilistic Dice Similarity Coefficient using the Aitchison Distance and Bipartite Graph Matching
Venue: arXiv cs.CV 2015
Year: 2015

Validation of image segmentation methods is of critical importance. Probabilistic image segmentation is increasingly popular as it captures uncertainty in the results. Image segmentation methods that support multi-region (as opposed to binary) delineation are more favourable as they capture interactions between the different objects in the image. The Dice similarity coefficient (DSC) has been a popular metric for evaluating the accuracy of automated or semi-automated segmentation methods by comparing their results to the ground truth. In this work, we develop an extension of the DSC to multi-region probabilistic segmentations (with unordered labels). We use bipartite graph matching to establish label correspondences and propose two functions that extend the DSC, one based on absolute probability differences and one based on the Aitchison distance. These provide a robust and accurate measure of multi-region probabilistic segmentation accuracy.
CRDT: Correlation Ratio Based Decision Tree Model for Healthcare Data Mining
Venue: arXiv cs.AI 2015
Year: 2015

The phenomenal growth in the healthcare data has inspired us in investigating robust and scalable models for data mining. For classification problems Information Gain(IG) based Decision Tree is one of the popular choices. However, depending upon the nature of the dataset, IG based Decision Tree may not always perform well as it prefers the attribute with more number of distinct values as the splitting attribute. Healthcare datasets generally have many attributes and each attribute generally has many distinct values. In this paper, we have tried to focus on this characteristics of the datasets while analysing the performance of our proposed approach which is a variant of Decision Tree model and uses the concept of Correlation Ratio(CR). Unlike IG based approach, this CR based approach has no biasness towards the attribute with more number of distinct values. We have applied our model on some benchmark healthcare datasets to show the effectiveness of the proposed technique.
Stale View Cleaning: Getting Fresh Answers from Stale Materialized Views
Venue: arXiv cs.DB 2015
Year: 2015

Materialized views (MVs), stored pre-computed results, are widely used to facilitate fast queries on large datasets. When new records arrive at a high rate, it is infeasible to continuously update (maintain) MVs and a common solution is to defer maintenance by batching updates together. Between batches the MVs become increasingly stale with incorrect, missing, and superfluous rows leading to increasingly inaccurate query results. We propose Stale View Cleaning (SVC) which addresses this problem from a data cleaning perspective. In SVC, we efficiently clean a sample of rows from a stale MV, and use the clean sample to estimate aggregate query results. While approximate, the estimated query results reflect the most recent data. As sampling can be sensitive to long-tailed distributions, we further explore an outlier indexing technique to give increased accuracy when the data distributions are skewed. SVC complements existing deferred maintenance approaches by giving accurate and bounded query answers between maintenance. We evaluate our method on a generated dataset from the TPC-D benchmark and a real video distribution application. Experiments confirm our theoretical results: (1) cleaning an MV sample is more efficient than full view maintenance, (2) the estimated results are more accurate than using the stale MV, and (3) SVC is applicable for a wide variety of MVs.
Near-optimal small-depth lower bounds for small distance connectivity
Venue: arXiv cs.CC 2015
Year: 2015

We show that any depth-$d$ circuit for determining whether an $n$-node graph has an $s$-to-$t$ path of length at most $k$ must have size $n^{Ω(k^{1/d}/d)}$. The previous best circuit size lower bounds for this problem were $n^{k^{\exp(-O(d))}}$ (due to Beame, Impagliazzo, and Pitassi [BIP98]) and $n^{Ω((\log k)/d)}$ (following from a recent formula size lower bound of Rossman [Ros14]). Our lower bound is quite close to optimal, since a simple construction gives depth-$d$ circuits of size $n^{O(k^{2/d})}$ for this problem (and strengthening our bound even to $n^{k^{Ω(1/d)}}$ would require proving that undirected connectivity is not in $\mathsf{NC^1}.$) Our proof is by reduction to a new lower bound on the size of small-depth circuits computing a skewed variant of the "Sipser functions" that have played an important role in classical circuit lower bounds [Sip83, Yao85, Hås86]. A key ingredient in our proof of the required lower bound for these Sipser-like functions is the use of \emph{random projections}, an extension of random restrictions which were recently employed in [RST15]. Random projections allow us to obtain sharper quantitative bounds while employing simpler arguments, both conceptually and technically, than in the previous works [Ajt89, BPU92, BIP98, Ros14].
Description of the Odin Event Extraction Framework and Rule Language
Venue: arXiv cs.CL 2015
Year: 2015

This document describes the Odin framework, which is a domain-independent platform for developing rule-based event extraction models. Odin aims to be powerful (the rule language allows the modeling of complex syntactic structures) and robust (to recover from syntactic parsing errors, syntactic patterns can be freely mixed with surface, token-based patterns), while remaining simple (some domain grammars can be up and running in minutes), and fast (Odin processes over 100 sentences/second in a real-world domain with over 200 rules). Here we include a thorough definition of the Odin rule language, together with a description of the Odin API in the Scala language, which allows one to apply these rules to arbitrary texts.
On Optimizing Human-Machine Task Assignments
Venue: arXiv cs.HC 2015
Year: 2015

When crowdsourcing systems are used in combination with machine inference systems in the real world, they benefit the most when the machine system is deeply integrated with the crowd workers. However, if researchers wish to integrate the crowd with "off-the-shelf" machine classifiers, this deep integration is not always possible. This work explores two strategies to increase accuracy and decrease cost under this setting. First, we show that reordering tasks presented to the human can create a significant accuracy improvement. Further, we show that greedily choosing parameters to maximize machine accuracy is sub-optimal, and joint optimization of the combined system improves performance.
Counting isomorphism classes of $β$-normal linear lambda terms
Venue: arXiv cs.LO 2015
Year: 2015

Unanticipated connections between different fragments of lambda calculus and different families of embedded graphs (a.k.a. "maps") motivate the problem of enumerating $β$-normal linear lambda terms. In this brief note, it is shown (by appeal to a theorem of Arquès and Beraud) that the sequence counting isomorphism classes of $β$-normal linear lambda terms up to free exchange of adjacent lambda abstractions coincides with the sequence counting isomorphism classes of rooted maps on oriented surfaces (A000698).
Cyclic codes from the first class two-prime Whiteman's generalized cyclotomic sequence with order 6
Venue: arXiv cs.IT 2015
Year: 2015

Binary Whiteman's cyclotomic sequences of orders 2 and 4 have a number of good randomness properties. In this paper, we compute the autocorrelation values and linear complexity of the first class two-prime Whiteman's generalized cyclotomic sequence (WGCS-I) of order $d=6$. Our results show that the autocorrelation values of this sequence is four-valued or five-valued if $(n_1-1)(n_2-1)/36$ is even or odd respectively, where $n_1$ and $n_2$ are two distinct odd primes and their linear complexity is quite good. We employ the two-prime WGCS-I of order 6 to construct several classes of cyclic codes over $\mathrm{GF}(q)$ with length $n_1n_2$. We also obtain the lower bounds on the minimum distance of these cyclic codes.
Taking a moment to measure Networks - A hierarchical approach
Venue: arXiv cs.SI 2015
Year: 2015

Network-theoretic tools contribute to understanding real-world system dynamics, e.g., in wildlife conservation, epidemics, and power outages. Network visualization helps illustrate structural heterogeneity; however, details about heterogeneity are lost when summarizing networks with a single mean-style measure. Researchers have indicated that a hierarchical system composed of multiple metrics may be a more useful determinant of structure, but a formal method for grouping metrics is still lacking. We develop a hierarchy using the statistical concept of moments and systematically test the hypothesis that this system of metrics is sufficient to explain the variation in processes that take place on networks, using an ecological systems example. Results indicate that the moments approach outperforms single summary metrics and accounts for a majority of the variation in process outcomes. The hierarchical measurement scheme is helpful for indicating when additional structural information is needed to describe system process outcomes.
Mixed-ADC Massive MIMO Detectors: Performance Analysis and Design Optimization
Venue: arXiv cs.IT 2015
Year: 2015

Using a very low-resolution analog-to-digital convertor (ADC) unit at each antenna can remarkably reduce the hardware cost and power consumption of a massive multiple-input multiple-output (MIMO) system. However, such a pure low-resolution ADC architecture also complicates parameter estimation problems such as time/frequency synchronization and channel estimation. A mixed-ADC architecture, where most of the antennas are equipped with low-precision ADCs while a few antennas have full-precision ADCs, can solve these issues and actualize the potential of the pure low-resolution ADC architecture. In this paper, we present a unified framework to develop a family of detectors over the massive MIMO uplink system with the mixed-ADC receiver architecture by exploiting probabilistic Bayesian inference. As a basic setup, an optimal detector is developed to provide a minimum mean-squared-error (MMSE) estimate on data symbols. Considering the highly nonlinear steps involved in the quantization process, we also investigate the potential for complexity reduction on the optimal detector by postulating the common \emph{pseudo-quantization noise} (PQN) model. In particular, we provide asymptotic performance expressions including the MSE and bit error rate for the optimal and suboptimal MIMO detectors. The asymptotic performance expressions can be evaluated quickly and efficiently; thus, they are useful in system design optimization. We show that in the low signal-to-noise ratio (SNR) regime, the distortion caused by the PQN model can be ignored, whereas in the high-SNR regime, such distortion may cause 1-bit detection performance loss. The performance gap resulting from the PQN model can be narrowed by a small fraction of high-precision ADCs in the mixed-ADC architecture.
Inserting Multiple Edges into a Planar Graph
Venue: arXiv cs.DS 2015
Year: 2015

Let $G$ be a connected planar (but not yet embedded) graph and $F$ a set of additional edges not yet in $G$. The {multiple edge insertion} problem (MEI) asks for a drawing of $G+F$ with the minimum number of pairwise edge crossings, such that the subdrawing of $G$ is plane. An optimal solution to this problem approximates the crossing number of the graph $G+F$. Finding an exact solution to MEI is NP-hard for general $F$, but linear time solvable for the special case of $|F|=1$ (SODA01, Algorithmica) or when all of $F$ are incident to a new vertex (SODA09). The complexity for general $F$ but with constant $k=|F|$ was open, but algorithms both with relative and absolute approximation guarantees have been presented (SODA11, ICALP11). We show that the problem is fixed parameter tractable (FPT) in $k$ for biconnected $G$, or if the cut vertices of $G$ have degrees bounded by a constant. We give the first exact algorithm for this problem; it requires only $O(|V(G)|)$ time for any constant $k$.