analisis de conjuntos de datos rdf para mejorar´ la...

UNIVERSIDAD DE VALLADOLID

EDIFICIO DE LAS TECNOLOGIAS DE LA

INFORMACION Y LAS COMUNICACIONES

TRABAJO FIN DE MASTER

MASTER UNIVERSITARIO EN INVESTIGACION

EN TECNOLOGIAS DE LA INFORMACION Y LAS COMUNICACIONES

Analisis de conjuntos de datos RDF para mejorarla compresion usando HDT

Autor:

D. Mario Arias Gallego

Tutor:

Dr. D. Pablo de la Fuente Redondo,Dr. D. Miguel A. Martınez-Prieto,

D. Javier David Fernandez Garcıa.

Valladolid, 14 de Enero de 2011

T ITULO: Analisis de conjuntos de datos RDF paramejorar la compresion usando HDT

AUTOR: D. Mario Arias GallegoTUTOR: Dr. D. Pablo de la Fuente Redondo

Dr. D. Miguel A. Martınez-PrietoD. Javier David Fernandez Garcıa

DEPARTAMENTO: GRINBD

TribunalPRESIDENTE: Dr. D. Yannis Dimitriadis DamoulisVOCAL: Dr. D. Jesus Vegas HernandezSECRETARIO: Dr. D. Miguel Angel Laguna SerranoFECHA: 14 de Enero de 2011CALIFICACION:

Resumen del TFMHDT es una iniciativa para representar grandes ficheros RDF de manera compacta,

y ası poder almacenarlos en menos espacio, transmitirlos mas rapido por la red, y poderacceder a la informacion sin tener que descomprimirla por completo. El objetivo de estetrabajo es analizar datos RDF del mundo real para conocer a fondo sus caracterısticasgenerales y descubrir los casos especiales. Posteriormente estudiaremos la influencia deestas peculiaridades en la eficiencia de compresion mediante HDT.

Palabras claveWeb Semantica, RDF, Compresion, Indexado, SPARQL, Billion Triples, Estadısticas.

AbstractHDT is an initiative to represent huge RDF data files in a compact manner, so they

can be stored using less space, sent faster through a network, or accessed without the needof uncompressing the whole file. The main objective of this work is analyzing real-worldRDF data to understand its general characteristics and discover special cases. Afterwardswe analyze the influence of these peculiarities on the efficiency of compression usingHDT.

KeywordsSemantic Web, RDF, Compression, Indexing, SPARQL, Billion Triples, Statistics.

Agradecimientos

El autor de este trabajo de investigacion quiere mostrar su agradecimiento a los tutoresPablo de la Fuente, Miguel Angel Martınez y Javier David Fernandez, por su apoyo tantoprofesional como personal. Tambien a todos los que han participado y han hecho posibleel Master MUI-TIC.

Por ultimo agradecer a mis padres y amigos su apoyo tanto en la motivacion que mehan aportado, como en la comprension cuando estaba absorto en el trabajo y no les pres-taba la atencion que se merecıan. Especialmente a Marisol y Alejandro por estimularme arealizar este trabajo respetando los plazos previstos.

V

Indice general

1. Introduccion 11.1. Motivacion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2. Estructura de la memoria . . . . . . . . . . . . . . . . . . . . . . . . . . 2

2. Conocimientos previos 32.1. Web Semantica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2.1.1. Conceptos generales y RDF basico . . . . . . . . . . . . . . . . . 32.1.2. Identificadores de Recursos y Literales . . . . . . . . . . . . . . 52.1.3. Serializacion de grafos RDF . . . . . . . . . . . . . . . . . . . . 5

2.2. Compresion e Indices . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72.2.1. Efectividad de los compresion . . . . . . . . . . . . . . . . . . . 132.2.2. Mapas de bits, rank y select . . . . . . . . . . . . . . . . . . . . 142.2.3. Estructuras de datos Sucintas . . . . . . . . . . . . . . . . . . . . 142.2.4. Transformada de Burrows-Wheeler . . . . . . . . . . . . . . . . 15

2.3. Herramientas estadısticas . . . . . . . . . . . . . . . . . . . . . . . . . . 162.3.1. Analisis exploratorio de Datos . . . . . . . . . . . . . . . . . . . 162.3.2. Estadıstica descriptiva . . . . . . . . . . . . . . . . . . . . . . . 172.3.3. Power-law . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.4. Otros analisis de RDF . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202.5. Compresion de RDF mediante HDT . . . . . . . . . . . . . . . . . . . . 21

3. Planteamiento del estudio 273.1. Presentacion del problema . . . . . . . . . . . . . . . . . . . . . . . . . 273.2. Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283.3. Diseno de experimentos . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

3.3.1. Caracterısticas a analizar . . . . . . . . . . . . . . . . . . . . . . 293.3.2. Eleccion de Datasets . . . . . . . . . . . . . . . . . . . . . . . . 32

4. Experimentacion y Resultados 354.1. Procesamiento del conjunto de datos BillionTriples . . . . . . . . . . . . 354.2. Generacion y limpieza de datos . . . . . . . . . . . . . . . . . . . . . . . 404.3. Analisis del dataset RDF . . . . . . . . . . . . . . . . . . . . . . . . . . 42

4.3.1. Numero y tamano de triples . . . . . . . . . . . . . . . . . . . . 424.3.2. Numero de Sujetos y Objetos . . . . . . . . . . . . . . . . . . . 444.3.3. Predicados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 474.3.4. Grados del Grafo RDF . . . . . . . . . . . . . . . . . . . . . . . 51

VII

VIII INDICE GENERAL

4.3.5. Longitud de cadenas . . . . . . . . . . . . . . . . . . . . . . . . 564.4. Analisis de compresion de BT2010 con HDT . . . . . . . . . . . . . . . 59

4.4.1. Diccionario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 594.4.2. Triples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 624.4.3. Global . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

4.5. Herramienta visual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 694.5.1. Analisis visual de los conjuntos de datos . . . . . . . . . . . . . . 72

4.6. Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

5. Conclusiones y Trabajo Futuro 79

Indice de figuras

2.1. Representacion de RDF en forma de Grafo. . . . . . . . . . . . . . . . . 42.2. Paradigma de Shannon de un modelo compresor/descompresor. . . . . . . 82.3. Ejemplo de un arbol de Huffman para un alfabeto σ = {σ1 . . . σ6} junto

con las probabilidades de aparicion de cada uno de los nodos. . . . . . . . 102.4. Ejemplo de operaciones rank y select en un mapa de bits. . . . . . . . . . 142.5. Ejemplo de transformada de Burrows-Wheeler sobre la cadena “BANANA”. 152.6. Ejemplo de grafo RDF de la DBpedia. . . . . . . . . . . . . . . . . . . . 222.7. Grafo de la DBpedia en formato HDT. . . . . . . . . . . . . . . . . . . . 232.8. Distintas representaciones del grafo RDF dentro de la seccion Triples de

HDT. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242.9. Distintas representaciones del grafo RDF dentro de la seccion Triples de

HDT. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

4.1. Numero de triples por dominio, en orden decreciente. . . . . . . . . . . . 374.2. Tamano de los 700 dominios con mas ternas. . . . . . . . . . . . . . . . 374.3. Tamano de dominios a partir del 700. . . . . . . . . . . . . . . . . . . . . 384.4. Tamano en bytes por triple, ordenados por orden de tamano creciente. . . 424.5. Distribucion del tamano de los triples en bytes. . . . . . . . . . . . . . . 434.6. Numero de triples en relacion al tamano del dataset en bytes. . . . . . . . 434.7. Numero de objetos y sujetos a medida que incrementamos el numero de

triples. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 444.8. Distribucion de la proporcion de sujetos/objetos en los distintos datasets. . 454.9. Numero de sujetos y objetos compartidos a medida que incrementamos el

numero de triples. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 464.10. Distribucion del ratio SOCompartidos/triples. . . . . . . . . . . . . . . . 464.11. Numero de predicados a medida que incrementamos el numero de triples. 474.12. Distribucion de la cantidad de predicados. . . . . . . . . . . . . . . . . . 484.13. Distribucion de la cantidad de uso de cada predicado en la DBPedia. . . . 494.14. Distribucion de la cantidad de uso de cada predicado en Freebase. . . . . 494.15. Distribucion de la cantidad de uso de cada predicado en ChatMusicBrainz. 504.16. Distribucion de la cantidad de uso de cada predicado en DBLP. . . . . . . 504.17. Distribucion de la cantidad de uso de cada predicado en RossettiArchive. . 514.18. Comparativa entre histograma del grado de salida y del ranking de grado

de salida . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 524.19. Grado de salida y su ajuste potencial. . . . . . . . . . . . . . . . . . . . . 524.20. Rank del grado de salida y su ajuste potencial. . . . . . . . . . . . . . . . 53

IX

X INDICE DE FIGURAS

4.21. Distribucion de grados de entrada y de salida. . . . . . . . . . . . . . . . 544.22. Distribucion de grados parciales de entrada y salida. . . . . . . . . . . . . 554.23. Distribucion de grados etiquetados de entrada y salida. . . . . . . . . . . 564.24. Distribucion del ratio Literal/Objeto entre los distintos datasets. . . . . . . 574.25. Distribucion de longitudes de las URIs. . . . . . . . . . . . . . . . . . . 584.26. Distribucion de longitudes de los literales. . . . . . . . . . . . . . . . . . 584.27. Distribucion de longitudes de los nodos anonimos. . . . . . . . . . . . . 604.28. Crecimiento del tamano del diccionario respecto al numero de triples. . . 604.29. Comparativa de los ratios de compresion del diccionario con los distintos

compresores universales. . . . . . . . . . . . . . . . . . . . . . . . . . . 614.30. Comparativa de parsing en la compresion de Triples, expresado como el

ratio respecto a PlainTriples. . . . . . . . . . . . . . . . . . . . . . . . . 624.31. Comparativa de compresion de Triples, expresado como el ratio respecto

a PlainTriples. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 634.32. Distribucion del ratio Diccionario/Triples en plano. . . . . . . . . . . . . 644.33. Distribucion del ratio Diccionario/Triples comprimido. . . . . . . . . . . 644.34. Dependencia entre los grados de entrada y el ratio de compresion Com-

pactTriples en plano en distintos parsings. . . . . . . . . . . . . . . . . . 654.35. Dependencia entre los grados de salida y el ratio de compresion Compact-

Triples en plano en distintos parsings. . . . . . . . . . . . . . . . . . . . 664.36. Dependencia entre el ratio de compresion POS Compact y el grado parcial

de entrada. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 674.37. Dependencia entre el ratio de compresion POS Compact+Huffman y el

grado parcial de entrada. . . . . . . . . . . . . . . . . . . . . . . . . . . 674.38. Comparativa del ratio final de compresion entre HDT y otros. . . . . . . . 684.39. Pantalla inicial del visualizador HDT RDF. . . . . . . . . . . . . . . . . 694.40. Vista tridimensional del visualizador HDT RDF. . . . . . . . . . . . . . . 704.41. Ejemplo de lıneas verticales correspondientes al predicado rdf:type. . 724.42. Ejemplo de lınea horizontal correspondiente los predicados rdf: N, ada

uno identificado por su color. . . . . . . . . . . . . . . . . . . . . . . . . 724.43. Vista general del conjunto de datos bibsonomy antes y despues del clus-

tering. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 744.44. Vista general del conjunto de datos BerkeleyBop original antes y despues

de la reasignacion de ındices. . . . . . . . . . . . . . . . . . . . . . . . . 75

Capıtulo 1

Introduccion

1.1. Motivacion

La Web ha supuesto una revolucion en la forma de comunicarse las personas. La WebSemantica intenta ir un paso mas alla y propone organizar la informacion de la Web paraque tambien las maquinas sean capaces de publicar, encontrar y procesar datos de maneraautomatica. El estandar RDF [29] ası como todos los vocabularios y herramientas asocia-dos hacen posible la comparticion de datos en la Web en formato estructurado formandola filosofıa que se conoce como de datos enlazados (Linked-Data) [6, 38].

El desarrollo de todo este tipo de utilidades ha propiciado que se empiecen a publicarconjuntos de datos de gran magnitud como Dbpedia [3, 7], Uniprot [39], Freebase [22],o BillionTriples [2], apareciendo el problema ya conocido en la Web de la escalabilidad.El volumen de datos es de tal magnitud, que se hace necesario estudiar delicadamentenuevos formatos y estructuras de datos para manejarlos de manera eficiente, ya sea en unamaquina local o en un sistema distribuido.

Uno de los problemas de las serializaciones RDF es que estan disenadas para ser ex-presivas, no para ocupar poco espacio. Esto acarrea problemas tanto de cara al almacena-miento como a su transmision por la red, por tanto es necesario comprimirlos para reducirel volumen. Se pueden utilizar algoritmos de compresion generalistas tradicionales ba-sados en Lempel-Ziv [41] o Burrows-Wheeler [12], para comprimir las serializacionesestandar de RDF como N3 [37], Turtle[4], o RDF-XML [5]. Efectivamente este tipo detecnicas reducen en gran medida el tamano de los datos, pero tienen un gran inconvenien-te: Es necesario descomprimirlos por completo para realizar cualquier tipo de busquedaen la estructura, como por ejemplo encontrar una terna RDF concreta o filtrar todas lasternas que cumplan una determinada condicion. En la literatura existen una gran cantidadde trabajos de estructuras de datos compactas que permiten tanto reducir el tamano comorealizar busquedas de distinto tipo. Sin embargo, existen pocos estudios que se centren enRDF desde el punto de vista de su compresion e indizado de manera simultanea.

Uno de los primeros pasos de la compresion particularizada a un tipo de informa-cion concreto es el de comprender las caracterısticas de los datos. La compresion se basaen construir modelos que representen la informacion para posteriormente codificarla demanera que utilice menos bits para representar cada elemento. Para entender los datos de-beremos usar estadısticas, buscar patrones, factores comunes, tendencias y casos extranos.

1

2 CAPITULO 1. INTRODUCCION

Una vez conocida la naturaleza de los datos, se disenaran estructuras, ındices y represen-taciones que exploten la redundancia para minimizar el espacio necesario permitiendo asu vez realizar busquedas.

Otro problema interesante a resolver al trabajar con datos genericos RDF es la diver-sidad. Existen multiples fuentes de datos con distintos objetivos y por tanto estructurasmuy diferentes. Sera necesario encontrar que pautas comunes podemos extraer de ellos yque partes son mas variables y por tanto mas difıcilmente predecibles.

Debido al rapido crecimiento de la cantidad de informacion publicada en RDF y asu diversidad, no existen trabajos profundos estudiando sus caracterısticas intrınsecas, yninguno de los existentes se centra en caracterısticas que seran importantes desde el puntode vista de compresion. La motivacion de este trabajo por tanto, es realizar un analisisexperimental de conjuntos de datos RDF reales para conocer caracterısticas estructuralesy de redundancia desde el punto de vista de la compresion. Este trabajo servira como puntode partida de cara disenar estructuras de datos y algoritmos que trabajen con este tipo deinformacion, especialmente en las tareas de almacenamiento, compactacion e indexado.Tambien es interesante la metodologıa, tecnicas, herramientas y metricas utilizadas en elestudio de los datos.

El grupo GRINBD de la Universidad de Valladolid ya ha trabajado durante los ulti-mos meses en el desarrollo de un sistema de almacenamiento e indizado RDF llamadoHDT [20, 21]. La motivacion de este trabajo parte de su necesidad de comprender losdatos para optimizar sus estructuras de datos y algoritmos. Utilizaremos sus estudios yherramientas como punto de partida para desarrollar este estudio.

1.2. Estructura de la memoriaEl capıtulo 1 presenta una breve motivacion del estado actual, la problematica encon-

trada y el objeto del estudio.El capıtulo 2 repasa los conceptos mas importantes de cada una de las areas tratadas,

indicando el estado de la tecnica y los ultimos avances en temas de investigacion, y de estamanera asegurar que se conoce suficientemente la materia para entender el resto del estu-dio. Por ejemplo se introducen la Web Semantica y el lenguaje RDF, conceptos generalesde compresion o herramientas estadısticas usadas en el estudio. Tambien se describenotros estudios de RDF y el estado actual del compresor HDT.

El capıtulo 3 desarrolla el planteamiento del estudio. Se presenta en mayor detalleel problema, se fijan una serie de objetivos a resolver, se seleccionan los conjuntos dedatos a utilizar, y se disenan los experimentos a realizar para encontrar las caracterısticasbuscadas.

El capıtulo 4 describe en detalle todo el proceso seguido para realizar los experimen-tos sobre los datos, de manera que se puedan replicar o aplicar a otras fuentes de datos. Enconcreto se detalla como se ha procesado el conjunto de datos BT2010 y los resultadosobtenidos de las metricas definidas en el capıtulo 3. Tambien se estudian las caracterısti-cas de compresion del conjunto de datos usando HDT, y se utiliza una herramienta devisualizacion RDF construida para tal efecto.

Por ultimo en el capıtulo 5 se presentan las conclusiones finales de este trabajo, ası co-mo las areas que pueden ser interesantes para trabajos futuros.

Capıtulo 2

Conocimientos previos

En esta seccion se hace un repaso de los conceptos fundamentales de las distintasareas. Esto permitira tanto comprender mejor el resto del estudio, como conocer la van-guardia de investigaciones en los distintos ambitos.

2.1. Web Semantica

La Web Semantica es la Web de los datos. Se basa en la idea de anadir metadatossemanticos usando ontologıas a la World Wide Web tradicional. Estas anotaciones descri-ben el contenido de una manera formal, anadiendo significado y relaciones entre los re-cursos. Esta metainformacion facilita la interoperabilidad entre los sistemas informaticosutilizando agentes inteligentes, es decir, artefactos software autonomos que son capacesde realizar operaciones sobre los datos sin intervencion humana.

Para conseguir estos objetivos se definen una serie de lenguajes, protocolos y estanda-res que permiten construir herramientas para trabajar con este tipo de informacion. Unode los pilares basicos de la Web Semantica es el framework RDF [29], disenado comomodelo para describir metadatos y apoyado por distintas especificaciones del World WideWeb Consortium (W3C).

2.1.1. Conceptos generales y RDF basico

El modelo RDF se basa en la idea de describir la realidad a traves de afirmacionesexpresadas en la forma sujeto-predicado-objeto (conocidas en terminos RDF como triple-ta). El sujeto es el recurso, es decir aquello que se esta describiendo. El predicado es lapropiedad o relacion que se desea expresar de ese sujeto. Y por ultimo, el objeto es elvalor de la propiedad, que puede ser o bien un literal (un valor constante concreto), o bienotro recurso con el que se establece una relacion.

<h t t p : / / www. example . o rg / i n d e x . h tml> <h t t p : / / p u r l . o rg / dc / e l e m e n t s / 1 . 1 /c r e a t o r> <h t t p : / / www. example . o rg / s t a f f i d /85740> .

<h t t p : / / www. example . o rg / i n d e x . h tml> <h t t p : / / www. example . o rg / t e r m s /c r e a t i o n−d a t e> ” August 16 , 1999 ” .

<h t t p : / / www. example . o rg / i n d e x . h tml> <h t t p : / / p u r l . o rg / dc / e l e m e n t s / 1 . 1 /l a n g u a g e> ” en ” .

3

4 CAPITULO 2. CONOCIMIENTOS PREVIOS

Figura 2.1: Representacion de RDF en forma de Grafo.

En el ejemplo anterior podemos observar un extracto de informacion RDF en formatoN3. Cada lınea representa una sentencia (tripleta) RDF. En este caso se esta describien-do el elemento http://www.example.org/index.html. En cada lınea se afirmauna de las propiedades, el creador, la fecha de creacion y el idioma. Podemos observarpor ejemplo que en la primera sentencia se esta enlazando con otro recurso, en este casoel creador de la pagina Web, identificado por su URI completa. Sin embargo en las otrasdos lıneas se especifican directamente las propiedades con un literal rodeado de comillas.En todo caso las sentencias RDF se terminan con un punto.

Una de las peculiaridades de RDF es que las tripletas pueden visualizarse en formade grafo. Por ejemplo un sujeto puede tener varios predicados que lo asocian con otrosrecursos. Algunos de estos recursos a su vez estaran asociados otros y ası sucesivamente.Esta representacion normalmente es mas util para tratar con datos RDF, como puede verseen la figura 2.1.

RDF permite utilizar en principio cualquier nombre de propiedad. Sera responsabili-dad de los autores describir el significado de cada una de ellas y asociarle una semanticaque de significado a la sintaxis. RDF proporciona un vocabulario basico que permite rea-lizar esta tarea, por ejemplo:

rdf:type. Para poder establecer que un recurso pertenece a una clase, es decir, sutipo.

rdf:Property. La clase a la que pertenecen las propiedades.

rdf:Alt, rdf:Bag, rdf:Seq. Contenedores de elementos (opciones alternativas, gru-po no ordenado, y ordenado respectivamente).

RDF solo especifica como construir las tripletas con afirmaciones, pero generalmentese necesitan abstracciones adicionales de mas alto nivel que permitan ampliar la expresi-vidad. Para ello se utilizan extensiones que se encuentran un nivel por encima de RDF.

Por ejemplo RDFSchema (RDFs) [9] extiende el vocabulario original de RDF permi-tiendo:

2.1. WEB SEMANTICA 5

Tipos rdfs:Class permite declarar nuevas clases con las que calificar recuros.rdfs:Resource es la clase a la que pertenecen todos los recuros, rdfs:Literales la clase de todos los literales cadenas y enteros y rdfs:Datatype es la claseque abarca los tipos de datos definidos en RDF.

Relaciones. Permiten expresar relaciones entre recursos. Fundamentalmente exis-ten rdfs:subClassOf y rdf:subPropertyOf que permiten construir jerar-quıas de clases y propiedades respectivamente.

Restricciones. Permiten establecer las condiciones que deben cumplir los recursospara poder tener una propiedad. Puede ser o bien rdfs:domain para indicar eldominio (que sujetos) y rdfs:range para indicar el rango (que objetos).

Otras. RDFs tambien incluye opciones adicionales como rdfs:seeAlso, rdfs:label,y tambien rdfs:comment.

Existen otros vocabularios estandar como OWL [31] o DAML [15] que permiten cons-truir ontologıas y vocabularios mas avanzados pero sus detalles no son de especial interespara este estudio.

2.1.2. Identificadores de Recursos y LiteralesLos recursos deberan tener un identificador unico, de manera que en cada tripleta RDF

se identifique unıvocamente a que recurso nos estamos refiriendo. Para ello RDF proponeel sistema de URIs. Cada recurso tendra una URI diferente, compuesta por una parte dedominio que puede ser comun para varias URIs con la misma procendencia y una parteconcreta especıfica de ese recurso concreto.

Un problema de las URIs es que tienden a ser bastante largas, por ello RDF permitedefinir prefijos. Por ejemplo a la parte http://www.w3.org/TR/rdf-schema/ sele puede acortar con el prefijo rdfs:. De esta manera una URI concreta como http://www.w3.org/TR/rdf-schema/Resource se acorta como rdfs:Resource.Ademas de ahorrar espacio, esto permite a los humanos identificar de manera mas intuitivalos nombres de los recursos.

Los literales son numeros o cadenas de texto que representan valores concretos pa-ra propiedades. Por ejemplo el nombre de una persona, la cifra de su edad o su correoelectronico. Una caracterıstica interesante es que un literal puede indicar en que idio-ma se ha expresado. Por ejemplo podrıamos tener la propiedad Color con el valor“red”@english y “rojo”@spanish.

En RDF existen una serie de nodos que se conocen como anonimos (Blank nodes)o blancos. Su existencia radica en que hay nodos que solo aparecen una vez como nexode otros nodos, y por tanto no es necesario referirse a ellos posteriormente. Aun ası,sera necesario tenerlos en cuenta a la hora de trabajar con el grafo RDF porque si sepierden cambiara todo el significado.

2.1.3. Serializacion de grafos RDFExisten dos formas fundamentales de representar informacion RDF, o bien como una

lista de tripletas individuales, o bien ver el conjunto como un grafo dirigido de recursos

con sus relaciones, donde los literales son nodos hoja.A la hora de guardar un conjunto de datos RDF en un fichero, existen varias aproxi-

maciones estandar:

N-Triples Consiste en escribir una tripleta por lınea en el formato:

<SUJETO> <PREDICADO> <OBJETO> .

Su mayor ventaja es que es muy facil de parsear y procesar, y aunque es legible paralos humanos la visualizacion se hace pesada cuando el numero de ternas es eleva-do. Permite el uso de determinados prefijos para las URIs, pero aun ası contienemuchısima redundancia. Por ejemplo:

<h t t p : / / www. w3 . org / 2 0 0 1 / sw / RDFCore / n t r i p l e s /><h t t p : / / www. w3 . org /1999/02 /22− r d f−syn t ax−ns # type><h t t p : / / xmlns . com / f o a f / 0 . 1 / Document> .

<h t t p : / / www. w3 . org / 2 0 0 1 / sw / RDFCore / n t r i p l e s /><h t t p : / / p u r l . o rg / dc / t e r m s / t i t l e > ”N−T r i p l e s ”@en−US .

<h t t p : / / www. w3 . org / 2 0 0 1 / sw / RDFCore / n t r i p l e s /><h t t p : / / xmlns . com / f o a f / 0 . 1 / maker> : a r t .

<h t t p : / / www. w3 . org / 2 0 0 1 / sw / RDFCore / n t r i p l e s /><h t t p : / / xmlns . com / f o a f / 0 . 1 / maker> : dave .

: a r t <h t t p : / / www. w3 . org /1999/02 /22− r d f−syn t ax−ns#><h t t p : / / xmlns . com / f o a f / 0 . 1 / Person> .

: a r t <h t t p : / / xmlns . com / f o a f / 0 . 1 / name> ” Ar t Bars tow ” .

: dave <h t t p : / / www. w3 . org /1999/02 /22− r d f−syn t ax−ns#><h t t p : / / xmlns . com / f o a f / 0 . 1 / Person> .

: dave <h t t p : / / xmlns . com / f o a f / 0 . 1 / name> ” Dave B e c k e t t ” .

Turtle Trata de paliar algunos de los inconvenientes de N-Triples, ademas de es-tablecer prefijos permite definir listas y organizar las tripletas en forma jerarquicade arbol. Para cada sujeto, indica su lista de predicados, y para cada predicado lalista de Objetos. De esta manera se consigue agrupar reduciendo la redundancia yhaciendo mas legible el contenido. Cada hoja indicara una tripleta RDF compuestapor el Sujeto y Predicado de sus padres. Por ejemplo:

@pref ix r d f : <h t t p : / / www. w3 . org /1999/02 /22− r d f−syn t ax−ns#> .@pref ix dc : <h t t p : / / p u r l . o rg / dc / e l e m e n t s / 1 . 1 / > .@pref ix ex : <h t t p : / / example . o rg / s t u f f / 1 . 0 / > .

<h t t p : / / www. w3 . org / TR / r d f−syn t ax−grammar>dc : t i t l e ”RDF/XML Syntax S p e c i f i c a t i o n ( Rev i sed ) ” ;ex : e d i t o r [

ex : f u l l n a m e ” Dave B e c k e t t ” ;ex : homePage <h t t p : / / p u r l . o rg / n e t / d a j o b e />

] .

2.2. COMPRESION E INDICES 7

Normalmente estas serializaciones pueden comprimirse con metodos genericos decompresion, generando ası ficheros binarios de menor tamano. Por ejemplo podemos uti-lizar GZIP o BZIP2 por ser algoritmos bastante comunes. Podremos comprimir y des-comprimir al vuelo el fichero cuando necesitemos acceder a el (utilizando un stream).

2.2. Compresion e IndicesLa compresion consiste en encontrar las redundancias en el contenido de un mensaje

y codificarlas de manera que se minimice el numero de bits necesarios para representarlo.Para ello sera necesario construir un modelo que organice la estructura de la informacionde una manera adecuada para posteriormente codificarla en un espacio mas reducido.

Una de las mayores ventajas de la compresion ha sido tradicionalmente la reducciondel espacio ocupado y por tanto el ahorro de almacenamiento en disco. Con el incrementode la capacidad de almacenamiento de los discos duros y el abaratamiento de coste por biteste factor ha ido perdiendo peso, pero no por ello la compresion deja de ser importante.Una de las caracterısticas fundamentales es que la velocidad de acceso a almacenamientosecundario no ha evolucionado tan rapidamente como lo han hecho los procesadores ylas memorias de acceso aleatorio. Por lo tanto, si almacenando cierta informacion com-primida en disco utilizamos 2 bloques en lugar de 4, tardaremos la mitad de tiempo enleerlos de nuevo. Esto ocurre suponiendo que el procesador sea capaz de descomprimiresa informacion en lınea, lo cual es cierto en la mayoria de los casos debido a la diferenciade velocidad entre el procesador y el disco.

La compresion tambien cobra gran importancia en la transmision de datos a travesde redes de computadores. Permite reducir la cantidad de ancho de banda necesaria paratransmitir cierto mensaje y por lo tanto disminuye el trafico de la red. Por otro lado, fijadoun ancho de banda constante, permite enviar mas cantidad de informacion incrementandoası el rendimiento (throughput) y disminuyendo la latencia.

Existen fundamentalmente dos tipos de compresores: sin perdidas (lossless) y conperdidas (lossy). Estos ultimos tienden a obtener unas mejores tasas de compresion dadoque la informacion que se descomprime no coincide exactamente con la originalmentecomprimida. La aplicacion de los compresores con perdida se lleva a cabo sobre los datoscuya naturaleza permite renunciar a parte de su informacion sin que esto suponga unaperdida cualitativa en el mensaje transmitido. Basicamente, la compresion con perdida seaplica a datos de naturaleza audiovisual (imagenes, video o sonido) dado que no afectasustancialmente a la recepcion del mensaje por parte de un ser humano. Sin embargo estaperdida no es aceptable en otras areas en las que se precisa que el contenido descom-primido coincida exactamente con el mensaje original. RDF es un caso eminentementesin perdidas, aunque puede considerarse que el orden de los triples no es relevante y enocasiones se obvia.

Normalmente se utiliza redundancia estadıstica para comprimir sin perdidas. Se estu-diara la distribucion de probabilidad de los elementos para encontrar cuales se repiten conmas frecuencia.

Por ejemplo encontramos dos tipos fundamentales de redundancia:

Redundancia en la codificacion: Los compresores centrados en la eliminacion deeste tipo de redundancia se basan en que el alfabeto utilizado cuenta con una distri-

8 CAPITULO 2. CONOCIMIENTOS PREVIOS14 2. Conceptos Basicos

Fuente Canal

Codificador

Descodificador

Modelo

Modelo

Transmisor de Shannon

Receptor de Shannon

Predicción

Predicción

Mensaje Mensaje

MensajeMensaje

Error

Error

Figura 2.1: Paradigma de la compresion/descompresion formulado por Shannon.

Modelado. Inicialmente, el modelado de una fuente de informacion requiere, definir que seconsidera como sımbolo, de acuerdo a sus propiedades especıficas. Un sımbolo es, generalmente,un caracter unico, un numero finito de caracteres o una palabra de texto definida como unasecuencia maximal de caracteres alfanumericos o no alfanumericos. El conjunto de todos estossımbolos se denomina alfabeto fuente. Los mensajes emitidos por una fuente de informacion estanformados por la combinacion de los sımbolos contenidos en dicho alfabeto fuente. Aunque cadamensaje tiene unas caracterısticas particulares, las reglas generales consideradas por la fuentede informacion facilitan la identificacion de regularidades genericas en los mensajes. Este es elobjetivo principal del modelo: obtener una representacion estadıstica del mensaje que facilite elaprovechamiento de estas regularidades en la mejora de la efectividad del compresor.

Codificacion. La etapa de codificacion establece la representacion, en el mensaje comprimido,de cada sımbolo modelado de acuerdo a sus propiedades en el mensaje original [BWC89]. Elobjetivo principal del codificador es encontrar una representacion efectiva de la informacionque el modelo no es capaz de predecir o representar implıcitamente. Basicamente, cada sımboloemitido en la fuente genera un nuevo sımbolo en el modelo, de forma que la discrepancia existenteentre ambos es lo que el codificador representa de una forma compacta.

Esta sencilla caracterizacion, en dos etapas, muestra como un compresor requiere obtener unmodelo de la fuente sobre el que posteriormente aplicar una codificacion efectiva para la infor-macion que este representa. La combinacion de ambas etapas da lugar a numerosas tecnicas decompresion, especıficas para diferentes fuentes de informacion y basadas en tecnicas de codifi-cacion particulares que aportan unas propiedades determinadas al resultado obtenido con cadauna de ellas. A continuacion se profundiza en las propiedades de una fuente de informacion.

2.3.1. Fuentes de informacion

Una fuente de informacion discreta emite mensajes basados en la sucesion de sımbolos proce-dentes de un conjunto finito de eventos denominado alfabeto fuente (A). La notacion

Figura 2.2: Paradigma de Shannon de un modelo compresor/descompresor.

bucion de probabilidad no uniforme. Por ejemplo en el lenguaje castellano algunossımbolos ocurren con mayor frecuencia que el resto (Por ejemplo las vocales apa-recen con mayor probabilidad que la w). Por lo tanto si utilizamos un codigo de bitsmas corto para las vocales estaremos ahorrando espacio en el mensaje final. Paraello Huffman [25] propuso un algoritmo de compresion basado en codigos de lon-gitud variable que afronta esta redundancia permitiendo una representacion efectivade los sımbolos mas frecuentes. Al tratarse de un algoritmo sin perdidas, se puederecuperar el codigo original intacto.

Redundancia en la secuencia de aparicion: Los compresores que identifican yexplotan este tipo de redundancia buscan correlaciones entre los sımbolos ante-riormente utilizados y los siguientes. Por ejemplo en el mismo ejemplo anteriordel lenguaje castellano, la probabilidad de que la letra m preceda a la p es muchomayor que de que sea la letra n la que preceda a la p. Este tipo de correlaciones de-rivadas de las reglas linguısticas sobre las que se construyen los mensajes, anadenuna redundancia que puede ser detectada y eliminada. Existen diferentes algorit-mos de naturaleza muy diferente como RLE, LZW o PPM, que explotan este tipode redundancia.

En la figura 2.2 podemos observar el esquema de un compresor/descompresor tıpico.A la izquierda podemos observar la fuente de mensajes en plano. En la parte superiorse representa el compresor, compuesto por un modelo que reorganiza la informacion deentrada utilizando un algoritmo de compresion para realizar una prediccion, que poste-riormente debera ser codificada. Una vez generado el mensaje comprimido se enviara porel canal. En la parte inferior de la figura podemos ver el efecto complementario. El deco-dificador convierte el codigo comprimido nuevamente generando el mismo modelo, y se


extrae el mensaje original.La etapa de modelado de la fuente se puede realizar de tres grandes formas diferen-

ciadas:

Modelado estatico: Tanto el compresor como el descompresor toman como pun-to de partida la misma distribucion de probabilidad prefijada. Esta distribucion seconstruye sobre una vision generica de los datos, asumiendo que todos los mensa-jes van a contar con unas caracterısticas comunes y similares a las precalculadas.La eficiencia de este metodo dependera en gran medida de la similaridad del men-saje comprimido con la distribucion prefijada. Por ejemplo los estandares JPEG yMPEG-4 Layer 3 proporcionan una distribucion prefijada de coeficientes espectra-les calculada considerando caracterısticas cognitivas del ser humano.

Modelado semi-estatico: Proporciona un modelo diferente para cada mensaje deentrada. Esto se realiza en dos fases, en la primera se realizara un analisis estadısti-co de la entrada para construir la distribucion de frecuencias, y posteriormente setransmitira el mensaje en el nuevo codigo. Esta distribucion debera ser enviada aldescompresor antes que el mensaje, y este la utilizara posteriormente para descom-primir el mensaje de nuevo a su version original. Cabe destacar que una vez genera-da la distribucion de probabilidad inicial, esta se mantendra inalterada para el restodel mensaje, de ahı su nombre semi-estatica.

Modelado adaptativo: Este tipo de modelado, al igual que el anterior, utiliza unmodelo diferente para cada tipo de mensaje. El compresor mantendra un modeloen memoria que ira actualizando cada vez que aparece un nuevo sımbolo en la en-trada, codificandolo segun el estado actual del modelo. Esto hace que un sımbolode entrada pueda ser codificado de manera diferente a medida que el modelo se vaactualizando. Esto permite que el algoritmo sea muy flexible, adaptandose en todomomento a la entrada. Por ejemplo si en un mensaje un sımbolo aparece muchasveces al principio pero al final apenas aparece, al principio se utilizara un codi-go mas corto pero el sistema terminara por cambiar su codigo por otro mas largo,adaptandose de esta manera a la entrada. Otra ventaja es que el descompresor puedea su vez ir actualizando el modelo a medida que genera la salida, por lo tanto no esnecesario que el emisor transmita de manera explıcita este modelo. Como inconve-niente de este metodo de modelado podemos citar que el proceso de adaptacion ycalculo del modelo puede requerir mayor potencia de computo.

Ademas de los metodos de compresion anteriores, existe un gran metodo conocidocomo basado en diccionario. Este tipo de metodos consiste en construir un diccionariode frases que se repiten, de manera que posteriormente en el mensaje pueden substituirsepor una referencia al diccionario. La efectividad de estos metodos se basa en que frasesvamos a representar en el diccionario. Aunque en este tipo de metodos no se distingueexplıcitamente entre las fases de modelado y codificacion, sı que se puede diferenciarentre la fase de construccion del diccionario y la de reasignacion de referencias.

Una vez reorganizada la informacion usando cualquier tipo de modelado, deberemosasignar codigos para representar mediante bits los diferentes sımbolos del alfabeto, etapaconocida como Codificacion. La idea general es eliminar la redundancia en los codigos

10 CAPITULO 2. CONOCIMIENTOS PREVIOS3.3. Codificacion 45

Figura 3.5: Ejemplo de codificacion Hu!man.

La figura 3.5 muestra el ejemplo de construccion de un codigo de Huffman para la mismadistribucion de sımbolos considerada en la figura anterior. En este caso, la longitud media depalabra coincide con la obtenida por el codigo de Shannon-Fano (1, 75 bits/sımbolo). En elprimer paso se agrupan los sımbolos !5 y !6 obteniendo un nuevo grupo con probabilidad 0, 09;el segundo paso une !3 y !4 dando lugar a un grupo con probabilidad 0, 13. En el tercer pasopuede observarse la union el grupo de probabilidad 0, 09 con el sımbolo !2 obteniendo un grupode probabilidad 0, 20. El proceso continua hasta la fusion final de !1 con el grupo que acumulalas probabilidades de todos los sımbolos restantes en el alfabeto fuente.

En este ejemplo se decide asignar el bit 0 al grupo mas frecuente y el bit 1 al menos frecuente.Sin embargo, esta es una decision arbitraria y la asignacion podrıa llevarse a cabo con cualquierotra polıtica. Esto supone que, para un alfabeto de n sımbolos distribuidos de acuerdo a unconjunto de frecuencias determinado, existen 2n!1 codigos de Huffman diferentes, todos ellos deredundancia mınima.

Schwartz y Kallick [SK64] plantean una clase de codigos de Huffman, denominados codigoscanonicos, cuyas propiedades matematicas facilitan su almacenamiento y manipulacion. Se diceque un codigo de Huffman es canonico si posee la propiedad de secuencia numerica:

- Las palabras de codigo se organizan siguiendo un orden decreciente de tamano de acuerdoal conjunto de longitudes obtenidas por el algoritmo de Huffman y manteniendo un ordenlexicografico creciente para las palabras del mismo tamano.

- Todos los codigos de un determinado tamano son numeros consecutivos.

- Sea c1 la ultima palabra de codigo de longitud l bits (o de mayor valor numerico) y c2 laprimera cuya longitud es l ! 1 bits (o de menor valor numerico); entonces c1 = B(c2 ! 1),donde B representa la base numerica utilizada para la generacion del codigo de Huffman.

La ventajas de este tipo de codificacion se estudian de forma detallada en [HL90]. Otrostrabajos interesantes al respecto de este tipo de codigos pueden ser encontrados en [MT97,LM07]. Notese que la implementacion del codigo de Huffman orientado a bit planteada porMo!at y Turpin se utiliza como base el desarrollo de algunas de las tecnicas planteadas en lapresente tesis.

Figura 2.3: Ejemplo de un arbol de Huffman para un alfabeto σ = {σ1 . . . σ6} junto conlas probabilidades de aparicion de cada uno de los nodos.

suponiendo que existe una distribucion de probabilidad P no uniforme en la aparicionde sımbolos del alfabeto. Por lo tanto, se asignaran codigos mas cortos de menos bits aaquellos sımbolos que sean mas frecuentes, dejando codigos mas largos para aquellos quelo son menos. Existen dos algoritmos principales para obtener estos codigos:

La codificacion de Huffman planteada por David Huffman en 1952 [25], que esla primera solucion optima en lo que respecta a codigos de redundancia mınima.Ademas en su trabajo original propone un algoritmo para obtener esta codificacion.El algoritmo parte de una lista de n sımbolos del alfabeto junto con sus frecuenciasde aparicion. En caso de no contar con ellas sera necesaria una primera pasada deconteo o contar con una distribucion de probabilidad general, como por ejemplo lasprobabilidades de aparicion de caracteres en texto ingles. El algoritmo construira unarbol binario de abajo a arriba (bottom-up), donde cada nodo hoja representa unode los sımbolos del alfabeto. Para ello se iran tomando sucesivamente los dos nodoscon menor frecuencia, y se agruparan creando un nuevo nodo, asignando como hijoizquierdo y derecho (0 y 1) los dos nodos originales. El proceso se repetira hastaque no existan nodos huerfanos. Con esto se consigue que los nodos con menos pro-babilidad queden a una mayor profundidad en el arbol, y los nodos mas probablesqueden mas cerca de la raız. En la figura 2.3 podemos observar un ejemplo.

A partir del arbol podemos realizar las dos operaciones:

• A partir del sımbolo del alfabeto, obtener su codificacion. Partiremos del nodode ese sımbolo en el arbol, y lo navegaremos hacia arriba, concatenando 0 o 1segun sea hijo izquierdo o derecho

• A partir de la codificacion, obtener el sımbolo del alfabeto. Partiremos de laraız, y navegaremos el arbol siguiendo el hijo izquierdo o derecho segun cada

uno de los bits de la entrada hasta que nos encontremos en un nodo hoja, esesera el sımbolo buscado.

En la practica por cuestiones de eficiencia normalmente se construye una tabla apartir del arbol y se descarta el arbol.

La codificacion aritmetica utiliza numeros en el intervalo [0, 1) para codificar cadauno de los sımbolos del alfabeto. Tambien utiliza la frecuencia de aparicion decada sımbolo para ir dividiendo ese intervalo en segmentos teniendo en cuenta laprobabilidad de aparicion, y posteriormente se utiliza un numero de precision fijapara representarlo. La codificacion aritmetica en general es algo mejor que la deHuffman, pero no es tan utilizada ya que requiere mayor potencia computacionalpara calcularla, ademas de estar protegida por patentes.

A continuacion detallamos algunas de las implementaciones mas importantes utiliza-das:

GZIP [28] utiliza una variante del algoritmo LZ77 desarrollados por Lempel yZiv [41] a finales de los anos 70. Su caracterıstica fundamental es el uso de unaventana deslizante de tamano finito que se utiliza como historico de procesamientopara la codificacion de los siguientes sımbolos en el mensaje de entrada (llamadobuffer de prevision o lookahead buffer). La capacidad de compresion radica en quealgunos de los sımbolos de entrada ya habran aparecido anteriormente y por tantono es necesario representarlos de nuevo, sino indicar una referencia a la aparicionanterior dentro de la ventana deslizante. La codificacion se realiza utilizando ternasde la forma < p, l, s >, el valor p indica la posicion de la ventana deslizante en laque se ha encontrado una secuencia en el buffer de prevision, indicada como posi-cion relativa entre la posicion actual y la anterior. El valor l indica la longitud de lasecuencia encontrada, y s representa el sımbolo siguiente en el buffer de prevision.Cuando se encuentra una tripleta, se anade a la salida la secuencia encontrada en laventana con la longitud adecuada y se desplaza la ventana. En caso de que el sımbo-lo no se encuentre en la ventana, se emitira una tripleta con los valores p y l nulos, yel valor s indicara el nuevo sımbolo. La eficacia de los compresores LZ77 dependeen gran medida del tamano de ventana seleccionado. Una ventana deslizante mayorhara que sea mas probable encontrar repeticiones de la secuencia actual, pero tam-bien necesitara mas bits para codificar la posicion relativa, ademas de requerir masmemoria y capacidad de procesamiento en el compresor y descompresor. Normal-mente se utilizan 12 bits para codificar la posicion relativa y 4 para la longitud de laterna, constituyendo una ventana de 4096 posiciones con una longitud maxima de16. GZIP se popularizo por sustituir a la utilidad compress de Unix, y ser utiliza-do junto con la utilidad tar para empaquetar archivos. No debe confundirse con lautilidad ZIP, que aunque tambien esta basada en LZ77, no es compatible con GZIP.

BZIP2 [35] es la evolucion natural de compresion en los entornos Unix. Se basa enla transformada de Burrows-Wheeler para crear una reordenacion de los sımbolosde entrada que hace que las repeticiones aparezcan en series de sımbolos en lugarde aislados. Esta serie de sımbolos posteriormente seran codificados con un algorit-mo llamado traer al frente (move to front) junto con Huffman [25]. Este algoritmo


lo que hace es mantener una pila de los sımbolos recientemente usados, y utilizarcomo codificacion el ındice dentro de esta pila. La pila se ira actualizando a medidaque se va consumiendo la entrada. El algoritmo de traer al frente se compenetra biencon Burrows Wheeler porque este hace que haya muchas secuencias con el mismosımbolo, que seran codificadas con ceros seguidos. Ademas cabe destacar que tantoel algoritmo de traer al frente como la transformada de Burrows-Wheeler son ambosrevocables, pudiendo volver al mensaje original sin mas que deshacer los cambios,este hecho quizas no es tan intuitivo en la transformada de Burrows-Wheeler peroesta demostrado por los autores en su propuesta original. BZIP2 primero divide elmensaje original en bloques de hasta 900KB, y los procesa individualmente. En ca-so de que el mensaje de entrada no tenga un tamano multiplo del tamano de bloque,se rellenara con ceros hasta que lo haga. El proceso de compresion es bastante maslento que en GZIP, ya que para aplicar la transformacion de Burrows-Wheeler senecesitan hacer varias ordenaciones de cadenas, pero el proceso de descompresiones mucho mas rapido. Otra caracterıstica interesante es la posibilidad de paralelizarel algoritmo. Existe una version de BZIP2 que permite enviar un bloque diferen-te a cada procesador, ya que son completamente independientes, consiguiendo unaescalabilidad casi lineal respecto al numero de procesadores.

Re-Pair [27] es un compresor basado en diccionario gramatical, donde cada frasese representa como una jerarquıa binaria donde una frase se construye a partir dedos subfrases constituyentes de nivel inferior. La mayor limitacion de Re-Pair esque necesita que el mensaje se encuentre por completo en memoria principal parapoder optimizar el modelo. A cambio Re-Pair tiene una alta velocidad de descom-presion (solamente hay que navegar por el arbol binario) y una alta efectividad paradatos tan dispares como texto plano o secuencias biologicas. Ademas permite acce-der directamente a subfragmentos del texto, siendo muy util para recuperacion deinformacion. El algoritmo consiste en ir recorriendo la secuencia de entrada buscan-do pares (bigramas) que aparecen mas de una vez, creando un nuevo sımbolo pararepresentarlos como tal. Se realiza de manera recursiva una y otra vez hasta que lasalida no contiene ningun bigrama repetido. La salida del compresor sera esta se-cuencia de sımbolos donde ningun bigrama aparece repetido y una serializacion dela gramatica empleada.

PPM [32] o Prediction by Partial Matching es una propuesta de modelo adaptativoestadıstico que trata de predecir cual sera el sımbolo siguiente en la secuencia deentrada a partir de los k anteriores, donde k se denomina orden. Posteriormente seutilizara una codificacion adecuada, de manera que el sımbolo mas probable utilicemenos bits que uno que sea menos probable. Por ejemplo en el caso del idioma cas-tellano, en un PPM de orden 2, podrıamos adivinar que despues de la secuencia ques muy probable que aparezca una e y utilizaremos un solo bit para representarlo. Enla practica se utilizan ordenes finitos, alrededor de k = 10. Ademas sera necesariodelegar en un orden de nivel inferior si no se han encontrado apariciones anterio-res de esa secuencia. En el ejemplo anterior si qu no ha aparecido anteriormente,podemos intentar predecir cual suele seguir solamente a la u. Tambien es necesariodecidir que hacer cuando ni siquiera ha aparecido ninguna vez ese sımbolo, dan-


do lugar a diversas variantes de PPM. Uno de los mayores problemas de PPM esque necesita mucha memoria para mantener las estadısticas del modelo en ordenessuperiores, y gran capacidad de procesamiento para calcularlas, pero a cambio con-sigue eficiencias muy buenas, de entorno al 20 − 30 % en lenguaje natural usandocaracteres como alfabeto.

2.2.1. Efectividad de los compresionPara poder comparar metodos de compresion, deberemos analizar los resultados desde

el punto de vista de la efectividad y eficiencia. El primero se refiere a la capacidad delcompresor de reducir el mensaje, comparando el tamano del mensaje original en plano conel resultado comprimido. Por ejemplo, sea un mensaje original de tamano u comprimidoen tamano n, y con c bits para representar el alfabeto en el lenguaje original, podemosdefinir las siguientes medidas [30]:

Tasa de compresion: Presenta una tendencia creciente con la mejora de la efectivi-dad del compresor. Se calcula como:(

1− n

u

)(2.1)

Numero de bits por sımbolo (BPS): Indica el numero de bits necesarios para larepresentacion de un sımbolo del mensaje original y se calcula mediante la siguienteformula:

c× n

u(2.2)

Razon de compresion: Mide el tamano proporcional del mensaje comprimido res-pecto al tamano del mensaje original:

100× n

u(2.3)

Factor de compresion (X:1): Indica la proporcion existente entre el tamano delmensaje sin comprimir y el tamano del resultado comprimido. Este valor se repre-senta tıpicamente de la forma X:1 donde X es un entero que se calcula:

X =u

n(2.4)

Entropıa de la informacion: Aunque no es tan util experimentalmente, a veces esnecesario conocer la entropıa del mensaje de datos. La entropıa analiza la cantidadde informacion que aporta cada sımbolo a partir de su probabilidad de informa-cion, asumiendo que los sımbolos que aparecen pocas veces aportan mucha masinformacion que los que se repiten mucho. La entropıa viene definida como:

I(xi) = log21

pi= −log2 pi (2.5)


2 Text search approaches

2.1 Compression assessment

Before going through the details of the specific datastructures, we need to define some of the basic con-cepts and how to measure the solutions.

The aim of a structure is, given a sequence ofsymbols T of size n, find some substrings Sij con-tained within the string.

T = {t0, t1, . . . , tn} (1)

Sij = {ti, ti+1 . . . tj} / 0 ≤ i ≤ j ≤ n, (2)

There are three typical operations that are per-formed against text succinct data structures [13]:

• exist(i,T). Given a substring i, determinewhether the substring occurs or not within thetext T .

• count(i,T). Count the number of occurrencesof the substring i within the text T .

• enum(i,T). Enumerate all the positions wherethe substring i appears within the text T .

We need some measurements to evaluate thegoodness of the different solutions:

• Entropy of the information: It aims atdefining how probable are the symbols of thealphabet/vocabulary, assuming that less prob-able symbols provide more information thanmore probable ones as defined by:

I(xi) = log2

1

pi= − log2 pi (3)

The objective of compression is reducing theredundancy of the information, i.e. minimiz-ing the entropy by giving the same probabilityto all symbols. The entropy can be used tomake a theoretical analysis of the methods ofcompression, but there are works on how to useexperimental entropy measurements to evalu-ate the quality of a compressor [7].

• A most common approach to evaluate andcompare compression algorithms experimen-tally is by using the compression ratio whichcompares the size of the compressed documentto the original in bytes:

Ratiocompression =Sizeoriginal

Sizecompressed(4)

0 0 1 1 0 0 1 1 1 0 1 0 1 0 0 0

select(B,1) = 3 select(B,7) = 13

rank(B,3) = 1 rank(B,10) = 5

Figure 1: Example of rank and select operationswithin a bit sequence

• Space saving. The space saving is the pro-portion of space saved:

Saving = (1 − Sizecompressed

Sizeoriginal) (5)

• Number of bits per symbol(BPS). Number ofbits to represent each symbol of the input. Itdepends on how we interpret the input. If forexample we consider the input as a sequenceof bytes, each input symbol uncompressed willoccupy 8 bits. Conversely, if we consider eachinput symbol a word, we require more bits torepresent each word in raw format.

2.2 Rank and Select on binary se-quences

Let’s consider we have a sequence of n bits, calledB[1, n]. We define the rank and select [10] as:

• rankb(B, i): Number of occurrences of bit bwithin B[1, i].

• selectb(B, i): Where does the bit b occurwithin B for the i-th time.

As we can see in the figure 1, rank and selecthave opposite meaning. The rank operation findshow many ones appear up to the supplied positionincluded, whereas select finds the position where anumber of ones have occurred.

The advantage of using rank and select is thatthere are efficient ways of storing the bitmaps toanswer these operations in constant time. The moststraightforward way would be storing every answerin O(n log n) space, but there are ways of doing itin n + o(n). If the bitmap is very sparse we caneven compress the bitmap to save even more space.

2

Figura 2.4: Ejemplo de operaciones rank y select en un mapa de bits.

2.2.2. Mapas de bits, rank y selectUna estructura de datos interesante desde el punto de vista de la compresion son los

mapas de bits. Por ejemplo podemos contar con una secuencia de n bits llamada B[1, n].Cada bit podra tener dos valores, 0 o 1 con un significado asociado. Sobre esta secuenciaB definiremos dos operaciones:

rankb(B, i): Numero de ocurrencias del bit b en la subsecuencia B[1, i].

selectb(B, i): Lugar donde aparece el bit b por i-esima vez.

Como se puede observar en la figura 2.4, las operaciones rank y select tienen un sig-nificado opuesto. La operacion rank encuentra cuantos unos aparecen hasta la posicionindicada (con esta posicion incluida), mientras que select encuentra la posicion donde unnumero determinado de unos han ocurrido.

La mayor ventaja de usar rank y select es que existen maneras eficientes de almacenarlas respuestas a estas operaciones en tiempo constante. La manera trivial serıa almacenaresta informacion en espacio O(nlogn), pero existen maneras mas eficientes que permitenhacerlo en n+ o(n). Si el mapa de bits es muy disperso con una cantidad muy grande deunos respecto a ceros o viceversa, existen incluso estructuras de datos y algoritmos quepermiten comprimir la secuencia para ahorrar aun mas espacio.

2.2.3. Estructuras de datos SucintasUna de las areas de investigacion en compresion mas activa en la actualidad es la

de las estructuras de datos sucintas. Son estructuras de datos que utilizan conceptos decompresion para representar la informacion estructurada de manera compacta, utilizandoel menor numero posible de bits, permitiendo codificar listas, arboles o incluso grafos.

La caracterıstica mas importante es que estas estructuras de datos ocupan menos es-pacio, tanto en memoria principal como en almacenamiento secundario, pero a su vez nos


^BANANA@@^BANANAA@^BANANNA@^BANAANA@^BANNANA@^BAANANA@^BBANANA@^

ANANA@^BANA@^BANA@^BANANBANANA@^NANA@^BANA@^BANA^BANANA@@^BANANA

BNN^AA@A^BANANA@

Input Output

Rotations Sorted Rotations

Figure 2: Burrows-Wheeler transform process onthe string ”BANANA”.

2.3 Burrows-Wheeler Transform(BWT)

The Burrows-Wheeler transform [11] is not a com-pression algorithm, just an algorithm to obtain aspecific permutation of the input. Therefore, it willtake the same space as the original (plus two sym-bols to specify the start and end). Its major advan-tage is that if the original string had several sub-strings that occurred often, then the transformedstring will have several places where a single char-acter is repeated multiple times in a row. This isuseful for compression, since it is usually easier tocompress a string that has runs of repeated charac-ters by techniques such as move-to-front and run-length encoding.

The transform is done by sorting all the rota-tions of the text, then taking the last column. Youcan see the process for the text ”BANANA” in thefigure 2.

Obviously, there exists an inverse BurrowsWheeler transform that given the output string”BNNˆAA@A” gives back the original ”BA-NANA”. It basically starts with an empty tableand at each step appends the transformed stringto the last column and sorts all rows. When per-formed n times, the original string will be the rowthat ends with the termination character.

The implementations of the Burrows-Wheeler

!"#$%#&%'&()&(*($"#"+,$Binary tree: each node has twopointers to its leftand right children

An n-node tree takes2n pointers or 2n lg n bits(can be easily reduced to n lg n + O(n) bits).

Supports finding left child or right child of a node (in constant time).

For each extra operation (eg. parent, subtree size) we have to pay, roughly, an additional n lg n bits.

x

xxxx

x xx x

Figure 3: Binary tree using traditional two-pointerimplementation

transform do not need to represent the full tableto perform the transformation (that would requiren2 space), but instead they use pointers to the orig-inal string.

One of the most famous examples of Burrows-Wheeler implementation is bzip2 [1]. It splits theinput in block of a specified size (between 100k and900k) and applies BWT, move-to-front and Huff-man encoding.

3 Succinct data structures

3.1 Succinct binary tree

Let’s start with the example of a binary tree with nnodes. Despite it is not intended for text, it is easyto represent it in a compact way so it can providean underlying idea on how succinct data structuresrepresent the information.

The traditional implementation gives each nodetwo pointers to refer to its children, therefore need-ing 2n pointers or 2n log n bits as seen in figure 3.The structure supports finding the left and theright child in constant time, just by following thepointer. Without extending this structure, addi-tional operations like finding the parent or calcu-lating a sub-tree size would require n log n time.

We can use a heap-like notation to represent pre-vious binary tree [12]. If we label internal nodeswith 0 and leaves with 1, by traversing the tree inlevel order we can generate the following string:

11110110100100000

3

Figura 2.5: Ejemplo de transformada de Burrows-Wheeler sobre la cadena “BANANA”.

permiten realizar busquedas y accesos a partes individuales de la informacion. Por lo tantoson ideales para almacenamiento y recuperacion de informacion. Como se ha mencionadoanteriormente, no solo es relevante el ahorro de espacio, sino ademas la importante mejo-ra de velocidad asociada a la necesidad de leer menos bloques de disco. Ademas algunasde estas estructuras se organizan de manera que los ındices principales de primer nivel semantengan en memoria principal, accediendo aun a menos bloques del disco.

2.2.4. Transformada de Burrows-WheelerLa transformada de Burrows-Wheeler no es un algoritmo de compresion como tal,

sino que se trata solamente de un algoritmo que permite obtener una permutacion de laentrada. Por lo tanto, la salida ocupara exactamente el mismo espacio que el original (condos sımbolos adicionales para indicar el inicio y el final). Su mayor ventaja es que sila cadena original tiene varias subcadenas que ocurren frecuentemente, entonces en latransformada aparecera el mismo caracter muchas veces seguidas. Esto es util de cara a lacompresion ya que es sencillo comprimir estas secuencias de caracteres seguidos (runs)con algoritmos de tipo move-to-front y run-length.

La transformacion se realiza ordenando todas las rotaciones del texto, siendo la salidadel algoritmo la ultima columna. Se puede observar el proceso en la figura 2.5, donde laultima columna se ha marcado en negrita para explicitar la salida.

Evidentemente existe una inversa de la transformada, que permite volver a la cadenaoriginal a partir de la salida de la transformacion. En el ejemplo serıa capaz de devolver laoriginal “BANANA” a partir de la salida “BNNAA@A”. Este proceso de inversa no es tanevidente como la propia transformacion, pero basicamente consiste en empezar con una


tabla vacıa de n × n, donde n es el tamano de la cadena. En cada paso se va anadiendoa la ultima columna la cadena transformada y se reordenan todas las filas. Cuando se haefectuado este proceso n veces, la cadena original sera aquella en el que el caracter de finde cadena aparezca en la ultima posicion.

Las implementaciones reales de Burrows-Wheeler no necesitan representar la tablaentera para efectuar la transformacion o la inversa ya que eso requerirıa un tamano deorden n2, sino que mantienen solo la cadena original junto con una lista de punteros quevan actualizando.

Como se ha mencionado anteriormente, uno de los ejemplos mas famosos de usode la transformada Burrows-Wheeler es el de BZIP [35], aunque tambien existen otrasaplicaciones para campos muy diversos a parte de la compresion de texto, como puede serel de compresion de secuencias de ADN o proteınas.

2.3. Herramientas estadısticas

2.3.1. Analisis exploratorio de DatosEl objeto de este trabajo es analizar los datos RDF para conocer sus caracterısticas de

cara a la compresion. A priori no conocemos nada de su comportamiento, ni contamoscon hipotesis prefijadas que deseemos probar o refutar. Por lo tanto las caracterısticas delestudio seran especıficas. El area de la estadıstica que se encarga de analizar datos demanera general se denomina Analisis exploratorio de datos, y propone una aproximacioncon serie de pautas que permiten extraer hechos o hipotesis de los datos para su posteriorcomprobacion, de manera que podamos obtener conocimiento mas detallado y de masalto nivel de los datos. Se utilizan la estadıstica y los graficos como herramientas para po-der encontrar estructuras, variables importantes, comportamientos, estructuras y tambiencasos extranos (outliers).

Puede entenderse el analisis de datos como un proceso con una serie de fases, a saber:

Diseno del experimento. En esta fase se establecen los objetivos del estudio yque resultados pretendemos obtener. Si se trata de un experimento controlado, de-beremos disenar cuidadosamente las condiciones bajo las que vamos a conducirel experimento. Normalmente no podremos estudiar la poblacion completa, y de-beremos tomar una muestra lo suficientemente grande como para que el estudiotenga potencia estadıstica, pero que sea lo suficientemente pequeno como para queel coste sea reducido y los datos tratables. Tambien deberemos establecer que pro-piedades van a ser interesantes para nuestro estudio y por lo tanto que variablesvamos a medir y almacenar. No siempre nosotros podremos disenar el experimen-to, en ocasiones ya contamos con una serie de datos y deberemos analizarlos, perosiempre buscando unos objetivos concretos.

Recopilacion de datos. Una vez disenados los experimentos, se procede a la eje-cucion de los mismos y a la toma de datos. En el caso del ambito de ciencias dela computacion experimentales se suelen ejecutar artefactos software que ejecutanalgoritmos sobre los datos y generan una serie de datos en crudo, resultado de losprocesos de computacion.

2.3. HERRAMIENTAS ESTADISTICAS 17

Limpieza de datos. Una vez recopilados los datos, se hace una limpieza inicial. Enesta fase eliminaremos variables no necesarias, buscaremos mediciones erroneas ono relevantes y las eliminaremos. Normalmente se generan muchos mas datos de losque son relevantes para los estudios, y es importante saber descartar adecuadamentede manera objetiva lo que no es relevante, pero sin descartar datos utiles. Tambiengeneraremos otras variables nuevas a partir de las anteriores, por ejemplo puede queno nos interesen las coordenadas del raton del usuario en pantalla en cada momento,sino la distancia recorrida por el mismo, o el tiempo en reposo. En ocasiones hayvalores ausentes y deberemos decidir que hacer con ellos, si incluirlos en el estudio,volver a recopilarlos, o estudiar por que estan ausentes. El resultado de esta fase sedenomina Datos de Salida, que ya podran ser utilizados para los distintos estudios.

Analisis inicial de los datos. En esta fase se presentan los datos ya organizados yse generan estadısticas y graficos que nos muestren los primeros indicios. Por ejem-plo tomaremos medidas de tendencia central y dispersion (Media, mediana, desvia-cion tıpica, rango, cuartiles, mınimo y maximo), tambien representaremos variablesgraficamente en histogramas y graficas de dispersion. A la vista de las graficas dedispersion tambien podemos empezar a buscar correlaciones entre variables, tantolineales como no lineales (exponencial, logarıtmica, potencial).

Test de hipotesis. A la vista de los resultados anteriores, ya podemos empezar aentender de mejor manera los datos, y en el caso de analisis exploratorio empezar adefinir que variables son mas interesantes y empezar a proponer hipotesis sobre losdatos que podemos probar con ellos. Una vez tengamos al menos una hipotesis queprobar, utilizaremos un test para comprobar si es cierta o no. Normalmente conside-raremos la hipotesis nula y comprobaremos estadısticamente la probabilidad de queocurra fortuitamente. En ciertos casos sera necesario dividir la muestra en un con-junto de entrenamiento y prueba, o incluso disenar un experimento completamentenuevo para comprobar la hipotesis.

Extraccion de resultados e informe. Una vez que hayamos planteado la hipotesisy hayamos comprobado si se cumple o no, deberemos proceder a recopilar las con-clusiones de nuestro estudio, buscando una explicacion o causa de la misma. Porejemplo si comparamos el algoritmo GZIP comprimiendo texto plano y binarios,y observamos que comprime mucho mas el texto, podemos buscar una explicacioncalculando la entropıa de cada una de las fuentes. El informe final que se generadebera incluir las condiciones del experimento, los resultados obtenidos, como sehan procesado, que tipos de tests se han utilizado para que hipotesis y como hemosllegado a las conclusiones

2.3.2. Estadıstica descriptiva

La estadıstica descriptiva permite resumir las caracterısticas principales de una co-leccion de datos de manera cuantitativa. Su objetivo es resumir el conjunto de datos envalores numericos sin utilizar probabilidades, y es una de las bases del analisis cuantita-tivo de datos. Hay que tener en cuenta que estos valores no tienen por que ser fieles a los


datos originales, perdiendo a veces detalles importantes. A pesar de esto puede utilizarsetambien para efectuar comparaciones entre conjuntos de datos similares.

Algunas caracterısticas que suelen ser interesantes en el analisis univariante de varia-bles:

Distribucion. Consiste en agrupar el conjunto de datos por valores y contar la fre-cuencia de cada uno de ellos. En el caso de variables nominales los grupos ya estanpredefinidos a priori, pero en el caso de variables ordinales puede ser necesario creargrupos por intervalos. La distribucion puede representarse graficamente utilizandoun histograma.

Tendencia Central. Trata de localizar el “centro” de una distribucion. Los estima-dores mas utilizados de tendencia central son:

• La media aritmetica es la suma de todos los valores dividido por el total. Tam-bien se conoce como el valor esperado de la variable.

• La moda es el valor mas frecuente de la distribucion.

• La mediana es el valor que deja la mitad de los casos hacia un lado y la mitadhacia el otro tras haber ordenado el conjunto de valores.

Aunque pueden tomar el mismo valor (por ejemplo para una distribucion normal),lo habitual es que tomen diferentes valores.

Dispersion. Miden como de alejadas estan las muestras de la tendencia central.

• El rango Es la diferencia entre el mayor y el menor de los valores. No se sueleutilizar demasiado por ser muy sensible a outliers.

• La varianza es la media de las desviaciones al cuadrado a la media.

• La desviacion tıpica es la raız cuadrada de la varianza, y es similar con ladiferencia de que atenua la importancia de los valores extremos.

• Los percentiles son los puntos en los que se deja un cierto porcentaje p

• Rango intercuartılico. Si definimos los cuartiles Q1 y Q3 como los puntosque dejan el 25 % de las muestras a la izquierda o a la derecha respectivamente,podemos definir el rango intercuartılico como IQ = Q3−Q1. Nos da una ideade la dispersion siendo poco sensible a los outliers.

Tambien sera interesante contar con graficas de visualizacion de datos:

Graficas de dispersion: Representan en dos ejes cada punto y respecto al x. Sonmuy interesantes cuando queremos observar la relacion entre dos variables y com-probar si existe alguna tendencia. A la vista de los datos decidiremos que modelosson mas plausibles y ajustaremos sus parametros siguiendo alguna de las tecnicasestadısticas.

Histograma: Sirve para tener una vision inicial de la distribucion de probabilidadde una variable aleatoria X . Consiste en dividir los valores posibles en intervalos ycontar cuantas apariciones hay de la variable en cada intervalo.

2.3. HERRAMIENTAS ESTADISTICAS 19

Diagrama de caja: Consiste en dibujar una caja en los valores de la mediana y loscuartiles Q1 y Q3. Permite ver no solo la zona central sino tambien la variabilidade identificar los valores extranos o outliers.

Q-Q Plot: es un metodo grafico de comparar dos distribuciones de probabilidad,representando los cuantiles de cada una de ellas respecto a la otra. Si las dos dis-tribuciones tienen la misma forma los puntos se agruparan a lo largo de una lınearecta, que no tiene por que ser y = x, dependiendo de la localizacion y la escala.

Ademas tambien necesitaremos alguna manera de conocer si existe correlacion entredos variables. Para ello lo primero sera calcular coeficientes de correlacion como Pearsono Spearman. Valores mas cercanos a 1 indicaran que existe algun tipo de relacion entrelas variables, mientras que valores casi nulos indicaran que no existe correlacion aparenteentre ellas.

Si encontramos que existe relacion, procedemos a ajustar modelos estadısticos. A lavista del diagrama de dispersion podemos identificar que modelos ajustar. Por ejemplosi los puntos se agrupan en torno a una recta, utilizaremos regresion lineal por mınimoscuadrados para encontrar la pendiente y la ordenada en el origen.

2.3.3. Power-lawMuchos fenomenos tanto naturales como originados por el hombre siguen una dis-

tribucion power-law. Por ejemplo el tamano de las ciudades, la nomina, frecuencias depalabras o magnitudes de terremotos. Todos ellos tienen una caracterıstica comun, lasmagnitudes pequenas son comunes, pero las grandes son casos muy especiales. Por ejem-plo hay pocos terremotos de gran magnitud pero existen muchos pequenos, existe muchagente con sueldos comunes pero hay pocos millonarios, hay pocas ciudades grandes perohay muchos pequenos pueblos.

Decimos que una cantidad x obedece una ley power-law[14] cuando su distribucionde probabilidad es:

f(x) = ax−k + o(x−k) (2.6)

A la constante k se la conoce como exponente o factor de escala, y la funcion o(x−k)es una funcion asintoticamente pequena de x−k.

Una caracterıstica interesante de la distribucion power-law es que es invariante en laescala, dada una relacion f(x) = ax−k, multiplicar x por un factor constante solo causaun escalado proporcional de la funcion misma c−k, es decir:

f(cx) = a(cx)−k = c−kf(x) ∝ f(x) (2.7)

El hecho anterior tambien puede observarse si tomamos logaritmos:

log(f(x)) = −klog(x) + log(a) (2.8)

Esta expresion tiene forma de relacion lineal con pendiente k. Reescalar el argumentoproduce un movimiento de la recta de arriba a abajo, pero la pendiente permanece inalte-rada. Ademas esta es una de las razones por las que las distribuciones power-law se suelenrepresentar en graficas con escalas logarıtmicas.


En la practica pocos fenomenos empıricos siguen una distribucion power-law paratodos los valores de x. Normalmente la ley power-law solo se cumple para los valores dex mayores de un cierto xmin. En esos casos diremos que la cola de la distribucion sigueuna ley power-law con funcion de probabilidad:

p(x) =k − 1

xmin

(x

xmin

)−k

(2.9)

Un caso especial de power-law, es la ley de Zipf [1], originalmente aplicada a lasdistribuciones de palabras en un idioma. La diferencia fundamental con power-law es quelos datos se ordenan de manera decreciente, y lo que se representa es el tamano y delelemento respecto a la posicion r (rank) dentro de la lista ordenada:

y ∝ r−b (2.10)

En el caso del idioma ingles, Zipf determino que b era aproximadamente igual a la unidad,siendo la frecuencia de la palabra por tanto inversamente proporcional a su posicion en elranking.

Normalmente sospecharemos que una distribucion obtenida empıricamente a partir delos datos sigue una distribucion power-law cuando al representarlo graficamente con lasdos escalas logarıtmicas obtengamos una lınea decreciente. Esta es condicion necesariapero no suficiente, comprobaremos si esto es realmente cierto siguiendo este proceso:

1. Calculando el parametro k (y xmin si fuera necesario) para construir un modelo quese ajuste a la distribucion power-law.

2. Calculando la capacidad de ajuste entre los datos y el modelo. Si el valor R2 ≥ 0,9,entonces la hipotesis es estadısticamente plausible.

Ademas de poder ajustar la recta utilizando mınimos cuadrados sobre la ecuacion(2.8), algunos autores [14] sugieren utilizar un metodo de maxima verosimilitud paraestimar el factor k con mayor exactitud.

2.4. Otros analisis de RDFAntes de realizar nuestro estudio, deberemos analizar como han abordado otros au-

tores tareas similares. Buscaremos otros analisis de caracterısticas RDF para ver comoenfocan el problema, que metodologıas han utilizado y a que conclusiones han llegado.

El primer estudio interesante es Characterizing the Semantic Web de Ding y Finin en2006 [17]. En el realizan un crawler de paginas semanticas para caracterizar sus propieda-des, recopilando miles de documentos semanticos de muchos hosts diferentes. Estudian lacantidad de documentos semanticos por Web, sus tamanos y los tiempos de actualizacion.Una caracterıstica interesante es su estimacion del numero de documentos semanticos enla Web, estableciendo un orden de entre 107 y 109. Una vez recopiladas las paginas rea-lizan un estudio del contenido semantico. Por ejemplo analizan el numero de clases ypropiedades diferentes, ası como el numero de instancias utilizandolas.

2.5. COMPRESION DE RDF MEDIANTE HDT 21

Por ejemplo existen otros trabajos que generan estadısticas de BillionTriples [24] pa-ra conocer sus caracterısticas. A ellos les interesa mas buscar conceptos de alto nivel,como por ejemplo cuantos orıgenes diferentes hay o que esquemas son mas utilizados.Ademas proponen una pagina Web interactiva hecha con Javascript para navegar por estainformacion, lo cual es una muy buena de cara a la visualizacion de la informacion.

Un trabajo interesante es el de Gil y Garcıa [23]. En el comparan la Web Semanticacon un sistema complejo, modelandolo como una red. En el determinan que el grado delos nodos sigue una distribucion Power-law, que tiene la caracterıstica de mundo pequeno,es decir que dos nodos cualesquiera estan conectados en pocos pasos, y que el coeficientede agrupamiento es alto, es decir, que la probabilidad de que dos vecinos de un nodo seantambien vecinos es alta.

Theoharis [36] analiza el RDF como un grafo buscando distribuciones power-law, perose centra mas en caracterısticas del esquema. Por ejemplo analiza los arboles generadosmediante rdf:subClass, el rango y dominio de rdf:property y la relacion entrelas clases nuevas que define una ontologıa y las importadas.

En el proyecto RDFStats [26] construyen un framework para extraer estadısticas deficheros RDF. En el destacan que su motivacion fue la falta de este tipo de herramientaspara comprender la informacion RDF. Una vez mas, se centran en caracterısticas de altonivel, como clases, propiedades e instancias OWL.

2.5. Compresion de RDF mediante HDTRDF HDT (Header-Dictionary-Triples)[19], es un formato para publicar e intercam-

biar datos RDF a gran escala. RDF HDT representa RDF de una manera compacta, permi-tiendo dividir inmensos grafos RDF en partes mas pequenas. Esta disenado para permitirgrandes ratios de compresion. Esto se consigue representando el grafo en tres grandescomponentes:

La cabecera (Header) incluye un sistema de metadatos tanto del RDF como suorigen y organizacion. HDT propone un vocabulario para especificar este tipo deinformacion, pero es extensible de manera que se pueda incluir cualquier informa-cion relevante del conjunto de datos.

El diccionario mantiene todas las cadenas de texto del RDF (URIs, Literales ynodos en blanco) de manera compacta de manera que ocupen poco espacio pero ala vez permitiendo las busquedas. De esta manera se evita la repetitividad dentrodel grafo de URIs y literales largos, ya que en el diccionario solo aparecen una solavez.

El componente Triples mantiene la estructura de grafo de una manera comprimida.Por supuesto es posible convertir otros formatos RDF como N3 o RDF-XML aformato HDT y viceversa.

Las principales cualidades de HDT son:

Compresion. Utilizar mucho menos espacio, de manera que se ahorre tanto espaciode almacenamiento como ancho de banda de red y tiempo de transmision. Ademas


Figura 2.6: Ejemplo de grafo RDF de la DBpedia.

esto hace posible que en ciertos casos sea posible mantener mayor cantidad de datosen memoria principal.

Publicacion e intercambio limpios. Separando el diccionario de los triples e in-cluyendo una cabecera con metainformacion y estadısticas del conjunto de datos.

Acceso indexado. Permite operaciones basicas indexadas, de manera que podamoshacer busquedas o acceder a subconjuntos del fichero sin tener que procesarlo en sutotalidad.

Gracias a las anteriores ventajas, HDT es un medio ideal para compartir datos RDF,puesto que ocupa menos espacio, tarda menos en transmitirse por la red, podemos conocerel dataset antes de descargarlo por completo usando la cabecera, y podemos acceder a lainformacion que queremos sin tener que descargarlo entero.

Para entender el funcionamiento de HDT, presentaremos un ejemplo concreto. Supon-gamos que deseamos representar en HDT un conjunto de datos de la DBpedia, como elque podemos ver en la figura 2.6. En el observamos una serie de recursos enlazados me-diante propiedades. Por ejemplo vemos ovalos representando URIs y cuadros represen-tando literales. Ademas los literales estan anotados con el idioma. Tambien observamosque estos recursos estan enlazados mediante propiedades de distintos vocabularios (RDF,RDFs, SKOS, DBpedia), utilizando cada predicado su URI completa.

En la figura 2.7 podemos observar la representacion HDT de ese mismo grafo. En laparte superior observamos la cabecera HDT, que incluye en formato RDF informacion deldataset, por ejemplo que se trata de un extracto de la DBPedia, cuantos triples tiene entotal, o que tipo de codificacion se esta utilizando.

Lo siguiente en la figura es el diccionario. Como bien podemos observar esta divididoen cuatro secciones bien diferenciadas. La primera, marcada a la derecha como S-O, esla zona compartida de Sujetos/Objetos, es decir, recursos que aparecen por lo menos endos triples, en una como sujeto y en otra como objeto. Podemos identificarlos en el grafo


Figura 2.7: Grafo de la DBpedia en formato HDT.

como aquellos recursos que tienen grado de entrada y de salida mayor o igual a uno, yno son nodos hoja. Este tipo de recursos tendran como identificador desde el 1 hasta el|S −O|.

La siguiente parte del diccionario es la de sujetos. Aquı apareceran todos los recursosque son sujeto de uno o mas triples, pero que no aparecen nunca como objetos. En estecaso se tratara de recursos con grado de salida mayor a uno en el grafo, y grado de entradanulo. El identificador ira a continuacion del de la zona compartida, es decir, desde |S−O|hasta |S|.

La siguiente zona del diccionario esta destinada a los objetos. En este caso se alma-cenaran todos los recursos que aparecen una o mas veces como objeto, pero nunca comosujetos. Esto quiere decir que seran nodos con grado de entrada mayor o igual a uno, ygrado de salida igual a cero. Se les asignara un identificador desde |S − O| hasta |O|.Cabe observar que los identificadores se solapan, es decir, hay sujetos y objetos con elmismo identificador (en el caso de ejemplo el 2 y el 3). Con esto se consigue poder contarcon un identificador mas compacto, y no es un inconveniente, ya que cuando se solicite aldiccionario cualquier tipo de acceso (Obtener el ID a partir de la URI, o viceversa, la URIa partir del identificador), se le indicara de que tipo es lo que buscamos, si sujeto, objetoo predicado.

La ultima seccion del diccionario almacena todos los predicados, identificados por loscodigos de 1 a |P |. Del mismo modo, es irrelevante que los identificadores se solapen conlos de sujetos y objetos.

Ademas cabe destacar que dentro de cada seccion del diccionario, los elementos estanordenados por orden lexicografico. Esto tiene dos finalidades fundamentales, la primera es


Figura 2.8: Distintas representaciones del grafo RDF dentro de la seccion Triples de HDT.

Figura 2.9: Distintas representaciones del grafo RDF dentro de la seccion Triples de HDT.

poder realizar busquedas binarias dentro del diccionario para poder localizar informacionrapidamente. La segunda es agrupar todas las raıces juntas de manera que el diccionario sepueda comprimir mas con un compresor general, como PPM [32], Re-Pair [27], o inclusoGZIP [28] y BZIP2 [35].

Para diferenciar las zonas del diccionario deberemos conocer cuantos elementos tienecada una, en concreto |S−O|, |S|, |P | y |O|. Esto no es problema ya que estos datos estananotados en la seccion de cabecera.

Por ultimo podemos observar en la parte de abajo de la figura 2.7 el componentedestinado a almacenar el grafo RDF. En este caso se utiliza una compactacion basada enBitmaps.

A continuacion explicamos las distintas representaciones del grafo RDF en la seccionTriples de HDT, como pueden verse en la figura 2.8.

La primera representacion y mas sencilla es ir escribiendo una tripleta por fila, perosustituyendo la URI completa por el identificador dentro del diccionario. Simplemente porno tener que repetir las largas URIs ya estaremos ahorrando espacio de almacenamiento.Ademas ordenaremos los triples por orden de identificadores, de manera que establecemosun orden total en las URIs. Ademas, si hubiera ternas repetidas las eliminaremos, dejandounicamente una de ellas, ya que esto no altera el significado global de los datos RDF.

Si bien la representacion de triples en plano es trivial, no es la mas compacta ni lamas adecuada para realizar busquedas. Podemos idear una nueva forma de representacionllamada CompactTriples. Se basa en la idea de ordenar los triples en listas de adyacencia,


de manera que aparezca una unica vez cada identificador, tal como se puede ver en la figu-ra 2.9. Es mucho mas sencillo verlo en el ejemplo. Si nos fijamos en PlainTriples, vemosque por estar ordenadas, en la primera columna se repite el mismo sujeto una y otra vez yademas va siempre consecutivo incrementandose de uno en uno. Para representar esto enCompactTriples estableceremos dos flujos de identificadores, uno de Predicados y otro deObjetos, representando las dos ultimas columnas de PlainTriples. En el flujo de predica-dos, iremos anadiendo cada identificador de predicado siempre que nos mantengamos enel mismo sujeto, y cuando cambiemos de sujeto lo indicaremos insertando un cero. En elflujo de objetos lo haremos de manera similar, iremos insertando el identificador de cadaobjeto hasta que cambiemos de predicado, en ese caso insertaremos un cero. Recordemosque los identificadores en el diccionario empezaban siempre en uno, precisamente parapermitir esta codificacion.

Para descompactar el CompactTriples y volver a la representacion en plano, no tene-mos mas que mantener un puntero a la posicion en el flujo de predicados, y un puntero ala posicion en el flujo de objetos. Mantendremos un contador indicando el sujeto actual, ylo incrementaremos cada vez que aparezca un cero en el flujo de predicados. Cada vez queaparezca un cero en el contador de Objetos, deberemos avanzar el puntero del contadorde Predicados.

La busqueda en CompactTriples no es tan inmediata, deberemos ir avanzando con-tando ceros en el stream de predicados hasta que encontremos el sujeto que queremos, yposteriormente buscar el predicado y los objetos. Ademas deberemos mantener los pun-teros a objetos, lo que resulta en una busqueda secuencial.

Para paliar el problema de la busqueda, se utiliza la representacion mediante bitmaps.Esta vez utilizaremos dos flujos de identificadores para predicados SP y objetos SO, de lamisma manera que en el caso anterior, pero ademas usaremos un mapa de bits de predica-dos BP y de objetos BO. En este caso, en lugar de marcar con ceros donde termina cadasujeto y cada predicado, lo que haremos sera insertar ceros en el mapa de bits mientrasnos mantengamos en el mismo, e indicar con un 1 los cambios. De esta manera los flujosno contendran ceros, y separamos esta informacion a los bitmaps.

Almacenar los bitmaps requiere muy poco espacio, un byte por cada 8 predicados uobjetos, pero la mayor ventaja es que existen implementaciones que utilizando un 5 %mas de espacio nos permiten realizar las operaciones rank y select en tiempo cons-tante. De esta manera buscar un determinado triple es mucho mas rapido, solo tendremosque hacer select en el flujo de predicados para encontrar un sujeto sin realizar busquedasecuencial.

En el ejemplo se ha plasmado la representacion Sujeto-Predicado-Objeto (SPO), perotambien podrıa haberse realizado en cualquier otro orden (SOP, POS, PSO, OPS, OSP).La representacion elegida se indicara en la cabecera Header, y se elegira segun el tipo dedatos y el tipo de consultas que se desee hacer.

Una caracterıstica en fase de estudio de HDT, es la de reasignacion de ındices en eldiccionario. El objetivo es conseguir que al ordenar los triples por orden (Primera, segunday tercera componente para cualquier tipo de parsing), las ternas se agrupen en grupos oclusters. Esto mejorara la compresion utilizando metodos como RLE o K2Trees ya quepodremos utilizar un codigo para identificar el grupo y otro codigo para identificar alelemento dentro del grupo, eliminando la dispersion inherente.

Capıtulo 3

Planteamiento del estudio

3.1. Presentacion del problema

La cantidad de datos semanticos en lenguajes como RDF se ha ido incrementando enlos ultimos anos. Cada vez son mas las organizaciones y usuarios que deciden publicar suinformacion en la red en este formato facilitando la interoperabilidad en lo que se conocecomo Linked-Data [38, 6].

Desde el inicio Tim-Berners-Lee sonaba con la Web no solo como un medio de com-partir documentos con hipervınculos sino tambien de incluir informacion semantica enlos mismos. Por desgracia esto no pudo ser posible desde el inicio y se empezo a incluirinformacion semantica con posterioridad. Para ello se ideo el lenguaje RDF y se empeza-ron a construir frameworks de diseno de ontologıas de mas alto nivel como OWL [31] yDAML [15]. Con ellos es posible construir vocabularios tan populares como FOAF [10]y DublinCore [16].

En la actualidad se sigue estudiando como aprovechar todas las posibilidades de laWeb Semantica para construir aplicaciones utiles para los usuarios. En el Semantic WebChallenge [8] se premian las aplicaciones mas punteras, como por ejemplo en el 2010la limpieza y organizacion de grandes volumenes de datos (Por ejemplo informacion degubernamental o biomedica) y la creacion de portales que permitan acceder y buscar estainformacion de manera sencilla.

Deberemos almacenar y organizar la informacion semantica para permitir esos accesosde una manera eficiente, probablemente utilizando consultas en el lenguaje SPARQL [34].Existen trabajos en la literatura que construyen sistemas de almacenamiento de RDF, nor-malmente organizando la informacion en una Base de Datos Relacional [11]. Tambienexisten trabajos que buscan como indexar la informacion RDF para su acceso mas rapi-do [40, 13], permitiendo un mayor numero de consultas y un tiempo de latencia masreducido.

Un area de investigacion que se encuentra presente es el de comprimir grandes volume-nes datos de informacion RDF. Normalmente loc conjuntos de datos se publican en for-mato N3 comprimidos con GZIP [28] o BZIP2 [35]. Esto es adecuado para descargarloe instalarlo en un datastore local, pero no para hacer consultas o acceder a un subconjntodel mismo. Por tanto se hace necesario contar con algoritmos de compresion que ademasde comprimir mas, permitan acceder a la informacion. HDT [18, 19] trata de proponer

27

28 CAPITULO 3. PLANTEAMIENTO DEL ESTUDIO

una solucion a estas limitaciones.Para poder resolver el problema de comprimir RDF, primero deberemos conocer las

caracterısticas de la informacion RDF. Buscando en la bibliografıa encontramos variosanalisis pero ninguno lo analiza desde un punto de vista de la redundancia de la informa-cion o la entropıa. En este estudio analizaremos las caracterısticas de RDF desde el puntode vista de la compresion.

3.2. Objetivos

El objetivo principal de este estudio es entender la idiosincrasia de la informacionRDF de cara la compresion, especialmente para proponer mejoras de la compresionen HDT. Para ello trataremos de:

Conocer caracterısticas generales de RDF y encontrar patrones comunes. Porejemplo, ¿como crece el numero de sujetos diferentes segun el tamano del conjun-to?, ¿y los predicados y objetos? Como de largas son las URIs?

Buscar casos especiales. ¿Existe algun caso extrano que se salga de lo normal?¿Algun conjunto de datos pequeno con muchos predicados, o alguno muy grandepero con pocos?

Conocer la variabilidad. ¿Una determinada caracterıstica se cumple siempre? ¿Po-demos predecir sus valores? ¿Con que exactitud? ¿Alguna caracterıstica es comple-tamente aleatoria e impredecible?

Estudiar el grafo RDF. ¿Como son los grados de entrada y salida del grafo?¿Que cantidad de nodos hay? ¿Que cantidad de enlaces?

Estudiar como afectan esas caracterısticas a la compresion con HDT. Compri-miremos estos conjuntos de datos con HDT y veremos que dependencia hay de suscaracterısticas con la compresion final.

Buscar explicaciones en el RDF original. Cuando encontremos alguna carac-terıstica, intentaremos explicarla buscando en el RDF original cuales son las causasdel mismo.

Visualizar los datos RDF de alguna manera para ver sus caracterısticas. Enciertas ocasiones es mejor representar la informacion graficamente para poder en-tender conceptualmente la informacion y los patrones que siguen.

Comparar parametros de compresion HDT y ver cuales son mejores en que ca-sos. De esta manera podremos saber que opciones son mas adecuadas segun losdatos que vayamos a tratar.

3.3. DISENO DE EXPERIMENTOS 29

3.3. Diseno de experimentos

Una vez determinados los objetivos del estudio, procederemos a disenar una serie deexperimentos para responder a nuestras preguntas de investigacion.

Realizaremos dos estudios diferenciados, primero realizaremos un analisis cuantitati-vo, tomando metricas de distintas caracterısticas del RDF, para posteriormente analizarlospor medio de metodos estadısticos de analisis y minado de datos.

Tambien desarrollaremos una herramienta grafica que permita visualizar la informa-cion RDF. A partir de ella mostraremos los distintos conjuntos de datos y buscaremoscaracterısticas cualitativas de la estructura del RDF, intentando buscar una explicacion enlos datos originales.

Para ello sera necesario contar con un conjunto de datos RDF lo suficientemente gran-de y variado para ser representativo, pero lo suficientemente pequeno como para ser ma-nejable en un ordenador actual.

A priori no sabemos que tipo de caracterısticas vamos a encontrar, no podemos pro-poner una hipotesis de partida y tratar de demostrar si es verdadera o falsa. Por lo tantoutilizaremos una metodologıa estadıstica exploratoria para tratar de entender los datos yya entonces poder plantear distintas hipotesis de las que demostrar su verosimilitud.

3.3.1. Caracterısticas a analizar

El primer paso sera decidir cuales son las variables a tener en cuenta en el estudio.Separamos el estudio en dos secciones diferenciadas. Primero buscaremos caracterısticasintrınsecas al conjunto de datos independientemente de la compresion, que podrıan serinteresantes para cualquiera que trabaje procesando o almacenando datos RDF. Posterior-mente analizaremos propiedades de compresion de HDT sobre cada conjunto de datos,comparandolo con otros compresores generalistas.

Caracterısticas generales de RDF

En esta seccion establecemos una serie de metricas que nos permitiran tomar medidasde variables aleatorias. En concreto para cada conjunto de datos obtendremos:

Nombre del dataset. Nos permitira identificarlo y tambien en ocasiones saberque tipo de informacion contiene.

Tamano del dataset en plano en formato N3. Nos permitira conocer el espacio endisco que ocupa el dataset, y compararlo por ejemplo con su tamano comprimido.

Numero de ternas en el dataset. Permite saber cuantas sentencias RDF contiene ydar una idea de la magnitud del tamano.

Numero de sujetos diferentes. Permite saber cuantos sujetos diferentes se estandescribiendo en el conjunto.

Numero de objetos diferentes. Permite saber cuantos objetos existen.


Numero de sujetos y objetos compartidos. Es decir, aquellas URIs o identificado-res de blancos que aparecen por lo menos una vez como sujeto y otra como objetoen dos o mas ternas diferentes.

Numero de predicados diferentes. Permite saber cuantos tipos de predicado exis-ten, es decir que tipo de relaciones existen entre recursos o que propiedades.

Numero de literales diferentes. Permite saber si existen pocos literales que serepiten con frecuencia, o si hay muchos literales diferentes que no se repiten.

Numero de nodos en blanco. Permite saber si este tipo de estructura se utilizafrecuentemente.

Ademas estudiaremos una serie de caracterısticas globales, independientemente deldataset:

Tamano de los Literales. Es interesante saber la longitud de los literales, parasaber si suelen ser tamanos cortos o largos, ya que utilizaremos distintos metodosde compresion segun corresponda.

Tamano de las URIs. Tambien puede ser util conocer la distribucion de tamanos delas URIs, suponemos que tendran un tamano reducido pero deberemos comprobarloexperimentalmente.

Tambien sera interesante analizar algunas caracterısticas del grafo RDF, sobre todogrados de entrada y salida. Recordemos que los datos RDF forman un grafo dirigidoetiquetado, por lo tanto deberemos definir una serie de metricas para estudiar en mayorprofundidad el tipo de grados:

Grado de salida. Es la cantidad de triples en las que una URI aparece como sujeto.Nos dara una idea de la importancia de ese sujeto, ya que habra algunos de ellos quetengan muchos enlaces de salida y por tanto sean nodos estrella dentro del grafo.

Grado parcial de salida. Es la cantidad de triples en las que aparece un determi-nado sujeto y predicado.

Grado etiquetado de salida. Es el numero diferente de predicados con los queesta relacionado un sujeto.

Grado de entrada. Es la cantidad de triples en las que una URI aparece comoobjeto. Es decir, dado un objeto, en cuantas ternas aparece. De la misma maneraque el grado de salida, nos da una idea de la importancia de ese nodo.

Grado parcial de entrada. Es la cantidad de triples en las que aparece un determi-nado predicado y objeto.

Grado etiquetado de entrada. Es el numero diferente de predicados con los queesta relacionado un objeto.


Compresion HDT

A parte de las caracterısticas generales de los datasets RDF, tambien queremos estu-diar como se comporta HDT ante distintas fuentes de datos, para ver cuales de las carac-terısticas afectan mas a la compresion. Para ello estudiaremos las siguientes variables:

Tamano del diccionario HDT: Necesitamos saber tanto el numero de entradascomo el tamano total en plano concatenando todos los identificadores. Tambienprobaremos a utilizar PPMDi y Re-Pair (Con y sin Huffman) para ver como afectala compresion con estos dos ultimos.

Tamano de los Triples: Analizaremos el tamano de la representacion del grafo entriples, utilizando para ello los diferentes formatos (PlainTriples, CompactTriples,BitmapTriples), y tambien los distintos parsings (SPO, OPS, PSO, POS, OSP, OPS).Ademas tambien utilizaremos codigos de Huffman para comprimir los identifica-dores del diccionario para ver como mejora.

Proporcion entre Diccionario y Triples. De esta manera sabremos como afecta eltener muchos sujetos/objetos diferentes con el tamano del grafo.

Destacar que no incluimos el tamano de la cabecera porque en la implementacionactual no se genera metainformacion en formato plano.

Visualizacion

Otro objetivo que nos marcamos es visualizar la informacion RDF graficamente parapoder observar la distribucion de los datos e identificar caracterısticas de manera cualita-tiva.

Normalmente los visualizadores de RDF lo que hacen es representar los nodos delgrafo con ovalos en un plano bidimensional que representan recursos y rectangulos querepresentan literales. Para cada triple, se unen los nodos del grafo segun corresponda. Estarepresentacion es adecuada para grafos pequenos pero es inviable para un conjunto grandede RDF con muchos triples. En este caso se podrıa representar una subparte del grafo,perdiendo de esta manera la nocion global, o representar el grafo en su totalidad perosin incluir los nodos, solo las aristas. Ademas serıan necesarios algoritmos de enrutado(Layout) para ver donde colocar cada nodo, teniendo en cuenta la propiedad de localidadde referencia para minimizar las aristas que conectan un lado del grafo con el otro y deesta manera mejorar la visibilidad.

Otra aproximacion mas sencilla es representar la matriz de adyacencia Sujetos/Obje-tos en una grafica, donde el eje X representa objetos y el Y sujetos. Dado un triple RDFpodemos indicarlo en el grafico colocando un punto en la posicion x del objeto e y delsujeto respectivamente. Ademas podremos indicar con un codigo de colores de que pre-dicado se trata. El mayor problema son los casos donde un mismo sujeto y objeto estenunidos por mas de un predicado, ya que se solaparan y no sera visible.

Esta representacion es muy adecuada para representar datos HDT, ya que los dos ejesrepresentarıan los identificadores de Sujetos y Objetos respectivamente en cada eje, ypodrıamos ver la dispersion de los datos, ası como las correlaciones. Ademas se puedeindicar en cada eje a que zona del diccionario pertenece, por ejemplo en el eje y primero


habra una zona de sujetos-objetos, y luego el resto de sujetos. En el eje x ademas de lazona compartida, podemos distinguir entre zona de URIs, nodos anonimos, o literales.

Tambien serıa deseable que se pudieran seleccionar triples del grafico para conocerde que se trata. Por ejemplo podemos tener una zona donde se agrupan todos los literalescon fechas, y nos gustarıa saber que esos puntos estan agrupados por esa razon. De estamanera sera mas sencillo cumplir el objetivo de buscar explicaciones a las caracterısticasvistas en el grafico.

Un problema en la visualizacion de grandes volumenes de datos es precisamente el dela escalabilidad. Es muy difıcil trabajar en tiempo real con grandes volumenes de datosy renderizar todos los puntos. Por lo tanto sera necesario contar con estructuras de datoseficientes que permitan acceder a los datos directamente, por ejemplo la estructura internadel HDT. Ademas deberemos contar con alguna manera de muestrear los datos sin perdersignificatividad.

Una de las caracterısticas en desarrollo dentro del prototipo HDT es la de reasignacionde ındices o clustering. El objetivo es cambiar los ındices (y por tanto cambiar el orden delos triples para mantenerlos ordenados) de manera que los triples se agrupen en clustersde nodos similares y por tanto sea mas facil aplicar tecnicas de compresion. Aunque HDTtodavıa no utiliza la tecnica de cluster para compactar mas la informacion, si que permiterealizar una reordenacion inicial de los resultados. Tambien sera oportuno visualizar estadistribucion y poder comparar con el original, para ayudar tambien al desarrollo de nuevosalgoritmos de reasignacion de ındices.

3.3.2. Eleccion de DatasetsEl siguiente paso es escoger los conjuntos de datos que vamos a analizar. Idealmente

debe tener las siguientes caracterısticas:

Tamano adecuado. Debe ser lo suficientemente grande como para ser representa-tivo de la poblacion global, pero lo suficientemente pequeno como para ser tratablecomputacionalmente con los medios disponibles.

Representativo, con alta variabilidad. El conjunto de datos debe recopilar infor-macion de distintos orıgenes. Por ejemplo Uniprot es un conjunto de datos muyamplio, con gran cantidad de triples RDF, pero esta disenado y centrado en un areamuy especıfica que es el de estudio de proteınas. Deberemos buscar conjuntos dedatos de distinta ındole, por ejemplo otros conjuntos de datos especıficos similaresa Uniprot, como los censos de USA y UK, Uniprot, ADN, Wikipedia, Kaufkauf(codigos de barras). Tambien necesitaremos contar con RDF general de distintasfuentes, idealmente recopilados de la Web y con orıgenes muy diversos. De estamanera conseguiremos un conjunto de datos representativo de la informacion conla que se trabaja en RDF en general.

Reproducible. El conjunto de datos debe ser publico para que otros investigadorespuedan descargarlo y realizar sus propias pruebas para comparar con las nuestraso ampliarlas. Idealmente el conjunto de datos sera estatico. Por ejemplo la Wiki-pedia va evolucionando dıa a dıa, lo ideal es utilizar una instantanea (dump) de unmomento determinado y que pueda ser descargable en el futuro.


BillionTriples

Uno de los conjuntos de datos que cumple todas las caracterısticas anteriormente ci-tadas es BillionTriples [2], por ejemplo en su edicion 2010:

Gran tamano: En la edicion 2010 asciende a 3.2 miles de millones de triples (Re-cibe el nombre del Billon americano).

Variedad alta: Cuenta con muchas fuentes diversas, desde conjuntos de datos gran-des, hasta redes sociales, conjuntos de proteınas o paginas aisladas recopiladas dela Web.

Edicion anual: Cada ano se recopila un conjunto de datos diferente y actualizado,disponible desde el 2009.

Dataset muy estudiado: La iniciativa de BillionTriples es servir como conjuntode datos comun para el track de Semantic Web Challenge, por tanto muchos auto-res realizan proyectos tomando este conjunto de datos como partida con objetivosmuy diversos. Nuestro estudio puede ser interesante para proyectos futuros de estosautores.

Formato adecuado: El conjunto de datos se distribuye en formato NQ comprimidomediante GZIP. Esto hace que la importacion a HDT sea muy sencilla.

Incluye el origen: Al estar en formato NQ, en lugar de ternas se incluye un cuartoelemento que es el origen. De esta manera podemos saber de donde se ha extraıdocada sentencia y hacer un analisis por distintos orıgenes.

Capıtulo 4

Experimentacion y Resultados

A continuacion procedemos a explicar todos los pasos seguidos en el proceso de rea-lizacion de experimentos, de manera que puedan ser reproducidos en caso necesario.

4.1. Procesamiento del conjunto de datos BillionTriplesEl primer paso es descargar el conjunto de datos y preprocesar la informacion en cru-

do. La descarga puede realizarse de la pagina oficial [2] y consiste en 317 Fragmentos de1 millon de triples cada uno. El tamano total comprimido en GZIP es de 27GB, mientrasque la version en plano ocupa 640GB.

Ese tamano es inabordable desde el punto de vista de un ordenador personal actual,por lo tanto deberemos realizar algun tipo de muestreo de los datos para que el tamanosea menor pero perdiendo la menor significatividad posible. Lo normal es tomar las Nprimeras ternas del conjunto de datos. La mayor ventaja es que es muy sencillo de rea-lizar, basta con truncar el fichero a las primeras N lıneas. El problema es que nadie nosasegura que las N primeras lıneas sean representativas del total. Tambien podemos to-mar aleatoriamente N ternas de cualquier parte del conjunto de datos (Sin repeticion). Elproblema de esta otra aproximacion es que no es suficientemente representativa, puestoque estaremos eliminando aristas aleatoriamente afectando ası a la medicion del grado decada recurso. Por ultimo tambien podemos partir de varios nodos raız e ir siguiendo todoslos triples a partir de el hasta llegar a una profundidad maxima o a un numero maximo denodos, de esta manera aseguramos que las partes con las que nos quedamos son conexasy las mediciones de grado no se ven tan afectadas.

En nuestro caso hemos optado por otro tipo de muestreo, que es el de hacer subcon-juntos agrupados por origen. La mayor ventaja de este metodo es que ası podemos realizarel mismo estudio sobre cada origen y de esta manera satisfacer el objetivo de analizar lavariabilidad de los parametros. Mediremos cada una de las variables para cada subcon-junto y ası sabremos la varianza de ese parametro sobre el global. Una de las desventajases que perdemos las relaciones entre conjuntos. Por ejemplo si rdf:type aparece envarios subconjuntos, nosotros lo trataremos como recursos diferentes, y al comprimirlocon HDT aparecera una vez en cada diccionario.

El primer paso por tanto es ver que orıgenes hay disponibles en el conjunto de BT2010,ya que esta informacion no esta disponible en ningun sitio. Para eso desarrollamos un

35

36 CAPITULO 4. EXPERIMENTACION Y RESULTADOS

Numero de Triples (M) Dominio6.676.965 dbpedia.org6.691.460 planeta.rambler.ru6.700.407 users.livejournal.com7.643.002 sw.opencyc.org

10.619.518 sws.geonames.org12.165.374 www4.wiwiss.fu-berlin.de13.158.688 www.bibsonomy.org16.568.885 po.debii.curtin.edu.au16.886.434 dblp.l3s.de17.085.248 static.cpantesters.org21.410.176 products.semweb.bestbuy.com21.580.171 transport.data.gov.uk22.608.589 www.rdfabout.com51.199.071 www.mybloglog.com60.149.507 dbtune.org72.814.841 rdf.opiumfield.com87.806.384 www.uniprot.org

20.444.8874 api.hi5.com658.151.538 data-gov.tw.rpi.edu

1.616.059.815 openean.kaufkauf.net

Cuadro 4.1: Lista de los 20 Dominios con mas triples, y el numero de ellas.

pequeno script en Perl que va analizando cada lınea y se queda con la ultima componenteque indica el origen. Algunas URIs de origen son las siguientes:

<h t t p : / / openean . k a u f k a u f . n e t / i d / EanUpc 0070950541106><h t t p : / / s t a t i c . c p a n t e s t e r s . o rg / a u t h o r / L / LUNATIC . r s s><h t t p : / / da t a−gov . tw . r p i . edu / raw / 9 0 / da t a −90−18834. r d f>

Estas URIs indican el origen completo de la terna, pero a nosotros nos interesa so-lamente el dominio. Por lo tanto aplicaremos una expresion regular para eliminar elhttp:// y todo lo que siga a la primera barra, quedandonos unicamente con el nom-bre del dominio. Para saber cuantos triples tiene cada dominio de origen recorreremostodos los ficheros leyendo el origen de cada triple. Tendremos una tabla hash en memo-ria que para cada origen mantenga un contador con el numero de apariciones. Por ultimovolcamos a un fichero una lista con los dominios y el numero de triples asociado a cadauno. En la tabla 4.1 puede verse el numero de triples de los 20 dominios que cuentan conmas de ellas.

El primer estudio que podemos realizar es la distribucion de la cantidad de triples pordataset. No podemos generalizar que esto aplique a la WEB, puesto que no sabemos si enBT se recopilan todos los triples de cada dominio. Asumimos que no lo hace, porque porejemplo la DBPedia tiene 6 millones de triples en BT2010, mientras que en el dump de lapagina oficial tiene muchas mas. Lo mismo ocurre con Uniprot.

Aun ası podemos representar graficamente el resultado, como puede verse en la figu-ra 4.1. A la izquierda se puede apreciar una zona de bajada repentina, para luego estabili-

4.1. PROCESAMIENTO DEL CONJUNTO DE DATOS BILLIONTRIPLES 37

0 0.5 1 1.5 2 2.5 3 3.5 4x 105

100

102

104

106

108

Triples per dataset

Dataset

Num

ber o

f Trip

les

Figura 4.1: Numero de triples por dominio, en orden decreciente.

0 100 200 300 400 500 600 700

10

12

14

16

18

20

Dataset

log(

Num

ber o

f Trip

les)

Triples per dataset 700 Biggest

datasetSizeL1Power

Figura 4.2: Tamano de los 700 dominios con mas ternas.


0 0.5 1 1.5 2 2.5 3 3.5 4x 105

0

1

2

3

4

5

6

7

8

9

Dataset

log(

Num

ber o

f Trip

les)

Triples per dataset Without 700 Biggest

datasetSizeL2 Power

Figura 4.3: Tamano de dominios a partir del 700.

zarse en una bajada mas regular. Separaremos la grafica en esas dos secciones, la inicial yel resto.

En la figura 4.2 podemos ver los 700 primeros elementos. Ademas hemos ajustadouna curva potencial de tipo y = a ∗ xb + c, con parametros a = 71,37, b = −0,0294 yc = −49,93, lo cual da un valor de R2 = 0,9975, siendo un ajuste muy bueno.

En la figura 4.3 representamos los elementos restantes junto con una curva potencialde tipo y = a ∗ xb + c, con parametros a = −0,05385, b = 0,3733 y c = 9,421, lo cual daun valor de R2 = 0,9908, tambien un valor bastante elevado.

La explicacion que se puede dar a priori es que muy probablemente los datos de lazona inicial de la grafica se traten de datasets muy grandes tomados tal cual e importadosa BillionTriples, mientras que la segunda zona se refiere mas bien a datos importados dela Web de conjuntos de datos mas pequenos.

Cabe pensar que el tamano de los datasets en la WEB tambien siga una distribucionpotencial o power-law, aunque mediante este estudio no podemos afirmarlo por la formaen que se han recopilado los datos en BT2010.

Una vez conocemos las distintas fuentes de datos escogemos 400 subconjuntos deentre los 1000 primeros. De esta manera aseguramos que los conjuntos de datos son su-ficientemente grandes como para ser representativos al analizar grados en el grafo RDF.Para ello realizaremos otro script en Perl (split.pl), que vaya leyendo el conjuntode datos original y para cada lınea extraiga la cuarta componente de origen, obtenga eldominio, y si es uno de los seleccionados guarde esa terna N3 en su propio fichero dedatos.

4.1. PROCESAMIENTO DEL CONJUNTO DE DATOS BILLIONTRIPLES 39

A continuacion se detallan algunos de los datasets seleccionados y el tipo de informa-cion que contienen:

Kaufkauf: Se trata de una Web alemana que recopila gran cantidad de productosjunto con sus codigos de barras.

data-gov.tw.rpi.edu: Datos gubernamentales de Estados Unidos, como censo, energıa,proteccion, trafico...

api.hi5.com: Perfiles foaf de la red social hi5 junto con las relaciones entre sususuarios.

www.uniprot.org: Informacion de proteınas.

rdf.opiumfield.com: Informacion rdf de distintas fuentes, especialmente musica ypelıculas.

dbtune.org: Informacion musical, como grupos, cantantes, discos y canciones.

www.mybloglog.com: Blog de Yahoo.

www.rdfabout.com: Informacion gubernamental, similar a data-gov.

products.semweb.bestbuy.com: Productos disponibles en la Web bestbuy.com ca-talogados en RDF.

dblp.l3s.de: Informacion DBLP de autores, revistas y publicaciones.

www.bibsonomy.org: Gestion de marcadores y publicaciones.

www.wiwiss.fu-berlin.de: Mashup que incluye informacion de la DBPedia, de li-bros...

www.geonames.org: Informacion de entidades geograficas, Paıses, Ciudades, ytambien rıos, montanas, cerros.

sw.opencyc.org: Catalogo de conocimiento general.

dbpedia.org: Informacion general.

www.daml.org: Definiciones de vocabularios ontologicos.

bio2rdf: Informacion biologica.

geospecies: Catalogo de especies animales y vegetales.

data.nytimes.com: Informacion de noticias y sucesos.


Estos son solo algunos de los conjuntos de datos elegidos, pero es suficiente paramostrar la gran diversidad existente. Tenemos desde catalogos de productos con estructuraprefijada (bestbuy), hasta informacion biologica en un formato especıfico(bio2rdf,uniprot)pasando por conjuntos generalistas (dbpedia,opencyc).

Una caracterıstica importante a la hora de procesar grandes volumenes de datos es in-tentar realizar esta tarea eficientemente. Por ejemplo es mejor realizar las menores pasadasposibles sobre los datos y sacar de los bucles todo lo innecesario. Nosotros hemos utili-zado Perl como lenguaje porque es muy sencillo procesar datos, y aunque sea algo maslento que realizar esta tarea en C/C++, es mucho mas sencillo de modificar y mantener.

Por ejemplo, en la maquina de pruebas1 se tarda unos 10 segundos en descomprimircada uno de los fragmentos de BT2010 desde el formato GZIP redirigiendo la salida a/dev/null (Para evitar medir la escritura de datos en disco). Cada fichero contiene 10millones de ternas, ocupando unos 90MB comprimido, y 1,9GB descomprimido. El pro-grama count tarda aproximadamente 2 minutos en procesar cada uno de estos ficheros,tardando un total de 10 horas y media para el conjunto de datos completo. El programasplit sin embargo tarda 24 horas en generar todos los ficheros.

Finalmente, procesaremos un total de 174 millones de ternas RDF, ocupando compri-mido en GZIP 6,03GB y 48,9GB en plano. Esto supone aproximadamente un 10 % delconjunto BT2010 original.

4.2. Generacion y limpieza de datosUna vez que contamos con el corpus de datos dividido en subconjuntos por origen,

procedemos a procesarlo para extraer las metricas necesarias. Para ello utilizaremos laherramienta HDT, que ya esta preparada para leer los datos RDF en distintos formatos(N3, Turtle, RDF-XML) y generar la representacion correspondiente. Sin embargo debe-remos realizar una serie de modificaciones:

Conseguir que la herramienta HDT lea directamente ficheros comprimidos enGZIP. Como hemos visto, un fichero de 90MB comprimido ocupa 2GB en planodebido a la gran redundancia del formato de serializacion N3. Por tanto es muchomas adecuado contar con los datasets ya comprimidos y a medida que se necesi-tan ir descomprimiendolos, de esta manera podemos tener todos los conjuntos dedatos en el portatil dedicado al trabajo. Para ello se ha utilizado la primitiva de Cpopen(), que permite automaticamente lanzar un subproceso y redirigir su salidaestandar a una tuberıa (pipe) de la cual nosotros podemos leer con un manejador defichero. Podrıamos haber utilizado la librerıa zlib, pero usando las tuberıas tenemosla ventaja de poder cambiar a cualquier tipo de descompresor siempre que sea capazde escribir el resultado descomprimido en la salida estandar. Ademas el descompre-sor se ejecutara en otro proceso de la maquina, por tanto podra ejecutarse en otronucleo en caso de que la maquina cuente con mas de un procesador virtual.

Cargar toda la informacion de HDT en memoria. En ciertos casos no es trivialtrabajar con las ternas HDT en formato CompactTriples o BitmapTriples, en oca-siones es mas sencillo cargar los datos en memoria en formato plano, realizar las

1AMD Opteron 270 con 4GB de RAM, Gentoo Linux x86 64, Perl 5.8.8 y GZIP 1.3.11

4.2. GENERACION Y LIMPIEZA DE DATOS 41

busquedas o reordenaciones correspondientes y volver a volcar los datos (o descar-tarlos si ya no son necesarios). Para ello escribimos una rutina que se encarga decargar los datos en memoria a partir de cualquier formato de triples.

Convertir entre formatos de parsing. En ciertas ocasiones contamos con los da-tos de triples organizados en SPO y deseamos realizar una operacion que solo sepuede realizar en PSO. Para ello una opcion es intercambiar los dos primeros ele-mentos (El S por el P) y reordenar el conjunto de triples para mantener el ordenlexicografico. Para ello construimos un procedimiento que se encarga de realizaresta operacion para cualquier parsing de origen y cualquier destino.

Realizar mediciones de grados. Necesitaremos, dado un grafo RDF, contar losgrados, grados parciales y etiquetados, tanto de entrada y salida. Para ello se partedel grafo de triples HDT en memoria, se cambia el parsing a SPO para contar losgrados de salida y a OPS para contar los de entrada.

Extraer estadısticas del diccionario. Por ejemplo deberemos contar el numero deliterales, de nodos anonimos y de URIs.

Corregir algunos errores menores de HDT, como algun problema en la lecturade ficheros RDF N3 con lıneas en blanco, o en la gestion de identificadores deldiccionario en casos puntuales.

El proceso seguido para cada procesar cada fichero se ha automatizado para poder repetirde manera sencilla los experimentos, y es el siguiente:

1. Preprocesar el fichero N3 comprimido en GZIP con la herramienta HDT, gene-rando el diccionario y los triples HDT en formato plano y con parsing SPO. De estamanera no necesitaremos parsear y leer el conjunto de datos cada vez, tarea muycostosa en procesamiento y tiempo, sino que podremos utilizar ya directamente elformato HDT para trabajar con el.

2. Guardar el dataset en los distintos formatos HDT (PlainTriples, CompactTri-ples, BitmapTriples) para cada tipo de parsing (SPO, SOP, PSO, POS, OPS, OSP),generando en total 18 representaciones HDT diferentes.

3. Comprimir los diccionarios y los triples HDT utilizando Re-Pair, PPMDi y Huff-man, para conocer los tamanos comprimidos.

4. Generar estadısticas.

Estadısticas del diccionario: Numero de entradas, tamano total, numero de lite-rales, nodos en blanco y URIs. Ademas generamos histogramas de la longitudde las cadenas separadas por tipo (literal, blank, URI).

Mediciones de grados.

Histograma de predicados. Para conocer dado un predicado en cuantos triplesaparece, y por lo tanto saber los grados mas importantes.


50 100 150 200 250 300 350

2

3

4

5

6

7

8

9

10

Dataset

Byte

s / T

riple

Size of each triple in bytes

dataSLPower fit

Figura 4.4: Tamano en bytes por triple, ordenados por orden de tamano creciente.

Para terminar de automatizar el proceso, construiremos un script que ejecute el gene-rador de estadısticas sobre cada uno de nuestros datasets, y posteriormente recopile todala informacion en una tabla que resuma la informacion de cada uno de ellos, para poderanalizarla con los paquetes de software estadıstico.

La tabla de resultados esta disponible en formato CSV en la siguiente URI:http://gutenberg.dcs.fi.uva.es/˜marari/hdt/rdfresults.csv

4.3. Analisis del dataset RDFUna vez generados todos los datos y recopilados en ficheros, procedemos a aplicar

tecnicas estadısticas de analisis y minado de datos para extraer modelos que se ajusten aellos. De esta manera podremos tener un conocimiento de mas alto nivel de la estructuray buscar explicaciones a esas caracterısticas.

4.3.1. Numero y tamano de triples

Un primer analisis que podemos realizar, es ver cuanto ocupa cada triple. Podemosdividir el tamano total del dataset en bytes por el numero de triples que contiene paraobtener en tamano medio, segun esta representado en la figura 4.4, ordenado ascendente-mente por tamano y dataset. Como podemos observar, sigue una tendencia potencial, conuna zona practicamente lineal y una leve rampa de subida al final.

De todas maneras es mas interesante visualizar la distribucion en un histograma, como

4.3. ANALISIS DEL DATASET RDF 43

100 1000 10000 1000000

10

20

30

40

50

60

70

80C

ount

Triple size

Triple size Distribution

Figura 4.5: Distribucion del tamano de los triples en bytes.

1e+14 1e+15 1e+16 1e+17 1e+18 1e+19 1e+20 1e+21 1e+22 1e+23

1e+08

1e+10

1e+12

1e+14

1e+16

1e+18

Dataset size

Trip

les

Triples vs Dataset size

triplesL vs. datasetsizeLfit 2

Figura 4.6: Numero de triples en relacion al tamano del dataset en bytes.


1000 3162.28 10000 31622.8 100000 316228 1e+063.16228e+061e+073.16228e+07100

316.228

1000

3162.28

10000

31622.8

100000

316228

1e+06

3.16228e+06

1e+07

Triples

Subj

ects

/Obj

ects

Subjects and Objects vs Triples

subjects vs. triples fit subjectsobjects vs. triples fit objects

Figura 4.7: Numero de objetos y sujetos a medida que incrementamos el numero de triples.

se puede ver en la figura 4.5. En ella representamos cuantos datasets tienen el tamanomedio de triple en un determinado intervalo. Vemos que tiene una distribucion unimodal,con moda= 161,91, agrupandose la mayorıa de los datasets en torno a ese valor.

Tambien podemos comparar la dependencia del numero de triples con el tamano enplano del fichero, como puede observarse en la figura 4.6. Lo representamos en dobleescala logarıtmica para mejorar la visibilidad, y podemos apreciar que los puntos se agru-pan con una tendencia potencial definida por y = 0,03x0,87. El valor de ajuste R2 = 0,82refleja que el ajuste no es demasiado bueno, ya que existen puntos bastante alejados enla zona inferior, que son aquellos datasets que a pesar de tener bastante tamano, tienenmenos triples que la media. Revisando los datos asociados a algunos de esos puntos, nosdamos cuenta que eso es debido a que existen literales muy largos que contienen bastantetexto y por ello se incrementa la media de espacio en bytes.

4.3.2. Numero de Sujetos y ObjetosA continuacion procedemos a estudiar el crecimiento de sujetos y objetos a medida

que aumenta el numero de triples. Para ello utilizaremos el diagrama de dispersion mos-trado en la figura 4.7. La primera observacion que podemos hacer es que el numero deobjetos es significativamente mayor que el de sujetos. Ademas podemos ajustar los suje-tos a la ecuacion potencial y = 0,54x0,97 con un R2 = 0,93 y los objetos a la ecuaciony = 0,21x0,98 con R2 = 0,91.

Si observamos las dos tienen un exponente muy cercano a 1, por lo tanto aunque elcrecimiento es sublineal, es muy proximo a una recta. La primera conclusion que pode-mos sacar de este resultado es que el crecimiento de sujetos y objetos va disminuyendoa medida que aumentamos el numero de triples, por lo que cabe esperar que el dicciona-


0 0.5 1 1.5 2 2.5 3 3.5 40

20

40

60

80

100

120

Dat

aset

Cou

nt

Subject/Object Ratio

Subject/Object Ratio Distribution

Figura 4.8: Distribucion de la proporcion de sujetos/objetos en los distintos datasets.

rio vaya disminuyendo tambien su crecimiento a medida que aumentamos el numero detriples.

Tambien es interesante conocer si hay mayor cantidad de sujetos que objetos o vi-ceversa. Para ello definimos el ratio sujetos/objetos, de manera que valores menores a 1indiquen mayor numero de objetos, y valores mayores a 1 indiquen mayor numero desujetos. Podemos ver la distribucion de este ratio en la figura 4.8. Vemos que es unimodaly centrada en 0,5, por lo tanto lo mas habitual es que el numero de sujetos sea la mitad delnumero de objetos, aunque existen casos extremos con hasta 4 veces mas de sujetos quede objetos.

A continuacion analizamos que ocurre con la evolucion de sujetos y objetos compar-tidos (En adelante SOCompartidos). Esta metrica es muy importante de cara a la compre-sion porque podremos aprovechar esta caracterıstica para eliminar la redundancia, utili-zando una representacion o identificadores comunes para estos elementos. Tambien cabedestacar la importancia de esta zona desde el punto de vista de las busquedas, puesto queen SPARQL jugaran un papel muy importante en los JOINs. Ademas desde el punto devista del grafo, estos nodos son el nucleo siempre que tratemos de realizar busquedas,recorridos o visualizaciones.

En la grafica 4.9 podemos observar que el numero de sujetos/objetos compartidosrespecto al numero de triples se ajusta a la ecuacion y = 0,16x0,97, con un R2 = 0,8.El ajuste no es demasiado bueno, puesto que hay mucha variabilidad, existiendo inclusoalgunos datasets que apenas tienen sujetos/objetos compartidos.

Tambien podemos definir el ratio de compartidos como el numero de compartidosdividido por el numero de triples (r = shared/triples), y estudiar su distribucion como


1000 10000 100000 1e+06 1e+07 1e+08 1000 10000 100000 1e+06 1e+0710

100

1000

10000

100000

1e+06

1e+07

Triples

Shar

ed S

ubje

cts

Obj

ects

Shared vs. triplesPower fit

Figura 4.9: Numero de sujetos y objetos compartidos a medida que incrementamos elnumero de triples.

0 0.1 0.2 0.3 0.4 0.5 0.60

1

2

3

4

5

6

Data

Den

sity

Shared Subject−Object Ratio Distribution

sharedratioLogistic fit

Figura 4.10: Distribucion del ratio SOCompartidos/triples.


103 104 105 106 107

101

102

103

104

Triples

Pred

icat

es

Predicates vs Triples

Figura 4.11: Numero de predicados a medida que incrementamos el numero de triples.

se muestra en el histograma de la figura 4.10. Podemos observar una distribucion centradaen la moda 0,13, y con media 0,1471. Ademas podemos ajustar una curva logıstica quecaracterice la distribucion, con parametros µ = 0,1395 y σ = 0,047, que obtiene un valorde maxima verosimilitud logarıtmica de 388.

Ademas si nos fijamos en la grafica podemos observar que el primer y el ultimo in-tervalo tienen valores de frecuencia un poco mayores a lo que hay a su alrededor. Estoquiere decir que a pesar de que lo normal es que el ratio este en torno a 0,13, tambienexisten conjuntos de datos con muy pocos compartidos, lo cual significa que es un grafopoco conexo con definiciones mas aisladas. Tambien existen conjuntos de datos con ca-si su totalidad de sujetos y objetos compartidos, en este caso significa que existe muchaimportancia en las relaciones entre elementos.

4.3.3. PredicadosEl siguiente paso es ver que ocurre con los predicados. Sera interesante conocer la

cantidad y distribucion de ellos, puesto que algunas representaciones separan los datospor predicado, sistema conocido como particionado vertical en la indexacion RDF.

Para ello, representamos de igual modo el numero de predicados respecto al de triplesen un diagrama de dispersion con doble escala logarıtmica (Figura 4.11). Como podemosobservar, no existe una relacion directa entre el numero de predicados y el de triples,como podemos corroborar utilizando el coeficiente de correlacion de Pearson que da unvalor de 0,041. Esto significa que existen grandes datasets con pocos predicados, comopor ejemplo los que tienen una gran lista de elementos con pocas propiedades de cada


0 100 200 300 400 500 6000

0.002

0.004

0.006

0.008

0.01D

ensi

ty

Number of predicates

Distribution of Number of predicates

predicatesGEV fit

Figura 4.12: Distribucion de la cantidad de predicados.

uno, y tambien conjuntos de datos pequenos con muchos predicados, como por ejemploaquellos que definen ontologıas.

Tambien representaremos la distribucion del numero de predicados, como puede verseen la figura 4.12. En el vemos que lo mas habitual es que haya pocos predicados, con pocosdatasets que tengan un numero elevado. La relacion parece exponencial, aunque ajustandodistintas curvas por metodos de maxima entropıa encontramos que se ajusta mejor a unadistribucion de valor extremo generalizado (Generalized Extreme Value) con parametrosk = 0,99, σ = 51,51 y µ = 47,79. Ademas si nos fijamos con atencion veremos que enel primer intervalo tiene menos elementos que el segundo, esto quiere decir que el valormas probable no esta cercano a cero, sino que la moda esta en torno a 30.

Otro analisis que podemos realizar es el de con que frecuencia se utiliza cada pre-dicado dentro de cada dataset. Para ello podemos tomar un dataset y calcular su his-tograma o su distribucion de probabilidad. Partamos por ejemplo de dos corpus gran-des y con gran cantidad de predicados, como DBPedia (17011 predicados para 6,5Mtriples) y Freebase(5062 predicados para 3,5M Triples), que se pueden ver en las figu-ras 4.13 y 4.14. Podemos observar una power-law en el uso de los predicados, apro-ximados por las funciones: y = −0,96 ∗ x0,19 + 6,07 y R2 = 0,9942 para DBPedia,y = −0,61 ∗ x0,026 + 5,514 con R2 = 0,9944 para Freebase. Es sorprendente la bonanzadel ajuste en estos casos, siendo practicamente perfecto.

Tambien podemos analizar otros subconjuntos con menos predicados y triples. Porejemplo en ChatMusicBrainz (3311 predicados para 6,5M Triples, ver Figura 4.15) po-demos ver un descenso pero esta vez con una forma mas recta y menos pronunciada.Tambien si miramos DBLP que tiene solamente 28 Predicados para 14M triples podemosapreciar una forma de descenso potencial aunque no perfecta.


0 2000 4000 6000 8000 10000 12000 14000 16000

1

10

100

1000

10000

100000

1e+06

Predicate ID

Trip

les

of th

e pr

edic

ate

Uses of each predicate in DBPedia

dbpediaPower Fit

Figura 4.13: Distribucion de la cantidad de uso de cada predicado en la DBPedia.

0 500 1000 1500 2000 2500 3000 3500 4000 4500 5000

1

10

100

1000

10000

100000

Predicate ID

Trip

les

of th

e pr

edic

ate

Uses of each predicate in Freebase

freebasePower Fit

Figura 4.14: Distribucion de la cantidad de uso de cada predicado en Freebase.


0 500 1000 1500 2000 2500 30001

10

100

1000

10000

100000

1e+06

Predicate ID

Trip

les

of th

e pr

edic

ate

Uses of each predicate in ChatMusicBrainz

chatMusic

Figura 4.15: Distribucion de la cantidad de uso de cada predicado en ChatMusicBrainz.

0 5 10 15 20 25 300

0.5

1

1.5

2

2.5

3

3.5x 106

Predicate

Trip

le c

ount

Triple count per predicate on DBLP

Figura 4.16: Distribucion de la cantidad de uso de cada predicado en DBLP.


0 5 10 15 20 250

0.5

1

1.5

2

2.5

3

3.5x 104

Predicate

Trip

le c

ount

Triple count per predicate on Rossetti Archive

Figura 4.17: Distribucion de la cantidad de uso de cada predicado en RossettiArchive.

Un ejemplo mas pequeno aun es el de RossettiArchive, con 23 predicados para 273Ktriples. En el vemos que no se cumple el descenso power-law.

Una cosa que observamos tanto en DBLP como en RossettiArchive es que existenzonas llanas en la grafica. Esto quiere decir que existen dos o mas predicados que seutilizan exactamente el mismo numero de veces. Esto puede ser debido a que se utilizan enconjunto. Por ejemplo en DBLP cada autor tiene un foaf:name y un foaf:surname,por eso aparecen el mismo numero de veces.

Como conclusion podemos sacar que los conjuntos de datos grandes tienden a ha-cer un uso de los predicados con forma de power-law, pero que no tiene por que serloobligatoriamente y dependera del conjunto de datos.

4.3.4. Grados del Grafo RDFTambien es interesante estudiar dado un recurso, con cuantos otros recursos o literales

se relaciona. Esto nos ayudara a conocer cual sera el grado de compresion usando listasde adyacencia en los triples HDT.

En este caso no realizaremos el estudio por cada dataset, sino sobre el conjunto com-pleto. Para ello se generan los histogramas de cada dataset por separado (cuantas vecesaparece cada grado), y posteriormente se realiza la suma componente a componente detodos los datasets para obtener el global.

En la figura 4.18 vemos dos representaciones de la misma informacion (Pareto, vsZIPF). En la parte superior representamos el numero de sujetos (eje y) que tienen undeterminado grado de salida (eje x). Como podemos observar hay una tendencia poten-


0 200 400 600 800 1000 1200 1400 1600100

102

104

106

108

Out Degree

Cou

nt

Out Degree Histogram

0 200 400 600 800 1000 1200 1400 1600100

102

104

106

108

Rank Out Degree

Cou

nt

Figura 4.18: Comparativa entre histograma del grado de salida y del ranking de grado desalida

Figura 4.19: Grado de salida y su ajuste potencial.


Figura 4.20: Rank del grado de salida y su ajuste potencial.

cialmente decrecientemente, aunque en ciertos grados existen picos. Por otra parte en lagrafica inferior representamos la misma informacion ordenada decreciemtemente, en estecaso el eje x no representa el grado sino el ranking de grado, desde el grado que apareceen mas nodos hasta el que menos. En este ultimo observamos que no tiene picos y tieneuna bajada muy suave, debido a la ordenacion.

Ambas representaciones son equivalentes y podemos convertir los ajustes de una enla otra [1], pero quizas es mas interesante para nosotros la superior porque nos permiteconocer para cada grado cuantas veces aparece, por ello en las siguientes graficas utili-zaremos la primera representacion (Power-law). Ajustando los parametros de la ecuacionpotencial obtenemos y = 14,22 ∗ x−0,173 − 3,592 que se ajusta con un R2 = 0,93 taly como puede verse en la figura 4.19. El valor es bastante alto pero no llega a 1 por lavariabilidad mencionada.

Tambien podemos construir un modelo para el grado ordenado por ranking. En estecaso la ecuacion es y = 25,25x−0,058 − 16,26 con R2 = 0,983 que puede verse en lafigura 4.20. En este caso vemos que el valor sı que es muy proximo a 1 debido a que noexisten los picos mencionados. Ademas podemos afirmar que se cumple la ley de ZIPFen el grado de salida de los nodos RDF.

De ahora en adelante representaremos solo la primera version por ser equivalentes. Porejemplo podemos representar simultaneamente el grado de entrada junto con el de salida(Figura 4.21). Como podemos observar, el grado de entrada tiene una tendencia potencialque sigue la ecuacion y = 12,03x−0,187 − 2,16 con R2 = 0,9. Ademas tambien podemosobservar que la frecuencia de los grados de entrada es en general superior a los grados desalida, lo cual es logico sabiendo que el numero de objetos es mayor que el de sujetos.

Tambien podemos representar graficamente los grados parciales tanto de entrada como

Figura 4.21: Distribucion de grados de entrada y de salida.

de salida. Recordemos que el grado parcial de salida es dado un sujeto y un predicado, encuantos triples aparece. De manera similar, el grado parcial de entrada es dado un objetoy un predicado, con cuantos sujetos se relaciona.

Por ejemplo en el siguiente fragmento de codigo, el objeto literal EMBL tendrıa gradoparcial de entrada = 2 (En el dataset real Bio2RDF, probablemente existan muchos sujetosque pertenezcan a la base de datos EMBL y por tanto el grado parcial de entrada sera muygrande): ”EMBL” . ”EMBL” .

De manera similar, el nodo bio2rdf:homologene:4585 tendra grado parcial desalida = 3. tambien tomado del dataset Bio2RDF: . . .

En la figura 4.22 podemos ver la representacion conjunta de la distribucion de gradosparciales de entrada y salida. Podemos observar que el grado parcial de entrada es signi-ficativamente mas grande que el de salida. Esto quiere decir que fijado un objeto con unpredicado (color rojo) es muy frecuente que aplique a muchos sujetos (existiran muchascosas rojas). Sin embargo fijado el sujeto con el predicado (Juan autor) no suele aplicar amuchos objetos (Juan no es autor de muchas cosas). Por supuesto esto es solo un ejemplodel comportamiento general, pero pueden existir contraejemplos donde sı que se den estospatrones. Por ejemplo en la grafica vemos el punto rojo en (x, y) = (800, 1000) que indicaque hay 1000 nodos diferentes con grado parcial de salida 800 (podrıa tratarse de un autormas avezado de lo habitual).

Figura 4.22: Distribucion de grados parciales de entrada y salida.

Ademas podemos ajustar un modelo potencial que se ajuste al grado parcial de salida:y = −34,04x0,0299 + 41,92 con R2 = 0,9515 y otro al grado parcial de entrada: y =84,28 ∗ x−0,0114 − 76,8 con R2 = 0,9505.

Tambien podemos analizar que ocurre con la metrica de grado etiquetado. El gradoetiquetado de salida es, fijando un sujeto, cuantos predicados diferentes tiene sin importarel numero de objetos. Por ejemplo siguiendo con el ejemplo de Bio2RDF:

 <r d f : type> . ” homologene :45 85 ” . < r d f s : l a b e l > ” [ homologene : 4 5 8 5 ] ” . . .

En este caso el nodo homologene:4585 tendrıa grado etiquetado de salida = 4,ya que tiene 4 predicados diferentes aunque bio2rdf:linkedToFrom se repita dosveces.

Del mismo modo podemos encontrar un ejemplo de grado etiquetado de entrada:

 <dc : c r e a t e d > ”2004−10−13” . <dc : c r e a t e d > ”2004−10−13” . <dc : modi f i ed> ”2004−10−13” . <dc : modi f i ed> ”2004−10−13” .

En el vemos que un mismo objeto, el literal que representa la fecha, esta asociadocon 4 objetos, pero solo tiene dos predicados diferentes, por tanto el grado etiquetado deentrada de ese nodo serıa 2.

Analicemos que ocurre con el grado etiquetado de entrada y salida en nuestro conjuntode datos, observando la figura 4.23. Vemos que en este caso se han cambiado las tornas y


Figura 4.23: Distribucion de grados etiquetados de entrada y salida.

ahora es el grado de salida etiquetado el que es mayor que el de entrada. Esto quiere decirque dado un objeto, normalmente no se relaciona con muchos predicados diferentes. Sinembargo los sujetos sı que se relacionan con varios predicados diferentes para describirvarias propiedades de un mismo recurso.

Podemos ajustar un modelo potencial para el grado parcial de salida: y = 14,62x−0,184−4,63 con R2 = 0,8867 y otro para el grado parcial de entrada: y = 10,69x−0,319− 1,9 conR2 = 0,9568.

4.3.5. Longitud de cadenasOtro parametro que podemos evaluar es la longitud de las cadenas, tanto de URIs,

como de literales y blancos. Los sujetos solo pueden ser URIs o blancos, ya que debemosindicar que recurso estamos describiendo en esa terna. Los objetos ademas de URIs yblancos podran tener literales indicando propiedades textuales o numericas.

El primer paso es comprobar cual es la proporcion de literales diferentes respecto altotal de objetos, y su distribucion puede verse en la figura 4.24. Lo primero que observa-mos es que tiene una forma aproximadamente normal centrada en 0,5, aunque con muchavariabilidad. Tambien destaca que el primer intervalo de la izquierda tiene muchos ele-mentos, lo que significa que muchos datasets apenas tienen literales en comparacion conel numero de objetos. Tambien vemos que la parte de la derecha esta muy vacıa lo quesignifica que existen pocos conjuntos de datos que esten formados en su mayor totalidadpor literales. Lo general, la moda, es que los conjuntos de datos ronden en torno a la mitadde literales y la mitad de URIs.

Analizando los conjuntos con una mayor proporcion de literales, nos damos cuen-

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 10

5

10

15

20

25

30

35

40

45

50

Ratio Literals/Objects

Cou

nt

Literal/Object Ratio distribution

Figura 4.24: Distribucion del ratio Literal/Objeto entre los distintos datasets.

ta que se tratan basicamente de descripciones de entidades, donde se declara un recursocomo perteneciente a un tipo mediante rdf:type y posteriormente se describen propie-dades textuales del mismo.

Una vez analizada la proporcion de URIs y Literales, procedemos a ver que ocurrecon la longitud de cada uno de ellos por separado.

Primero estudiaremos la longitud de las URIs, facilmente identificables porque en for-mato N3 se encierran entre angulos: <URI>. La distribucion de longitudes se puede obser-var en la figura 4.25. Lo primero que vemos es que la grafica comienza en 20, es decir, haymuy pocas URIs que tengan menos de 20 caracteres. Tambien vemos que tiene una formaparecida a la normal, pero con mucha variabilidad y con tres zonas que podemos llamarmodales y que tienen un mayor numero de elementos. En la grafica estan identificadasmediante una lınea roja vertical y se indican sus valores: 34, 52 y 87. Tambien podemosobservar una lınea muy larga de longitud 46 que se trata de la cadena rdf:type, en lagrafica se ha recortado para visualizar mejor el resto pero serıa aproximadamente el doblede larga de lo que aparece. Por ultimo citar que la longitud media de las URIs es de 59,27caracteres con una desviacion tıpica de 19,62.

A continuacion analizaremos que ocurre con las longitudes de los literales, a la vista dela figura 4.26. Lo primero que observamos es que los literales mas cortos tienen longitudtres, es decir un caracter entre las comillas que delimitan los literales en N3. Tambienvemos que tiene una forma trimodal con tres cuspides diferenciadas en 14, 53 y 70. Apartir de ese punto los literales se repiten con mucha menor frecuencia. Cabe destacar,que existen muchos literales de mas de 150 caracteres, existiendo algunos de hasta 50K,pero no se han representado en la grafica porque no se repiten con frecuencia y ocurren


20 40 60 80 100 120 1400

0.5

1

1.5

2

2.5

3

3.5

4x 106

URI Length

Cou

nt

URI Distribution

34 52 87

rdf:type7Million

Figura 4.25: Distribucion de longitudes de las URIs.

0 50 100 1500

2

4

6

8

10

12

14

16

18x 105

14 53 70

Literal length

Cou

nt

Literal length distribution

Figura 4.26: Distribucion de longitudes de los literales.

4.4. ANALISIS DE COMPRESION DE BT2010 CON HDT 59

L Cadena14 "Juska, Jane"14 "NINTENDO DS"14 CO:00020110"14 "Mosquito"@en53 .Exploiting Untrustworthy Agents in Team Formation."53 "Functionality Distribution for Parallel Rendering."53 "Fuzzy Backpropagation Training of Neural Networks."53 "http://4travel.jp/traveler/kyan/album/10436567/"@ja70 2ou know, you could search all your mail if you stored it with imap"70 .ENSXETT00000049182(11),FGENESH00000100361(9),GENSCAN00000051485(11)"70 "Prion-like-(Q/N-rich)-domain-bearing protein [affymetrix:180033 at]"34 <http://dbpedia.org/resource/Viceroy of Liangjiang>34 <http://u.2blog.jp/d/loveless />34 <http://schema.spam.com/#employs>34 <http://swrc.org/small1#Insitute>34 <http://www.amk.ca/books/h/Money>34 <http://bio2rdf.org/geneid:67103>52 <http://4travel.jp/traveler/yanjie/album/10140385/>52 <http://www.esri.com/metadata/catalog/adl/#d0e7172>52 <http://www.opengalen-cohse.org/#ImplantableDevice>52 <http://www.owl-ontologies.com/unnamed.owl#Digoxin>52 <http://www.daml.org/2001/01/gedcom/royal92#@F126@>87 <http://www.archiplanet.org/wiki/Special:ExportRDF/Eybl International Research Center>87 <http://www.co-ode.org/ontologies/amino-acid/2005/10/11/amino-acid.owl#Hydrophobicity>87 <http://www.bibsonomy.org/uri/bibtex/24dbca5bae8d39470c231c24124cf1b5a/matthias.kranz>87 <http://www.biologeek.com/django,freelance/freelance-django-enfin-independant/#c28518>87 <http://biomanta.sourceforge.net/2007/07/psimi instance edit.owl#cdna library MI 0343>

Cuadro 4.2: Cadenas extraıdas aleatoriamente de los tamanos modales en el diccionario.

de manera aislada.A modo de referencia tambien incluimos un histograma con la longitud de los no-

dos anonimos (Ver figura 4.27. Este no es significativo puesto que los nodos anonimosse han renombrado en el dataset BillionTriples anadiendo al final la URI completa delorigen para que no haya solapamiento entre conjuntos de datos diferentes. Por ejemplosi un nodo anonimo se identifica por :1, y aparece en Geonames y Bio2RDF se lla-mara :1geonames y :2bio2rdf respectivamente.

4.4. Analisis de compresion de BT2010 con HDT

Una vez conocemos las caracterısticas del conjunto de datos por sı mismo, procede-mos a analizar que ocurre cuando comprimimos cada uno de los subconjuntos utilizandola herramienta HDT. Cambiaremos los parametros de compresion y analizaremos concuales obtenemos los mejores resultados y buscaremos una explicacion en los parametrosmedidos anteriormente.

4.4.1. Diccionario

El primer paso es estudiar que ocurre con el tamano del diccionario. Como hemosvisto en las secciones anteriores, el vocabulario de sujetos y objetos crece de una manerapotencial con exponente menor que uno, por lo tanto es de esperar que el diccionario lohaga de una manera parecida.


60 80 100 120 140 160 1800

2

4

6

8

10

12

14

16x 105

84 99 164

Blank size distribution

Blank size

Freq

uenc

y

66

Figura 4.27: Distribucion de longitudes de los nodos anonimos.

103 104 105 106 107 108

103

104

105

106

107

Triples

Dic

tiona

ry E

ntrie

s

Dictionary Entries vs Triples

Figura 4.28: Crecimiento del tamano del diccionario respecto al numero de triples.


0

0.1

0.2

0.3

0.4

0.5

0.6

Dictionary Compression Method

Com

pres

sion

Rat

io

Dictionary compression ratio

GZIPBZIP2PPMDiRe−PairRe−Pair HF

Figura 4.29: Comparativa de los ratios de compresion del diccionario con los distintoscompresores universales.

Podemos ver el resultado en la figura 4.28. Como podemos ver el crecimiento delnumero de entradas en el diccionario es aproximadamente potencial a medida que incre-mentamos el numero de triples, ya que podemos ajustarlo a la curva y = 0,62x0,97 con unR2 = 0,95. Este resultado es muy interesante, puesto que dice que el tamano del diccio-nario crece de manera sublineal respecto al numero de triples, aunque si observamos elexponente vemos que el valor es muy cercano a la unidad.

A continuacion compararemos el tamano del diccionario en plano con los diferentesmetodos de compresion: GZIP2, BZIP23, PPMDI4, Re-Pair5, Re-Pair + Huffman6. Todosellos han sido compilados con gcc v4.3.2 con las opciones por defecto.

En la grafica 4.29 podemos ver la comparativa entre los mismos, donde cada barrarepresenta la media de todos los conjuntos de prueba y las lıneas adicionales representanla desviacion tıpica. Podemos observar que el peor es Re-Pair, incluso cuando aplicamosHuffman. Ademas necesita tener todo el conjunto de datos en memoria, lo cual para lasmagnitudes de las que estamos hablando es una limitacion muy fuerte. De hecho en lamaquina de prueba con 4GB de RAM no fue capaz de procesar los conjuntos de datosmayores, debido fundamentalmente al uso excesivo de memoria y a necesitar por tantomucha memoria virtual ralentizando el sistema. GZIP y BZIP se comportan adecuada-

2gzip v1.3.123BZIP2 v1.0.54http://pizzachili.dcc.uchile.cl/utils/ppmdi.tar.gz5http://www.dcc.uchile.cl/˜gnavarro/software/repair.tgz6shuff-1.1 Turpin y Moffat


SPO SOP PSO POS OSP OPS0

0.2

0.4

0.6

0.8

1

1.2C

ompr

essi

on ra

tio (a

gain

st P

lain

Trip

les)

Compression method

Triples Compression Methods Comparison

CompactCompact HFBitmapBitmap HF

Figura 4.30: Comparativa de parsing en la compresion de Triples, expresado como el ratiorespecto a PlainTriples.

mente, siendo BZIP un poco mejor a costa de tardar mas tiempo en comprimir. El quemejor tasa de compresion consigue es PPMDi.

4.4.2. TriplesRespecto a los triples deberemos analizar dos parametros, el tipo de parsing empleado

(Es decir, cual es el orden en las listas de adyacencia: SPO, SOP, PSO, POS, OSP u OPS),y el algoritmo de compactacion utilizado, CompactTriples o BitmapTriples. Ademas po-dremos aplicar Huffman para cambiar la codificacion de los enteros.

En las figuras 4.30 y 4.31 representamos la media de ratio de compresion obtenidopara todos los subconjuntos seleccionados de BT2010 comparando en cada caso con larepresentacion en plano PlainTriples. Ademas se indica en cada barra la variabilidad uti-lizando la desviacion tıpica de esa variable entre todos los conjuntos.

En la primera grafica se muestran todas las variantes agrupadas por metodo de par-sing y en el segundo por metodo de compactacion. Lo primero que podemos observar esque hay dos metodos de parseo (SOP y OSP) que incluso ocupan mas que mantener lostriples en plano. Esto es debido a que las listas de adyacencia son muy cortas y se introdu-cen ceros terminadores que tambien ocupan espacio, concretamente 32 bits. Los mejoresmetodos de parseo sin Huffman son POS y OPS, es decir los que acaban en el sujeto.

En todos los parsings tambien vemos una diferencia muy significativa de usar o noHuffman como codificador. En algunos casos se reduce el tamano hasta un 80 %. Tam-bien observamos que el tamano una vez comprimido con Huffman el ratio final es mucho


Compact Compact HF Bitmap Bitmap HF0

0.2

0.4

0.6

0.8

1

1.2C

ompr

essi

on ra

tio (a

gain

st P

lain

Trip

les)

Compression method

Triples Compression Methods Comparison

SPOSOPPSOPOSOSPOPS

Figura 4.31: Comparativa de compresion de Triples, expresado como el ratio respecto aPlainTriples.

mas equiparable entre metodos de parsing. Esto es debido a que Huffman ajusta el tamanode codigo a las frecuencias, es decir si cambiando el parsing conseguimos que un identi-ficador se repita menos veces, Huffman lo compensara asignandole un codigo mas largo,con lo cual la variabilidad global no es tan grande.

4.4.3. GlobalUn analisis interesante es observar que proporcion del tamano final del dataset ocupa

el diccionario y los triples. En la figura 4.32 podemos observar la distribucion de estavariable sin haber utilizado ningun metodo de compresion adicional. Comprobamos quela distribucion tiene una forma unimodal con media y moda en torno a 0,75 lo cual quieredecir que en general el diccionario ocupa la mayor parte del tamano final.

En la figura 4.33 podemos observar la misma proporcion pero esta vez utilizando elmejor metodo de compresion para cada uno de los casos. El diccionario, por tratarse detexto plano comprime mucho mejor y esta vez la distribucion es normal y centrada en 0,5,ocupando aproximadamente lo mismo el diccionario que los triples.

Un dato interesante a analizar es ver si existe una dependencia directa entre las me-didas de grados en el grafo y el ratio de compresion final. Para ello representamos en lasfiguras 4.34 y 4.35 todas las posibles combinaciones de medidas de grados con sus co-rrespondientes parsings. Observando vemos que muchos de ellos no tienen dependencia yaparece una zona dispersa, pero otros tienen lo que parece ser una dependencia potencial oexponencial. Por ejemplo elegimos uno de ellos, POSCompact y lo representamos frente


0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 10

10

20

30

40

50

60

70

80

Cou

nt

Dictionary/Triples Ratio

Dictionary/Triples Ratio Distribution

Figura 4.32: Distribucion del ratio Diccionario/Triples en plano.

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 10

5

10

15

20

25

30

35

40

45

Cou

nt

Dictionary/Triples Ratio

Compressed Dictionary/Triples Ratio Distribution

Figura 4.33: Distribucion del ratio Diccionario/Triples comprimido.


0 10 200.4

0.5

0.6

0.7

0.8

DegInAvg

SPO

1 1.5 20.4

0.5

0.6

0.7

0.8

DegLinAvg

SPO

0 10 200.4

0.5

0.6

0.7

0.8

DegPinAvg

SPO

0 10 200.4

0.5

0.6

0.7

0.8

DegInAvg

SOP

1 1.5 20.4

0.5

0.6

0.7

0.8

DegLinAvg

SOP

0 10 200.4

0.5

0.6

0.7

0.8

DegPinAvg

SOP

0 10 200.4

0.5

0.6

0.7

0.8

DegInAvg

PSO

1 1.5 20.4

0.5

0.6

0.7

0.8

DegLinAvg

PSO

0 10 200.4

0.5

0.6

0.7

0.8

DegPinAvg

PSO

0 10 200.4

0.5

0.6

0.7

0.8

DegInAvg

POS

1 1.5 20.4

0.5

0.6

0.7

0.8

DegLinAvg

POS

0 10 200.4

0.5

0.6

0.7

0.8

DegPinAvg

POS

0 10 200.4

0.5

0.6

0.7

0.8

DegInAvg

OSP

1 1.5 20.4

0.5

0.6

0.7

0.8

DegLinAvg

OSP

0 10 200.4

0.5

0.6

0.7

0.8

DegPinAvg

OSP

0 10 200.4

0.5

0.6

0.7

0.8

DegInAvg

OPS

1 1.5 20.4

0.5

0.6

0.7

0.8

DegLinAvg

OPS

0 10 200.4

0.5

0.6

0.7

0.8

DegPinAvg

OPS

Figura 4.34: Dependencia entre los grados de entrada y el ratio de compresion Compact-Triples en plano en distintos parsings.


0 10 20 300.4

0.5

0.6

0.7

0.8

DegOutAvg

SPO

0 10 20 300.4

0.5

0.6

0.7

0.8

DegLoutAvg

SPO

0 2 4 60.4

0.5

0.6

0.7

0.8

DegPoutAvg

SPO

0 10 20 300.55

0.6

0.65

0.7

0.75

DegOutAvg

SOP

0 10 20 300.5

0.6

0.7

0.8

0.9

DegLoutAvg

SOP

0 2 4 60.5

0.6

0.7

0.8

0.9

DegPoutAvg

SOP

0 10 20 300.4

0.5

0.6

0.7

0.8

DegOutAvg

PSO

0 10 20 300.4

0.5

0.6

0.7

0.8

DegLoutAvg

PSO

0 2 4 60.4

0.5

0.6

0.7

0.8

DegPoutAvg

PSO

0 10 20 300.2

0.4

0.6

0.8

1

DegOutAvg

POS

0 10 20 300.2

0.4

0.6

0.8

1

DegLoutAvg

POS

0 2 4 60.2

0.4

0.6

0.8

1

DegPoutAvg

POS

0 10 20 300.55

0.6

0.65

0.7

0.75

DegOutAvg

OSP

0 10 20 300.5

0.6

0.7

0.8

0.9

DegLoutAvg

OSP

0 2 4 60.5

0.6

0.7

0.8

0.9

DegPoutAvg

OSP

0 10 20 300.2

0.4

0.6

0.8

1

DegOutAvg

OPS

0 10 20 300.2

0.4

0.6

0.8

1

DegLoutAvg

OPS

0 2 4 60.2

0.4

0.6

0.8

1

DegPoutAvg

OPS

Figura 4.35: Dependencia entre los grados de salida y el ratio de compresion Compact-Triples en plano en distintos parsings.


5 10 15 20 25 30 35 40

0.5

1

1.5

Partial IN Degree

POS

Com

pact

Com

pres

sion

Rat

io

Compression Ratio / Partial IN Degree dependency

POS Compact SizePower FIT

Figura 4.36: Dependencia entre el ratio de compresion POS Compact y el grado parcialde entrada.

0 5 10 15 20 25 30 35 40 450

0.05

0.1

0.15

0.2

0.25

0.3

0.35

Partial In Degree

POS

Com

pact

+Huf

fman

Com

pres

sion

Rat

io

Compression Ratio / Partial IN Degree Dependency

Figura 4.37: Dependencia entre el ratio de compresion POS Compact+Huffman y el gradoparcial de entrada.


0

0.02

0.04

0.06

0.08

0.1

0.12

Compression method

Com

pres

sion

ratio

Compression ratio of the different methods

GZIPBZIP2PPMHDT

Figura 4.38: Comparativa del ratio final de compresion entre HDT y otros.

al grado parcial de entrada (Dado un predicado y objeto, con cuantos sujetos se relaciona),es decir comparten la parte PO. El resultado puede verse en la figura 4.36, existiendo unaclara relacion potencial con ecuacion: y = 0,6721x−1,139 + 0,3623 con R2 = 0,99.

Esto hace pensar que sı que existe realmente una relacion directa entre la medida deciertos grados en el grafo con el resultado final de compactacion en las listas de adyacenciaen formato plano.

Sin embargo, si probamos a generar las mismas tablas en formato CompactTriplespero con Huffman, vemos que las dependencias se difuminan. (No mostramos las tablasenteras por razones de espacio, pero en la figura 4.37 puede verse el equivalente al ejemploanterior). Esto es debido de nuevo a que Huffman compensa el tamano con el numero deapariciones de los elementos.

Por ultimo y mas interesante, deberemos comparar el ratio de compresion final de usarHDT a usar otros compresores generalistas como GZIP y BZIP2. El resultado se puede veren la figura 4.38, siendo HDT significativamente mejor, ocupando HDT menos espacioque sus alternativas.

Para demostrar que esto no ha ocurrido debido al azar por la muestra tomada, realiza-remos un test z comparando PPMPPM con HDT.

Para ello utilizaremos el siguiente estadıstico:

z =(X1 − X2)√

s21n1

+s22n2

=(0,0394− 0,0282)√

0,02372

374+ 0,1972

374

= 6,9786 (4.1)

Lo cual da un valor de p = 10−11. Por lo tanto podemos descartar la hipotesis nula sinmiedo a equivocarnos, HDT consigue una mejora significativa respecto a PPM.

4.5. HERRAMIENTA VISUAL 69

Figura 4.39: Pantalla inicial del visualizador HDT RDF.

4.5. Herramienta visual

Otra aproximacion para entender los datos RDF es visualizarlos graficamente paraentender su estructura y su distribucion. Al contrario que otros autores, nosotros visua-lizaremos el grafo RDF como una matriz de adyacencia, en lugar de visualizar el grafocomo nodos y relaciones. Para ello utilizaremos una representacion tridimensional de lamatriz de adyacencia, utilizando el eje x para objetos, el eje y para sujetos y el z parapredicados. De esta forma cada triple tendra asociado un unico punto en el espacio. Pa-ra mostrarlo en pantalla, sera necesario realizar una proyeccion de este espacio 3D enuno 2D, siendo la proyeccion ortogonal la mas adecuada por no realizar correcciones deperspectiva.

La herramienta se ha construido utilizando OpenGL [33] por ser una librerıa graficamuy potente que permite acelerar los calculos por hardware utilizando las tarjetas graficasmodernas, permitiendo mostrar gran cantidad de informacion en tiempo real. El usuariopuede rotar la vista tridimensional a su gusto de manera interactiva con el raton paraentender mejor la informacion mostrada.

El usuario debera indicar a la herramienta visual que conjunto de datos desea explo-rar. Por cuestiones de eficiencia, la herramienta solo es capaz de abrir ficheros en formatoHDT. Este es un ejemplo claro de aplicacion de HDT, los datos ya estan en formato com-pacto y por tanto no es necesario realizar ningun preprocesamiento, simplemente abrir elfichero HDT y cargar las estructuras auxiliares en memoria. La aplicacion accedera al dic-cionario HDT para realizar la conversion Identificadores-URIs o viceversa, y explorara los


Figura 4.40: Vista tridimensional del visualizador HDT RDF.

triples HDT para generar los puntos del grafo.El usuario se encontrara con una pantalla como la de la figura 4.39. En el se muestran

los ejes x e y de objetos y sujetos respectivamente, tal cual se verıan desde el eje z. Portratarse de una proyeccion ortogonal, todos los puntos de un mismo sujeto y objeto co-rresponden al mismo pixel de la pantalla independientemente del predicado. Ademas sepuede apreciar una cuadrıcula indicando el identificador de sujeto y objeto en cada eje.Existe tambien un cuadro coloreado cerca del origen que indica la zona de sujetos-objetoscompartidos, de manera que el usuario pueda observar si se cumplen caracterısticas dife-rentes en esta zona. En la figura se puede ver en la zona de la izquierda, indicando quepracticamente todos los sujetos de este conjunto de datos actuan tambien como objeto, esdecir, estan relacionados entre ellos. El usuario puede rotar la vista utilizando el raton, mo-verse utilizando el boton derecho y ampliar/reducir con el boton central del raton, comose puede ver en la figura 4.40.

En la parte superior izquierda se muestra la ruta del fichero HDT abierto para saber elconjunto de datos, y tambien se indica el predicado seleccionado a mostrar actualmente.Por defecto se muestran todos los predicados, pero pueden seleccionarse mediante Re-Pag, AvPag, o seleccionando cualquiera de ellos con el raton (O hacer click derecho paravolver a mostrar todos). En caso de que haya un predicado seleccionado, la herramientamostrara ademas el numero de triples de ese predicado.

Cuando el usuario pasa el raton por encima de los puntos que representan triples RDF,la aplicacion convierte las posiciones (x, y) en los identificadores sujeto y objeto corres-pondientes. Entonces la aplicacion buscara el triple mas cercano que se corresponda a esas


coordenadas, utilizando como metrica la distancia euclıdea. Entonces el sistema muestracon un aspa el punto encontrado, indicando en pantalla no solo los ındices, sino tambien laURI/Literal correspondiente haciendo uso para ello del diccionario HDT (Tambien visibleen la figura 4.39).

Para diferenciar unos predicados de otros se ha utilizado un codigo de color diferentepara representar cada uno de ellos. Lo ideal es que los colores generados sean lo masdiferentes posibles para poder diferenciarlos. Un algoritmo basico para hacerlo es utilizarel espacio de color HSB (Hue, Saturation, Brightness, en castellano Tonalidad, Saturacion,Brillo). Lo que haremos es ir rotando el valor de tonalidad en grados (de 0 a 360) e irdecrementando el brillo progresivamente. De esta manera conseguimos que el color dedos predicados seguidos sea bastante mas diferente.

Otra caracterıstica interesante es la de poder saber en que orden estan los puntos den-tro del dataset. Para ello lo mas facil y visual es realizar una animacion. Pulsando la tecla’R’, la aplicacion borrara todos los puntos de la pantalla y los ira dibujando por orden cre-ciente. El visualizador utiliza la representacion interna de triples PSO, es decir primerodibujara todos los sujetos-objetos del primer predicado, luego los del segundo y ası su-cesivamente. El ritmo de aparicion tambien es relevante, las zonas que se dibujen muyrapido sera que tienen poca densidad de puntos, y las zonas o predicados que tarden massignificara que tienen mas puntos.

Un primer problema es la escalabilidad. A pesar de la representacion compacta deHDT, el framework grafico no es capaz de enviar 3 millones de puntos con tres compo-nentes cada uno (12 Bytes por punto) y al menos a 30 frames por segundo. Ademas deser intratable tampoco es necesario, puesto que muchos de los puntos se solaparan enla pantalla, y apareceran como zonas completamente llenas solapando unos puntos conotros.

Para realizar el muestreo existen varias alternativas:

Muestreo equiespaciado: En lugar de mostrar todos los triples, mostramos uni-camente 1 de cada N. No tenemos control de que triples se eliminan, pero si ladensidad de puntos es grande no perderemos informacion global.

Realizar un histograma de intensidad: Dividimos el espacio tridimensional entexels, y para cada uno de ellos indicamos cuantos puntos se encuentran dentro.Posteriormente solo mostramos todos aquellos texels con valor mayor a la unidad.

Utilizar arboles bidimensionales o multidimensionales, como R-trees, K2-Treeso Quad-Trees. Permiten dividir el espacio en subfragmentos anidados unos dentrode otros, hasta llegar al nivel de detalle deseado. Son mucho mas eficientes si ladensidad de aristas es muy baja (como el caso que nos ocupa), aunque son masdifıciles de implementar.

En nuestro caso pensabamos que el muestreo equiespaciado perderıa demasiada infor-macion, pero tras probarlo comprobamos que para el objetivo de este visualizador es masque suficiente, puesto que lo que queremos es mostrar zonas y tendencias, nos da igual sise ignora algun punto aislado.

El numero de triples a eliminar en el muestreo dependera de la potencia de la maquina.

Figura 4.41: Ejemplo de lıneas verticales correspondientes al predicado rdf:type.

Figura 4.42: Ejemplo de lınea horizontal correspondiente los predicados rdf: N, ada unoidentificado por su color.

En el portatil de pruebas7 comprobamos experimentalmente que era capaz de mostrar confluidez (a 60FPS) alrededor de 200,000 puntos. Por lo tanto en caso de que el conjunto dedatos tenga mas de esos triples, tomaremos una muestra equiespaciada de ellos y sera laque trataremos.

4.5.1. Analisis visual de los conjuntos de datosUna vez explicadas las caracterısticas y el uso de la herramienta, observaremos con

ella los conjuntos de datos de BT2010, intando buscar patrones comunes y buscar explica-ciones a los mismos. De esta manera completamos el analisis cuantitativo de las seccionesanteriores con un analisis cualitativo basado en la observacion.

El primer analisis sera el de las formas. encontramos las siguientes:

Lınea vertical: Significa que un objeto se relaciona con muchos sujetos. Por ejem-plo es muy comun junto con el predicado rdf:type. Por ejemplo definimosla rdf:class Persona y posteriormente describimos muchas personas, el triple<?p><rdf:type><Persona> aparecera muchas veces, generando una lıneavertical en el visualizador. Cabe destacar que las lıneas no tienen por que ser siem-pre finas. Por ejemplo si las personas tienen profesiones identificadas por URI detipo <profesion:abogado> o <profesion:medico> estaran todas agru-padas en el eje x ya que estan ordenados lexicograficamente. La anchura de la lıneavendra definida por la cantidad de alternativas diferentes. Evidentemente si acer-camos suficientemente la vista sı que identificaremos las distintas profesiones, elefecto de lınea gruesa solo ocurre en una vista global. Por ejemplo en la figura 4.41

7Macbook Core2Duo 2Ghz, 4GB DDR3 Ram, Nvidia GeForce 9400M, MacOS X 10.6.6


podemos ver varias lıneas verticales correspondientes al predicado rdf:type delconjunto de datos revyu.

Lınea horizontal: Equivale a la vertical pero en este caso es un sujeto el que tienemuchos objetos con uno o varios predicados. Aunque no es tan comun como la ver-tical, si que aparece en ocasiones, especialmente cuando hay alguna enumeracion,como rdf:seq. Ademas en este caso cada elemento utilizara un predicado dife-rente rdf: 1, rdf: 2, y ası sucesivamente, cada uno expresado de un color. Sepuede ver un ejemplo en la figura 4.42.

Lınea diagonal: Representan correlaciones, por ejemplo si tenemos una URI derecurso tienda:ID0023 se etiqueta con rdfs:label “ID0023”. Como tantosujetos como objetos estan ordenados lexicograficamente, los IDs iran seguidos tan-to en la URI como en el literal, y daran lugar a una lınea diagonal. Dependiendo dela continuidad (no tienen por que ser IDs, o ni siquiera correlativos), encontraremosuna recta o algun tipo de curva con distintas pendientes. Tambien es tıpico encontrarestructuras de este tipo cuando aparecen nodos anonimos, ya que se suelen numerarde manera sucesiva.

Zona triangular. Tambien es habitual encontrar zonas triangulares superiores, queson similares a las lıneas diagonales pero con repeticiones. La lınea diagonal re-presenta la primera aparicion del elemento, mientras que los puntos que aparezcanen la parte de encima seran las repeticiones de los elementos ya definidos. En cier-tas ocasiones la diagonal no sera completamente recta, sino que tendra forma decurva polinomica, tıpicamente cuadratica (Ver figura 4.43). Cabe destacar que estoocurre especialmente cuando aplicamos tecnicas de reordenacion y reasignacion deındices.

Zona rectangular. En ciertas ocasiones existen zonas rectangulares con muchospuntos dispersos. Eso lo que representa son subconjuntos de sujetos que estan re-lacionados con subconjuntos de objetos, pero no existe una relacion lexicografi-ca entre esta relacion. Son candidatos perfectos a ser compactados con algoritmosde reasignacion de ındices para convertirlos en zonas triangulares o diagonales.Ademas introducen el concepto de localidad de referencia, ya que se encuentranproximos en el espacio. Este hecho tambien es interesante desde el punto de vistade la compresion, ya que se puede utilizar esa hipotesis para modelar los datos aligual que se hace en el caso de grafos Web.

Puntos aislados. Representan triples aislados que no conforman patrones especıfi-cos o tienen poca cantidad de puntos. Son candidatos ideales a ser dejados para elfinal en los algoritmos de clustering puesto que no seran muy relevantes desde elpunto de vista de la compresion final.

Una caracterıstica interesante de la herramienta visual es que nos permite ver como secomportan los datos ante la reasignacion de ındices. En la figura 4.43 vemos el conjuntode datos original Bibsonomy, que cuenta con 13 millones de triples y 409 predicados ydescribe autores junto con publicaciones. En la zona compartida observamos varias lıneasdiagonales, que pertenecen a listas rdf de nodos anonimos. En la parte superior podemos


Figura 4.43: Vista general del conjunto de datos bibsonomy antes y despues del clustering.


Figura 4.44: Vista general del conjunto de datos BerkeleyBop original antes y despues dela reasignacion de ındices.


ver un rectangulo que a partir de la herramienta observamos que son las relaciones en-tre artıculos, revistas y autores. A la derecha observamos otro rectangulo disperso, quecorresponde fundamentalmente a la asignacion de literales como nombres y tıtulos. Laslıneas verticales de la derecha corresponden como no a asignar el tipo RDF, tratandosefundamentalmente de Personas, y campo en el que trabajan. Este es un ejemplo de unconjunto de datos con muchos triples pero con una estructura nada compleja. Es mas,si realizamos el clustering (Ver figura 4.43 abajo), vemos como se agrupan los compo-nentes. El cuadro disperso de colores de abajo son las listas rdf. En la parte de arriba sehan agrupado en tres diagonales las relaciones entre autores, editores, y campos en losque trabajan. En la derecha se han agrupado los literales de nombres en una zona trian-gular debido a las repeticiones. Abajo sigue quedando una zona rectangular que son masdefiniciones de literales, pero esta vez con valores como URIs e identificadores de recur-sos. Arriba a la derecha con forma de Z aparecen las definiciones de la ontologıa comoowl:sameAs.

Si utilizaramos un modelo basado en superficie, sin duda esta reasignacion de ındicesserıa interesante. De todas maneras la herramienta visual solo es un indicio, lo ideal escomparar los algoritmos utilizando como medida el ratio final de compresion.

En algunas ocasiones el algoritmo actual de reasignacion de ındices no funciona tanbien como se podrıa esperar de el. Por ejemplo en la figura 4.44 vemos lo que ocurre en elconjunto de datos BerkeleyBop. Podemos observar que ha agrupado bastante el predicadorojo (correspondiente a rdfs:label pero todavıa han quedado bastantes puntos sueltos.

A continuacion se muestran las visualizaciones de algun conjunto de datos mas. Laconclusion que podemos sacar es que la herramienta de visualizacion nos permite observarlas estructuras RDF, en ciertas ocasiones observamos comportamientos con aparienciacaotica, pero en otros casos encontramos formas geometricas o patrones reconocibles. Elobjetivo de la compresion de triples RDF sera ser capaz de identificar y modelar estospatrones, para posteriormente codificarlos con codigos de redundancia mınima.

4.6. Resultados

A partir de nuestro estudio hemos llegado a los siguientes resultados:

La cantidad de triples por dominio en BT2010 sigue una distribucion power-law,pero dos zonas diferentes y distinta pendiente. Cabe esperar que en la Web ocurra lomismo, pero no podemos extrapolar por la forma en que se ha recopilado BT2010.

La mayorıa de los triples ocupan entre 100 y 2000 bytes, con la moda en 161.Existen triples de hasta 100KB.

A medida que incrementamos el numero de triples, tambien aumentaran de mane-ra sublineal (potencial con exponente menor que 1 pero proximo): el numero desujetos, objetos, SOCompartidos y entradas en el diccionario.

En general, los datasets suelen tener el doble de objetos que sujetos, aunque enalgunos casos excepcionales ocurre lo contrario.

4.6. RESULTADOS 77

El numero de SOCompartidos es aproximadamente del 15 %, superando escasasveces el 50 %.

El numero de predicados diferentes es independiente del numero de triples y engeneral pequeno.

El numero de triples que utilizan un predicado tiene forma power-law para algunosconjuntos de datos grandes. En otros casos la forma es impredecible.

Los grados de entrada y salida parciales, etiquetados y totales siguen una distribu-cion power-law.

El ratio de literales/objetos toma todos los valores entre 0 y 1, aunque encontramosdos modas en torno a 0 y a 0,5.

La longitud de las uris mas utilizadas suele estar entre 30 y 140, con modas en52 y 87. Destaca el gran uso de rdf:type con 7 millones de apariciones en losconjuntos de datos.

Son mas abundantes los literales cortos, entre 5 y 100 bytes, aunque existen literalesmuy largos.

El metodo de compresion de diccionario con mejor ratio es PPMDi, seguido deBZIP2 y GZIP. Re-Pair es muy lento y consigue peores ratios incluso con Huffman.

Sin utilizar Huffman, el mejor tipo de parsing para los triples en plano es OPS yPOS. El uso de bitmaps mejora significativamente a la representacion compactabasada en listas de adyacencia. Al utilizar Huffman las diferencias entre Compact/-Bitmap y los parsings son menos significativas.

Sin comprimir ni diccionario ni triples, el tamano del diccionario ocupa alrededordel 75 % del total, por ser texto plano. Una vez comprimidos ambos, el espacio entrediccionario y triples es aproximadamente similar. A pesar de este comportamientogeneral, existe mucha variabilidad en esta proporcion.

Los grados de entrada y salida afectan notablemente al ratio de compresion de larepresentacion en plano. Una vez codificado con Huffman la relacion es poco apre-ciable.

La mejor representacion de las posibles usando HDT, es significativamente mejorque comprimir el N3 usando PPM, BZIP2 y GZIP, en este orden.

El uso de la herramienta visual permite encontrar patrones, como zonas con locali-dad de referencia, objetos y sujetos muy compartidos (lıneas verticales y horizonta-les), y zonas aleatorias mas dispersas.

La herramienta visual nos permite ver la estructura RDF, y encontrar tanto patronescomo comportamientos caoticos.


El uso de la reasignacion de ındices reorganiza la informacion de manera que agrupaen conjuntos mas cohesivos. En ocasiones el funcionamiento es adecuado pero esnecesario investigar nuevos metodos de agrupamiento y estudiar su influencia en latasa de compresion final.

Capıtulo 5

Conclusiones y Trabajo Futuro

En este trabajo hemos analizado las caracterısticas de un conjunto grande de datosRDF, teniendo como objetivo encontrar patrones que den ideas de como mejorar la com-presion de este tipo de datos. Para ello hemos realizado tanto un analisis cuantitativobasado en metricas, estadısticas y construccion de modelos, como un analisis cualitativobasado en un metodo nuevo de representar informacion RDF, apropiado para mostrar lainformacion segun la almacena HDT.

Hemos encontrado que en multitud de casos aparecen leyes Power-law, por ejemploen el crecimiento del numero de sujetos y objetos, en el crecimiento del diccionario o enlos grados de salida de los nodos. Es muy interesante conocer este dato desde el puntode vista de la compresion, ya que podemos comprimir los elementos que aparecen nu-merosas veces utilizando codigos mas cortos que en los que lo hacen menos veces. Aunası debemos tener cuidado con los disenos estructurales, ya que las colas largas aunquetienen pocas repeticiones, tienen muchos elementos.

Tambien es destacable que el numero de predicados no depende del numero de triples,y su numero es en general reducido. Esto se debera tener en cuenta a la hora de disenarlas estructuras de datos y los algoritmos.

En cuanto a la herramienta grafica propuesta comprobamos que es bastante util desdeel punto de vista del analista que desea conocer mas acerca de la estructura de un conjuntode datos grande RDF. Se pueden identificar los sujetos y objetos mas relevantes, encontrarzonas con localidad de referencia, o ver el grado de alineamiento o dispersion entre suje-tos y predicados. Tambien es muy util de cara al estudio de tecnicas de reasignacion deındices, pudiendo ver las modificaciones en lınea. Ademas en nuestro analisis cualitativono solo hemos citado los patrones encontrados, sino que tambien hemos propuesto expli-caciones de por que se dan estas caracterısticas, creando una asociacion entre los hechosy la representacion visual.

Desde el punto de vista de HDT comprobamos que es una muy buena idea desde elpunto de vista no solo de compresion de informacion en formato RDF, sino tambien demedio de almacenamiento y organizacion. La herramienta grafica sirve como ejemplo deuna aplicacion que utiliza HDT como formato de representacion interna que permite hacerbusquedas rapidamente, e incluso mostrarlo en tiempo real.

Hemos comprobado que HDT mejora significativamente la tasa de compresion res-pecto a metodos de compresion general. Hemos visto que dependiendo del tipo de datoses mas conveniente un tipo de orden para Sujeto, Predicado y Triples. En general PSO

79

80 CAPITULO 5. CONCLUSIONES Y TRABAJO FUTURO

y POS han obtenido los mejores resultados ası que son candidatos a ser utilizados comoparametro por defecto.

Usar algoritmos generales para comprimir el diccionario y los triples tambien reduceel numero final de bytes, pero deberemos tener en cuenta que al hacerlo no siempre esposible realizar busquedas. Dependiendo de si lo vamos a utilizar como almacenamiento,como ındice, o ambos, decidiremos que tipo de compresion utilizar.

Este trabajo cubre un area poco tratada en la bibliografıa, que es estudiar el RDF desdeel punto de vista de la compresion. Aun ası hemos obtenido resultados que pueden serinteresantes para cualquiera que necesite tratar con volumenes grandes de datos en RDF.Hemos explicado rigurosamente todo el proceso seguido en la fase de experimentacion,de manera que otros autores puedan reproducir nuestros experimentos y/o aprender denuestra metodologıa.

Como trabajo futuro del estudio, se podrıan aplicar muchos otros tipos de tecnicas.Por ejemplo serıa interesante realizar un analisis de regresion logıstico o un analisis decomponentes principales para ver cuales son los parametros (ratio de compartidos, gra-dos...) que mas afectan a la compresion final. Tambien serıa interesante aplicar tecnicasavanzadas de data mining, como algoritmos de aprendizaje o metodologıas de analisis degrafos. Por ultimo serıa aconsejable aplicar algun tipo de analisis de varianza para ver lavariabilidad en los parametros por cada conjunto.

Tambien serıa interesante utilizar otros corpus a parte de BT2010 como evaluacion ycomprobar si los patrones y modelos que hemos obtenido con el son aplicables a otros, yestimar en que grado esto serıa generalizable a los datos Linked-Data de la Web.

HDT todavıa cuenta con muchos areas de mejora. Por ejemplo nuevas propuestas derepresentacion del diccionario y los triples, integracion de codificadores tipo Huffman,Re-Pair y PPM. Desde el punto de vista de la reasignacion de ındices deberemos ser cui-dadosos eligiendo el conjunto de entrenamiento. Si disenamos los algoritmos para mejorarunos conjuntos de datos concretos, es probable que empeoremos en el resto.

Desde el punto de vista de este estudio como Trabajo Final de Master, ha servidoal alumno para realizar un trabajo de investigacion de principio a fin. Desde la fase deanalisis de la bibliografıa para conocer el estado del arte en la materia, pasando por la fasede diseno, ejecucion y analisis de experimentos, hasta la fase final de documentacion. Elsiguiente paso sera identificar algun foro cientıfico, como un workshop, una conferenciao una revista cientıfica y elaborar un artıculo para compartir los resultados del estudiocon la comunidad. De esta manera estaremos contribuyendo con nuestra investigacion alavance cientıfico y tambien obtendremos realimentacion de otros expertos en campo decomo continuar nuestro trabajo.

Una caracterıstica de este trabajo es que bastante multidisciplinar dentro del area deTecnologıas de la Informacion, por lo tanto ha sido necesaria la lectura y profundizacionen distintas areas. Estamos trabajando con informacion semantica, por lo tanto necesi-tamos conocer conceptos como RDF, OWL, ontologıas y como se define este tipo deinformacion. Tambien trabajamos con estructuras de datos sucintas y compresion, muyrelacionado con la teorıa de la informacion. Por otro lado para el estudio necesitamosmetodologıas y herramientas tanto matematicas como estadısticas para realizar el estudiocon rigor cientıfico. Para finalizar la herramienta de visualizacion requiere conocimientotanto de manejo de graficos tridimensionales, como de interaccion hombre-maquina.

Bibliografıa

[1] L. A. Adamic. Zipf, power-laws, and pareto, a ranking tutorial. Technical re-port, April 2000. http://www.hpl.hp.com/research/idl/papers/ranking/ranking.html [10/01/2011].

[2] Andreas Harth. Billion Triples 2010 Dataset, 2008. http://km.aifb.kit.edu/projects/btc-2010/ [10/01/2011].

[3] Soren Auer, Christian Bizer, Georgi Kobilarov, Jens Lehmann, Richard Cyganiak,and Zachary Ives. Dbpedia: a nucleus for a web of open data. In Proceedings ofthe 6th international The semantic web and 2nd Asian conference on Asian seman-tic web conference, ISWC’07/ASWC’07, pages 722–735, Berlin, Heidelberg, 2007.Springer-Verlag.

[4] David Beckett and Tim Berners-Lee. Turtle - terse rdf triple language. W3C teamsubmission, W3C, January 2008. http://www.w3.org/TeamSubmission/turtle/.

[5] David Beckett and Brian McBride. RDF/XML syntax specification. W3C recom-mendation, W3C, February 2004. http://www.w3.org/TR/REC-rdf-syntax/.

[6] Christian Bizer, Tom Heath, Kingsley Idehen, and Tim Berners-Lee. Linked data onthe web (ldow2008). In Proceeding of the 17th international conference on WorldWide Web, WWW ’08, pages 1265–1266, New York, NY, USA, 2008. ACM.

[7] Christian Bizer, Jens Lehmann, Georgi Kobilarov, Soren Auer, Christian Becker,Richard Cyganiak, and Sebastian Hellmann. Dbpedia - a crystallization point forthe web of data. Web Semant., 7:154–165, September 2009.

[8] Christian Bizer and Diana Maynard. Semantic web challenge, 2010. http://challenge.semanticweb.org [10/01/2011].

[9] Dan Brickley and R.V. Guha. RDF vocabulary description language 1.0: Rdf sche-ma. W3C recommendation, W3C, feb 2004. http://www.w3.org/TR/rdf-schema/.

[10] Dan Brickley and Libby Miller. FOAF vocabulary specification. Technical report,FOAF, nov 2007. http://xmlns.com/foaf/spec/.

[11] Jeen Broekstra, Arjohn Kampman, and Frank van Harmelen. Sesame: A genericarchitecture for storing and querying rdf and rdf schema. In Proceedings of the FirstInternational Semantic Web Conference on The Semantic Web, ISWC ’02, pages54–68, London, UK, 2002. Springer-Verlag.

81

82 BIBLIOGRAFIA

[12] M. Burrows and D. J. Wheeler. A block-sorting lossless data compression algorithm.Technical Report 124, 1994.

[13] Roger Castillo. Rdfmatview: Indexing rdf data for sparql queries. In 9th Internatio-nal Semantic Web Conference (ISWC2010), November 2010.

[14] Aaron Clauset, Cosma R. Shalizi, and M. E. J. Newman. Power-Law Distributionsin Empirical Data. SIAM Review, 51(4):661–703, 2009.

[15] Dan Connolly, Frank van Harmelen, Ian Horrocks, Deborah L. McGuinness, Peter F.Patel-Schneider, and Lynn Andrea Stein. DAML+OIL reference description. W3Cnote, W3C, December 2001. http://www.w3.org/TR/daml+oil-reference.

[16] DCMI. Dublin core metadata initiative. Technical report, DCMI, nov 2010.http://www.dublincore.org.

[17] Li Ding and Tim Finin. Characterizing the semantic web on the web. In In Procee-dings of the 5th International Semantic Web Conference. Springer Verlag, 2006.

[18] Javier D. Fernandez, Claudio Gutierrez, and Miguel A. Martınez-Prieto. Rdf com-pression: basic approaches. In Michael Rappa, Paul Jones, Juliana Freire, and Sou-men Chakrabarti, editors, WWW, pages 1091–1092. ACM, 2010.

[19] Javier D. Fernandez, Miguel A. Martınez-Prieto, and Claudio Gutierrez. Compactrepresentation of large rdf data sets for publishing and exchange. In Peter F. Patel-Schneider, Yue Pan, Pascal Hitzler, Peter Mika, Lei Zhang, Jeff Z. Pan, Ian Horrocks,and Birte Glimm, editors, International Semantic Web Conference (1), volume 6496of Lecture Notes in Computer Science, pages 193–208. Springer, 2010.

[20] Javier D Fernandez, Miguel A. Martınez-Prieto, and Claudio Gutierrez. Compactrepresentation for RDF data sets. Technical report, University of Valladolid andUniversity of Chile, August 2010. http://hdt.dcc.uchile.cl/.

[21] Javier D Fernandez, Miguel A. Martınez-Prieto, Claudio Gutierrez, and Axel Polle-res. Header-Dictionary-Triples representation for RDF (HDT) submission. W3Csubmission, W3C, August 2010. http://hdt.dcc.uchile.cl/Overview.html.

[22] Freebase. Freebase data dumps. http://download.freebase.com/datadumps/, 2010.

[23] Rosa Gil, R. Garca, and J. Delgado. Measuring the semantic web. SIGSEMIS Bu-lletin, 1, 2004.

[24] Gunnar Aastrand Grimnes. Billion Triples Statistics, 2010.http://gromgull.net/blog/category/semantic-web/billion-triple-challenge/ [10/01/2011].

[25] D.A. Huffman. A method for the construction of minimum-redundancy codes. Pro-ceedings of the IRE, 40(9):1098 –1101, September 1952.

BIBLIOGRAFIA 83

[26] Andreas Langegger and Wolfram Woss. RDFStats - An Extensible RDF StatisticsGenerator and Library. 2009 20th International Workshop on Database and ExpertSystems Application, pages 79–83, 2009.

[27] N. Jesper Larsson. Structures of String Matching and Data Compression. PhD the-sis, Department of Computer Science, Lund University, Sweden, September 1999.

[28] Jean loup Gailly and Mark Adler. GZIP compression implementation, 2003. http://www.gzip.org [10/01/2011].

[29] Frank Manola and Eric Miller. RDF primer. W3C recommendation, W3C, feb 2004.http://www.w3.org/TR/2004/REC-rdf-primer-20040210/.

[30] Miguel A. Martınez-Prieto. Estudio y aplicacion de nuevos metodos de compresionde texto orientada a palabras. PhD thesis, Universidad de Valladolid, July 2010.

[31] Deborah L. McGuinness and Frank van Harmelen. OWL web on-tology language overview. W3C recommendation, W3C, feb 2004.http://www.w3.org/TR/2004/REC-owl-features-20040210/.

[32] A. Moffat. Implementing the ppm data compression scheme. Communications,IEEE Transactions on, 38(11):1917 –1921, November 1990.

[33] Opengl, D. Shreiner, M. Woo, J. Neider, and T. Davis. OpenGL(R) Program-ming Guide : The Official Guide to Learning OpenGL(R), Version 2 (5th Edition).Addison-Wesley Professional, August 2005.

[34] Eric Prudhommeaux and Andy Seaborne. SPARQL query language for RDF.W3C recommendation, W3C, January 2008. http://www.w3.org/TR/2004/REC-rdf-primer-20040210/.

[35] Julian Seward. BZIP2 compression implementation, 2006. http://www.bzip.org [10/01/2011].

[36] Y. Theoharis. On power laws and the semantic web. Mas-ter thesis, University of Crete, February 2007. athe-na.ics.forth.gr:9090/RDF/publications/MasterThesisTheohari.pdf.

[37] Tim Berners-Lee. Notation3(N3) A readable RDF Syntax, 1998. http://www.w3.org/DesignIssues/Notation3.html [10/01/2011].

[38] Tom Heah. Linked Data, 2008. http://linkeddata.org [10/01/2011].

[39] UniProt Consortium. UniProt, 2002-2010. http://www.uniprot.org [10/01/2011].

[40] Cathrin Weiss, Panagiotis Karras, and Abraham Bernstein. Hexastore: sextuple in-dexing for semantic web data management. Proc. VLDB Endow., 1:1008–1019,August 2008.

[41] Jacob Ziv and Abraham Lempel. A universal algorithm for sequential data compres-sion. IEEE Transactions on Information Theory, 23(3):337–343, 1977.

analisis de conjuntos de datos rdf para mejorar´ la...

Documents