OpenRaiser/Intern-Atlas huggingface dataset:
Query sensitive comparative summarization of search results using concept based segmentation
Venue: arXiv cs.IR 2012
Year: 2012

Query sensitive summarization aims at providing the users with the summary of the contents of single or multiple web pages based on the search query. This paper proposes a novel idea of generating a comparative summary from a set of URLs from the search result. User selects a set of web page links from the search result produced by search engine. Comparative summary of these selected web sites is generated. This method makes use of HTML DOM tree structure of these web pages. HTML documents are segmented into set of concept blocks. Sentence score of each concept block is computed with respect to the query and feature keywords. The important sentences from the concept blocks of different web pages are extracted to compose the comparative summary on the fly. This system reduces the time and effort required for the user to browse various web sites to compare the information. The comparative summary of the contents would help the users in quick decision making.
Stochastic Low-Rank Kernel Learning for Regression
Venue: arXiv cs.LG 2012
Year: 2012

We present a novel approach to learn a kernel-based regression function. It is based on the useof conical combinations of data-based parameterized kernels and on a new stochastic convex optimization procedure of which we establish convergence guarantees. The overall learning procedure has the nice properties that a) the learned conical combination is automatically designed to perform the regression task at hand and b) the updates implicated by the optimization procedure are quite inexpensive. In order to shed light on the appositeness of our learning strategy, we present empirical results from experiments conducted on various benchmark datasets.
Integrating Interactive Visualizations in the Search Process of Digital Libraries and IR Systems
Venue: arXiv cs.DL 2012
Year: 2012

Interactive visualizations for exploring and retrieval have not yet become an integral part of digital libraries and information retrieval systems. We have integrated a set of interactive graphics in a real world social science digital library. These visualizations support the exploration of search queries, results and authors, can filter search results, show trends in the database and can support the creation of new search queries. The use of weighted brushing supports the identification of related metadata for search facets. We discuss some use cases of the combination of IR systems and interactive graphics. In a user study we verify that users can gain insights from statistical graphics intuitively and can adopt interaction techniques.
Fork-forests in bi-colored complete bipartite graphs
Venue: arXiv cs.DM 2012
Year: 2012

Motivated by the problem in [6], which studies the relative efficiency of propositional proof systems, 2-edge colorings of complete bipartite graphs are investigated. It is shown that if the edges of $G=K_{n,n}$ are colored with black and white such that the number of black edges differs from the number of white edges by at most 1, then there are at least $n(1-1/\sqrt{2})$ vertex-disjoint forks with centers in the same partite set of $G$. Here, a fork is a graph formed by two adjacent edges of different colors. The bound is sharp. Moreover, an algorithm running in time $O(n^2 \log n \sqrt{n α(n^2,n) \log n})$ and giving a largest such fork forest is found.
Query-Subquery Nets
Venue: arXiv cs.DB 2012
Year: 2012

We formulate query-subquery nets and use them to create the first framework for developing algorithms for evaluating queries to Horn knowledge bases with the properties that: the approach is goal-directed; each subquery is processed only once and each supplement tuple, if desired, is transferred only once; operations are done set-at-a-time; and any control strategy can be used. Our intention is to increase efficiency of query processing by eliminating redundant computation, increasing flexibility and reducing the number of accesses to the secondary storage. The framework forms a generic evaluation method called QSQN. To deal with function symbols, we use a term-depth bound for atoms and substitutions occurring in the computation and propose to use iterative deepening search which iteratively increases the term-depth bound. We prove soundness and completeness of our generic evaluation method and show that, when the term-depth bound is fixed, the method has PTIME data complexity. We also present how tail recursion elimination can be incorporated into our framework and propose two exemplary control strategies, one is to reduce the number of accesses to the secondary storage, while the other is depth-first search.
Dynamic 3-sided Planar Range Queries with Expected Doubly Logarithmic Time
Venue: arXiv cs.DS 2012
Year: 2012

This work studies the problem of 2-dimensional searching for the 3-sided range query of the form $[a, b]\times (-\infty, c]$ in both main and external memory, by considering a variety of input distributions. We present three sets of solutions each of which examines the 3-sided problem in both RAM and I/O model respectively. The presented data structures are deterministic and the expectation is with respect to the input distribution.
DBAS: A Deployable Bandwidth Aggregation System
Venue: arXiv cs.NI 2012
Year: 2012

The explosive increase in data demand coupled with the rapid deployment of various wireless access technologies have led to the increase of number of multi-homed or multi-interface enabled devices. Fully exploiting these interfaces has motivated researchers to propose numerous solutions that aggregate their available bandwidths to increase overall throughput and satisfy the end-user's growing data demand. These solutions, however, have faced a steep deployment barrier that we attempt to overcome in this paper. We propose a Deployable Bandwidth Aggregation System (DBAS) for multi-interface enabled devices. Our system does not introduce any intermediate hardware, modify current operating systems, modify socket implementations, nor require changes to current applications or legacy servers. The DBAS architecture is designed to automatically estimate the characteristics of applications and dynamically schedule various connections or packets to different interfaces. Since our main focus is deployability, we fully implement DBAS on the Windows operating system and evaluate various modes of operation. Our implementation and simulation results show that DBAS achieves throughput gains up to 193% compared to current operating systems, while operating as an out-of-the-box standard Windows executable, highlighting its deployability and ease of use.
Strategy Improvement for Concurrent Reachability and Safety Games
Venue: arXiv cs.GT 2012
Year: 2012

We consider concurrent games played on graphs. At every round of a game, each player simultaneously and independently selects a move; the moves jointly determine the transition to a successor state. Two basic objectives are the safety objective to stay forever in a given set of states, and its dual, the reachability objective to reach a given set of states. First, we present a simple proof of the fact that in concurrent reachability games, for all $ε>0$, memoryless $ε$-optimal strategies exist. A memoryless strategy is independent of the history of plays, and an $ε$-optimal strategy achieves the objective with probability within $ε$ of the value of the game. In contrast to previous proofs of this fact, our proof is more elementary and more combinatorial. Second, we present a strategy-improvement (a.k.a.\ policy-iteration) algorithm for concurrent games with reachability objectives. We then present a strategy-improvement algorithm for concurrent games with safety objectives. Our algorithms yield sequences of player-1 strategies which ensure probabilities of winning that converge monotonically to the value of the game. Our result is significant because the strategy-improvement algorithm for safety games provides, for the first time, a way to approximate the value of a concurrent safety game from below. Previous methods could approximate the values of these games only from one direction, and as no rates of convergence are known, they did not provide a practical way to solve these games.
Acoustical Quality Assessment of the Classroom Environment
Venue: arXiv cs.LG 2012
Year: 2012

Teaching is one of the most important factors affecting any education system. Many research efforts have been conducted to facilitate the presentation modes used by instructors in classrooms as well as provide means for students to review lectures through web browsers. Other studies have been made to provide acoustical design recommendations for classrooms like room size and reverberation times. However, using acoustical features of classrooms as a way to provide education systems with feedback about the learning process was not thoroughly investigated in any of these studies. We propose a system that extracts different sound features of students and instructors, and then uses machine learning techniques to evaluate the acoustical quality of any learning environment. We infer conclusions about the students' satisfaction with the quality of lectures. Using classifiers instead of surveys and other subjective ways of measures can facilitate and speed such experiments which enables us to perform them continuously. We believe our system enables education systems to continuously review and improve their teaching strategies and acoustical quality of classrooms.
Metrics to evaluate research performance in academic institutions: A critique of ERA 2010 as applied in forestry and the indirect H2 index as a possible alternative
Venue: arXiv cs.DL 2012
Year: 2012

Excellence for Research in Australia (ERA) is an attempt by the Australian Research Council to rate Australian universities on a 5-point scale within 180 Fields of Research using metrics and peer evaluation by an evaluation committee. Some of the bibliometric data contributing to this ranking suffer statistical issues associated with skewed distributions. Other data are standardised year-by-year, placing undue emphasis on the most recent publications which may not yet have reliable citation patterns. The bibliometric data offered to the evaluation committees is extensive, but lacks effective syntheses such as the h-index and its variants. The indirect H2 index is objective, can be computed automatically and efficiently, is resistant to manipulation, and a good indicator of impact to assist the ERA evaluation committees and to similar evaluations internationally.
Using Neighborhood Diversity to Solve Hard Problems
Venue: arXiv cs.DS 2012
Year: 2012

Parameterized algorithms are a very useful tool for dealing with NP-hard problems on graphs. Yet, to properly utilize parameterized algorithms it is necessary to choose the right parameter based on the type of problem and properties of the target graph class. Tree-width is an example of a very successful graph parameter, however it cannot be used on dense graph classes and there also exist problems which are hard even on graphs of bounded tree-width. Such problems can be tackled by using vertex cover as a parameter, however this places severe restrictions on admissible graph classes. Michael Lampis has recently introduced neighborhood diversity, a new graph parameter which generalizes vertex cover to dense graphs. Among other results, he has shown that simple parameterized algorithms exist for a few problems on graphs of bounded neighborhood diversity. Our article further studies this area and provides new algorithms parameterized by neighborhood diversity for the p-Vertex-Disjoint Paths, Graph Motif and Precoloring Extension problems -- the latter two being hard even on graphs of bounded tree-width.
An algorithm to compute the differential equations for the logarithm of a polynomial
Venue: arXiv cs.SC 2012
Year: 2012

We present an algorithm to compute the annihilator of (i.e., the linear differential equations for) the logarithm of a polynomial in the ring of differential operators with polynomial coefficients. The algorithm consists of differentiation with respect to the parameter s of the annihilator of f^s for a polynomial f and quotient computation. More generally, the annihilator of f^s(log f)^m for a complex number s and a positive integer m can be computed, which constitutes what is called a holonomic system in D-module theory. This enables us to compute a holonomic system for the integral of a function involving the logarithm of a polynomial by using integration algorithm for D-modules.
The computation of first order moments on junction trees
Venue: arXiv cs.AI 2012
Year: 2012

We review some existing methods for the computation of first order moments on junction trees using Shafer-Shenoy algorithm. First, we consider the problem of first order moments computation as vertices problem in junction trees. In this way, the problem is solved using the memory space of an order of the junction tree edge-set cardinality. After that, we consider two algorithms, Lauritzen-Nilsson algorithm, and Mauá et al. algorithm, which computes the first order moments as the normalization problem in junction tree, using the memory space of an order of the junction tree leaf-set cardinality.
Organic Design of Massively Distributed Systems: A Complex Networks Perspective
Venue: arXiv cs.NI 2012
Year: 2012

The vision of Organic Computing addresses challenges that arise in the design of future information systems that are comprised of numerous, heterogeneous, resource-constrained and error-prone components or devices. Here, the notion organic particularly highlights the idea that, in order to be manageable, such systems should exhibit self-organization, self-adaptation and self-healing characteristics similar to those of biological systems. In recent years, the principles underlying many of the interesting characteristics of natural systems have been investigated from the perspective of complex systems science, particularly using the conceptual framework of statistical physics and statistical mechanics. In this article, we review some of the interesting relations between statistical physics and networked systems and discuss applications in the engineering of organic networked computing systems with predictable, quantifiable and controllable self-* properties.
Optimizing the Performance of Streaming Numerical Kernels on the IBM Blue Gene/P PowerPC 450 Processor
Venue: arXiv cs.PF 2012
Year: 2012

Several emerging petascale architectures use energy-efficient processors with vectorized computational units and in-order thread processing. On these architectures the sustained performance of streaming numerical kernels, ubiquitous in the solution of partial differential equations, represents a challenge despite the regularity of memory access. Sophisticated optimization techniques are required to fully utilize the Central Processing Unit (CPU). We propose a new method for constructing streaming numerical kernels using a high-level assembly synthesis and optimization framework. We describe an implementation of this method in Python targeting the IBM Blue Gene/P supercomputer's PowerPC 450 core. This paper details the high-level design, construction, simulation, verification, and analysis of these kernels utilizing a subset of the CPU's instruction set. We demonstrate the effectiveness of our approach by implementing several three-dimensional stencil kernels over a variety of cached memory scenarios and analyzing the mechanically scheduled variants, including a 27-point stencil achieving a 1.7x speedup over the best previously published results.
TripNet: A Heuristic Algorithm for Constructing Rooted Phylogenetic Networks from Triplets
Venue: arXiv cs.DS 2012
Year: 2012

The problem of constructing an optimal rooted phylogenetic network from a set of rooted triplets is an NP-hard problem. In this paper, we present a heuristic algorithm called TripNet which tries to construct an optimal rooted phylogenetic network from an arbitrary set of triplets. We prove some theorems to justify the performance of the algorithm.
Formal proofs in real algebraic geometry: from ordered fields to quantifier elimination
Venue: arXiv cs.LO 2012
Year: 2012

This paper describes a formalization of discrete real closed fields in the Coq proof assistant. This abstract structure captures for instance the theory of real algebraic numbers, a decidable subset of real numbers with good algorithmic properties. The theory of real algebraic numbers and more generally of semi-algebraic varieties is at the core of a number of effective methods in real analysis, including decision procedures for non linear arithmetic or optimization methods for real valued functions. After defining an abstract structure of discrete real closed field and the elementary theory of real roots of polynomials, we describe the formalization of an algebraic proof of quantifier elimination based on pseudo-remainder sequences following the standard computer algebra literature on the topic. This formalization covers a large part of the theory which underlies the efficient algorithms implemented in practice in computer algebra. The success of this work paves the way for formal certification of these efficient methods.
Elasticity on Ontology Matching of Folksodriven Structure Network
Venue: arXiv cs.DL 2012
Year: 2012

Nowadays folksonomy tags are used not just for personal organization, but for communication and sharing between people sharing their own local interests. In this paper is considered the new concept structure called "Folksodriven" to represent folksonomies. The Folksodriven Structure Network (FSN) was thought as folksonomy tags suggestions for the user on a dataset built on chosen websites - based on Natural Language Processing (NLP). Morphological changes, such as changes in folksonomy tags chose have direct impact on network connectivity (structural plasticity) of the folksonomy tags considered. The goal of this paper is on defining a base for a FSN plasticity theory to analyze. To perform such goal it is necessary a systematic mathematical analysis on deformation and fracture for the ontology matching on the FSN. The advantages of that approach could be used on a new interesting method to be employed by a knowledge management system.
QGRP: A Novel QoS-Geographic Routing Protocol for Multimedia Wireless Sensor Networks
Venue: arXiv cs.NI 2012
Year: 2012

Thanks to the potential they hold and the variety of their application domains, Multimedia Wireless Sensor Networks (MWSN) are forecast to become highly integrated into our daily activities. Due to the carried content nature, mainly composed of images and/or video streams with high throughput and delay constraints, Quality of Service in the context of MWSN is a crucial issue. In this paper, we propose a QoS and energy aware geographic routing protocol for MWSN: QGRP. The proposed protocol addresses bandwidth, delay and energy constraints associated with MWSN. QGRP adopts an analytical model of IEEE 802.11 Distributed Coordination Function (DCF) to estimate available bandwidth and generates loop-free routing paths.
Connectivity of Confined Dense Networks: Boundary Effects and Scaling Laws
Venue: arXiv cs.NI 2012
Year: 2012

In this paper, we study the probability that a dense network confined within a given geometry is fully connected. We employ a cluster expansion approach often used in statistical physics to analyze the effects that the boundaries of the geometry have on connectivity. To maximize practicality and applicability, we adopt four important point-to-point link models based on outage probability in our analysis: single-input single-output (SISO), single-input multiple-output (SIMO), multiple-input single-output (MISO), and multiple-input multiple-output (MIMO). Furthermore, we derive diversity and power scaling laws that dictate how boundary effects can be mitigated (to leading order) in confined dense networks for each of these models. Finally, in order to demonstrate the versatility of our theory, we analyze boundary effects for dense networks comprising MIMO point-to-point links confined within a right prism, a polyhedron that accurately models many geometries that can be found in practice. We provide numerical results for this example, which verify our analytical results.
On the Multiple Access Channel with Asymmetric Noisy State Information at the Encoders
Venue: arXiv cs.IT 2012
Year: 2012

We consider the problem of reliable communication over multiple-access channels (MAC) where the channel is driven by an independent and identically distributed state process and the encoders and the decoder are provided with various degrees of asymmetric noisy channel state information (CSI). For the case where the encoders observe causal, asymmetric noisy CSI and the decoder observes complete CSI, we provide inner and outer bounds to the capacity region, which are tight for the sum-rate capacity. We then observe that, under a Markov assumption, similar capacity results also hold in the case where the receiver observes noisy CSI. Furthermore, we provide a single letter characterization for the capacity region when the CSI at the encoders are asymmetric deterministic functions of the CSI at the decoder and the encoders have non-causal noisy CSI (its causal version is recently solved in \cite{como-yuksel}). When the encoders observe asymmetric noisy CSI with asymmetric delays and the decoder observes complete CSI, we provide a single letter characterization for the capacity region. Finally, we consider a cooperative scenario with common and private messages, with asymmetric noisy CSI at the encoders and complete CSI at the decoder. We provide a single letter expression for the capacity region for such channels. For the cooperative scenario, we also note that as soon as the common message encoder does not have access to CSI, then in any noisy setup, covering the cases where no CSI or noisy CSI at the decoder, it is possible to obtain a single letter characterization for the capacity region. The main component in these results is a generalization of a converse coding approach, recently introduced in [1] for the MAC with asymmetric quantized CSI at the encoders and herein considerably extended and adapted for the noisy CSI setup.
Secondary use of data in EHR systems
Venue: arXiv cs.PL 2012
Year: 2012

We show how to use aspect-oriented programming to separate security and trust issues from the logical design of mobile, distributed systems. The main challenge is how to enforce various types of security policies, in particular predictive access control policies - policies based on the future behavior of a program. A novel feature of our approach is that advice is able to analyze the future use of data. We consider a number of different security policies, concerning both primary and secondary use of data, some of which can only be enforced by analysis of process continuations.
On Shore and Johnson properties for a Special Case of Csiszár f-divergences
Venue: arXiv cs.IT 2012
Year: 2012

The importance of power-law distributions is attributed to the fact that most of the naturally occurring phenomenon exhibit this distribution. While exponential distributions can be derived by minimizing KL-divergence w.r.t some moment constraints, some power law distributions can be derived by minimizing some generalizations of KL-divergence (more specifically some special cases of Csiszár f-divergences). Divergence minimization is very well studied in information theoretical approaches to statistics. In this work we study properties of minimization of Tsallis divergence, which is a special case of Csiszár f-divergence. In line with the work by Shore and Johnson (IEEE Trans. IT, 1981), we examine the properties exhibited by these minimization methods including the Pythagorean property.