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

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