OpenRaiser/Intern-Atlas huggingface dataset:
A Two Step Perspective for Kripke Structure Reduction
Venue: arXiv cs.FL 2012
Year: 2012

This paper presents a novel theoretical framework for the state space reduction of Kripke structures. We define two equivalence relations, Kripke minimization equivalence (KME) and weak Kripke minimization equivalence (WKME). We define the quotient system under these relations and show that these relations are strictly coarser than strong (bi)simulation and divergence-sensitive stutter (bi)simulation, respectively. We prove that the quotient system obtained under KME and WKME preserves linear-time and stutter-insensitive linear-time properties. Finally, we show that KME is compositional w.r.t. synchronous parallel composition.
Multi-Agent Programming Contest 2012 - The Python-DTU Team
Venue: arXiv cs.MA 2012
Year: 2012

We provide a brief description of the Python-DTU system, including the overall design, the tools and the algorithms that we plan to use in the agent contest.
Graph Size Estimation
Venue: arXiv cs.SI 2012
Year: 2012

Many online networks are not fully known and are often studied via sampling. Random Walk (RW) based techniques are the current state-of-the-art for estimating nodal attributes and local graph properties, but estimating global properties remains a challenge. In this paper, we are interested in a fundamental property of this type - the graph size N, i.e., the number of its nodes. Existing methods for estimating N are (i) inefficient and (ii) cannot be easily used with RW sampling due to dependence between successive samples. In this paper, we address both problems. First, we propose IE (Induced Edges), an efficient technique for estimating N from an independence sample of graph's nodes. IE exploits the edges induced on the sampled nodes. Second, we introduce SafetyMargin, a method that corrects estimators for dependence in RW samples. Finally, we combine these two stand-alone techniques to obtain a RW-based graph size estimator. We evaluate our approach in simulations on a wide range of real-life topologies, and on several samples of Facebook. IE with SafetyMargin typically requires at least 10 times fewer samples than the state-of-the-art techniques (over 100 times in the case of Facebook) for the same estimation error.
PCNM: A New Platform for Cellular Networks Measurements and Optimization
Venue: arXiv cs.NI 2012
Year: 2012

In this paper, we present PCNM, a new mobile platform for cellular networks measurements. PCNM is based on a set of techniques that tailors theoretical calculations and simulations to the real cellular network environment. It includes: (a) modules that measure different parameters of a base station (BS) such as localization, cells identification, time advance information, reception level and quality, (b) a new protocol that optimizes the task of network measurement by monitoring a set of mobile nodes and finally (c) the ability to extend an existing cellular network by adding new base stations. We evaluate our genetic algorithm used to reduce the nodes mobility and optimize the measurement extraction of N base stations using k mobile sensors (k >= 1). We show how connecting real measurements (using mobile sensors in a collaborative way) to theoretical and prediction methods is of high benefits for cellular networks maintenance, extension and performances evaluation.
Joint Source-Channel Coding for Deep-Space Image Transmission using Rateless Codes
Venue: arXiv cs.IT 2012
Year: 2012

A new coding scheme for image transmission over noisy channel is proposed. Similar to standard image compression, the scheme includes a linear transform followed by successive refinement scalar quantization. Unlike conventional schemes, in the proposed system the quantized transform coefficients are linearly mapped into channel symbols using systematic linear encoders. This fixed-to-fixed length "linear index coding" approach avoids the use of an explicit entropy coding stage (e.g., arithmetic or Huffman coding), which is typically fragile to channel post-decoding residual errors. We use linear codes over GF(4), which are particularly suited for this application, since they are matched to the dead-zone quantizer symbol alphabet and to the QPSK modulation used on the deep-space communication channel. We optimize the proposed system where the linear codes are systematic Raptor codes over GF(4). The rateless property of Raptor encoders allows to achieve a "continuum" of coding rates, in order to accurately match the channel coding rate to the transmission channel capacity and to the quantized source entropy rate for each transform subband and refinement level. Comparisons are provided with respect to the concatenation of state-of-the-art image coding and channel coding schemes used by Jet Propulsion Laboratories (JPL) for the Mars Exploration Rover (MER) Mission.
Planar shape manipulation using approximate geometric primitives
Venue: arXiv cs.CG 2012
Year: 2012

We present robust algorithms for set operations and Euclidean transformations of curved shapes in the plane using approximate geometric primitives. We use a refinement algorithm to ensure consistency. Its computational complexity is $\bigo(n\log n+k)$ for an input of size $n$ with $k=\bigo(n^2)$ consistency violations. The output is as accurate as the geometric primitives. We validate our algorithms in floating point using sequences of six set operations and Euclidean transforms on shapes bounded by curves of algebraic degree~1 to~6. We test generic and degenerate inputs. Keywords: robust computational geometry, plane subdivisions, set operations.
Stream on the Sky: Outsourcing Access Control Enforcement for Stream Data to the Cloud
Venue: arXiv cs.CR 2012
Year: 2012

There is an increasing trend for businesses to migrate their systems towards the cloud. Security concerns that arise when outsourcing data and computation to the cloud include data confidentiality and privacy. Given that a tremendous amount of data is being generated everyday from plethora of devices equipped with sensing capabilities, we focus on the problem of access controls over live streams of data based on triggers or sliding windows, which is a distinct and more challenging problem than access control over archival data. Specifically, we investigate secure mechanisms for outsourcing access control enforcement for stream data to the cloud. We devise a system that allows data owners to specify fine-grained policies associated with their data streams, then to encrypt the streams and relay them to the cloud for live processing and storage for future use. The access control policies are enforced by the cloud, without the latter learning about the data, while ensuring that unauthorized access is not feasible. To realize these ends, we employ a novel cryptographic primitive, namely proxy-based attribute-based encryption, which not only provides security but also allows the cloud to perform expensive computations on behalf of the users. Our approach is holistic, in that these controls are integrated with an XML based framework (XACML) for high-level management of policies. Experiments with our prototype demonstrate the feasibility of such mechanisms, and early evaluations suggest graceful scalability with increasing numbers of policies, data streams and users.
Distributed High Dimensional Information Theoretical Image Registration via Random Projections
Venue: arXiv cs.IT 2012
Year: 2012

Information theoretical measures, such as entropy, mutual information, and various divergences, exhibit robust characteristics in image registration applications. However, the estimation of these quantities is computationally intensive in high dimensions. On the other hand, consistent estimation from pairwise distances of the sample points is possible, which suits random projection (RP) based low dimensional embeddings. We adapt the RP technique to this task by means of a simple ensemble method. To the best of our knowledge, this is the first distributed, RP based information theoretical image registration approach. The efficiency of the method is demonstrated through numerical examples.
Schrödinger Diffusion for Shape Analysis with Texture
Venue: arXiv cs.CV 2012
Year: 2012

In recent years, quantities derived from the heat equation have become popular in shape processing and analysis of triangulated surfaces. Such measures are often robust with respect to different kinds of perturbations, including near-isometries, topological noise and partialities. Here, we propose to exploit the semigroup of a Schrödinger operator in order to deal with texture data, while maintaining the desirable properties of the heat kernel. We define a family of Schrödinger diffusion distances analogous to the ones associated to the heat kernels, and show that they are continuous under perturbations of the data. As an application, we introduce a method for retrieval of textured shapes through comparison of Schrödinger diffusion distance histograms with the earth's mover distance, and present some numerical experiments showing superior performance compared to an analogous method that ignores the texture.
The Definition of AI in Terms of Multi Agent Systems
Venue: arXiv cs.AI 2012
Year: 2012

The questions which we will consider here are "What is AI?" and "How can we make AI?". Here we will present the definition of AI in terms of multi-agent systems. This means that here you will not find a new answer to the question "What is AI?", but an old answer in a new form. This new form of the definition of AI is of interest for the theory of multi-agent systems because it gives us better understanding of this theory. More important is that this work will help us answer the second question. We want to make a program which is capable of constructing a model of its environment. Every multi-agent model is equivalent to a single-agent model but multi-agent models are more natural and accordingly more easily discoverable.
A Survey of Delay Tolerant Networks Routing Protocols
Venue: arXiv cs.NI 2012
Year: 2012

Advances in Micro-Electro-Mechanical Systems (MEMS) have revolutionized the digital age to a point where animate and inanimate objects can be used as a communication channel. In addition, the ubiquity of mobile phones with increasing capabilities and ample resources means people are now effectively mobile sensors that can be used to sense the environment as well as data carriers. These objects, along with their devices, form a new kind of networks that are characterized by frequent disconnections, resource constraints and unpredictable or stochastic mobility patterns. A key underpinning in these networks is routing or data dissemination protocols that are designed specifically to handle the aforementioned characteristics. Therefore, there is a need to review state-of-the-art routing protocols, categorize them, and compare and contrast their approaches in terms of delivery rate, resource consumption and end-to-end delay. To this end, this paper reviews 63 unicast, multicast and coding-based routing protocols that are designed specifically to run in delay tolerant or challenged networks. We provide an extensive qualitative comparison of all protocols, highlight their experimental setup and outline their deficiencies in terms of design and research methodology. Apart from that, we review research that aims to exploit studies on social networks and epidemiology in order to improve routing protocol performance. Lastly, we provide a list of future research directions.
Logical segmentation for article extraction in digitized old newspapers
Venue: arXiv cs.IR 2012
Year: 2012

Newspapers are documents made of news item and informative articles. They are not meant to be red iteratively: the reader can pick his items in any order he fancies. Ignoring this structural property, most digitized newspaper archives only offer access by issue or at best by page to their content. We have built a digitization workflow that automatically extracts newspaper articles from images, which allows indexing and retrieval of information at the article level. Our back-end system extracts the logical structure of the page to produce the informative units: the articles. Each image is labelled at the pixel level, through a machine learning based method, then the page logical structure is constructed up from there by the detection of structuring entities such as horizontal and vertical separators, titles and text lines. This logical structure is stored in a METS wrapper associated to the ALTO file produced by the system including the OCRed text. Our front-end system provides a web high definition visualisation of images, textual indexing and retrieval facilities, searching and reading at the article level. Articles transcriptions can be collaboratively corrected, which as a consequence allows for better indexing. We are currently testing our system on the archives of the Journal de Rouen, one of France eldest local newspaper. These 250 years of publication amount to 300 000 pages of very variable image quality and layout complexity. Test year 1808 can be consulted at plair.univ-rouen.fr.
Students Perceptions of the Effectiveness of Discussion Boards What can we get from our students for a freebie point
Venue: arXiv cs.CY 2012
Year: 2012

We investigate how the students think of their experience in a junior 300 level computer science course that uses blackboard as the underlying course management system. The discussion boards in Blackboard are heavily used for programming project support and to foster cooperation among students to answer their questions and concerns. A survey is conducted through blackboard as a voluntary quiz and the student who participated were given a participation point for their effort. The results and the participation were very interesting. We obtained statistics from the answers to the questions. The students also have given us feedback in the form of comments to all questions except for two only. The students have shown understanding, maturity and willingness to participate in pedagogy-enhancing endeavors with the premise that it might help their education and other people education as well.
On streams that are finitely red
Venue: arXiv cs.LO 2012
Year: 2012

Mixing induction and coinduction, we study alternative definitions of streams being finitely red. We organize our definitions into a hierarchy including also some well-known alternatives in intuitionistic analysis. The hierarchy collapses classically, but is intuitionistically of strictly decreasing strength. We characterize the differences in strength in a precise way by weak instances of the Law of Excluded Middle.
Evaluating Discussion Boards on BlackBoard as a Collaborative Learning Tool A Students Survey and Reflections
Venue: arXiv cs.CV 2012
Year: 2012

In this paper, we investigate how the students think of their experience in a junior level course that has a blackboard course presence where the students use the discussion boards extensively. A survey is set up through blackboard as a voluntary quiz and the student who participated were given a freebie point. The results and the participation were very interesting in terms of the feedback we got via open comments from the students as well as the statistics we gathered from the answers to the questions. The students have shown understanding and willingness to participate in pedagogy-enhancing endeavors.
Graphical Visualization of Risk Assessment for Effective Risk Management during Software Development Process
Venue: arXiv cs.SE 2012
Year: 2012

Success of any IT industry depends on the success rate of their projects, which in turn depends on several factors such as cost, time, and availability of resources. These factors formulate the risk areas, which needs to be addressed in a proactive way. The rudimentary objective of risk management is to circumvent the possibility of their occurrence by identifying the risks, preparing the contingency plans and mitigation plans in order to reduce the consequences of the risks. Hence, effective risk management becomes one of the imperative challenges in any organization, which if deemed in an apt way assures the continued sustainability of the organization in the high-end competitive environment. This paper provides visualization of risk assessment through a graphical model. Further, the matrix representation of the risk assessment aids the project personnel to identify all the risks, comprehend their frequency and probability of their occurrence. In addition, the graphical model enables one to analyze the impact of identified risks and henceforth to assign their priorities. This mode of representation of risk assessment factors helps the organization in accurate prediction of success rate of the project.
Learning Heterogeneous Similarity Measures for Hybrid-Recommendations in Meta-Mining
Venue: arXiv cs.LG 2012
Year: 2012

The notion of meta-mining has appeared recently and extends the traditional meta-learning in two ways. First it does not learn meta-models that provide support only for the learning algorithm selection task but ones that support the whole data-mining process. In addition it abandons the so called black-box approach to algorithm description followed in meta-learning. Now in addition to the datasets, algorithms also have descriptors, workflows as well. For the latter two these descriptions are semantic, describing properties of the algorithms. With the availability of descriptors both for datasets and data mining workflows the traditional modelling techniques followed in meta-learning, typically based on classification and regression algorithms, are no longer appropriate. Instead we are faced with a problem the nature of which is much more similar to the problems that appear in recommendation systems. The most important meta-mining requirements are that suggestions should use only datasets and workflows descriptors and the cold-start problem, e.g. providing workflow suggestions for new datasets. In this paper we take a different view on the meta-mining modelling problem and treat it as a recommender problem. In order to account for the meta-mining specificities we derive a novel metric-based-learning recommender approach. Our method learns two homogeneous metrics, one in the dataset and one in the workflow space, and a heterogeneous one in the dataset-workflow space. All learned metrics reflect similarities established from the dataset-workflow preference matrix. We demonstrate our method on meta-mining over biological (microarray datasets) problems. The application of our method is not limited to the meta-mining problem, its formulations is general enough so that it can be applied on problems with similar requirements.
Methods of QoS improvement for P2P IPTV based on traffic modelling
Venue: arXiv cs.NI 2012
Year: 2012

Over the last years many technological advances were introduced in Internet television to meet user needs and expectations. However due to an overwhelming bandwidth requirements traditional IP-based television service based on simple client-server approach remains restricted to small group of clients. In such situation the use of the peer-to-peer overlay paradigm to deliver live television on the Internet is gaining increasing attention. Unfortunately the current Internet infrastructure provides only best effort services for this kind of applications and do not offer quality of service. This paper is a research proposition which presents potential solutions for efficient IPTV streaming over P2P networks. We assume that the solutions will not directly modify existing P2P IPTV protocols but rather will be dedicated for a network engineer or an Internet service provider which will be able to introduce and configure the proposed mechanisms in network routers.
Relation Liftings on Preorders and Posets
Venue: arXiv cs.LO 2012
Year: 2012

The category Rel(Set) of sets and relations can be described as a category of spans and as the Kleisli category for the powerset monad. A set-functor can be lifted to a functor on Rel(Set) iff it preserves weak pullbacks. We show that these results extend to the enriched setting, if we replace sets by posets or preorders. Preservation of weak pullbacks becomes preservation of exact lax squares. As an application we present Moss's coalgebraic over posets.
Controlled Collaboration for Linear Coherent Estimation in Wireless Sensor Networks
Venue: arXiv cs.IT 2012
Year: 2012

We consider a wireless sensor network consisting of multiple nodes that are coordinated by a fusion center (FC) in order to estimate a common signal of interest. In addition to being coordinated, the sensors are also able to collaborate, i.e., share observations with other neighboring nodes, prior to transmission. In an earlier work, we derived the energy-optimal collaboration strategy for the single-snapshot framework, where the inference has to be made based on observations collected at one particular instant. In this paper, we make two important contributions. Firstly, for the single-snapshot framework, we gain further insights into partially connected collaboration networks (nearest-neighbor and random geometric graphs for example) through the analysis of a family of topologies with regular structure. Secondly, we explore the estimation problem by adding the dimension of time, where the goal is to estimate a time-varying signal in a power-constrained network. To model the time dynamics, we consider the stationary Gaussian process with exponential covariance (sometimes referred to as Ornstein-Uhlenbeck process) as our representative signal. For such a signal, we show that it is always beneficial to sample as frequently as possible, despite the fact that the samples get increasingly noisy due to the power-constrained nature of the problem. Simulation results are presented to corroborate our analytical results.
Promising outcomes of an online course in research writing at a Rwandan university
Venue: arXiv cs.CY 2012
Year: 2012

Background: Researchers in developing countries often do not have access to training on research writing. The purpose of this study was to test whether researchers in Rwanda might complete and benefit from a pilot online course in research writing. Methods: The pilot course was set up on Moodle, an open-source online learning environment, and facilitated by the author. The lessons and assignment were spread over six weeks, followed by a two-week extension period. Twenty-eight faculty members of the National University of Rwanda enrolled themselves in the course. Results: Twenty-five of the 28 learners completed the course. After the course, these learners expressed high satisfaction, e.g, 24 of them felt that they were ready to write a research paper for publication. Conclusion: The high completion rate (89%) is noteworthy for two reasons: e-learning courses tend to have lower completion rates than classroom courses, and 76% of the learners in the pilot course had not taken an e-learning course before. This result and the positive feedback indicate that online courses can benefit researchers in developing countries who may not have access to classroom courses on research writing.