Spatial indexing of distributed multidimensional datasets

TitleSpatial indexing of distributed multidimensional datasets
Publication TypeConference Papers
Year of Publication2005
AuthorsNam B, Sussman A
Conference NameIEEE International Symposium on Cluster Computing and the Grid, 2005. CCGrid 2005
Date Published2005/05/09/12
ISBN Number0-7803-9074-1
Keywordscentralized global index algorithm, centralized index server, Computer science, database indexing, distributed databases, distributed multidimensional dataset, Educational institutions, File servers, Indexing, Large-scale systems, Multidimensional systems, Network servers, replication protocol, replication techniques, scalability, Sensor systems, spatial data structures, spatial indexing, two-level hierarchical index algorithm, wide area networks

While declustering methods for distributed multidimensional indexing of large datasets have been researched widely in the past, replication techniques for multidimensional indexes have not been investigated deeply. In general, a centralized index server may become the performance bottleneck in a wide area network rather than the data servers, since the index is likely to be accessed more often than any of the datasets in the servers. In this paper, we present two different multidimensional indexing algorithms for a distributed environment - a centralized global index and a two-level hierarchical index. Our experimental results show that the centralized scheme does not scale well for either insertion or searching the index. In order to improve the scalability of the index server, we have employed a replication protocol for both the centralized and two-level index schemes that allows some inconsistency between replicas without affecting correctness. Our experiments show that the two-level hierarchical index scheme shows better scalability for both building and searching the index than the non-replicated centralized index, but replication can make the centralized index faster than the two-level hierarchical index for searching in some cases.