Parallelizing Multidimensional Index Structures

Indexing multidimensional data is inherently complex leading to slow queryprocessing. This behavior becomes more pronounced with the increase indatabase size and/or number of dimensions. In this paper, we address thisissue by processing an index structure in parallel. First, we study differentways of partitioning an index structure. We then propose efficient algorithmsfor processing each query in parallel on the index structure. Using thesestrategies, we parallelized two multidimensional index structures -- R* and LIBand evaluated the performance gains for the Gazetteer and the Catalog data ofthe Alexandria Digital Library on the Meiko CS-2.