1 Las Mathemáticas de Búsqueda en Internet Gil Bor, CIMAT [email protected]

2

3

4

5

6

7

8

9 Información 1 bit = si/no 1 B = Byte = 8 bit = 1 letra 1 kB = 1000 Byte = 1 hoja 1 MB = 1000 kB = 1 libro

10 Información

11

12 Números grandes

13

14 “…Cuando se proclamó que la Biblioteca abarcaba todos los libros, la primera impresión fue de extravagante felicidad. Todos los hombres se sintieron señores de un tesoro intacto y secreto. No había problema personal o mundial cuya elocuente solución no existiera… …se esperó entonces la aclaración de los misterios básicos de la humanidad…

15

16

17 …Hay buscadores oficiales, inquisidores… … toman el libro más cercano y lo hojean, en busca de palabras infames. Visiblemente, nadie espera descubrir nada… …A la desaforada esperanza, sucedió, como es natural, una depresión excesiva.”

18

19 Búsqueda 1. Rápido 2. Documentos más relevantes primeros

20

21 Rápido: 1. Índice invertido 2. Muchas computadoras…

22

23 Índice Invertido

24 Página 1: “Eso es lo que es" Página 2: “Que es eso" Página 3: “Es una mariposa“ “eso": {1,2} “es": {1,2,3} “lo": {1} “que": {1,2} “una": {3} “mariposa": {3} Ejemplo: buscar “Que es eso” {1,2} ∩ {1,2,3} ∩ {1,2} = {1,2} Índice Invertido

25 Rápido: 1. Índice invertido 2. Muchas computadoras…

26

27

28

29

30 Búsqueda 1. Rápido 2. Documentos más relevantes primeros

31

32

33 Documentos más relevantes primeros: Algoritmo PageRank

34 Algoritmo PageRank (1998) calificar páginas web por “popularidad” Brin + Page (1973- )

35 Trabajo matemático previo Andrey Markov (1856-1922) Oskar Perron (1880-1975 ) Georg Frobenius (1849 –1917)

36

37

38

39 ¿Cómo funciona el “ ranking de popularidad ”? Un caso (muy) simple