Web based Geographic Information Systems (GIS) services have become a very popular tool for many individuals. Services like MapQuest and Google Maps are among the most obvious examples, but there are also numerous other services that serve GIS data to web based clients. Typically at the heart of such systems in some form of spatial database that handles storage and retrieval of the objects to be mapped. Data structures such as B-Trees that are commonly used to index tables in databases are not suitable for multidimensional data stored in a spatial database, rather special indicies design specifically for spatial or multidimensional data have had to be developed. Among such indicies the most widely used is the R-Tree data structure. Originally proposed by [14], the R-Tree serves as the indexing structure for spatial databases developed by major GIS vendors.
Perhaps the most common operation that needs to be performed on a GIS database in a web based setting is the window query where a client requests that the database objects stored within a rectangular window be returned. The window query can be stated as follows, given a rectangular query window Q, return all the items in the database that intersect Q. During times of heavy load such databases are expected to handle large numbers of window queries in quick succession. The multi-search or batch searching problem is one in which a large number of queries are simultaneously processed [12]. The goal of this research is to develop methods for answering multi-search or batched queries on R-Trees efficiently in the EM model.
The Floating Buffer Tree presented here is designed to answer batch queries in an I/O efficient manner on static R-Trees. Static trees are of interest because in the web based GIS environment the changes to the data being indexed will be infrequent. The floating buffer method is a variant of a buffered version of the R-Tree presented in [2]. The floating buffer tree technique is described in this report and preliminary experimental results comparing performance with the Buffered R-Tree and standard R-Trees are presented.
This report is structured as follows. Section 2 provides a brief introduction to external memory (EM) algorithms, introduces some terminology and provides a brief overview of some applications of EM algorithms for batch processing in computational geometry. Section 3 provides and overview of the R-Tree data structure. In section 4 the buffer tree and and the buffered R-Tree are presented. Section 5 introduces the floating buffer tree and describes the main operation of the method while section 6 shows results of initial experimental comparisons between standard R-Trees, Buffered R-Trees, and Floating Buffer R-Trees. Conclusions are included in 7.