Optimizing Physical Design of Multidimensional Files for Join Queries

S. Mohammed (Saudi Arabia) and B. Srinivasan (Australia)


Join, Multidimensional files, choice vector.


Optimally organizing multidimensional data is NP-hard. The little work that has been done in optimising multi dimensional data was limited to uniform data distribution and rarely considered the probability of use of each query. And those who did consider the probability of use of each query, they were limited to either partial match query or range query. This work shows that by combining heuristics and combinatorial algorithms, near-optimal solutions can be found which organize multidimensional data (uniform or skewed) on which join queries are efficiently performed. The experimental results of the proposed algorithms show that performance gains of up to 716% are achieved, when compared with standard schemes. Moreover, the proposed algorithms are not very sensitive to the change in the query distribution. The result show that if the query probabilities change by up to 80% of their original values, the original storage organizations remain near optimal.

Important Links:

Go Back