OpenRaiser/Intern-Atlas huggingface dataset:
Survey of Nearest Neighbor Techniques
Venue: arXiv cs.CV 2010
Year: 2010

The nearest neighbor (NN) technique is very simple, highly efficient and effective in the field of pattern recognition, text categorization, object recognition etc. Its simplicity is its main advantage, but the disadvantages can't be ignored even. The memory requirement and computation complexity also matter. Many techniques are developed to overcome these limitations. NN techniques are broadly classified into structure less and structure based techniques. In this paper, we present the survey of such techniques. Weighted kNN, Model based kNN, Condensed NN, Reduced NN, Generalized NN are structure less techniques whereas k-d tree, ball tree, Principal Axis Tree, Nearest Feature Line, Tunable NN, Orthogonal Search Tree are structure based algorithms developed on the basis of kNN. The structure less method overcome memory limitation and structure based techniques reduce the computational complexity.
First Smart Spaces
Venue: arXiv cs.DC 2010
Year: 2010

This document describes the Gloss software currently implemented. The description of the Gloss demonstrator for multi-surface interaction can be found in D17. The ongoing integration activity for the work described in D17 and D8 constitutes our development of infrastructure for a first smart space. In this report, the focus is on infrastructure to support the implementation of location aware services. A local architecture provides a framework for constructing Gloss applications, termed assemblies, that run on individual physical nodes. A global architecture defines an overlay network for linking individual assemblies. Both local and global architectures are under active development.
Channel Assortment Strategy for Reliable Communication in Multi-Hop Cognitive Radio Networks
Venue: arXiv cs.NI 2010
Year: 2010

In this paper, we propose a channel assortment strategy for Reliable Communication in Multi-Hop Cognitive Radio Networks.
From matrix interpretations over the rationals to matrix interpretations over the naturals
Venue: arXiv cs.SC 2010
Year: 2010

Matrix interpretations generalize linear polynomial interpretations and have been proved useful in the implementation of tools for automatically proving termination of Term Rewriting Systems. In view of the successful use of rational coefficients in polynomial interpretations, we have recently generalized traditional matrix interpretations (using natural numbers in the matrix entries) to incorporate real numbers. However, existing results which formally prove that polynomials over the reals are more powerful than polynomials over the naturals for proving termination of rewrite systems failed to be extended to matrix interpretations. In this paper we get deeper into this problem. We show that, under some conditions, it is possible to transform a matrix interpretation over the rationals satisfying a set of symbolic constraints into a matrix interpretation over the naturals (using bigger matrices) which still satisfies the constraints.
An Optimization and Control Theoretic Approach to Noncooperative Game Design
Venue: arXiv cs.GT 2010
Year: 2010

This paper investigates design of noncooperative games from an optimization and control theoretic perspective. Pricing mechanisms are used as a design tool to ensure that the Nash equilibrium of a fairly general class of noncooperative games satisfies certain global objectives such as welfare maximization or achieving a certain level of quality-of-service (QoS). The class of games considered provide a theoretical basis for decentralized resource allocation and control problems including network congestion control, wireless uplink power control, and optical power control. The game design problem is analyzed under different knowledge assumptions (full versus limited information) and design objectives (QoS versus utility maximization) for separable and non-separable utility functions. The ``price of anarchy'' is shown not to be an inherent feature of full-information games that incorporate pricing mechanisms. Moreover, a simple linear pricing is shown to be sufficient for design of Nash equilibrium according to a chosen global objective for a fairly general class of games. Stability properties of the game and pricing dynamics are studied under the assumption of time-scale separation and in two separate time-scales. Thus, sufficient conditions are derived, which allow the designer to place the Nash equilibrium solution or to guide the system trajectory to a desired region or point. The obtained results are illustrated with a number of examples.
Repairing People Trajectories Based on Point Clustering
Venue: arXiv cs.CV 2010
Year: 2010

This paper presents a method for improving any object tracking algorithm based on machine learning. During the training phase, important trajectory features are extracted which are then used to calculate a confidence value of trajectory. The positions at which objects are usually lost and found are clustered in order to construct the set of 'lost zones' and 'found zones' in the scene. Using these zones, we construct a triplet set of zones i.e. three zones: In/Out zone (zone where an object can enter or exit the scene), 'lost zone' and 'found zone'. Thanks to these triplets, during the testing phase, we can repair the erroneous trajectories according to which triplet they are most likely to belong to. The advantage of our approach over the existing state of the art approaches is that (i) this method does not depend on a predefined contextual scene, (ii) we exploit the semantic of the scene and (iii) we have proposed a method to filter out noisy trajectories based on their confidence value.
The Transfer of Evolved Artificial Immune System Behaviours between Small and Large Scale Robotic Platforms
Venue: arXiv cs.NE 2010
Year: 2010

This paper demonstrates that a set of behaviours evolved in simulation on a miniature robot (epuck) can be transferred to a much larger scale platform (a virtual Pioneer P3-DX) that also differs in shape, sensor type, sensor configuration and programming interface. The chosen architecture uses a reinforcement learning-assisted genetic algorithm to evolve the epuck behaviours, which are encoded as a genetic sequence. This sequence is then used by the Pioneers as part of an adaptive, idiotypic artificial immune system (AIS) control architecture. Testing in three different simulated worlds shows that the Pioneer can use these behaviours to navigate and solve object-tracking tasks successfully, as long as its adaptive AIS mechanism is in place.
Femto-Macro Cellular Interference Control with Subband Scheduling and Interference Cancelation
Venue: arXiv cs.NI 2010
Year: 2010

A significant technical challenge in deploying femtocells is controlling the interference from the underlay of femtos onto the overlay of macros. This paper presents a novel interference control method where the macrocell bandwidth is partitioned into subbands, and the short-range femtocell links adaptively allocate their power across the subbands based on a load-spillage power control method. The scheme can improve rate distribution in the macro network while also providing opportunities for short-range communication as well. Moreover, the proposed scheme requires minimal interference coordination communication between the femtos and macros, which is one of the main challenges in femtocell systems. Also, simulations show certain advantages over simpler orthogonalization schemes or power control schemes without subband partitioning. Further modest gains may also be possible with interference cancelation.
Limits of responsiveness concerning human-readable knowledge bases: an operational analysis
Venue: arXiv cs.DL 2010
Year: 2010

Introduction. The purpose of this work is the evaluation of responsiveness when remote users communicate with a human-readable knowledge base (KB). Responsiveness [R(s)] is considered here as a measure of service quality. Method. The preferred method is operational analysis, a variation of classical stochastic theory, which allows for the study of user-system interaction with minimal computational effort. Analysis. The analysis is based on well-known performance metrics, such as service ability, elapsed time, and throughput: from these metrics estimates of R(s) are derived analytically. Results. Critical points indicating congestion are obtained: these are limits on the number of admissible requests and the number of connected users. Also obtained is a sufficient condition for achieving flow balance between the KB host and the request-relaying servers. Conclusions. When R(s) is within normal limits, users should appreciate the benefits from using the services offered by their KB host. When bottlenecks are formed, R(s) declines, and the whole communication system heads for saturation. Flow balancing procedures are necessary for the elimination of bottlenecks, which leads to a better resource management.
Online Cake Cutting
Venue: arXiv cs.AI 2010
Year: 2010

We propose an online form of the cake cutting problem. This models situations where players arrive and depart during the process of dividing a resource. We show that well known fair division procedures like cut-and-choose and the Dubins-Spanier moving knife procedure can be adapted to apply to such online problems. We propose some desirable properties that online cake cutting procedures might possess like online forms of proportionality and envy-freeness, and identify which properties are in fact possessed by the different online cake procedures.
Fusion of Wavelet Coefficients from Visual and Thermal Face Images for Human Face Recognition - A Comparative Study
Venue: arXiv cs.CV 2010
Year: 2010

In this paper we present a comparative study on fusion of visual and thermal images using different wavelet transformations. Here, coefficients of discrete wavelet transforms from both visual and thermal images are computed separately and combined. Next, inverse discrete wavelet transformation is taken in order to obtain fused face image. Both Haar and Daubechies (db2) wavelet transforms have been used to compare recognition results. For experiments IRIS Thermal/Visual Face Database was used. Experimental results using Haar and Daubechies wavelets show that the performance of the approach presented here achieves maximum success rate of 100% in many cases.
Retransmission Steganography Applied
Venue: arXiv cs.CR 2010
Year: 2010

This paper presents experimental results of the implementation of network steganography method called RSTEG (Retransmission Steganography). The main idea of RSTEG is to not acknowledge a successfully received packet to intentionally invoke retransmission. The retransmitted packet carries a steganogram instead of user data in the payload field. RSTEG can be applied to many network protocols that utilize retransmissions. We present experimental results for RSTEG applied to TCP (Transmission Control Protocol) as TCP is the most popular network protocol which ensures reliable data transfer. The main aim of the performed experiments was to estimate RSTEG steganographic bandwidth and detectability by observing its influence on the network retransmission level.
On the independence polynomial of an antiregular graph
Venue: arXiv cs.DM 2010
Year: 2010

A graph with at most two vertices of the same degree is called antiregular (Merris 2003), maximally nonregular (Zykov 1990) or quasiperfect (Behzad, Chartrand 1967). If s_{k} is the number of independent sets of cardinality k in a graph G, then I(G;x) = s_{0} + s_{1}x + ... + s_{alpha}x^{alpha} is the independence polynomial of G (Gutman, Harary 1983), where alpha = alpha(G) is the size of a maximum independent set. In this paper we derive closed formulae for the independence polynomials of antiregular graphs. In particular, we deduce that every antiregular graph A is uniquely defined by its independence polynomial I(A;x), within the family of threshold graphs. Moreover, I(A;x) is logconcave with at most two real roots, and I(A;-1) belongs to {-1,0}.
An axiomatic formalization of bounded rationality based on a utility-information equivalence
Venue: arXiv cs.AI 2010
Year: 2010

Classic decision-theory is based on the maximum expected utility (MEU) principle, but crucially ignores the resource costs incurred when determining optimal decisions. Here we propose an axiomatic framework for bounded decision-making that considers resource costs. Agents are formalized as probability measures over input-output streams. We postulate that any such probability measure can be assigned a corresponding conjugate utility function based on three axioms: utilities should be real-valued, additive and monotonic mappings of probabilities. We show that these axioms enforce a unique conversion law between utility and probability (and thereby, information). Moreover, we show that this relation can be characterized as a variational principle: given a utility function, its conjugate probability measure maximizes a free utility functional. Transformations of probability measures can then be formalized as a change in free utility due to the addition of new constraints expressed by a target utility function. Accordingly, one obtains a criterion to choose a probability measure that trades off the maximization of a target utility function and the cost of the deviation from a reference distribution. We show that optimal control, adaptive estimation and adaptive control problems can be solved this way in a resource-efficient way. When resource costs are ignored, the MEU principle is recovered. Our formalization might thus provide a principled approach to bounded rationality that establishes a close link to information theory.
A Theory of Network Equivalence, Parts I and II
Venue: arXiv cs.IT 2010
Year: 2010

A family of equivalence tools for bounding network capacities is introduced. Part I treats networks of point-to-point channels. The main result is roughly as follows. Given a network of noisy, independent, memoryless point-to-point channels, a collection of communication demands can be met on the given network if and only if it can be met on another network where each noisy channel is replaced by a noiseless bit pipe with throughput equal to the noisy channel capacity. This result was known previously for the case of a single-source multicast demand. The result given here treats general demands -- including, for example, multiple unicast demands -- and applies even when the achievable rate region for the corresponding demands is unknown in the noiseless network. In part II, definitions of upper and lower bounding channel models for general channels are introduced. By these definitions, a collection of communication demands can be met on a network of independent channels if it can be met on a network where each channel is replaced by its lower bounding model andonly if it can be met on a network where each channel is replaced by its upper bounding model. This work derives general conditions under which a network of noiseless bit pipes is an upper or lower bounding model for a multiterminal channel. Example upper and lower bounding models for broadcast, multiple access, and interference channels are given. It is then shown that bounding the difference between the upper and lower bounding models for a given channel yields bounds on the accuracy of network capacity bounds derived using those models. By bounding the capacity of a network of independent noisy channels by the network coding capacity of a network of noiseless bit pipes, this approach represents one step towards the goal of building computational tools for bounding network capacities.
Compositional closure for Bayes Risk in probabilistic noninterference
Venue: arXiv cs.FL 2010
Year: 2010

We give a sequential model for noninterference security including probability (but not demonic choice), thus supporting reasoning about the likelihood that high-security values might be revealed by observations of low-security activity. Our novel methodological contribution is the definition of a refinement order and its use to compare security measures between specifications and (their supposed) implementations. This contrasts with the more common practice of evaluating the security of individual programs in isolation. The appropriateness of our model and order is supported by our showing that our refinement order is the greatest compositional relation --the compositional closure-- with respect to our semantics and an "elementary" order based on Bayes Risk --- a security measure already in widespread use. We also relate refinement to other measures such as Shannon Entropy. By applying the approach to a non-trivial example, the anonymous-majority Three-Judges protocol, we demonstrate by example that correctness arguments can be simplified by the sort of layered developments --through levels of increasing detail-- that are allowed and encouraged by compositional semantics.
Using CSP To Improve Deterministic 3-SAT
Venue: arXiv cs.DS 2010
Year: 2010

We show how one can use certain deterministic algorithms for higher-value constraint satisfaction problems (CSPs) to speed up deterministic local search for 3-SAT. This way, we improve the deterministic worst-case running time for 3-SAT to O(1.439^n).
A Jamming-Resistant MAC Protocol for Multi-Hop Wireless Networks
Venue: arXiv cs.DC 2010
Year: 2010

This paper presents a simple local medium access control protocol, called \textsc{Jade}, for multi-hop wireless networks with a single channel that is provably robust against adaptive adversarial jamming. The wireless network is modeled as a unit disk graph on a set of nodes distributed arbitrarily in the plane. In addition to these nodes, there are adversarial jammers that know the protocol and its entire history and that are allowed to jam the wireless channel at any node for an arbitrary $(1-ε)$-fraction of the time steps, where $0<ε<1$ is an arbitrary constant. We assume that the nodes cannot distinguish between jammed transmissions and collisions of regular messages. Nevertheless, we show that \textsc{Jade} achieves an asymptotically optimal throughput if there is a sufficiently dense distribution of nodes.
Efficient Sketches for the Set Query Problem
Venue: arXiv cs.DS 2010
Year: 2010

We develop an algorithm for estimating the values of a vector x in R^n over a support S of size k from a randomized sparse binary linear sketch Ax of size O(k). Given Ax and S, we can recover x' with ||x' - x_S||_2 <= eps ||x - x_S||_2 with probability at least 1 - k^{-Ω(1)}. The recovery takes O(k) time. While interesting in its own right, this primitive also has a number of applications. For example, we can: 1. Improve the linear k-sparse recovery of heavy hitters in Zipfian distributions with O(k log n) space from a (1+eps) approximation to a (1 + o(1)) approximation, giving the first such approximation in O(k log n) space when k <= O(n^{1-eps}). 2. Recover block-sparse vectors with O(k) space and a (1+eps) approximation. Previous algorithms required either omega(k) space or omega(1) approximation.
Improved approximation bounds for Vector Bin Packing
Venue: arXiv cs.DS 2010
Year: 2010

In this paper we propose an improved approximation scheme for the Vector Bin Packing problem (VBP), based on the combination of (near-)optimal solution of the Linear Programming (LP) relaxation and a greedy (modified first-fit) heuristic. The Vector Bin Packing problem of higher dimension (d \geq 2) is not known to have asymptotic polynomial-time approximation schemes (unless P = NP). Our algorithm improves over the previously-known guarantee of (ln d + 1 + epsilon) by Bansal et al. [1] for higher dimensions (d > 2). We provide a θ(1) approximation scheme for certain set of inputs for any dimension d. More precisely, we provide a 2-OPT algorithm, a result which is irrespective of the number of dimensions d.
Top-K Color Queries for Document Retrieval
Venue: arXiv cs.DS 2010
Year: 2010

In this paper we describe a new efficient (in fact optimal) data structure for the {\em top-$K$ color problem}. Each element of an array $A$ is assigned a color $c$ with priority $p(c)$. For a query range $[a,b]$ and a value $K$, we have to report $K$ colors with the highest priorities among all colors that occur in $A[a..b]$, sorted in reverse order by their priorities. We show that such queries can be answered in $O(K)$ time using an $O(N\log σ)$ bits data structure, where $N$ is the number of elements in the array and $σ$ is the number of colors. Thus our data structure is asymptotically optimal with respect to the worst-case query time and space. As an immediate application of our results, we obtain optimal time solutions for several document retrieval problems. The method of the paper could be also of independent interest.
Flows in One-Crossing-Minor-Free Graphs
Venue: arXiv cs.DS 2010
Year: 2010

We study the maximum flow problem in directed H-minor-free graphs where H can be drawn in the plane with one crossing. If a structural decomposition of the graph as a clique-sum of planar graphs and graphs of constant complexity is given, we show that a maximum flow can be computed in O(n log n) time. In particular, maximum flows in directed K_{3,3}-minor-free graphs and directed K_5-minor-free graphs can be computed in O(n log n) time without additional assumptions.
Quantum search by partial adiabatic evolution
Venue: arXiv cs.DS 2010
Year: 2010

A quantum search algorithm based on the partial adiabatic evolution\cite{Tulsi2009} is provided. We calculate its time complexity by studying the Hamiltonian in a two-dimensional Hilbert space. It is found that the algorithm improves the time complexity, which is $O(\sqrt{N/M})$, of the local adiabatic search algorithm\cite{Roland2002}, to $O(\sqrt{N}/M)$.
Stability Analysis of GI/G/c/K Retrial Queue with Constant Retrial Rate
Venue: arXiv cs.NI 2010
Year: 2010

We consider a GI/G/c/K-type retrial queueing system with constant retrial rate. The system consists of a primary queue and an orbit queue. The primary queue has $c$ identical servers and can accommodate the maximal number of $K$ jobs. If a newly arriving job finds the full primary queue, it joins the orbit. The original primary jobs arrive to the system according to a renewal process. The jobs have general i.i.d. service times. A job in front of the orbit queue retries to enter the primary queue after an exponentially distributed time independent of the orbit queue length. Telephone exchange systems, Medium Access Protocols and short TCP transfers are just some applications of the proposed queueing system. For this system we establish minimal sufficient stability conditions. Our model is very general. In addition, to the known particular cases (e.g., M/G/1/1 or M/M/c/c systems), the proposed model covers as particular cases the deterministic service model and the Erlang model with constant retrial rate. The latter particular cases have not been considered in the past. The obtained stability conditions have clear probabilistic interpretation.
Generalized Mean-payoff and Energy Games
Venue: arXiv cs.LO 2010
Year: 2010

In mean-payoff games, the objective of the protagonist is to ensure that the limit average of an infinite sequence of numeric weights is nonnegative. In energy games, the objective is to ensure that the running sum of weights is always nonnegative. Generalized mean-payoff and energy games replace individual weights by tuples, and the limit average (resp. running sum) of each coordinate must be (resp. remain) nonnegative. These games have applications in the synthesis of resource-bounded processes with multiple resources. We prove the finite-memory determinacy of generalized energy games and show the inter-reducibility of generalized mean-payoff and energy games for finite-memory strategies. We also improve the computational complexity for solving both classes of games with finite-memory strategies: while the previously best known upper bound was EXPSPACE, and no lower bound was known, we give an optimal coNP-complete bound. For memoryless strategies, we show that the problem of deciding the existence of a winning strategy for the protagonist is NP-complete.