Arañas distribuidas --Asignación Efectiva de Trabajo Evitando Duplicidad de Espacio y Tiempo

Ésta es la tesis de maestría de Luis Antonio Olguín Aguilar. El documento comleto se encuentra aquí.
RESUMEN. La computación desde sus inicios, como en la actualidad, es utilizada como una herramienta que le ayuda al hombre a resolver problemas de su vida diaria. Tanto la computación clásica como la computación cuántica, bajo distintos paradigmas, están orientados a resolver problemas que a una o varias personas le tomaría mucho tiempo resolver. Uno de los problemas a los que se enfrenta el hombre en la realización de sus actividades está en que una, dos o más personas pueden llegar a realizar la misma actividad y por ende generar los mismos resultados. Esto se conoce como duplicidad de trabajo. La duplicidad de trabajo no sólo es costosa por el hecho de hacer la misma tarea múltiples veces sin la necesidad de requerirlo, sino que también desde el punto de vista de un mundo capitalista puede llegar a costar mucho dinero: pagar sueldos a personas que realicen la misma actividad, gastos de mantenimiento, gastos de operación, entre otros, dependiendo de la actividad que se realice.

Con la llegada de la Web se abrió una etapa en la que la información se puso disponible para cualquier persona que desee conectarse a la Internet. Con el paso del tiempo esta información ha ido creciendo y se hizo necesario crear programas que examinaran constantemente la información que los usuarios ponían disponible día a día. Estos programas son conocidos como “Web crawlers” o “arañas”. Un Web crawler es un programa que inspecciona de manera metódica y automatizada las páginas de la Internet. Para un Web crawler es sumamente importante no duplicar trabajo, pues una dirección URL duplicada puede originarle perder varias horas o incluso días de trabajo ya que otra de sus tareas es extraer direcciones URL incluidas dentro de ella y procesarlas de igual manera.

El presente trabajo muestra el análisis, diseño, implementación, pruebas y resultados de una aplicación que resuelve el problema de duplicidad de trabajo evitando la duplicidad en espacio de almacenamiento, así como de tiempo de procesamiento en la extracción de documentos de la Internet permitiendo que por cada página Web se asocie a ella 4 de los principales temas de los que trata el documento. De manera particular el trabajo que cada araña hace, sin duplicación, es el siguiente: “buscar en cada página indicada por una lista de URLs, documentos que contengan suficiente texto, e indizar tanto la página como el documento (si existe). Si en cierta página hay apuntadores, éstos señalan nuevas páginas, las que a su vez reciben el mismo tratamiento, hasta un cierto nivel de profundidad, 4 en nuestro caso. Repetir este procedimiento periódicamente, variando dinámicamente el período de visita, según la actividad que muestre la página. Evitar volver a indizar un documento que no ha cambiado.”

En el capítulo 1 se presenta una introducción a nuestro tema de tesis. Se incluye el planteamiento del problema que vamos a resolver, mostramos los objetivos planteados tanto de manera general como de manera particular. Mostramos una breve justificación respecto a construir un sistema que resuelve el problema planteado y finalmente mostramos los alcances y límites que pretendemos lograr. En el capítulo 2 mostramos lo que es un Web Crawler, conocemos el estado del arte y finalmente mostramos las características generales que tiene. En el capítulo 3 describimos lo que es un sistema distribuido. Presentamos sus ventajas y desventajas. También explicamos la arquitectura RMI (Remote Method Invocation, Invocación de Métodos Remotos) de Java que es utilizada para implementar sistemas distribuidos. Se muestran las capas con que cuenta esta arquitectura, las clases que deben ser implementadas y algunos ejemplos que son de utilidad para su entendimiento. En el capítulo 4 se describe el problema planteado, mostramos la arquitectura propuesta que lo resuelve, así como un ejemplo práctico del funcionamiento que debe implementarse.

En el capítulo 5 se muestra el diseño de la aplicación. En él se describen los distintos procesos involucrados en la realización de las tareas tanto del servidor como de la araña. El capítulo 6 muestra la implementación de la aplicación. Esta implementación muestra el esquema de comunicación del servidor y de la araña. Finalmente, se explica la manera en que obtenemos los temas que trata cada documento mediante Clasitex. El capítulo 7 muestra la fase de pruebas. En este capítulo se muestran varias pruebas realizadas a la aplicación así como sus resultados. El capítulo 8 es dedicado a presentar las conclusiones a las que llegamos después de haber obtenido los resultados, producto de las pruebas realizadas en el capítulo 7.

ABSTRACT. (The full document is here) The computation since the begining to today is used as a tool that helps people to resolve a lot of problems of their daily life. Classic computing as well as Quantum computing, under differt paradigms, are oriented to solve problems that for a single person could take a lof of years to answer. One of the main problems that people has to deal is about to do the same work many times at different times for more than one person. This is known as duplicity.

The duplicity of the work costs a lot of money in a capitalistic world, for example paying a salary to people who has to do the work, maintain costs, operation costs and many others.

When the World Wide Web (www) came to our lifes it opened a new style of life because the information was online just with a simple click. Since 80’s to our days this information has grown exponentially and it had new necesities like to organize those millions of Web Pages. That was the main reason to build Web Crawlers or Spiders. A Web Crawler is a program which explores the Web Pages on the Internet. One of the main characteristics of a Web Crawler is not to duplicate the work because when it crawls the Web, with a simple URL, a Web Crawler could spend a lot of hours and maybe days doing its work.

This thesis shows the analysis, design, implementation, tests and results of an application which solve the problem of the duplicity of work avoiding the duplicity of the space used to save the Web Pages and the time crawling the Internet making possible to associate to every Web Page four of the main topics of that document The work of a spider is the next: “looking for documents with enough text, in every Web page that contains the list of URLs, to index that page and the document. When the page has links to anothers pages these new ones receive the same tratement with a level of deep 4. This procedure must be repited everyday, changing the time of visit depending the time of change of that Web page. It`s very important not to process tha same document twice or more”.

Chapter 1 shows an introduction to the thesis. It includes the problem to resolve, the objetives and the main reasons to build this system and finally the limits and goals to reach. Chapter 2 shows what a web crawler is and its main characteristics. Chapter 3 shows what a distributed crawler is. We explain the RMI architecture, that allows to build a Distributed System and finally shows an example of it. Chapter 4 shows the problem to solve and the way to solution it. Chapter 5 shows the design of the application. Chapter 6 shows the implementation of the application. It shows the architecture of the Server, the clients and their comunication. It shows the way to obtain the main topics of a document through Clasitex.Chapter 7 shows several tests of the system and their results. Chapter 8 shows conclusions.