The grid file is a well known access method for multi-dimensional and spatial data. The response time needed to process path and range queries on the grid file access method can be improved significantly by distributing the data pages over multiple disks. The paper explores the disk allocation methods used to allocate the data pages of grid file among a set of disks, which can be accessed in parallel. Given N disks, a perfect allocation will speed up the processing of each query by a factor of N in this environment. The authors show that no disk allocation is perfect for the set of all orthogonal range queries, even on uniformly distributed read-only data. They then introduce two families of allocation methods, namely the Linear allocation method and the Lattice allocation method, which are perfect for a large collection of interesting path queries (rows, columns, diagonals, anti-diagonals) and range queries (small rectangles), on an interesting set of data distributions. They address the issues in extending disk allocation methods to general data distributions with random updates. Finally, they provide experimental results on the performance of the proposed methods and other well known disk allocation methods on different query sets, data distributions and data set sizes.>

Three path-planning algorithms for single-pair path computation are evaluated. These algorithms are the iterative breath-first search, Dijkstra's single-source path-planning algorithm, and the A* single-path planning algorithm. The performance of the algorithms is evaluated on graphs representing the roadmap of Minneapolis. In order to get an insight into their relative performance, synthetic grid maps are used as a benchmark computation. The effects of two parameters, namely path length and edge-cost-distribution, on the performance of the algorithms are examined. The effects of implementation decisions on the performance of the A* algorithm are discussed. The main hypothesis is that estimator functions can improve the average-case performance of single-pair path computation when the length of the path is small compared to the diameter of the graph. This hypothesis is examined using experimental studies and analytical cost modeling.>

An approach to learning query-transformation rules based on analyzing the existing data in the database is proposed. A framework and a closure algorithm for learning rules from a given data distribution are described. The correctness, completeness, and complexity of the proposed algorithm are characterized and a detailed example is provided to illustrate the framework.>