Comparison of spatial indexing methods

COMPARISON OF SPATIAL INDEXING METHODSMURAT SEÇKİN AYHANAbstractAccording to achievements in computer sciences and resultingtechnologies, such as geographic information systems (GIS) and computer aideddesign (CAD) applications those have interest in spatial data types which aredifferent from primitive data types like integers, characters etc., take more placenowadays. To query these different, complex and also huge volumes of data in anefficient way, some spatial indexing methods are urgent. Common standards ondata types and representations have been defined by the Open GeospatialConsortium (OGC), but nothing about spatial indexing has occurred yet precisely.In the concept of the research project named Evliya Çelebi GeographicInformation Core, funded by TUBITAK under the code SOBAG-105K040, generalobjective is to study spatial indexing methods and to compare their performances.Three spatial indexing methods examined are: R-tree, STR-tree and MX-CIFQuadtree. Data sets are generated synthetically by Gaussian and uniformdistributions, and Bezier curves. Window queries are applied in test scenarios.To conclude, we can say that STR-tree has the best results. Because of itsinternal structure and definition, STR-tree targets static data sets. If dynamic datainsertions and deletions occur frequently, reorganization is urgent. R-tree and MX-CIF Quadtree are more suitable for dynamic environments.Keywords : Spatial Indexing, Spatial Access Method, Spatial Database,Bezier Curve, PostgreSQL, R-tree, STR-tree, MX-CIF Quadtree