Implementation Technique of Join Operation on KD-Tree Indexed Relations

概要

論文の詳細を見る
In [1] we have introduced join strategies for KD-tree indexed relations. We proposed five basic strategies with page fetch and page unload policies to reduce the I/O cost of the join of very large relations indexed by KD-trees. Analytical analysis and simulation results showed that efficient page fetching can be done using the KD-tree index information. Besides, in order to maximize the memory efficiency and to minimize the I/O cost we proposed four extended strategies with garbage collection not at the level of pages, but at the level of chunks of tuples. Introducing this garbage collection mechanism, analytical expressions and simulation results showed that the I/O cost can be minimized to one scan of each relation. In order to verify and analyze the total cost of the proposed strategies with garbage collection, they are under implementation now. Here, after informally recalling the basic ideas of the join strategies, we present the adopted storage allocation and garbage collection mechanism and show some preliminary results of our implementation.
一般社団法人情報処理学会の論文
1989-03-15