No description available.

No description available.

No description available.

The shortest path problem in graphs is both a classic combinatorial optimization problem and a practical problem that admits many applications. Techniques for preprocessing a graph are useful for reducing shortest path query times. This dissertation studies the foundations of a class of algorithms that use preprocessed landmark information and the triangle inequality to guide A* search in graphs. A new heuristic is presented for solving shortest path queries that enables the use of higher order polygon inequalities. We demonstrate this capability by leveraging distance information from two landmarks when visiting a vertex as opposed to the common single landmark paradigm. The new heuristic’s novel feature is that it computes and stores a reduced amount of preprocessed information (in comparison to previous landmark-based algorithms) while enabling more informed search decisions. We demonstrate that domination of this heuristic over its predecessor depends on landmark selection and that, in general, the denser the landmark set, the better heuristic performs. Due to the reduced memory requirement, this new heuristic admits much denser landmark sets. We conduct experiments to characterize the impact that landmark configurations have on this new heuristic, demonstrating that centrality-based landmark selection has the best tradeoff between preprocessing and runtime. Using a developed graph library and static information from benchmark road map datasets, the algorithm is compared experimentally with previous landmark-based shortest path techniques in a fixed-memory environment to demonstrate a reduction in overall computational time and memory requirements. Experimental results are evaluated to detail the significance of landmark selection and density, the tradeoffs of performing preprocessing, and the practical use cases of the algorithm.

The aim of this thesis is to build the foundations of generalized ordinary differ- ential equation theory in metric spaces. While differential equations in metric spaces have been studied before, the chosen approach cannot be extended to in- clude more general types of integral equations. We introduce a definition which combines the added generality of metric spaces with the strength of Kurzweil's generalized ordinary differential equations. Additionally, we present existence and uniqueness theorems which offer new results even in the context of Euclidean spaces.

Estruturas de indexação para domínios métricos são úteis para agilizar consultas por similaridade sobre dados complexos, tais como imagens, onde o custo computacional da comparação de dois itens de dados geralmente é alto. O estado da arte para executar consultas por similaridade está centrado na utilização dos chamados \"Métodos de Acesso Métrico\" (MAM). Tais métodos consideram os dados como elementos de um espaço métrico, onde apenas valem as propriedades fundamentais para que um espaço seja considerado métrico, onde a única informação que os MAMs utilizam é a medida de similaridade entre pares de elementos do domínio. No campo teórico, espaços métricos são extensamente estudados e servem de base para diversas áreas da Matemática. No entanto, a maioria dos trabalhos que têm sido desenvolvidos em Computação se restringem a utilizar as definições básicas desses espaços, e não foram encontrados estudos que explorem em mais profundidade os muitos conceitos teóricos existentes. Assim, este trabalho aplica conceitos teóricos importantes da Teoria de Espaços Métricos para desenvolver técnicas que auxiliem o tratamento e a manipulação dos diversos dados complexos, visando principalmente o desenvolvimento de métodos de indexação mais eficientes. É desenvolvida uma técnica para realizar um mapeamento de espaços métricos que leva à atenuação do efeito da maldição da dimensionalidade, a partir de uma aplicação lipschitziana real baseada em uma função de deformação do espaço das distâncias entre os elementos do conjunto. Foi mostrado que uma função do tipo exponecial deforma as distâncias de modo a diminuir os efeitos da maldição da dimensionalidade, melhorando assim o desempenho nas consultas. Uma segunda contribuição é o desenvolvimento de uma técnica para a imersão de espaços métricos, realizada de maneira a preservar a ordem das distâncias, possibilitando a utilização de propriedades no espaço de imersão. A imersão de espaços métricos no \' R POT. n\' possibilita a utilização da lei dos cossenos e assim viabiliza o cálculo de distâncias entre elementos e um hiperplano métrico, permitindo aumentar a agilidade à consultas por similaridade. O uso do hiperplano métrico foi exemplificado construindo uma árvore binária métrica, e também foi aplicado em um método de acesso métrico, a família MMH de métodos de acesso métrico, melhorando o particionamento do espaço dos dados / The access methods designed for metric domains are useful to answer similarity queries on any type of data, being specially useful to index complex data, such as images, where the computacional cost of comparison are high. The main mecanism used up to now to perform similarity queries is centered on \"Metric Acess Methods\" (MAM). Such methods consider data as elements that belong to a metric space, where only hold the properties that define the metric space. Therefore, the only information that a MAM can use is the similarity measure between pairs of elements in the domain. Metric spaces are extremelly well studied and is the basis for many mathematics areas. However, most researches from computer science are restrained to use the basic properties of metric spaces, not exploring the various existing theorical concepts. This work apply theoretical concepts of metric spaces to develop techniques aiding the treatment and manipulation of diverse complex data, aiming at developing more efficient indexing methods. A technique of mapping spaces was developed in order to ease the dimensionality curse effects, basing on a real lipschitz application that uses a stretching function that changes the distance space of elements. It was shown that an exponential function changes the distances space reducing the dimensionality curse effects, improving query operations. A second contribution is the developing of a technique based on metric space immersion, preserving the distances order between pairs of elements, allowing the usage of immersion space properties. The immersion of metric spaces into \'R POT. n\' allow the usage of the cossine law leading to the determination of distances between elements and a hiperplane, forming metric hiperplanes. The use of the metric hiperplanes lead to an improvement of query operations performance. The metric hiperplane itself formed the binary metric tree, and when applied to a metric access method, lead the formation of a family of metric access methods that improves the metric space particioning achieving faster similarity queries

We investigate two combinatorial properties of classes of finite structures, as well as related applications to topological dynamics. Using the Hrushovski property of classes of finite structures -- a finite extension property of homomorphisms -- we can show the existence of ample generics. For example, Solecki proved the existence of ample generics in the context of finite metric spaces that do indeed possess this extension property. Furthermore, Kechris, Pestov and Todorcevic have shown that the Ramsey property of Fraisse classes of finite structures implies that the automorphism group of the corresponding Fraisse limit is extremely amenable, i.e., it possesses a very strong fixed point property. Gromov and Milman had shown that the unitary group of the infinite-dimensional separable Hilbert space is extremely amenable using non-combinatorial methods. This result encourages a deeper look into structural Euclidean Ramsey theory, i.e., Euclidean Ramsey theory in which we colour more than just points. In particular, we look at complete finite labeled graphs whose vertex sets are subsets of the Hilbert space and whose labels correspond to the inner products. We prove "Ramsey-type" and "Hrushovski-type" theorems for linearly ordered metric subspaces of "sufficiently" orthogonal sets. In particular, the latter is used to show a "Hrushovski version" of the Ramsey-type Matousek-Rodl theorem for simplices. It is known that the square root of the metric induced by the distance between vertices in graphs produces a metric space embeddable in a Euclidean space if and only if the graph is a metric subgraph of the Cartesian product of three types of graphs. These three are the half-cube graphs, the so-called cocktail party graphs, and the Gosset graph. We show that the class of metric spaces related to half-cube graphs -- metric spaces on sets with the symmetric difference metric -- satisfies the Hrushovski property up to 3 points, but not more. Moreover, the amalgamation in this class can be too restrictive to permit the Ramsey Property. Finally, following the work of Fouche, we compute the Ramsey degrees of structures induced by the leaf sets of boron trees. Also, we briefly show that this class does not satisfy the full Hrushovski property. Fouche's trees are in fact related to ultrametric spaces, as was observed by Lionel Nguyen van The. We augment Fouche's concept of orientation so that it applies to these boron tree structures. The upper bound computation of the Ramsey degree in this case, turns out to be an "asymmetric" version of the Graham-Rothschild theorem. Finally, we extend these structures to "oriented" ones, yielding a Ramsey class and a corresponding Fraisse limit whose automorphism group is extremely amenable.

We investigate two combinatorial properties of classes of finite structures, as well as related applications to topological dynamics. Using the Hrushovski property of classes of finite structures -- a finite extension property of homomorphisms -- we can show the existence of ample generics. For example, Solecki proved the existence of ample generics in the context of finite metric spaces that do indeed possess this extension property. Furthermore, Kechris, Pestov and Todorcevic have shown that the Ramsey property of Fraisse classes of finite structures implies that the automorphism group of the corresponding Fraisse limit is extremely amenable, i.e., it possesses a very strong fixed point property. Gromov and Milman had shown that the unitary group of the infinite-dimensional separable Hilbert space is extremely amenable using non-combinatorial methods. This result encourages a deeper look into structural Euclidean Ramsey theory, i.e., Euclidean Ramsey theory in which we colour more than just points. In particular, we look at complete finite labeled graphs whose vertex sets are subsets of the Hilbert space and whose labels correspond to the inner products. We prove "Ramsey-type" and "Hrushovski-type" theorems for linearly ordered metric subspaces of "sufficiently" orthogonal sets. In particular, the latter is used to show a "Hrushovski version" of the Ramsey-type Matousek-Rodl theorem for simplices. It is known that the square root of the metric induced by the distance between vertices in graphs produces a metric space embeddable in a Euclidean space if and only if the graph is a metric subgraph of the Cartesian product of three types of graphs. These three are the half-cube graphs, the so-called cocktail party graphs, and the Gosset graph. We show that the class of metric spaces related to half-cube graphs -- metric spaces on sets with the symmetric difference metric -- satisfies the Hrushovski property up to 3 points, but not more. Moreover, the amalgamation in this class can be too restrictive to permit the Ramsey Property. Finally, following the work of Fouche, we compute the Ramsey degrees of structures induced by the leaf sets of boron trees. Also, we briefly show that this class does not satisfy the full Hrushovski property. Fouche's trees are in fact related to ultrametric spaces, as was observed by Lionel Nguyen van The. We augment Fouche's concept of orientation so that it applies to these boron tree structures. The upper bound computation of the Ramsey degree in this case, turns out to be an "asymmetric" version of the Graham-Rothschild theorem. Finally, we extend these structures to "oriented" ones, yielding a Ramsey class and a corresponding Fraisse limit whose automorphism group is extremely amenable.

No description available.

Estruturas de indexação para domínios métricos são úteis para agilizar consultas por similaridade sobre dados complexos, tais como imagens, onde o custo computacional da comparação de dois itens de dados geralmente é alto. O estado da arte para executar consultas por similaridade está centrado na utilização dos chamados \"Métodos de Acesso Métrico\" (MAM). Tais métodos consideram os dados como elementos de um espaço métrico, onde apenas valem as propriedades fundamentais para que um espaço seja considerado métrico, onde a única informação que os MAMs utilizam é a medida de similaridade entre pares de elementos do domínio. No campo teórico, espaços métricos são extensamente estudados e servem de base para diversas áreas da Matemática. No entanto, a maioria dos trabalhos que têm sido desenvolvidos em Computação se restringem a utilizar as definições básicas desses espaços, e não foram encontrados estudos que explorem em mais profundidade os muitos conceitos teóricos existentes. Assim, este trabalho aplica conceitos teóricos importantes da Teoria de Espaços Métricos para desenvolver técnicas que auxiliem o tratamento e a manipulação dos diversos dados complexos, visando principalmente o desenvolvimento de métodos de indexação mais eficientes. É desenvolvida uma técnica para realizar um mapeamento de espaços métricos que leva à atenuação do efeito da maldição da dimensionalidade, a partir de uma aplicação lipschitziana real baseada em uma função de deformação do espaço das distâncias entre os elementos do conjunto. Foi mostrado que uma função do tipo exponecial deforma as distâncias de modo a diminuir os efeitos da maldição da dimensionalidade, melhorando assim o desempenho nas consultas. Uma segunda contribuição é o desenvolvimento de uma técnica para a imersão de espaços métricos, realizada de maneira a preservar a ordem das distâncias, possibilitando a utilização de propriedades no espaço de imersão. A imersão de espaços métricos no \' R POT. n\' possibilita a utilização da lei dos cossenos e assim viabiliza o cálculo de distâncias entre elementos e um hiperplano métrico, permitindo aumentar a agilidade à consultas por similaridade. O uso do hiperplano métrico foi exemplificado construindo uma árvore binária métrica, e também foi aplicado em um método de acesso métrico, a família MMH de métodos de acesso métrico, melhorando o particionamento do espaço dos dados / The access methods designed for metric domains are useful to answer similarity queries on any type of data, being specially useful to index complex data, such as images, where the computacional cost of comparison are high. The main mecanism used up to now to perform similarity queries is centered on \"Metric Acess Methods\" (MAM). Such methods consider data as elements that belong to a metric space, where only hold the properties that define the metric space. Therefore, the only information that a MAM can use is the similarity measure between pairs of elements in the domain. Metric spaces are extremelly well studied and is the basis for many mathematics areas. However, most researches from computer science are restrained to use the basic properties of metric spaces, not exploring the various existing theorical concepts. This work apply theoretical concepts of metric spaces to develop techniques aiding the treatment and manipulation of diverse complex data, aiming at developing more efficient indexing methods. A technique of mapping spaces was developed in order to ease the dimensionality curse effects, basing on a real lipschitz application that uses a stretching function that changes the distance space of elements. It was shown that an exponential function changes the distances space reducing the dimensionality curse effects, improving query operations. A second contribution is the developing of a technique based on metric space immersion, preserving the distances order between pairs of elements, allowing the usage of immersion space properties. The immersion of metric spaces into \'R POT. n\' allow the usage of the cossine law leading to the determination of distances between elements and a hiperplane, forming metric hiperplanes. The use of the metric hiperplanes lead to an improvement of query operations performance. The metric hiperplane itself formed the binary metric tree, and when applied to a metric access method, lead the formation of a family of metric access methods that improves the metric space particioning achieving faster similarity queries