The team's research on multidimensional indexing in the past one year
was two-fold: the theoretical complexity of multidimensional indexing,
specifically range searching, and performance enhancements to
existing index structures.
As part of the theoretical research, a lower bound of 
was established for linear-space, tree-structured index
structures that hold n d-dimensional objects.
Besides the above theoretical result, two
mechanisms were examined to improve the average query performance.
First is the use of data semantics.
This builds on the earlier research on LIB structures.
The LIB structures exploited the non-uniformity in spatial data to achieve
reasonable
performance enhancements. However, since they were maintained as separate
structures, they were sensitive to the extent of non-uniformity in the data.
Consequently, a new scheme was proposed that maintains a single structure but
retains the advantages of the LIB. This scheme promotes appropriate data
objects to higher levels in the tree. Two different strategies
to effect this promotion were investigated.
In the experiments on the Gazetteer and Catalog datasets of the Alexandria
Digital Library, the proposed schemes showed substantial improvement over
conventional structures like the 
trees.
The second approach to improving the average query performance
uses parallel processing [1]. The LIB structures and the
trees are parallelized on the Meiko CS-2.
The improvements in their performance were studied
for varying number of processors and varying query ranges.
A speedup of nearly 3.5 on 5 processors was obtained for both the structures.
Besides parallel query processing, some preliminary
experiments were also conducted
on parallel creation/updating of multidimensional indices.