VTQ-Tree: Quadtree Access Method With Variable Threshold; Application To GIS

The spatial queries in a geographical information system (GIS) uses the space attributes related to the geometry of the geographical objects. In these queries, research is done according to the location of the object in space. In order to efficiently process these queries, one needs specific access method. Among these methods one finds, the grid file, the R-trees, the quadtrees. In this paper, we propose an alternative of the quadtree with a variable threshold and a modification of the point query algorithm in case of a topological representation model. Instead of having a fixed threshold of S objects by quadrant, we propose to vary this threshold according to the level of the tree depth. Initially one starts with a threshold S₀, then the threshold is calculated according to the depth level dl with the root depth which is supposed to be null. In GIS the representation and the density of the space objects depend one hand on the scale and/or the resolution of the initial image and on the other hand the space data model representation. For the topological model representation, we propose an optimization of the point query algorithm in order to play down the research time. Finally we tested the proposed algorithms on a data files.