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.

CoordenaÃÃo de AperfeiÃoamento de Pessoal de NÃvel Superior / 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. / 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.