OpenRaiser/Intern-Atlas huggingface dataset:
Piecemeal Journey To 'HALCYON' World Of Pervasive Computing : From past progress to future challenges
Venue: arXiv cs.HC 2010
Year: 2010

Although 'Halcyon' means serene environment which pervasive computing aims at, we have tried to present a different interpretation of this word. Through our approach, we look at it in context of achieving future 'calm technology'. The paper gives a general overview of the state of pervasive computing today, proposes the 'HALCYON Model' and outlines the 'social' challenges faced by system designers.
Inductive Logic Programming in Databases: from Datalog to DL+log
Venue: arXiv cs.LO 2010
Year: 2010

In this paper we address an issue that has been brought to the attention of the database community with the advent of the Semantic Web, i.e. the issue of how ontologies (and semantics conveyed by them) can help solving typical database problems, through a better understanding of KR aspects related to databases. In particular, we investigate this issue from the ILP perspective by considering two database problems, (i) the definition of views and (ii) the definition of constraints, for a database whose schema is represented also by means of an ontology. Both can be reformulated as ILP problems and can benefit from the expressive and deductive power of the KR framework DL+log. We illustrate the application scenarios by means of examples. Keywords: Inductive Logic Programming, Relational Databases, Ontologies, Description Logics, Hybrid Knowledge Representation and Reasoning Systems. Note: To appear in Theory and Practice of Logic Programming (TPLP).
Information Contagion: an Empirical Study of the Spread of News on Digg and Twitter Social Networks
Venue: arXiv cs.CY 2010
Year: 2010

Social networks have emerged as a critical factor in information dissemination, search, marketing, expertise and influence discovery, and potentially an important tool for mobilizing people. Social media has made social networks ubiquitous, and also given researchers access to massive quantities of data for empirical analysis. These data sets offer a rich source of evidence for studying dynamics of individual and group behavior, the structure of networks and global patterns of the flow of information on them. However, in most previous studies, the structure of the underlying networks was not directly visible but had to be inferred from the flow of information from one individual to another. As a result, we do not yet understand dynamics of information spread on networks or how the structure of the network affects it. We address this gap by analyzing data from two popular social news sites. Specifically, we extract social networks of active users on Digg and Twitter, and track how interest in news stories spreads among them. We show that social networks play a crucial role in the spread of information on these sites, and that network structure affects dynamics of information flow.
Some Remarks on the Model Theory of Epistemic Plausibility Models
Venue: arXiv cs.LO 2010
Year: 2010

Classical logics of knowledge and belief are usually interpreted on Kripke models, for which a mathematically well-developed model theory is available. However, such models are inadequate to capture dynamic phenomena. Therefore, epistemic plausibility models have been introduced. Because these are much richer structures than Kripke models, they do not straightforwardly inherit the model-theoretical results of modal logic. Therefore, while epistemic plausibility structures are well-suited for modeling purposes, an extensive investigation of their model theory has been lacking so far. The aim of the present paper is to fill exactly this gap, by initiating a systematic exploration of the model theory of epistemic plausibility models. Like in 'ordinary' modal logic, the focus will be on the notion of bisimulation. We define various notions of bisimulations (parametrized by a language L) and show that L-bisimilarity implies L-equivalence. We prove a Hennesy-Milner type result, and also two undefinability results. However, our main point is a negative one, viz. that bisimulations cannot straightforwardly be generalized to epistemic plausibility models if conditional belief is taken into account. We present two ways of coping with this issue: (i) adding a modality to the language, and (ii) putting extra constraints on the models. Finally, we make some remarks about the interaction between bisimulation and dynamic model changes.
Nearly Optimal Resource Allocation for Downlink OFDMA in 2-D Cellular Networks
Venue: arXiv cs.IT 2010
Year: 2010

In this paper, we propose a resource allocation algorithm for the downlink of sectorized two-dimensional (2-D) OFDMA cellular networks assuming statistical Channel State Information (CSI) and fractional frequency reuse. The proposed algorithm can be implemented in a distributed fashion without the need to any central controlling units. Its performance is analyzed assuming fast fading Rayleigh channels and Gaussian distributed multicell interference. We show that the transmit power of this simple algorithm tends, as the number of users grows to infinity, to the same limit as the minimal power required to satisfy all users' rate requirements i.e., the proposed resource allocation algorithm is asymptotically optimal. As a byproduct of this asymptotic analysis, we characterize a relevant value of the reuse factor that only depends on an average state of the network.
Hierarchical Location Service with Prediction in Mobile Ad-Hoc Networks
Venue: arXiv cs.NI 2010
Year: 2010

Position-based routing protocols take advantage of location information to perform a stateless and efficient routing. To enable position-based routing, a node must be able to discover the location of the messages' destination node. This task is typically accomplished by a location service. Recently, several location service protocols have been developed for ad hoc networks. In this paper we propose a novel location service called PHLS: Predictive Hierarchical Location Service. In PHLS, the entire network is partitioned into a hierarchy of smaller and smaller regions. For each node, one node in each-level region of the hierarchy is chosen as its local location server. When the network initializes or when a node attaches the network, nodes contact their local location server with their current location information (ie. position and velocity). Then, they only need to update their location server when they move away from their current region. Finally, nodes query their location servers and get the exact or predicted location of destination nodes.
Effective closed subshifts in 1D can be implemented in 2D
Venue: arXiv cs.LO 2010
Year: 2010

In this paper we use fixed point tilings to answer a question posed by Michael Hochman and show that every one-dimensional effectively closed subshift can be implemented by a local rule in two dimensions. The proof uses the fixed-point construction of an aperiodic tile set and its extensions.
Querying Incomplete Data over Extended ER Schemata
Venue: arXiv cs.DB 2010
Year: 2010

Since Chen's Entity-Relationship (ER) model, conceptual modeling has been playing a fundamental role in relational data design. In this paper we consider an extended ER (EER) model enriched with cardinality constraints, disjointness assertions, and is-a relations among both entities and relationships. In this setting, we consider the case of incomplete data, which is likely to occur, for instance, when data from different sources are integrated. In such a context, we address the problem of providing correct answers to conjunctive queries by reasoning on the schema. Based on previous results about decidability of the problem, we provide a query answering algorithm that performs rewriting of the initial query into a recursive Datalog query encoding the information about the schema. We finally show extensions to more general settings. This paper will appear in the special issue of Theory and Practice of Logic Programming (TPLP) titled Logic Programming in Databases: From Datalog to Semantic-Web Rules.
Stability Analysis of Linear Uncertain Systems via Checking Positivity of Forms on Simplices
Venue: arXiv cs.SC 2010
Year: 2010

In this paper, we mainly study the robust stability of linear continuous systems with parameter uncertainties, a more general kind of uncertainties for system matrices is considered, i.e., entries of system matrices are rational functions of uncertain parameters which are varying in intervals. we present a method which can check the robust Hurwitz stability of such uncertain systems in finite steps. Examples show the efficiency of our approach.
Scalable, Time-Responsive, Digital, Energy-Efficient Molecular Circuits using DNA Strand Displacement
Venue: arXiv cs.OH 2010
Year: 2010

We propose a novel theoretical biomolecular design to implement any Boolean circuit using the mechanism of DNA strand displacement. The design is scalable: all species of DNA strands can in principle be mixed and prepared in a single test tube, rather than requiring separate purification of each species, which is a barrier to large-scale synthesis. The design is time-responsive: the concentration of output species changes in response to the concentration of input species, so that time-varying inputs may be continuously processed. The design is digital: Boolean values of wires in the circuit are represented as high or low concentrations of certain species, and we show how to construct a single-input, single-output signal restoration gate that amplifies the difference between high and low, which can be distributed to each wire in the circuit to overcome signal degradation. This means we can achieve a digital abstraction of the analog values of concentrations. Finally, the design is energy-efficient: if input species are specified ideally (meaning absolutely 0 concentration of unwanted species), then output species converge to their ideal concentrations at steady-state, and the system at steady-state is in (dynamic) equilibrium, meaning that no energy is consumed by irreversible reactions until the input again changes. Drawbacks of our design include the following. If input is provided non-ideally (small positive concentration of unwanted species), then energy must be continually expended to maintain correct output concentrations even at steady-state. In addition, our fuel species - those species that are permanently consumed in irreversible reactions - are not "generic"; each gate in the circuit is powered by its own specific type of fuel species. Hence different circuits must be powered by different types of fuel. Finally, we require input to be given according to the dual-rail convention, so that an input of 0 is specified not only by the absence of a certain species, but by the presence of another. That is, we do not construct a "true NOT gate" that sets its output to high concentration if and only if its input's concentration is low. It remains an open problem to design scalable, time-responsive, digital, energy-efficient molecular circuits that additionally solve one of these problems, or to prove that some subset of their resolutions are mutually incompatible.
Improved Bounds on Restricted Isometry Constants for Gaussian Matrices
Venue: arXiv cs.IT 2010
Year: 2010

The Restricted Isometry Constants (RIC) of a matrix $A$ measures how close to an isometry is the action of $A$ on vectors with few nonzero entries, measured in the $\ell^2$ norm. Specifically, the upper and lower RIC of a matrix $A$ of size $n\times N$ is the maximum and the minimum deviation from unity (one) of the largest and smallest, respectively, square of singular values of all ${N\choose k}$ matrices formed by taking $k$ columns from $A$. Calculation of the RIC is intractable for most matrices due to its combinatorial nature; however, many random matrices typically have bounded RIC in some range of problem sizes $(k,n,N)$. We provide the best known bound on the RIC for Gaussian matrices, which is also the smallest known bound on the RIC for any large rectangular matrix. Improvements over prior bounds are achieved by exploiting similarity of singular values for matrices which share a substantial number of columns.
k-Step Relative Inductive Generalization
Venue: arXiv cs.DM 2010
Year: 2010

We introduce a new form of SAT-based symbolic model checking. One common idea in SAT-based symbolic model checking is to generate new clauses from states that can lead to property violations. Our previous work suggests applying induction to generalize from such states. While effective on some benchmarks, the main problem with inductive generalization is that not all such states can be inductively generalized at a given time in the analysis, resulting in long searches for generalizable states on some benchmarks. This paper introduces the idea of inductively generalizing states relative to $k$-step over-approximations: a given state is inductively generalized relative to the latest $k$-step over-approximation relative to which the negation of the state is itself inductive. This idea motivates an algorithm that inductively generalizes a given state at the highest level $k$ so far examined, possibly by generating more than one mutually $k$-step relative inductive clause. We present experimental evidence that the algorithm is effective in practice.
Sliding window approach based Text Binarisation from Complex Textual images
Venue: arXiv cs.CV 2010
Year: 2010

Text binarisation process classifies individual pixels as text or background in the textual images. Binarization is necessary to bridge the gap between localization and recognition by OCR. This paper presents Sliding window method to binarise text from textual images with textured background. Suitable preprocessing techniques are applied first to increase the contrast of the image and blur the background noises due to textured background. Then Edges are detected by iterative thresholding. Subsequently formed edge boxes are analyzed to remove unwanted edges due to complex background and binarised by sliding window approach based character size uniformity check algorithm. The proposed method has been applied on localized region from heterogeneous textual images and compared with Otsu, Niblack methods and shown encouraging performance of the proposed method.
A Formal Approach to Modeling the Memory of a Living Organism
Venue: arXiv cs.AI 2010
Year: 2010

We consider a living organism as an observer of the evolution of its environment recording sensory information about the state space X of the environment in real time. Sensory information is sampled and then processed on two levels. On the biological level, the organism serves as an evaluation mechanism of the subjective relevance of the incoming data to the observer: the observer assigns excitation values to events in X it could recognize using its sensory equipment. On the algorithmic level, sensory input is used for updating a database, the memory of the observer whose purpose is to serve as a geometric/combinatorial model of X, whose nodes are weighted by the excitation values produced by the evaluation mechanism. These values serve as a guidance system for deciding how the database should transform as observation data mounts. We define a searching problem for the proposed model and discuss the model's flexibility and its computational efficiency, as well as the possibility of implementing it as a dynamic network of neuron-like units. We show how various easily observable properties of the human memory and thought process can be explained within the framework of this model. These include: reasoning (with efficiency bounds), errors, temporary and permanent loss of information. We are also able to define general learning problems in terms of the new model, such as the language acquisition problem.
On Extractors and Exposure-Resilient Functions for Sublogarithmic Entropy
Venue: arXiv cs.CC 2010
Year: 2010

We study deterministic extractors for oblivious bit-fixing sources (a.k.a. resilient functions) and exposure-resilient functions with small min-entropy: of the function's n input bits, k << n bits are uniformly random and unknown to the adversary. We simplify and improve an explicit construction of extractors for bit-fixing sources with sublogarithmic k due to Kamp and Zuckerman (SICOMP 2006), achieving error exponentially small in k rather than polynomially small in k. Our main result is that when k is sublogarithmic in n, the short output length of this construction (O(log k) output bits) is optimal for extractors computable by a large class of space-bounded streaming algorithms. Next, we show that a random function is an extractor for oblivious bit-fixing sources with high probability if and only if k is superlogarithmic in n, suggesting that our main result may apply more generally. In contrast, we show that a random function is a static (resp. adaptive) exposure-resilient function with high probability even if k is as small as a constant (resp. log log n). No explicit exposure-resilient functions achieving these parameters are known.
A Comprehensive Review of Image Enhancement Techniques
Venue: arXiv cs.CV 2010
Year: 2010

Principle objective of Image enhancement is to process an image so that result is more suitable than original image for specific application. Digital image enhancement techniques provide a multitude of choices for improving the visual quality of images. Appropriate choice of such techniques is greatly influenced by the imaging modality, task at hand and viewing conditions. This paper will provide an overview of underlying concepts, along with algorithms commonly used for image enhancement. The paper focuses on spatial domain techniques for image enhancement, with particular reference to point processing methods and histogram processing.
Plagiarism Detection using ROUGE and WordNet
Venue: arXiv cs.OH 2010
Year: 2010

With the arrival of digital era and Internet, the lack of information control provides an incentive for people to freely use any content available to them. Plagiarism occurs when users fail to credit the original owner for the content referred to, and such behavior leads to violation of intellectual property. Two main approaches to plagiarism detection are fingerprinting and term occurrence; however, one common weakness shared by both approaches, especially fingerprinting, is the incapability to detect modified text plagiarism. This study proposes adoption of ROUGE and WordNet to plagiarism detection. The former includes ngram co-occurrence statistics, skip-bigram, and longest common subsequence (LCS), while the latter acts as a thesaurus and provides semantic information. N-gram co-occurrence statistics can detect verbatim copy and certain sentence modification, skip-bigram and LCS are immune from text modification such as simple addition or deletion of words, and WordNet may handle the problem of word substitution.
Computation of Reducts Using Topology and Measure of Significance of Attributes
Venue: arXiv cs.IR 2010
Year: 2010

Data generated in the fields of science, technology, business and in many other fields of research are increasing in an exponential rate. The way to extract knowledge from a huge set of data is a challenging task. This paper aims to propose a hybrid and viable method to deal with an information system in data mining, using topological techniques and the significance of the attributes measured using rough set theory, to compute the reduct, This will reduce the randomness in the process of elimination of redundant attributes, which, in turn, will reduce the complexity of the computation of reducts of an information system where a large amount of data have to be processed.
Comparative Study of Hidden Node Problem and Solution Using Different Techniques and Protocols
Venue: arXiv cs.NI 2010
Year: 2010

Hidden nodes in a wireless network refer to nodes that are out of range of other nodes or a collection of nodes. We will discuss a few problems introduced by the RTS/CTS mechanism of collision avoidance and focus on the virtual jamming problem, which allows a malicious node to effectively jam a large fragment of a wireless network at minimum expense of power. We have also discussed WiCCP (Wireless Central Coordinated Protocol) which is a protocol booster that also provides good solution to hidden nodes.
Quality of Service with Bandwidth
Venue: arXiv cs.NI 2010
Year: 2010

This paper deals with providing Quality of Service (QoS) over IP based networks. We are going to give a brief survey about this topic, and present our work at this area. There are many solutions of the problem, but the standardization of the methods is not finished yet. At the moment there are two kinds of approaches of the reservation problem. The distributed method handles the network nodes independently, and get the nodes making their own admittance decisions along the reservation path (i.e. Border Gateway Reservation Protocol BGRP. The centralized way -we discuss in details-, which collects the network nodes into domains, and handles them using a network manager. Generally there are two significant parts of the network management: intra domain, and inter-domain. This article focuses on making reservations over several domains, which is the part of the inter-domain functions.
Similarity Data Item Set Approach: An Encoded Temporal Data Base Technique
Venue: arXiv cs.DB 2010
Year: 2010

Data mining has been widely recognized as a powerful tool to explore added value from large-scale databases. Finding frequent item sets in databases is a crucial in data mining process of extracting association rules. Many algorithms were developed to find the frequent item sets. This paper presents a summary and a comparative study of the available FP-growth algorithm variations produced for mining frequent item sets showing their capabilities and efficiency in terms of time and memory consumption on association rule mining by taking application of specific information into account. It proposes pattern growth mining paradigm based FP-tree growth algorithm, which employs a tree structure to compress the database. The performance study shows that the anti- FP-growth method is efficient and scalable for mining both long and short frequent patterns and is about an order of magnitude faster than the Apriority algorithm and also faster than some recently reported new frequent-pattern mining.
Voice Recognition Algorithms using Mel Frequency Cepstral Coefficient (MFCC) and Dynamic Time Warping (DTW) Techniques
Venue: arXiv cs.MM 2010
Year: 2010

Digital processing of speech signal and voice recognition algorithm is very important for fast and accurate automatic voice recognition technology. The voice is a signal of infinite information. A direct analysis and synthesizing the complex voice signal is due to too much information contained in the signal. Therefore the digital signal processes such as Feature Extraction and Feature Matching are introduced to represent the voice signal. Several methods such as Liner Predictive Predictive Coding (LPC), Hidden Markov Model (HMM), Artificial Neural Network (ANN) and etc are evaluated with a view to identify a straight forward and effective method for voice signal. The extraction and matching process is implemented right after the Pre Processing or filtering signal is performed. The non-parametric method for modelling the human auditory perception system, Mel Frequency Cepstral Coefficients (MFCCs) are utilize as extraction techniques. The non linear sequence alignment known as Dynamic Time Warping (DTW) introduced by Sakoe Chiba has been used as features matching techniques. Since it's obvious that the voice signal tends to have different temporal rate, the alignment is important to produce the better performance.This paper present the viability of MFCC to extract features and DTW to compare the test patterns.