abstract: The spatial databases are used to store geometric objects such as points, lines, polygons. Querying such complex spatial objects becomes a challenging task. Index structures are used to improve the lookup performance of the stored objects in the databases, but traditional index structures cannot perform well in case of spatial databases. A significant amount of research is made to ingest, index and query the spatial objects based on different types of spatial queries, such as range, nearest neighbor, and join queries. Compressed Spatial Bitmap Index (cSHB) structure is one such example of indexing and querying approach that supports spatial range query workloads (set of queries). cSHB indexes and many other approaches lack parallel computation. The massive amount of spatial data requires a lot of computation and traditional methods are insufficient to address these issues. Other existing parallel processing approaches lack in load-balancing of parallel tasks which leads to resource overloading bottlenecks. In this thesis, I propose novel spatial partitioning techniques, Max Containment Clustering and Max Containment Clustering with Separation, to create load-balanced partitions of a range query workload. Each partition takes a similar amount of time to process the spatial queries and reduces the response latency by minimizing the disk access cost and optimizing the bitmap operations. The partitions created are processed in parallel using cSHB indexes. The proposed techniques utilize the block-based organization of bitmaps in the cSHB index and improve the performance of the cSHB index for processing a range query workload. / Dissertation/Thesis / Masters Thesis Computer Science 2018

With the large number of spatial queries for spatial data objects changing with time in many applications, e.g., the location based services and geographic information systems, spatio-temporal databases have been developed to manipulate them in spatial or temporal databases. We focus on queries for stationary and moving objects in the spatial database in the present. However, there is no total ordering for the large volume and complicated objects which may change their geometries with time. A spatial access method based on the spatial index structure attempts to preserve the spatial proximity as much as possible. Then, the number of disk access which takes the response time is reduced during the query processing. Therefore, in this dissertation, based on the NA-tree, first, we propose the NA-tree join method over the stationary objects. Our NA-tree join simply uses the correlation table to directly obtain candidate leaf nodes based on two NA-trees which have non-empty overlaps. Moreover, our NA-tree join accesses objects once from those candidate leaf nodes and returns pairs of objects which have non-empty overlaps. Second, we propose the NABP method for the continuous range queries over the moving objects. Our NABP method uses the bit-patterns of regions in the NA-tree to check the relation between the range queries and moving objects. Our NABP method searches only one path in the NA-tree for the range query, instead of more than one path in the R*-tree-based method which has the overlapping problem. When the number of range queries increases with time, our NABP method incrementally updates the affected range queries by bit-patterns checking, instead of rebuilding the index like the cell-based method. From the experimental results, we have shown that our NABP method needs less time than the cell-based method for range queries update and less time than the R*-tree-based method for moving objects update. Based on the Hilbert curve with the good clustering property, we propose the ANHC method to answer the all-nearest-neighbors query by our ONHC method. Our ONHC method is used to answer the one-nearest-neighbor query over the stationary objects. We generate direction sequences to store the orientations of the query block in the Hilbert curve of different orders. By using quaternary numbers and direction sequences of the query block, we obtain the relative locations of the neighboring blocks and compute their quaternary numbers. Then, we directly access the neighboring blocks by their sequence numbers which is the transformation of the quaternary numbers from base four to ten. The nearest neighbor can be obtained by distance comparisons in these blocks. From the experimental results, we have shown that our ONHC and ANHC methods need less time than CCSF method for the one-nearest-neighbor query and the method based on R*-trees for the all-nearest-neighbors query, respectively.

The presence of millions of interconnected personal computing devices has given rise to a new class of decentralized networking applications, which are loosely labeled as peer-to-peer (P2P) applications. These P2P applications leverage resources such as processing cycles, storage, content, and network bandwidth available to the user devices, which are also known as peers. A number of current systems - SETI@home, Napster, BitTorrent, and Pastry - are examples of these emerging P2P systems. To fully realize the potential of the peer-to-peer technology, there is a need to define and provide a set of core competencies, serving as the basic services upon which various peer-to-peer applications can be built on. Among these core competencies, this dissertation focuses on two fundamental services, which are search and delivery. In the first part of the dissertation, delivery techniques to support video-on-demand services in wireline and wireless P2P networks are investigated. Video services are considered due to two reasons. First, video services are the pivotal basis for many other multimedia applications. Second, it is challenging to provide on-demand video services due to asynchronous playback progresses at peers. The proposed techniques enable efficient video sharing between peers with asynchronous playback progresses, and maximize peer bandwidth utilization. In the second part of the dissertation, the problem of supporting continuous moving range queries in wireless mobile peer-to-peer networks is studied. Continuous moving range queries have a number of applications when a moving object wants to monitor its surrounding environment for a period of time. When a fixed network infrastructure is not available, wireless mobile peer-to-peer networks become a viable option to support the continuous query system. The proposed distributed solution ensures the accuracy of the query results under realistic assumptions, and incurs much less overhead than alternative solutions.

COSTA, Camila Ferreira. Nearest Neighbors with Operating Time Constraints and Optimal Sequenced Route Queries in Time-Dependent Road Networks. 2014. 75 f. : Dissertação (mestrado) - Universidade Federal do Ceará, Centro de Ciências, Departamento de Computação, Fortaleza-CE, 2014. / Submitted by guaracy araujo (guaraa3355@gmail.com) on 2016-06-06T19:14:12Z No. of bitstreams: 1 2014_dis_cfcosta.pdf: 2126584 bytes, checksum: a2635ed2f82226579173a9e49d960c00 (MD5) / Approved for entry into archive by guaracy araujo (guaraa3355@gmail.com) on 2016-06-06T19:18:16Z (GMT) No. of bitstreams: 1 2014_dis_cfcosta.pdf: 2126584 bytes, checksum: a2635ed2f82226579173a9e49d960c00 (MD5) / Made available in DSpace on 2016-06-06T19:18:16Z (GMT). No. of bitstreams: 1 2014_dis_cfcosta.pdf: 2126584 bytes, checksum: a2635ed2f82226579173a9e49d960c00 (MD5) Previous issue date: 2014 / In this thesis we study the problems of processing a variation of nearest neighbors and of routing planning queries in time-dependent road networks, i.e., one where travel time along each edge is a function of the departure time. We first study the problem of finding the k points of interest (POIs), for example, museums or restaurants, in which a user can start to be served in the minimum amount of time, accounting for both the travel time to the POI and the waiting time there, if it is closed. Previous works have proposed solutions to answer k-nearest neighbor queries considering the time dependency of the network but not the operating times of the points of interest. We propose and discuss three solutions to this type of query which are based on the previously proposed incremental network expansion and use the A* search algorithm equipped with suitable heuristic functions. We also present experimental results comparing the number of disk access required in each solution with respect to a few different parameters. In the second query, we aim at finding the optimal route that connects a origin to a destination and passes through a number of POIs in a specific sequence imposed on the categories of the POIs. Previous works have addressed this problem, but they do not consider the time dependency of the network. We propose an optimal sequenced route query algorithm which performs an incremental network expansion adopting an A* search. Furthermore, as an OSR query on road network tends to re-expand an extremely large number of nodes, we propose a scheme to reduce the re-expansions. For comparison purposes, we also present a baseline solution which was obtained by extending the previously proposed progressive neighbor exploration algorithm to cope with the time-dependent problem. We performed experiments in synthetic networks comparing the proposed solutions according to the number of expanded vertices in the search and the processing time of the queries. / Nesta dissertação nós estudamos os problemas de processar uma variação de consulta de vizinhos mais próximos e de planejamento de rotas em redes viárias dependentes do tempo. Diferentemente de redes convencionais, onde o custo de deslocamento de um ponto a outro é geralmente dado pela distância física entre esses dois pontos, uma rede dependente do tempo representa de forma mais realista o custo de realizar esse deslocamento, considerando o histórico das condições de tráfego. Mais especificamente, o tempo que um objeto móvel leva para percorrer uma via em tal rede depende do tempo de partida. Por exemplo, o tempo para se deslocar de um ponto a outro em grandes centros durante os horários de pico, quando o tráfego é intenso e as ruas estão congestionadas, é muito maior do que em horários normais. Dentro do contexto apresentado, primeiramente nós estudamos o problema de encontrar k pontos de interesse, como por exemplo, museus ou restaurantes, nos quais um usuário pode começar a ser servido o mais rápido possível. Em outras palavras, nós buscamos minimizar a soma do tempo de viagem até um ponto de interesse mais o tempo de espera até que ele abra, caso esteja fechado. Trabalhos anteriores tratam do problema de encontrar os k vizinhos mais próximos em redes dependentes do tempo, porém, eles não levam em consideração o horário de funcionamento dos pontos de interesse. Desta forma, a consulta abordada nesses trabalhos pode retornar pontos de interesse que estão mais próximos do usuário, considerando um dado tempo de partida, mas que podem demorar para abrir, fazendo com que o usuário espere por muito tempo. Nós propomos e discutimos três soluções para essa consulta que são baseadas em um algoritmo de expansão incremental da rede previamente proposto na literatura e usam o algoritmo de busca A* equipado com funções heurísticas adequadas para cada solução. Com o uso do algoritmo A*, nós visamos reduzir o percentual da rede avaliado na busca, evitando expandir vértices que oferecem uma baixa probabilidade de alcançar nosso objetivo. Também apresentamos resultados experimentais que comparam o número de acessos ao disco exigido em cada solução em relação a alguns parâmetros diferentes e que indicam em que casos deve-se optar por cada solução. Na segunda consulta, nós visamos encontrar a rota ótima que conecta uma dada origem a um dado destino e que passa por uma série de pontos de interesse pertencentes a categorias determinadas pelo usuário em uma certa ordem também especificada pelo usuário. Esse tipo de consulta é conhecida como OSR, do inglês, Optimal Sequenced Route, na literatura. Como exemplo, considere que alguém está indo do trabalho para casa e no seu caminho deseja passar em um banco para sacar dinheiro e depois ir a um restaurante para jantar. Embora existam vários bancos e restaurantes em uma cidade, uma consulta OSR deve procurar pelo banco e pelo restaurante que minimizam o custo da viagem do trabalho para casa. Trabalhos anteriores propuseram soluções para consultas OSR em redes com arestas de custo fixo, mas nenhum deles considerou que esse custo pode variar de acordo com o tempo de partida. Nós propomos uma solução ótima para esse problema que, assim como as abordagens propostas para o problema anterior, expande a rede incrementalmente e usa o algoritmo A* para guiar essa expansão. Além disso, como uma consulta OSR em redes viárias tende a re-expandir um número muito grande de vértices, nós incorporamos à essa solução um esquema para reduzir o número de re-expansões. Nós também apresentamos resultados experimentais que mostram a eficiência dessa solução em comparação com uma solução de base que foi obtida a partir da estensão de um algoritmo anteriormente proposto na literatura. Todos os experimentos foram realizados em redes sintéticas.

CoordenaÃÃo de AperfeiÃoamento de Pessoal de NÃvel Superior / Nesta dissertaÃÃo nÃs estudamos os problemas de processar uma variaÃÃo de consulta de vizinhos mais prÃximos e de planejamento de rotas em redes viÃrias dependentes do tempo. Diferentemente de redes convencionais, onde o custo de deslocamento de um ponto a outro à geralmente dado pela distÃncia fÃsica entre esses dois pontos, uma rede dependente do tempo representa de forma mais realista o custo de realizar esse deslocamento, considerando o histÃrico das condiÃÃes de trÃfego. Mais especificamente, o tempo que um objeto mÃvel leva para percorrer uma via em tal rede depende do tempo de partida. Por exemplo, o tempo para se deslocar de um ponto a outro em grandes centros durante os horÃrios de pico, quando o trÃfego à intenso e as ruas estÃo congestionadas, à muito maior do que em horÃrios normais. Dentro do contexto apresentado, primeiramente nÃs estudamos o problema de encontrar k pontos de interesse, como por exemplo, museus ou restaurantes, nos quais um usuÃrio pode comeÃar a ser servido o mais rÃpido possÃvel. Em outras palavras, nÃs buscamos minimizar a soma do tempo de viagem atà um ponto de interesse mais o tempo de espera atà que ele abra, caso esteja fechado. Trabalhos anteriores tratam do problema de encontrar os k vizinhos mais prÃximos em redes dependentes do tempo, porÃm, eles nÃo levam em consideraÃÃo o horÃrio de funcionamento dos pontos de interesse. Desta forma, a consulta abordada nesses trabalhos pode retornar pontos de interesse que estÃo mais prÃximos do usuÃrio, considerando um dado tempo de partida, mas que podem demorar para abrir, fazendo com que o usuÃrio espere por muito tempo. NÃs propomos e discutimos trÃs soluÃÃes para essa consulta que sÃo baseadas em um algoritmo de expansÃo incremental da rede previamente proposto na literatura e usam o algoritmo de busca A* equipado com funÃÃes heurÃsticas adequadas para cada soluÃÃo. Com o uso do algoritmo A*, nÃs visamos reduzir o percentual da rede avaliado na busca, evitando expandir vÃrtices que oferecem uma baixa probabilidade de alcanÃar nosso objetivo. TambÃm apresentamos resultados experimentais que comparam o nÃmero de acessos ao disco exigido em cada soluÃÃo em relaÃÃo a alguns parÃmetros diferentes e que indicam em que casos deve-se optar por cada soluÃÃo. Na segunda consulta, nÃs visamos encontrar a rota Ãtima que conecta uma dada origem a um dado destino e que passa por uma sÃrie de pontos de interesse pertencentes a categorias determinadas pelo usuÃrio em uma certa ordem tambÃm especificada pelo usuÃrio. Esse tipo de consulta à conhecida como OSR, do inglÃs, Optimal Sequenced Route, na literatura. Como exemplo, considere que alguÃm està indo do trabalho para casa e no seu caminho deseja passar em um banco para sacar dinheiro e depois ir a um restaurante para jantar. Embora existam vÃrios bancos e restaurantes em uma cidade, uma consulta OSR deve procurar pelo banco e pelo restaurante que minimizam o custo da viagem do trabalho para casa. Trabalhos anteriores propuseram soluÃÃes para consultas OSR em redes com arestas de custo fixo, mas nenhum deles considerou que esse custo pode variar de acordo com o tempo de partida. NÃs propomos uma soluÃÃo Ãtima para esse problema que, assim como as abordagens propostas para o problema anterior, expande a rede incrementalmente e usa o algoritmo A* para guiar essa expansÃo. AlÃm disso, como uma consulta OSR em redes viÃrias tende a re-expandir um nÃmero muito grande de vÃrtices, nÃs incorporamos à essa soluÃÃo um esquema para reduzir o nÃmero de re-expansÃes. NÃs tambÃm apresentamos resultados experimentais que mostram a eficiÃncia dessa soluÃÃo em comparaÃÃo com uma soluÃÃo de base que foi obtida a partir da estensÃo de um algoritmo anteriormente proposto na literatura. Todos os experimentos foram realizados em redes sintÃticas. / In this thesis we study the problems of processing a variation of nearest neighbors and of routing planning queries in time-dependent road networks, i.e., one where travel time along each edge is a function of the departure time. We first study the problem of finding the k points of interest (POIs), for example, museums or restaurants, in which a user can start to be served in the minimum amount of time, accounting for both the travel time to the POI and the waiting time there, if it is closed. Previous works have proposed solutions to answer k-nearest neighbor queries considering the time dependency of the network but not the operating times of the points of interest. We propose and discuss three solutions to this type of query which are based on the previously proposed incremental network expansion and use the A* search algorithm equipped with suitable heuristic functions. We also present experimental results comparing the number of disk access required in each solution with respect to a few different parameters. In the second query, we aim at finding the optimal route that connects a origin to a destination and passes through a number of POIs in a specific sequence imposed on the categories of the POIs. Previous works have addressed this problem, but they do not consider the time dependency of the network. We propose an optimal sequenced route query algorithm which performs an incremental network expansion adopting an A* search. Furthermore, as an OSR query on road network tends to re-expand an extremely large number of nodes, we propose a scheme to reduce the re-expansions. For comparison purposes, we also present a baseline solution which was obtained by extending the previously proposed progressive neighbor exploration algorithm to cope with the time-dependent problem. We performed experiments in synthetic networks comparing the proposed solutions according to the number of expanded vertices in the search and the processing time of the queries.