The PML-tree
Kap S. Bang, Huizhu Lu · 1996
In most applications, very large sets of spatial data are stored in secondary storage (e.g., disk).Parallelization of 1/0 operations can significantly reduce the query response time of the spatial index structure since operations on spatial index structures are highly l/0 bound.Furthermore, the parallelization technique with multiple disk units is specially suitable for handling massive data.In this paper, a new dynamic parallel spatial index structure called a parallel multi-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 authors propose and implement 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.In addition, the PML-tree does not require extra search paths, and does not contain any duplicated entries in leaf nodes.The performances of the PML-tree and the MXR-tree are compared and analyzed using the two types of data: (l) system generated data (uniformly distributed data and randomly distributed data) and (2) real application data (Tiger/Line™ files of the TIGER (geographic information system) database and VLSI layout data generated by the Magic system).Compared with the MXR-tree, the PML-tree increases space (node) utilization and improves query performances on a system with multiple disks.Penniuion to make diJitallhard copies of all or part of thia material for personal or clauroom usc is granted without fcc providod that the copies arc not made or diltributed for profit or commercial advantage, the c~y right notice, the title of the publication and ita date appear, and notice ta given that copyright ia by penniuion of the ACM, Inc.To copy Olherwise, to republish, to post on ~erven or to redistribute to liata, requires !lpCCific penniBiion and/or fcc.CSC '96, Philadelphia PA USA