본 논문에서는 PML-트리라는 공간색인구조를 제안한다. PML-트리는 object distribution heuristics를 사용하여 공간 데이터 객체를 여러 개의 데이터 공간에 균일하게 배치함으로써 질의처리 속도를 향상시킨다. 두 가지의 object distribution heuristics(absolute crowd index와 relative crowd index)가 제안이 된다. PML-트리는 공간 객체를 분배함으로써 R+-트리의 말단 노드 내에 존재하는 데이터의 중복을 제거하면서, R-트리의 단점인 색인 사각형들 사이에 중첩을 허용치 않는다. PML-트리의 성능은 여러 타입의 테스트 데이터를 사용하여 MXR-트리와 비교된다. PML-트리는 MXR-트리에 비해 높은 공간활용도와 빠른 질의 반응시간을 보임으로써 공간 데이터베이스를 위한 효율적인 색인구조로 사용이 될 것으로 기대된다.

In this paper, a new dynamic parallel index structure called a parallel multiple-layer(PML) tree is proposed. The PML-tree increases speed of query processing by distributing data objects evenly among the multiple data spaces using object distribution heuristics. The author proposes and implements two heuristic methods, absolute crowd index and relative crowd index for an even distribution of objects over the multiple disks on which the PML-tree resides. The PML-tree does not require extra search paths as in R-tree, and does not contain any duplicated entries in leaf node as in R -tree. The performance the PML-tree and the MXR-tree are compared and analyzed using test data. Compared with the MXR-tree, the PML-tree increases space utilization and improves query performances on a system with multiple disks and expected as an efficient index structure for spatial databases.