Submitted by Lucelia Lucena (lucelia.lucena@ufpe.br) on 2015-03-05T19:44:25Z No. of bitstreams: 2 DISSERTAÇÃO Antonio Ezequiel de Mendonça.pdf: 2393951 bytes, checksum: 04f2793296259577c32a75f66eb859aa (MD5) license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) / Made available in DSpace on 2015-03-05T19:44:25Z (GMT). No. of bitstreams: 2 DISSERTAÇÃO Antonio Ezequiel de Mendonça.pdf: 2393951 bytes, checksum: 04f2793296259577c32a75f66eb859aa (MD5) license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) Previous issue date: 2014-08-21 / FACEPE / Usuários acessam aplicações de consulta a dados com a intenção de obter informações que lhes possam ser úteis. Para isso, eles submetem uma consulta e, dependendo da resposta, podem tentar refazê-la diversas vezes e, a cada nova consulta submetida, procuram filtrar os resultados, até que uma resposta satisfatória seja encontrada. Esse problema ocorre devido, principalmente, à grande quantidade de informação disponível e, até mesmo, devido à diferença de contexto existente para cada usuário. Entendemos por contexto o conjunto de elementos que caracterizam uma entidade de domínio e que são considerados relevantes em uma situação específica, durante um intervalo de tempo. Diante disso, temos que diferentes usuários podem receber informações diversas e considerá-las relevantes ou não para suas consultas, pois eles têm contextos e objetivos diferentes quando as realizam. Nesse sentido, um processo automático para reescrita de consultas pode criar uma consulta personalizada fazendo uso do contexto adquirido (por exemplo, do usuário e do ambiente) e, assim, as respostas retornadas tendem a ser mais adequadas. Para isso, a consulta pode ser reescrita usando técnicas de expansão, relaxamento ou formatação de respostas. Nesse panorama, o presente trabalho propõe a utilização de informações contextuais a fim de realizar a reescrita de consultas SQL submetidas pelos usuários. Para tanto, é apresentada a abordagem para reescrita de consultas denominada CORE - Context-based Rules for rEwriting queries, que proporciona a adequação da consulta original submetida pelo usuário de acordo com o contexto adquirido. O trabalho incluiu o desenvolvimento de um protótipo que implementa a abordagem. Este protótipo foi usado para realizar experimentos com usuários, os quais submeteram consultas que consideravam ou não o uso do contexto. Em outro experimento, foram aplicadas métricas de precisão e cobertura para avaliar a relevância da informação retornada pelas consultas com e sem o uso do contexto. Analisando os resultados dos experimentos, pôde-se observar que as consultas reescritas a partir do contexto obtiveram mais repostas consideradas relevantes do que as consultas sem contexto. O presente trabalho traz como diferencial de pesquisa em comparação com outros, o fato de tanto fazer uso de contexto como realizar inferência de novos elementos contextuais.

XAVIER, William Sheldon Maia. Efeitos de grupos na demanda por consultas odontológicas. 2012. 32f. Dissertação (mestrado profissional) - Programa de Pós Graduação em Economia, CAEN, Universidade Federal do Ceará, Fortaleza, CE, 2012. / Submitted by Mônica Correia Aquino (monicacorreiaaquino@gmail.com) on 2013-09-24T22:10:15Z No. of bitstreams: 1 2012_dissert_wsmxavier.pdf: 257797 bytes, checksum: 2d2d176e8390486a04835e248f3e8f99 (MD5) / Approved for entry into archive by Mônica Correia Aquino(monicacorreiaaquino@gmail.com) on 2013-09-24T22:10:55Z (GMT) No. of bitstreams: 1 2012_dissert_wsmxavier.pdf: 257797 bytes, checksum: 2d2d176e8390486a04835e248f3e8f99 (MD5) / Made available in DSpace on 2013-09-24T22:10:55Z (GMT). No. of bitstreams: 1 2012_dissert_wsmxavier.pdf: 257797 bytes, checksum: 2d2d176e8390486a04835e248f3e8f99 (MD5) Previous issue date: 2012 / The purpose of this study is to identify the existence of group effects, known as peer effects, at the demand for dental appointments in collective contracts that are exclusively dental health plans. This paper compares the number of dental appointments of each person with the amount of dental appointments in the group, despising the history appoint of the analyzed individual. In order to test empirically if the group effect is important, a model of traditional counting was used, with the introduction of the variable that indicates of group effect, particularly, the model of binomial negative counting for panel with random effects, embracing both the effect of over-dispersion and the time dependence of the use for the same person. The companies were divided into five groups according to their size, as follows: 2 to 20, 21 to 50, 51 to 100, 101 to 200 and more than 200 beneficiaries. The results showed that the group effects increased successively according to the size of the company, in which companies with more than 200 beneficiaries were the ones most affected. / O objetivo deste estudo é identificar a existência de efeitos de grupo, ou peer effect, na demanda por consultas odontológicas dentro de contratos coletivos de planos saúde exclusivamente odontológicos. O trabalho compara a quantidade de consultas odontológicas de cada indivíduo com a quantidade de consultas odontológicas do grupo, desconsiderando o histórico de consultas do indivíduo analisado. Para testar empiricamente se o efeito de grupo é importante, foram utilizados modelos de contagem tradicionais com a introdução da variável indicadora de efeito de grupo, em particular, o modelo de contagem binomial negativo para painel com efeito aleatório para acomodar tanto o efeito sobre-dispersão quanto à dependência temporal do uso para o mesmo indivíduo. As empresas foram divididas em 5 grupos de acordo com seu porte, sendo: 2 a 20, 21 a 50, 51 a 100, 101 a 200 e mais de 200 beneficiários. Os resultados mostraram que os efeitos de grupo aumentaram sucessivamente de acordo com o aumento do porte da empresa, sendo as empresas com mais de 200 beneficiários aquelas mais afetadas pelos efeitos de grupo.

Made available in DSpace on 2014-06-12T15:55:07Z (GMT). No. of bitstreams: 2 arquivo2130_1.pdf: 2467414 bytes, checksum: 13314da66987a6c25fe1d16d9d5ccfe3 (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2010 / Atualmente as corporações buscam ferramentas para suporte à decisão que contemplem a semântica do seu negócio (i.e., suas terminologias e regras). Neste contexto, OLAP (OnLine Analytical Processing) e ontologia, de forma isolada, têm se destacado, respectivamente, como ferramentas para subsidiar o processo de tomada de decisão e o processamento semântico de dados. De forma simplificada pode-se dizer que as ferramentas OLAP são voltadas para realizar cruzamentos (i.e., análise multidimensional - e.g., vendas de produtos por cliente, fornecedor e tempo) e agregações de dados em diferentes níveis de detalhe (i.e., análise multinível - e.g., vendas de produtos por ano, semestre, trimestre e mês). Por sua vez, uma ontologia pode ser resumidamente definida como uma representação não ambígua de um vocabulário e de regras para um determinado domínio de negócio, permitindo que raciocínios possam ser feitos a partir da ontologia. Apesar da boa aceitação destas ferramentas, estas foram concebidas para propósitos diferentes e, por isso, originalmente, não permitem a realização de análises multidimensionais, multiníveis e que considerem, de forma dinâmica e escalável, a semântica do negócio (e.g., vendas de produtos por clientes especiais, grandes fornecedores em dias de feriado santo ou comercial). Visando dar uma contribuição para solucionar o problema em questão, este trabalho define uma arquitetura de software que permite a integração de ferramentas OLAP com Ontologias, bem como um metamodelo que proporciona o mapeamento entre essas tecnologias a fim de permitir que a semântica do negócio possa ser utilizada em consultas analíticas. Como prova de conceito, foi utilizado um protótipo implementado em Java, que faz uso do servidor OLAP Mondrian, do seu cliente JPivot para exibir os resultados das consultas, de uma ontologia que estende a ontologia temporal OWL-Time e do raciocinador Jena

MAIA, M. S. ASBJOIN: uma estratégia adaptativa para consultas envolvendo operadores de junção em Linked data. 2013. 97 f. Dissertação (Mestrado em Ciência da Computação) - Centro de Ciências, Universidade Federal do Ceará, Fortaleza, 2013. / Submitted by Daniel Eduardo Alencar da Silva (dealencar.silva@gmail.com) on 2015-01-23T20:44:30Z No. of bitstreams: 1 2013_dis_msmaia.pdf: 2212047 bytes, checksum: 8fa549e690c4186b7f45d9eaa02e0029 (MD5) / Approved for entry into archive by Rocilda Sales(rocilda@ufc.br) on 2015-02-09T15:46:07Z (GMT) No. of bitstreams: 1 2013_dis_msmaia.pdf: 2212047 bytes, checksum: 8fa549e690c4186b7f45d9eaa02e0029 (MD5) / Made available in DSpace on 2015-02-09T15:46:07Z (GMT). No. of bitstreams: 1 2013_dis_msmaia.pdf: 2212047 bytes, checksum: 8fa549e690c4186b7f45d9eaa02e0029 (MD5) Previous issue date: 2013 / Motivated by the success of Linked Data and driven by the growing number of data sources into RDF files available on the web, new challenges for query processing are emerging, especially in distributed settings. These environments allow distributed execution of federated queries, which involve joining data provided by multiple sources, which are often unstable. In this sense, the design of new algorithms and adaptive strategies for efficiently implementing joins is a major challenge. In this paper, we present a solution to the adaptive joins execution in federated queries. The adaptative context of distributed data sources is based on statistics that are collected at runtime. For this, we use a module that updates the information in the catalog as the query is executed. The module works in parallel with the query processor. / Motivado pelo sucesso de Linked Data e impulsionado pelo crescimento do número de fontes de dados em formato RDF disponíveis na Web, novos desafios para processamento de consultas estão emergindo, especialmente em configurações distribuídas. No ambiente de Linked Data, é possível executar consultas federadas, as quais envolvem junções de dados fornecidos por múltiplas fontes. O termo consulta federada é usado quando queremos prover soluções baseadas em informações obtidas de diferentes fontes. Nesse sentido, a concepção de novos algoritmos e estratégias adaptativas para a execução de junções de forma eficiente constitui um desafio importante. Nesse trabalho, apresentamos uma solução para a execução adaptativa de operações de junções de dados em consultas federadas. A execução da operação de junção adaptativa entre informações contidas em fontes de dados distribuídas baseia-se em estatísticas, que são coletadas em tempo de execução. Uma informação estatística sobre uma determinada fontes seria, por exemplo, o tempo decorrido (Elapsed Time) para obter algum resultado. Para obter as informações estatísticas atualizadas, usamos uma estratégia que coleta essas informações durante a execução da consulta e,logo após, são armazenadas em uma base de dados local, na qual denominamos como catálogo de informações estatísticas.

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.

Submitted by Lucelia Lucena (lucelia.lucena@ufpe.br) on 2015-03-06T19:07:13Z No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) DISSERTAÇÃO Danusa Ribeiro Bezerra da Cunha.pdf: 5211208 bytes, checksum: c051cd99928c224160a77aa04d2ef53b (MD5) / Made available in DSpace on 2015-03-06T19:07:13Z (GMT). No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) DISSERTAÇÃO Danusa Ribeiro Bezerra da Cunha.pdf: 5211208 bytes, checksum: c051cd99928c224160a77aa04d2ef53b (MD5) Previous issue date: 2014-02-21 / CAPES / Um dos principais desafios a serem solucionados quando se deseja oferecer uma visão integrada de dados distribuídos em múltiplas fontes de dados diz respeito à decomposição de consultas. Em sistemas de integração de dados que fazem uso de um esquema de mediação, o problema de decomposição de consultas consiste em decompor uma consulta definida de acordo com o esquema de mediação em uma ou mais consultas a serem executadas nas fontes de dados locais. Um componente fundamental para a decomposição de consultas é o conjunto de mapeamentos entre o esquema de mediação e os esquemas das fontes de dados. Tendo em vista que os esquemas podem ser complexos e heterogêneos, um dos grandes problemas das soluções convencionais de integração de dados consiste em descobrir esses mapeamentos, pois este processo geralmente é feito de forma manual ou semiautomática, demandando um elevado custo durante a inicialização do sistema. Este trabalho aborda o problema de decomposição de consultas no contexto de integração de dados na Web de Dados, onde as fontes de dados seguem o modelo RDF (Resource Description Framework) e podem ser acessadas a partir de consultas SPARQL (SPARQL Protocol and RDF Query Language). Além disso, as fontes de dados podem estar associadas a uma ontologia que, em geral, desempenha o papel do esquema da fonte de dados. É importante destacar que, dada a natureza dinâmica e heterogênea do ambiente, não se deve esperar que uma estratégia de decomposição seja aplicada sobre toda a Web de Dados por questões de escalabilidade. Especificamente, neste trabalho propõe-se uma solução para o problema de decomposição de consultas em federações de conjuntos de dados interligados disponíveis na Web de Dados, ou seja, conjuntos de dados publicados de acordo com os princípios de Linked Data. Neste tipo de ambiente, se uma aplicação necessita consultar diferentes conjuntos de dados sem ter que formular uma nova consulta para cada um deles, pode ser necessário lidar com o problema de decomposição de consultas entre conjuntos de dados distintos e heterogêneos. Para solucionar tal problema, este trabalho propõe uma abordagem para decomposição de consultas em federações de dados interligados, a qual é dividida em três atividades principais. Dentre estas atividades, a principal contribuição reside na definição e implementação de um processo para decomposição de consultas, considerando que as fontes de dados possuem ontologias estruturalmente distintas que descrevem seus esquemas. Nesta abordagem, são manipuladas consultas SPARQL e são utilizados mapeamentos heterogêneos com o objetivo de tratar aspectos referentes às diferenças estruturais entre as ontologias. Para avaliar a abordagem proposta, um protótipo foi implementado e alguns experimentos foram realizados com fontes de dados que seguem os princípios Linked Data.

Made available in DSpace on 2014-06-12T15:58:00Z (GMT). No. of bitstreams: 2 arquivo3241_1.pdf: 9393847 bytes, checksum: e5bc9db1f5524adb5b2392e6cbfe1e9e (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2010 / Um sistema para consultas espaciais visuais a Bancos de Dados Geográficos (BDG) é caracterizado pela utilização de representações gráficas que visam abstrair a sintaxe da linguagem de consulta do BDG. Web Mapping é um serviço disponibilizado na Web que permite a criação e visualização de mapas e rotas a partir de um Web site. Neste contexto, apesar da popularidade dos serviços de Web Mapping (e.g., Google Maps, Yahoo Maps e Bing Maps), estes não foram concebidos para realizar consultas espaciais (e.g. topológicas, métricas e direcionais) sobre BDG. Visando propor uma alternativa a esta limitação, esta dissertação especifica e implementa o sistema Visual Spatial Query (ViSQ) para, a partir de um serviço de Web Mapping, realizar consultas espaciais visuais sobre um BDG. O ViSQ faz uso de tecnologias abertas, extensíveis e de acordo com padrões consolidados, como Java, XML e SQL. Como avaliação do conceito, é realizado um estudo de caso com dados sobre o setor elétrico que mostra a viabilidade do sistema ViSQ

Consultas por similaridade constituem um paradigma de busca que fornece suporte à diversas tarefas computacionais, tais como agrupamento, classificação e recuperação de informação. Neste contexto, medir a similaridade entre objetos requer comparar a distância entre eles, o que pode ser formalmente modelado pela teoria de espaços métricos. Recentemente, um grande esforço de pesquisa tem sido dedicado à inclusão de consultas por similaridade em Sistemas Gerenciadores de Bases de Dados (SGBDs), com o objetivo de (i) permitir a combinação de comparações por similaridade com as comparações por identidade e ordem já existentes em SGBDs e (ii) obter escalabilidade para grandes bases de dados. Nesta tese, procuramos dar um próximo passo ao estendermos também o otimizador de consultas de um SGBD. Em particular, propomos a ampliação de dois módulos do otimizador: o módulo de Espaço de Distribuição de Dados e o módulo de Modelo de Custo. Ainda que o módulo de Espaço de Distribuição de Dados permita representar os dados armazenados, essas representações são insuficientes para modelar o comportamento das comparações em espaços métricos, sendo necessário estender este módulo para contemplar distribuições de distância. De forma semelhante, o módulo Modelo de Custo precisa ser ampliado para dar suporte à modelos de custo que utilizem estimativas sobre distribuições de distância. Toda a investigação aqui conduzida se concentra em cinco contribuições. Primeiro, foi criada uma nova sinopse para distribuições de distância, o Histograma Compactado de Distância (CDH), de onde é possível inferir valores de seletividade e raios para consultas por similaridade. Uma comparação experimental permitiu mostrar os ganhos das estimativas da sinopse CDH com relação à diversos competidores. Também foi proposto um modelo de custo baseado na sinopse CDH, o modelo Stockpile, cujas estimativas se mostraram mais precisas na comparação com outros modelos. Os Histogramas-Omni são apresentados como a terceira contribuição desta tese. Estas estruturas de indexação, construídas a partir de restrições de particionamento de histogramas, permitem a execução otimizada de consultas que mesclam comparações por similaridade, identidade e ordem. A quarta contribuição de nossa investigação se refere ao modelo RVRM, que é capaz de indicar quanto é possível empregar as estimativas das sinopses de distância para otimizar consultas por similaridade em conjuntos de dados de alta dimensionalidade. O modelo RVRM se mostrou capaz de identificar intervalos de dimensões para os quais essas consultas podem ser executadas eficientes. Finalmente, a última contribuição desta tese propõe a integração das sinopses e modelos revisados em um sistema com sintaxe de alto nível que pode ser acoplado em um otimizador de consultas. / Similarity searching is a foundational paradigm for many modern computer applications, such as clustering, classification and information retrieval. Within this context, the meaning of similarity is related to the distance between objects, which can be formally expressed by the Metric Spaces Theory. Many studies have focused on the inclusion of similarity search into Database Management Systems (DBMSs) for (i) enabling similarity comparisons to be combined with the DBMSs identity and order comparisons and (ii) providing scalability for very large databases. As a step further, we propose the extension of the DBMS Query Optimizer and, particularly, the extension of two modules of the Query Optimizer, namely Data Distribution Space and Cost Model modules. Although the Data Distribution Space enables representations of stored data, such representations are unsuitable for modeling the behavior of similarity comparisons, which requires the extension of the module to support distance distributions. Likewise, the Cost Model module must be extended to support cost models that depend on distance distributions. Our study is based on five contributions. A new synopsis for distance distributions, called Compact-Distance Histogram (CDH), is proposed and enables radius and selectivity estimation for similarity searching. An experimental comparison showed the gains of the estimates drawn from CDH in comparison to several competitors. A cost model based on the CDH synopsis and with accurate estimates, called Stockpile, is also proposed. Omni-Histograms are presented as the third contribution of the thesis. Such indexing structures are constructed according to histogram partition constraints and enable the optimization of queries that combine similarity, identity and order comparisons. The fourth contribution refers to the model RVRM, which indicates the possible use of the estimates obtained from distance-based synopses for the query optimization of high-dimensional datasets and identifies intervals of dimensions where similarity searching can be efficiently executed. Finally, the thesis proposes the integration of the reviewed synopses and cost models into a single system with a high-level language that can be coupled to a DBMS Query Optimizer.

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.

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.