A Survey on Spatial Indexing

Shaik Abdul Nusrath Begum, K. P. Supreethi

Abstract


Spatial information processing has been a centre of attention of research in the previous decade. In spatial databases, data related with spatial coordinates and extents are retrieved based on spatial proximity. A large number of spatial indexes have been proposed to make ease of efficient indexing of spatial objects in large databases and spatial data retrieval. The goal of this paper is to review the advance techniques of the access methods. This paper tries to classify the existing multidimensional access methods, according to the types of indexing, and their performance over spatial queries. K-d trees out performs quad tress without requiring additional memory usage.


Full Text:

PDF

References


Indexing in Spatial Databases BC Ooi, R Sacks-Davis, J Han-Unpublished/Technical Papers, 1993.

Multidimensional Access Methods , VOLKER GAEDEIC-Parc, Imperial College, London and OLIVER GU¨ NTHER Humboldt-Universita¨ t, Berlin, ACM Computing Surveys, Vol. 30, No. 2, June 1998.

Spatial access methods P VAN OOSTEROM Geographical information systems, 1999.

A white paper on Spatial Partitioning and Indexing, Claudia Dolci, Dante Salvini, Michael Schrattner, Robert Weibel, GITTA(Geographic Information Technology Training Alliance).

Bentley, J. L., “Multidimensional Binary Search Trees Used For Associative Searching, ”Communications of the ACM, 18(9), 509-517, 1975.

J. L. Bentley, J. H. Friedman. Data structures for range searching. ACM Comput. Surv. 11, 1979, 4, 397–409.

J.T. Robinson. The K-D-B-tree: A search structure for large multidimensional dynamic indexes. In Proceedings of the ACM SIGMOD International Conference on Management of Data, 1981, pp. 10-18.

D.B. Lomet, B. Salzberg. The hBtree: A robust multi attribute search structure. In Proceedings of the Fifth IEEE International Conference on Data Engineering, 1989,pp. 296–304.

G. Evangelidis, D. Lomet, B. Salzberg. The hBP- tree: A modified hB-tree supporting concurrency, recovery and node consolidation. In Proceedings of the 21st InternationalConference on Very Large Data Bases, 1995, pp. 551–561.

J. B. Rosenberg: Geographical data structures compared: A study of data structures supporting region queries, IEEE Trans. on Comp. Aided Design CAD-4, 1, 53-67 (1985).


Refbacks

  • There are currently no refbacks.