Efficient Data Access for Location-Dependent Spatial Queries

详细信息    查看全文

• 作者：Kwangjin Park (1)
  
• 关键词：spatial index ; data broadcasting ; location ; based service
• 刊名：Journal of Computer Science and Technology
• 出版年：2014
• 出版时间：May 2014
• 年：2014
• 卷：29
• 期：3
• 页码：449-469
• 全文大小：
• 参考文献：1. Yang W, Hwang S. iTravel: A recommender system in mobile peer-to-peer environment. / Journal of Systems and Software, / Kwangjin Park: Spatial Query Processing on Air J. Comput. Sci. & Technol., May 2014, Vol.29, No.3 2013, 86(1): 12-20.
  2. Tanin E, Nayar D, Samet H. An efficient nearest neighbor algorithm for P2P settings. In / Proc. National Conference on Digital Government Research, May 2005, pp.21-28.
  3. Budiarto, Nishio S, Tsukamoto M. Data management issues in mobile and peer-to-peer environments. / Data Knowl. Eng., 2002, 41(2/3): 183-204. CrossRef
  4. Pushp S, Cho T, Han J, Lee D, Song J, Choi S. An efficient way to track peers in mobile P2P network. In / Proc. the 18th International Conference on Mobile Computing and Networking, Aug. 2012, pp.431-434.
  5. Takeshita K, Sasabe M, Nakano H. Mobile P2P networks for highly dynamic environments. In / Proc. the 6th IEEE Int. Conf. Pervasive Computing and Communications, March 2008, pp.453-457.
  6. Park K, Valduriez P. Energy efficient data access in mobile P2P networks. / IEEE Trans. Knowl. Data Eng., 2011, 23(11): 1619-1634. CrossRef
  7. Gurun S, Nagpurkar P, Zhao B. Energy consumption and conservation in mobile peer-to-peer systems. In / Proc. International Workshop on Decentralized Resource Sharing in Mobile Computing and Networking, Sept. 2006, pp.18-23.
  8. Sistla A P, Wolfson O, Xu B. Opportunistic data dissemination in mobile peer-to-peer networks. In / Proc. International Symposium on Spatial and Temporal Databases, Aug. 2005, pp.346-363.
  9. Park K, Choo H. Energy-efficient data dissemination schemes for nearest neighbor query processing. / IEEE Trans. Computers, 2007, 56(6): 754-768. CrossRef
  10. Huang Z, Jensen C, Lu H, Ooi B. Collaborative spatial data sharing among mobile lightweight devices. In / Proc. International Symposium on Advances in Spatial and Temporal Databases, July 2007, pp.366-384.
  11. Krikelis A. Location-dependent multimedia computing. / IEEE Concurrency, 1999, 7(2): 13-15. CrossRef
  12. Lee K, Lee W, Winter J, Zheng B, Xu J. CS cache engine: Data access accelerator for location-based service in mobile environments. In / Proc. ACM SIGMOD Int. Conf. Management of Data, June 2006, pp.787-789.
  13. Acharya S, Alonso R, Franklin M, Zdonik S. Broadcast disks: Data management for asymmetric communications environments. In / Proc. International Conference on Management of Data, May 1995, pp.199-210.
  14. Zheng B, Lee W, Lee D. On searching continuous / k nearest neighbors in wireless data broadcast systems. / IEEE Trans. Mobile Computing, 2007, 6(7): 748-761. CrossRef
  15. Imielinski T, Viswanathan S, Badrinath B. Data on air: Organization and access. / IEEE Trans. Knowledge and Data Eng., 1997, 9(3): 353-372. CrossRef
  16. Imielinski T, Viswanathan S, Badrinath B. Energy efficient indexing on air. In / Proc. Int. Conf. Management of Data, May 1994, pp.25-36.
  17. Zheng B, Xu J, Lee W, Lee D. Grid-partition index: A hybrid method for nearest-neighbor queries in wireless location-based services. / The VLDB Journal, 2006, 15(1): 21-39. CrossRef
  18. Zheng B, Lee W, Lee D. Spatial queries in wireless broadcast systems. / Wireless Network, 2004, 10(6): 723-736. CrossRef
  19. Park K, Song M, Hwang C. Adaptive data dissemination schemes for location-aware mobile services. / Journal of Systems and Software, 2006, 79(5): 674-688. CrossRef
  20. Lee W, Zheng B. DSI: A fully distributed spatial index for location-based wireless broadcast services. In / Proc. the 25th International Conference on Distributed Computing Systems, June 2005, pp.349-358.
  21. Park K. A hierarchical sequential index scheme for range queries in wireless location-based services. / Journal of Korean Society for Internet Information, 2010, 11(1): 15-20.
  22. Hu Q, Lee D, Lee W. Optimal channel allocation for data dissemination in mobile computing environments. In / Proc. the 18th International Conference on Distributed Computing Systems, May 1998, pp.480-487.
  23. Lee W, Lee D. Using signature techniques for information filtering in wireless and mobile environments. / Distributed and Parallel Databases, 1996, 4(3): 205-227. CrossRef
  24. Mokbel M, Chow C, Aref W. The new casper: A privacy-aware location-based database server. In / Proc. the 23rd International Conference on Data Engineering, April 2007, pp.1499-1500.
  25. Wolfson O, Xu B, Yin H. Dissemination of spatial-temporal information in mobile networks with hotspots. In / Proc. the 2nd Workshop on Databases, Information Systems, and Peer-to-Peer Computing, Aug. 2004, pp.185-199.
  26. Mondal A, Lifu Y, Kitsuregawa M. P2PR-tree: An R-tree-based spatial index for peer-to-peer environments. In / Proc. Int. Conf. Current Trends in Database Technology, March 2004, pp.516-525.
  27. Zhou P, Nadeem T, Kang P, Borcea C, Iftode L. EZCab: A cab booking application using short-range wireless communication. In / Proc. 3rd International Conference on Pervasive Computing and Communications, March 2005, pp.27-38.
  28. Ku W, Zimmermann R, Wang H. Location-based spatial query processing in wireless broadcast environments. / IEEE Trans. Mob. Comput., 2008, 7(6): 778-791. CrossRef
  29. Park K, Song M, Hwang C. Adaptive data dissemination schemes for location-aware mobile services. / Journal of Systems and Software, 2006, 79(5): 674-688. CrossRef
  30. Lee K, Lee W, Zheng B, Tian Y. ROAD: A new spatial object search framework for road networks. / IEEE Trans. Knowl. Data Eng., 2012, 24(3): 547-560. CrossRef
  31. Wang H, Zimmermann R. Processing of continuous location-based range queries on moving objects in road networks. / IEEE Trans. Knowl. Data Eng, 2011, 23(7): 1065-1078. CrossRef
  32. Zhang W, Wu W, Yang X, Xiang G. An optimized query index method based on R-tree. In / Proc. International Joint Conference on Computational Sciences and Optimization, April 2011, pp.1007-1011.
  33. Jing Y, Chen C, Sun W, Zheng B, Liu L, Tu C. Energy-efficient shortest path query processing on air. In / Proc. International Conference on Advances in Geographic Information Systems, Nov. 2011, pp.393-396.
  34. Zheng B, Lee W, Lee K, Lee D, Shao M. A distributed spatial index for error-prone wireless data broadcast. / The VLDB Journal, 2009, 18(4): 959-986. CrossRef
  35. Im S, Song M, Hwang C. An error-resilient cell-based distributed index for location-based wireless broadcast services. In / Proc. International Workshop on Data Engineering for Wireless and Mobile Access, June 2006, pp.59-66.
  36. Im S, Choi J. MLAIN: Multi-leveled air indexing scheme in non-flat wireless data broadcast for efficient window query processing. / Computers and Mathematics with Applications, 2012, 64(5): 1242-1251. CrossRef
  37. Guttman A. R-trees: A dynamic index structure for spatial searching. In / Proc. ACM SIGMOD Int. Conf. Management of Data, June 1984, pp.47-57.
  38. Xu J, Zheng B, Lee W, Lee D. The D-tree: An index structure for planar point queries in location-based wireless services. / IEEE Trans. Knowl. Data Eng., 2004, 16(12): 1526-1542. CrossRef
  39. Zheng B, Lee W, Lee D. Search continuous nearest neighbors on the air. In / Proc. International Conference on Mobile and Ubiquitous Systems: / Networking and Services, Dec. 2004, pp.236-245.
  40. Feeney L. An energy consumption model for performance analysis of routing protocols for mobile ad hoc networks. / Mobile Networks and Applications, 2001, 6(3): 239-249. CrossRef
  41. Camp T, Boleng J, Davies V. A survey of mobility models for ad hoc network research. / Wireless Communication and Mobile Computing, 2002, 2(5): 483-502. CrossRef
  42. Pfoser D, Jensen C. Indexing of network constrained moving objects. In / Proc. the 11th International Symp. Advances in Geographic Information Systems, Nov. 2003, pp.25-32.
  43. Atallah M J, Prabhakar S. (Almost) optimal parallel block access for range queries. / Information Sciences, 2003, 157: 21-31. CrossRef
  
• 作者单位：Kwangjin Park (1)
  
  1. Department of Information Communication Engineering, Wonkwang University, Iksan, Chunbuk, Korea
  
• ISSN：1860-4749

文摘

When the mobile environment consists of light-weight devices, the loss of network connectivity and scarce resources, e.g., low battery power and limited memory, become primary issues of concern in order to efficiently support portable wireless devices. In this paper, we propose an index-based peer-to-peer data access method that uses a new Hierarchical Location-Based Sequential (HLBS) index. We then propose a novel distributed Nearest First Broadcast (NFB) algorithm. Both HLBS and NFB are specifically designed for mobile peer-to-peer service in wireless broadcast environments. The system has a lower response time, because the client only contacts a qualified service provider by accessing the HLBS and quickly retrieves the data to answer the query by using NFB. HLBS and NFB design the index for spatial objects according to the positions of individual clients and transfer the index in the order arranged so that the spatial query can be processed even after the user tunes the partial index. Hence, this design can support rapid and energy-efficient service. A performance evaluation is conducted to compare the proposed algorithms with algorithms based on R-tree and Hilbert-curve air indexes. The results show that the proposed data dissemination algorithm with the HLBS index is scalable and energy efficient in both range queries and nearest neighbor queries.