<div> <div> <p>Due to the large volumes of spatial data, data is stored on clusters of machines that inter-communicate to achieve a task. In such distributed environment; communicating intermediate results among computing nodes dominates execution time. Communication overhead is even more dominant if processing is in memory. Moreover, the way spatial data is partitioned affects overall processing cost. Various partitioning strategies influence the size of the intermediate results. Spatial data poses the following additional challenges: 1)Storage load balancing because of the skewed distribution of spatial data over the underlying space, 2)Query load imbalance due to skewed query workload and query hotspots over both time and space, and 3)Lack of effective utilization of the computing resources. We introduce a new kNN query evaluation technique, termed BCDB, for evaluating nearest-neighbor queries (NN-queries, for short). In contrast to clustered partitioning of spatial data, BCDB explores the use of declustered partitioning of data to address data and query skew. BCDB uses summaries of the underling data and a coarse-grained index to localize processing of the NN-query on each local node as much as possible. The coarse-grained index is locally traversed using a new uncertain version of classical distance browsing resulting in minimal O( √k) elements to be communicated across all processing nodes.</p> </div> </div>

Proximity problems and point set embeddability problems are fundamental and well-studied in computational geometry and graph drawing. Examples of such problems that are of particular interest to us in this dissertation include: finding the closest pair among a set P of points, finding the k-nearest neighbors to each point p in P, answering reverse k-nearest neighbor queries, computing the Yao graph, the Semi-Yao graph and the Euclidean minimum spanning tree of P, and mapping the vertices of a planar graph to a set P of points without inducing edge crossings. In this dissertation, we consider so-called kinetic version of these problems, that is, the points are allowed to move continuously along known trajectories, which are subject to change. We design a set of data structures and a mechanism to efficiently update the data structures. These updates occur at critical, discrete times. Also, a query may arrive at any time. We want to answer queries quickly without solving problems from scratch, so we maintain solutions continuously. We present new techniques for giving kinetic solutions with better performance for some these problems, and we provide the first kinetic results for others. In particular, we provide: • A simple kinetic data structure (KDS) to maintain all the nearest neighbors and the closest pair. Our deterministic kinetic approach for maintenance of all the nearest neighbors improves the previous randomized kinetic algorithm. • An exact KDS for maintenance of the Euclidean minimum spanning tree, which improves the previous KDS. • The first KDS's for maintenance of the Yao graph and the Semi-Yao graph. • The first KDS to consider maintaining plane graphs on moving points. • The first KDS for maintenance of all the k-nearest neighbors, for any k ≥ 1. • The first KDS to answer the reverse k-nearest neighbor queries, for any k ≥ 1 in any fixed dimension, on a set of moving points. / Graduate

Com o crescente aumento no número de imagens geradas em mídias digitais surgiu a necessidade do desenvolvimento de novas técnicas de recuperação desses dados. Um critério de busca que pode ser utilizado na recuperação das imagens é o da dissimilaridade, no qual o usuário deseja recuperar as imagens semelhantes à uma imagem de consulta. Para a realização das consultas são empregados vetores de características extraídos das imagens e funções de distância para medir a dissimilaridade entre pares desses vetores. Infelizmente, a busca por conteúdo de imagens em consultas simples tende a gerar resultados que não correspondem ao interesse do usuário misturados aos resultados significativos encontrados, pois em geral há uma descontinuidade semântica entre as características extraídas automaticamente e a subjetividade da interpretação humana. Com o intuito de tratar esse problema, diversos métodos foram propostos para a diminuição da descontinuidade semântica. O foco principal desta tese é o desenvolvimento de métodos escaláveis para a redução da descontinuidade semântica em sistemas recuperação de imagens por conteúdo em tempo real. Nesta sentido, são apresentados: a formalização de consultas por similaridade que permitem a utilização de múltiplos centros de consulta em espaços métricos como base para métodos de realimentação de relevância; um método exato para otimização dessas consultas nesses espaços; e um modelo para tratamento da diversidade em consultas por similaridade e heurísticas para sua otimização / The increasing number of images captured in digital media fostered the developmet of new methods for the recovery of these images. Dissimilarity is a criteria that can be used for image retrieval, where the results are images that are similar to a given reference. The queries are based on feature vectors automatically extracted from the images and on distance functions to measure the dissimilarity between pair of vectors. Unfortunately, the search for images in simple queries may result in images that do not fulfill the user interest together with meaningful images, due to the semantic gap between the image features and to the subjectivity of the human interpretation. This problem leaded to the development of many methods to deal with the semantic gap. The focus of this thesis is the development of scalable methods aiming the semantic gap reduction in real time for content-based image retrieval systems. For this purpose, we present the formal definition of similarity queries based on multiple query centers in metric spaces to be used in relevance feedback methods, an exact method to optimize these queries and a model to deal with diversity in nearest neighbor queries including heuristics for its optimization

Com o crescente aumento no número de imagens geradas em mídias digitais surgiu a necessidade do desenvolvimento de novas técnicas de recuperação desses dados. Um critério de busca que pode ser utilizado na recuperação das imagens é o da dissimilaridade, no qual o usuário deseja recuperar as imagens semelhantes à uma imagem de consulta. Para a realização das consultas são empregados vetores de características extraídos das imagens e funções de distância para medir a dissimilaridade entre pares desses vetores. Infelizmente, a busca por conteúdo de imagens em consultas simples tende a gerar resultados que não correspondem ao interesse do usuário misturados aos resultados significativos encontrados, pois em geral há uma descontinuidade semântica entre as características extraídas automaticamente e a subjetividade da interpretação humana. Com o intuito de tratar esse problema, diversos métodos foram propostos para a diminuição da descontinuidade semântica. O foco principal desta tese é o desenvolvimento de métodos escaláveis para a redução da descontinuidade semântica em sistemas recuperação de imagens por conteúdo em tempo real. Nesta sentido, são apresentados: a formalização de consultas por similaridade que permitem a utilização de múltiplos centros de consulta em espaços métricos como base para métodos de realimentação de relevância; um método exato para otimização dessas consultas nesses espaços; e um modelo para tratamento da diversidade em consultas por similaridade e heurísticas para sua otimização / The increasing number of images captured in digital media fostered the developmet of new methods for the recovery of these images. Dissimilarity is a criteria that can be used for image retrieval, where the results are images that are similar to a given reference. The queries are based on feature vectors automatically extracted from the images and on distance functions to measure the dissimilarity between pair of vectors. Unfortunately, the search for images in simple queries may result in images that do not fulfill the user interest together with meaningful images, due to the semantic gap between the image features and to the subjectivity of the human interpretation. This problem leaded to the development of many methods to deal with the semantic gap. The focus of this thesis is the development of scalable methods aiming the semantic gap reduction in real time for content-based image retrieval systems. For this purpose, we present the formal definition of similarity queries based on multiple query centers in metric spaces to be used in relevance feedback methods, an exact method to optimize these queries and a model to deal with diversity in nearest neighbor queries including heuristics for its optimization