OpenRaiser/Intern-Atlas huggingface dataset:
Tracking Live Fish from Low-Contrast and Low-Frame-Rate Stereo Videos
Venue: arXiv cs.CV 2015
Year: 2015

Non-extractive fish abundance estimation with the aid of visual analysis has drawn increasing attention. Unstable illumination, ubiquitous noise and low frame rate video capturing in the underwater environment, however, make conventional tracking methods unreliable. In this paper, we present a multiple fish tracking system for low-contrast and low-frame-rate stereo videos with the use of a trawl-based underwater camera system. An automatic fish segmentation algorithm overcomes the low-contrast issues by adopting a histogram backprojection approach on double local-thresholded images to ensure an accurate segmentation on the fish shape boundaries. Built upon a reliable feature-based object matching method, a multiple-target tracking algorithm via a modified Viterbi data association is proposed to overcome the poor motion continuity and frequent entrance/exit of fish targets under low-frame-rate scenarios. In addition, a computationally efficient block-matching approach performs successful stereo matching, which enables an automatic fish-body tail compensation to greatly reduce segmentation error and allows for an accurate fish length measurement. Experimental results show that an effective and reliable tracking performance for multiple live fish with underwater stereo cameras is achieved.
Challenges and some new directions in channel coding
Venue: arXiv cs.IT 2015
Year: 2015

Three areas of ongoing research in channel coding are surveyed, and recent developments are presented in each area: spatially coupled Low-Density Parity-Check (LDPC) codes, non-binary LDPC codes, and polar coding.
Coordinated Multicasting with Opportunistic User Selection in Multicell Wireless Systems
Venue: arXiv cs.IT 2015
Year: 2015

Physical layer multicasting with opportunistic user selection (OUS) is examined for multicell multi-antenna wireless systems. By adopting a two-layer encoding scheme, a rate-adaptive channel code is applied in each fading block to enable successful decoding by a chosen subset of users (which varies over different blocks) and an application layer erasure code is employed across multiple blocks to ensure that every user is able to recover the message after decoding successfully in a sufficient number of blocks. The transmit signal and code-rate in each block determine opportunistically the subset of users that are able to successfully decode and can be chosen to maximize the long-term multicast efficiency. The employment of OUS not only helps avoid rate-limitations caused by the user with the worst channel, but also helps coordinate interference among different cells and multicast groups. In this work, efficient algorithms are proposed for the design of the transmit covariance matrices, the physical layer code-rates, and the target user subsets in each block. In the single group scenario, the system parameters are determined by maximizing the group-rate, defined as the physical layer code-rate times the fraction of users that can successfully decode in each block. In the multi-group scenario, the system parameters are determined by considering a group-rate balancing optimization problem, which is solved by a successive convex approximation (SCA) approach. To further reduce the feedback overhead, we also consider the case where only part of the users feed back their channel vectors in each block and propose a design based on the balancing of the expected group-rates. In addition to SCA, a sample average approximation technique is also introduced to handle the probabilistic terms arising in this problem. The effectiveness of the proposed schemes is demonstrated by computer simulations.
Faster Algorithms for Testing under Conditional Sampling
Venue: arXiv cs.DS 2015
Year: 2015

There has been considerable recent interest in distribution-tests whose run-time and sample requirements are sublinear in the domain-size $k$. We study two of the most important tests under the conditional-sampling model where each query specifies a subset $S$ of the domain, and the response is a sample drawn from $S$ according to the underlying distribution. For identity testing, which asks whether the underlying distribution equals a specific given distribution or $ε$-differs from it, we reduce the known time and sample complexities from $\tilde{\mathcal{O}}(ε^{-4})$ to $\tilde{\mathcal{O}}(ε^{-2})$, thereby matching the information theoretic lower bound. For closeness testing, which asks whether two distributions underlying observed data sets are equal or different, we reduce existing complexity from $\tilde{\mathcal{O}}(ε^{-4} \log^5 k)$ to an even sub-logarithmic $\tilde{\mathcal{O}}(ε^{-5} \log \log k)$ thus providing a better bound to an open problem in Bertinoro Workshop on Sublinear Algorithms [Fisher, 2004].
Student Satisfaction mining in a typical core course of Computer Science
Venue: arXiv cs.CY 2015
Year: 2015

Students' satisfaction plays a vital role in success of an educational institute. Hence, many educational institutes continuously improve their service to produce a supportive learning environment to satisfy the student need. For this reason, educational institutions collect student satisfaction data to make decision about institutional quality, but till now it cannot be determined because student satisfaction is a complex matter which is influenced by variety of characteristics of students and institutions. There are many studies have been performed to inspect student satisfaction in the form of college services, programs, student accommodation facility, student-faculty interaction, consulting hours etc. So, still we cannot have a standard method to know what is going on about satisfaction in the case of a core course. In this research we determined the attributes that heavily affect student satisfaction in a core course of computer science and the current status of other attributes as well.
MigrantStore: Leveraging Virtual Memory in DRAM-PCM Memory Architecture
Venue: arXiv cs.AR 2015
Year: 2015

With the imminent slowing down of DRAM scaling, Phase Change Memory (PCM) is emerging as a lead alternative for main memory technology. While PCM achieves low energy due to various technology-specific advantages, PCM is significantly slower than DRAM (especially for writes) and can endure far fewer writes before wearing out. Previous work has proposed to use a large, DRAM-based hardware cache to absorb writes and provide faster access. However, due to ineffectual caching where blocks are evicted before sufficient number of accesses, hardware caches incur significant overheads in energy and bandwidth, two key but scarce resources in modern multicores. Because using hardware for detecting and removing such ineffectual caching would incur additional hardware cost and complexity, we leverage the OS virtual memory support for this purpose. We propose a DRAM-PCM hybrid memory architecture where the OS migrates pages on demand from the PCM to DRAM. We call the DRAM part of our memory as MigrantStore which includes two ideas. First, to reduce the energy, bandwidth, and wear overhead of ineffectual migrations, we propose migration hysteresis. Second, to reduce the software overhead of good replacement policies, we propose recently- accessed-page-id (RAPid) buffer, a hardware buffer to track the addresses of recently-accessed MigrantStore pages.
Higher category models of the pi-calculus
Venue: arXiv cs.LO 2015
Year: 2015

We present an approach to modeling computational calculi using higher category theory. Specifically we present a fully abstract semantics for the pi-calculus. The interpretation is consistent with Curry-Howard, interpreting terms as typed morphisms, while simultaneously providing an explicit interpretation of the rewrite rules of standard operational presentations as 2-morphisms. One of the key contributions, inspired by catalysis in chemical reactions, is a method of restricting the application of 2-morphisms interpreting rewrites to specific contexts.
PAR: Petal ant routing algorithm for mobile ad hoc network
Venue: arXiv cs.NI 2015
Year: 2015

During route discovery of mobile ad hoc network, broadcasting of route request and route reply packets are the essential operations for finding the path between two ends. In such situations, intermediate node which may or may not belongs will participate in route discovery process, update routing table and rebroadcast the route discovery packets again to its neighboring nodes. Finally optimal path is found with minimum hops. This simply upsurges overhead and deteriorates the performance of routing. The proposed Petal Ant Routing (PAR) algorithm offers a low overhead by optimizing FANT and BANT transmissions in route discover process. The algorithm is an improved version of SARA and has features extracted from petal routing. The algorithm is simulated on NS2, compared with ACO frame work called SARA and classical routing protocols such as AODV and AOMDV. The simulation results shows that PAR further reduces overhead by eliminating redundant FANT transmission compared to other routing algorithm.
On the Experimental Evaluation of Vehicular Networks: Issues, Requirements and Methodology Applied to a Real Use Case
Venue: arXiv cs.NI 2015
Year: 2015

One of the most challenging fields in vehicular communications has been the experimental assessment of protocols and novel technologies. Researchers usually tend to simulate vehicular scenarios and/or partially validate new contributions in the area by using constrained testbeds and carrying out minor tests. In this line, the present work reviews the issues that pioneers in the area of vehicular communications and, in general, in telematics, have to deal with if they want to perform a good evaluation campaign by real testing. The key needs for a good experimental evaluation is the use of proper software tools for gathering testing data, post-processing and generating relevant figures of merit and, finally, properly showing the most important results. For this reason, a key contribution of this paper is the presentation of an evaluation environment called AnaVANET, which covers the previous needs. By using this tool and presenting a reference case of study, a generic testing methodology is described and applied. This way, the usage of the IPv6 protocol over a vehicle-to-vehicle routing protocol, and supporting IETF-based network mobility, is tested at the same time the main features of the AnaVANET system are presented. This work contributes in laying the foundations for a proper experimental evaluation of vehicular networks and will be useful for many researchers in the area.
Structural Learning of Diverse Ranking
Venue: arXiv cs.IR 2015
Year: 2015

Relevance and diversity are both crucial criteria for an effective search system. In this paper, we propose a unified learning framework for simultaneously optimizing both relevance and diversity. Specifically, the problem is formalized as a structural learning framework optimizing Diversity-Correlated Evaluation Measures (DCEM), such as ERR-IA, a-NDCG and NRBP. Within this framework, the discriminant function is defined to be a bi-criteria objective maximizing the sum of the relevance scores and dissimilarities (or diversity) among the documents. Relevance and diversity features are utilized to define the relevance scores and dissimilarities, respectively. Compared with traditional methods, the advantages of our approach lie in that: (1) Directly optimizing DCEM as the loss function is more fundamental for the task; (2) Our framework does not rely on explicit diversity information such as subtopics, thus is more adaptive to real application; (3) The representation of diversity as the feature-based scoring function is more flexible to incorporate rich diversity-based features into the learning framework. Extensive experiments on the public TREC datasets show that our approach significantly outperforms state-of-the-art diversification approaches, which validate the above advantages.
On the readability of overlap digraphs
Venue: arXiv cs.DM 2015
Year: 2015

We introduce the graph parameter readability and study it as a function of the number of vertices in a graph. Given a digraph D, an injective overlap labeling assigns a unique string to each vertex such that there is an arc from x to y if and only if x properly overlaps y. The readability of D is the minimum string length for which an injective overlap labeling exists. In applications that utilize overlap digraphs (e.g., in bioinformatics), readability reflects the length of the strings from which the overlap digraph is constructed. We study the asymptotic behaviour of readability by casting it in purely graph theoretic terms (without any reference to strings). We prove upper and lower bounds on readability for certain graph families and general graphs
Permissive Controller Synthesis for Probabilistic Systems
Venue: arXiv cs.LO 2015
Year: 2015

We propose novel controller synthesis techniques for probabilistic systems modelled using stochastic two-player games: one player acts as a controller, the second represents its environment, and probability is used to capture uncertainty arising due to, for example, unreliable sensors or faulty system components. Our aim is to generate robust controllers that are resilient to unexpected system changes at runtime, and flexible enough to be adapted if additional constraints need to be imposed. We develop a permissive controller synthesis framework, which generates multi-strategies for the controller, offering a choice of control actions to take at each time step. We formalise the notion of permissivity using penalties, which are incurred each time a possible control action is disallowed by a multi-strategy. Permissive controller synthesis aims to generate a multi-strategy that minimises these penalties, whilst guaranteeing the satisfaction of a specified system property. We establish several key results about the optimality of multi-strategies and the complexity of synthesising them. Then, we develop methods to perform permissive controller synthesis using mixed integer linear programming and illustrate their effectiveness on a selection of case studies.
Unsupervised Dependency Parsing: Let's Use Supervised Parsers
Venue: arXiv cs.CL 2015
Year: 2015

We present a self-training approach to unsupervised dependency parsing that reuses existing supervised and unsupervised parsing algorithms. Our approach, called `iterated reranking' (IR), starts with dependency trees generated by an unsupervised parser, and iteratively improves these trees using the richer probability models used in supervised parsing that are in turn trained on these trees. Our system achieves 1.8% accuracy higher than the state-of-the-part parser of Spitkovsky et al. (2013) on the WSJ corpus.
The model checking fingerprints of CTL operators
Venue: arXiv cs.LO 2015
Year: 2015

The aim of this study is to understand the inherent expressive power of CTL operators. We investigate the complexity of model checking for all CTL fragments with one CTL operator and arbitrary Boolean operators. This gives us a fingerprint of each CTL operator. The comparison between the fingerprints yields a hierarchy of the operators that mirrors their strength with respect to model checking.
A Knowledge-poor Pronoun Resolution System for Turkish
Venue: arXiv cs.CL 2015
Year: 2015

A pronoun resolution system which requires limited syntactic knowledge to identify the antecedents of personal and reflexive pronouns in Turkish is presented. As in its counterparts for languages like English, Spanish and French, the core of the system is the constraints and preferences determined empirically. In the evaluation phase, it performed considerably better than the baseline algorithm used for comparison. The system is significant for its being the first fully specified knowledge-poor computational framework for pronoun resolution in Turkish where Turkish possesses different structural properties from the languages for which knowledge-poor systems had been developed.
On the Identity Type as the Type of Computational Paths
Venue: arXiv cs.LO 2015
Year: 2015

We introduce a new way of formalizing the intensional identity type based on the fact that a entity known as computational paths can be interpreted as terms of the identity type. Our approach enjoys the fact that our elimination rule is easy to understand and use. We make this point clear constructing terms of some relevant types using our proposed elimination rule. We also show that the identity type, as defined by our approach, induces a groupoid structure. This result is on par with the fact that the traditional identity type induces a groupoid, as exposed by Hofmann \& Streicher (1994).
Visual Recognition Using Directional Distribution Distance
Venue: arXiv cs.CV 2015
Year: 2015

In computer vision, an entity such as an image or video is often represented as a set of instance vectors, which can be SIFT, motion, or deep learning feature vectors extracted from different parts of that entity. Thus, it is essential to design efficient and effective methods to compare two sets of instance vectors. Existing methods such as FV, VLAD or Super Vectors have achieved excellent results. However, this paper shows that these methods are designed based on a generative perspective, and a discriminative method can be more effective in categorizing images or videos. The proposed D3 (discriminative distribution distance) method effectively compares two sets as two distributions, and proposes a directional total variation distance (DTVD) to measure how separated are they. Furthermore, a robust classifier-based method is proposed to estimate DTVD robustly. The D3 method is evaluated in action and image recognition tasks and has achieved excellent accuracy and speed. D3 also has a synergy with FV. The combination of D3 and FV has advantages over D3, FV, and VLAD.
Exploring Bayesian Models for Multi-level Clustering of Hierarchically Grouped Sequential Data
Venue: arXiv cs.LG 2015
Year: 2015

A wide range of Bayesian models have been proposed for data that is divided hierarchically into groups. These models aim to cluster the data at different levels of grouping, by assigning a mixture component to each datapoint, and a mixture distribution to each group. Multi-level clustering is facilitated by the sharing of these components and distributions by the groups. In this paper, we introduce the concept of Degree of Sharing (DoS) for the mixture components and distributions, with an aim to analyze and classify various existing models. Next we introduce a generalized hierarchical Bayesian model, of which the existing models can be shown to be special cases. Unlike most of these models, our model takes into account the sequential nature of the data, and various other temporal structures at different levels while assigning mixture components and distributions. We show one specialization of this model aimed at hierarchical segmentation of news transcripts, and present a Gibbs Sampling based inference algorithm for it. We also show experimentally that the proposed model outperforms existing models for the same task.
Homing Vector Automata
Venue: arXiv cs.FL 2015
Year: 2015

We introduce homing vector automata, which are finite automata augmented by a vector that is multiplied at each step by a matrix determined by the current transition, and have to return the vector to its original setting in order to accept the input. The computational power of the deterministic, nondeterministic and blind versions of these real-time machines are examined and compared to various related types of automata. A generalized version of the Stern-Brocot encoding method, suitable for representing strings on arbitrary alphabets, is also developed.
Around Kolmogorov complexity: basic notions and results
Venue: arXiv cs.IT 2015
Year: 2015

Algorithmic information theory studies description complexity and randomness and is now a well known field of theoretical computer science and mathematical logic. There are several textbooks and monographs devoted to this theory where one can find the detailed exposition of many difficult results as well as historical references. However, it seems that a short survey of its basic notions and main results relating these notions to each other, is missing. This report attempts to fill this gap and covers the basic notions of algorithmic information theory: Kolmogorov complexity (plain, conditional, prefix), Solomonoff universal a priori probability, notions of randomness (Martin-Löf randomness, Mises--Church randomness), effective Hausdorff dimension. We prove their basic properties (symmetry of information, connection between a priori probability and prefix complexity, criterion of randomness in terms of complexity, complexity characterization for effective dimension) and show some applications (incompressibility method in computational complexity theory, incompleteness theorems). It is based on the lecture notes of a course at Uppsala University given by the author.
Understanding Big Data Analytic Workloads on Modern Processors
Venue: arXiv cs.DC 2015
Year: 2015

Big data analytics applications play a significant role in data centers, and hence it has become increasingly important to understand their behaviors in order to further improve the performance of data center computer systems, in which characterizing representative workloads is a key practical problem. In this paper, after investigating three most impor- tant application domains in terms of page views and daily visitors, we chose 11 repre- sentative data analytics workloads and characterized their micro-architectural behaviors by using hardware performance counters, so as to understand the impacts and implications of data analytics workloads on the systems equipped with modern superscalar out-of-order processors. Our study reveals that big data analytics applications themselves share many inherent characteristics, which place them in a different class from traditional workloads and scale-out services. To further understand the characteristics of big data analytics work- loads we performed a correlation analysis of CPI (cycles per instruction) with other micro- architecture level characteristics and an investigation of the big data software stack impacts on application behaviors. Our correlation analysis showed that even though big data ana- lytics workloads own notable pipeline front end stalls, the main factors affecting the CPI performance are long latency data accesses rather than the front end stalls. Our software stack investigation found that the typical big data software stack significantly contributes to the front end stalls and incurs bigger working set. Finally we gave several recommen- dations for architects, programmers and big data system designers with the knowledge acquired from this paper.
Tabulation of Noncrossing Acyclic Digraphs
Venue: arXiv cs.DS 2015
Year: 2015

I present an algorithm that, given a number $n \geq 1$, computes a compact representation of the set of all noncrossing acyclic digraphs with $n$ nodes. This compact representation can be used as the basis for a wide range of dynamic programming algorithms on these graphs. As an illustration, along with this note I am releasing the implementation of an algorithm for counting the number of noncrossing acyclic digraphs of a given size. The same tabulation can be modified to count other classes of combinatorial structures, including weakly connected noncrossing acyclic digraphs, general noncrossing digraphs, noncrossing undirected graphs.