In the field of life sciences, numerous databases are publicly available in the form of graph structures called RDF (Resource Description Framework). Each node in these graphs is linked to a unique URI representing entities such as genes and proteins. Consequently, these databases contain vast amounts of graph-structured data with numerous URIs. By establishing links to URIs in other databases, these databases become interconnected through links, ultimately forming a massive knowledge graph.
CEUR ceur-ws.org
In the life science field, a large number of heterogeneous data is produced. To facilitate their integration, RDF (Resource Description Framework) is frequently employed, These RDF datasets exhibit graph structures, with URIs serving as universal identifiers. The utilization of large RDF datasets necessitates the development of an eficient method for storing and retrieving a comprehensive set of URIs that appear within these datasets.
A previous study by Martínez-Prieto et al. [
Front Coding is a technique employed to compress a set of sorted strings by comparing each string with its preceding string and encoding the shared substring to its length. To facilitate eficient location, the strings are subdivided into subsets, known as buckets. In this study, we employed a bucket size of 128 for Front Coding. Trie, on the other hand, is a tree structure designed for locating a specific string within a set of strings. In a Trie, each node corresponds to a character in a string, and each path in the Trie corresponds to a string within the set. These two methods are often used for locating a string from a set of strings.
However, we observed a distinctive feature among the URIs present in life-science RDF datasets: they tend to exhibit a limited number of prefixes and an abundance of sufixes. Based on this observation, we devised an innovative approach for URI location within a set of URIs. We propose breaking down URIs by ”/” delimiter, with each substring corresponding to a node in a tree structure. As depicted in Fig. 1, the number of leaves in this tree can sometimes be substantial. To address this, we divided the search method into two phases. In the first phase, we search for the URI from the root to a leaf, akin to a Trie. If a node possesses a significant number of children, we employ a secondary method in the second phase. In this context, we present two distinct methods for the second phase: the first (Method 1) involves binary search for the children, while the second method (Method 2) entails constructing Tries for each child node.
We utilized four life-science RDF datasets sourced from the RDF portal [
It’s worth noting that the tree structures utilized in both the Trie and our proposed methods
are implemented using LOUDS (Level-Order Unary Degree Sequence) methodology [
Based on the findings of our computational experiments, we can deduce that the choice of method should be contingent on specific application requirements. If expediting the time of URI location is of paramount importance, particularly in cases where prefix finding is unnecessary, Front Coding emerges as the preferred method. Conversely, when there is a demand for prefix ifnding and a preference for a lower compression ratio, Method 2 should be the method of choice. For scenarios where both prefix finding and the time of URI location are top priorities, Method 1 ofers the most suitable solution.
As delineated in Section 2, URIs commonly encountered in life science datasets exhibit a distinctive pattern of limited prefix variety and extensive sufix diversity. Consequently, our proposed methods are designed with a dual-phase approach that focuses on traversing paths corresponding to the strings from the prefix perspective. In instances where a node has a substantial number of children, Method 1 resorts to binary search to locate the children, refraining from compressing the strings corresponding to them. This non-compression strategy may result in a relatively lower compression ratio. In contrast, Method 2 takes a diferent approach, constructing a Trie for each node with a large number of children, efectively compressing the strings related to these children, and consequently yielding the smallest size of compressed URIs.
In the context of this poster, we employed LOUDS for implementing tree structures. However, it is worth noting that the double array implementation of Trie is recognized for its speed, even though it entails larger compression sizes compared to LOUDS. An important avenue for future exploration remains a comparative analysis with Trie utilizing a double array implementation.
This work was supported by ROIS-DS-JOINT 2020 and 2021 from Research Organization of Information and Systems (ROIS) and by JSPS KAKENHI grant number 21K12148.