Mason Archival Repository Service

Distributed Approaches to Spatial Pivot Indexing

Show simple item record

dc.contributor.advisor Yang, Chaowei Tyler, Kevin
dc.creator Tyler, Kevin 2016-04-25 2016-07-27T17:17:16Z 2016-07-27T17:17:16Z
dc.description.abstract Spatial indexing is critical for retrieving data efficiently from geospatial databases, and has been a long-standing research direction of GIS. In a departure from recent spatial indexing paradigms, this study leverages pivot indexing. Pivot indexing begins by selecting a small number of points from the dataset. Then, the distances from the points in this subset- the pivots- to every point in the database are stored in secondary memory. During query time, these pre-computed values are used to evaluate candidates for range or nearest neighbor search. This approach offers a substantial reduction in the number of distance computations necessary to evaluate objects in the spatial plane. While previous spatial pivot indexing research leverages graphical processing units, this study utilizes an alternative parallelization mechanism- distributed computing. The Hadoop file system is used to accelerate index creation and querying in a scalable fashion. The results are then compared to an existing distributed solution. I ultimately discovered that my implementation of the pivot index at the distributed level underperformed existing methods by a small margin; however, my implementation offered an improved kNN query performance. These results affirm the legitimacy of the pivot indexing approach, and suggest that similar approaches deserve further investigation. Ultimately, this research does not assert that pivot indexing is superior to other approaches. Rather, it is an exploration of pivot indices in a specific computing context (the Hadoop File System). Thus, the contribution to the research community is in application. The outcome of this study is to demonstrate the utility of this particular indexing paradigm in the Hadoop software environment.
dc.language.iso en en_US
dc.subject spatial indexing en_US
dc.subject GIS en_US
dc.subject distributed computing en_US
dc.subject information retrieval en_US
dc.title Distributed Approaches to Spatial Pivot Indexing en_US
dc.type Thesis en Master of Science in Geoinformatics and Geospatial Intelligence en_US Master's en Geoinformatics and Geospatial Intelligence en George Mason University en

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search MARS


My Account