Effective reorganization and self-indexing of big semantic data

PROGRAMA DE DOCTORADO EN INFORMÁTICA TESIS DOCTORAL: Effective Reorganization and Self-Indexing of Big Semantic Data Presentada por Antonio Hernández Illera para optar al grado de Doctor/a por la Universidad de Valladolid Dirigida por: Miguel Ángel Martínez Prieto Javier David Fernández García Agradecimientos Hace tiempo le´ı una dedicatoria en un trabajo de fin de grado: “A mis padres, por aguantarme”. En aquel momento la frase me pareci´o algo pueril, pero en realidad contiene una gran carga de emotividad, pues dependiendo del sentido que se le de al verbo, el significado de la frase se balancea entre la broma y el m´as profundo agradecimiento. Hoy, siendo padre de dos hijas peque˜nas, solo soy capaz de intuir la dif´ıcil tarea que implicar´a el aguantarlas firmemente, sustentarlas para que no caigan, y si lo hacen, saber curar bien sus heridas. Que el remedio no sea peor que la enfermedad. Tiempo atr´as, fueron las manos de mi madre las que nos soportaron a mi hermana y a m´ı. Ell´a nos indic´o el camino de la formaci´on como aquel que deb´ıamos de seguir, pese a que ella a penas lo hubo caminado. Hoy quiero aprovechar para dedicar estas l´ıneas a todas las mujeres que me han mantenido en pie a lo largo de mi vida: mi abuela Felicitas, mi madre Genoveva, mi t´ıa ´ Angeles, mi hermana Eva, mi esposa Lourdes y mis hijas Carmen y Ana. Gracias a todas ellas, en especial a mi madre (a la que nunca antes se lo hab´ıa dicho), sin cuya dedicaci´on y entereza hoy no estar´ıa ecribiendo esto y, en cierto modo, siento que este trabajo es m´as suyo que m´ıo. Gracias por el esfuerzo que te supuso el darnos una formaci´on cuando no pod´ıas permit´ırtelo. Miguel y Javi, ha sido un verdadero honor teneros a mi lado en esta aventura. Gracias por vuestro tiempo, dedicaci´on, entrega, conocimientos, experiencia, asesoramiento y, por encima de todo, gracias por vuestro entusiasmo, pasi´on y fuerza vital tan contagiosa. Ni que decir tiene que nunca habr´ıa escrito esta tesis sin vuestra ayuda y apoyo. La Universidad de Valladolid debe de estar bien orgullosa de forjar profesionales como vosotros. Abstract The classic Web infrastructure used to publish, consume, and exchange content is also available to host raw data so machines can access and process such information. This so-called Web of Data has grown exponentially in recent years, weaving its own net of online, connected datasets, using RDF as a common language and a bridge between them. All this amount of generated RDF data result in huge collections, consequently opening the doors to various lines of research, including RDF data compression, which optimizes the storage and streamlines data exchange. In contrast to universal compressors, RDF compression techniques are able to detect and exploit specific forms of redundancy, leveraging syntactic and semantic redundancies in RDF data. However, to date, little attention has been paid to some structural regularities that real-world datasets follow and that constitute another source of redundancy. In this thesis we have analyzed the structural redundancy that the RDF graph inherently possesses and we have proposed a preprocessing technique called RDF-Tr (RDF Triples Reorganizer) which groups, reorganizes and re-codes RDF triples, alleviating two sources of structural redundancy underlying the schema-relaxed nature of RDF. We have integrated RDF-Tr into two of the main state-of-the-art RDF compressors, HDT and k2-triples, significantly reducing in both cases the size that the original compressors achieve, thus outperforming the most prominent stateof-the-art techniques. We have denominated HDT++ and k2-triples++ the result of applying RDF-Tr to each compressor. RDF is supported by a whole set of semantic technologies that allows, among other things, access to data in large RDF collections thanks to SPARQL, its own SQL-like query language. In the field of RDF compression, different compact data structure configurations are used to build RDF self-indexes, providing efficient access to the data without (partial or total) decompression. The indexed HDT (called HDT-FoQ) was the pioneer in this scenario and is nowadays used by the semantic community to publish and consume large RDF data collections. In this thesis, we could not ignore this fact, and we have extended HDT++ (called iHDT++) to support full SPARQL Triple Patterns resolution, consuming less memory than its counterpart. We have proven that iHDT++ reduces by 20-45% the space that HDT-FoQ needs, while speeding up the resolution of most Triple Pattern queries, reporting space-time tradeoffs that compete and outperform, in different scenarios, the state-of-the art RDF self-indexes. Resumen La infraestructura de la Web cl´asica que utilizamos para publicar, consumir e intercambiar contenido, tambi´en est´a disponible para alojar el raw data que puede ser accedido y procesado por las m´aquinas. Esta Web de Datos ha experimentado un crecimiento exponencial durante los ´ultimos a˜nos, tejiendo su propia red de datasets (conjuntos de datos) interconectados y disponibles en l´ınea, utilizando RDF como lenguaje com´un, haciendo de puente entre ellos. Esta enorme cantidad de datos en RDF deviene en colecciones de datos de gran tama˜no, y ha abierto las puertas a diversas l´ıneas de investigaci´on, incluyendo la compresi´on de datos en RDF, que optimiza el espacio de almacenamiento y, a su vez, agilizando su intercambio. A diferencia de los compresores universales, las t´ecnicas de compresi´on de RDF detectan y tratan las redundancias espec´ıficas que poseen a niveles sint´actico y sem´antico. Sin embargo, hasta la fecha, se ha prestado poca atenci´on a ciertos patrones estructurales que los conjuntos de datos del mundo real siguen y que constituyen otra fuente de redundancia. En esta tesis hemos analizado la redundancia estructural que los grafos RDF inherentemente poseen y hemos propuesto una t´ecnica de preprocesamiento llamada RDF-Tr (RDF Triples Reorganizer) que agrupa, reorganiza y recodifica los triples, tratando dos fuentes de redundancia estructural subyacentes a la naturaleza del esquema RDF. Hemos integrado RDF-Tr en dos de los principales compresores RDF del estado del arte, HDT y k2-triples, reduciendo significativamente en ambos casos el tama˜no que obtienen los compresores originales, superando a las t´ecnicas m´as prominentes del estado del arte. Hemos denominado HDT++ y k2-triples++ al resultado de aplicar RDF-Tr en cada compresor. RDF adem´as, se apoya en un conjunto de tecnolog´ıas sem´anticas que permiten, entre otras cosas, hacer consultas a las grandes colecciones de datos en RDF gracias a SPARQL, un lenguaje de consulta propio parecido a SQL. En el ´ambito de la compresi´on RDF se utilizan diferentes configuraciones de estructuras de datos compactas para construir auto-´ındices RDF, que proporcionan acceso eficiente a los datos sin necesidad de una descompresi´on previa de los mismos (parcial o total). HDT-FoQ, la versi´on indexada de HDT, fue el pionero en este ´ambito y hoy en d´ıa es utilizado por la comunidad sem´antica para publicar y consumir grandes colecciones de datos RDF. En esta tesis no pod´ıamos ignorar este hecho, y hemos extendido HDT++, llam´andolo iHDT++, para permitir la resoluci´on de patrones de tripletas SPARQL consumiendo menos memoria que HDT-FoQ. Hemos demostrado que iHDT++ reduce en un 20-45 % el espacio que necesita HDT-FoQ, a la vez que acelera la resoluci´on de la mayor´ıa de las consultas por patr´on de tripleta, mejorando la relaci´on espacio-tiempo, en algunos escenarios, del resto de auto-´ındices RDF del estado del arte. Figure 1.1: Evolution of the Linked Open Data cloud. evolution can be seen in Figure 1.1, where the first twelve datasets that, in 2007, originally formed the LOD cloud [38] (i.e., open and interconnected datasets) can be seen on the left. In contrast, the right hand side of the Figure shows the growth that the LOD cloud has experienced in these twelve years, where it is virtually impossible to visualize any of the 1,239 datasets. Note that DBpedia [3] is really at the core of the LOD, as it is present in the center of both clouds. The reason for this is that DBpedia is based on the Wikipedia structured content (mainly infoboxes), and hence contains cross-domain information that references to (and is referenced by) specific knowledge datasets. Since the first version of the LOD cloud in 2007, many important projects of heterogenous fields of knowledge have joined the initiative, such as geography (e.g., LinkedGeoData1, with more than 1.2 billion statements), life sciences (e.g., Bio2RDF2, 11 billion statements) or general knowledge (e.g., DBpedia3or more recently WikiData4with 9.5 billion and 8 billion statements respectively). One of the main achievements of the Linked Open Data project is that the datasets that comprise the LOD cloud share their information in the same language, in order to make it easy for machines to access, browse and navigate their data model. RDF. The W3C (World Wide Web Consortium) proposed a model to describe, publish and interchange data on the Web called RDF (Resource Desciption Framework) [32]. The information in RDF is expressed through 1http://linkedgeodata.org/ 2http://bio2rdf.org/ 3http://www.dbpedia.org/ 4https://www.wikidata.org/ 6 Figure 1.2: Example of an RDF graph. triples, each one comprising the resource being described (i.e., subject), a property of that resource (i.e., predicate), and the corresponding value (i.e., object). This linking structure forms a directed, labeled graph, where the edges represent the named link between two resources; i.e., the graph nodes. Within a triple, a subject can be a URI or a blank node (i.e., anonymous resource), a predicate must be a URI and the object can be a URI, a blank node (or bnode) or a literal. A more formal definition can be found in Section 2.1. A simple but real example of an RDF graph, extracted from DBpedia, is shown in Figure 1.2, where we have a few triples representing some features about the University of Valladolid5: It is a University established in 1290 whose motto is ”Sapientia Aedificavit Sibi Domvm (Latin)”. Besides, it is present in two cites, Valladolid and Palencia, both are part of Castile and Le´on, in Spain. An example of a triple is (:University of Valladolid, dbo:motto, "Sapientia Aedificavit Sibi Domvm (Latin)" ), which expresses the motto of the University. The W3C recommends syntaxes for storing and exchanging RDF such as Turtle [46], JSON-LD [50] or N-Triples [13], among others, but RDF is not tied to a fixed serialization format, hence the RDF Graph in Figure 1.2 can be written in any standard RDF format. For example, the Turtle and N-Triples serializations for our example are shown in Figure 1.3. All RDF formats convey the same meaning, but they also suffer the same problems: their high level of verbosity and redundancy. Although 5http://dbpedia.org/page/University of Valladolid 7 Figure 1.3: Serialization of the RDF graph. Turtle mitigates redundancy by grouping prefixes (with the inclusion of "@prefix" terms) and using some sort of adjacency lists, arbitrary long URIs (e.g., http://dbpedia.org/resource/Castile and Le´on) are still present in several triples, playing the role of subjects and/or objects. Verbosity and redundancy are particularly troubling in the Linked Open Data domain, where large datasets are increasingly consolidated. This problem is not new, but remains challenging [16] and is usually referred to as Big Semantic Data management [34]. In this scenario, the W3C Member Submission, HDT (Header – Dictionary – Triples) [19] [18], emerges as the first RDF binary serialization that proposes to transform the classical RDF graph to a graph of integer IDs. HDT minimizes the repetition of potentially large strings using a Dictionary, which assigns a numerical ID to each term in the dataset. It divides the RDF terms into four subsets lexicographically sorted, depending on the role that each RDF term plays within the dataset (subject, predicate, object or subject-object6). This partitioning [2] avoids the duplication of terms in the dictionary, since up to 60% of the RDF terms of a dataset belong to the subject-object category [37]. Figure 1.4 shows the four clusters of RDF terms in the Dictionary component, and the transformed ID graph corresponding to our example. To decode Triple-ID, for example (4, 4, 7), we just have to look for the particular ID of each term (subject, predicate and object) in their specific Dictionary. Therefore, sub6HDT refers to ”subject-object” as the terms that play both subject and object roles in the dataset. 8 Figure 1.4: Our example as a graph of integer IDs. ject 4 corresponds to the term :University of Valladolid; the predicate 4 is dbo:motto; and finally, the object 7 encodes the literal "Sapientia Aedificavit Sibi Domvm (Latin)" . The original triple is retrieved replacing the identifiers with their corresponding RDF terms, (:University of Valladolid, dbo:motto, "Sapientia Aedificavit Sibi Domvm (Latin)" ). SPARQL. While it is true that the main use of RDF compression is for the publication and exchange of Big Semantic Data, HDT finds its maximum expression when querying these large collections of linked data through a query language, SPARQL (SPARQL Query Language for RDF) [47]. The simplest form of querying RDF with SPARQL is a Triple Pattern, an RDF triple in which any of its components (subject,predicate,object) can be a variable (denoted by a question mark) or a constant. Therefore, eight possible combinations (i.e., Triple Patterns) are possible: {(?,?,?), (?,?,o), (?,p,?), (?,p,o), (s,?,?), (s,?,o), (s,p,?), (s,p,o)}. The following example, (:University of Valladolid,dbo:motto,?o) asks for the object of the triple; i.e., we want to know the actual motto of the University of Valladolid. Tra9 ditionally, SPARQL queries have been made possible thanks to endpoints provided by specific RDF graph storage artifacts (i.e., triple stores) that allow the query of their contents. However, HDT introduced a novelty in the SPARQL field, since it is the first RDF serialization technique that allows Triple Pattern query resolution on the file, without the need for any additional support (i.e., triple stores), but adding some indexes to accelerate their resolution. HDT-FoQ (HDT Focused on Querying) [33] is the extension of the HDT model that attaches some compact data structures that make simple but efficient data retrieval possible. For these reasons, HDT is an RDF binary serialization format, but it is also used as a storage engine in well known Semantic Web projects such as Linked Data Fragments (LDF)7,LOD Laundromat8[5] or LOD-a-lot [17]. LDF provides a query interface based on Triple Pattern Fragments (TPF) [53], an iterative process that converts the clients’ complex SPARQL queries (over HDT datasets) into the union of simple Triple Patterns, returning paginated partial results, and therefore balancing the computational cost between servers and clients. LOD Laundromat is a project that cleans the LOD RDF datasets, removing blank nodes, duplicated triples and syntax errors. After being cleaned, data is published in many syntaxes, including HDT, and can be queried by the TPF APIs. LOD-a-lot exposes an HDT mashup of 28 billion cleaned triples (from LOD Laundromat), queryables by the TPF interface. Challenges. The big boom in the exposure of large datasets on the Web of Data, and the wide acceptance of RDF as the glue that links them, has focused the research of the last few years on the compaction of the serialization of RDF graphs. The fact that HDT was the first RDF binary serializer, along with its simple and intuitive model, has made HDT a great success within the Semantic Web community. Precisely because of its simplicity, HDT (and HDT-FoQ) does not capture the peculiarities of the RDF graph and can therefore be improved by detecting and eliminating additional redundancy in the Triples component. Specifically, RDF collections hoard three types of redundancy [41]: Semantic redundancy occurs when the knowledge described by some triples can be inferred from others. In this case, these triples can be removed, thus reducing the size of the dataset, but preserving the knowledge. Compression in this case is merely related to how information is available within the dataset, so classic compression techniques are not valid to alleviate this type of redundancy. It should be noted that semantic 7https://linkeddatafragments.org/ 8http://lodlaundromat.org/ 10 compression can be lossy, so the decompression process will not necessarily return the original graph (but an equivalent one). Symbolic redundancy is present when there are similarities and repetitions between the URIs and Literals (i.e., symbol repetitions). Symbolic redundancy is mainly due to URIs with long prefixes. This kind of redundancy can be removed by universal compressors (i.e., gzip,bzip2, . . . ), since URI prefixes appear repeatedly throughout the dataset. However, on the contrary, they do not allow access to data without a prior decompression. This type of redundancy can also be mitigated with the use of compressed string dictionaries [35], which are used to encode the RDF terms present in a dataset as integers, making a translation possible between a term and its identifier and vice versa. Finally, syntactic redundancy refers to the existence of structural regularities in the RDF graph. Resources of the same class are usually described by the same predicates; for example, the predicate dbo:motto describes resources such as Universities, but could not be used to describe printers, for instance. Unlike N-Triples, which writes the full terms of each triple (one per line), Turtle syntax is able to minimize this redundancy by serializing the triples, grouping predicate-object pairs related to the same subject (i.e., adjacency lists). As in the case of subject-predicate connections, relationships established between predicates and objects are also restricted to a limited range. Specific graph compressors can treat this sort of redundancy by serializing the graph in compressed adjacency lists or matrix structures. The fact that graph compressors usually work with integers must be taken into account, so a previous step of generating a dictionary is necessary. 1.2. Hypothesis Specific RDF compressors mitigate any of the three redundancies above achieving a size reduction. These compressors are classified into physiscal compressors, if they exploit the syntactic and/or symbolic redundancy; logical compressors, if they act on semantic redundancy; and hybrid compressors, which mix both types. An introduction to the main RDF compressors of the state of the art can be found in Section 2.2. In this thesis, we have addresed a particular RDF problem: the distribution of the predicates of the RDF real-world datasets are such that they introduce overheads in their serializations. This problem brings up two challenges. On the one hand, specific syntactic redundancy should be identified and treated in order to improve the compression that the main state-of-theart techniques currently achieve. On the other hand, new data structure configurations should be proposed to allow SPARQL Triple Pattern queries 11 on compressed data. This feature is currently available in techniques that lead the state of the art. All of the above leads us to raise the main hypothesis of this thesis: “RDF graphs are not randomly structured, on the contrary, they tend to follow organizational patterns resulting in semi-structured datasets. Based on this inherent RDF characteristic, the terms can be organized, grouped and re-encoded so that syntactic redundancy is minimized, improving the existing RDF compression techniques, such as HDT, while maintaining its ability to query in compressed space.” Within a dataset, subjects of the same class are usually described by the same predicates. For example, a person might be described by predicates such as an ID, name, sex, date of birth, etc. However, those predicates do not fit when describing countries, for instance. In our example (see Figure 1.2), the resources :Valladolid and :Palencia are described by the same predicates {dbo:country, dbo:isPartOf, rdf:type}, since both are of the same class (i.e., cities). We call predicate-family (or family) the set of predicates that describe subjects of the same nature, splitting the graph into subgraphs, each one containing all subjects described by the same characteristics. Therefore, the relationships established between subjects and predicates can be replaced by those between subjects and families. A more fine-grained analysis is performed when considering the presence of predicate rdf:type. This predicate is used extensively to categorize the information in the dataset, providing the class of the subject it describes. Therefore, although it is not mandatory, this predicate appears many times throughout the dataset. Type objects (i.e., related to the rdf:type predicate) can be attached to the family to semantically categorize the subjects they are describing. Besides, although RDF allows the connection between any predicate and object, predicates are, in practice, related to a well-defined range of objects. Therefore, objects can be locally identified within the scope of each predicate, using fewer bits to be encoded. The second part of the hypothesis proposes that our new form of serialization can be queried efficiently. In this context, RDF self-indexing provides efficient access to the data without a decompression. As seen before, HDT can generate auto-indexes on the top of its structure to allow and speed up the query of its data. HDT-FoQ (HDT and its self-indexes) manages to efficiently perform searches by subject, but requieres expensive indexes to run predicate and object-based queries. We efficiently guarantee data querying by adding new compact data structures on top of our proposal, which will al12 leviate the main weakness of HDT-FoQ (i.e., predicate-based queries), while preserving the efficiency of the rest. 1.3. Contribution This thesis encompasses several contributions. First of all, a full revision of RDF compression [34], which has been published in the homonymous chapter of the book Encyclopedia of Big Data Technologies [49], where we have also described the sources of redundancy that RDF inherently possesses (see the previous section) and how the different kinds of compressors are able to mitigate them. In this thesis we analyze common patterns related to the use of predicates and objects in RDF real-world datasets, and show how structural sources of redundancy underlying the schema-relaxed nature of RDF can be exploited to improve their effective encoding. Its main contribution is the conception of our proposed RDF graph reorganization technique, called RDF-Tr, which alleviates its structural redundancies and improves HDT (the most used RDF compressor by the community) in terms of compression space and decompression time. However, the use of RDF-Tr is not limited to HDT. In particular, it is applied to another syntactic compressor, k2-triples [1], which performs a more effective ID-graph encoding, organizing the RDF terms like HDT (four partitions), but encoding the triples in |P|binary matrices, which are subsequently compressed using k2-trees [11] (see Section 2.2 for more details). Applying RDF-Tr to k2-triples, as in the case of HDT, achieves improvements in compression size and decompression speed. RDF-Tr groups triples by families of predicates and recodes object IDs within the scope of the predicate in which they act. This results in a new binary representation of the triples, called HDT++, while retaining the original HDT Dictionary component. HDT++, which was presented in the Data Compression Conference (DCC) in 2015 [22] (see Chapter 3), outperforms its original effectiveness up to 2.3 times, accelerating the decompression time up to 3.4 times. The fact that RDF-Tr acts only on the Triples component of HDT, leaving the Dictionary intact, makes it possible to apply the same transformations to some other RDF compressors, as in the case of the aforementioned k2-triples. RDF-Tr, which was published in the journal Information Sciences in 2020 [24] (see Chapter 4), formalizes the DCC proposal, optimizing the configuration of some parameters that allow the improvement of HDT++. In addition, it is also used to improve k2-triples. Once RDF-Tr is applied over k2-triples, a more compact version is obtained, called k2-triples++, sav13 ing up to 2.3 times the space needed by its original version, and increasing the decompression time up to 2.4 times. In addition to compression, one of the strengths that both HDT and k2triples have, as well as RDFCSA [10] (another of the leaders in RDF compression), is that they all allow for the resolution of SPARQL Triple Patterns on the serialized file. Therefore, and despite the great numbers obtained in terms of compression, another contribution is needed for this thesis: A proposal for indexing the reorganized RDF graph for the sake of providing resolution of Triple Patterns. To complete this challenge, iHDT++ (indexed HDT++) extends the concept of HDT++ with the inclusion of proficient self-indexes that alleviate the main weakness of HDT-FoQ (i.e., predicate-based queries). On the one hand, iHDT++ outperforms HDT-FoQ in terms of space complexity by up to ≈45%. On the other hand, regarding the resolution of Triple Patterns, the main achievement is the improvement of two orders of magnitude when solving the query {(?,P,?)}, while {(?,?,?)}is up to one order of magnitude faster in iHDT++, depending on the dataset. For the rest of the Triple Patterns accessed by predicate (i.e., {(S,P,O), (S,P,?)}), iHDT++ is still faster, although the difference is less significant. Accessing by object (i.e., {(S,?,O), (?,P,O), (?,?,O)}) reports similar times as HDT-FoQ, being the access by subject (i.e., (S,?,?)), the only operation that HDT-FoQ solves faster than iHDT++. A preliminary version of iHDT++ was presented at the Jornadas de Ingenier´ıa del Software y Bases de Datos (JISBD) [23] in 2017. Finally, an optimized and definitive version was presented in the International Symposium on Language & Knowledge Engineering (LKE) [25] in 2019, and published in the Journal of Intelligent & Fuzzy Systems [26] in 2020 (see Chapter 5). Finally, all these contributions have been compiled into a tool9, capable of being integrated into the original HDT library, which allows it to perform the reorganization of the triples from an HDT file, transforming it into HDT++. This transformation can also be applied to k2-triples. In addition, iHDT++ self-indexes can be built with this tool to enable Triple Pattern query processing. 1.4. Thesis Structure This thesis is presented as a compendium of publications. Chapter 2 provides the background on which the compendium is based, including the processes of publishing and querying data on the Web of Data, basic compression concepts and a state of the art of RDF compressors. Chapters 3 9https://github.com/antonioillera/iHDTpp-src 14 to 5 gather the three publications that constitute this thesis, each of them corresponding to a particular contribution, which are the following: – Chapter 3: “Serializing RDF in Compressed Space”. [22] In proceedings of the Data Compression Conference (DCC 2015). Conference indexed in GII-GRIN-SCIE (GGS)10 Conference Rating: GGS Class 2. – Chapter 4: “RDF-TR: Exploiting structural redundancies to boost RDF compression”. [24] Journal article published in Information Sciences, indexed in the Journal Citation Reports (JCR) Ranking: Impact factor 5,910. Q1: Computer Science, Information Systems (9/156). – Chapter 5: “iHDT++: Improving HDT for SPARQL Triple Pattern Resolution”. [26] Journal article published in Journal of Intelligent & Fuzzy Systems, indexed in the Journal Citation Reports (JCR) Ranking: Impact factor 1,851. Q3: Computer Science, Artificial Intelligence (79/136). Finally, Chapter 6 presents the Conclusions of the thesis and the open lines of research that are left as future work. 10http://gii-grin-scie-rating.scie.es/ 15 Figure 2.5: SPARQL UNION in DBPedia and DESCRIBE (returns the description of a resource) can be used. Yet, SPARQL not only allows the querying of RDF data, it also supports updating the data, by adding or deleting triples. 2.2. RDF Compression The main objective of RDF compression is to serialize an RDF graph, or a semantic equivalent, using fewer bits than traditional representations. For this purpose, RDF redundancies introduced in Section 1.1 must be detected and treated. RDF specific compressors are classified into the following three types, depending on the redundancy they treat. Physical compressors usually remove symbolic redundancy, transforming the RDF graph into a compressed-dictionary ID graph that replaces the original graph. The most widespread way to perform the dictionary compression, the aforementioned four-section vocabulary (subjects, predicates, objects, and those terms with the subject-object role), is present in many RDF physical compressors, such us HDT [19] or k2-triples [1] (see Figure 1.4). After creating the dictionary, the syntactic redundancy needs to be addressed on the transformed graph of integers. The graph is succintly encoded, for example, as adjacency lists or matrices. HDT, the pioneer of this type of compressors, conceives the graph as a forest of |S|subject-rooted trees, each of them storing the relationships between that particular subject and predicates. The last layer of the tree contains the objects related to the subject-predicate pairs. Later, the forest is encoded with two sequences of integers, the first concatenates the predicate IDs related to the root-subject and the second stores the relationships between objects and the subject-predicate pairs. Two additional sequences of bits mark the ranges of subject-predicate relationships and predicate-object 22 Figure 2.6: HDT BitmapTriples relationships within the scope of each subject. This resulting structure is called BitmapTriples. Figure 2.6 shows the forest of trees representing the ID-graph we had in Figure 1.4, as well as its BitmapTriples encoding. HDT allows subject-based queries to simply traverse the trees starting from the subject roots, hence solving those triple patterns with a bounded subject. In contrast, this encoding needs additional indexes that HDT-FoQ [33] builds on top of it to solve the rest of the Triple Patterns. Specifically, HDT-FoQ replaces the predicate list by a wavelet tree [20] (called WP) to provide indexed predicate-based access: (?, p, ?) and (?, p, o), and uses an additional adjacency list (called O-Index) to store the positions where each object is located within the BitmapTriples sequence of objects, allowing the resolution of (?, ?, o). Both structures are shown in Figure 2.7 along with the BitmapTriples. K2-triples uses the same four-vacabulary dictionary as HDT, but proposes a different way of encoding the graph, building |P|adjacency matrices. A 1-bit in the coordinate (i,j) of the nth matrix means that the triple (i,n,j) is an existing triple within the dataset. The resulting matrices, which are very sparse, are subsequently compressed using k2-trees [11], improving HDTFoQ compression ratios. Figure 2.8 illustrates the resulting k2-tree for the predicate 2 of our example, which encodes all triples for the second predicate. We consider k= 2, hence each level is divided into k2= 4 submatrices. The right hand side of the Figure depicts the conceptual tree and two sequences of bits Tand L, which encode the k2-tree. RDFCSA [10] recodes ID-triples to avoid ID overlappings among subjects, predicates, and objects. This rearrangement ensures that all subject 23 Figure 2.7: HDT-FoQ. IDs are smaller than predicate IDs, and that these are smaller than object IDs, ensuring that ID-triples are ”lexicographically” sorted, respectively, by subject, predicate, and object. RDFCSA exploits the fact that this organization can be effectively encoded using the Compressed Suffix Array (CSA) [48], which also guarantees efficient queries over the compressed representation, competing with k2-triples, at the cost of using more space. BMatrix [12], also based on k2-trees, is specifically designed to work with datasets with a large number of predicates, in this case improving the state-of-the-art RDF compressors. RDF terms are encoded using the fourvacabulary dictionary, and it builds two binary matrices compressed in the end with k2-trees; the first one stores the subjects occurrences (in rows), in triples (in columns), while the other one does the same with the objects. Triples in columns are grouped by predicate, so a last data structure is necessary to mark the positions where the triples change their predicate. Karim et al. [29] propose a technique to detect Frequent Star Patterns across the RDF graph: pairs of predicates-objects that define entities (i.e., subjects) of the same Class. The graph is subsequently factorized, replacing the original triples with RDF molecules (graph patterns that match those Frequent Star patterns), thus decreasing the edges and compacting the graph. This method is more efficient in ontologies, where classes are well defined. RDF compression is also applied in specific domains, as in the case of the provenance data [8], RDF metadata generated when creating or updating content in web documents, such as Wikipedia. In this specific and 24 Figure 2.8: Vertical-Partitioning on k2-triples (k=2) for P2. restricted scenario, the RDF graph follows structural patterns that are exploited, achieving an effective compression in this domain. There are other works, not focused on the compression of the RDF graph itself, but on the optimization of RDF self-indexes used for the resolution of SPARQL Triple Patterns. Pibiri et al. [44] propose 3 three-layer indexes (i.e., permutations), one for the triples ordered in SPO, a second index stores the triples ordered in POS, and the last contains the triples ordered in SOP. Note that the SPO index is actually the HDT BitmapTriples configuration, replacing the bit sequences with pointers. As the set of triples in the dataset is tripled, the nodes can subsequently be recoded with the relative positions of the index where the information is already located, reducing the size of the indexes. Logical compressors address the semantic redundancy, detecting and removing from the RDF graph redundant triples (i.e., those that can be inferred), obtaining the canonical subgraph. The first contributions in this field are based on the notion of lean subgraph [27] [39], the smallest instance (i.e., subgraph) of the original RDF graph. The structure of the graph clearly influences the number of triples removed by the lean subgraph, the threshold being in two triples eliminated per blank node in the graph [27]. However, the subgraph obtained does not ensure that it is the canonical graph, so there may be triples that could be inferred and therefore redundant [39]. The rule-based (RB) technique [28] mines the graph, looking for patterns of relationship between RDF terms (intra-property and inter-property patterns), which are subsequently used to create rules and eliminate inferable triples. However, the compression obtained when applying RB is not very important, and the authors ultimately compress the datasets with HDT in order to be competitive with the rest of the RDF compressors. Effectiveness 25 in this kind of compression can be improved by using more expressive rules, as frequent patterns do not catch all the semantic associations. Horn rules can be detected by exploring the dataset [52] and then used to delete triples that match with the Head of a Horn rule, while the remaining triples are compressed with the RB method. Hybrid compressors encompass logical and physical techniques, so that the three types of redundancies can be tackled. Although they combine the best of both compression methods, in practice, it is a field that has been little explored. The graph pattern-based (GPB) compressor [40] groups the triples that share the same subject in Entitiy Description Blocks (EDB). Each EDB is described by an Entity Description Patterns (EDP), which is a concept similar to predicate families. Each EDP is encoded as a pair containing an EDP and instances that match it, constituting the simplest level of de GPB (LV0); then better patterns are acquired (LV1) by merging the EDBs. The last level in GPB (LV2) recursively joins the merged EDBs. Experiments show that, at the logical level, GPB (LV2) removes more triples (i.e., compresses more) than RB; however, its effectiveness has not been compared to physical compressors. Finally, RDF2NormRDF [51] is not a compressor per se, but an attempt to normalize the RDF graph. It deals with blank node particularities and cleans duplicated RDF terms from the graph by applying several transformations rules. At the physical level, RDF2NormRDF applies another set of rules to normalize types and certain tags, such as language. Experiments show that RDF2NormRDF only outperforms HDT when dealing with small datasets. 26 Chapter 3 Serializing RDF in Compressed Space 27 Serializing RDF in Compressed Space∗ Antonio Hern´andez-Illera∗,MiguelA.Mart´ınez-Prieto∗, and Javier D. Fern´andez† ∗DataWeb Research †Institute for Information Business Department of Computer Science Vienna University of Economics and Universidad de Valladolid, Spain Business (WU), Austria [email protected], [email protected], [email protected] Abstract The amount of generated RDF data has grown impressively over the last decade, promoting compression as an essential tool for storage and exchange. RDF compression techniques leverage syntactic and semantic redundancies, but structural repetitions are not always addressed effectively. This paper first shows two schema-based sources of redundancy underlying to the schema-relaxed nature of RDF. Then, we revisit the W3C HDT binary format to further compact its graph structure encoding. Our HDT++ approach reduces the original HDT Triples requirements up to 2 times for more structured datasets, and reports significant improvements even for highly semi-structured datasets like DBpedia. In general, HDT++ competes with the current state of the art for structural RDF compression, leading the comparison for three of the four analyzed datasets. 1 Introduction The Resource Description Framework (RDF) [9] is a conceptual model which describes data in the form of triples. Each triple comprises the resource being described (referred to as subject), a property of that resource (predicate), and the corresponding value (object). Each triple can be seen as a simple graph in which the predicate labels the edge from the subject to the object node. Thus, an RDF dataset is a labeled directed graph linking subject descriptions in the form of triples. This flexible paradigm has seen a massive growth in interest over the past few years. RDF has been adopted in many and varied fields of knowledge and leading projects1: life-sciences (e.g. Uniprot), geography (e.g. Geonames), open-government (e.g. US data.gov), etc. Not surprisingly, DBpedia, an RDF conversion of Wikipedia, is the biggest crossdomain dataset and the most accepted reference to assess the benefits of RDF. Despite it is being widely used, the RDF framework does not restrict how data are serialized. Recently, the RDF Working Group of the World Wide Web Consortium (W3C) collected several practical RDF serialization formats2. Although the original RDF/XML is still considered, Turtle-based languages are promoted over it. In any case, these formats are dominated by a document-centric and a human-readable view of RDF, adding unnecessary overheads to the final dataset representation [5]. Thus, the resulting RDF files take up much space, wasting storage and bandwidth resources. ∗Research funded by Ministerio de Econom´ıa y Competitividad, Spain: TIN2013-46238-C4-3-R, and Austrian Science Fund (FWF): M1720-G11. 1Uniprot: http://www.uniprot.org/;Geonames: http://www.geonames.org/; US data-gov: https://www.data.gov/; DBpedia: http://www.dbpedia.org/ 2See the recent new version of the RDF primer, http://www.w3.org/TR/rdf11-primer/ 2015 Data Compression Conference 1068-0314/15 $31.00 © 2015 IEEE DOI 10.1109/DCC.2015.16 363 Even when considering JSON-LD, a serialization which leverages JSON features for compaction (and also makes easy data parsing), the syntax requires great amounts of bytes for effective serialization, so storage and exchange remains inefficient. HDT [6] is another RDF syntax within the W3C scope3but, in contrast to the previous “plain” serializations, it proposes a binary format. HDT encodes RDF into two main data components: the Dictionary, providing a mapping between textual terms and numerical identifiers (IDs), and the Triples, which encodes the graph structure of IDs, avoiding management of nodes and edges with long strings. HDT outputs very compact RDF serializations [4], enabling meaningful savings in storage and also speeding up exchange processes. However, its graph structure encoding (the Triples component) is quite straightforward, and it is not able to leverage particular sources of redundancy underlying to RDF. This paper revisits HDT to improve its Triples encoding. The new approach: HDT++, reduces up to 2 times the original Triples space, while outperforms the most prominent RDF compressor: k2-triples [1] by 10 −13%. The rest of the paper is organized as follows. Section 2 delves into the low-level details of HDT and also summarizes the current state of the art for RDF compression. Section 3 shows how some structural RDF features are potential sources of redundancy, and Section 4 explains how our current approach exploits them within HDT foundations. Section 5 compares the current approach with respect to the original HDT, and the aforementioned k2-triples. Finally, Section 6 concludes about our current work and devises future research leveraging the reported advances. 2 Background HDT [6] is a binary serialization format optimized for RDF storage and transmission over a network. It encodes RDF data into three components (Header,Dictionary,and Triples) carefully described to address some RDF peculiarities, but also considering how these data are used in the common Publication-Exchange-Consumption workflow. The Header is a metadata component that describes relevant information for discovering, parsing and consumption purposes. It uses few kilobytes, so it is free of scalability issues. Then, the RDF graph is represented on the basis of two data components: the Dictionary maps all different terms in the dataset to unique identifiers (IDs), and enables the Triples component to encode the inner RDF structure as a compact graph of IDs. Efficient encoding of string dictionaries is a challenge beyond RDF compression [2], so the dictionary representation is orthogonal to the problem addressed in this paper. Nevertheless, note that the HDT Dictionary component has already been encoded using effective compressed RDF dictionaries [4, 11]. The Triples component encodes RDF triples as groups of three IDs: (idsidpido), where ids,idp,andidoare respectively the IDs of the corresponding subject, predicate, and object terms in the Dictionary. The current Triples component organizes all these triples into a forest of trees, one per different subject in the dataset (see Figure 1). These trees are ordered by subject ID, i.e. the ith tree organizes all triples rooted by the ith subject in the Dictionary. Each tree has three levels: the root encodes the subject; the second level encodes all predicates related to the subject (predicate 3HDT was acknowledged as Member Submission,http://www.w3.org/Submission/HDT/ 364 Figure 1: Forest of trees modeling ID triples in HDT. Figure 2: Configuration of binary streams used for encoding the Triples component. IDs are listed in increasing order); and, the leaves encode the adjacency lists of all objects related to each (subject, predicate) pair, also listed in increasing order of object IDs. Note that if a subject is related to jdifferent predicates, its tree encodes jdifferent object lists. This forest organization is succinctly serialized using four binary streams. On the one hand, two sequences:Sp and So, which concatenate predicate and object IDs respectively, following the tree orderings. Given an RDF dataset that comprises |P|different predicates and |O|different objects, the encoded IDs in Sp and So take log |P|and log |O|bits per element respectively. On the other hand, two bitsequences:Bp and Bo, which are aligned with Sp and So respectively, in the following way. When Sp[a] stores the last predicate ID of an adjacency list, then Bp[a]=1,being0otherwise. In other words, the list of predicates related to the kth subject ends in the kth 1-bit in the Bp bitsequence and starts after the k−1th 1-bit. This reasoning also applies for object encoding in Bo and So. Figure 2 shows the structures which encode the previous example. For instance, the 4th predicate list is encoded from Sp[12] to Sp[14]:{1,2,4}, because Bp[14] stores the 4th 1-bit and Bp[12] stores the next 0-bit after the 3rd 1-bit. State of the Art of RDF Compression Following the categorization in [13], HDT can be considered as a syntactic compressor because it detects redundancy at serialization level. On the one hand, the Dictionary reduces symbolic redundancy from the terms used in the dataset. On the other hand, the Triples component leverages structural redundancy from the graph topology. This kind of redundancy is also detected in k2-triples [1]. This approach performs a predicate-based partition of the dataset into disjoint subsets of (subject, object) pairs. These subsets are highly compressed as (sparse) binary matrices that also allow efficient data retrieval. Other approaches, like HDT-FoQ [10] or WaterFowl [3] also enable data retrieval in compressed space. Both techniques, based on HDT serialization, report competitive performance at the price of using more space than k2-triples, which is the most effective compressor, to the best of our knowledge. RDF compression may also leverage semantic redundancy. These logical compressors [8] discard triples which can be inferred from others, and they only encode these “primitive triples”. Thus, these techniques save space because they reduce the number of triples to be encoded. In addition, they may also apply syntactic com365 provide efficient rank/select resolution [7]. This straightforward deployment allows HDT++ files to be loaded in roughly the same space used for disk storage (even the space is slightly reduced for dbtune), and triples decoding is faster than the original HDT. For instance, HDT++ decodes dbtune in 2.8 seconds, and HDT needs 4.46 seconds. 6 Conclusions and Future Work This paper revisits the W3C HDT serialization of RDF datasets, improving the compressibility of its graph structure encoding. In spite of the theoretical schema-relaxed nature of RDF, we practically show the presence of two types of schema-based redundancies underlying to RDF: predicate families are massively repeated for general and typed subjects, and objects are often related to just one predicate. Our HDT++ approach leverages these features, saving up to half the space used by its HDT predecessor and competing on equal terms with the most effective RDF compressor, k2-triples. Our achievements can be directly reused by the community since all decisions are aligned to the HDT foundations. Thus, solutions exchanging/consuming HDT can greatly reduce their storage requirements and network latencies. Our future work focuses on exploiting this approach to provide triple pattern resolution by reusing previous experiences on HDT-based retrieval [10]. 7 References [1] S. ´ Alvarez-Garc´ıa, N. Brisaboa, J.D. Fern´andez, M.A. Mart´ınez-Prieto, and G. Navarro. Compressed Vertical Partitioning for Efficient RDF Management. Knowl. Inf. Syst., 2014. DOI: 10.1007/s10115-014-0770-y. [2] N. Brisaboa, R. C´anovas, F. Claude, M.A. Mart´ınez-Prieto, and G. Navarro. Compressed String Dictionaries. In Proc.ofSEA, pages 136–147, 2011. [3] O. Cur´e, G. Blin, D. Revuz, and D.C. Faye. WaterFowl: A Compact, Self-indexed and Inference-Enabled Immutable RDF Store. In Proc. of ESWC, pages 302–316, 2014. [4] J.D. Fern´andez. Binary RDF for Scalable Publishing, Exchanging and Consumption in the Web of Data. PhD thesis, University of Valladolid, Spain, 2014. [5] J.D. Fern´andez, M. Arias, M.A. Mart´ınez-Prieto, and C. Guti´errez. Management of Big Semantic Data. In Big Data Computing, chapter 4. Taylor and Francis/CRC, 2013. [6] J.D. Fern´andez, M.A. Mart´ınez-Prieto, C. Guti´errez, A. Polleres, and M. Arias. Binary RDF Representation for Publication and Exchange. J. Web Semant., 19:22–41, 2013. [7] R. Gonz´alez, S. Grabowski, V. M¨akinen, and G. Navarro. Practical implementation of rank and select queries. In Proc.ofWEA, pages 27–38, 2005. [8] A. Joshi, P. Hitzler, and G. Dong. Logical Linked Data Compression. In Proc. of ESWC, pages 170–184, 2013. [9] F. Manola and R. Miller. RDF Primer. W3C Recomm., 2004. www.w3.org/TR/rdf-primer/. [10] M.A. Mart´ınez-Prieto, M. Arias, and J.D. Fern´andez. Exchange and Consumption of Huge RDF Data. In Proc.ofESWC, pages 437–452, 2012. [11] M.A. Mart´ınez-Prieto, J.D. Fern´andez, and R. C´anovas. Querying RDF dictionaries in compressed space. SIGAPP Appl. Comput. Rev., 12(2):64–77, 2012. [12] D. Okanohara and K. Sadakane. Practical Entropy-Compressed Rank/Select Dictionary. In Proc. of ALENEX, pages 60–70, 2007. [13] J.Z. Pan, J.M. G´omez-P´erez, Y. Ren, H. Wu, and M. Zhu. SSP: Compressing RDF data by Summarisation, Serialisation and Predictive Encoding. Technical report, 2014. Available at http://www.kdrive-project.eu/wp-content/uploads/2014/06/WP3-TR2-2014 SSP.pdf. 372 Chapter 4 RDF-TR: Exploiting structural redundancies to boost RDF compression 39 RDF-TR: Exploiting Structural Redundancies to boost RDF CompressionI Antonio Hern´andez-Illera∗,a, Miguel A. Mart´ınez-Prietoa, Javier D. Fern´andezb,c aDepartment of Computer Science, University of Valladolid, Spain. bVienna University of Economics and Business, Austria cComplexity Science Hub Vienna, Vienna, Austria Abstract The number and volume of semantic data have grown impressively over the last decade, promoting compression as an essential tool for RDF preservation, sharing and management. In contrast to universal compressors, RDF compression techniques are able to detect and exploit specific forms of redundancy in RDF data. Thus, state-of-the-art RDF compressors excel at exploiting syntactic and semantic redundancies, i.e., repetitions in the serialization format and information that can be inferred implicitly. However, little attention has been paid to the existence of structural patterns within the RDF dataset; i.e. structural redundancy. In this paper, we analyze structural regularities in real-world datasets, and show three schemabased sources of redundancies that underpin the schema-relaxed nature of RDF. Then, we propose RDF-Tr (RDF Triples Reorganizer), a preprocessing technique that discovers and removes this kind of redundancy before the RDF dataset is effectively compressed. In particular, RDF-Tr groups subjects that are described by the same predicates, and locally re-codes the objects related to these predicates. Finally, we integrate RDF-Tr with two RDF compressors, HDT and k2-triples. Our experiments show that using RDF-Tr with these compressors improves by up to 2.3 times their original effectiveness, outperforming the most prominent state-of-the-art techniques. Keywords: RDF compression, Linked Data 1. Introduction The Resource Description Framework (RDF) [29] is a logical model which describes data in the form of triples. Each triple comprises the resource being described (referred to as subject), a property of that resource (predicate), and the corresponding value (object). For instance, the triple (<http://example.org/Dead Man Walking>,<http://example.org/prop/title>,"Dead Man Walking") sets that the resource <http://example.org/ Dead Man Walking> has a title property with the value "Dead Man Walking". An RDF triple can be seen as a directed graph in which the predicate labels the edge from the subject to the object node. Thus, an RDF dataset (a set of triples) is often represented as a labelled directed graph that links data descriptions in the form of triples. Figure 1 shows a simple RDF graph with four triples that provide a basic description of Sean Penn and one of his films, “Dead Man Walking”. Note that RDF restricts the types of terms that can play as subject, predicate, or object. Subject roles are always played by International Resource Identifiers (IRIs) or local identifiers (referred to as blank nodes) used to denote resources without explicitly naming them. Predicates are always IRIs (often described in a vocabulary or ontology), whereas the object role can be played by both IRIs, blank nodes and also literal values (such as "Dead Man Walking" in Figure 1). This flexible paradigm has attracted increasingly interest over the past few years. RDF has been adopted as the mainstream data representation in diverse fields of knowledge and leading projects1such IA preliminary version of this paper appeared in Proc. Data Compression Conference (DCC), pages 363–372, 2015. ∗Corresponding author: Departamento de Inform´atica, Escuela de Ingenier´ıa Inform´atica, Campus Miguel Delibes, Paseo de Bel´en 15, Valladolid, Spain. Email addresses: [email protected] (Antonio Hern´andez-Illera), [email protected] (Miguel A. Mart´ınez-Prieto), [email protected] (Javier D. Fern´andez) 1Bio2RDF: http://bio2rdf.org/; Geonames: http://www.geonames.org/; Wikidata: https://www.wikidata.org; DBpedia: http://www.dbpedia.org/ Preprint published in Information Sciences 508 (2020): 234-259 http://example.org/Sean_Penn “Sean Penn” http://example.org/prop/name http://example.org/Dead_Man_Walking http://example.org/prop/title http://example.org/class/film http://www.w3.org/1999/02/22-rdf-syntax-ns#type http://example.org/prop/starring “Dead Man Walking” Figure 1: RDF triples modelled as a labelled directed graph. NTriples <http://example.org/Dead_Man_Walking> <http://example.org/prop/title> "Dead Man Walking". <http://example.org/Sean_Penn> <http://example.org/prop/name> "Sean Penn". <http://example.org/Dead_Man_Walking> <http://example.org/prop/starring> <http://example.org/Sean_Penn>. <http://example.org/Dead_Man_Walking> <http://www.w3.org/1999/02/22-rdf-syntax-ns#type> <http://example.org/class/film>. Turtle @prefix ex: <http://example.org/> . @prefix prop: <http://example.org/prop/> . @prefix class: <http://example.org/class/> . ex:Dead_Man_Walking prop:title "Dead Man Walking" ; prop:starring ex:Sean_Penn ; a class:film . ex:Sean_Penn prop:name "Sean Penn" . Figure 2: RDF triples presented in NTriples and Turtle formats. as life-sciences (e.g. Bio2RDF), geography (e.g. Geonames), or general knowledge (e.g. Wikidata), to name but a few. Not surprisingly, DBpedia, an RDF conversion of Wikipedia, is the largest cross-domain dataset2and the most accepted reference to assess the benefits of RDF. In fact, DBpedia is considered the nucleus for the so-called Web of Data [3], an interconnected data-to-data cloud that grows progressively encouraged by the Linked Open Data (LOD) initiative3. Despite its success, the RDF framework is a logical model, hence it does not restrict how data are (phisically) serialized. The RDF Working Group of the World Wide Web Consortium (W3C) focuses on this issue and collects several practical RDF serialization formats [45]. Serializations have evolved from the initial verbose RDF/XML specification, to more specific, simple and compact formats, such as JSONLD, Turtle, NTriples, or NQuads. All these “plain” formats lead to document-centric, human-readable serializations of RDF, which add unnecessary overheads when storing, exchanging and consuming RDF graphs in the context of a large-scale and machine-understandable Web of Data. Figure 2 shows the RDF representation of the previous example in two different formats, Ntriples and Turtle. These forms of representation are equivalent and they suffer from similar verbosity and redundancy problems, as they are both intended for human readability. Although Turtle mitigates redundancy by grouping prefixes (with the inclusion of "@prefix" terms) and using some sort of adjacency lists, arbitrary long IRIs, e.g. ex:Mystic River are still present in several triples, acting as subject and object in different triples (the sources of RDF redundancies are reviewed in Section 2). Thus, RDF-specific compression has recently emerged as an effective technique to detect and leverage internal redundancies in RDF data, minimizing space requirements for storage, exchange and consumption processes [30]. In addition, RDF compression plays an increasingly important role in other application areas, such as RDF archiving and versioning [47] or distributed RDF stores [22], among others. In this scenario, HDT [17], also within the W3C scope [16], represents one of the first and more standardized binary formats for RDF data. The HDT format results in a very compact RDF serialization, enabling significant savings in storage and speeding up data exchange (i.e., less bits over the wire). HDT minimizes the repetition of potentially large strings using the so-called HDT Dictionary, which assigns a numerical ID to each term in the dataset. Then, the graph structure of the dataset is managed as a graph of term IDs, in the HDT Triples component. While efficient encoding of string dictionaries is a challenge beyond RDF compression [32], triples encoding is an open and active research area. In 2The latest DBpedia version comprises more than 13 billion triples from 128 different languages. 3http://linkeddata.org/ 2 particular, HDT uses a straightforward configuration and encodes the triples as a forest of trees, one per different subject, using bit and (compact) integer sequences. In turn, the k2-triples [1] technique elaborates on the encoding of the triples and reports excellent compression ratios by representing triples as a set of (compressed) adjacency matrices, one per different predicate. These compressors, though, disregard specific sources of structural redundancies underlying RDF, i.e., common patterns emerging while describing a subject. Note that, although RDF is a flexible, schema-relaxed model, data represented in RDF come with different levels of structuredness [12], from structured data (e.g. converted from a relational database) to unstructured data (e.g. from Wikipedia). In this paper, we analyze common patterns related to the use of predicates and objects in real-world RDF datasets, and show three structural sources of redundancy (introduced in Section 4) underlying the schema-relaxed nature of RDF. This knowledge is then used to describe and implement a new preprocessor: RDF-Tr (RDF Triples Reorganizer), which reorganizes triples to improve their effective encoding. Then, we practically show the application of the technique for the aforementioned HDT and k2-triples compressors, renamed HDT++ and k2-triples++ respectively. Our evaluation using real-world RDF datasets shows that the improved compressors outperform their original effectiveness up to 2.3 times, and speed up decompression time up to 3.4 times in HDT and 2.4 times in the case of k2-triples. The rest of the paper is organized as follows. Section 2 describes the three different sources of redundancy underlying RDF datasets and summarizes the current state of the art for RDF compression. Section 3 provides background on data compression and compact data structures. Section 4 presents the concrete foundations and sources of redundancy addressed by RDF-Tr. The RDF-Tr reorganization algorithm is fully detailed in Section 5, together with the configuration of compact data structures required to implement it and how the original triples can be decoded. Sections 6 and 7 illustrate the integration of RDF-Tr with existing RDF compressors. In particular, we introduce HDT++ and k2-triples++, the variants of HDT and k2-triples that compress the “reorganized triples” . Section 8 conducts an exhaustive empirical evaluation of RDF-Tr with different real-world datasets, comparing HDT++ and k2-triples++ to their original counterparts. Finally, Section 9 concludes and devises future lines of research. 2. Preliminaries and State of the Art The adoption of RDF as the main model to represent information in the Web of Data, and the development of ambitious projects such as Linked Open Data, has fostered its use in emerging areas such as Knowledge Graphs [7], Smart Cities or the Web Of Things, and critical sectors such as healthcare and biomedecine [25]. For instance, Bio2RDF consists of around 11 billion triples generated from 35 important biomedical data sources, such as DrugBank, PharmGKB and KEGG. Such ever-increasing dataset sizes present scalability challenges [14] and require efficient mechanisms to represent and consume RDF data. In this context, RDF compression has emerged as an active research and development field over the past years [30]. Although universal compressors (e.g., gzip,bzip2, etc) leverage highly verbose RDF serializations, their effectiveness is far from optimal. In general, universal compressors are not able to detect and exploit all types of redundancy underlying RDF data. We first review these sources of redundancy and then analyze state-of-the-art RDF compressors. 2.1. Sources of RDF redundancies RDF redundancies are categorized at the semantic,symbolic and syntactic level [40]. An RDF graph has semantic redundancy when the information it contains can be represented with fewer triples. Semantic compressors are able to detect this type of redundancy and eliminate extra triples from the original dataset [21]. Then, using inference techniques, the original dataset can be recreated, or at least, a semantically equivalent graph can be obtained. Pure semantic compressors are not so effective by themselves, hence they are often combined with symbolic and/or syntactic compressors. Symbolic compression involves removing unnecessary repetitions of symbols in a dataset. This is achieved by encoding each element of the RDF graph (URIs, blank nodes and literals) with a corresponding integer identifier (ID), whose value is stored in a dictionary. In turn, these dictionaries provide at least two primitive operations to translate RDF terms to IDs, and vice versa. Note that RDF dictionaries reach non-negligible sizes and, in practice, they must also be compressed [33]. A survey on compressed string dictionaries [32] shows that URI dictionaries can be highly compressed (up to 5% of 3 their original size), while literal dictionaries need more space due to their more heterogeneous composition. In both cases, translation queries can be resolved efficiently (e.g., in 1 −2µs per operation in a standard setup [32]). Syntactic redundancy depends on the RDF graph serialization and also on the underlying graph structure. The simplest RDF syntaxes, such as NTriples [5], write all triples to serialize this subgraph, e.g., one per line. That is, the same subject value would be repeated ntimes in the resulting file. This drawback can be addressed by simply grouping triples by subject, i.e., considering that the subject structure is described as an adjacency list of (predicate,object) pairs. RDF syntaxes, such as Turtle [6], make similar decisions to obtain more compact serializations. RDF compression at this level is traditionally achieved by serializations that firstly reorganize the structure of the graph in order to leverage such redundancies. In addition, serializations can use compact data structures (a brief background is provided in Section 3) to achieve higher levels of compression [30]. 2.2. RDF Compression The current state of the art comprises a rich and diverse set of compressors for RDF data. These are mainly lossless compressors (because they preserve the original information in the dataset), yet lossy compressors are also emerging [24]. We focus on the former and classify them into physical and logical compressors if they mainly focus on symbolic/syntactic or semantic redundancy respectively. Techniques performing at both physical and logical levels are referred to as hybrid compressors. Physical compressors. These techniques adapt traditional concepts from data compression to the particular case of RDF . On the one hand, they capture and remove symbolic redundancy from RDF terms by using compressed string dictionaries [32]. As explained above, this decision enables the original RDF graph to be processed as an ID-graph, in which IDs refer to the corresponding terms in the dictionary. On the other hand, different graph encodings have been proposed to compress the resulting ID-graph. Although this approach is widely implemented, there are some physical compressors which tune it from different perspectives. HDT [17] pioneers this family of RDF compressors and proposes a simple but effective encoding using three main components: i) the Header provides descriptive metadata about the dataset; ii) the Dictionary maps RDF terms to IDs; and iii) the Triples component encodes the underlying graph. The Header is used for dataset discovery and processing, but it is not relevant for compression purposes. We focus on the other two components: •The Dictionary processes RDF terms according to the role they play in the dataset (subjects, predicates, or objects), but organizes them into four disjoint partitions: one for each role, and a fourth one comprising terms which play both subject and object roles. This organization was originally introduced in [2] and allows subject-object terms to be encoded only once. It is a relevant improvement if one considers that, in real-world datasets, up to 60% of the terms are in fact subject-object terms [33]. Let us refer to |SO|,|S|,|O|, and |P|as the number of different subjects-objects, total subjects, total objects, and total predicates in the dataset, respectively. Then, term-ID mappings are performed as follows: [1,|SO|] for subjects-objects, [|SO|+ 1,|S|] for exclusive subjects, [|SO|+ 1,|O|] for exclusive objects, and |P|for predicates. Each dictionary partition is encoded (by default) using the prefix-based Front-Coding compression [32], which ensures very efficient dictionary operations and excellent compression ratios for IRIs. In contrast, this differential encoding is not so effective for literals, hence HDT also provides a self-indexed dictionary for literals [33], which saves space storage at the price of less efficient retrieval operations. Both types of dictionaries can be parameterized to optimize space/time tradeoffs. •The Triples component encodes the resulting ID-graph as a set of |S|adjacency lists, one per different subject in the dataset. Each list is modelled as a 3-level tree where the corresponding subject is represented at the root; the middle level sorts all predicate IDs related to the subject; while the leaves organize all object IDs related to each (subject, predicate) pair. These trees are encoded using two integer sequences for predicates and objects (subjects are represented implicitly) and two additional bitsequences to represent the shape of the trees. More details about the HDT Triples component can be found in Section 6.1. HDT has been widely adopted by the Semantic Web community because of its simplicity, its compression levels and its performance for data retrieval operations. It is worth noting that HDT is successfully 4 deployed in client-side query processors, such as Triple Pattern Fragments4[50] and SAGE5[35], indexing/reasoning systems like HDT-FoQ [31] or WaterFowl [11], or recommender systems [19] among others. However, its encoding of the graph topology is quite simple and further compression could be achieved. This is addressed by k2-triples [1], a compressor that organizes RDF terms in the same four partitions used by HDT, but performs a more effective ID-graph encoding. In particular, k2-triples implements a predicate-based partitioning of the ID-graph and obtains |P|unlabelled graphs. Each of these predicategraphs is independently encoded as a binary matrix Mp, where Mp[i, j] = 1 means that the subject i and the object jare related by the predicate p, and 0 otherwise. These adjacency matrices, which tend to be sparse, are compressed using the (universal) k2-trees technique [9], reporting the best compression ratios in the current state of the art of RDF compressors. More details about k2-triples are provided in Section 7.1. Two other physical compressors have been published more recently, RDFCSA [8] and OFR [46]. Their contribution is quite different. On the one hand, RDFCSA excels in data retrieval at the cost of larger space requirements, hence it does not outperform the best RDF compressors in the state of the art. RDFCSA first performs the same dictionary transformation explained above. Then, it uses Sadakane’s CSA (Compressed Suffix Array) [42] to encode the ID-graph. In comparison to those RDF compressors providing efficient triple retrieval, RDFCSA competes with HDT in effectiveness, but it does not reach compression ratios reported by k2-triples. On the other hand, OFR is a two-stage compressor that mainly focuses on reducing storage requirements, disregarding triples retrieval needs. In the first stage, OFR also isolates terms and triples. Terms are organized into a structure of six sub-dictionaries, first performing partitions by subject, predicate, and object, and then building dictionaries for each different class of term inside them. These dictionaries are run-length and delta compressed [43]. Regarding triples, they are sorted by (object,subject) value and also run-length and delta encoding to exploit multiple object occurrences and the non-decreasing order of the consecutive subjects. Dictionary and triples outputs are then re-compressed during the second stage. The authors consider two universal compressors (zip and 7zip) to remove all remaining redundancy after OFR reorganization. Compression ratios reported by OFR, combined with zip and 7zip, outperform that achieved by HDT+zip and HDT+7zip. Despite of this achievement, these numbers are not enough to compare whether a standalone OFR (with no universal compression afterwards) improves HDT, or the techniques previously explained. Finally, gRePair [28] extends the RePair algorithm to cater for graphs, including RDF graphs. In short, gRePair builds a grammar with the relationships in the graph and replaces the original graph by another with the rules of the corresponding grammar. gRePair is effective in very specific scenarios, i.e., when the graph has very few predicates and where there is a large number of repetitions in subjectpredicate or object-predicate relationships. In addition, gRePair has not been compared with specific RDF compressors, but with the interleaved k2-tree method, which is comparable to k2-triples. In such scenarios, gRePair obtains the best compression, up to 10 times w.r.t the k2-tree, in a graph with a single rdf:type predicate. In contrast, when the number of predicates increases, the advantage over the k2-tree decreases, and no evaluation is provided with large and complete real-world datasets. Logical compressors. These compressors propose different strategies to detect redundant triples (those that could be inferred) and to obtain the canonical subgraphs, which are finally encoded. Initial approaches [21, 34] consider the notion of lean subgraph. This concept refers to the smallest instance of the original graph which preserves the ground part of the graph (non-blank nodes and edges connecting them), and maps redundant blank nodes to labels already existing in the graph or to other blank nodes. Ianone et al. [21] conclude that the number of triples removed by a lean subgraph greatly depends on the graph features, but a reasonable lower limit is two triples removed] per blank node. Meier [34] states that semantic redundancy is still possible in lean graphs because some of their triples can be derived from others. The author introduces a user-specific redundancy elimination technique based on Datalog-like rules. In short, this approach understands rules in a generative way; i.e., r(X, Y )→t(Y, X) means that t(Y, X) are generated from r(X, Y ). Thus, if r(a, b) exists in the dataset, it is not necessary to store t(b, a), because it can be inferred. Despite its theoretical contribution, this technique is only well-suited when user-defined rules are explicitly specified. The work of Pichler et al. [41] goes a step further and studies how rules, constraints, and queries influence graph minimization. Although it provides a relevant complexity analysis, it does not report any practical results. In fact, Joshi et al. [23] note that 4http://linkeddatafragments.org/ 5http://sage.univ-nantes.fr/ 5 this approach is application dependent, hindering their adoption for compressing the ever growing RDF datasets. The rule-based (RB) compression method [23] is one of the first approaches reporting effectiveness numbers. It uses mining techniques to detect two types of frequent patterns which are then used as generative rules to remove all triples that can be inferred from such patterns. On the one hand, intraproperty patterns encompass groups of objects which are commonly used for subject description through a particular predicate. On the other hand, inter-property patterns group pairs of predicate-object values related to many subjects. Once the patterns are discovered, RB splits the dataset into two disjoint sets of triples: i) the dormant set preserves (in an uncompressed way) those triples to which no inference rule can be applied, and ii) the active set differentially encodes all triples to which rules are applied for inferring new triples. While intra-property patterns are not so effective, inter-property allows up to 50% of the original triples to be removed. However, it has no a significant effect on compression ratios by itself, and RB must be combined with HDT to compete with physical compressors. The use of frequent patterns does not capture all semantic associations in the dataset [49], so effectiveness can be improved if more expressive rules are considered. The technique proposed in [49] introduces a mining algorithm focused on Horn rules. A Horn rule can be simply expressed as B⇒H, where B=B1∧B2∧. . . Bnis the body and His the head. Both Biand Hare of the form (?s pred ?o), where pred is any predicate relating a subject and an object (which can be bounded or left as variables). An instantiation of the rule is considered invalid when a set of triples matches the body rule, but the expected heading triple does not exist in the dataset. On the contrary, a valid instantiation occurs when the corresponding heading triple is in the dataset. Once these Horn Rules are detected, all triples matching the head parts are discarded and the remaining triples are encoded by following the RB strategy. In this case, the active set contains all triples used in the body rules, and the dormant set comprises triples which do not match any rule. It is worth noting that the latter set also contains conflicting triples. That is, triples that are part of an invalid instantiation of a rule and a valid instantiation of another rule. This Horn rule-based compressor outperforms RB in compression ratio at the price of less efficient compression/decompression processes. More recently, Guang et al. [18] proposed a new rule-based compressor that uses OWL2RL rules [36] to remove redundant triples. First, it analyzes subject-object entities to discover common subgraph patterns. These entity description patterns (EDPs) are quite similar to the predicate families that we previously proposed in our seminal paper [20] (further detailed in Section 5). That is, for a given entity e, the corresponding EDP comprises i) all predicates pisuch that (e,pi,ox)exists in the dataset, and (optionally) ii) the class value vif the triple (e,rdf:type,v) is also present. Additionally, an EDP contains all predicates pjsuch that (sx,pj,e). The original dataset can be transformed into a set of EDPs by grouping entities which are described by the same EDP. Each group is then independently processed and OWL2RL rules are matched with piand pjpredicates in the EDP. An EDPRule is added when the EDP satisfies a particular rule, and its inferred triples are removed. Finally, the remaining sx and oxvalues are also encoded in the context of their EDP. The authors do not provide compression ratios, but report that their approach detects up to 32.77% of redundant triples. In quantitative terms, this result does not improve the previous compressors. Hybrid compressors. These compressors combine the best of both worlds. On the one hand, they detect and remove syntactic/symbolic redundancy at the serialization level. On the other hand, they consider different strategies to compact the graph by deleting semantic redundancy at the logical level. Although this form of compressors has barely been researched until now, interesting insights are provided in [39, 48]. The graph-pattern based (GPB) compressor [39] was published concurrently with our seminal paper [20], and has some common points with our current approach, as explained in the following sections. GPB converts the original dataset into a sequence of entity description blocks (EDBs), which group all triples that share the same subject. Each EDB is described by the set of predicates related to the subject and all types assigned to them. EDBs are then grouped into entity description patterns (EDPs) which comprise all EDBs with the same description. The current notion of EDP is similar to that explained above. That is, an EDP is a subgraph pattern that describes the structure of predicates and type values for a subset of subjects in the dataset. Each EDP is encoded as a pair which comprises the corresponding pattern and all instances matching them6. This serialization is called Level 0 method (LV0). GPB introduces a 6Instances are encoded as IDs based on their MD5 hashes. 6 merge operator that joins EDBs by their relations. This strategy is referred to as the Level 1 method (LV1). Finally, the Level 2 method (LV2) recursively joins EDBs merged in previous stages. Experimental results show that GPB-LV2 is able to detect and remove many more triples than RB, reporting better compression ratios. It is clear evidence that GPB performs better at the logical level. Regarding its effectiveness at the physical level, the paper does not compare GPB results to those achieved by other compressors. However, the authors emphasize the potential improvements of GPB due to its ability to remove syntactic redundancy. Finally, RDF2NormRDF [48] is an RDF normalization approach, which cleans and eliminates redundancies from RDF datasets as a means of converging into a canonical representation. Thus, it is not a compressor by itself. At the logical level, it removes edge and node duplication by applying particular transformation rules. From a critical point of view, this problem is partially addressed by physical compressors when removing duplicate triples and assigning unique IDs to literals used in more than one triple. However, physical compressors do not deal with blank nodes particularities, preserving their inner redundancy. At the physical level, RDF2NormRDF introduces additional rules to deal with namespace issues and to provide consistent statement orders. It also normalizes how types and language tags are effectively encoded. The normalization process implemented by RDF2NormRDF does not detect more logical/physical redundancy than HDT, but it outperforms HDT for an experimental setup that only comprises small datasets. Besides its compression achievements, RDF2NormRDF outputs normalized datasets that verify all desired quality properties (completeness, minimality, compliance and consistency). 3. Data Compression and Coding Data compression consists of reducing the number of bits required to encode data [43]. In this paper, we only focus on lossless compression (i.e., techniques that are able to reconstruct the original data from its compressed representation), and particularly, on the encoding of integer numbers. In the following, we first review the concept of Variable-Length codes (VLCs) [44], and we summarize state-of-the-art encodings of integer sequences. We then introduce the innovative concept of compact data structures [37] and delve into more details of functional bitsequences. Finally, we review compact data structures for graphs, which are then used in our approach. 3.1. Variable-Length Codes Some prominent RDF compressors (such as HDT [17]) first transform the RDF dataset into a dictionary of terms and a graph of IDs, before applying additional compression techniques. This allows symbolic and syntactic redundancy to be detected and removed independently, improving the overall compression effectiveness. Focusing on the ID-graph, its adjacency information is first modelled in the form of lists or matrices, and then these structures are encoded. Variable-Length codes (VLCs) [44] are often used to encode adjacency information, represented in the form of integer IDs. Given an alphabet of integers A={1,2, . . . , σ}, a VLC maps each value into a variable-length sequence of bits. Thus, VLCs consist of short and long codewords, i.e., compression is optimized when the most frequent integers are encoded with the shortest codewords. Note that VLCs assign the shortest codewords to the initial elements of the alphabet, hence IDs often need to be rearranged to meet this premise. Different forms of variable-length compression have been proposed in the state of the art [44]. In the following, we focus on the so-called Elias codes [13], which are practically used in the implementation of our approach. The gamma code:γis the simplest one and encodes any positive integer nin binary, preceded by blog2(n)c0-bits. For instance, the binary encoding of 17 is 10001 and blog2(17)c= 4, so γ(17) = 000010001.γuses 1 + 2blog2(n)cbits to encode an integer n. In contrast to γ, the Elias delta code:δonly uses 1 + blog2(n)c+ 2blog2(1 + blog2(n)c)cbits to represent n. In this case, the delta code concatenates γ(blog2(n)c+ 1), followed by the binary representation of the number excluding the first 1bit (since it is implicit); e.g., to encode 17, its gamma representation is first obtained: γ(blog2(17)c+1) = γ(4+1) = γ(5) =00101, and then the binary encoding of 17 is added (without the first 1-bit): 001010001. 3.2. Encoding of Integer Sequences Although VLCs can be directly used to compress individual integer IDs from the ID-graph, they disregard potential common regularities in adjacency lists. It is worth noting that adjacency lists are often sequences of increasing IDs, which introduces an additional redundancy. 7 S1 P1 O1. S1 P1 O8. S1 P3 O10. S1 P5 O14. S1 P7 O9. S2 P4 O1. S2 P5 O14. S2 P6 O11. S3 P1 O5. S3 P3 O12. S3 P5 O15. S3 P7 O9. S4 P1 O6. S4 P2 O7. S4 P4 O1. S5 P1 O4. S5 P2 O7. S5 P2 O13. S5 P4 O2. S6 P1 O6. S6 P3 O3. S6 P5 O14. S6 P7 O9. S7 P1 O8. S7 P2 O16. S7 P4 O1. Figure 8: RDF triples used for illustrating the RDF-Tr algorithm. •Finally, we consider an inner precedence relationship between subjects, predicates and objects. That is, Si< Sjif i<j;i, j ∈[1,|S|] (similarly for Piand Oiin ranges [1,|P|] and [1,|O|], respectively). In general, we assume that triples are sorted by (subject, predicate, object), otherwise an initial transformation (referred to as T0) is needed. T0. Subject-based reorganization. This initial step groups together all triples describing the same subject. As shown in Figure 9, this decision enables the RDF graph to be re-encoded as a forest of trees, where each subject is the root of a tree that includes all the triples in which the subject is involved. That is, triples are organized as a series of predicate-object lists (one per subject). For instance, S1has adjacency lists rooted by P1,P3,P5, and P7. The same four predicates are used by lists of S3and S6, so the first, the third, and the sixth subjects are described using the same predicate structure. Note that red dotted lines are used, in the figure, to show triples labelled with the rdf:type predicate, as they will have a special treatment (see Section 5.2). 5.1. Object-based transformation Based on the results of Fern´andez et al [15], a particular object in an RDF dataset is often tied to a certain predicate. Under this premise, we will perform the first transformation (T1) at object level. Object identifiers will be re-coded to predicate-local IDs, as using local identifiers takes up less space than global ones (see Foundation 3). T1. Object re-mapping. We re-map objects related to the same predicate with a new sequential identifier. These new local-IDs will be assigned in global-ID order. That is, we sort all objects of a given predicate by their (original) IDs in the dictionary, and we then assign the position of each object as its local-ID. Definition 3 formalizes this concept. Definition 3 (Local Object ID). Formally, we define O∗ i|Pj, a local object of predicate Pj, as O∗ i|Pj= Pj[i] : Pj={Ok. . . Ol};j∈[1,|P|],{k, l} ∈ [1,|O|], k < · · · < l. We abuse the notation to refer to a local Object ID as O∗ i, where the concrete predicate can be inferred from the context. For instance, in our previous excerpt, P3is used in 3 triples {(S1,P3,O10), (S3,P3,O12), (S6,P3,O3)}. Thus, taking into account the global order of objects, O∗ 1in P3refers to O3,O∗ 2to O10, and O∗ 3to O13. The same process is carried out for each predicate until all triples are rewritten with the new object identifiers. Figure 10 shows the output of this first transformation. Note that objects related to predicate rdf:type remain unchanged, since these triples will be treated separately (see T3 in Section 5.2). This transformation requires the introduction of an additional object mapping structure (MapO) to obtain (during decoding, presented in Section 5.4) the original ID of a local object. As shown in Figure 10, MapO is implemented as an adjacency list structure that contains the original IDs of the objects related to each predicate (except for those related to rdf:type). Thus, MapO encodes |P−1|adjacency lists. As explained in Section 3.4, this structure encompasses an integer sequence, MapO.S, which contains the lists of object IDs, and a bitsequence, MapO.B, which marks with 1-bits the end of each list. This can be easily seen in Figure 10, where the predicate P1is related to five objects: O1,O4,O5,O6, and O8(note that MapO.B[5]=1 marks the end of the list), P2is related to objects O7,O13, and O16 (MapO.B[8]=1 marks the end of the second list), and so on. Mapping a local object ID (O∗ i|Pj) to its global ID is simply implemented as neigh(MapO,j)[i], i.e., the ID of the i-th direct neighbor of Pj. For instance, the global ID of O∗ 3|P2can be computed as neigh(MapO,2)[3]=16, as the third object of predicate 2 is stored at MapO.S[8]= 16. 14 S1 O8O1O10 O14 O9O12O5O15 O912 17 7 O3 S3S6 O6O7 S4 O1O4O7 S5 O13 O8O16 S7 O1O2O1O14 S2 O11 P3P1P5P7P3P1P5P7P3P1P5P7 P2P1P4P2P1P4P2P1P4P5P4P6 O6O14 O9 Figure 9: RDF triples organized as a forest of trees. S1 O*5 O*1O*2O*1O9O*3O*3O*2O912 17 7 O*1 S3S6 O*4O*1 S4 O*1O*2O*1 S5 O*2O*5O*3 S7 O*1O*2O*1O*1 S2 O*1 P3P1P5P7P3P1P5P7P3P1P5P7 P2P1P4P2P1P4P2P1P4P5P4P6 O*4O*1O9 0 0 0 0 1 0 0 1 0 0 1 0 1 0 1 1 MapO 1 4 5 6 8 7 13 16 3 10 12 1 2 14 15 11 12 3 4 5 6 7 8 9 10 11 12 13 14 15 16 P1P2P3P4P5P6 Figure 10: Object re-mapping (note that local object IDs are assigned according to the global object ID order). S1 O*5 O*1O*2O*1O9O*3O*3O*2O912 17 7 O*1 S3S6 O*4O*1 S4 O*1O*2O*1 S5 O*2O*5O*3 S7 O*1O*2O*1O*1 S2 O*1 F1F1F1 F3F3F3 F2 O*4O*1O9 families P1P3P5P7P4P5P6P1P3P5P7P1P2P4P1P1P4 P2P1P3P5P7P1P2P4 0 0 0 0 1 0 0 1 0 0 1 0 1 0 1 1 MapO 1 4 5 6 8 7 13 16 3 10 12 1 2 14 15 11 12 3 4 5 6 7 8 9 10 11 12 13 14 15 16 P1P2P3P4P5P6 0 1 1 1 0 1 0 1 1 1 3 3 1 2 3 1 2 2 1 2 3 4 5 6 7 8 9 P1P2P3P4P5P6 Figure 11: Predicate family discovery. 5.2. Predicate-based Transformations Two predicate-based transformations are proposed to implement Foundations 1 and 2. Predicate families must first be discovered (transformation T2), and then be enriched, when necessary, with rdf:type values (transformation T3). After these transformations, general triples are re-encoded in the form of (subject, family, object), and triples involving rdf:type are removed and represented separately. T2. Predicate family discovering. This transformation looks for all the different combinations of predicates that are used for subject descriptions. As mentioned in Foundation 2, the different families are numbered with an autoincremental ID, hence all families are identified within the range [1,|F|], where |F|is the number of different families in the dataset. Thus, each subject Siis now related to a family Fj, hence adjacency lists can be compacted by replacing (multiple) predicate occurrences with the corresponding family ID. Figure 11 illustrates this transformation in our previous example, where three different families are discovered: F1={P1, P3, P5, P7},F2={P4, P5, P6}, and F3={P1, P2, P4}. Reconstructing the original triples from this encoding is straightforward. For instance, S1is related to F1, and the last level of objects contains four lists (one per predicate): 1. The first list contains O∗ 1and O∗ 5, and corresponds to the first predicate in F1, which is P1. Thus, it encodes the triples (S1, P1, O∗ 1) and (S1, P1, O∗ 5). 2. The second list only includes O∗ 2, and is related to the second predicate in F1, i.e., P3. Thus, it encodes the triple (S1, P3, O∗ 2). 3. The third list contains O∗ 1, which is related to the third predicate in F1, i.e., P5. Thus, it encodes the triple (S1, P5, O∗ 1). 4. Finally, the last list is tagged with P7, which refers to rdf:type. Thus, the corresponding triple will be removed from this representation (and encoded separately) in the following transformation. 15 S1 O*5 O*1O*2O*1O*3O*3O*212 17 O*1 S3S6 O*4O*1 S4 O*1O*2O*1 S5 O*2O*5O*3 S7 O*1O*2 O*1O*1 S2 O*1 F1F1F1 F3F3F3 F2 O*4O*1 0 1 1 1 9 types P1P3P5P4P5P6P1P3P5P1P2P4P1 P1P4 P2P1P3P5P1P2P4 families 0 1 1 1 0 1 0 1 1 1 3 3 1 2 3 1 2 2 1 2 3 4 5 6 7 8 9 P1P2P3P4P5P6 000010010010101 1 MapO 1 4 5 6 8 7 13 16 3 10 12 1 2 14 15 11 12 3 4 5 6 7 8 9 10 11 12 13 14 15 16 P1P2P3P4P5P6 MapO Figure 12: rdf:type encoding Information about predicates and families must also be preserved as part of the encoding. A new adjacency list structure, called families, is used for this purpose. As shown in Figure 11, it encompasses |P−1|adjacency lists, each one listing the IDs of the families in which each predicate (except for rdf:type) is used. For instance, the first predicate is used in two families: {F1, F3}, the second predicate only appears in a single family: {F3}, and so on. Retrieving the IDs of the families for a given predicate pis simply implemented using neigh(families, p). For instance, in our example, the families in which P4 appears can be retrieved as neigh(families,4) ={2,3}, i.e., families F2and F3. T3. Encoding of rdf:type.This transformation processes triples with the rdf:type predicate, retrieving class values (i.e., the objects of these triples) and using them to type the corresponding predicate families. Following Definition 2, the object types are part of the predicate families, so if two subjects are related to the same initial family, but they differ in the types, two independent families will be formed. Note also that a typed family can be related to multiple types, e.g., a family with the set of predicates prop:starring and prop:title can be used to describe a subject having the general type class:film and the more specific type class:Documentary. Figure 12 shows the resulting transformation. The typed triples (previously marked with red dotted lines) are no longer represented in the trees, as they are encoded in an additional data structure: types. This adjacency list preserves the IDs of the object types related to each predicate family. Note that, in this case, non-typed families are encoded as empty lists, hence types.B is implemented using the adjacency list variant that allows for empty lists (see Section 3.4). For instance, in our example, types.B=[0111] encodes that the first family is associated with one object type, while the other families have empty lists, i.e., they are not typed. The types structure is used to retrieve object types for a predicate family. For a given family f, it is easily implemented as neigh(types,f), being ∅if fis not typed. For instance, neigh(types,1)= 9, because O9is the class value of the first family. In contrast, neigh(types,2)=neigh(types,3)=∅, as F2and F3are not typed. 5.3. Subject-based Transformations As stated in Foundation 1, a subject is described by a particular family of predicates. Thus, the set of subjects described by the same family can be re-mapped as (family) local subjects. The following transformations allow local subjects to be represented and efficiently managed. T4. Subject re-mapping. This transformation first groups subjects by the family they belong to, and then orders each group by subject ID. This rearrangement is finally used to assign a new sequential identifier for each subject within a family. Definition 4 formalizes this concept. Definition 4 (Local Subject ID). Formally, we define S∗ i|Fj, a local subject of the family Fj, as S∗ i|Fj=Fj[i] : Fj6=∅and Fj={Sk. . . Sl};j∈[1,|F|],{k, l} ∈ [1,|S|], k < · · · < l. We abuse the notation to refer to a local subject ID S∗ i, where the concrete family can be inferred from the context. Figure 13 shows the resulting organization on our running example, where triples are now grouped by family. As we can see, subjects have been re-encoded within the family they are related to, represented with the new local subject identifiers, S∗ i. For instance, subjects S4,S5and S7were described by family F3(see Figure 12), and they are now re-mapped to S∗ 1,S∗ 2,S∗ 3, respectively. 16 S*1 O*5 O*1O*2O*1O*3O*3O*212 17 O*1 S*2S*3 O*4O*1 S*1 O*1O*2O*1 S*2 O*2O*5O*3 S*3 O*1 O*2O*1O*1 S*1 O*1 F1F1F1F3F3F3 F2 O*4O*1 0011001 MapS 1362457 1234567 P1P3P5P4P5P6 P1P3P5P1P2P4P1 P1P4 P2 P1P3P5P1P2P4 F1F2F3 0 1 1 1 9 typesfamilies 0 1 1 1 0 1 0 1 1 1 3 3 1 2 3 1 2 2 1 2 3 4 5 6 7 8 9 P1P2P3P4P5P6 0 0 0 0 1 0 0 1 0 0 1 0 1 0 1 1 MapO 1 4 5 6 8 7 13 16 3 10 12 1 2 14 15 11 12 3 4 5 6 7 8 9 10 11 12 13 14 15 16 P1P2P3P4P5P6 MapO Figure 13: Subject re-mapping. P1 O*5 O*1O*3O*4O*2O*4O*512 O*1 P4 O*1O*1 P2 O*2O*1O*2O*1O*3O*2O*3 P3 O*1 F1F3F2 F3F3 F1 O*1 P5 O*1O*2O*1 F2F1 O*1 P6 F2 S*1S*2S*3S*1 S*1S*2 S*1S*2S*3S*3S*1S*2S*3 S*1 S*1S*2S*3S*1S*2S*3S*1 0 0 1 1 0 0 1 MapS 1 3 6 2 4 5 7 1 2 3 4 5 6 7 F1F2F3 0 1 1 1 9 typesfamilies 0 1 1 1 0 1 0 1 1 1 3 3 1 2 3 1 2 2 1 2 3 4 5 6 7 8 9 P1P2P3P4P5P6 0 0 0 0 1 0 0 1 0 0 1 0 1 0 1 1 MapO 1 4 5 6 8 7 13 16 3 10 12 1 2 14 15 11 12 3 4 5 6 7 8 9 10 11 12 13 14 15 16 P1P2P3P4P5P6 MapO Figure 14: Triples rewritten with the RDF-Tr algorithm. A new subject mapping structure, (MapS), is required to obtain (during decoding, presented in Section 5.4) the original IDs of local subjects. MapS is implemented as an adjacency list structure that concatenates the original IDs of the subjects described by each predicate family. Thus, MapS encodes |F| adjacency lists. As shown in Figure 13, the subjects S1,S3, and S6are described by the family F1, and they are mapped to S∗ 1|F1,S∗ 2|F1, and S∗ 3|F1, respectively. Mapping a local subject ID (S∗ i|Fj) to its global ID is simply implemented as neigh(MapS,j)[i]. For instance, the local subject S∗ 3|F1is mapped to neigh(MapS,1)[3]= 6, i.e., the global subject S6. Note that this structure is also used during the decoding process to retrieve all subjects described by a given family Fj. This functionality is also implemented using the neigh operation, accessing the whole list of directed neighbors. For instance, in our example, neigh(MapS,1)={1,3,6}retrieves all subjects described by F1. T5. Predicate Grouping. The Subject-Family-Object tree-shape organization from the previous transformations results in a very flat representation, as one subject is only represented by one family. Thus, the last step of our process consists of obtaining a bushy representation that can help compression and favor fast decoding. The previous representation is rearranged by predicate, obtaining Predicate-FamilyObject trees, such as the example shown in Figure 14. Therefore, a predicate is related to several lists of objects, one per each family where the predicate is present. This forest of trees can be represented in a more compact notation based on adjacency lists. The “abstract” representation of these adjacency data, referred to as ATr, is shown in Figure 15. ATr only needs to provide a simple operation getObjects, which retrieves all local object IDs given a predicate and a subject. Sections 6 and 7 describe two practical implementations of ATr on the basis of the existing HDT and k2-triples compressors. 5.4. RDF-Tr Implementation and Decoding Figure 15 shows the final organization and structures after applying RDF-Tr, which includes the compact representation of triples (ATr), and other auxiliary structures, families,types,MapS and 17 (P1 [O*1,O*5|O*3|O*4] [O*4|O*2|O*5]) (P2 [O*1|O*1,O*2|O*3]) (P3 [O*2|O*3|O*1]) (P4 [O*1] [O*1|O*2|O*1]) (P5 [O*1|O*2|O*1] [O*1]) (P6 [O*1]) ATR 0 1 1 1 9 types families 0 1 1 1 0 1 0 1 1 1 3 3 1 2 3 1 2 2 1 2 3 4 5 6 7 8 9 P1P2P3P4P5P6 0 0 1 1 0 0 1 MapS 1 3 6 2 4 5 7 1 2 3 4 5 6 7 F1F2F3 000010010010101 1 MapO 1 4 5 6 8 7 13 16 3 10 12 1 2 14 15 11 12 3 4 5 6 7 8 9 10 11 12 13 14 15 16 P1P2P3P4P5P6 Figure 15: Predicate family based (adjacency list) encoding. MapO. In the following, we briefly summarize the implementation remarks shown in the previous section: •RDF-Tr focuses on the reorganization of triples in a dataset, hence it manages IDs for each subject, predicate and object term and assumes the use of a dictionary to make a bidirectional translation between terms and integer IDs (similar to most symbolic compressors). •The mapping structures for subjects and objects, MapS and MapO, are represented as adjacency lists, which are succintly encoded using a bitsequence and an integer ID sequence (see Section 3.4). The types and families structures are similarly encoded as adjacency lists. •The implementation of ATr (essentially, adjacency data) may vary, depending on the internal structure of the RDF syntactic compressor that uses RDF-Tr (as shown in Sections 6 and 7). Algorithm 5 illustrates the decoding process that retrieves the original triples from the RDF-Trbased encoding. It implements a multi-nested-loop algorithm that iterates through all predicates (Line 1), except for rdf:type. For each predicate, we obtain the list of families in which the predicate is present (Line 3), and iterate over them (Line 4). For each family, we first obtain its ID (Line 5), and then use it to retrieve the list of object types (or ∅, if it is a non-typed family), and the list of subjects related to this family (Lines 6and 7). These subjects are then also iterated (Line 8). For each subject, we use ATr to retrieve the list of objects related to the current predicate and subject (Line 10), referred to as Os. At this point, we have retrieved all IDs, but they must be mapped from their local encoding to their original IDs in the dictionary. In Line 9, the local subject ID is mapped to its global one, and global object IDs are obtained in Line 13 (within a loop that iterates over all objects in Os). Finally, in Line 14, the corresponding triple is emitted. Note that Lines 15 to 17 are only executed for typed families. In this case, object types are iterated and new typed triples are emitted for the corresponding subject and object type. In the following sections, we show how RDF-Tr can be integrated into existing compressors, which assume the responsibility of implementing ATr. 6. HDT++ The integration of HDT and RDF-Tr is referred to as HDT++. We first provide an overview of HDT, with particular attention to triples encoding. Then, we show how RDF-Tr can be plugged into HDT. 6.1. HDT HDT [17] was a pioneer in RDF binary serialization, specifically focused on optimizing storage and transmission costs over a network, as well as fast retrieval on compressed space. It is specifically tailored to potentially large datasets, achieving similar compression ratios to general techniques such as gzip. As summarized in Section 2.2, RDF is encoded using three logical components: Header (i.e., metadata), Dictionary (the aforementioned mapping between string terms and IDs), and Triples (the graph of IDs). We focus on the Triples component hereinafter, as RDF-Tr is focused on triples organization. 18 Algorithm 5: Decoding algorithm. 1for predicate ←1to |P−1|do 2ptrSubject ←1; 3Fp←neigh(families, predicate); 4for f←1to |Fp|do 5family ← Fp[f]; 6Tf←neigh(types, family); 7Sf←neigh(MapS, family); 8for s←1to |Sf|do 9subject ← Sf[s]; 10 Os←ATr.getObjects(predicate, ptrSubject); 11 ptrSubject ←ptrSubject + 1; 12 for o←1to |Os|do 13 object ←neigh(MapO, predicate)[Os[o]]; 14 newtriple(subject, predicate, object); 15 if Tf6=∅then 16 for t←1to |Tf|do 17 newtriple(subject, rdf:type,Tf[t]); 1 81 10 14 9 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 125 15 9 12 17 73 36 6 7 4 1 4 7 5 13 8 16 7 121 14 2 11 31 5 7 0 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 1 0 0 0 1 0 0 1 31 5 7 31 5 7 21 4 21 4 21 454 6 Subjects Predicates Objects 6 14 9 Figure 16: Forest of trees modeling ID triples in HDT. Bp 000100100010010010001001 Sp 135745613571241241357124 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 Bo 01111111111111110111111111 So 1 8 10 14 9 1 14 11 5 12 15 9 6 7 1 4 7 13 2 6 3 14 9 8 16 1 Figure 17: BitmapTriples implementation. Figure 16 shows the organization of HDT Triples over the original triples of our running example (see Figure 8). Triples are organized as a forest of trees, one per different subject in the dataset: the root of each tree encodes the subject, the second level encodes the predicates related to the subject and the leaves encode the adjacency lists of all objects related to each predicate within its root (subject) scope. Note that the IDs of subjects, the predicates related to each subject, and the objects related to a subject-predicate pair, are in increasing order. HDT encodes triple IDs using the so-called Bitmap Triples structure. As shown in Figure 17, this approach consists of two coordinated adjacency lists that respectively encode predicate and object adjacency information for each subject. On the one hand, predicate IDs are listed in the integer sequence Sp, delimiting each subject list with 1-bits in Bp. Thus, the i-th 1-bit marks the end of the list corresponding to subject i. On the other hand, So contains the integer sequence of object IDs, corresponding to the leaves of the forest, where a 1-bit in the bitsequence Bo marks the end of the objects related to the corresponding subject-predicate pair. 6.2. Plugging RDF-Tr into HDT Plugging RDF-Tr into HDT is straightforward. RDF-Tr assumes that the HDT dictionary and the corresponding forest of trees (represented in Figure 16) has been created. Then, leaving aside the dictionary compression, which is performed as in HDT, the novel HDT++ process starts by traversing the obtained forest of trees and performing transformations T1, T2, T3, T4, and T5 to reorganize triples and build the data structures described previously. Finally, the abstract ATr structure is implemented as follows. 19 HDT++ (P1 [O*1,O*5|O*3|O*4] [O*4|O*2|O*5]) (P2 [O*1|O*1,O*2|O*3]) (P3 [O*2|O*3|O*1]) (P4 [O*1] [O*1|O*2|O*1]) (P5 [O*1|O*2|O*1] [O*1]) (P6 [O*1]) Bo 0111111 So 1 5 3 4 4 2 5 Bo 1 0 1 1 So 1 1 2 3 Bo 1 1 1 So 2 3 1 Bo 1 1 1 1 So 1 1 2 1 Bo 1 So 1 P1 P2 P3 P4 P5 P6 Ps Bo 1 1 1 1 So 1 2 1 1 Figure 18: HDT++ implementation of ATr. Algorithm 6: HDT++: getObjects(predicate, ptrSubject). 1return neigh(Ps[predicate], ptrSubject); HDT++ encodes ATr as an array of |P−1|adjacency lists (one per predicate, except for rdf:type), referred to as Ps. Each list is encoded as in BitmapTriples, i.e., using an integer sequence of IDs, So, and its aligned bitsequence, Bo. This simple but effective approach allows adjacency lists to be managed independently, hence each one can be encoded according to the features of its corresponding predicate. Algorithm 6 shows the implementation of the getObjects method in HDT++. Recall that this operation is used in the decoding process (see Line 10 of Algorithm 5) to get the objects related to a given predicate and subject. Note that, in practice, the decoding algorithm does not iterate on the subject ID, but the position (i.e., ‘ptrSubject’ in the code) where its object list is encoded for a given predicate, as explained in Section 5.4. This algorithm simply performs the neigh operation over the corresponding adjacency list structure, stored at Ps[predicate], retrieving all neighbors encoded in the list of ptrSubject. Finally, note that the remaining data structures (MapO, MapS, types and families) are built in HDT++ following the same aforementioned procedures7(see Section 5). 7. K2-triples++ We refer to k2-triples++ as the integration of k2-triples and RDF-Tr. As in the previous section, we first introduce the foundations of k2-triples and then we describe the RDF-Tr integration. 7.1. k2-triples Similarly to HDT, k2-triples [1] performs dictionary compression before encoding the resulting IDgraph. It is worth noting that both approaches implement the same scheme for dictionary compression. k2-triples takes advantage of the low number of predicates used in an RDF dataset and partitions it vertically. That is, k2-triples performs a predicate-based partition of the dataset into disjoint subsets of subject-object pairs, and then these subsets are highly compressed as binary matrices (i.e., a 1-bit marks that the corresponding triple exists in the dataset) using k2-trees [9]. The size of these matrices will be m×m, where mis the minimum power of kthat is greater than max(|S|,|O|). Continuing with the triples given in our running example, Figure 19 illustrates the resulting k2-tree for the first predicate (with ID 1), i.e., it encodes all triples (s, 1, o), where sand oare the IDs of the corresponding subjects and objects. The conceptual 16 ×16 matrix is illustrated on the left hand side (note that, in this example |S|= 7 and |O|= 15), modelling subjects by rows and objects by columns. We consider k= 2, hence each level is divided into k2= 4 submatrices. Recall that (i, j) = 1 means that there is a triple, in which the subject i (rows) is related to object j (columns) through the predicate 1. The right hand side of Figure 19 depicts the conceptual tree and the final configuration of bitsequences Tand L, which effectively encode the k2-tree. As explained in Section 3.4, all the aforementioned graph operations (including neigh) are efficiently provided by the k2-tree using rank and select. 7These structures are not represented in Figure 18 for simplicity, but their configuration is the same as in Figure 15. 20 P 11 2 3 4 5 6 7 8 ... 16 110000001 0 200000000 30 0 0 0 1000 40000010 0 500010000 60000010 0 700000001 800000000 ... 0 0 16 T = 1000 1111 1000 0110 0100 1001 L = 1000 0100 1001 0100 0001 0100 1000 1 1 1 1 1 0 0 0 0 1 1 0 0 1 0 0 1001 100001001001 01000 0 0 1 0100 objects subjects Figure 19: Vertical-Partitioning on k2triples (k=2) for predicate P1. k2triples++ (P1 [O*1,O*5|O*3|O*4] [O*4|O*2|O*5]) (P2 [O*1|O*1,O*2|O*3]) (P3 [O*2|O*3|O*1]) (P4 [O*1] [O*1|O*2|O*1]) (P5 [O*1|O*2|O*1] [O*1]) (P6 [O*1]) 12345678 110001000 200100000 300010 0 0 0 400010 0 0 0 501000000 600001000 700000000 800000000 1234 11000 2110 0 30010 40000 1234 1010 0 20010 31000 40000 1 2 3 4 110 0 0 210 0 0 3010 0 410 0 0 1234 11000 2010 0 31000 41000 1 11 P1 P2P3 P4P5 P6 Figure 20: K2triples++ implementation of ATr Algorithm 7: k2triples++: getObjects(predicate, ptrSubject). 1return neigh(k2−tree[predicate], ptrSubject); 7.2. Plugging RDF-Tr into k2-triples Transforming k2-triples into k2-triples++ involves a similar process to that described for HDT++. Thus, the dictionary and the ID-graph are first obtained, and the RDF-Tr transformations are then performed to obtain MapO, MapS, types, families and the ATr structure, which is represented as follows. As in k2-triples, ATr is vertically partitioned by predicate, i.e., (subject, object) pairs are encoded in the k2-tree corresponding to their related predicate(s). It is worth noting that, in k2-triples++, the size of each adjacency matrix depends exclusively on the number of subjects and objects related to the corresponding predicate (instead of the total number of subjects and objects in the dataset). Figure 20 illustrates how k2-triples++ implements ATr. Note that the largest matrix (of size 8 ×8) is modelled for predicate 1, as it is related to 6 different subjects and 5 different objects. In contrast, the matrix for predicate 6 is 1 ×1, as this predicate is just present in a single triple. The implementation of ATr in k2-triples++ provides the getObjects operation, required for decoding. As shown in Algorithm 7, we also make use of the neigh operation of the k2-tree to process the row ptrSubject and retrieve the corresponding objects. 8. Experimental Evaluation This section evaluates the performance of RDF-Tr in real-world RDF datasets. We first provide concrete details of our prototype (Section 8.1) and then describe the evaluation corpus (Section 8.2). We analyze the results of the evaluation in Section 8.3 and Section 8.4 provides a final discussion of our results. 8.1. Practical RDF-Tr Implementation Our RDF-Tr prototype8is built in C++11, making extensive use of the Succinct Data Structure Library9(SDSL). This library implements different compact data structures and provides rich functionality 8The code of the prototype is publicly available at https://github.com/antonioillera/HDTpp-src 9https://github.com/simongog/sdsl-lite 21 over these structures10. Thus, our prototype implements all the auxiliary RDF-Tr structures, types, families, MapO and MapS on SDSL functionalities: •Types is serialized as an adjacency list: the sequence Sis implemented as an SDSL int vector, which uses log2(|O|) bits per ID, and the bitsequence Bis built over a plain bit vector. Note that a variant of the aforementioned Clark’s structure11 [10] is loaded to provide efficient select support. •Families is serialized as an adjacency list, but it is loaded as a vector of vectors to speed up data access. Each secondary vector is implemented as an independent SDSL int vector, which encodes each ID using a number of bits proportional to the greatest family ID: F’ related to the given predicate; i.e. log2(F0)≤log2(|F|) bits per ID. •MapO is also serialized as an adjacency list, but it is loaded as a vector of vectors to optimize the memory footprint. Note that the list of objects related to each predicate can be very large, so bitsequences use more bits than the required pointers. Besides, object lists can be compressed, saving additional space. Thus, we implement secondary vectors using the compressed SDSL enc vector. First, we perform gap-encoding over the elements of each list and store samples each t dens positions. Then, the resulting representation is compressed using Elias-Delta. Note that t dens is a user-defined value, so it is possible to tune this parameter for faster decompression, or greater compression (at the expense of speed). Thus, in the analysis section, we will evaluate how the variation of this parameter affects the decompression time and space of some datasets. •MapS is loaded similarly to MapO in order to exploit the fact that the lists of subjects for predicate families are also large, and these are effectively compressed using gap-encoding and Elias-Delta. Finally, we provide two concrete implementations of ATr leading to the HDT++ and k2-triples++ compressors (as explained in Sections 6 and 7): •HDT++ serializes |P−1|adjacency lists and loads them into an array for decoding purposes. Note that the int vector of each adjacency list is configured to use log2(|Op|) bits per ID, where |Op| is the number of different objects within the range of the predicate p. •k2-triples++ serializes |P−1|k2-trees, each one configured according to the number of subjects and objects related to the corresponding predicate. We use k= 2, as in the original k2-triples approach [1]. 8.2. Evaluation Corpus: Description and Statistics Our evaluation considers five real-world RDF datasets: dblp provides open bibliographic information on major computer science journals and proceedings; dbtune includes music-related structured data; us census provides census data from the U.S.; linkedgeodata uses the information collected by the OpenStreetMap project and makes it available as an RDF knowledge base according to the Linked Data principles; and dbpedia is an RDF conversion of Wikipedia (mostly on the infobox information). Table 1 reports the main statistics of these datasets, namely, the number of triples, and the number of total subjects, predicates, and objects, (|S|,|P|, and |O|, respectively). Furthermore, Table 2 reports relevant statistics for RDF-Tr. We show, for each dataset, the number of families (|F|), the number of different types used in the dataset, the number of typed-families (recall that a typed-family is a family that is defined by at least one type), the number of typed-triples (i.e., triples involving rdf:type), as well as the maximum value of local object identifiers (i.e., the maximum number of objects in the range of a particular predicate). A first analysis of these statistics shows that linkedgeodata and dbpedia are the less-structured datasets, inasmuch as the number of families is ≈24 times the number of predicates in linkedgeodata and ≈50 times in the case of dbpedia. Despite their low structural level, it is important to note that the number of detected families is small compared to the possible combinations of relationships between subjects and predicates. Conversely, dbtune and dblp are structured datasets, since the number of 10A brief summary of the structures and operations is available at http://simongog.github.io/assets/data/sdslcheatsheet.pdf 11https://github.com/simongog/sdsl-lite/blob/master/include/sdsl/select support mcl.hpp 22 Dataset #triples |S| |P| |O| dblp 55,586,971 3,591,091 27 25,154,979 dbtune 58,920,361 12,401,228 394 14,264,221 us census 149,182,415 23,904,658 429 23,996,813 linkedgeodata 271,180,352 51,916,995 18,272 121,749,861 dbpedia 837,257,959 113,986,155 60,264 221,623,898 Table 1: Main statistics of the evaluation corpus. Dataset |F|#types #typed-families #typed-triples Max local-obj dblp 283 14 283 5,475,762 6,428,355 dbtune 1,047 64 866 12,340,116 2,254,960 us census 106 0 0 0 1,242,683 linkedgeodata 441,922 1,081 440,035 81,261,427 38,826,195 dbpedia 2,969,486 370,069 2,811,839 92,725,995 40,325,707 Table 2: Statistics related to RDF-Tr. 0 0.5 1 1.5 2 2.5 3 3.5 4 DBLP Dbtune 2000 US Census Linked Geo Data Dbpedia Mean Datasets #predicates per object (with deviations) Figure 21: Number of predicates per object (mean and standard deviation). 1 10 100 1000 10000 1 10 100 1000 10000 100000 1e+06 Number of RDFpredicates related to X objects Number of RDF objects related to Y predicates Figure 22: Distribution of RDF objects per predicate in linkedgeodata. families is ≈2.5 and ≈10.5 times the number of their predicates, respectively. Finally, us census is a clear example of a highly-structured dataset because the number of families is even less than the number of predicates. The use of types is denoted by #types,#typed-families and #typed-triples columns in Table 2. A comparison of #typed-families with the total number of families shows that most families are actually typed (except for us census, which does not use types). In other words, although the predicate rdf:type is optional in a dataset, it is actually present in most subject descriptions. In this regard, the #typedtriples column shows that typed datasets include a high number of triples involving rdf:type. For instance, linkedgeodata has more than 81 million typed triples, which corresponds to almost 30% of its total triples, while in the rest of the typed datasets, 10-20% of the triples are typed. Figure 21 extends these statistics and represents the average number of predicates per object. As expected (see Section 4.2), we can observe that the number of predicates per object is very close to 1, even in the less structured datasets. In turn, Figure 22 shows the inverse relation, i.e., the number 23 Journal of Intelligent & Fuzzy Systems (2020) 1–12 1 IOS Press iHDT++: Improving HDT for SPARQL Triple Pattern Resolution Antonio Hernández-Illera a,∗, and Miguel A. Martínez-Prieto aand Javier D. Fernándezband Antonio Fariña c aDepartment of Computer Science, University of Valladolid, Spain bVienna University of Economics and Business & Complexity Science Hub Vienna, Austria cUniversity of A Coruña, Database Lab, CITIC, Spain Abstract. RDF self-indexes compress the RDF collection and provide efficient access to the data without a previous decompression (via the so-called SPARQL triple patterns). HDT is one of the reference solutions in this scenario, with several applications to lower the barrier of both publication and consumption of Big Semantic Data. However, the simple design of HDT takes a compromise position between compression effectiveness and retrieval speed. In particular, it supports scan and subject-based queries, but it requires additional indexes to resolve predicate and object-based SPARQL triple patterns. A recent variant, HDT++, improves HDT compression ratios, but it does not retain the original HDT retrieval capabilities. In this article, we extend HDT++ with additional indexes to support full SPARQL triple pattern resolution with a lower memory footprint than the original indexed HDT (called HDT-FoQ). Our evaluation shows that the resultant structure, iHDT++, requires 70−85% of the original HDT-FoQ space (and up to 48 −72% for an HDT Community variant). In addition, iHDT++ shows significant performance improvements (up to one level of magnitude) for most triple pattern queries, being competitive with state-of-the-art RDF self-indexes. Keywords: HDT, RDF compression, Triple pattern resolution, SPARQL, Linked Data. 1. Introduction The World Wide Web is a network of documents, in which nodes (web pages) contain pieces of information intended for human consumption, and the edges relate this information through links, which facilitate navigation among pages. This document-centric information architecture does not facilitate access to raw data, hindering to automate different processes. The Web of Data arises as a response to this situation and offers, on the own infrastructure of the Web, mechanisms to represent and interconnect data with sufficient semantics and level of granularity to allow automatic processing [2]. RDF (Resource Description Framework) [24] plays a fundamental role in the Web of Data. RDF models and interconnects data using ternary sentences (triples) formed by a subject (S), a predicate (P), and an object (O). These RDF triples can be in- *Corresponding author. Antonio Hernández Illera, Department of Computer Science, University of Valladolid. Campus María Zambrano, 40006, Segovia, Spain. E-mail: [email protected]. terpreted as directed graphs in which subjects and objects act as nodes and predicates are the edges between them. The flexibility of RDF has facilitated its use as a standard de facto for the publication of raw data on the Web, and, more recently, Knowledge Graphs [3]; DBpedia or Bio2RDF publish billions of triples, being a clear example of the volume reached by RDF collections and, in turn, the scalability challenges that entail its management and consumption. One of these scalability problems is the way RDF datasets are serialized. Traditionally, “flat” formats (like XML) have been used, whose verbosity is a limiting factor when managing Big Semantic Data. The alternative is to use binary formats that encode the RDF datasets according to its structural and/or semantic properties. HDT (Header-Dictionary-Triples) [7] is positioned in this scenario and proposes a binary format that exploits RDF redundancy [14]. HDT obtains compression ratios comparable to those reached by gzip, and it reports competitive performance for scan queries and subject-based retrieval [8], with no prior decompression. In addition, HDT-FoQ (Focused on Querying) 0000-0000/20/$00.00 c 2020 – IOS Press and the authors. All rights reserved 2Hernández-Illera et al. / iHDT++: Improving HDT for SPARQL Triple Pattern Resolution [15] adds two indexes (either loaded into memory or mapped from disk) on top of HDT to allow for full SPARQL [21] triple pattern (TP) resolution.1 HDT has been adopted in the Web of Data because of its simplicity and a competitive space/time tradeoff, taking a key role in the development of client-side query processors such as Triple Pattern Fragments [25] and SAGE [17]. However, both HDT and HDT-FoQ are limited by a design that emphasizes simplicity of representation and disregards other sources of redundancy. HDT++ [11] modifies that design and implements a reorganization of triples that partially eliminates structural redundancies. Specifically, HDT++ takes advantage of the fact that subjects of the same type are described by similar sets of properties and that their value ranges have little overlap. HDT++ notably improves the compression ratios obtained by HDT, as well as its decoding speed. Yet, it does not provide the necessary mechanisms to solve SPARQL TPs. In this paper, we present iHDT++ an enhanced representation that allows HDT++ files to be efficiently queried. In particular, we extend the existing HDT++ structures with additional information to resolve predicate-based and subject-based TPs (i.e. those in which the predicate or subject are provided, respectively). Then, we provide a new object-based index that completes the iHDT++ proposal and enables full SPARQL TP resolution. Our experiments show that iHDT++ uses around 70 −85% of the memory footprint of HDT-FoQ, largely outperforming most of the TPs (e.g. the challenging predicate-based retrieval, (?P?)). The space differences are even more noticeable with the HDT Community version (48-72%), a practical proposal to speed up predicate-based issues (presented in Section 2.3). iHDT++ also shows competitive space/time tradeoffs with state-of-the-art RDF self-indexes, k2-triples and RDFCSA. The rest of the article is organized as follows. Section 2 presents the background of iHDT++. Section 3 describes the structures added by iHDT++ on top of HDT++, and explains how these can be used to resolve SPARQL TPs. Section 4 compares the performance of iHDT++ with the existing HDT-based solutions and the most promising RDF self-indexes. Finally, our conclusion and future work are discussed in Section 5. 1ATP is an RDF triple in which any of its components can be variable (?is used to indicate components that are variables): (SPO), (SP?),(S?O),(S??),(?PO),(?P?),(??O), and (???). 2. Background This section provides the basic background of the paper. We introduce the notion of compact data structure [18], with particular attention to those structures used by the HDT-based approaches and iHDT++. Compact data structures are also at the core of the most competitive RDF compressors, including efficient RDF self-indexes. We also review state-of-the-art RDF compression techniques, and we delve into particular details of HDT-based approaches, which set the foundations of our proposal. 2.1. Compact Data Structures A compact data structure [18] proposes a data arrangement that uses an amount of space close to the theoretical optimal number of bits (required to preserve the data), while providing efficient functionality with no prior decompression. Thus, a compact data structure compresses the original data and allows it to be queried and manipulated in compressed form. The main blocks of compact data structures are functional bitsequences, explained as follows. Bitsequences. A bitsequence B[1, n]is an array of n bits that provides three basic operations: –access(B, i)returns B[i], for any 1≤i≤n. –rankv(B, i)counts the number of occurrences of the bit v∈ {0,1}in B[1, i], for any 1≤i≤n; rankv(B, 0) = 0. –selectv(B, j)returns the position of the j−th occurrence of the bit v∈ {0,1}in B, for any j≥ 0;selectv(B, 0) = 0 and selectv(B, j) = n+ 1 if j > rankv(B, n). iHDT++ uses a “plain bitsequence” that implements Clark’s approach [6], which adds additional structures on top of Bto efficiently resolve rank and select (access is directly performed on the bit array in constant time). Bitsequences can be compressed [18] to save space requirements, but none of the RDF compressors analyzed in this paper use them. Sequences. A sequence S[1, n]is a generalization of a bitsequence, whose elements S[i](i.e. symbols) come from to an alphabet Σ = [1, σ]. They support the same operations: access(S, i)returns the symbol stored at S[i], while ranks(B, i)and selects(B, j) allow any symbol s∈Σto be queried. The simplest sequence implementation is an array that encodes each symbol using dlog2(σ)ebits. This Hernández-Illera et al. / iHDT++: Improving HDT for SPARQL Triple Pattern Resolution 3 Fig. 1. Example of adjacency list encoding. “plain sequence” answers access(S, i)in O(1), by accessing S[i], but it does not resolve rank and select efficiently. The wavelet tree [10] proposes an alternative for sequence encoding. It organizes symbols in a balanced tree of height h= log(σ), comprising hbitsequences of nbits each. It requires nlog2(σ) + o(n)bits of space, using plain bitsequences, and answers access,rank, and select in O(h). Sequences of symbols are highly compressible in many cases; e.g. posting lists in Information Retrieval or adjacency lists in (Semantic) Web Graphs are usually gap-encoded [13] to exploit that symbols are sorted, in increasing order, within the sequence. Different forms of variable length compression [23] can also be adopted to compress the sequence of symbols. They compress sequences at the cost of slower access, as the symbols must be previously decompressed. Adjacency Lists. Adjacency lists are typically used to encode graphs. Given the RDF scope of this paper, we hereinafter focus on directed graph encoding. A directed graph G= (V, E)is composed of a set of vertices, V, and the set of edges, E⊆V×V. Typically, the direct neighbors of a vertex vrefer to all vertices that can be reached from v, i.e. {(v, u)∈E}. Conversely, the set of reverse neighbors of a vertex vcontains vertices usuch that {(u, v)∈E}. Figure 1 shows the adjacency list encoding for a graph with n= 6 vertices and a set of e= 10 edges: E={(1,2),(1,3),(2,4),(3,2),(3,4),(3,5),(4,5), (4,6),(5,6),(6,1)}. Note that the structure AL concatenates all adjacency lists into a single sequence, S, and a bitsequence, B, in which 1-bits mark the last element of the list of each vertex. In the example, the list for the first vertex v1is encoded in S[1,2], the list for v2in S[3], and so on. The direct neighbors of v1are {v2, v3}, and the reverse neighbors of v2are {v1, v3}. Adjacency lists are optimized to obtain direct neighbors for a vertex v:neigh(G, v), and to check if two vertices vand uare connected: adj(G, v, u), which returns the position of uin the list if (v, u)∈E, or -1 otherwise. Both operations are implemented using select on Band then access to the corresponding positions in S, but this organization is not well suited for reverse neighbors queries, unless the transposed graph is encoded, doubling the required space [18]. Self-Indexes. A self-index is a compressed index that provides search functionality over a data collection and contains enough information to reproduce it [19]. Thus, a self-index can replace the original data collection by a compressed representation that also enables efficient retrieval operations to be performed. Although self-indexes were originally designed for text collections, they are currently used to manage different types of data, including RDF. In the scope of this paper, we refer the k2-tree [5], a highly compressed binary matrix that is used for graph encoding and supports efficient direct and reverse neighbors queries, and CSA [22], a fullyfunctional compressed suffix array. 2.2. RDF Compression RDF compressors detect and remove redundancy at symbolic,syntactic, and/or semantic levels [20], reporting impressive space savings, and enabling efficient management of big semantic data [14]. HDT [8] was originally devised as binary serialization format for RDF, but it has been used as RDF compressor due to its compactness (similar to gzip). HDT also allows for basic, but efficient retrieval functionality. This feature was further improved by HDT-FoQ [15], a compact data structure configuration that enables full SPARQL TPs resolution to be performed on top of HDT files, with no prior decompression. This functionality was rapidly adopted, making HDT a core component of state-of-the-art client-side query processors such as Triple Pattern Fragments [25] and SAGE [17]. More recently, HDT++ [11] revisited HDT to reduce its memory footprint, but the resulting approach did not retain the retrieval capabilities of HDT-FoQ. More details about HDT are provided in Section 2.3. RDF self-indexes [14] detect and remove syntactic redundancy underlying to the graph structure of RDF. These self-indexes support full SPARQL TPs resolution, like HDT-FoQ, but their optimized configurations of compact data structures make them more competitive in terms of space. K2-triples [1] partitions the RDF dataset by predicate and, for each predicate, it models pairs (subject, object) as binary matrices where [i, j] = 1 mean that the i-th subject and the j-th object are connected by the given predicate. The resulting matrices are very sparse and can be effectively compressed using k2-trees [5]. RDFCSA [4] models the RDF dataset as a text, in which subjects precede lexicographically predicates and objects. This “text” is then indexed using a compressed suffix array (CSA) 4Hernández-Illera et al. / iHDT++: Improving HDT for SPARQL Triple Pattern Resolution [22], which ensures efficient data retrieval. Nevertheless, this organization promotes subject-based queries, which are more efficient than the remaining SPARQL TPs. Both self-indexes are included in our experimental setup and compared to iHDT++ (see Section 4). Finally, note that other RDF compressors purely focus on space reduction and disregard search functionality [14], which is our core contribution. 2.3. HDT-based Approaches HDT [8] is a binary serialization format that organizes the content of an RDF dataset into two components (Dictionary and Triples), which are primarily responsible for the effectiveness of HDT. On the one hand, the Dictionary faces the symbolic redundancy of an RDF graph providing a compressed catalog with the terms used in the nodes and edges of the RDF graph, assigning a unique identifier (ID) to each of them. These IDs are used to encode the structure of the graph in the Triples component. In this paper, we leave aside Dictionary compression and retrieval [16], as it is orthogonal to our current approach, and we focus on optimizing the Triples component. The Triples (in the form of IDs) conform a forest with subject-rooted trees and (predicate, object) sorted branches. As shown in Figure 2, the content of these trees is stored in two correlated adjacency lists, that represent the predicates of each subject, and the objects of each subject-predicate pair.2The HDT adjacency list implementations encompass a plain sequence (i.e. an integer array) and a plain bitsequence [9], where 1-bits mark the end of each list; i.e the last descendent of a branch. This organization makes triples decompression efficient and facilitates access per subject (i.e. in SPO order), but prevents the rest of SPARQL TPs from being efficiently resolved. 2.3.1. HDT-FoQ (Focused on Querying) HDT-FoQ [15] enhances HDT files with two additional indexes to provide full TPs resolution. On the one hand, it replaces the sequence Sp(in the adjacency list of predicates) by a wavelet tree [10], which provides indexed access by predicate (PSO order). It adds a little space overhead, but ensures that all predicatebased accesses are performed in logarithmic time (with the number of predicates). On the other hand, HDTFoQ defines an object-index in the form of adjacency 2In Figure 2, we highlight the triples involving the predicate rdf:type, as they will have a special treatment in HDT++. list (OPS-order). It keeps track of the positions of each object (in the adjacency list of objects), enabling fast object-based TPs. However, this object index requires non-negligible space, reducing the overall HDT-FoQ effectiveness. Although HDT-FoQ reports competitive space-time tradeoffs, it is worth noting that its performance is not competitive for the TP that only binds the predicate: (?P?). In this case, predicate occurrences are performed via select operations over the wavelet tree, which suffer from scalability problems with a mediumlarge number of predicates. A community version of HDT-FoQ, referred to as HDT Community hereinafter, solve this issue pragmatically. First, it removes the wavelet tree and restores the original plain adjacency list of predicates. Then, it uses the transposed version of this latter to speed up predicate-based queries. Thus, this alternative improves predicate-based queries, but increases space requirements. 2.3.2. HDT++ HDT++ [11] proposes an alternative serialization for RDF datasets that optimizes the HDT effectiveness by applying the RDF-TRtransformation [12]. RDF-TR preprocesses the HDT Triples component (see Figure 2) to detect and eliminate redundancy at various levels, using three types of transformations. Object-based transformation. The ranges of objects related to different predicates tend to be disjoint, i.e. an object does not usually relate to more than one different predicate [11]. This fact enables objects to be locally identified within the range of each predicate, hence using lower IDs to encode each object. It reduces drastically the number of bits used to encode object occurrences, but requires a mapping structure (referred to as MapO) to translate the new local IDs to the original ones. MapO is an adjacency list that encompasses (in increasing order) the original IDs of the objects related to each predicate. Figure 3 illustrates the MapO configuration for the triples in Figure 2: predicate 1is related to the original object IDs {1,4,5,6,8}, predicate 2with the objects {7,13,16}, etc. MapO uses the neigh primitive, of the adjacency list structure, to map local IDs to their global counterparts. Predicate-based transformations. RDF does not restrict how entities are described, but subjects are usually described using common sets of properties. For instance, in the graph in Figure 2, subjects 1,3and 6are described with the same properties {1,3,5,7}, Hernández-Illera et al. / iHDT++: Improving HDT for SPARQL Triple Pattern Resolution 5 Fig. 2. Organization of Triples component in HDT (note that only predicates and objects adjacency lists are preserved). Fig. 3. HDT++ Triples component. or subjects 4,5, and 7use the properties {1,2,4}. RDF-TRdetermines these predicate families and assigns them a unique identifier in [1,|F|]. In our example, there are three families: F1={1,3,5,7}, which describes subjects 1,3and 6;F2={4,5,6}, which describes subject 2; and F3={1,2,4}, which describes subjects 4,5, and 7. A new adjacency list, called Families, preserves the families in which each predicate is used. As shown in Figure 3, the first predicate is present in families {1,3}, predicate 2is only in family {3}, etc. Families also uses neigh to retrieve the list of families for a given predicate. The repetitions of the predicate families are even more explicit with the use of the predicate rdf:type. In these cases, it is quite likely that subjects of the same type are described using the same set of predicates. RDF-TRconsiders the existence of “typed” predicate families, i.e. families that declare some value for the predicate rdf:type, and enhances the definition of the family with the value(s) of this predicate. This decision avoids triples tagged with rdf:type to be explicitly encoded. Managing typed families requires an additional adjacency list structure: types, which preserves the type values of each family. Figure 3 illustrates this structure and encodes3that the first family is typed with the object 9. Finally, note that HDT++ 3In this case, the bitsequence implements a slightly different encoding to allow empty lists, as some families may not be typed. also maps rdf:type to the last predicate ID; in our example, it is identified using the ID |P|= 7. Subject-based transformation. Each subject can be now described by a predicate family, hence all subjects of the same family have the same connection structure. RDF-TRexploits this by grouping subjects of the same family, which are now locally re-encoded within their corresponding family. This decision requires an additional mapping structure (MapS) to translate the new local subject IDs to their corresponding counterparts. As shown in Figure 3, it is implemented as an adjacency list that arranges subject IDs per family; e.g. family 1is related to subjects 1,3, and 6, which correspond to local subjects 1,2and 3(for such family). The previous transformations allow triples to be serialized in the form of Subject-Family-Object trees, with the local ID objects (per predicate) and local ID subjects (per family). However, it is a flat representation in which each subject is connected to a single family. RDF-TRproposes a final transformation to obtain a bushy (and more compressible) encoding in the form Predicate-Family-Object. Each tree is now rooted by a predicate, which is connected to objects (in leaves) by the corresponding family. Subjects are implicitly encoded in this representation, thanks to the family-based grouping and the local subject IDs. The structure Ps is required to implement this encoding. As shown in Figure 3, it is a vector of |P|adjacency lists (one per predicate), called Psin which sequences Sopreserve local 6Hernández-Illera et al. / iHDT++: Improving HDT for SPARQL Triple Pattern Resolution object IDs and bitsequences Boencodes relationships between local objects and subjects, within the scope of each predicate. Ps provides the getObjects(p, pos) operation, which retrieves the list of objects starting in position pos for the predicate p(see [12] for additional details). Finally, note that the inner sequences of MapS and MapO are gap-encoded (with parameterizable samples) and then compressed using Elias-Delta [23]. The remaining adjacency lists are encoded using plain sequences and bitsequences. The experiments reported in [12] showed that HDT++ is faster than HDT for triple scanning (decompression), while it uses less than half the HDT space for more-structured datasets. However, HDT++ does not retain the HDT-FoQ retrieval capabilities, so it cannot be directly used to replace the current HDT-based infrastructure in query processors. 3. iHDT++ HDT++ ensures efficient data scan, i.e. it resolves the (???) TP. In contrast, subject-based and predicatebased TP can be resolved in a non-efficient manner, and object-based TPs are practically discarded (they might require a full scan). iHDT++ transforms HDT++ into a query processor for SPARQL TPs. We enhance the existing structures with additional information to ensure subject and predicate-based TPs to be efficiently resolved. In addition, a new index, iObjects, is proposed to resolve object-based TPs. 3.1. Additional Data Structures HDT++ uses adjacency lists to implement their components. These structures are optimized to obtain direct neighbors for a given vertex v, but are inefficient to retrieve the reverse neighbors of a v(i.e. vertices usuch that (u, v)∈E). However, reverse neighbor operations are needed to resolve SPARQL TPs, hence MapS,MapO, and Families must be enhanced with their transposed structures. Transposed Structures. MapO arranges object IDs by predicate, allowing local objects to be mapped to their original IDs. This operation is useful for decoding purposes, but is not enough for TPs resolution because triple patterns use global IDs instead. iHDT++ proposes to use the transposed of MapO (referred to as MapO’) to list the predicate(s) of each object (i.e. usually just one). MapO’ is implemented as an adjacency Fig. 4. Transposed structures of iHDT++. Fig. 5. Indexed Ps (iPs). Algorithm 1: getObjSubject(pred, fam, subj) 1posf←select1(iPs[pred].Bf, fam −1); 2rnk ←rank1(iPs[pred].Bo, posf); 3poss←1+ select1(iPs[pred].Bo, subj +rnk −1); 4return iPs.getObjects(pred, poss); list, encompassing a plain bitsequence and a plain sequence that uses log2(|P|)bits per ID. The previous reasoning also applies for MapS and Families. The transposed of these structures, MapS’ and Families’ respectively, are needed to support subject-based retrieval: MapS’ is used to obtain the ID of the family related to a given subject (the subject is referred by its global ID) and Families’ allows the predicate set of a given family to be efficiently retrieved. MapS’ is implemented as an ID array, as each subject is only related to a single family; i.e. MapS’[i] stores the ID of the family corresponding to the i−th subject. It uses log2(|F|)bits per ID. Families’ is implemented as an adjacency list, in which each ID is encoded using log2(|P|)bits. Figure 4 shows the resulting configuration of MapO’, MapS’, and Families’ for the previous example. Indexing Ps.The Ps structure encodes PredicateFamily-Object trees, but the limits of each family (within each predicate) are not explicitly delimited. This information is not needed for decoding purposes because the scan algorithm traverses Ps sequentially [12]. However, family limits must be explicitly encoded to allow random access. An additional bitse- Hernández-Illera et al. / iHDT++: Improving HDT for SPARQL Triple Pattern Resolution 7 Fig. 6. iObjects configuration. quence Bfis added on top of each adjacency list to mark the end of each family within the predicate. The resulting structure is called iPs. iPs enhances the getObject primitive to retrieve the objects related to a given (subject,predicate) pair within a given family. Algorithm 1 describes this operation, called getObjSubject, and Figure 5 illustrates the iPs configuration for our current example. For instance, if we are looking for the objects related to the third subject of the second family of P1,getObjSubject(1,2,3) finds that the corresponding list is encoded from poss= 7 and getObjects(1,7) = {5}. The iObjects Index. This structure enhances HDT++ for object-based queries, storing the positions in which each object occurrence is encoded in iPs. The special value 0is used to encode that a given object is only associated with predicate rdf:type. These objects have a special consideration, as explained below. iObjects is also implemented as an adjacency list, which concatenates object positions according to their global IDs; i.e. positions of O1are first encoded, then positions of O2, and so on. The positions of each object are internally organized in increasing order for each related predicate, and 1-bits mark the last object occurrence for a given predicate. The resulting iObjects for our example is illustrated in Figure 6 (we also show MapO’ for explanation purposes). For instance, O1is related to two predicates: P1and P4, as shown in MapO’. Thus, iObjects encodes two list of occurrences for O1, one for each predicate: L1,1={1}and L1,4={1,2,4}. To decode the corresponding triples, the adjacency lists of each predicate must be accessed in iPs, retrieving the corresponding positions; e.g. positions 1,2, and 4of iPs[4] encodes the (local) subject IDs of the triples that relate P4and O1. iObjects needs a secondary structure (iTypes) to manage the set of objects that are related to the predicate rdf:type. Note that, in Figure 6, S[15] = 0. Algorithm 2: pattern_SPO(subj,pred,obj) 1family ←MapS0[subj]; 2if pred < |P|then // pred is a regular predicate 3if adj(Families’, family, pred)6=−1then 4localo←adj(MapO, pred, obj); 5if localo6=−1then 6locals←adj(MapS, family, subj); 7idf←adj(Families, pred, family); 8O ←iPs.getObjSubject(pred, idf, locals); 9if bsearch(O, localo)6=−1then return true ; 10 else return false ; 11 end 12 else return false ; 13 end 14 else return false ; 15 end 16 else // pred is rdf:type 17 if adj(Types, family, obj)6=−1then return true ; 18 else return false ; 19 end It means that O9is related to rdf:type, but the related family is unknown. iTypes is composed of a bitsequence (Bt) that marks those objects related to rdf:type, and an adjacency list that contains the IDs of the families that are typed with the corresponding object. The corresponding iObjects configuration for our example is depicted in Figure 6 (bottom). Note that the bitsequence only sets the bits corresponding to O9and the adjacency list has a single element that encodes F1, because F1has the type O9. 3.2. Triple Pattern Resolution In this section, we explain how iHDT++ can resolve all SPARQL TPs, except for (???), which corresponds to the scan of the dataset and it is already provided by HDT++ [12]. Note that we assume that the bounded terms in queries are IDs (in the HDT Dictionary) that identify the corresponding subjects, predicates, or objects. 3.2.1. Access by Predicate The organization of iHDT++ promotes predicatebased operations, as it encodes Predicate-FamilyObject trees that can be efficiently traversed. Thus, besides (???), all TPs binding the predicate can exploit the iHDT++ organization. In the following, we present the algorithms to resolve (SPO),(SP?) and (?P?). Even though (?PO) could be also resolved, but its performance improves notably by accessing by the value of the object (see Section 3.2.3), as there are generally fewer triples associated to a particular object than to a given predicate [7]. 8Hernández-Illera et al. / iHDT++: Improving HDT for SPARQL Triple Pattern Resolution Algorithm 3: pattern_SP?(subj,pred) 1family ←MapS0[subj]; 2if pred < |P|then // pred is a regular predicate 3if adj(Families’, family, pred)6=−1then 4locals←adj(MapS, family, subj); 5idf←adj(Families, pred, family); 6O ←iPs.getObjSubject(pred, idf, locals); 7res ← ∅; 8for i←1to |O| do 9res ←res ∪neigh(MapO, pred)[O[i]]; 10 end 11 return res; 12 end 13 else return false ; 14 end 15 else // pred is rdf:type 16 return neigh(Types, family); 17 end (SPO) This TP checks the existence of the triple (subj,pred,obj) in the RDF dataset, as shown in Algorithm 2. First, the family of the subject is retrieved (line 1), and then the predicate is checked (line 2) to determine if it is a regular predicate or it is rdf:type. The latter case is easily resolved because the requested triple exists in the dataset only if family and obj are related in Types (line 17). The former case, which involves a regular predicate, requires a multiple check: we verify that family includes pred (line 3), and then obtain the local ID of obj within pred; if pred and obj are not related (i.e. ID = -1), the triple does not exist (line 12). The following step maps subj to its local ID within its family (line 6), and then the position of family in pred is retrieved (line 7). Line 8 gets the set of objects related to (subj,pred) and then obj is binary searched in O(line 9); if localo∈ O, the triple exists in the dataset. (SP?) This TP retrieves all objects associated with the pair (subj,pred), as shown in Algorithm 3. It first obtains the family of subj and then evaluates pred, as in the previous pattern. If the TP asks for rdf:type, the requested objects are the direct neighbors of family in Types (line 16). Looking for the objects associated to a normal predicate also requires checking that family includes pred, obtaining the local ID of subj, the position of family in pred, retrieving the corresponding objects using getObjSubject (line 6) and finally mapping them to their original counterparts (lines 8-10). (?P?) This TP returns all the pairs (subject,object) described by pred, which was poorly resolved by HDT-FoQ. Algorithm 4 illustrates the resolution with iHDT++. For a normal predicate (lines 2-18), the algorithm proceeds as the decompression process [12], but for a concrete predicate. First, the families includAlgorithm 4: pattern_?P?(pred) 1res ← ∅; 2if pred < |P|then // pred is a regular predicate 3ptrSubj ←1; 4F ← neigh(Families, pred); 5for i←1to |F| do 6family ← F[i]; 7S ← neigh(MapS, family); 8for j←1to |S| do 9subject ← S[j]; 10 O ← iPs.getObjects(predicate, ptrSubject); 11 ptrSubj ←ptrSubj + 1; 12 for k←1to |O| do 13 object ←neigh(MapO, pred)[O[k]]; 14 res ←res ∪(subject, object); 15 end 16 end 17 end 18 end 19 else // pred is rdf:type 20 for i←1to |F|do 21 O ← neigh(Types, i); 22 if O 6=∅then 23 S ← neigh(MapS, i); 24 for i←1to |S| do 25 for j←1to |O| do 26 res ←res ∪(S[i],O[j]); 27 end 28 end 29 end 30 end 31 end 32 return res; ing pred are retrieved (line 4) and iterated (lines 5-17). For each family, its related subjects are obtained (line 7) and also iterated (lines 8-16). The objects related to each pair (subject, pred) are obtained (line 10) and then mapped to their global IDs (lines 12-15), as in the previous algorithms. The process for rdf:type also requires a nested loop algorithm. In this case, the algorithm iterates over all families and, for each one, it retrieves its type values (line 21). If Ois not empty (line 22), the family is typed and its related subjects are retrieved from MapS. Finally, we iterate over Sand Oto return all the pair combinations from each set. 3.2.2. Access by Subject As opposed to the original HDT, iHDT++ resolves only a single TP accessing by subject: (S??). (S??) This TP looks for all pairs (predicate, object) describing a given subject (subj). As shown in Algorithm 5, subj is used to retrieve its related family, which is then used to obtain the corresponding predicates (lines (2-3). The set of predicates is then iterated to retrieve all objects related to subj and each predicate. It is easily resolved by calling pattern_SP? (line 5), and the returned objects are appended to the result set (lines 6-8). Finally, we check whether the family Hernández-Illera et al. / iHDT++: Improving HDT for SPARQL Triple Pattern Resolution 9 Algorithm 5: pattern_S??(subj) 1res ← ∅; 2family ←MapS’[subj]; 3P ← neigh(Families’,family); 4for i←1to |P| do 5O ← pattern_SP?(subj, P [i]); 6for j←1to |O| do 7res ←res ∪(P[i], O[j]); 8end 9end 10 O ← neigh(Types,family); 11 if O 6=∅then 12 for i←1to |O| do 13 res ←res ∪(|P|, O[j]); 14 end 15 end 16 return res; Algorithm 6: pattern_S?O(subj,obj) 1res ← ∅; 2P ← neigh(MapO’,obj); 3for i←1to |P| do 4if pattern_SPO(subj, P[i], obj)then 5res ←res ∪P[i]; 6end 7end 8return res; is typed, to add the corresponding pairs (rdf:type, value)to the result set. In line 10, the possible type values of the family are retrieved from Types; if there exist, they are added to the final result set (note that the ID |P|, in line 13, refers to the predicate rdf:type). 3.2.3. Access by Object iHDT++ provides efficient object-based search via MapO’ and iObjects, resolving the TPs (S?O), (??O), and (?PO). (S?O) This TP retrieves all predicates that label the pair (subj,obj), illustrated in Algorithm 6. It uses MapO’ to get the predicates related to obj (line 2), and then invokes pattern_SPO to check the combinations (subj, P[i], obj (line 3), for each retrieved predicate P[i]. If the triple exists, P[i]is added to the result set. (?PO) This TP retrieves all subjects characterized by the pair (pred,obj). It distinguishes between normal predicates and rdf:type. The process for normal predicates first checks if obj is related to pred (lines 3-4), and then retrieves the position in which these occurrences are encoded in iObjects (lines 5-6). For each occurrence in Occs, we navigate the adjacency list of pred in iPs to finally decode the corresponding subject, which is mapped to its original ID (line 11). If pred is rdf:type, we also check if obj is related to such predicate. In this case, we retrieve the families Algorithm 7: pattern_?PO(pred,obj) 1res ← ∅; 2if pred < |P|then // pred is a regular predicate 3posp←adj(MapO’, obj, pred); 4if posp6=−1then 5pos ←posp+select1(MapO’.B, obj −1); 6Occs ←neigh(iObjects,pos); 7for i←1to |Occs|do 8idf←1+rank1(iPs[pred].Bf,Occs[i]−1); 9family ←neigh(Families, pred)[idf]; 10 locals← Occs[i]− select1(iPs[pred].Bf, idf−1); 11 res ←res ∪neigh(MapS, family)[locals]; 12 end 13 end 14 end 15 else // pred is rdf:type 16 if access1(iTypes.Bt, obj)=1then 17 object ←rank1(iTypes.Bt, obj); 18 F ← neigh(iTypes, object); 19 for i←1to |F| do 20 S ← neigh(MapS,F[i]) ; 21 for j←1to |S| do 22 res ←res ∪ S[j]; 23 end 24 end 25 end 26 end 27 return res; Algorithm 8: pattern_??O(obj) 1res ← ∅; 2P ← neigh(MapO’,obj); 3for i←1to |P| do 4S ← pattern_?PO(P[i], obj); 5for j←1to |S| do 6res ←res ∪(S[j],P[i]); 7end 8end typed by obj from iTypes (line 18). For each family, we obtain its corresponding subjects, which are added to the final result set. (??O) This TP retrieves all the (subject,predicate) pairs described with the given obj value. The resolution is illustrated in Algorithm 8. It uses MapO’ to retrieve all predicates P[i]related to obj. Then the pattern_?PO is invoked for each one, and the returned subjects, and the corresponding P[i], are added to the result set. 4. Evaluation This section presents a comprehensive evaluation that compares iHDT++ to its predecessors, HDT-FoQ [15] and its Community variant. Our goal is to show that iHDT++ can replace the existing HDT-based deployments by a more lightweight approach, without Bibliography [1] S. ´ Alvarez-Garc´ıa, N. Brisaboa, J.D. Fern´andez, M.A. Mart´ınez-Prieto, and G. Navarro. Compressed Vertical Partitioning for Efficient RDF Management. Knowledge and Information Systems, 44(2):439–474, 2014. [2] M. Atre, V. Chaoji, M.J. Zaki, and J.A. Hendler. Matrix ”Bit” Loaded: A Scalable Lightweight Join Query Processor for RDF Data. In Proceedings of the International Conference on World Wide Web (WWW), pages 41–50, 2010. [3] S. Auer, C. Bizer, G. Kobilarov, J. Lehmann, R. Cyganiak, and Z. Ives. DBpedia: A Nucleus for a Web of Open Data. In The Semantic Web, pages 722–735. Springer Berlin Heidelberg, 2007. [4] T. Baker and E. Prud’hommeaux. Shape Expressions (ShEx) Primer. Draft Community Group Report 14 July 2017, 2017. [5] W. Beek, L. Rietveld, H.R. Bazoobandi, J. Wielemaker, and S. Schlobach. LOD Laundromat: A Uniform Way of Publishing Other People’s Dirty Data. In The Semantic Web – ISWC 2014, pages 213– 228. Springer International Publishing, 2014. [6] T. Berners-Lee. Linked Data. URL https://www.w3.org/DesignIssues/LinkedData.html, 2006. [7] T. Berners-Lee, M. Fischetti, and M.L. Dertouzos. Weaving the Web: The Original Design and Ultimate Destiny of the World Wide Web by Its Inventor. 1st edition, 1999. [8] K. Bok, J. Han, J. Lim, and J. Yoo. Provenance compression scheme based on graph patterns for large RDF documents. The Journal of Supercomputing, pages 1–23, 2019. 87 [9] D. Brickley and Guha R.V. RDF Schema 1.1. W3C Recommendation, 2014. https://www.w3.org/TR/r2rml/. [10] N. Brisaboa, A. Cerdeira-Pena, A. Farina, and G. Navarro. A Compact RDF Store Using Suffix Arrays. In Proc. of SPIRE, pages 103–115, 2015. [11] N. Brisaboa, S. Ladra, and G. Navarro. Compact Representation of Web Graphs with Extended Functionality. Information Systems, 39(1):152– 174, 2014. [12] N.R. Brisaboa, A. Cerdeira-Pena, G. de Bernardo, and A. Fari˜na. Revisiting compact RDF stores based on k2-trees. In Proceedings of the Data Compression Conference (DCC 2020), pages 123–132, 2020. [13] G. Carothers and A. Seabourne. RDF 1.1 N-Triples: A linebased syntax for an RDF graph. W3C Recommendation, 2014. https://www.w3.org/TR/n-triples/. [14] D. Connolly. Gleaning Resource Descriptions from Dialects of Languages (GRDDL). W3C Recommendation, 2007. https://www.w3.org/TR/grddl/. [15] D. Connolly. R2RML: RDB to RDF Mapping Language. W3C Recommendation, 2012. https://www.w3.org/TR/r2rml/. [16] N.L. Elzein, M.A. Majid, I.B. Targio Hashem, I. Yaqoob, F.A. Alaba, and M. Imran. Managing Big RDF Data in Clouds: Challenges, Opportunities, and Solutions. Sustainable Cities and Society, pages 375–386, 2018. [17] J.D. Fern´andez, W. Beek, M.A. Mart´ınez-Prieto, and M. Arias. LODa-lot: A Queryable Dump of the LOD Cloud. In The Semantic Web – ISWC 2017, pages 75–83. Springer International Publishing, 2017. [18] J.D. Fern´andez, M.A. Mart´ınez-Prieto, C. Guti´errez, and A. Polleres. Binary RDF Representation for Publication and Exchange (HDT). W3C Member Submission, 2011. https://www.w3.org/Submission/HDT/. [19] J.D. Fern´andez, M.A. Mart´ınez-Prieto, C. Guti´errez, A. Polleres, and M. Arias. Binary RDF Representation for Publication and Exchange. Journal of Web Semantics, 19:22–41, 2013. 88 [20] Roberto Grossi, Ankur Gupta, and Jeffrey Scott Vitter. High-order entropy-compressed text indexes. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’03, page 841–850. Society for Industrial and Applied Mathematics, 2003. [21] C. Guti´errez, C. Hurtado, A.O. Mendelzon, and J. P´erez. Foundations of Semantic Web Databases. Journal of Computer and System Sciences, 77:520–541, 2011. [22] A. Hern´andez-Illera, M.A. Mart´ınez-Prieto, and J.D. Fern´andez. Serializing RDF in Compressed Space. In Proceedings of the Data Compression Conference (DCC 2015), pages 363–372, 2015. [23] A. Hern´andez-Illera, M.A. Mart´ınez-Prieto, and J.D. Fern´andez. iHDT++: un Auto´ındice Sem´antico para la Resoluci´on de Patrones de Consulta SPARQL. In Proceedings of Jornadas de Ingenier´ıa del Software y Bases de Datos (JISBD), 2017. [24] A. Hern´andez-Illera, M.A. Mart´ınez-Prieto, and J.D. Fern´andez. RDFTr: Exploiting Structural Redundancies to boost RDF Compression. Information Sciences, 508:234–259, 2020. [25] A. Hern´andez-Illera, M.A. Mart´ınez-Prieto, J.D. Fern´andez, and A. Fari˜na. iHDT++: Improving HDT for SPARQL Triple Pattern Resolution. In Proceedings of the 7th Int Symp On Language and Knowledge Engineering (LKE), 2019. [26] A. Hern´andez-Illera, M.A. Mart´ınez-Prieto, J.D. Fern´andez, and A. Fari˜na. iHDT++: Improving HDT for SPARQL Triple Pattern Resolution. Journal of Intelligent & Fuzzy Systems, 2020. http://doi.org/10.3233/JIFS-179888. [27] L. Iannone, I. Palmisano, and D. Redavid. Optimizing RDF Storage Removing Redundancies: An Algorithm. In Procedings of the International Conference on Industrial and Engineering Applications of Artificial Intelligence and Expert Systems (IEA/AIE), pages 732–742, 2005. [28] A. Joshi, P. Hitzler, and G. Dong. Logical Linked Data Compression. In Proceedings of the Extended Semantic Web Conference (ESWC), pages 170–184, 2013. [29] F. Karim, M.E. Vidal, and S. Auer. Compacting Frequent Star Patterns in RDF Graphs. ArXiv, abs/2003.05238, 2020. 89 [30] H. Knublauch and D. Kontokostas. Shapes constraint language (SHACL). W3C Recommendation, 2017. [31] P. Maillot and C. Bobed. Measuring structural similarity between rdf graphs. In Proceedings of the Symposium on Applied Computing (SAC), pages 1960–1967. ACM, 2018. [32] F. Manola and R. Miller. RDF Primer. W3C Recommendation, 2004. https://www.w3.org/TR/rdf-primer/. [33] M.A. Mart´ınez-Prieto, M. Arias, and J.D. Fern´andez. Exchange and Consumption of Huge RDF Data. In Proc. of ESWC, pages 437–452, 2012. [34] M.A. Mart´ınez-Prieto, J.D. Fern´andez, A. Hern´andez-Illera, and C. Guti´errez. RDF Compression. In Encyclopedia of Big Data Technologies. Springer International Publishing, 2018. [35] M.A. Mart´ınez-Prieto, N. Brisaboa, R. C´anovas, F. Claude, and G. Navarro. Practical compressed string dictionaries. Information Systems, 56:73 – 108, 2016. [36] M.A. Mart´ınez-Prieto, C.E. Cuesta, M. Arias, and J.D. Fern´andez. The solid architecture for real-time management of big semantic data. Future Generation Computer Systems, 47, 10 2014. [37] M.A. Mart´ınez-Prieto, J.D. Fern´andez, and R. C´anovas. Compression of RDF Dictionaries. In Proceedings of the 27th Annual ACM Symposium on Applied Computing, SAC ’12, page 340–347. Association for Computing Machinery, 2012. [38] J.P. McCrae, A. Abele, P. Buitelaar, R. Cyganiak, A. Jentzsch, V. Andryushechkin, and J. Debattista. The Linked Open Data Cloud. URL https://lod-cloud.net/, 2019. [39] M. Meier. Towards Rule-Based Minimization of RDF Graphs under Constraints. In Procedings of the International Conference on Web Reasoning and Rule Systems (RR), pages 89–103, 2008. [40] J.Z. Pan, J.M. G´omez-P´erez, Y. Ren, H. Wu, W. Haofen, and M. Zhu. Graph Pattern Based RDF Data Compression. In Proceedings of the Joint International Conference om Semantic Technology (JIST), pages 239–256, 2015. 90 [41] J.Z. Pan, J.M. G´omez-P´erez, Y. Ren, H. Wu, and M. Zhu. SSP: Compressing RDF data by Summarisation, Serialisation and Predictive Encoding. Technical report, 2014. Available at http://www.kdrive-project.eu/wp-content/uploads/2014/06/WP3-TR2-2014 SSP.pdf. [42] H. Pascal, M. Kr¨otzsch, B. Parsia, Patel-Schneider P.F., and Rudolph S. OWL 2 Web Ontology Language Primer. W3C Recommendation, 2012. https://www.w3.org/TR/2012/REC-owl2-primer-20121211/. [43] S. Pemberton. XHTML 1.0 The Extensible HyperText Markup Language. W3C Recommendation, 2000. https://www.w3.org/TR/xhtml1. [44] G.E. Pibiri, R. Perego, and R. Venturini. Compressed Indexes for Fast Search of Semantic Data. IEEE Transactions on Knowledge and Data Engineering, 2020. [45] A. Polleres, A. Hogan, R. Delbru, and J. Umbrich. RDFS and OWL Reasoning for Linked Data, pages 91–149. Springer Berlin Heidelberg, 2013. [46] E. Prud’hommeaux and G. Carothers. RDF 1.1 Turtle: Terse RDF Triple Language. W3C Recommendation, 2014. https://www.w3.org/TR/turtle/. [47] E. Prud’hommeaux and A. Seaborne. SPARQL Query Language for RDF. W3C Recommendation, 2008. https://www.w3.org/TR/json-ld/. [48] K. Sadakane. New Text Indexing Functionalities of the Compressed Suffix Arrays. Journal of Algorithms, 48(2):294–313, 2003. [49] Sherif Sakr and Albert Zomaya. Encyclopedia of big data technologies. Springer Publishing Company, Incorporated, 2019. [50] Kellogg G. Sporny, M. and Lanthaler M. JSON-LD 1.0: A JSONbased Serialization for Linked Data. W3C Recommendation, 2014. https://www.w3.org/TR/json-ld/. [51] R. Ticona-Herrera, R. Tekli, J. Chbeir, S. Laborie, I. Dongo, and R. Guzman. Toward RDF Normalization. In Proceedings of the International Conference on Conceptual Modeling (ER), pages 261—-275, 2015. [52] G. Venkataraman and P. Sreenivasa Kumar. Horn-rule based compression technique for RDF data. In Proceedings of the Annual ACM Symposium on Applied Computing (SAC), pages 396–401, 2015. 91 [53] R. Verborgh, M. Vander Sande, O. Hartig, J. Van Herwegen, L. De Vocht, B. De Meester, G. Haesendonck, and P. Colpaert. Triple Pattern Fragments: A low-cost knowledge graph interface for the Web. Journal of Web Semantics, 37-38:184 – 206, 2016. 92 Appendix A Using RDF-Tr and iHDT++ This appendix presents the iHDT++ library, which contains the practical implementation of the theoretical work of the research developed over the last few years and now compiled in this thesis. The library is free software under the terms of the GNU Lesser General Public License, and it is available at GitHub1. This has a special relevance for the scientific community, since it allows the results of the experiments contained in the papers that are part of the thesis to be reproduced. This project makes use of two already existing libraries: HDT and SDSL. On the one hand, HDT is the first and most used binary representation of RDF, so it was taken as a starting point to apply our reorganization and self-indexing processes, preserving and reusing the dictionary that HDT implements. HDT serializes the triple IDs succinctly using the Compressed Data Structure Library (libcds)2, whose development has been discontinued despite its effectiveness in compression. That is the main reason why we use the Succinct Data Structure Library (SDSL)3, which must be installed to use the compact data structures (and their operations) provided and used by iHDT++. The source code is written in C++ and is available online in a public repository, along with the latest available HDT version. The main folders of the project are: libsdsl, which contains the installation of the SDSL library; hdtpp contains the core of our work, which includes the data structures and methods necessary to reorganize triples and access information in compressed space; finally the tools folder provides simple utilities to perform these operations. Below there is a representation of the project folder tree where the mentioned directories are located. 1https://github.com/antonioillera/iHDTpp-src 2https://github.com/fclaude/libcds2 3https://github.com/simongog/sdsl-lite 93 iHDTpp-src libsdsl libhdt src hdtpp tools By means of an example, we can see the necessary steps to create a representation in HDT++ from a data collection (e.g., dblp) serialized in HDT to later access its data. Given an HDT dataset, hdt2hdtpp applies RDF-Tr and recompresses the HDT file into HDT++ (see Code 1). $iHDTpp−src/libhdt/tools/hdt2hdtpp dblp.hdt dblp.hdtpp Bash Code 1: Applying RDF-Tr on an HDT file. iHDT++ indexes allow data in a compressed HDT++ file to be accessed. The hdtppSearch utility implements a simple interface to access the dataset by SPARQL Triple Patterns. A simple use of this tool is shown in Code 2, where we ask for all triples. Indexes are created/loaded in execution time. $iHDTpp−src/libhdt/tools/hdtppSearch dblp.hdtpp "? ? ?" Bash Code 2: Applying RDF-Tr on an HDT file. On the other hand, hdtpp2rdf decompresses the HDT++ file, obtaining the RDF version of the dataset (see Code 3). $iHDTpp−src/libhdt/tools/hdtpp2rdf dblp.hdtpp dblp.rdf Bash Code 3: Decompressing an HDT++ file. 94