## 3 Hybrid Index System
### Extended Multidimensional Histogram  
We adapt the MDH technique for LOD storage and searching. Our histogram, called MDH*, aims to support efficient join query processing without significant storage demand. To achieve scalable query processing, we design a compact storage structure and minimize the number of indexes used in the query execution. As a running example, we extract sample data from a small portion of the RDF file. Figure 3 shows these sample data. In MDH*, we adopt a dictionary compression method [13] to reduce the redundancy of long common URI prefixes. This method divides a URI into prefix and suffix parts using the last separator \"/\". Moreover, instead of storing the prefix and suffix parts as a string, all strings are replaced with unique numerical codes. For instance, [PERSON] would be represented by a URL such as \"[[http://dbpedia.org/person/[PERSON]](http://dbpedia.org/person/[PERSON])]([http://dbpedia.org/person/[PERSON]](http://dbpedia.org/person/[PERSON]))\" (accessed on 17 January 2021) in a real-world RDF graph; storing compressed numbers instead of this string can save large spaces. Here, we provide a brief introduction of the MDH concept [5]. The first step in building the MDH involves transforming the RDF triples into points in a three-dimensional space by applying hash functions (e.g., hashCode() function in Java) to the individual components of the RDF triples. Next, the three-dimensional space is partitioned into disjoint regions, each defining a so-called bucket. Each bucket contains entries of all URIs whose data include RDF triples in the corresponding region. Given a triple pattern for an RDF query, a lookup entails computing the corresponding triple points by applying the same hash function and retrieving buckets responsible for the obtained triple points. Any URI relevant to the triple pattern can only be contained in buckets. Similarly, the first step of building the MDH* involves transforming the RDF triples into compressed numbers using Java's hashCode() function. In this case, these numbers are points in the \(n\)-dimensional data space, whose coordinates correspond to three-dimensional cubes for (s, p, o). The coordinates are inserted sequentially and aggregated into regions. Each region contains a list of these compressed triple numbers. The triple numbers in the list are added with two special count frequencies, rather than ordinary triple numbers, to improve the join query performance. The count frequencies specify \(\alpha\) and \(\beta\), where \(\alpha\) indicates the number of subjects in which \(o\) occurs as subjects in the LOD cloud; similarly, \(\beta\) indicates the number of objects in which \(s\) occurs as objects. We observe that a number of triples in the LOD cloud are used as subjects of one triple and objects of another triple. [PERSON] et al. [13] demonstrated that more than 57% of LOD subjects are also objects. Figure 3: Sample data used for the running example. **Definition 1:**_Let (t, f) be an extended RDF tuple with frequency f, where t is the compressed triple numbers (x, y, z) and f is the count frequency (\(\alpha\), \(\beta\)). Then, the extended RDF tuple ((x, y, z), (\(\alpha\), \(\beta\))) equals the quintuple (x, y, z, \(\alpha\), \(\beta\))._  
Considering the running example presented in Figure 3, the converted compression numbers are represented in Figure 3(a). We can then obtain the compressed triple numbers for each RDF triple (e.g., (Smith, knows, Lucy) \(\rightarrow\) (11, 12, 13)). The count frequencies are initialized (0, 0) if \(o\) and \(s\) have not appeared in \(s\) and \(o\), respectively. Otherwise, when \(o\) or \(s\) appears in \(s\) or \(o\), respectively, the values are incremented by 1. Figure 3(b) shows the completed extended RDF tuples in our running example after adding the count frequencies. Because calculating the count frequencies would be expensive, counting and inserting the frequencies can be performed as batch processing after compressed triple numbers are established.