## 3 Hybrid Index System
### Two-Step Index Structure  
The success of the MDH* method depends on its ability to rapidly narrow down a set of relevant resources that are affected by the SPARQL queries. To decide which resources are relevant for a particular query, we need an efficient index structure that can organize the set of resources. A number of index structures for LOD have been proposed, including QTree, R-tree, \(k\)-d tree, and SameAsPrefixIndex. However, these structures are deemed unsuitable for organizing LOD datasets. Because of rough approximation, the candidate results contain large numbers of false hits that do not fulfill the query condition. All candidates must be transmitted into the refinement processing, even if they contain false hits. The refinement processing in the main memory is expensive, particularly if the  
Figure 4: Converted compression numbers and extended resource description framework (RDF) tuples. Figure 5: Extended RDF tuples in the three-dimensional MDH*. number of candidates is large, because time-consuming internet access is required for many unreliable resources. In this section, we do not aim to discuss in detail which index structure is most suitable for organizing LOD datasets. Instead, we propose an extension of the existing index structure. Because the cost of developing a new index structure can be more expensive than the cost of simply extending an existing one, adding new features to the existing index structure is an excellent alternative. We select 3D R*-tree [27] for our index structure. R*-tree, the most popular variant of R-tree, is originally a multidimensional index structure for spatial data. Figure 6 depicts our two-step index structure. This figure is distinguished into two parts. The first level indicates the multidimensional index structure for organizing MDH*, which is a straightforward modification of the 3D R*-tree. The second level shows a set of \(k\)-d trees, which are used for refinement processing. Using this two-phase mechanism, we can completely filter irrelevant data. The 3D R*-tree comprises leaf and nonleaf nodes. A leaf node contains entries of the form (id, region), where id refers to a \(k\)-d tree in the database and region is the MBB of that tree. A nonleaf node is built by grouping MBBs at the lower level. Each \(k\)-d tree node maintains a list of (uri, tuple) pairs, where uri is a pointer to the address where the object actually resides and tuple is an extended RDF tuple. In our case, the extended RDF tuples comprise points in the \(n\)-dimensional data space, which are represented by compressed hash values and count frequencies. We can significantly reduce the memory pressure by replacing long string literals with hash values. The hash values are inserted sequentially and aggregated into the \(k\)-d trees. The 3D R*-tree is well suited for disk use because it is a broad shallow tree and requires few node accesses to retrieve a value. From our experiments in Section 4.2, we find that the 3D R*-tree stored in SSD does not have much performance effect. Thus, all R*-tree nodes are stored in HDD because the cost of SSD is higher than that of HDD. Each list of (uri, tuple) pairs is maintained on a designated \(k\)-d tree, which is completely transferred into the main memory when the refinement processing requires the corresponding list. The \(k\)-d tree is suitable for memory usage owing to its excellent storage utilization capacity (the pointer to data ratio is small and leaf nodes hold only data items), rapid searching (few nodes are retrieved using a binary search), and fast updating. However, existing Big Data systems either suffer from large memory space requirements or incur huge computational overhead. To improve the overall performance of the storage system, we divide the data into hot and cold. The frequently accessed data (i.e., hot data) are stored in SSDs, and the less frequently accessed data (i.e., cold data) are stored in HDDs. To distinguish hot and cold data more effectively, we use access history to train the decision tree model [28].