英文摘要 |
Location-based services (LBSs) provide information based on location information specified in a query. Queries that support for LBS are called Location-Dependent Queries (LDQ). LDQ contains Range query, Nearest Neighbor (NN) query, K-Nearest Neighbor (KNN) query and Reverse Nearest Neighbor (RNN) query etc. Example of mobile LBSs include location-dependent information access (e.g., traffic reports and attractions) and nearest neighbor queries (e.g., finding the nearest restaurant).While the LDQ is well studied in the traditional wired, disk-based client-server environment; it has not been tackled in a wireless broadcast environment. In this paper, the issues involved with organizing location dependent data and answering LDQ queries on air are investigated. The linear property of wireless broadcast media and power conserving requirement of mobile devices make the problem particularly interesting and challenging. An efficient data organization, called Jump-Rdnn Tree, and the corresponding search algorithm are proposed. Performance of the proposed Jump-Rdnn Tree and other traditional indexes (enhanced for wireless broadcast) is evaluated using both uniform and skew data. The result shows that Jump-Rdnn Tree substantially outperforms the traditional indexes. |