Busquedas en redes p2p

PeerSearch: B´squeda por sem´ntica para redes u a P2P
Rodolfo Bernales 2473044-1 Cristian Fuentes 2673059-7 Ignacio Fuenzalida 2773028-0 Valeria Gonz´lez a 2573058-5 Francisco Gutierrez 2473036-0
Universidad T´cnica Federico Santa Mar´ e ıa Deptartamento de Inform´tica a Computaci´n Cient´ o ıfica 1

13 de julio de 2010
Resumen En este paper, los autores proponen un sistema eficiente derecuperaci´n de informaci´n, PeerSearch, que soporta b´squedas por cono o u tenido y por sem´ntica. PeerSearch evita el problema de escalabilidad a existente en las redes que utilizan indexaci´n centralizada, index floodo ing o query flooding. Tambi´n evita el no determinismo presente en ale gunos tipos de redes con el uso de enfoques basados en meta-heur´ ısticas. PeerSearch logra esta eficiencia ydeterminismo mediante la combinaci´n o de un ´ ındice de colocaci´n y una consulta de enrutamiento. En una cono sulta, PeerSearch s´lo necesita buscar en un peque˜o n´mero de nodos o n u para identificar el documento correspondiente.

1

1.

Introducci´n o

El r´pido crecimiento de internet supera con creces las capacidades a de cualquier motor de b´squeda. Se estima que en el a˜o 2000, lacantiu n dad de contenido web era alrededor de 550 mil millones de documentos, muy superior a los cerca de 1.2 mil millones identificados por “google”, sin mencionar de los 600 millones de p´ginas que “google” es capaz de a buscar. Sistemas Peer to Peer tales como Gnutella o Bittorrent han adquirido gran popularidad gracias al anonimato del que proveen y la capacidad del usuario sobre compartir suscontenidos. Aqu´ es donde nace la necesiı dad de un sistema de recuperaci´n de la informaci´n (IR) descentralizado. o o En la actualidad existen diversos tipos de sistemas P2P, tales como Pastry y CAN (ambos sistemas estructurados) o Gnutella y Bittorrent (sistemas no estructurados). Normalmente basan su sistema de b´squeda en inu dexaci´n centralizada, query flooding, indexing flooding o heur´ oısticas. Indexaci´n centralizada sufre de los problemas de “cuello de botella” ya o que todas las b´squedas deben pasar por un servidor central de indexaci´n. u o T´cnicas basadas en flooding env´ una consulta o un ´ e ıan ındice a distintos nodos del sistema, consumiendo una gran cantidad de ancho de banda, disminuyendo los tiempos de respuesta del sistema. Las t´cnicas basadas e en heur´ ısticasrealizan las b´squeda con una fracci´n de la poblaci´n de la u o o red, por lo que los resultados pueden fallar al momento de retribuir datos importantes. Los sistemas de tipo “Distributed hash table” (DHT) como CAN, proveen de una buena escalabilidad y de garant´ de determinismo, pero ellos s´lo ıas o ofrecen una interfaz simple para almacenar y recuperar (key, value). Aplicando directamente a la IR, siun usuario desea requerir alg´n documento u en espec´ ıfico, deber´ especificar el ID (key) del documento solicitado para a obtenerlo, algo impracticable en una red del orden de los miles de millones, con organizaciones y usuarios independientes entre s´ ı. PeerSearch logra eficiencia y determinismo mediante la combinaci´n de o “index placement” y “query routing”. Cuando se realiza una petici´n, oPeerSearch s´lo necesita buscar en un peque˜o n´mero de nodos para o n u identificar el documento correspondiente. Para utilizar los algoritmos de IR m´s desarrollados tal como “Modelo de Espacio Vectorial” (VSM) e a “Indexaci´n Sem´ntica Latente” (LSI), PeerSearch representa documeno a tos y consultas como vectores y mide la similitud entre una consulta y un documento como el coseno del anguloentre sus representaciones de ´ vector. PeerSearch almacena un ´ ındice de documento en CAN utilizando la representaci´n del vector como las coordenadas, resultando que ´ o ındices almacenados cerca mutuamente tendr´n similar sem´ntica. Esto unifica el a a problema del contenido o la b´squeda basada sem´ntica con la asignaci´n u a o de ruta en una red. Varias caracter´ ısticas distinguen PeerSearch...