OpenRaiser/Intern-Atlas huggingface dataset:
Introduction to the Bag of Features Paradigm for Image Classification and Retrieval
Venue: arXiv cs.CV 2011
Year: 2011

The past decade has seen the growing popularity of Bag of Features (BoF) approaches to many computer vision tasks, including image classification, video search, robot localization, and texture recognition. Part of the appeal is simplicity. BoF methods are based on orderless collections of quantized local image descriptors; they discard spatial information and are therefore conceptually and computationally simpler than many alternative methods. Despite this, or perhaps because of this, BoF-based systems have set new performance standards on popular image classification benchmarks and have achieved scalability breakthroughs in image retrieval. This paper presents an introduction to BoF image representations, describes critical design choices, and surveys the BoF literature. Emphasis is placed on recent techniques that mitigate quantization errors, improve feature detection, and speed up image retrieval. At the same time, unresolved issues and fundamental challenges are raised. Among the unresolved issues are determining the best techniques for sampling images, describing local image features, and evaluating system performance. Among the more fundamental challenges are how and whether BoF methods can contribute to localizing objects in complex images, or to associating high-level semantics with natural images. This survey should be useful both for introducing new investigators to the field and for providing existing researchers with a consolidated reference to related work.
Inducing the LCP-Array
Venue: arXiv cs.DS 2011
Year: 2011

We show how to modify the linear-time construction algorithm for suffix arrays based on induced sorting (Nong et al., DCC'09) such that it computes the array of longest common prefixes (LCP-array) as well. Practical tests show that this outperforms recent LCP-array construction algorithms (Gog and Ohlebusch, ALENEX'11).
Capacity of DNA Data Embedding Under Substitution Mutations
Venue: arXiv cs.IT 2011
Year: 2011

A number of methods have been proposed over the last decade for encoding information using deoxyribonucleic acid (DNA), giving rise to the emerging area of DNA data embedding. Since a DNA sequence is conceptually equivalent to a sequence of quaternary symbols (bases), DNA data embedding (diversely called DNA watermarking or DNA steganography) can be seen as a digital communications problem where channel errors are tantamount to mutations of DNA bases. Depending on the use of coding or noncoding DNA hosts, which, respectively, denote DNA segments that can or cannot be translated into proteins, DNA data embedding is essentially a problem of communications with or without side information at the encoder. In this paper the Shannon capacity of DNA data embedding is obtained for the case in which DNA sequences are subject to substitution mutations modelled using the Kimura model from molecular evolution studies. Inferences are also drawn with respect to the biological implications of some of the results presented.
Tagging with DHARMA, a DHT-based Approach for Resource Mapping through Approximation
Venue: arXiv cs.DC 2011
Year: 2011

We introduce collaborative tagging and faceted search on structured P2P systems. Since a trivial and brute force mapping of an entire folksonomy over a DHT-based system may reduce scalability, we propose an approximated graph maintenance approach. Evaluations on real data coming from Last.fm prove that such strategies reduce vocabulary noise (i.e., representation's overfitting phenomena) and hotspots issues.
Secret Key Agreement Over Multipath Channels Exploiting a Variable-Directional Antenna
Venue: arXiv cs.IT 2011
Year: 2011

We develop an approach of key distribution protocol (KDP) proposed recently by T. Aono et al. A more general mathematical model based on the use of Variable-Directional Antenna (VDA) under the condition of multipath wave propagation is proposed. Statistical characteristics of VDA were investigated by simulation, that allows us to specify model parameters. The security of the considered KDP is estimated in terms of Shannon's information leaking to an eavesdropper depending on the mutual locations of the legal users and the eavesdropper. Antenna diversity is proposed as a mean to enhance the KDP security. In order to provide a better agreement of the shared keys it is investigated the use of error-correcting codes.
Superiority of exact quantum automata for promise problems
Venue: arXiv cs.CC 2011
Year: 2011

In this note, we present an infinite family of promise problems which can be solved exactly by just tuning transition amplitudes of a two-state quantum finite automata operating in realtime mode, whereas the size of the corresponding classical automata grow without bound.
Characteristic Generators and Dualization for Tail-Biting Trellises
Venue: arXiv cs.IT 2011
Year: 2011

This paper focuses on dualizing tail-biting trellises, particularly KV-trellises. These trellises are based on characteristic generators, as introduced by Koetter/Vardy (2003), and may be regarded as a natural generalization of minimal conventional trellises, even though they are not necessarily minimal. Two dualization techniques will be investigated: the local dualization, introduced by Forney (2001) for general normal graphs, and a linear algebra based dualization tailored to the specific class of tail-biting BCJR-trellises, introduced by Nori/Shankar (2006). It turns out that, in general, the BCJR-dual is a subtrellis of the local dual, while for KV-trellises these two coincide. Furthermore, making use of both the BCJR-construction and the local dualization, it will be shown that for each complete set of characteristic generators of a code there exists a complete set of characteristic generators of the dual code such that their resulting KV-trellises are dual to each other if paired suitably. This proves a stronger version of a conjecture formulated by Koetter/Vardy.
Short Propositional Refutations for Dense Random 3CNF Formulas
Venue: arXiv cs.CC 2011
Year: 2011

Random 3CNF formulas constitute an important distribution for measuring the average-case behavior of propositional proof systems. Lower bounds for random 3CNF refutations in many propositional proof systems are known. Most notably are the exponential-size resolution refutation lower bounds for random 3CNF formulas with $Ω(n^{1.5-ε}) $ clauses [Chvatal and Szemeredi (1988), Ben-Sasson and Wigderson (2001)]. On the other hand, the only known non-trivial upper bound on the size of random 3CNF refutations in a non-abstract propositional proof system is for resolution with $Ω(n^{2}/\log n) $ clauses, shown by Beame et al. (2002). In this paper we show that already standard propositional proof systems, within the hierarchy of Frege proofs, admit short refutations for random 3CNF formulas, for sufficiently large clause-to-variable ratio. Specifically, we demonstrate polynomial-size propositional refutations whose lines are $TC^0$ formulas (i.e., $TC^0$-Frege proofs) for random 3CNF formulas with $ n $ variables and $ Ω(n^{1.4}) $ clauses. The idea is based on demonstrating efficient propositional correctness proofs of the random 3CNF unsatisfiability witnesses given by Feige, Kim and Ofek (2006). Since the soundness of these witnesses is verified using spectral techniques, we develop an appropriate way to reason about eigenvectors in propositional systems. To carry out the full argument we work inside weak formal systems of arithmetic and use a general translation scheme to propositional proofs.
A QoS Routing Protocol based on Available Bandwidth Estimation for Wireless Ad Hoc Networks
Venue: arXiv cs.NI 2011
Year: 2011

At the same time as the emergence of multimedia in mobile Ad hoc networks, research for the introduction of the quality of service (QoS) has received much attention. However, when designing a QoS solution, the estimation of the available resources still represents one of the main issues. This paper suggests an approach to estimate available resources on a node. This approach is based on the estimation of the busy ratio of the shared canal. We consider in our estimation the several constraints related to the Ad hoc transmission mode such as Interference phenomena. This approach is implemented on the AODV routing protocol. We call AODVwithQOS our new routing protocol. We also performed a performance evaluation by simulations using NS2 simulator. The results confirm that AODVwithQoS provides QoS support in ad hoc wireless networks with good performance and low overhead.
GridCertLib: a Single Sign-on Solution for Grid Web Applications and Portals
Venue: arXiv cs.DC 2011
Year: 2011

This paper describes the design and implementation of GridCertLib, a Java library leveraging a Shibboleth-based authentication infrastructure and the SLCS online certificate signing service, to provide short-lived X.509 certificates and Grid proxies. The main use case envisioned for GridCertLib, is to provide seamless and secure access to Grid/X.509 certificates and proxies in web applications and portals: when a user logs in to the portal using Shibboleth authentication, GridCertLib can automatically obtain a Grid/X.509 certificate from the SLCS service and generate a VOMS proxy from it. We give an overview of the architecture of GridCertLib and briefly describe its programming model. Its application to some deployment scenarios is outlined, as well as a report on practical experience integrating GridCertLib into portals for Bioinformatics and Computational Chemistry applications, based on the popular P-GRADE and Django softwares.
Indexing Properties of Primitive Pythagorean Triples for Cryptography Applications
Venue: arXiv cs.CR 2011
Year: 2011

This paper presents new properties of Primitive Pythagorean Triples (PPT) that have relevance in applications where events of different probability need to be generated and in cryptography.
A Comparative Agglomerative Hierarchical Clustering Method to Cluster Implemented Course
Venue: arXiv cs.DB 2011
Year: 2011

There are many clustering methods, such as hierarchical clustering method. Most of the approaches to the clustering of variables encountered in the literature are of hierarchical type. The great majority of hierarchical approaches to the clustering of variables are of agglomerative nature. The agglomerative hierarchical approach to clustering starts with each observation as its own cluster and then continually groups the observations into increasingly larger groups. Higher Learning Institution (HLI) provides training to introduce final-year students to the real working environment. In this research will use Euclidean single linkage and complete linkage. MATLAB and HCE 3.5 software will used to train data and cluster course implemented during industrial training. This study indicates that different method will create a different number of clusters.
Discrete Time Elastic Vector Spaces
Venue: arXiv cs.DM 2011
Year: 2011

We propose in this paper a framework dedicated to the construction of what we call time elastic inner products that allows embedding sets of non-uniformly sampled multivariate time series of varying lengths into vector space structures. This framework is based on a recursive definition that covers the case of multiple embedded time elastic dimensions. We prove that such inner products exist in our framework and show how a simple instance of this inner product class operates on some toy applications, while generalizing the Euclidean inner product.
Session Types = Intersection Types + Union Types
Venue: arXiv cs.PL 2011
Year: 2011

We propose a semantically grounded theory of session types which relies on intersection and union types. We argue that intersection and union types are natural candidates for modeling branching points in session types and we show that the resulting theory overcomes some important defects of related behavioral theories. In particular, intersections and unions provide a native solution to the problem of computing joins and meets of session types. Also, the subtyping relation turns out to be a pre-congruence, while this is not always the case in related behavioral theories.
Adaptive Submodular Optimization under Matroid Constraints
Venue: arXiv cs.DS 2011
Year: 2011

Many important problems in discrete optimization require maximization of a monotonic submodular function subject to matroid constraints. For these problems, a simple greedy algorithm is guaranteed to obtain near-optimal solutions. In this article, we extend this classic result to a general class of adaptive optimization problems under partial observability, where each choice can depend on observations resulting from past choices. Specifically, we prove that a natural adaptive greedy algorithm provides a $1/(p+1)$ approximation for the problem of maximizing an adaptive monotone submodular function subject to $p$ matroid constraints, and more generally over arbitrary $p$-independence systems. We illustrate the usefulness of our result on a complex adaptive match-making application.
Tight Bounds on Information Dissemination in Sparse Mobile Networks
Venue: arXiv cs.DM 2011
Year: 2011

Motivated by the growing interest in mobile systems, we study the dynamics of information dissemination between agents moving independently on a plane. Formally, we consider $k$ mobile agents performing independent random walks on an $n$-node grid. At time $0$, each agent is located at a random node of the grid and one agent has a rumor. The spread of the rumor is governed by a dynamic communication graph process ${G_t(r) | t \geq 0}$, where two agents are connected by an edge in $G_t(r)$ iff their distance at time $t$ is within their transmission radius $r$. Modeling the physical reality that the speed of radio transmission is much faster than the motion of the agents, we assume that the rumor can travel throughout a connected component of $G_t$ before the graph is altered by the motion. We study the broadcast time $T_B$ of the system, which is the time it takes for all agents to know the rumor. We focus on the sparse case (below the percolation point $r_c \approx \sqrt{n/k}$) where, with high probability, no connected component in $G_t$ has more than a logarithmic number of agents and the broadcast time is dominated by the time it takes for many independent random walks to meet each other. Quite surprisingly, we show that for a system below the percolation point the broadcast time does not depend on the relation between the mobility speed and the transmission radius. In fact, we prove that $T_B = \tilde{O}(n / \sqrt{k})$ for any $0 \leq r < r_c$, even when the transmission range is significantly larger than the mobility range in one step, giving a tight characterization up to logarithmic factors. Our result complements a recent result of Peres et al. (SODA 2011) who showed that above the percolation point the broadcast time is polylogarithmic in $k$.
Online Adaptive Decision Fusion Framework Based on Entropic Projections onto Convex Sets with Application to Wildfire Detection in Video
Venue: arXiv cs.CV 2011
Year: 2011

In this paper, an Entropy functional based online Adaptive Decision Fusion (EADF) framework is developed for image analysis and computer vision applications. In this framework, it is assumed that the compound algorithm consists of several sub-algorithms each of which yielding its own decision as a real number centered around zero, representing the confidence level of that particular sub-algorithm. Decision values are linearly combined with weights which are updated online according to an active fusion method based on performing entropic projections onto convex sets describing sub-algorithms. It is assumed that there is an oracle, who is usually a human operator, providing feedback to the decision fusion method. A video based wildfire detection system is developed to evaluate the performance of the algorithm in handling the problems where data arrives sequentially. In this case, the oracle is the security guard of the forest lookout tower verifying the decision of the combined algorithm. Simulation results are presented. The EADF framework is also tested with a standard dataset.
Using Feature Weights to Improve Performance of Neural Networks
Venue: arXiv cs.LG 2011
Year: 2011

Different features have different relevance to a particular learning problem. Some features are less relevant; while some very important. Instead of selecting the most relevant features using feature selection, an algorithm can be given this knowledge of feature importance based on expert opinion or prior learning. Learning can be faster and more accurate if learners take feature importance into account. Correlation aided Neural Networks (CANN) is presented which is such an algorithm. CANN treats feature importance as the correlation coefficient between the target attribute and the features. CANN modifies normal feed-forward Neural Network to fit both correlation values and training data. Empirical evaluation shows that CANN is faster and more accurate than applying the two step approach of feature selection and then using normal learning algorithms.
Hybrid Digital-Analog Codes for Source-Channel Broadcast of Gaussian Sources over Gaussian Channels
Venue: arXiv cs.IT 2011
Year: 2011

The problem of broadcasting a parallel Gaussian source over an additive white Gaussian noise broadcast channel under the mean-squared error distortion criterion is studied. A hybrid digital-analog coding strategy which combines source coding with side information, channel coding with side information, layered source coding, and superposition broadcast channel coding is presented. When specialized to the open problem of broadcasting a white Gaussian source over an additive white Gaussian noise broadcast channel with bandwidth mismatch which has been the subject of several previous investigations, this coding scheme strictly improves on the state-of-the-art.
A Chronology of Torah Cryptography
Venue: arXiv cs.OH 2011
Year: 2011

Regarding some papers and notes submitted to, or presented at, the second congress of the International Torah Codes Society in Jerusalem, Israel, June 2000.
SmartInt: Using Mined Attribute Dependencies to Integrate Fragmented Web Databases
Venue: arXiv cs.DB 2011
Year: 2011

Many web databases can be seen as providing partial and overlapping information about entities in the world. To answer queries effectively, we need to integrate the information about the individual entities that are fragmented over multiple sources. At first blush this is just the inverse of traditional database normalization problem - rather than go from a universal relation to normalized tables, we want to reconstruct the universal relation given the tables (sources). The standard way of reconstructing the entities will involve joining the tables. Unfortunately, because of the autonomous and decentralized way in which the sources are populated, they often do not have Primary Key - Foreign Key relations. While tables may share attributes, naive joins over these shared attributes can result in reconstruction of many spurious entities thus seriously compromising precision. Our system, \smartint\ is aimed at addressing the problem of data integration in such scenarios. Given a query, our system uses the Approximate Functional Dependencies (AFDs) to piece together a tree of relevant tables to answer it. The result tuples produced by our system are able to strike a favorable balance between precision and recall.
Approximating the Influence of a monotone Boolean function in O(\sqrt{n}) query complexity
Venue: arXiv cs.DS 2011
Year: 2011

The {\em Total Influence} ({\em Average Sensitivity) of a discrete function is one of its fundamental measures. We study the problem of approximating the total influence of a monotone Boolean function \ifnum\plusminus=1 $f: \{\pm1\}^n \longrightarrow \{\pm1\}$, \else $f: \bitset^n \to \bitset$, \fi which we denote by $I[f]$. We present a randomized algorithm that approximates the influence of such functions to within a multiplicative factor of $(1\pm \eps)$ by performing $O(\frac{\sqrt{n}\log n}{I[f]} \poly(1/\eps)) $ queries. % \mnote{D: say something about technique?} We also prove a lower bound of % $Ω(\frac{\sqrt{n/\log n}}{I[f]})$ $Ω(\frac{\sqrt{n}}{\log n \cdot I[f]})$ on the query complexity of any constant-factor approximation algorithm for this problem (which holds for $I[f] = Ω(1)$), % and $I[f] = O(\sqrt{n}/\log n)$), hence showing that our algorithm is almost optimal in terms of its dependence on $n$. For general functions we give a lower bound of $Ω(\frac{n}{I[f]})$, which matches the complexity of a simple sampling algorithm.
The Computing of Digital Ecosystems
Venue: arXiv cs.DC 2011
Year: 2011

A primary motivation for our research in digital ecosystems is the desire to exploit the self-organising properties of biological ecosystems. Ecosystems are thought to be robust, scalable architectures that can automatically solve complex, dynamic problems. However, the computing technologies that contribute to these properties have not been made explicit in digital ecosystems research. Here, we discuss how different computing technologies can contribute to providing the necessary self-organising features, including Multi-Agent Systems (MASs), Service-Oriented Architectures (SOAs), and distributed evolutionary computing (DEC). The potential for exploiting these properties in digital ecosystems is considered, suggesting how several key features of biological ecosystems can be exploited in Digital Ecosystems, and discussing how mimicking these features may assist in developing robust, scalable self-organising architectures. An example architecture, the Digital Ecosystem, is considered in detail. The Digital Ecosystem is then measured experimentally through simulations, considering the self-organised diversity of its evolving agent populations relative to the user request behaviour.
Walking on a Graph with a Magnifying Glass: Stratified Sampling via Weighted Random Walks
Venue: arXiv cs.SI 2011
Year: 2011

Our objective is to sample the node set of a large unknown graph via crawling, to accurately estimate a given metric of interest. We design a random walk on an appropriately defined weighted graph that achieves high efficiency by preferentially crawling those nodes and edges that convey greater information regarding the target metric. Our approach begins by employing the theory of stratification to find optimal node weights, for a given estimation problem, under an independence sampler. While optimal under independence sampling, these weights may be impractical under graph crawling due to constraints arising from the structure of the graph. Therefore, the edge weights for our random walk should be chosen so as to lead to an equilibrium distribution that strikes a balance between approximating the optimal weights under an independence sampler and achieving fast convergence. We propose a heuristic approach (stratified weighted random walk, or S-WRW) that achieves this goal, while using only limited information about the graph structure and the node properties. We evaluate our technique in simulation, and experimentally, by collecting a sample of Facebook college users. We show that S-WRW requires 13-15 times fewer samples than the simple re-weighted random walk (RW) to achieve the same estimation accuracy for a range of metrics.