OpenRaiser/Intern-Atlas huggingface dataset:
Fast adaptive elliptical filtering using box splines
Venue: arXiv cs.IT 2009
Year: 2009

We demonstrate that it is possible to filter an image with an elliptic window of varying size, elongation and orientation with a fixed computational cost per pixel. Our method involves the application of a suitable global pre-integrator followed by a pointwise-adaptive localization mesh. We present the basic theory for the 1D case using a B-spline formalism and then appropriately extend it to 2D using radially-uniform box splines. The size and ellipticity of these radially-uniform box splines is adaptively controlled. Moreover, they converge to Gaussians as the order increases. Finally, we present a fast and practical directional filtering algorithm that has the capability of adapting to the local image features.
Spreading grid cells
Venue: arXiv cs.CG 2009
Year: 2009

Let $S$ be a set of $n^2$ symbols. Let $A$ be an $n\times n$ square grid with each cell labeled by a distinct symbol in $S$. Let $B$ be another $n\times n$ square grid, also with each cell labeled by a distinct symbol in $S$. Then each symbol in $S$ labels two cells, one in $A$ and one in $B$. Define the \emph{combined distance} between two symbols in $S$ as the distance between the two cells in $A$ plus the distance between the two cells in $B$ that are labeled by the two symbols. Belén Palop asked the following question at the open problems session of CCCG 2009: How to arrange the symbols in the two grids such that the minimum combined distance between any two symbols is maximized? In this paper, we give a partial answer to Belén Palop's question. Define $c_p(n) = \max_{A,B}\min_{s,t \in S} \{\dist_p(A,s,t) + \dist_p(B,s,t) \}$, where $A$ and $B$ range over all pairs of $n\times n$ square grids labeled by the same set $S$ of $n^2$ distinct symbols, and where $\dist_p(A,s,t)$ and $\dist_p(B,s,t)$ are the $L_p$ distances between the cells in $A$ and in $B$, respectively, that are labeled by the two symbols $s$ and $t$. We present asymptotically optimal bounds $c_p(n) = Θ(\sqrt{n})$ for all $p=1,2,...,\infty$. The bounds also hold for generalizations to $d$-dimensional grids for any constant $d \ge 2$. Our proof yields a simple linear-time constant-factor approximation algorithm for maximizing the minimum combined distance between any two symbols in two grids.
Training-Based Schemes are Suboptimal for High Rate Asynchronous Communication
Venue: arXiv cs.IT 2009
Year: 2009

We consider asynchronous point-to-point communication. Building on a recently developed model, we show that training based schemes, i.e., communication strategies that separate synchronization from information transmission, perform suboptimally at high rate.
Retrieval of Remote Sensing Images Using Colour and Texture Attribute
Venue: arXiv cs.IR 2009
Year: 2009

Grouping images into semantically meaningful categories using low-level visual feature is a challenging and important problem in content-based image retrieval. The groupings can be used to build effective indices for an image database. Digital image analysis techniques are being used widely in remote sensing assuming that each terrain surface category is characterized with spectral signature observed by remote sensors. Even with the remote sensing images of IRS data, integration of spatial information is expected to assist and to improve the image analysis of remote sensing data. In this paper we present a satellite image retrieval based on a mixture of old fashioned ideas and state of the art learning tools. We have developed a methodology to classify remote sensing images using HSV color features and Haar wavelet texture features and then grouping them on the basis of particular threshold value. The experimental results indicate that the use of color and texture feature extraction is very useful for image retrieval.
Efficient Authenticated Data Structures for Graph Connectivity and Geometric Search Problems
Venue: arXiv cs.CR 2009
Year: 2009

Authenticated data structures provide cryptographic proofs that their answers are as accurate as the author intended, even if the data structure is being controlled by a remote untrusted host. We present efficient techniques for authenticating data structures that represent graphs and collections of geometric objects. We introduce the path hash accumulator, a new primitive based on cryptographic hashing for efficiently authenticating various properties of structured data represented as paths, including any decomposable query over sequences of elements. We show how to employ our primitive to authenticate queries about properties of paths in graphs and search queries on multi-catalogs. This allows the design of new, efficient authenticated data structures for fundamental problems on networks, such as path and connectivity queries over graphs, and complex queries on two-dimensional geometric objects, such as intersection and containment queries.
ABC-LogitBoost for Multi-class Classification
Venue: arXiv cs.LG 2009
Year: 2009

We develop abc-logitboost, based on the prior work on abc-boost and robust logitboost. Our extensive experiments on a variety of datasets demonstrate the considerable improvement of abc-logitboost over logitboost and abc-mart.
Exploration of the Gap Between Computer Science Curriculum and Industrial I.T Skills Requirements
Venue: arXiv cs.GL 2009
Year: 2009

This paper sets out to examine the skills gaps between the industrial application of Information Technology and university academic programmes (curriculum). It looks at some of the causes, and considers the probable solutions for bridging the gap between them and suggests the possibilities of exploring a new role for our universities and employers of labor. It also highlights strategies to abolish the misalignment between university and industry. The main concept is to blend the academic rigidity with the industrial relevance.
Distributed Flooding-based Storage Algorithms for Large-scale Sensor Networks
Venue: arXiv cs.IT 2009
Year: 2009

In this paper we propose distributed flooding-based storage algorithms for large-scale wireless sensor networks. Assume a wireless sensor network with $n$ nodes that have limited power, memory, and bandwidth. Each node is capable of both sensing and storing data. Such sensor nodes might disappear from the network due to failures or battery depletion. Hence it is desired to design efficient schemes to collect data from these $n$ nodes. We propose two distributed storage algorithms (DSA's) that utilize network flooding to solve this problem. In the first algorithm, DSA-I, we assume that every node utilizes network flooding to disseminate its data throughout the network using a mixing time of approximately O(n). We show that this algorithm is efficient in terms of the encoding and decoding operations. In the second algorithm, DSA-II, we assume that the total number of nodes is not known to every sensor; hence dissemination of the data does not depend on $n$. The encoding operations in this case take $O(Cμ^2)$, where $μ$ is the mean degree of the network graph and $C$ is a system parameter. We evaluate the performance of the proposed algorithms through analysis and simulation, and show that their performance matches the derived theoretical results.
Online Algorithms for Self-Organizing Sequential Search - A Survey
Venue: arXiv cs.DS 2009
Year: 2009

The main objective of this survey is to present the important theoretical and experimental results contributed till date in the area of online algorithms for the self organizing sequential search problem, also popularly known as the List Update Problem(LUP) in a chronological way. The survey includes competitiveness results of deterministic and randomized online algorithms and complexity results of optimal off line algorithms for the list update problem. We also present the results associated with list update with look ahead, list update with locality of reference and other variants of the list update problem. We investigate research issues, explore scope of future work associated with each issue so that future researchers can find it useful to work on.
Reasoning with Topological and Directional Spatial Information
Venue: arXiv cs.AI 2009
Year: 2009

Current research on qualitative spatial representation and reasoning mainly focuses on one single aspect of space. In real world applications, however, multiple spatial aspects are often involved simultaneously. This paper investigates problems arising in reasoning with combined topological and directional information. We use the RCC8 algebra and the Rectangle Algebra (RA) for expressing topological and directional information respectively. We give examples to show that the bipath-consistency algorithm BIPATH is incomplete for solving even basic RCC8 and RA constraints. If topological constraints are taken from some maximal tractable subclasses of RCC8, and directional constraints are taken from a subalgebra, termed DIR49, of RA, then we show that BIPATH is able to separate topological constraints from directional ones. This means, given a set of hybrid topological and directional constraints from the above subclasses of RCC8 and RA, we can transfer the joint satisfaction problem in polynomial time to two independent satisfaction problems in RCC8 and RA. For general RA constraints, we give a method to compute solutions that satisfy all topological constraints and approximately satisfy each RA constraint to any prescribed precision.
Reasoning about Cardinal Directions between Extended Objects
Venue: arXiv cs.AI 2009
Year: 2009

Direction relations between extended spatial objects are important commonsense knowledge. Recently, Goyal and Egenhofer proposed a formal model, known as Cardinal Direction Calculus (CDC), for representing direction relations between connected plane regions. CDC is perhaps the most expressive qualitative calculus for directional information, and has attracted increasing interest from areas such as artificial intelligence, geographical information science, and image retrieval. Given a network of CDC constraints, the consistency problem is deciding if the network is realizable by connected regions in the real plane. This paper provides a cubic algorithm for checking consistency of basic CDC constraint networks, and proves that reasoning with CDC is in general an NP-Complete problem. For a consistent network of basic CDC constraints, our algorithm also returns a 'canonical' solution in cubic time. This cubic algorithm is also adapted to cope with cardinal directions between possibly disconnected regions, in which case currently the best algorithm is of time complexity O(n^5).
State Space Reduction with Message Inspection in Security Protocol Model Checking
Venue: arXiv cs.CR 2009
Year: 2009

Model checking is a widespread automatic formal analysis that has been successful in discovering flaws in security protocols. However existing possibilities for state space explosion still hinder analyses of complex protocols and protocol configurations. Message Inspection, is a technique that delimits the branching of the state space due to the intruder model without excluding possible attacks. In a preliminary simulation, the intruder model tags the eavesdropped messages with specific metadata that enable validation of feasibility of possible attack actions. The Message Inspection algorithm then decides based on these metadata, which attacks will certainly fail according to known security principles. Thus, it is a priori known that i.e. an encryption scheme attack cannot succeed if the intruder does not posses the right key in his knowledge. The simulation terminates with a report of the attack actions that can be safely removed, resulting in a model with a reduced state space.
Median topographic maps for biomedical data sets
Venue: arXiv cs.LG 2009
Year: 2009

Median clustering extends popular neural data analysis methods such as the self-organizing map or neural gas to general data structures given by a dissimilarity matrix only. This offers flexible and robust global data inspection methods which are particularly suited for a variety of data as occurs in biomedical domains. In this chapter, we give an overview about median clustering and its properties and extensions, with a particular focus on efficient implementations adapted to large scale data analysis.
On Planning with Preferences in HTN
Venue: arXiv cs.AI 2009
Year: 2009

In this paper, we address the problem of generating preferred plans by combining the procedural control knowledge specified by Hierarchical Task Networks (HTNs) with rich qualitative user preferences. The outcome of our work is a language for specifyin user preferences, tailored to HTN planning, together with a provably optimal preference-based planner, HTNPLAN, that is implemented as an extension of SHOP2. To compute preferred plans, we propose an approach based on forward-chaining heuristic search. Our heuristic uses an admissible evaluation function measuring the satisfaction of preferences over partial plans. Our empirical evaluation demonstrates the effectiveness of our HTNPLAN heuristics. We prove our approach sound and optimal with respect to the plans it generates by appealing to a situation calculus semantics of our preference language and of HTN planning. While our implementation builds on SHOP2, the language and techniques proposed here are relevant to a broad range of HTN planners.
Decision Problems For Turing Machines
Venue: arXiv cs.LO 2009
Year: 2009

We answer two questions posed by Castro and Cucker, giving the exact complexities of two decision problems about cardinalities of omega-languages of Turing machines. Firstly, it is $D_2(Σ_1^1)$-complete to determine whether the omega-language of a given Turing machine is countably infinite, where $D_2(Σ_1^1)$ is the class of 2-differences of $Σ_1^1$-sets. Secondly, it is $Σ_1^1$-complete to determine whether the omega-language of a given Turing machine is uncountable.
Object-Oriented Intensional Programming: Intensional Classes Using Java and Lucid
Venue: arXiv cs.PL 2009
Year: 2009

This article introduces Object-Oriented Intensional Programming (OO-IP), a new hybrid language between Object-Oriented and Intensional Programming Languages in the sense of the latest evolutions of Lucid. This new hybrid language combines the essential characteristics of Lucid and Java, and introduces the notion of object streams which makes it is possible that each element in a Lucid stream to be an object with embedded intensional properties. Interestingly, this hybrid language also brings to Java objects the power to explicitly express and manipulate the notion of context, creating the novel concept of intensional object, i.e. objects whose evaluation is context-dependent, which are here demonstrated to be translatable into standard objects. By this new approach, we extend the use and meaning of the notion of intensional objects and enrich the meaning of object streams in Lucid and semantics of intensional objects in Java.
High-Dimensional Non-Linear Variable Selection through Hierarchical Kernel Learning
Venue: arXiv cs.LG 2009
Year: 2009

We consider the problem of high-dimensional non-linear variable selection for supervised learning. Our approach is based on performing linear selection among exponentially many appropriately defined positive definite kernels that characterize non-linear interactions between the original variables. To select efficiently from these many kernels, we use the natural hierarchical structure of the problem to extend the multiple kernel learning framework to kernels that can be embedded in a directed acyclic graph; we show that it is then possible to perform kernel selection through a graph-adapted sparsity-inducing norm, in polynomial time in the number of selected kernels. Moreover, we study the consistency of variable selection in high-dimensional settings, showing that under certain assumptions, our regularization framework allows a number of irrelevant variables which is exponential in the number of observations. Our simulations on synthetic datasets and datasets from the UCI repository show state-of-the-art predictive performance for non-linear regression problems.
Capacity Region of Layered Erasure One-sided Interference Channels without CSIT
Venue: arXiv cs.IT 2009
Year: 2009

This paper studies a layered erasure interference channel model, which is a simplification of the Gaussian interference channel with fading using the deterministic model approach. In particular, the capacity region of the layered erasure one-sided interference channel is completely determined, assuming that the channel state information (CSI) is known to the receivers, but there is no CSI at transmitters (CSIT). The result holds for arbitrary fading statistics. Previous results of Aggarwal, Sankar, Calderbank and Poor on the capacity region or sum capacity under several interference configurations are shown to be special cases of the capacity region shown in this paper.
User Experience, Software Interfaces, and The Unconscious
Venue: arXiv cs.HC 2009
Year: 2009

Ideas about how to increase the unconscious participation in interaction between 'a human' and 'a computer' are developed in this paper. Evidence of impact of the unconscious functioning is presented. The unconscious is characterised as being a responsive, contextual, and autonomous participant of human-computer interaction. The unconscious participation occurs independently of one's cognitive and educational levels and, if ignored, leads to learning inefficiencies and compulsive behaviours, illustrations of which are provided. Three practical approaches to a study of subjective user experience are outlined as follows: (a) tracing operant conditioning effects of software, (b) registering signs of brain activity psychological or information processing meaning of which is well-explored and (c) exploring submodality interfaces. Implications for improvement of current usability study methods, such as eye-tracking, are generally considered. Conclusions consider advantages and disadvantages of unconscious-embracing design and remind about a loss of human evolutionary choices if unconscious participation is ignored, complicated or blocked in interaction with computer interfaces and built environment.
A rich hierarchy of functionals of finite types
Venue: arXiv cs.LO 2009
Year: 2009

We are considering typed hierarchies of total, continuous functionals using complete, separable metric spaces at the base types. We pay special attention to the so called Urysohn space constructed by P. Urysohn. One of the properties of the Urysohn space is that every other separable metric space can be isometrically embedded into it. We discuss why the Urysohn space may be considered as the universal model of possibly infinitary outputs of algorithms. The main result is that all our typed hierarchies may be topologically embedded, type by type, into the corresponding hierarchy over the Urysohn space. As a preparation for this, we prove an effective density theorem that is also of independent interest.
SNR Estimation in Maximum Likelihood Decoded Spatial Multiplexing
Venue: arXiv cs.IT 2009
Year: 2009

Link adaptation is a crucial part of many modern communications systems, allowing the system to adapt the transmission and reception strategies to changes in channel conditions. One of the fundamental components of the link adaptation mechanism is signal to noise ratio (SNR) estimation, measuring the instantaneous (mostly post processing) SNR at the receiver. That is, the SNR at the decoder input, which is an important metric for the prediction of decoder performance. In linearly decoded MIMO, which is the common MIMO decoding strategy, the post processing SNR is well defined. However, this is not the case in optimal maximum likelihood (ML) decoding applied to spatial multiplexing (SM). This gap is interesting since ML decoded SM is gaining ever growing interest in recent research and practice due to the rapid increase in computation power, and available near optimal low complexity schemes. In this paper we close the gap and provide SNR estimation schemes for ML decoded SM, which are based on various approximations of the "per stream" error probability. The proposed methods are applicable for both horizonal and vertical decoding. Moreover, we propose a very low complexity implementation for the SNR estimation mechanism employing the ML decoder itself with negligible overhead.
On The Optimality Of All To All Broadcast In k ary n dimensional Tori
Venue: arXiv cs.NI 2009
Year: 2009

All to all broadcast is a collective communication in a network with the constraint that every node must send to each other certain piece of its data. This paper addresses the problem of optimal all port all to all broadcast in multidimensional tori. The optimality criteria considered are the minimum exchange steps, no duplicated data in the sense that only new data are conveyed to receivers and the balance of the communication links load. It is proved that under these constraints, an optimal broadcast is not feasible in any multidimensional torus. Then, the tori which are capable of optimal broadcasts are characterized.
On the Relations Between Diffie-Hellman and ID-Based Key Agreement from Pairings
Venue: arXiv cs.CR 2009
Year: 2009

This paper studies the relationships between the traditional Diffie-Hellman key agreement protocol and the identity-based (ID-based) key agreement protocol from pairings. For the Sakai-Ohgishi-Kasahara (SOK) ID-based key construction, we show that identical to the Diffie-Hellman protocol, the SOK key agreement protocol also has three variants, namely \emph{ephemeral}, \emph{semi-static} and \emph{static} versions. Upon this, we build solid relations between authenticated Diffie-Hellman (Auth-DH) protocols and ID-based authenticated key agreement (IB-AK) protocols, whereby we present two \emph{substitution rules} for this two types of protocols. The rules enable a conversion between the two types of protocols. In particular, we obtain the \emph{real} ID-based version of the well-known MQV (and HMQV) protocol. Similarly, for the Sakai-Kasahara (SK) key construction, we show that the key transport protocol underlining the SK ID-based encryption scheme (which we call the "SK protocol") has its non-ID counterpart, namely the Hughes protocol. Based on this observation, we establish relations between corresponding ID-based and non-ID-based protocols. In particular, we propose a highly enhanced version of the McCullagh-Barreto protocol.
Resource Matchmaking Algorithm using Dynamic Rough Set in Grid Environment
Venue: arXiv cs.DC 2009
Year: 2009

Grid environment is a service oriented infrastructure in which many heterogeneous resources participate to provide the high performance computation. One of the bug issues in the grid environment is the vagueness and uncertainty between advertised resources and requested resources. Furthermore, in an environment such as grid dynamicity is considered as a crucial issue which must be dealt with. Classical rough set have been used to deal with the uncertainty and vagueness. But it can just be used on the static systems and can not support dynamicity in a system. In this work we propose a solution, called Dynamic Rough Set Resource Discovery (DRSRD), for dealing with cases of vagueness and uncertainty problems based on Dynamic rough set theory which considers dynamic features in this environment. In this way, requested resource properties have a weight as priority according to which resource matchmaking and ranking process is done. We also report the result of the solution obtained from the simulation in GridSim simulator. The comparison has been made between DRSRD, classical rough set theory based algorithm, and UDDI and OWL S combined algorithm. DRSRD shows much better precision for the cases with vagueness and uncertainty in a dynamic system such as the grid rather than the classical rough set theory based algorithm, and UDDI and OWL S combined algorithm.