## 4 Experimental Evaluation
### Join Query Performance and Storage Amount
Although both attempt to save storage space by not loading all the data into a single repository, HYBRID and MIDAS perform slightly worse than DARQ because HYBRID has a 3D R*-tree with \(k\)-d trees, whereas MIDAS only has a \(k\)-d tree and requires additional space for service descriptions. QUAD performs significantly worse than the other three methods. Figure 10: Join query performance for various join types. During the join query processing, memory is allocated for retaining the filtering results. Thus, the memory size allocated for the join query processing is highly correlated with the filtering result size. Compared with QUAD, DARQ, and MIDAS, HYBRID requires the least amount of main memory because it can significantly reduce the filtering result size. Although DARQ requires the smallest storage space, it uses large memory to compute the join of intermediate results at the control site. The major motivation behind developing the HYBRID method is the desire to reduce the amount of main memory required to load the filtering results into the memory. Because the \(k\)-d trees are completely transferred into the main memory when the filtering results are required for the refinement phase, we assume that the main memory is sufficiently large to process these trees. If the \(k\)-d trees are excessively large to entirely fit in the main memory, a memory allocation problem arises. When the main memory becomes full and a new bucket must be inserted, any other bucket must be replaced. Several approaches have been proposed to determine the bucket that must be removed from the memory, including FIFO (First In First Out), LRU (Least Recently Used), and LFU (Least Frequently Used). Owing to memory space limitations, we should like to keep often-used data in the memory. Consequently, we use the LFU algorithm to manage the \(k\)-d trees, in which the least frequently used bucket is removed whenever the memory overflows. The storage amount of the filtering results can be considerably large if the dataset is large. Copying such a large quantity of data into the memory is obviously time- and space-consuming. Therefore, it is essential to reduce the storage amount of the filtering results, particularly in a multiuser environment. The proposed HYBRID method can significantly decrease the amount of required memory space. Moreover, the two-step query processing achieves better CPU performance than that of the other methods. The experimental results show that the storage and index structures in HYBRID are compact and efficient; hence, only data relevant to the queries are mostly accessed. The benefits provided by the compact storage and two-step index structure lead to efficient memory utilization and reduced I/O cost. From the above observations, we conclude that better performance is expected using HYBRID, even though it does not exhibit the best value in each criterion compared with other methods. This is because HYBRID achieves good join query performance with a small amount of storage. Therefore, we can reasonably predict that HYBRID will achieve a better overall performance than QUAD, DARQ, and MIDAS.