Slicing the metric space to provide quick indexing of complex data in the main memory

Searching in a dataset for elements that are similar to a given query element is a core problem in applications that manage complex data, and has been aided by metric access methods (MAMs). A growing number of applications require indices that must be built faster and repeatedly, also providing faster response for similarity queries. The increase in the main memory capacity and its lowering costs also motivate using memory-based MAMs. In this paper. we propose the Onion-tree, a new and robust dynamic memory-based MAM that slices the metric space into disjoint subspaces to provide quick indexing of complex data. It introduces three major characteristics: (i) a partitioning method that controls the number of disjoint subspaces generated at each node; (ii) a replacement technique that can change the leaf node pivots in insertion operations; and (iii) range and k-NN extended query algorithms to support the new partitioning method, including a new visit order of the subspaces in k-NN queries. Performance tests with both real-world and synthetic datasets showed that the Onion-tree is very compact. Comparisons of the Onion-tree with the MM-tree and a memory-based version of the Slim-tree showed that the Onion-tree was always faster to build the index. The experiments also showed that the Onion-tree significantly improved range and k-NN query processing performance and was the most efficient MAM, followed by the MM-tree, which in turn outperformed the Slim-tree in almost all the tests. (C) 2010 Elsevier B.V. All rights reserved.

The C(K, X) spaces for compact metric spaces K and X with a uniformly convex maximal factor

In this paper, we prove that if a Banach space X contains some uniformly convex subspace in certain geometric position, then the C(K, X) spaces of all X-valued continuous functions defined on the compact metric spaces K have exactly the same isomorphism classes that the C(K) spaces. This provides a vector-valued extension of classical results of Bessaga and Pelczynski (1960) [2] and Milutin (1966) [13] on the isomorphic classification of the separable C(K) spaces. As a consequence, we show that if 1 < p < q < infinity then for every infinite countable compact metric spaces K(1), K(2), K(3) and K(4) are equivalent: (a) C(K(1), l(p)) circle plus C(K(2), l(q)) is isomorphic to C(K(3), l(p)) circle plus (K(4), l(q)). (b) C(K(1)) is isomorphic to C(K(3)) and C(K(2)) is isomorphic to C(K(4)). (C) 2011 Elsevier Inc. All rights reserved.

A compact free space quantum key distribution system capable of daylight operation

A free space quantum key distribution system has been demonstrated. Consideration has been given to factors such as field of view and spectral width, to cut down the deleterious effect from background light levels. Suitable optical sources such as lasers and RCLEDs have been investigated as well as optimal wavelength choices, always with a view to building a compact and robust system. The implementation of background reduction measures resulted in a system capable of operating in daylight conditions. An autonomous system was left running and generating shared key material continuously for over 7 days. © 2009 Published by Elsevier B.V..

Every N-Dimensional Separable Metric Space Contains a Totally Disconnected (n-1)-Dimensional Subset with no True Quasi-Components

Владимир Тодоров, Петър Стоев - Тази бележка съдържа елементарна конструкция на множество с указаните в заглавието свойства. Да отбележим в допълнение, че така полученото множество остава напълно несвързано дори и след като се допълни с краен брой елементи.

Regrouping metric-space search index for search engine size adaptation

This work contributes to the development of search engines that self-adapt their size in response to fluctuations in workload. Deploying a search engine in an Infrastructure as a Service (IaaS) cloud facilitates allocating or deallocating computational resources to or from the engine. In this paper, we focus on the problem of regrouping the metric-space search index when the number of virtual machines used to run the search engine is modified to reflect changes in workload. We propose an algorithm for incrementally adjusting the index to fit the varying number of virtual machines. We tested its performance using a custom-build prototype search engine deployed in the Amazon EC2 cloud, while calibrating the results to compensate for the performance fluctuations of the platform. Our experiments show that, when compared with computing the index from scratch, the incremental algorithm speeds up the index computation 2–10 times while maintaining a similar search performance.

Weak and Semi Compatible Maps in Probabilistic Metric Space Using Implicit Relation

2000 Mathematics Subject Classification: 54H25, 47H10.

Self-adapting parallel metric-space search engine for variable query loads

This research focuses on automatically adapting a search engine size in response to fluctuations in query workload. Deploying a search engine in an Infrastructure as a Service (IaaS) cloud facilitates allocating or deallocating computer resources to or from the engine. Our solution is to contribute an adaptive search engine that will repeatedly re-evaluate its load and, when appropriate, switch over to a dierent number of active processors. We focus on three aspects and break them out into three sub-problems as follows: Continually determining the Number of Processors (CNP), New Grouping Problem (NGP) and Regrouping Order Problem (ROP). CNP means that (in the light of the changes in the query workload in the search engine) there is a problem of determining the ideal number of processors p active at any given time to use in the search engine and we call this problem CNP. NGP happens when changes in the number of processors are determined and it must also be determined which groups of search data will be distributed across the processors. ROP is how to redistribute this data onto processors while keeping the engine responsive and while also minimising the switchover time and the incurred network load. We propose solutions for these sub-problems. For NGP we propose an algorithm for incrementally adjusting the index to t the varying number of virtual machines. For ROP we present an ecient method for redistributing data among processors while keeping the search engine responsive. Regarding the solution for CNP, we propose an algorithm determining the new size of the search engine by re-evaluating its load. We tested the solution performance using a custom-build prototype search engine deployed in the Amazon EC2 cloud. Our experiments show that when we compare our NGP solution with computing the index from scratch, the incremental algorithm speeds up the index computation 2{10 times while maintaining a similar search performance. The chosen redistribution method is 25% to 50% faster than other methods and reduces the network load around by 30%. For CNP we present a deterministic algorithm that shows a good ability to determine a new size of search engine. When combined, these algorithms give an adapting algorithm that is able to adjust the search engine size with a variable workload.

Better-quasi-order : ideals and spaces

This thesis deals with combinatorics, order theory and descriptive set theory. The first contribution is to the theory of well-quasi-orders (wqo) and better-quasi-orders (bqo). The main result is the proof of a conjecture made by Maurice Pouzet in 1978 his thèse d'état which states that any wqo whose ideal completion remainder is bqo is actually bqo. Our proof relies on new results with both a combinatorial and a topological flavour concerning maps from a front into a compact metric space. The second contribution is of a more applied nature and deals with topological spaces. We define a quasi-order on the subsets of every second countable To topological space in a way that generalises the Wadge quasi-order on the Baire space, while extending its nice properties to virtually all these topological spaces. The Wadge quasi-order of reducibility by continuous functions is wqo on Borei subsets of the Baire space, this quasi-order is however far less satisfactory for other important topological spaces such as the real line, as Hertling, Ikegami and Schlicht notably observed. Some authors have therefore studied reducibility with respect to some classes of discontinuous functions to remedy this situation. We propose instead to keep continuity but to weaken the notion of function to that of relation. Using the notion of admissible representation studied in Type-2 theory of effectivity, we define the quasi-order of reducibility by relatively continuous relations. We show that this quasi-order both refines the classical hierarchies of complexity and is wqo on the Borei subsets of virtually every second countable To space - including every (quasi-)Polish space. -- Cette thèse se situe dans les domaines de la combinatoire, de la théorie des ordres et de la théorie descriptive. La première contribution concerne la théorie des bons quasi-ordres (wqo) et des meilleurs quasi-ordres (bqo). Le résultat principal est la preuve d'une conjecture, énoncée par Pouzet en 1978 dans sa thèse d'état, qui établit que tout wqo dont l'ensemble des idéaux non principaux ordonnés par inclusion forme un bqo est alors lui-même un bqo. La preuve repose sur de nouveaux résultats, qui allient la combinatoire et la topologie, au sujet des fonctions d'un front vers un espace métrique compact. La seconde contribution de cette thèse traite de la complexité topologique dans le cadre des espaces To à base dénombrable. Dans le cas de l'espace de Baire, le quasi-ordre de Wadge est un wqo sur les sous-ensembles Boréliens qui a suscité énormément d'intérêt. Cependant cette relation de réduction par fonctions continues s'avère bien moins satisfaisante pour d'autres espaces d'importance tels que la droite réelle, comme l'ont fait notamment remarquer Hertling, Schlicht et Ikegami. Nous proposons de conserver la continuité et d'affaiblir la notion de fonction pour celle de relation. Pour ce faire, nous utilisons la notion de représentation admissible étudiée en « Type-2 theory of effectivity » initiée par Weihrauch. Nous introduisons alors le quasi-ordre de réduction par relations relativement continues et montrons que celui-ci à la fois raffine les hiérarchies classiques de complexité topologique et forme un wqo sur les sous-ensembles Boréliens de chaque espace quasi-Polonais.

Stability of gradient semigroups under perturbations

In this paper we prove that gradient-like semigroups (in the sense of Carvalho and Langa (2009 J. Diff. Eqns 246 2646-68)) are gradient semigroups (possess a Lyapunov function). This is primarily done to provide conditions under which gradient semigroups, in a general metric space, are stable under perturbation exploiting the known fact (see Carvalho and Langa (2009 J. Diff. Eqns 246 2646-68)) that gradient-like semigroups are stable under perturbation. The results presented here were motivated by the work carried out in Conley (1978 Isolated Invariant Sets and the Morse Index (CBMS Regional Conference Series in Mathematics vol 38) (RI: American Mathematical Society Providence)) for groups in compact metric spaces (see also Rybakowski (1987 The Homotopy Index and Partial Differential Equations (Universitext) (Berlin: Springer)) for the Morse decomposition of an invariant set for a semigroup on a compact metric space).

On turbulent, erratic and other dynamical properties of Zadeh's extensions

Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP)

Chaos induced by turbulent and erratic functions

Let (X, d) be a compact metric space and f: X → X a continuous function and consider the hyperspace (K(X), H) of all nonempty compact subsets of X endowed with the Hausdorff metric induced by d. Let f̄: K(X) → K (X) be defined by f̄(A) = {f(a)/a ∈ A} the natural extension of f to K(X), then the aim of this work is to study the dynamics of f when f is turbulent (erratic, respectively) and its relationships.

Sobre a dimensão do quadrado de um espaço métrico compacto X de dimensão n e o conjunto dos mergulhos de X em R2n

Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)

The Feynman-Kac formula and applications to PDEs

The thesis presents a probabilistic approach to the theory of semigroups of operators, with particular attention to the Markov and Feller semigroups. The first goal of this work is the proof of the fundamental Feynman-Kac formula, which gives the solution of certain parabolic Cauchy problems, in terms of the expected value of the initial condition computed at the associated stochastic diffusion processes. The second target is the characterization of the principal eigenvalue of the generator of a semigroup with Markov transition probability function and of second order elliptic operators with real coefficients not necessarily self-adjoint. The thesis is divided into three chapters. In the first chapter we study the Brownian motion and some of its main properties, the stochastic processes, the stochastic integral and the Itô formula in order to finally arrive, in the last section, at the proof of the Feynman-Kac formula. The second chapter is devoted to the probabilistic approach to the semigroups theory and it is here that we introduce Markov and Feller semigroups. Special emphasis is given to the Feller semigroup associated with the Brownian motion. The third and last chapter is divided into two sections. In the first one we present the abstract characterization of the principal eigenvalue of the infinitesimal generator of a semigroup of operators acting on continuous functions over a compact metric space. In the second section this approach is used to study the principal eigenvalue of elliptic partial differential operators with real coefficients. At the end, in the appendix, we gather some of the technical results used in the thesis in more details. Appendix A is devoted to the Sion minimax theorem, while in appendix B we prove the Chernoff product formula for not necessarily self-adjoint operators.