A Comparative Study on Storing and Retrieval of URIs
for Life Sciences Databases
Atsuko Yamaguchi1,∗,† , Yasunori Yamamoto2
13

Tokyo City University, Setagaya, Tokyo, Japan
Database Center for Life Science, Kashiwa, Chiba, Japan

Abstract
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 amountsof 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.
As a result, it is essential to develop a foundational infrastructure for storing and searching asignificant number of URIs from life science data in this vast knowledge graph, utilizing database IDsand keywords. Presently, Front Coding is commonly employed for URI compression, but it suffers froma limitation in its inability to perform prefix matching searches. Trie is frequently used as an alternative
approach capable of retrieving prefixes. This study assess the compression ratio and search efficiency bycomparing the utilization of Front Coding, Trie, and our proposed methods. The evaluation is conductedusing a dataset of URIs extracted from life-science RDF datasets.

Keywords
Semantic Web, Resource Description Framework, URI, Information retreival

1. Introduction
In the life science field, a large number of heterogeneous data is produced. To facilitate theirintegration, 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 efficient method for storing and retrieving acomprehensive set of URIs that appear within these datasets.
A previous study by Martínez-Prieto et al. [1] delved into a comparative analysis of Hashing,
Front Coding, and FM-index, using dictionaries extracted from RDF datasets, focusing on URIs
and literals. They also introduced a method capable of swiftly locating strings within the dataset,achieving compression ratios of 22% to 66%. However, it’s noteworthy that their investigation
did not explore the potential of Trie, a technique with the capability to compress sets of strings
and retrieve not only the strings themselves but also their prefixes. Efficient federated searchhinges on the ability to identify servers offering datasets with specific prefixes in an efficientIJCKG 2023
Corresponding author.
Envelope-Open atsuko@tcu.ac.jp (A. Yamaguchi); yy@dbcls.rois.ac.jp (Y. Yamamoto)
Orcid 0000-0001-7538-5337 (A. Yamaguchi); 0000-0002-6943-6887 (Y. Yamamoto)∗© 2023 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
CEUR

Workshop
Proceedings

http://ceur-ws.org
ISSN 1613-0073

CEUR Workshop Proceedings (CEUR-WS.org)

manner. In this poster, we undertake a comparative study of Front Coding, Trie, and two novel
methods we propose. Our assessment is based on the average time required for locating, as
well as the compression ratio achieved by these methods.

2. Computational Experiment
Front Coding is a technique employed to compress a set of sorted strings by comparing eachstring with its preceding string and encoding the shared substring to its length. To facilitate
efficient location, the strings are subdivided into subsets, known as buckets. In this study, weemployed 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 suffixes. Basedon 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 besubstantial. 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, wepresent two distinct methods for the second phase: the first (Method 1) involves binary searchfor the children, while the second method (Method 2) entails constructing Tries for each childnode.

Figure 1: A typical exemple of URIs in a life science RDF dataset. While there is a single pathcorresponding to the string from the root to the ”refex” node, there are 4,430,897 leaves.

We utilized four life-science RDF datasets sourced from the RDF portal [2]. Due to variationsin the magnitude of URIs, four datasets were chosen. Table 1 provides an overview of thesedatasets, including their names, the count of URIs, and the size of the URI lists, with Quanto
being the smallest and KERO the largest. For the four datasets, it has been observed that typicalstructures of life science RDF URIs exhibit an explosive increase in the number of children froma certain depth.
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 [3]. This
choice of implementation is made due to its smaller space usage in comparison to other methods,
such as the double array. In our comparative analysis, we evaluated the performance of FrontTable 1Four datasets used for computational experiment
Name
Quanto
jPOST
RefEx
KERO

The count of URIs
1 995 998
11 412 967
19 828 641
290 338 001

The size (byte)
113 026 882
510 998 241
832 801 751
19 051 677 994

Coding, Trie, and our two methods (Method 1 and Method 2) using the RDF datasets. We
focused on assessing the compression ratio and the average time required for URI location. To
calculate the average time for URI location, we randomly selected 100 samples from the URI lists
for each dataset. All of the methods were implemented in C++. The computational experiments
were conducted on an Ubuntu 20.04.4 machine equipped with an Intel(R) Xeon(R) 2.40GHz CPU
and 200GB of memory.

3. Result
Table 2 presents the compressed sizes and compression ratios. The compressed sizes encompass
the necessary indexes for efficient location in the case of Trie and our methods. Notably, among
the four methods evaluated, both Trie and Method 2 exhibit superior performance, with Method
1 showing the least favorable results, albeit achieving compression ratios ranging from 0.31 to
0.37. Table 3 illustrates the average time required for URI location based on 100 trials. Front
Coding emerges as the top performer, closely followed by Method 1. While the compression
ratios of Trie and Method 2 are remarkably similar, Method 2 stands out as being two to threetimes faster than Trie.
Table 2Compressed size and compression ratio
Name
Original(bit)Front Coding
Trie
Method 1
Method 2

Quanto904 215 056
174 363 760(0.1928)
172 591 599(0.1908)285 735 820(0.3160)
172 591 344(0.1908)

jPOST
4 087 985 928
328 912 984(0.08045)
147 453 553(0.03606)
1 443 548 986(0.3531)
147 452 340(0.03606)

RefEx
6 662 414 008
541 609 480(0.08129)
220 324 169(0.03306)
2 103 835 010(0.3157)
222 547 974(0.03340)

KERO
152 413 423 952
11 110 721 176(0.07289)
6 738 005 419(0.04420)
57 241 426 238(0.3755)
6 738 004 412(0.04420)

4. Discussion and Conclusion
Based on the findings of our computational experiments, we can deduce that the choice ofmethod should be contingent on specific application requirements. If expediting the time of URI

Table 3
The average time (µs) to locate.
Name
Front Coding
Trie
Method1
Method2

Quanto
4.37
61.91
5.03
21.59

jPOST
4.26
56.05
4.66
18.41

RefEx
4.21
38.99
5.70
10.16

KERO
7.57
125.7011.32
72.48

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
finding and a preference for a lower compression ratio, Method 2 should be the method ofchoice. For scenarios where both prefix finding and the time of URI location are top priorities,
Method 1 offers 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 suffix diversity. Consequently, ourproposed 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 different approach,constructing a Trie for each node with a large number of children, effectively compressing thestrings related to these children, and consequently yielding the smallest size of compressedURIs.
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, eventhough 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.

5. Acknowledgments
This work was supported by ROIS-DS-JOINT 2020 and 2021 from Research Organization ofInformation and Systems (ROIS) and by JSPS KAKENHI grant number 21K12148.

References[1] M. A. Martínez-Prieto, J. D. Fernández, R. Cánovas, Compression of rdf dictionaries, in:Proceedings of the 27th Annual ACM Symposium on Applied Computing, SAC ’12, 2012,
pp. 340–347. doi:10.1145/2245276.2245343 .
[2] S. Kawashima, T. Katayama, H. Hatanaka, T. Kushida, T. Takagi, NBDC RDF portal: acomprehensive repository for semantic data in life sciences, Database 2018 (2018). doi:10.
1093/database/bay123 .
[3] G. Jacobson, Space-efficient static trees and graphs, in: Proceedings of the 30th FOCS,FOCS 1989, 1989, pp. 549–554.