Made available in DSpace on 2015-04-11T14:03:08Z (GMT). No. of bitstreams: 1 Celia Francisca dos Santos.pdf: 545200 bytes, checksum: 1be2bb65210d0ea7f3239ecdd2efa28d (MD5) Previous issue date: 2006-02-22 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Neste trabalho são propostos e avaliados experimentalmente novos métodos de poda estática especialmente projetados para máquinas de busca web. Os métodos levam em consideração a localidade de ocorrência dos termos nos documentos para realizar a poda em índices de máquinas de busca e, por esta razão, são chamados de "métodos de poda baseados em localidade". Quatro novos métodos de poda que utilizam informação de localidade são propostos aqui: two-pass lbpm, full coverage, top fragments e random. O método two-pass lbpm é o mais efetivo dentre os métodos baseados em localidade, mas requer uma construção completa dos índices antes de realizar o processo de poda. Por outro lado, full coverage, top fragments e random são métodos single-pass que executam a poda dos índices sem requerer uma construção prévia dos índices originais. Os métodos single-pass são úteis para ambientes onde a base de documentos sofre alterações contínuas, como em máquinas de busca de grande escala desenvolvidas para a web. Experimentos utilizando uma máquina de busca real mostram que os métodos propostos neste trabalho podem reduzir o custo de armazenamento dos índices em até 60%, enquanto mantém uma perda mínima de precisão. Mais importante, os resultados dos experimentos indicam que esta mesma redução de 60% no tamanho dos índices pode reduzir o tempo de processamento de consultas para quase 57% do tempo original. Além disso, os experimentos mostram que, para consultas conjuntivas e frases, os métodos baseados em localidade produzem resultados melhores do que o método de Carmel, melhor método proposto na literatura. Por exemplo, utilizando apenas consultas com frases, com uma redução de 67% no tamanho dos índices, o método baseados em localidade two-pass lbpm produziu resultados com uma grau de similaridade de 0.71, em relação aos resultados obtidos com os índices originais, enquanto o método de Carmel produziu resultados com um grau de similaridade de apenas 0.39. Os resultados obtidos mostram que os métodos de poda baseados em localidade são mais efetivos em manter a qualidade dos resultados providos por máquinas de busca.

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.

Submitted by Lúcia Brandão (lucia.elaine@live.com) on 2015-07-27T17:43:06Z No. of bitstreams: 1 Tese - André Luiz da Costa Carvalho.pdf: 766182 bytes, checksum: 6eecaa1fef5e14867610e7e4c889e91b (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2015-07-28T18:37:39Z (GMT) No. of bitstreams: 1 Tese - André Luiz da Costa Carvalho.pdf: 766182 bytes, checksum: 6eecaa1fef5e14867610e7e4c889e91b (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2015-07-28T18:47:09Z (GMT) No. of bitstreams: 1 Tese - André Luiz da Costa Carvalho.pdf: 766182 bytes, checksum: 6eecaa1fef5e14867610e7e4c889e91b (MD5) / Made available in DSpace on 2015-07-28T18:47:09Z (GMT). No. of bitstreams: 1 Tese - André Luiz da Costa Carvalho.pdf: 766182 bytes, checksum: 6eecaa1fef5e14867610e7e4c889e91b (MD5) Previous issue date: 2012-11-26 / CNPq - Conselho Nacional de Pesquisa e Desenvolvimento Científico e Tecnológico / Search engines station between main Ways to Get INFORMATION on the Internet, receiving Million daily queries. This volume Query topping generates a considerable burden In Query processors of search machines, that should NOT JUST worry with a quality fi nal ANSWER received by users, but Also with a latency This consultation, JA What A delay excessive on MAY rhythm harm a RESPONSE Experience Users ITS. In the Last Year HAS A considerable effort been Research in Technical Application Machine Learning During Query Processing, aiming mainly um increase in the fi nal quality of YOUR answers. This thesis studied the Technical Application machine learning During the generation of indexes, rather than apply them to processing Queries, therefore opening a new front for the Technical Application of Learning Machine in search systems. Within the study, we propose two techniques for the Application Machine learning in the Document Indexing in search of machines with Showing THAT That there Space paragraph enhance an indexing with the use of these techniques. The advantage of this approach is that as THAT Processing And Done Before Consultations Made to be looking machine, Regardless of how costly this computationally BE Process, THIS IS NOT re fl directly etirá In Query Processing Time. We propose here Two techniques: LePrEF, One Evidence Fusion Technique Indexing Time Who Has As a search Purpose Machines Performance Improvement During Processing Consultations, THROUGH indexes Generation que CODI fi cam a Better importance of each term Each Document, AND A phrasal TERMS detection technique (phrases OS), with the objective of improve the quality of the responses obtained FOR THEM. The Technical LePrEF Performs a Relevance of Evidence Sources Fusion pace in Indexing using for both machine learning. The need for evidence of fusion not Drift Query Processing What do FACT search Systems in General Several use Evidence Sources To compute answers YOUR Such As the text of web pages, the text of IN pointers received each page, pointing Analysis Methods As the PageRank, Among many others. However, the recent increase Evidence Sources lev Also one New custodian processing. This is, coupled with the constant growth in the Content Quantity / Máquinas de busca estão entre as principais formas de se obter informações na internet,recebendo milhões de consultas diárias. Este volume avantajado de consultas gera uma considerável carga nos processadores de consultas das máquinas de busca, que devem não apenas se preocupar com a qualidade da resposta final recebida pelos usuários, mas também com a latência desta consulta ,já que uma demora excessiva no tempo de resposta pode prejudicar a experiência de seus usuários. Nos últimos anos tem havido um considerável esforço de pesquisa na aplicação de técnicas de aprendizado de máquina durante o processamento de consultas, objetivando-se principalmente um aumento na qualidade final de suas respostas. Nesta tese estudamos a aplicação de técnicas de aprendizagem de máquina durante a geração de índices, ao invés de aplicá-las ao processamento de consultas, abrindo portanto uma nova frente para a aplicação de técnicas de aprendizagem de máquina em sistemas de busca. Dentro do estudo, propomos duas técnicas para a aplicação de aprendizado de máquina na indexação de documentos em máquinas de busca, mostrando com isso que há espaço para melhorar a indexação com o uso dessas técnicas. A vantagem de tal abordagem é que, como esse processamento é feito antes das consultas serem feitas à maquina de busca, independente de quão custoso computacionalmente seja este processo, isto não refletirá diretamente no tempo de processamento de consultas. Propomos aqui duas técnicas: LePrEF, uma técnica de fusão de evidências em tempo de indexação que tem como objetivo a melhoria do desempenho de máquinas de busca durante o processamento de consultas, por meio da geração de índices que codificam melhor a importância de cada termo em cada documento, e uma técnica de detecção de termos frasais (os sintagmas), com o objetivo de melhorar a qualidade das respostas obtidas por elas. A técnica LePrEF realiza a fusão de fontes de evidência de relevância em tempo de indexação utilizando para tanto aprendizagem de máquina. A necessidade da fusão de evidências no processamento de consultas deriva do fato de que sistemas de busca em geral utilizam diversas fontes de evidência para computar suas respostas, tais como o texto das páginas web, o texto dos apontadores recebidos por cada página, métodos de análise de apontadores como o PageRank, dentre muitos outros. Porém, o acréscimo de novas fontes de evidência leva também a novos custos de processamento. Isto, aliado ao constante crescimento na quantidade de conteúdo

Made available in DSpace on 2015-04-20T12:33:27Z (GMT). No. of bitstreams: 1 jucimar.pdf: 2914952 bytes, checksum: 07583d96a43d2aaee11457881962b461 (MD5) Previous issue date: 2013-03-08 / Search engines are among the most used tools to find information on the Web. Recent studies show that the user s confidence on these systems is high. However, the database of search engines usually contains noisy information that may decrease the search results quality and thus negatively affect the confidence of users in these systems. Such type of information is called noise and it can be intentional or not. The main goals of this thesis are to develop and enhance techniques to detect noise in databases of search engines. We evaluated noisy sources of information that may be present either in the anchor text and/or links structures of search engine indexes. As a result, we present methods to turn search engines less susceptible of negative impact caused by the presence of noisy. / Máquinas ou motores de busca são as ferramentas mais usadas para localizar informações na Internet. Para muitas empresas, a porta de entrada para seu negócio está nas respostas dadas por esses mecanismos a determinadas consultas. Por este motivo, é importante que suas páginas estejam bem posicionadas nestas respostas. Pesquisas recentes mostram que a confiança dos usuários neste mecanismo é relativamente alta. Entretanto, existe nos repositórios de máquinas de busca uma série de informações que podem levar à degradação da qualidade das respostas providas por estes sistemas. Tais informações são conhecidas como ruído, podendo ser geradas de maneira intencional ou não. Esta tese tem como principal objetivo desenvolver e aprimorar técnicas de detecção e tratamento de informação ruidosa em máquinas de busca. Foram avaliadas fontes ruidosas que podem estar nos textos de âncora e/ou nas estruturas dos apontadores presentes em repositórios de máquina de busca. Como resultados, são apresentados métodos para tornar máquinas de busca menos suscetíveis aos efeitos negativos da presença do ruído em seus repositórios.

Made available in DSpace on 2015-04-11T14:03:17Z (GMT). No. of bitstreams: 1 DISSERTACAO JUCIMAR.pdf: 1288048 bytes, checksum: eec502380e9a7d5716cd68993d6cab40 (MD5) Previous issue date: 2009-04-23 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Search engines have become an essential tool for web users today. They use algorithms to analyze the linkage relationships of the pages in order to estimate popularity for each page, taking each link as a vote of quality for pages. This information is used in the search engine ranking algorithms. However, a large amount of links found on the Web can not be considered as a good vote for quality, presenting information that can be considered as noise for search engine ranking algorithms. This work aims to detect noises in the structure of links that exist in search engine collections. We studied the impact of the methods developed here for detection of noisy links, considering scenarios in which the reputation of pages is calculated using Pagerank and Indegree algorithms. The results of the experiments showed improvement up to 68.33% in metric Mean Reciprocal Rank (MRR) for navigational queries and up to 35.36% for randomly selected navigational queries. / Máquinas de busca têm se tornado uma ferramenta imprescindível para os usuários da Web. Elas utilizam algoritmos de análise de apontadores para explorar a estrutura dos apontadores da Web para atribuir uma estimativa de popularidade a cada página. Essa informação é usada na ordenação da lista de respostas dada por máquinas de busca a consultas submetidas por seus usuários. Contudo, alguns tipos de apontadores prejudicam a qualidade da estimativa de popularidade por apresentar informação ruidosa, podendo assim afetar negativamente a qualidade de respostas providas por máquinas de busca a seus usuários. Exemplos de tais apontadores incluem apontadores repetidos, apontadores resultantes da duplicação de páginas, SPAM, dentre outros. Esse trabalho tem como objetivo detectar ruídos na estrutura dos apontadores existentes em base de dados de máquinas de busca. Foi estudado o impacto dos métodos aqui desenvolvidos para detecção de apontadores ruidosos, considerando cenários nos quais a reputação das páginas é calculada tanto com o algoritmos Pagerank quanto com o algoritmo Indegree. Os resultados dos experimentos apresentaram melhoria de até 68,33% na métrica Mean Reciprocal Rank (MRR) para consultas navegacionais e de até 35,36% para as consultas navegacionais aleatórias quando uma máquina de busca utiliza o algoritmo Pagerank.