Geo-Skip List Data Structure ? Implementation and Solving Spatial Queries

Abstract

A major portion of the queries fired on the internet have spatial keywords in them, the storage and retrieval of spatial data has become an important task in today?s era. Given a geographic query that is composed of query keywords and a location, a geographic search engine retrieves documents that are the most textually and spatially relevant to the query keywords and the location, respectively, and ranks the retrieved documents according to their joint textual and spatial relevance to the query. The lack of an efficient index that can simultaneously handle both the textual and spatial aspects of the documents makes existing geographic search engines inefficient in answering geographic queries. There are data structures which facilitate storage and retrieval of geographical data like R-trees, R* trees, KD trees etc. We propose Geo-Skip list data structure which is also one such data structure which is inspired from the skip list data structure. It is simple, dynamic, partly deterministic and partly randomized data structure. This structure brings out the hierarchy of administrative divisions of a region very well. Also it shows an improvement in the search efficiency as compared with R-trees. In this paper, we propose algorithms for the implementation of basic spatial queries with the help of Geo-Skip List data structure ? namely, point query, range query, finding the nearest neighbour query and kth nearest neighbour query.