SPACE FILLING CURVE BASED MULTIDIMENSIONAL RANGE QUERIES IN PEER TO PEER GRID ENVIRONMENT

Abstract

In Grid Computing Resource Discovery is an important activity as grid scheduler needs to find the available resources for carrying out the job. Traditionally in grid environment centralized or hierarchical resource discovery mechanism are used. But this is not scalable if number of entities participating in the grid becomes very large. In recent years peer to peer based resource discovery mechanisms for grid have been widely explored. Peer to peer resource discovery mechanism evolves from file sharing mechanism on internet. They are efficient for single dimensional exact match query. But in grid computing queries are generally multidimensional range queries. In past few years a large number of approaches have been proposed for multidimensional range queries for peer to peer environment. Space filling Curve (SFC) are used in database to map multidimensional data into one dimensional data. In this dissertation work we evaluate the work of Schmidt [4]. They have presented a SFC based mapping over CHORD [1] overlay network for complex queries in peer to. peer environment. They have used Hilbert SFC for their experiments. In this dissertation work we are evaluating feasibility of this system in grid environment. We are using Hilbert, Z-order and compact Hilbert SFC. Hamilton et al. [5] proposed the compact Hilbert indices where precision of various attribute differs, so that only minimum bits are used in construction of Hilbert indexes. In the experiments we find that Compact Hilbert index is better than Hilbert and Z-order SFC but for more than four dimensions its calculation becomes very time consuming and also using SFCs in high dimension generate a large number of clusters and locality properties may not be preserved. So we are dividing the attributes into groups and query the resources from these groups and finally take the intersection of results obtained. In the simulation we find that this gives better performance than using Single space filling