Degree Name

Master of Science (Hons.)


Department of Computer Science


A number of non-siandard database applications need to store and manipulate the representations of two-dimensional real world objects. Efficient support of these applications requires us to abandon the traditional database models and to develop specialised data structures that satisfy the needs of indnidual applications. Recent iinestigations in the area of data stmctures for spatial databases have produced a number of specialised data structures like quad trees. K-D-B trees. R-trees etc. All these techniques try to improve access to data through various indices that reflect the partitions of two-dimensional search space and the geometric properties of represented objects. The other way to improve efficiency is based on linear clustering of disk areas that store information about the objects residing in respective partitions. A number of techniques for linear clustering of objects have been proposed so far. They include Gray curve. Hilbert curve, z-scan curve and snake curve. Unfortunately all these approaches assumed uniform and regular partitions of the search space. A number of interesting questions arise: Are the linear clustering techniques developed so far good for non-uniform partitions of space? Is there a specialised linear clustering technique that provides better results for non-uniform partitions of space? The main objectn e of this thesis is to provide an algorithm for linear clustering of non-uniform partitions of two-dimensional space. An evaluation of existing linear clustering techniques for uniform partitions of space is also made.