OpenRaiser/Intern-Atlas huggingface dataset:
Inferring Strategies for Sentence Ordering in Multidocument News Summarization
Venue: arXiv cs.AI 2011
Year: 2011

The problem of organizing information for multidocument summarization so that the generated summary is coherent has received relatively little attention. While sentence ordering for single document summarization can be determined from the ordering of sentences in the input article, this is not the case for multidocument summarization where summary sentences may be drawn from different input articles. In this paper, we propose a methodology for studying the properties of ordering information in the news genre and describe experiments done on a corpus of multiple acceptable orderings we developed for the task. Based on these experiments, we implemented a strategy for ordering information that combines constraints from chronological order of events and topical relatedness. Evaluation of our augmented algorithm shows a significant improvement of the ordering over two baseline strategies.
Discriminatory Lossy Source Coding: Side Information Privacy
Venue: arXiv cs.IT 2011
Year: 2011

A lossy source coding problem is studied in which a source encoder communicates with two decoders, one with and one without correlated side information with an additional constraint on the privacy of the side information at the uninformed decoder. Two cases of this problem arise depending on the availability of the side information at the encoder. The set of all feasible rate-distortion-equivocation tuples are characterized for both cases. The difference between the informed and uninformed cases and the advantages of encoder side information for enhancing privacy are highlighted for a binary symmetric source with erasure side information and Hamming distortion.
Clustering with Multi-Layer Graphs: A Spectral Perspective
Venue: arXiv cs.LG 2011
Year: 2011

Observational data usually comes with a multimodal nature, which means that it can be naturally represented by a multi-layer graph whose layers share the same set of vertices (users) with different edges (pairwise relationships). In this paper, we address the problem of combining different layers of the multi-layer graph for improved clustering of the vertices compared to using layers independently. We propose two novel methods, which are based on joint matrix factorization and graph regularization framework respectively, to efficiently combine the spectrum of the multiple graph layers, namely the eigenvectors of the graph Laplacian matrices. In each case, the resulting combination, which we call a "joint spectrum" of multiple graphs, is used for clustering the vertices. We evaluate our approaches by simulations with several real world social network datasets. Results demonstrate the superior or competitive performance of the proposed methods over state-of-the-art technique and common baseline methods, such as co-regularization and summation of information from individual graphs.
On vertex covers and matching number of trapezoid graphs
Venue: arXiv cs.DS 2011
Year: 2011

The intersection graph of a collection of trapezoids with corner points lying on two parallel lines is called a trapezoid graph. Using binary indexed tree data structure, we improve algorithms for calculating the size and the number of minimum vertex covers (or independent sets), as well as the total number of vertex covers, and reduce the time complexity from $O (n^2)$ to $O (n \log n)$, where $n$ is the number of trapezoids. Furthermore, we present the family of counterexamples for recently proposed algorithm with time complexity $O (n^2)$ for calculating the maximum cardinality matching in trapezoid graphs.
Quantum Finite Automata and Probabilistic Reversible Automata: R-trivial Idempotent Languages
Venue: arXiv cs.FL 2011
Year: 2011

We study the recognition of R-trivial idempotent (R1) languages by various models of "decide-and-halt" quantum finite automata (QFA) and probabilistic reversible automata (DH-PRA). We introduce bistochastic QFA (MM-BQFA), a model which generalizes both Nayak's enhanced QFA and DH-PRA. We apply tools from algebraic automata theory and systems of linear inequalities to give a complete characterization of R1 languages recognized by all these models. We also find that "forbidden constructions" known so far do not include all of the languages that cannot be recognized by measure-many QFA.
HMTT: A Hybrid Hardware/Software Tracing System for Bridging Memory Trace's Semantic Gap
Venue: arXiv cs.AR 2011
Year: 2011

Memory trace analysis is an important technology for architecture research, system software (i.e., OS, compiler) optimization, and application performance improvements. Hardware-snooping is an effective and efficient approach to monitor and collect memory traces. Compared with software-based approaches, memory traces collected by hardware-based approaches are usually lack of semantic information, such as process/function/loop identifiers, virtual address and I/O access. In this paper we propose a hybrid hardware/software mechanism which is able to collect memory reference trace as well as semantic information. Based on this mechanism, we designed and implemented a prototype system called HMTT (Hybrid Memory Trace Tool) which adopts a DIMMsnooping mechanism to snoop on memory bus and a software-controlled tracing mechanism to inject semantic information into normal memory trace. To the best of our knowledge, the HMTT system is the first hardware tracing system capable of correlating memory trace with high-level events. Comprehensive validations and evaluations show that the HMTT system has both hardware's (e.g., no distortion or pollution) and software's advantages (e.g., flexibility and more information).
Extensible Pattern Matching in an Extensible Language
Venue: arXiv cs.PL 2011
Year: 2011

Pattern matching is a widely used technique in functional languages, especially those in the ML and Haskell traditions, where it is at the core of the semantics. In languages in the Lisp tradition, in contrast, pattern matching it typically provided by libraries built with macros. We present match, a sophisticated pattern matcher for Racket, implemented as language extension. using macros. The system supports novel and widely-useful pattern-matching forms, and is itself extensible. The extensibility of match is implemented via a general technique for creating extensible language extensions.
Automated Software Testing Using Metahurestic Technique Based on An Ant Colony Optimization
Venue: arXiv cs.SE 2011
Year: 2011

Software testing is an important and valuable part of the software development life cycle. Due to time, cost and other circumstances, exhaustive testing is not feasible that's why there is a need to automate the software testing process. Testing effectiveness can be achieved by the State Transition Testing (STT) which is commonly used in real time, embedded and web-based type of software systems. Aim of the current paper is to present an algorithm by applying an ant colony optimization technique, for generation of optimal and minimal test sequences for behavior specification of software. Present paper approach generates test sequence in order to obtain the complete software coverage. This paper also discusses the comparison between two metaheuristic techniques (Genetic Algorithm and Ant Colony optimization) for transition based testing
Robust Mobile Object Tracking Based on Multiple Feature Similarity and Trajectory Filtering
Venue: arXiv cs.CV 2011
Year: 2011

This paper presents a new algorithm to track mobile objects in different scene conditions. The main idea of the proposed tracker includes estimation, multi-features similarity measures and trajectory filtering. A feature set (distance, area, shape ratio, color histogram) is defined for each tracked object to search for the best matching object. Its best matching object and its state estimated by the Kalman filter are combined to update position and size of the tracked object. However, the mobile object trajectories are usually fragmented because of occlusions and misdetections. Therefore, we also propose a trajectory filtering, named global tracker, aims at removing the noisy trajectories and fusing the fragmented trajectories belonging to a same mobile object. The method has been tested with five videos of different scene conditions. Three of them are provided by the ETISEO benchmarking project (http://www-sop.inria.fr/orion/ETISEO) in which the proposed tracker performance has been compared with other seven tracking algorithms. The advantages of our approach over the existing state of the art ones are: (i) no prior knowledge information is required (e.g. no calibration and no contextual models are needed), (ii) the tracker is more reliable by combining multiple feature similarities, (iii) the tracker can perform in different scene conditions: single/several mobile objects, weak/strong illumination, indoor/outdoor scenes, (iv) a trajectory filtering is defined and applied to improve the tracker performance, (v) the tracker performance outperforms many algorithms of the state of the art.
Who clicks there!: Anonymizing the photographer in a camera saturated society
Venue: arXiv cs.CR 2011
Year: 2011

In recent years, social media has played an increasingly important role in reporting world events. The publication of crowd-sourced photographs and videos in near real-time is one of the reasons behind the high impact. However, the use of a camera can draw the photographer into a situation of conflict. Examples include the use of cameras by regulators collecting evidence of Mafia operations; citizens collecting evidence of corruption at a public service outlet; and political dissidents protesting at public rallies. In all these cases, the published images contain fairly unambiguous clues about the location of the photographer (scene viewpoint information). In the presence of adversary operated cameras, it can be easy to identify the photographer by also combining leaked information from the photographs themselves. We call this the camera location detection attack. We propose and review defense techniques against such attacks. Defenses such as image obfuscation techniques do not protect camera-location information; current anonymous publication technologies do not help either. However, the use of view synthesis algorithms could be a promising step in the direction of providing probabilistic privacy guarantees.
Co-c.e. spheres and cells in computable metric spaces
Venue: arXiv cs.LO 2011
Year: 2011

We investigate conditions under which a co-computably enumerable set in a computable metric space is computable. Using higher-dimensional chains and spherical chains we prove that in each computable metric space which is locally computable each co-computably enumerable sphere is computable and each co-c.e. cell with co-c.e. boundary sphere is computable.
Dominating Induced Matchings for P7-Free Graphs in Linear Time
Venue: arXiv cs.DM 2011
Year: 2011

Let $G$ be a finite undirected graph with edge set $E$. An edge set $E' \subseteq E$ is an {\em induced matching} in $G$ if the pairwise distance of the edges of $E'$ in $G$ is at least two; $E'$ is {\em dominating} in $G$ if every edge $e \in E \setminus E'$ intersects some edge in $E'$. The \emph{Dominating Induced Matching Problem} (\emph{DIM}, for short) asks for the existence of an induced matching $E'$ which is also dominating in $G$; this problem is also known as the \emph{Efficient Edge Domination} Problem. The DIM problem is related to parallel resource allocation problems, encoding theory and network routing. It is \NP-complete even for very restricted graph classes such as planar bipartite graphs with maximum degree three. However, its complexity was open for $P_k$-free graphs for any $k \ge 5$; $P_k$ denotes a chordless path with $k$ vertices and $k-1$ edges. We show in this paper that the weighted DIM problem is solvable in linear time for $P_7$-free graphs in a robust way.
Algebraic codes for Slepian-Wolf code design
Venue: arXiv cs.IT 2011
Year: 2011

Practical constructions of lossless distributed source codes (for the Slepian-Wolf problem) have been the subject of much investigation in the past decade. In particular, near-capacity achieving code designs based on LDPC codes have been presented for the case of two binary sources, with a binary-symmetric correlation. However, constructing practical codes for the case of non-binary sources with arbitrary correlation remains by and large open. From a practical perspective it is also interesting to consider coding schemes whose performance remains robust to uncertainties in the joint distribution of the sources. In this work we propose the usage of Reed-Solomon (RS) codes for the asymmetric version of this problem. We show that algebraic soft-decision decoding of RS codes can be used effectively under certain correlation structures. In addition, RS codes offer natural rate adaptivity and performance that remains constant across a family of correlation structures with the same conditional entropy. The performance of RS codes is compared with dedicated and rate adaptive multistage LDPC codes (Varodayan et al. '06), where each LDPC code is used to compress the individual bit planes. Our simulations show that in classical Slepian-Wolf scenario, RS codes outperform both dedicated and rate-adaptive LDPC codes under $q$-ary symmetric correlation, and are better than rate-adaptive LDPC codes in the case of sparse correlation models, where the conditional distribution of the sources has only a few dominant entries. In a feedback scenario, the performance of RS codes is comparable with both designs of LDPC codes. Our simulations also demonstrate that the performance of RS codes in the presence of inaccuracies in the joint distribution of the sources is much better as compared to multistage LDPC codes.
A Unified Relevance Retrieval Model by Eliteness Hypothesis
Venue: arXiv cs.IR 2011
Year: 2011

In this paper, an Eliteness Hypothesis for information retrieval is proposed, where we define two generative processes to create information items and queries. By assuming the deterministic relationships between the eliteness of terms and relevance, we obtain a new theoretical retrieval framework. The resulting ranking function is a unified one as it is capable of using available relevance information on both the document and the query, which is otherwise unachievable by existing retrieval models. Our preliminary experiment on a simple ranking function has demonstrated the potential of the approach.
A Characterization of the SPARC T3-4 System
Venue: arXiv cs.PF 2011
Year: 2011

This technical report covers a set of experiments on the 64-core SPARC T3-4 system, comparing it to two similar AMD and Intel systems. Key characteristics as maximum integer and floating point arithmetic throughput are measured as well as memory throughput, showing the scalability of the SPARC T3-4 system. The performance of POSIX threads primitives is characterized and compared in detail, such as thread creation and mutex synchronization. Scalability tests with a fine grained multithreaded runtime are performed, showing problems with atomic CAS operations on such physically highly parallel systems.
A new DFM approach to combine machining and additive manufacturing
Venue: arXiv cs.OH 2011
Year: 2011

Design For Manufacturing (DFM) approaches aim to integrate manufacturability aspects during the design stage. Most of DFM approaches usually consider only one manufacturing process, but products competitiveness may be improved by designing hybrid modular products, in which products are seen as 3-D puzzles with modules realized aside by the best manufacturing process and further gathered. A new DFM system is created in order to give quantitative information during the product design stage of which modules will benefit in being machined and which ones will advantageously be realized by an additive process (such as Selective Laser Sintering or laser deposition). A methodology for a manufacturability evaluation in case of a subtractive or an additive manufacturing process is developed and implemented in a CAD software. Tests are carried out on industrial products from automotive industry.
Reducing Interpolation on Multi-Grid to Quantizing Grid's Data-Base as a Recursion
Venue: arXiv cs.DC 2011
Year: 2011

In his article "Powerlist: A Structure for Parallel Recursion" Jayadev Misra wrote: "Many data parallel algorithms Fast Fourier Transform, Batcher's sorting schemes and prefix sum -exhibit recursive structure. We propose a data structure, powerlist, that permits succinct descriptions of such algorithms, highlighting the roles of both parallelism and recursion. Simple algebraic properties of this data structure can be exploited to derive properties of these algorithms and establish equivalence of different algorithms that solve the same problem." The quote above illustrates a widely shared assumption about recursion implementations: either they are done in purely structural terms or they cannot be done at all. Multi-dimensional interpolation on a grid is one of hosts of semi-recursive schemes that, while often referred to as recursive and routinely described in vaguely recursive terms, cannot be implemented as a recursion in their structural entirety. This article describes a computer-implemented scheme for isolating the recursive core of interpolation on a multi-grid, an arrangement that both stems from and provides a structural framework to a number of multi-dimensional interpolation optimization techniques that, once implemented, provide gains in multi-dimensional interpolation speed that, compared to some known benchmarks, measure in multiple orders of magnitude. Categories and Subject Descriptors: Multi-dimensional Programming; Concurrent Programming; Recursion General terms: Parallel Processing, Prioritized Processing, Interpolation, Recursion, Multi-Cube
Conditional Elimination through Code Duplication
Venue: arXiv cs.PL 2011
Year: 2011

We propose an optimizing transformation which reduces program runtime at the expense of program size by eliminating conditional jumps.
One Dimensional p-adic Integral Value Transformations
Venue: arXiv cs.DM 2011
Year: 2011

In this paper, a set of transformations T^(p,k) is defined on N_0^K to N_0. Some basic and naïve mathematical structure of T^(p,1) are adumbrated and introduced the concept of discrete dynamical systems through IVTs. Latterly, some further research scope of IVTs is highlighted.
Finding the Maximal Empty Rectangle Containing a Query Point
Venue: arXiv cs.CG 2011
Year: 2011

Let $P$ be a set of $n$ points in an axis-parallel rectangle $B$ in the plane. We present an $O(nα(n)\log^4 n)$-time algorithm to preprocess $P$ into a data structure of size $O(nα(n)\log^3 n)$, such that, given a query point $q$, we can find, in $O(\log^4 n)$ time, the largest-area axis-parallel rectangle that is contained in $B$, contains $q$, and its interior contains no point of $P$. This is a significant improvement over the previous solution of Augustine {\em et al.} \cite{qmex}, which uses slightly superquadratic preprocessing and storage.
Robust Bayesian reinforcement learning through tight lower bounds
Venue: arXiv cs.LG 2011
Year: 2011

In the Bayesian approach to sequential decision making, exact calculation of the (subjective) utility is intractable. This extends to most special cases of interest, such as reinforcement learning problems. While utility bounds are known to exist for this problem, so far none of them were particularly tight. In this paper, we show how to efficiently calculate a lower bound, which corresponds to the utility of a near-optimal memoryless policy for the decision problem, which is generally different from both the Bayes-optimal policy and the policy which is optimal for the expected MDP under the current belief. We then show how these can be applied to obtain robust exploration policies in a Bayesian reinforcement learning setting.
Uncertainty in Ontologies: Dempster-Shafer Theory for Data Fusion Applications
Venue: arXiv cs.AI 2011
Year: 2011

Nowadays ontologies present a growing interest in Data Fusion applications. As a matter of fact, the ontologies are seen as a semantic tool for describing and reasoning about sensor data, objects, relations and general domain theories. In addition, uncertainty is perhaps one of the most important characteristics of the data and information handled by Data Fusion. However, the fundamental nature of ontologies implies that ontologies describe only asserted and veracious facts of the world. Different probabilistic, fuzzy and evidential approaches already exist to fill this gap; this paper recaps the most popular tools. However none of the tools meets exactly our purposes. Therefore, we constructed a Dempster-Shafer ontology that can be imported into any specific domain ontology and that enables us to instantiate it in an uncertain manner. We also developed a Java application that enables reasoning about these uncertain ontological instances.
Verification of Quantum Programs
Venue: arXiv cs.LO 2011
Year: 2011

This paper develops verification methodology for quantum programs, and the contribution of the paper is two-fold: 1. Sharir, Pnueli and Hart [SIAM J. Comput. 13(1984)292-314] presented a general method for proving properties of probabilistic programs, in which a probabilistic program is modeled by a Markov chain and an assertion on the output distribution is extended into an invariant assertion on all intermediate distributions. Their method is essentially a probabilistic generalization of the classical Floyd inductive assertion method. In this paper, we consider quantum programs modeled by quantum Markov chains which are defined by super-operators. It is shown that the Sharir-Pnueli-Hart method can be elegantly generalized to quantum programs by exploiting the Schrödinger-Heisenberg duality between quantum states and observables. In particular, a completeness theorem for the Sharir-Pnueli-Hart verification method of quantum programs is established. 2. As indicated by the completeness theorem, the Sharir-Pnueli-Hart method is in principle effective for verifying all properties of quantum programs that can be expressed in terms of Hermitian operators (observables). But it is not feasible for many practical applications because of the complicated calculation involved in the verification. For the case of finite-dimensional state spaces, we find a method for verification of quantum programs much simpler than the Sharir-Pnueli-Hart method by employing the matrix representation of super-operators and Jordan decomposition of matrices. In particular, this method enables us to compute easily the average running time and even to analyze some interesting long-run behaviors of quantum programs in a finite-dimensional state space.
Discovery of Invariants through Automated Theory Formation
Venue: arXiv cs.LO 2011
Year: 2011

Refinement is a powerful mechanism for mastering the complexities that arise when formally modelling systems. Refinement also brings with it additional proof obligations -- requiring a developer to discover properties relating to their design decisions. With the goal of reducing this burden, we have investigated how a general purpose theory formation tool, HR, can be used to automate the discovery of such properties within the context of Event-B. Here we develop a heuristic approach to the automatic discovery of invariants and report upon a series of experiments that we undertook in order to evaluate our approach. The set of heuristics developed provides systematic guidance in tailoring HR for a given Event-B development. These heuristics are based upon proof-failure analysis, and have given rise to some promising results.