CoordenaÃÃo de AperfeiÃoamento de Pessoal de NÃvel Superior / ComputaÃÃo em Nuvem ou Cloud Computing à um paradigma promissor de computaÃÃo orientada a serviÃos. O seu maior benefÃcio à a elasticidade, isto Ã, a capacidade do sistema de adicionar e remover recursos automaticamente em tempo de execuÃÃo. Para isso, à essencial projetar e implementar uma tÃcnica efetiva e eficiente que tire proveito da flexibilidade do sistema. Dessa forma, prover elasticidade requer monitorar continuamente (ou prever) a demanda do sistema por recursos, com objetivo de decidir quando adicionÃ-los e removÃ-los. Este trabalho apresenta um mÃtodo de monitoramento nÃo-intrusivo e contÃnuo de SGBDs relacionais em uma infraestrutura de nuvem, visando minimizar a quantidade de mÃquinas virtuais provisionadas para o processamento de consultas, e consequentemente maximizar o uso eficiente do ambiente do provedor. AlÃm disso, ele visa satisfazer um "acordo de nÃvel de serviÃo", em inglÃs service-level agrement (SLA), associado a cada consulta submetida ao sistema. Dessa forma, um objetivo desse trabalho tambÃm à minimizar a penalidade paga pelo provedor para os casos em que ocorre a violaÃÃo do SLA. AlÃm do mÃtodo de monitoramento, este trabalho tambÃm apresenta um mÃtodo de provisionamento de MVs para o processamento da consulta como contribuiÃÃes. Nossa estratÃgia de monitoramento à aplicada a consultas select-range e consultas com agregaÃÃo sobre uma Ãnica tabela. Os experimentos foram realizados na infraestrutura de nuvem da Amazon, confirmando que nossa tÃcnica à elÃstica, permitindo ajustar os recursos alocados no sistema de forma automÃtica e dinÃmica, com base no SLA acordado.

[pt] Na abordagem tradicional para execução de consultas em um ambiente de integração de dados, os dados provenientes de fontes heterogêneas são convertidos para o modelo de dados global do sistema integrador, através do uso de adaptadores (wrappers), antes de serem submetidos aos operadores algébricos de uma consulta. Como conseqüência disto, planos de execução de consultas (PECs) contêm operadores que processam dados representados apenas no modelo de dados global. Esta dissertação apresenta uma nova abordagem para a execução de consultas de integração, denominada Moving Wrappers, na qual a conversão entre os modelos de dados acontece durante o processamento, em qualquer ponto do PEC, permitindo que os operadores processem dados representados no modelo de dados original de suas fontes. Baseada nesta abordagem, foi desenvolvida uma máquina de execução de consultas (MEC) que executa PECs de integração de dados de fontes Relacionais e XML, combinando, em um mesmo PEC, operadores em ambos os modelos. Esta MEC, denominada RXQEE (Relational-XML Query Execution Engine), foi instanciada a partir do framework QEEF (Query Execution Engine Framework), desenvolvido em um projeto de pesquisa do laboratório TecBD da PUC-Rio. De modo a permitir a execução de PECs de integração, a MEC RXQEE implementa operadores algébricos, nos modelos XML e Relacional, e operadores interalgébricos, desenvolvidos para a realizar a conversão entre esses modelos de dados na MEC construída. / [en] In the traditional approach for the evaluation of data integration queries, heterogeneous data in data sources are converted into the global data model by wrappers before being delivered to algebraic operators. Consequently, query execution plans (QEPs) are composed exclusively by operations in accordance to the global data model. This work proposes a new data integration query evaluation strategy, named Moving Wrappers, in which data conversion is considered as an operation placed in any part of the QEP, based on a query optimization process. This permits the use of algebraic operators of the data sourceís data model. So, a QEP may include fragments with operations in different data models converted to the global data model by inter-algebraic operators. Based on this strategy, a query execution engine (QEE), named RXQEE (Relational-XML Query Execution Engine), was developed as an instance of QEEF (Query Execution Engine Framework). In particular, RXQEE explores integration queries over Relational and XML data, and therefore it implements algebraic operators, in XML and Relational models, and inter-algebraic operators, permiting the execution of integration QEPs.

CRUZ, Lívia Almada. Consultas kNN em redes dependentes do tempo. 2013. 75 f. Dissertação (Mestrado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2013. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-07-11T18:24:05Z No. of bitstreams: 1 2013_dis_lacruz.pdf: 6954650 bytes, checksum: fbf7280f2f781976bae6e4474c2c16c6 (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-07-20T11:52:58Z (GMT) No. of bitstreams: 1 2013_dis_lacruz.pdf: 6954650 bytes, checksum: fbf7280f2f781976bae6e4474c2c16c6 (MD5) / Made available in DSpace on 2016-07-20T11:52:58Z (GMT). No. of bitstreams: 1 2013_dis_lacruz.pdf: 6954650 bytes, checksum: fbf7280f2f781976bae6e4474c2c16c6 (MD5) Previous issue date: 2013 / In this dissertation we study the problem of processing k-nearest neighbours (kNN)queries in road networks considering the history of traffic conditions, in particular the case where the speed of moving objects is time-dependent. For instance, given that the user is at a given location at a certain time, the query returns the k points of interest (e.g., gas stations) that can be reached in the minimum amount of time. Previous solutions to answer kNN queries and others common queries in road networks do not work when the moving speed in each road is not constant. Building efficient and correct approaches and algorithms and storage and access schemes for processing these queries is a challenge because graph properties considered in static networks do not hold in the time dependent case. Our approach uses the well-known A∗ search algorithm by applying incremental network expansion and pruning unpromising vertices. The goal is reduce the percentage of network assessed in the search. To support the algorithm execution, we propose a storage and access method for time-dependent networks. We discuss the design and correctness of our algorithm and present experimental results that show the efficiency and effectiveness of our solution. / Nesta dissertação foi estudado o problema de processar consultas kNN em redes de rodovias considerando o histórico das condições de tráfego, em particular o caso onde a velocidade dos objetos móveis depende do tempo. Dado que um usuário está em uma dada localização e em um determinado instante de tempo, a consulta retorna os k pontos de interesse (por exemplo, postos de gasolina) que podem ser alcançados em uma quantidade de tempo mínima considerando condições históricas de tráfego. Soluções anteriores para consultas kNN e outras consultas comuns em redes de rodovia estáticas não funcionam quando o custo das arestas (tempo de viagem) é dependente do tempo. A construção de estratégias e algoritmos eficientes e corretos, e métodos de armazenamento e acesso para o processamento destas consultas é um desafio desde que algumas das propriedades de grafos comumente supostas em estratégias para redes estáticas não se mantêm para redes dependentes do tempo. O método proposto aplica uma busca A∗ à medida que vai, de maneira incremental, explorando a rede. O objetivo do método é reduzir o percentual da rede avaliado na busca. Para dar suporte à execução do algoritmo, foi também proposto um método para armazenamento e acesso para redes dependentes do tempo. A construção e a corretude do algoritmo são discutidas e são apresentados resultados experimentais com dados reais e sintéticos que mostram a eficiência da solução.

SILVA, Ticiana Linhares Coelho da. Processamento elástico e não-intrusivo de consultas em ambientes de nuvem considerando o SLA. 2013. 54 f. Dissertação (Mestrado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2013. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-07-12T18:22:53Z No. of bitstreams: 1 2013_dis_tlcsilva.pdf: 1298584 bytes, checksum: 63992b01ae2b16152aa961224cc5edfb (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-07-22T12:41:07Z (GMT) No. of bitstreams: 1 2013_dis_tlcsilva.pdf: 1298584 bytes, checksum: 63992b01ae2b16152aa961224cc5edfb (MD5) / Made available in DSpace on 2016-07-22T12:41:07Z (GMT). No. of bitstreams: 1 2013_dis_tlcsilva.pdf: 1298584 bytes, checksum: 63992b01ae2b16152aa961224cc5edfb (MD5) Previous issue date: 2013 / Computação em Nuvem ou Cloud Computing é um paradigma promissor de computação orientada a serviços. O seu maior benefício é a elasticidade, isto é, a capacidade do sistema de adicionar e remover recursos automaticamente em tempo de execução. Para isso, é essencial projetar e implementar uma técnica efetiva e eficiente que tire proveito da flexibilidade do sistema. Dessa forma, prover elasticidade requer monitorar continuamente (ou prever) a demanda do sistema por recursos, com objetivo de decidir quando adicioná-los e removê-los. Este trabalho apresenta um método de monitoramento não-intrusivo e contínuo de SGBDs relacionais em uma infraestrutura de nuvem, visando minimizar a quantidade de máquinas virtuais provisionadas para o processamento de consultas, e consequentemente maximizar o uso eficiente do ambiente do provedor. Além disso, ele visa satisfazer um "acordo de nível de serviço", em inglês service-level agrement (SLA), associado a cada consulta submetida ao sistema. Dessa forma, um objetivo desse trabalho também é minimizar a penalidade paga pelo provedor para os casos em que ocorre a violação do SLA. Além do método de monitoramento, este trabalho também apresenta um método de provisionamento de MVs para o processamento da consulta como contribuições. Nossa estratégia de monitoramento é aplicada a consultas select-range e consultas com agregação sobre uma única tabela. Os experimentos foram realizados na infraestrutura de nuvem da Amazon, confirmando que nossa técnica é elástica, permitindo ajustar os recursos alocados no sistema de forma automática e dinâmica, com base no SLA acordado.

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 em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2014. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-07-28T19:27:19Z No. of bitstreams: 1 2014_dis_cfcosta.pdf: 2126584 bytes, checksum: a2635ed2f82226579173a9e49d960c00 (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-08-01T15:43:28Z (GMT) No. of bitstreams: 1 2014_dis_cfcosta.pdf: 2126584 bytes, checksum: a2635ed2f82226579173a9e49d960c00 (MD5) / Made available in DSpace on 2016-08-01T15:43:28Z (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.

CHUCRE, Mirla Rafaela Rafael Braga. K-nearest neighbors queries in time-dependent road networks: analyzing scenarios where points of interest move to the query point. 2015. 65 f. Dissertação (Mestrado em Ciência da Computação)-Universidade Federal do Ceará, Fortaleza, 2015. / Submitted by Jonatas Martins (jonatasmartins@lia.ufc.br) on 2017-06-29T12:26:58Z No. of bitstreams: 1 2015_dis_mrrbchucre.pdf: 15845328 bytes, checksum: a2e4d0a03ca943372c92852d4bcf7236 (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2017-06-29T13:54:36Z (GMT) No. of bitstreams: 1 2015_dis_mrrbchucre.pdf: 15845328 bytes, checksum: a2e4d0a03ca943372c92852d4bcf7236 (MD5) / Made available in DSpace on 2017-06-29T13:54:36Z (GMT). No. of bitstreams: 1 2015_dis_mrrbchucre.pdf: 15845328 bytes, checksum: a2e4d0a03ca943372c92852d4bcf7236 (MD5) Previous issue date: 2015 / A kNN query retrieve the k points of interest that are closest to the query point, where proximity is computed from the query point to the points of interest. Time-dependent road networks are represented as weighted graphs, where the weight of an edge depends on the time one passes through that edge. This way, we can model periodic congestions during rush hour and similar effects. Travel time on road networks heavily depends on the traffic and, typically, the time a moving object takes to traverse a segment depends on departure time. In time-dependent networks, a kNN query, called TD-kNN, returns the k points of interest with minimum travel-time from the query point. As a more concrete example, consider the following scenario. Imagine a tourist in Paris who is interested to visit the touristic attraction closest from him/her. Let us consider two points of interest in the city, the Eiffel Tower and the Cathedral of Notre Dame. He/she asks a query asking for the touristic attraction whose the path leading up to it is the fastest at that time, the answer depends on the departure time. For example, at 10h it takes 10 minutes to go to the Cathedral. It is the nearest attraction. Although, if he/she asks the same query at 22h, in the same spatial point, the nearest attraction is the Eiffel Tower. In this work, we identify a variation of nearest neighbors queries in time-dependent road networks that has wide applications and requires novel algorithms for processing. Differently from TD-kNN queries, we aim at minimizing the travel time from points of interest to the query point. With this approach, a cab company can find the nearest taxi in time to a passenger requesting transportation. More specifically, we address the following query: find the k points of interest (e.g. taxi drivers) which can move to the query point (e.g. a taxi user) in the minimum amount of time. Previous works have proposed solutions to answer kNN queries considering the time dependency of the network but not computing the proximity from the points of interest to the query point. We propose and discuss a solution 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 discuss the design and correctness of our algorithm and present experimental results that show the efficiency and effectiveness of our solution. / Uma consulta de vizinhos mais próximos (ou kNN, do inglês k nearest neighbours) recupera o conjunto de k pontos de interesse que são mais próximos a um ponto de consulta, onde a proximidade é computada do ponto de consulta para cada ponto de interesse. Nas redes de rodovias tradicionais (estáticas) o custo de deslocamento de um ponto a outro é dado pela distância física entre esses dois pontos. Por outro lado, nas redes dependentes do tempo o custo de deslocamento (ou seja, o tempo de viagem) entre dois pontos varia de acordo com o instante de partida. Nessas redes, as consultas kNN são denominadas TD-kNN (do inglês Time-Dependent kNN). As redes de rodovias dependentes do tempo representam de forma mais adequada algumas situações reais, como, por exemplo, o deslocamento em grandes centros urbanos, onde o tempo para se deslocar de um ponto a outro 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. Neste contexto, uma consulta típica consiste em descobrir os k restaurantes (pontos de interesse) mais próximos de um determinado cliente (ponto de consulta) caso este inicie o seu deslocamento ao meio dia. Nesta dissertação nós estudamos o problema de processar uma variação de consulta de vizinhos mais próximos em redes viárias dependentes do tempo. Diferentemente das consultas TD-kNN, onde a proximidade é calculada do ponto de consulta para um determinado ponto de interesse, estamos interessados em situações onde a proximidade deve ser calculada de um ponto de interesse para o ponto de consulta. Neste caso, uma consulta típica consiste em descobrir os k taxistas (pontos de interesse) mais próximos (ou seja, com o menor tempo de viagem) de um determinado cliente (ponto de consulta) caso eles iniciem o seu deslocamento até o referido cliente ao meio dia. Desta forma, nos cenários investigados nesta dissertação, são os pontos de interesse que se deslocam até o ponto de consulta, e não o contrário. O método proposto para executar este tipo de consulta aplica uma busca A∗ à medida que vai, de maneira incremental, explorando a rede. O objetivo do método é reduzir o percentual da rede avaliado na busca. A construção e a corretude do método são discutidas e são apresentados resultados experimentais com dados reais e sintéticos que mostram a eficiência da solução proposta.

COSTA, C. F. Nearest Neighbors with Operating Time Constraints and Optimal Sequenced Route Queries in Time-Dependent Road Networks. 2014. 75 f. Dissertação (Mestrado em Ciência da Computação) - Centro de Ciências, Universidade Federal do Ceará, Fortaleza, 2014. / Submitted by Daniel Eduardo Alencar da Silva (dealencar.silva@gmail.com) on 2015-01-23T20:05:38Z No. of bitstreams: 1 2014_dis_cfcosta.pdf: 2126584 bytes, checksum: a2635ed2f82226579173a9e49d960c00 (MD5) / Approved for entry into archive by Rocilda Sales(rocilda@ufc.br) on 2015-09-23T16:29:29Z (GMT) No. of bitstreams: 1 2014_dis_cfcosta.pdf: 2126584 bytes, checksum: a2635ed2f82226579173a9e49d960c00 (MD5) / Made available in DSpace on 2015-09-23T16:29:29Z (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.

Submitted by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2017-03-14T13:41:39Z No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Dissertação - Caio M. Daoud.pdf: 14164794 bytes, checksum: ad296e0b97a339ac0b0b30ff6da7e344 (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2017-03-14T13:41:58Z (GMT) No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Dissertação - Caio M. Daoud.pdf: 14164794 bytes, checksum: ad296e0b97a339ac0b0b30ff6da7e344 (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2017-03-14T13:42:20Z (GMT) No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Dissertação - Caio M. Daoud.pdf: 14164794 bytes, checksum: ad296e0b97a339ac0b0b30ff6da7e344 (MD5) / Made available in DSpace on 2017-03-14T13:42:20Z (GMT). No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Dissertação - Caio M. Daoud.pdf: 14164794 bytes, checksum: ad296e0b97a339ac0b0b30ff6da7e344 (MD5) Previous issue date: 2016-12-02 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Search systems have been one of the main forms of locating and retrieving information in digital environments in recent decades. They are present in a large number of applications, such as web search engines and e-commerce systems. Users of these systems more often than not have very specific information needs, only being satisfied with a few, highly relevant results. Due to this behavior, part of the recent research effort related to search systems aims to reduce computational costs to compute the top results of queries, which are the ones usually presented to most users. In this thesis, we study the problem of computing the top k results of a ranking in search engines. We present two novel document-at-a-time algorithms for fast computing of top-k query results in search systems, named as Block Max WAND with Candidate Selection and Preserving Top-K Results (BMW-CSP) and Waves. Both algorithms use multi-tier indexes for reducing the computational time required for processing queries. BMW-CSP is an extension of BMW-CS, a method previously proposed in the literature. Although very efficient, BMW-CS does not guarantee the preservation of the top-k results for a given query. Algorithms that do not preserve the top results may reduce the quality of ranking results in search systems. BMW-CSP extends BMW-CS to ensure that the top-k results will have their rankings preserved. In the experiments we performed for computing the top-10 results, the final average time required for processing queries with BMW-CSP was lesser than the ones required by the baselines adopted. As with BMWCS, the price paid by BMW-CSP, when compared to other document-at-a-time methods, is extra memory required to store partial scores of documents. Further studying the problem of query processing, we then proposed Waves. It performs successive tentative evaluations of results which we call waves. Each wave traverses the index, starting from a specific tier level i. Each wave i may insert only those documents that occur in that tier level into the answer. After processing a wave, the alv gorithm checks whether the answer achieved might be changed by successive waves or not. A new wave is started only if it has a chance of changing the top-k scores. We show through experiments that such lazy query processing strategy results in smaller query processing times when compared to previous approaches proposed in the literature. When compared to BMW-CSP, Waves presents the advantage of not requiring extra memory to store partial scores. We present experiments to compare the performance of Waves to BMW-CSP and to other state-of-the-art document-at-a-time query processing methods that preserve top-k results. These experiments indicate that the method can be an effective alternative algorithm for computing top-k results. / Trabalhos na literatura propõem diferentes técnicas para processamento de consultas em sistemas de busca. Esses sistemas são capazes de buscar informação relevante dentro de grandes coleções de dados e estão entre as principais formas de se obter informações na Internet. A popularização desses sistemas, associada ao crescimento constante de dispositivos eletrônicos para armazenamento e produção de informação, impulsionam pesquisas não apenas em relação à qualidade da resposta final fornecida aos usuários mas também com relação à redução no tempo de processamento de consultas. O foco principal deste trabalho é o desenvolvimento de soluções que reduzam o tempo de processamento de consultas sem afetar a qualidade de respostas fornecidas por sistemas de busca. Como usuários tipicamente estão interessado apenas em um determinado número de respostas do topo do ranking, estudamos o cenário mais comum onde busca-se computar rapidamente apenas os k documentos de maior escore dentre os que atendem às consultas dos usuários. São propostos, implementados e avaliados dois novos métodos de processamento de consultas, o método Block Max WAND with Candidate Selection and Preserving Top- K Results (BMW-CSP) e o método Waves. Os dois métodos utilizam uma abordagem documento-a-documento e índices em multi-camadas como base para reduzir o tempo de processamento de consultas. O método BMW-CSP é uma extensão do método BMW-CS, um método proposto anteriormente na literatura. Apesar de muito eficiente, o BMW-CS apresenta a desvantagem de não garantir a corretude dos resultados do topo das respostas em sistemas de busca por poder descartar documentos que estariam originalmente entre as melhores respostas. O métodoBMW-CSP modifica oBMW-CS para resolver o problema, tornando-se um método que calcula corretamente o escore de todos os documentos. Tanto o método BMW-CS quanto o BMW-CSP apresentam como desvantagem a necessidade de utilizar memória extra para armazenar resultados parciais obtidos pelos métodos durante o processamento de consultas. Estudando mais a fundo o problema, propôs-se aqui um novo algoritmo que não requer tal expaço extra de armazenamento, o algoritmo Waves. O métodoWaves realiza passadas sucessivas pelas diversas camadas dos índices. Cada passagem foi denominada aqui de wave (onda em inglês), o que deu origem ao nome do método. Cada passagem sobre o índice é numerada e dada uma i-ésima passagem, ela processa o índice apenas da i-ésima camada em diante. Após cada passagem, o algoritmo faz uma verificação para saber se já se pode garantir que os k maiores escores de documentos já foram computados corretamente. Se houver garantia, o algoritmo para o processamento. Do contrário, o algoritmo executa uma nova passagem no índice até que o resultado correto seja matematicamente garantido. Os experimentos realizados com diferentes bases e cenários indicam que os dois novos métodos podem processar consultas até duas vezes mais rápido que os principais métodos propostos anteriormente na literatura.

Um data warehouse geográco (DWG) é um banco de dados multidimensional, orientado a assunto, integrado, histórico, não-volátil e geralmente organizado em níveis de agregação. Além disso, também armazena dados espaciais em uma ou mais dimensões ou em pelo menos uma medida numérica. Visando oferecer suporte à tomada de decisão, é possível realizar em DWGs consultas SOLAP (spatial online analytical processing ), isto é, consultas analíticas multidimensionais (e.g., drill-down, roll-up, drill-across ) com predicados espaciais (e.g., intersecta, contém, está contido) denidos para range queries e junções espaciais. Um desafio no processamento dessas consultas é recuperar, de forma eficiente, dados espaciais e convencionais em DWGs muito volumosos. Na literatura, existem poucos índices voltados à indexação de DWGs, e ainda assim nenhum desses índices dedica-se a indexar consultas SOLAP drill-across e com junção espacial. Esta dissertação visa suprir essa limitação, por meio da proposta de estratégias para o processamento dessas consultas complexas. Para o processamento de consultas SOLAP drill-across foram propostas duas estratégias, Divide e Única, além da especicação de um conjunto de diretrizes que deve ser seguido para o projeto de um esquema de DWG que possibilite a execução dessas consultas e da especicação de classes de consultas. Para o processamento de consultas SOLAP com junção espacial foi proposta a estratégia SJB, além da identicação de quais características o esquema de DWG deve possuir para possibilitar a execução dessas consultas e da especicação do formato dessas consultas. A validação das estratégias propostas foi realizada por meio de testes de desempenho considerando diferentes congurações, sendo que os resultados obtidos foram contrastados com a execução de consultas do tipo junção estrela e o uso de visões materializadas. Os resultados mostraram que as estratégias propostas são muito eficientes. No processamento de consultas SOLAP drill-across, as estratégias Divide e Única mostraram uma redução no tempo de 82,7% a 98,6% com relação à junção estrela e ao uso de visões materializadas. No processamento de consultas SOLAP com junção espacial, a estratégia SJB garantiu uma melhora de desempenho na grande maioria das consultas executadas. Para essas consultas, o ganho de desempenho variou de 0,3% até 99,2% / A geographic data warehouse (GDW) is a special kind of multidimensional database. It is subject-oriented, integrated, historical, non-volatile and usually organized in levels of aggregation. Furthermore, a GDW also stores spatial data in one or more dimensions or at least in one numerical measure. Aiming at decision support, GDWs allow SOLAP (spatial online analytical processing) queries, i.e., multidimensional analytical queries (e.g., drill-down, roll-up, drill-across) extended with spatial predicates (e.g., intersects, contains, is contained) dened for range and spatial join queries. A challenging issue related to the processing of these complex queries is how to recover spatial and conventional data stored in huge GDWs eciently. In the literature, there are few access methods dedicated to index GDWs, and none of these methods focus on drill-across and spatial join SOLAP queries. In this master\'s thesis, we propose novel strategies for processing these complex queries. We introduce two strategies for processing SOLAP drill-across queries (namely, Divide and Unique), dene a set of guidelines for the design of a GDW schema that enables the execution of these queries, and determine a set of classes of these queries to be issued over a GDW schema that follows the proposed guidelines. As for the processing of spatial join SOLAP queries, we propose the SJB strategy, and also identify the characteristics of a DWG schema that enables the execution of these queries as well as dene the format of these queries. We validated the proposed strategies through performance tests that compared them with the star join computation and the use of materialized views. The obtained results showed that our strategies are very ecient. Regarding the SOLAP drill-across queries, the Divide and Unique strategies showed a time reduction that ranged from 82,7% to 98,6% with respect to star join computation and the use of materialized views. Regarding the SOLAP spatial join queries, the SJB strategy guaranteed best results for most of the analyzed queries. For these queries, the performance gain of the SJB strategy ranged from 0,3% to 99,2% over the star join computation and the use of materialized view

Submitted by Geyciane Santos (geyciane_thamires@hotmail.com) on 2015-06-17T14:33:52Z No. of bitstreams: 1 Dissertação - Cristian Rossi.pdf: 662641 bytes, checksum: 1f075c90b91e26f1afdb51e139918633 (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2015-06-17T20:40:09Z (GMT) No. of bitstreams: 1 Dissertação - Cristian Rossi.pdf: 662641 bytes, checksum: 1f075c90b91e26f1afdb51e139918633 (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2015-06-17T20:42:11Z (GMT) No. of bitstreams: 1 Dissertação - Cristian Rossi.pdf: 662641 bytes, checksum: 1f075c90b91e26f1afdb51e139918633 (MD5) / Made available in DSpace on 2015-06-17T20:42:11Z (GMT). No. of bitstreams: 1 Dissertação - Cristian Rossi.pdf: 662641 bytes, checksum: 1f075c90b91e26f1afdb51e139918633 (MD5) Previous issue date: 2013-03-27 / FAPEAM - Fundação de Amparo à Pesquisa do Estado do Amazonas / Search engines are mechanisms to seek relevant information within large data collections. The constant growth of electronic media for storage information, along with the popularization of search engines, brings the constant need for solutions that reduce processing costs queries. We present two new algorithms for query processing searching systems. The processing algorithms use the approach document-to-document and modify the current algorithm state of the art, BMW, for taking advantage of an index architecture divided into two layers. The first layer contains only the highest impact index entries and is used to preprocess consultations before accessing the rest of the index in the second layer. This approach results in significant performance gains. The first algorithm, called BMW-CS, is up to 40 times more fast compared to many compared methods, but causes small changes in the returned response. The second algorithm, called BMW-t, preserves the answer set and is 10% faster than the BMW. / Sistemas de busca são mecanismos capazes de buscar informação relevante dentro de grandes coleções de dados. O constante crescimento de meios eletrônicos para armazenamento de informação, junto com a popularização dos sistemas de busca, traz consigo a necessidade constante por soluções capazes de reduzir os custos de processamento de consultas. Neste trabalho, apresentamos dois novos algoritmos para processamento de consultas em sistemas de busca. Os algoritmos utilizam a abordagem de processamento documento-a-documento e modificam o atual algoritmo estado-da-arte, BMW, para tirar vantagem de uma arquitetura de índice dividido em duas camadas. A primeira camada contém apenas as entradas de maior impacto do índice e é utilizada para preprocessar as consultas antes de acessar o restante do índice na segunda camada. Esta abordagem resulta em consideráveis ganhos de desempenho. O primeiro algoritmo proposto, chamado BMW-CS, chega a ser 40 vezes mais rápido em relação a diversos métodos comparados, porém provoca pequenas modificações no conjunto de resposta retornado. O segundo algoritmo proposto, chamado BMW-t, preserva o conjunto de resposta e é 10% mais rápido que o BMW.