在廣播環境進行與位置有關的資訊查詢

Search Location Dependent Data on Air

10.6188/JEB.2007.9(2).07

林聯發(Lien-Fa Lin)；黃淵科(Yuan-Ke Huang)

索引架構 ； 資料廣播 ； 能源管理 ； 行動計算 ； index structure ； data broadcast ； energy-conserving ； mobile computing

電子商務學報

9卷2期（2007 / 06 / 01）

377 - 398

繁體中文

提供與物體位置有關的查詢服務稱為位置為基礎的服務(Location Based Services-LBSs)。提供關於LBSs的查詢，我們稱為位置有關的查詢(Location-Dependent Queries-LDQs)。LDQs的應用包括了範圍查詢(Range query)、最近者查詢(Nearest Neighbor-NN query)、k個最近者查詢(K-Nearest Neighbor-KNN query)以及反向最近者查詢(Reverse Nearest Neighbor-RNN query)等。LBSs的行動服務應用包括提供如交通資訊與attractions等與位置相關的資訊存取以及如找尋最近的餐廳、找尋五百公尺以內的加油站等查詢服務。雖然LDQ的問題在傳統有線以磁碟為基礎的主從架構(disk based client-server)環境有很好的研究，目前在無線的廣播環境只處理特定如最近者的LDQ並沒有處理同時支援各種不同類型的LDQ的問題。本論文中，我們討論如何在無線廣播的環境有效的組識與位置相關的資料以及可以同時提供多種不同形態的LDQ查詢的問題。無線廣播線性存取以及行動裝置必需考量節省電力的特性使得這個問題更具挑戰性。我們針對無線廣播提出一個可適應線性存取與有效節省電力稱為Jump-Rdnn tree的索引架構與相對的LDQ查尋演算法。我們設計了大量的實驗來驗證我們的方法，實驗結果驗證我們方法在效能方面有顯著的提升。

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.

1. Barbara, D.(1999).Mobile Computing And Databases-A Survey.IEEE Transactions on Knowledge and Data Engineering,11(1),108-117.
2. Chaudhuri, S.,L. Gravano(1999).Evaluating top-k selection queries.Proceedings of the 25th IEEE International Conference on Very Large Data Bases,297-410.
3. Chen, M. S.,P. S. Yu,K. L. Wu(2003).Optimizing index allocation for sequential data broadcasting in wireless mobile computing.IEEE Transactions on Knowledge and Data Engineering,15(1),161-173.
4. Computer Science and Telecommunication Board(2003).The National Academies Press.
5. Datta, A.,D. E. Vandermeer,A. Celik,V. Kumar(1999).Broadcast Protocols to Support Efficient Retrieval from Database by Mobile Users.ACM Transactions on Database Survey,26,1-79.
6. Guttman, A.(1984).R-Trees: A Dynamic Index Structure for Spatial Searching.Proceedings of the 1984 ACM SIGMOD international conference on Management of data,47-57.
7. Hu, Q.,W. C. Lee,D. L. Lee(2001).Index Techniques for Power Management in Multi-Attribute Data Broadcast.Mobile Networks and Applications,6(2),185-197.
8. Imielinski, T.,S. Viswanathan,B. R. Badrinath(1997).Data on Air: organization and access.IEEE Transactions on Knowledge and Data Engineering,9(3),353-372.
9. Kollios G.,D. Gunopulos,V. J. Tsotras(1999).Nearest Neighbor Queries in a Mobile Environment Spatio-Temporal Database Management.International Workshop,119-134.
10. Korn F.,N. Sidiropoulos,C. Faloutsos,E. Siegel,Z. Protopapas(1996).Fast nearest neighbor search in medical image database.In Proceedings of the 22th International Conference on Very Large Data Bases,215-226.
11. Korn F.,S. Muthukrishnan,D. Srivastava(2002).Reverse nearest neighbor aggregates over data streams.Proceedings of the International Conference on Very Large Data Bases,91-98.
12. Korn, F.,S. Muthukrishnan(2000).Influence sets based on reverse nearest neighbor queries.Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data,201-212.
13. Lee D. L.,. C. Lee,. Xu,. Zheng(2002).Data Management in location dependent services.IEEE Pervasive Computing,1(3),65-72.
14. llarri, S.,E. Mena,A. Illarramendi(2006).Location-Dependent Queries in Mobile Contexts: Distributed Processing using Mobile Agents.IEEE Transactions on Mobile Computing,5(8),1029-1044.
15. Ross, S.(2000).Introduction to Probability and Statistics for Engineers and Scientists.
16. Roussopoulos, N.,S. Kelley,F. Vincent(1995).Nearest neighbor queries.Proceedings of ACM Sigmod International Conference on Management of Data,71-79.
17. Song, Z.,N. Roussopoulos(2001).K-Nearest Neighbor Search for Moving Query Point.Proceedings of 7th International Symposium on Advances in Spatial and Temporal Databases,79-96.
18. Stanoi, I.,D. Agrawal,A. E. Abbadi(2000).Reverse Nearest Neighbor Queries for Dynamic Databases.ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery,44-53.
19. Stanoi, I.,M. Riedewald,D. Agrawal,A. E. Abbadi(2001).Discovery of Influence Sets in Frequently Updated Databases.Proceedings of the 27th VLDB Conference,99-108.
20. Viredaz, M. A.,L. S. Brakmo,W. R. Hamburgen(2003).Energy management on hand held devices.ACM Queue,1(7),44-52.
21. Xu, J.,B. Zheng,W. C. Lee,D. L. Lee(2003).Energy efficient index for energy query location-dependent data in mobile environments.In Proceedings of the 19th IEEE International Conference on Data Engineering,239-250.
22. Xu, J.,W. C. Lee,X. Tang(2004).Exponential Index: A Parameterized Distributed Indexing Scheme for Data on Air.Proceedings of the 2nd ACM/USENIX International Conference on Mobile Systems,153-164.
23. Yang, C.,K. I. Lin(2001).An index structure for efficient reverse nearest neighbor queries.Proceedings of the 17th International Conference on Data Engineering,485-492.
24. Zhang, J.,L. Gruenwald(2002).Prioritized sequencing for efficient query on broadcast geographical information in mobile-computing.Proceedings of the 10th ACM international symposium on Advances in geographic information systems, November 08-09,88-93.
25. Zhang, J.,M. Zhu,D. Papadias,Y. Tao,D. L. Lee(2003).Location-based Spatial Queries.Proceedings of the 2003 ACM SIGMOD international conference on Management of data,443-454.
26. Zheng, B.,D. L. Lee(2005).Information Dissemination via Wireless Broadcast.Communication of ACM,48(5),105-110.
27. Zheng, B.,J. Xu,W. C. Lee,D. L. Lee(2004).Energy Conserving Air Indexes for Nearest Neighbor Search.Proceedings of the 9th International Conference on Extending Database Technology,48-66.
28. Zheng, B.,W. C. Lee,D. L. Lee(2003).Search K Nearest Neighbors on Air.Proceedings of the 4th International Conference on Mobile Data Management,181-195.
29. Zheng, J.,L. Gruenwald(2002).Prioritized Sequencing for Efficient Query on Broadcast Geographical Information in Mobile Computing.ACM GIS,88-93.