Previous [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7] [ 8] [ 9] [ 10] [ 11] [ 12] [ 13] [ 14] [ 15] [ 16] [ 17] [ 18] [ 19]


Journal of Information Science and Engineering, Vol. 30 No. 6, pp. 1945-1963 (November 2014)

A Spatial Indexing Scheme for Location Based Service Queries in a Single Wireless Broadcast Channel

11Deptartment of Computer Science and Engineering
Sogang University
Seoul, 121-742 Korea
2LG Gasan Digital Center
LG Electronics
Seoul, Korea

The rapid advancement of mobile devices and wireless network technology has accelerated the development of applications in the mobile computing field. In particular, LBS (Location-Based Services) are one of the fastest growing areas in mobile applications. In a wireless data broadcasting environment, a server can effectively provide LBS to a large population of mobile clients. The two most typical types of LBS queries are window and kNN (k-Nearest Neighbors) queries. Previously proposed window and kNN query processing schemes in a single wireless broadcast channel environment tend to access much unnecessary index information and data objects due to their low filtering powers. In this paper, we propose a new spatial index called HMI (Hilbert curve-based MBR filtering Index) for the efficient processing of window and kNN queries in a single wireless broadcast channel. HMI is a tree-structured index whose construction is based on the Hilbert curve and MBR (Minimum Bounding Rectangle). By combining an MBR structure with the Hilbert curve order, HMI obtains the advantages of both structures. We present an in-depth experimental analysis of our method by comparing it with current existing schemes. Our performance analysis shows that HMI significantly decreases the average access and tuning times of kNN queries over current existing schemes. HMI also gives better average tuning times and comparable average access times of window queries over current existing schemes.

Keywords: mobile databases, kNN query, window query, wireless broadcast channel, Hilbert curve, location based services

Full Text () Retrieve PDF document (201411_15.pdf)

Received November 27, 2012; revised March 11 & June 16, 2013; accepted July 23, 2013.
Communicated by Wanjiun Liao.
* This research was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education, Science and Technology (2010-0023101).