Neelabh Pant

Graduation Semester and Year

2015

Language

English

Document Type

Thesis

Degree Name

Master of Science in Computer Science

Department

Computer Science and Engineering

First Advisor

Ramez Elmasri

Abstract

R-Trees are among the most popular multidimensional access methods suitable for indexing two dimensional spatial data and point data. R-Trees are found in most of the spatial database systems for indexing the spatial data. The data include points, lines and polygons which are retrieved and stored efficiently. There are many Spatial Database Systems which have incorporated R-Trees, for example, IBM Informix, Oracle Spatial, PostgreSQL and many others.Another version of R-Tree is R*-Tree which is also used for the same purpose i.e. indexing spatial data. R*-Tree has also been incorporated in an open source software SQLite with an extension of Spatialite. Several techniques have been proposed to improve the performance of spatial indexes, but none showed the comparative studies in their performance with the different categories of spatial and non-spatial queries. In this work, we compare the performance of three spatial indexing techniques: R-Tree (Rectangle Tree), GiST (Generalized Search Tree) and R*-Tree (A variant of R-Tree).We have five categories of spatial and non-spatial queries, namely, Simple SQL, Geometry, Spatial Relationship, Spatial Join and Nearest Neighbor search. We perform extensive experiments in all these five categories and record the execution time. The spatial data that are used for the experiments is the set of a benchmark data of New York City that include Point data: Subway stations, Line data: Streets and Subway lines, Polygon data: Boroughs and Neighborhoods plus non-spatial data such as Population data: Racially categorized.The comparison done in the experiments will give the reader performance criteria for selecting the most suitable index structure depending on the types of queries in the application.

Disciplines

Computer Sciences | Physical Sciences and Mathematics

Comments

Degree granted by The University of Texas at Arlington

Download

Share

COinS