¡¡Chinese Journal of Computers   Full Text
  TitleR-Tree Index Structure for Multi-Scale Representation of Spatial Data
  AuthorsDENG Hong-Yan1),2) WU Fang1) ZAI Ren-Jian1) ZHAO Qian3)
  Address1)(Department of Cartology and Geographical Information Engineering, Institute of Surveying and Mapping, Information Engineering University, Zhengzhou 450052)
2)(Institute of Geographic Sciences and Natural Resources Research, Beijing 100101)
3)(Airforce Command College, Beijing 100097)
  Year2009
  IssueNo.1(177¡ª184)
  Abstract &
  Background 		Abstract Aiming at multi-scale representation of spatial data not supported by R-tree, a transmutation index structure of R-tree used for multi-scale representation of spatial data is proposed: (1)Spatial objects may appear at non-leaf nodes; (2)Depth of the tree is made use for reflecting change of spatial resolutions£¬and resolution dimensions is supported; (3)Structure of the tree¡¯s branches supports algorithms of automatic cartography generalization. Query of spatial datas among multiple scales of based on the R-tree¡¯s transmutation index structure is analyzed, and constraint conditions, insert algorithms and divide algorithms among creations of the index structure are emphasized. For the same data source, compared with multi-scale index based on quad-tree for spatial data, experiments prove that the transmutation structure can search spatial data organized by multi-resolution and memorize generalization results with high efficiency.
Keywords spatial data; multi-scale representation; R-tree; index structure; geographical information system
Background The work is supported by the National Natural Science Foundation of China (grant Nos.40671162£¬ 40671152) and the High Technology Research and Development Program (863) of China under grant No.2007AA12Z211. The objective of these projects is to improve stone technologies for further development of GIS. So far, some achievements have been made in fields of intelligent generalization algorithms and automatic controlling for intelligent cartography.
To meet growing requirements and applications expansion of GIS, especially requirements for application and analysis of spatial data, processing and multi-scale representation of spatial data has become a far-reach topic in geo-science field, and it is also a world-wide hard problem. To solve the problem, scientific structure of spatial data and cartography generalization are prerequisites. A key technique to the representation is how to manage sequences of sub-spaces, that is how to build index structure for multi-scale representation of spatial data, because the technique will determine speed not only of representation but also query and analysis of the data. For the time being, solutions to the problem are improved structures on traditional index methods of spatial data, the best improved one is based on quad-tree, but it results in low efficiency for limitations of quad-tree.
In this paper, Spatial Data Multi-representation R-tree (SDMR), a transmutation index structure based on R-tree is proposed against limitations of traditional R-tree. Experiments prove that SDMR supports multi-scale representation of spatial data for all kinds of changes with higher efficiency than the improved one based on quad-tree, because the transmutation structure can memorize generalization results all through changes at the same scale and among different scales.