OpenRaiser/Intern-Atlas huggingface dataset:
Exploiting Parallelism in Coalgebraic Logic Programming
Venue: arXiv cs.PL 2013
Year: 2013

We present a parallel implementation of Coalgebraic Logic Programming (CoALP) in the programming language Go. CoALP was initially introduced to reflect coalgebraic semantics of logic programming, with coalgebraic derivation algorithm featuring both corecursion and parallelism. Here, we discuss how the coalgebraic semantics influenced our parallel implementation of logic programming.
RDF Translator: A RESTful Multi-Format Data Converter for the Semantic Web
Venue: arXiv cs.DL 2013
Year: 2013

The interdisciplinary nature of the Semantic Web and the many projects put forward by the community led to a large number of widely accepted serialization formats for RDF. Most of these RDF syntaxes have been developed out of a necessity to serve specific purposes better than existing ones, e.g. RDFa was proposed as an extension to HTML for embedding non-intrusive RDF statements in human-readable documents. Nonetheless, the RDF serialization formats are generally transducible among themselves given that they are commonly based on the RDF model. In this paper, we present (1) a RESTful Web service based on the HTTP protocol that translates between different serializations. In addition to its core functionality, our proposed solution provides (2) features to accommodate frequent needs of Semantic Web developers, namely a straightforward user interface with copy-to-clipboard functionality, syntax highlighting, persistent URI links for easy sharing, cool URI patterns, and content negotiation using respective HTTP headers. We demonstrate the benefit of our converter by presenting two use cases.
Semantic Annotation: The Mainstay of Semantic Web
Venue: arXiv cs.DL 2013
Year: 2013

Given that semantic Web realization is based on the critical mass of metadata accessibility and the representation of data with formal knowledge, it needs to generate metadata that is specific, easy to understand and well-defined. However, semantic annotation of the web documents is the successful way to make the Semantic Web vision a reality. This paper introduces the Semantic Web and its vision (stack layers) with regard to some concept definitions that helps the understanding of semantic annotation. Additionally, this paper introduces the semantic annotation categories, tools, domains and models.
Geometric Methods for Invariant-Zero Cancellation in Linear Multivariable Systems: Illustrative Examples
Venue: arXiv cs.SY 2013
Year: 2013

This note presents some numerical examples worked out in order to show the reader how to implement, within a widely accessible computational setting, the methodology for achieving zero cancellation in linear multivariable systems discussed in [1]. The results are evaluated in the light of applicability and performance of different methods available in the literature.
Efficient Online Bootstrapping for Large Scale Learning
Venue: arXiv cs.LG 2013
Year: 2013

Bootstrapping is a useful technique for estimating the uncertainty of a predictor, for example, confidence intervals for prediction. It is typically used on small to moderate sized datasets, due to its high computation cost. This work describes a highly scalable online bootstrapping strategy, implemented inside Vowpal Wabbit, that is several times faster than traditional strategies. Our experiments indicate that, in addition to providing a black box-like method for estimating uncertainty, our implementation of online bootstrapping may also help to train models with better prediction performance due to model averaging.
Local correlation clustering
Venue: arXiv cs.DS 2013
Year: 2013

Correlation clustering is perhaps the most natural formulation of clustering. Given $n$ objects and a pairwise similarity measure, the goal is to cluster the objects so that, to the best possible extent, similar objects are put in the same cluster and dissimilar objects are put in different clusters. Despite its theoretical appeal, the practical relevance of correlation clustering still remains largely unexplored, mainly due to the fact that correlation clustering requires the $Θ(n^2)$ pairwise similarities as input. In this paper we initiate the investigation into \emph{local} algorithms for correlation clustering. In \emph{local correlation clustering} we are given the identifier of a single object and we want to return the cluster to which it belongs in some globally consistent near-optimal clustering, using a small number of similarity queries. Local algorithms for correlation clustering open the door to \emph{sublinear-time} algorithms, which are particularly useful when the similarity between items is costly to compute, as it is often the case in many practical application domains. They also imply $(i)$ distributed and streaming clustering algorithms, $(ii)$ constant-time estimators and testers for cluster edit distance, and $(iii)$ property-preserving parallel reconstruction algorithms for clusterability. Specifically, we devise a local clustering algorithm attaining a $(3, \varepsilon)$-approximation in time $O(1/\varepsilon^2)$ independently of the dataset size. An explicit approximate clustering for all objects can be produced in time $O(n/\varepsilon)$ (which is provably optimal). We also provide a fully additive $(1,\varepsilon)$-approximation with local query complexity $poly(1/\varepsilon)$ and time complexity $2^{poly(1/\varepsilon)}$. The latter yields the fastest polynomial-time approximation scheme for correlation clustering known to date.
Deep Learning Embeddings for Discontinuous Linguistic Units
Venue: arXiv cs.CL 2013
Year: 2013

Deep learning embeddings have been successfully used for many natural language processing problems. Embeddings are mostly computed for word forms although a number of recent papers have extended this to other linguistic units like morphemes and phrases. In this paper, we argue that learning embeddings for discontinuous linguistic units should also be considered. In an experimental evaluation on coreference resolution, we show that such embeddings perform better than word form embeddings.
On the Effectiveness of Polynomial Realization of Reed-Solomon Codes for Storage Systems
Venue: arXiv cs.IT 2013
Year: 2013

There are different ways to realize Reed Solomon (RS) codes. While in the storage community, using the generator matrices to implement RS codes is more popular, in the coding theory community the generator polynomials are typically used to realize RS codes. Prominent exceptions include HDFS-RAID, which uses generator polynomial based erasure codes, and extends the Apache Hadoop's file system. In this paper we evaluate the performance of an implementation of polynomial realization of Reed-Solomon codes, along with our optimized version of it, against that of a widely-used library (Jerasure) that implements the main matrix realization alternatives. Our experimental study shows that despite significant performance gains yielded by our optimizations, the polynomial implementations' performance is constantly inferior to those of matrix realization alternatives in general, and that of Cauchy bit matrices in particular.
Tweet, but Verify: Epistemic Study of Information Verification on Twitter
Venue: arXiv cs.SI 2013
Year: 2013

While Twitter provides an unprecedented opportunity to learn about breaking news and current events as they happen, it often produces skepticism among users as not all the information is accurate but also hoaxes are sometimes spread. While avoiding the diffusion of hoaxes is a major concern during fast-paced events such as natural disasters, the study of how users trust and verify information from tweets in these contexts has received little attention so far. We survey users on credibility perceptions regarding witness pictures posted on Twitter related to Hurricane Sandy. By examining credibility perceptions on features suggested for information verification in the field of Epistemology, we evaluate their accuracy in determining whether pictures were real or fake compared to professional evaluations performed by experts. Our study unveils insight about tweet presentation, as well as features that users should look at when assessing the veracity of tweets in the context of fast-paced events. Some of our main findings include that while author details not readily available on Twitter feeds should be emphasized in order to facilitate verification of tweets, showing multiple tweets corroborating a fact misleads users to trusting what actually is a hoax. We contrast some of the behavioral patterns found on tweets with literature in Psychology research.
Robust Steganography Using LSB-XOR and Image Sharing
Venue: arXiv cs.CR 2013
Year: 2013

Hiding and securing the secret digital information and data that are transmitted over the internet is of widespread and most challenging interest. This paper presents a new idea of robust steganography using bitwise-XOR operation between stego-key-image-pixel LSB (Least Significant Bit) value and secret message-character ASCII-binary value (or, secret image-pixel value). The stego-key-image is shared in dual-layer using odd-even position of each pixel to make the system robust. Due to image sharing, the detection can only be done with all the image shares.
Dial It In: Rotating RF Sensors to Enhance Radio Tomography
Venue: arXiv cs.NI 2013
Year: 2013

A radio tomographic imaging (RTI) system uses the received signal strength (RSS) measured by RF sensors in a static wireless network to localize people in the deployment area, without having them to carry or wear an electronic device. This paper addresses the fact that small-scale changes in the position and orientation of the antenna of each RF sensor can dramatically affect imaging and localization performance of an RTI system. However, the best placement for a sensor is unknown at the time of deployment. Improving performance in a deployed RTI system requires the deployer to iteratively "guess-and-retest", i.e., pick a sensor to move and then re-run a calibration experiment to determine if the localization performance had improved or degraded. We present an RTI system of servo-nodes, RF sensors equipped with servo motors which autonomously "dial it in", i.e., change position and orientation to optimize the RSS on links of the network. By doing so, the localization accuracy of the RTI system is quickly improved, without requiring any calibration experiment from the deployer. Experiments conducted in three indoor environments demonstrate that the servo-nodes system reduces localization error on average by 32% compared to a standard RTI system composed of static RF sensors.
My First Deep Learning System of 1991 + Deep Learning Timeline 1962-2013
Venue: arXiv cs.NE 2013
Year: 2013

Deep Learning has attracted significant attention in recent years. Here I present a brief overview of my first Deep Learner of 1991, and its historic context, with a timeline of Deep Learning highlights.
Detecting Intentional Packet Drops on the Internet via TCP/IP Side Channels: Extended Version
Venue: arXiv cs.NI 2013
Year: 2013

We describe a method for remotely detecting intentional packet drops on the Internet via side channel inferences. That is, given two arbitrary IP addresses on the Internet that meet some simple requirements, our proposed technique can discover packet drops (e.g., due to censorship) between the two remote machines, as well as infer in which direction the packet drops are occurring. The only major requirements for our approach are a client with a global IP Identifier (IPID) and a target server with an open port. We require no special access to the client or server. Our method is robust to noise because we apply intervention analysis based on an autoregressive-moving-average (ARMA) model. In a measurement study using our method featuring clients from multiple continents, we observed that, of all measured client connections to Tor directory servers that were censored, 98% of those were from China, and only 0.63% of measured client connections from China to Tor directory servers were not censored. This is congruent with current understandings about global Internet censorship, leading us to conclude that our method is effective.
Measuring voting power in convex policy spaces
Venue: arXiv cs.GT 2013
Year: 2013

Classical power index analysis considers the individual's ability to influence the aggregated group decision by changing its own vote, where all decisions and votes are assumed to be binary. In many practical applications we have more options than either "yes" or "no". Here we generalize three important power indices to continuous convex policy spaces. This allows the analysis of a collection of economic problems like e.g. tax rates or spending that otherwise would not be covered in binary models.
Extending Construction X for Quantum Error-Correcting Codes
Venue: arXiv cs.IT 2013
Year: 2013

In this paper we extend the work of Lisonek and Singh on construction X for quantum error-correcting codes to finite fields of order $p^2^ where p is prime. The results obtained are applied to the dual of Hermitian repeated root cyclic codes to generate new quantum error-correcting codes.
An Algebra of Causal Chains
Venue: arXiv cs.AI 2013
Year: 2013

In this work we propose a multi-valued extension of logic programs under the stable models semantics where each true atom in a model is associated with a set of justifications, in a similar spirit than a set of proof trees. The main contribution of this paper is that we capture justifications into an algebra of truth values with three internal operations: an addition '+' representing alternative justifications for a formula, a commutative product '*' representing joint interaction of causes and a non-commutative product '.' acting as a concatenation or proof constructor. Using this multi-valued semantics, we obtain a one-to-one correspondence between the syntactic proof tree of a standard (non-causal) logic program and the interpretation of each true atom in a model. Furthermore, thanks to this algebraic characterization we can detect semantic properties like redundancy and relevance of the obtained justifications. We also identify a lattice-based characterization of this algebra, defining a direct consequences operator, proving its continuity and that its least fix point can be computed after a finite number of iterations. Finally, we define the concept of causal stable model by introducing an analogous transformation to Gelfond and Lifschitz's program reduct.
A Review on Automated Brain Tumor Detection and Segmentation from MRI of Brain
Venue: arXiv cs.CV 2013
Year: 2013

Tumor segmentation from magnetic resonance imaging (MRI) data is an important but time consuming manual task performed by medical experts. Automating this process is a challenging task because of the high diversity in the appearance of tumor tissues among different patients and in many cases similarity with the normal tissues. MRI is an advanced medical imaging technique providing rich information about the human soft-tissue anatomy. There are different brain tumor detection and segmentation methods to detect and segment a brain tumor from MRI images. These detection and segmentation approaches are reviewed with an importance placed on enlightening the advantages and drawbacks of these methods for brain tumor detection and segmentation. The use of MRI image detection and segmentation in different procedures are also described. Here a brief review of different segmentation for detection of brain tumor from MRI of brain has been discussed.
An Overview of the Commercial Cloud Monitoring Tools: Research Dimensions, Design Issues, and State-of-the-Art
Venue: arXiv cs.DC 2013
Year: 2013

Cloud monitoring activity involves dynamically tracking the Quality of Service (QoS) parameters related to virtualized resources (e.g., VM, storage, network, appliances, etc.), the physical resources they share, the applications running on them and data hosted on them. Applications and resources configuration in cloud computing environment is quite challenging considering a large number of heterogeneous cloud resources. Further, considering the fact that at each point of time, there will be a different and specific cloud service which may be massively required. Hence, cloud monitoring tools can assist a cloud providers or application developers in: (i) keeping their resources and applications operating at peak efficiency; (ii) detecting variations in resource and application performance; (iii) accounting the Service Level Agreement (SLA) violations of certain QoS parameters; and (iv) tracking the leave and join operations of cloud resources due to failures and other dynamic configuration changes. In this paper, we identify and discuss the major research dimensions and design issues related to engineering cloud monitoring tools. We further discuss how aforementioned research dimensions and design issues are handled by current academic research as well as by commercial monitoring tools.
Extracting Region of Interest for Palm Print Authentication
Venue: arXiv cs.CV 2013
Year: 2013

Biometrics authentication is an effective method for automatically recognizing individuals. The authentication consists of an enrollment phase and an identification or verification phase. In the stages of enrollment known (training) samples after the pre-processing stage are used for suitable feature extraction to generate the template database. In the verification stage, the test sample is similarly pre processed and subjected to feature extraction modules, and then it is matched with the training feature templates to decide whether it is a genuine or not. This paper presents use of a region of interest (ROI) for palm print technology. First some of the existing methods for palm print identification have been introduced. Then focus has been given on extraction of a suitable smaller region from the acquired palm print to improve the identification method accuracy. Several existing work in the topic of region extraction have been examined. Subsequently, a simple and original method has then proposed for locating the ROI that can be effectively used for palm print analysis. The ROI extracted using this new technique is suitable for different types of processing as it creates a rectangular or square area around the center of activity represented by the lines, wrinkles and ridges of the palm print. The effectiveness of the ROI approach has been tested by integrating it with a texture based identification / authentication system proposed earlier. The improvement has been shown by comparing the identification accuracy rate before and after the ROI pre-processing.
New Results for the Heterogeneous Multi-Processor Scheduling Problem using a Fast, Effective Local Search and Random Disruption
Venue: arXiv cs.DC 2013
Year: 2013

The efficient scheduling of independent computational tasks in a heterogeneous computing environment is an important problem that occurs in domains such as Grid and Cloud computing. Finding optimal schedules is an NP-hard problem in general, so we have to rely on approximate algorithms to come up schedules that are as near to optimal as possible. In our previous work on this problem, we applied a fast, effective local search to generate reasonably good schedules in a short amount of time and used ant colony optimisation (ACO) to incrementally improve those schedules over a longer time period. In this work, we replace the ACO component with a random disruption algorithm and find that this produces results which are competitive with the current state of the art over a 90 second execution time. We also ran our algorithm for a longer time period on 12 well-known benchmark instances and as a result provide new upper bounds for these instances.
Dimension-free Concentration Bounds on Hankel Matrices for Spectral Learning
Venue: arXiv cs.LG 2013
Year: 2013

Learning probabilistic models over strings is an important issue for many applications. Spectral methods propose elegant solutions to the problem of inferring weighted automata from finite samples of variable-length strings drawn from an unknown target distribution. These methods rely on a singular value decomposition of a matrix $H_S$, called the Hankel matrix, that records the frequencies of (some of) the observed strings. The accuracy of the learned distribution depends both on the quantity of information embedded in $H_S$ and on the distance between $H_S$ and its mean $H_r$. Existing concentration bounds seem to indicate that the concentration over $H_r$ gets looser with the size of $H_r$, suggesting to make a trade-off between the quantity of used information and the size of $H_r$. We propose new dimension-free concentration bounds for several variants of Hankel matrices. Experiments demonstrate that these bounds are tight and that they significantly improve existing bounds. These results suggest that the concentration rate of the Hankel matrix around its mean does not constitute an argument for limiting its size.
Output-Sensitive Tools for Range Searching in Higher Dimensions
Venue: arXiv cs.CG 2013
Year: 2013

Let $P$ be a set of $n$ points in ${\mathbb R}^{d}$. A point $p \in P$ is $k$\emph{-shallow} if it lies in a halfspace which contains at most $k$ points of $P$ (including $p$). We show that if all points of $P$ are $k$-shallow, then $P$ can be partitioned into $Θ(n/k)$ subsets, so that any hyperplane crosses at most $O((n/k)^{1-1/(d-1)} \log^{2/(d-1)}(n/k))$ subsets. Given such a partition, we can apply the standard construction of a spanning tree with small crossing number within each subset, to obtain a spanning tree for the point set $P$, with crossing number $O(n^{1-1/(d-1)}k^{1/d(d-1)} \log^{2/(d-1)}(n/k))$. This allows us to extend the construction of Har-Peled and Sharir \cite{hs11} to three and higher dimensions, to obtain, for any set of $n$ points in ${\mathbb R}^{d}$ (without the shallowness assumption), a spanning tree $T$ with {\em small relative crossing number}. That is, any hyperplane which contains $w \leq n/2$ points of $P$ on one side, crosses $O(n^{1-1/(d-1)}w^{1/d(d-1)} \log^{2/(d-1)}(n/w))$ edges of $T$. Using a similar mechanism, we also obtain a data structure for halfspace range counting, which uses $O(n \log \log n)$ space (and somewhat higher preprocessing cost), and answers a query in time $O(n^{1-1/(d-1)}k^{1/d(d-1)} (\log (n/k))^{O(1)})$, where $k$ is the output size.
The Sybil Attacks and Defenses: A Survey
Venue: arXiv cs.CR 2013
Year: 2013

In this paper we have a close look at the Sybil attack and advances in defending against it, with particular emphasis on the recent work. We identify three major veins of literature work to defend against the attack: using trusted certification, using resources testing, and using social networks. The first vein of literature considers defending against the attack using trusted certification, which is done by either centralized certification or distributed certification using cryptographic primitives that can replace the centralized certification entity. The second vein of literature considers defending against the attack by resources testing, which can by in the form of IP testing, network coordinates, recurring cost as by requiring clients to solve puzzles. The third and last vein of literature is by mitigating the attack combining social networks used as bootstrapping security and tools from random walk theory that have shown to be effective in defending against the attack under certain assumptions. Our survey and analyses of the different schemes in the three veins of literature show several shortcomings which form several interesting directions and research questions worthy of investigation.