A New Spatial Index Structure for Efficient Query Processing in Location Based Services
Yong-Hun Park, Dongmin Seo, Jongtae Lim, Jinju Lee, Mikyoung Kim, Weiwei Bao, Christopher T. Ryu, Jaesoo Yoo · 2010
The interests of Location Based Services (LBS) have been highly increased according to the development of location aware techniques and mobile devices. Various spatial-indexing methods based on R-tree structure have been proposed to process queries efficiently. However, many node accesses occur in tree based spatial index structures when queries are processed. In this paper, we propose a spatial index structure, called ISGrid that provides better efficient query processing than R-tree based index structures. ISGrid uses not a tree structure but a grid structure that provides direct accesses to data pages and uses Minimum Boundary Rectangle (MBR) as a leaf node. The grid structure is used to access the leaf node. In addition, each leaf nodes maintain the links to neighbor leaf nodes like B+-tree to avoid unnecessary parent node accesses to search a neighbor node. We show the superiority of ISGrid from performance evaluation.