在行動計算環境下, 使用者可以在任何時間任何地點,利用無線網路獲得如旅遊導覽或交通指引之類的服務.這一類的服務所需要的資料是和使用者所在位置有密切的相關性的Location Dependent Data (LDD).由於LDD只對位於其適用地區內的使用者而言才是正確而有意義的,因此使用者必須在離開LDD的適用地區前便取得所需的資料, 才能順利完成工作.為了避免使用者因為無線網路頻寬限制或快速移動而來不及取得所需要的LDD,導致工作無法完成,使用者必須設法預先取得未來可能用到的LDD.本論文採用評分的方式設計出一個mechansim,根據使用者未來的移動行為與LDD適用地區之間的關係, 以及LDD所能提供給使用者的資訊多寡,評量所預先抓取的資料可能帶給使用者的效益, 以作為使用者 prefetch LDD的依據.並且設計出一套 MVP algorithm,讓使用者可以迅速決定要如何進行prefetch,以獲得最大的效益.依據實驗的結果顯示,我們所設計的方法在多數的情況下都有很好的表現.

In the mobile computing environment,mobile services such as tourist guide and traffic report are avaliable anytime and anywhere for mobile users through wireless networks. Location Dependent Data (LDD) are the data for these kinds of services and are closely related to specific location called valid scope. In other words, the value of LDD is meaningful only when mobile users are in the valid scope of LDD. Therefore, LDD must be retrieved into client side before the user leaves the valid scope of LDD. However, due to limited bandwidth of the wireless link and frequent movements of mobile users, LDD could not be obtained in time. A solution of such a problem is to prefetch LDD needed in the near future. In this thesis, we first propose a rank-based mechanism for measuring the possible benefit of prefetched LDD. The mechanism considers both the relationship between user's mobility and the valid scope of LDD, and also the amount of information that LDD can provide. We then designed a Most Valuable Prefetching (MVP) algorithm for mobile users to efficiently earn the maximum benefit by prefetch. Finally, the performance results show that the MVP algorithm indeed performs better than other traditional methods in most situations.

[AF00] Mehmet Altinel and Michael J. Franklin, “Efficient Filtering of XML Documents for Selective Dissemination of Information,” in Proceedings of 26th VLDB Conference, Cairo, Egypt, 2000, pp 53-64.
[AFZ96] Swarup Acharya , Michael J. Franklin, and Stanley Zdonik “Prefetching from a Broadcast Disk,” in Proceedings of the 12th International Conference on Data Engineering (ICDE’96), New Orleans, LA, USA, February 2000, pp 276-285.
[BI94] Daniel Barbara and Tomasz Imielinski, “Sleepers andWorkaholics: Caching Strategies in Mobile Environments,” in Proceedings of ACM SIGMOD 1994, Minneapolis, MN, USA, May 1994, pp 1-12.
[BPS00] Philip A. Bernstein, Shankar Pal, and David Shutt, “Contextbased Prefetch - An Optimization for Implementing Objects on Relations,”in The VLDB Journal, Vol. 9, No. 3, 2000, pp 177-189.
[CC02] Sidney Chang and Dorothy Curtis, “An Approach to Disconnected Operation in an Object-Oriented Database,” in Proceedings of Mobile Data Management, Singapore, January 2002, pp 19-26.
[CB00] Boris Chidlovskii and Uwe M. Borghoff, “Semantic Caching of Web Queries,” in The VLDB Journal, Vol. 9, No. 1, 2000, pp 2-17.
[CFZ01] Mitch Cherniack, Michael J. Franklin, and Stan Zdonik, “Expressing User Profiles for Data Recharging,” IEEE Personal Communications, Vol 8, No 4, August 2001, pp 32-38.
[CGM01] Shimin Chen, Phillip B. Gibbons, and Todd C. Mowry, “Improving Index Performance Through Prefetching,” in Proceedings of ACM SIGMOD 2001, Santa Barbara, CA, USA, May 2001, pp 235-246.
[CPY01] Ing-Ray Chen, Ngoc Anh Phan, and I-Ling Yen, “Analysis of Algorithms for Supporting Disconnected Write Operations in Mobile Client-Server Environments,” in Proceedings of Autonomous Decentralized Systems, 2001.
[DFJS+96] Shaul Dar, Michael J. Franklin, Bj¨orn T. J´onsson, Divesh Srivastava, and Michael Tan, “Semantic Data Caching and Replacement,” in Proceedings of VLDB 1996, Mumbai, India, 1996.
[DK98] Margaret H. Dunham and Vijay Kumar, “Location Dependent Data and its Management in Mobile Database,” in Proceedings IEEE DEXA, August 1998, pp 414-419.
[HL98] Qinglong Hu and Dik Lun Lee, “Cache algorithms based on adaptive invalidation reports for mobile environments,” Cluster Computing, Vol. 1, No. 1, February 1998, pp 39-50.
[JYLK02] II-dong Jung, Young-ho You, Jong-hwan Lee, and Kyungsok Kim, “Broadcasting and Caching Policies for Location Dependent Queries in Urban Areas,” in Proceedings of Workshop on Mobile Commerce 2002 (WMC’02), Atlanta, Georgia, USA, September 2002, pp 54-60.
[KD98] Vijay Kumar and Margaret H. Dunham, “Defining Location Data Dependency, Transaction Mobility and Commitment,” Technical Report 98-CSE-01, Southern Methodist University, Dallas, TX, 1998.
[KP97] Geoffrey H. Kuenning and Gerald J. Popek, “Automated Hoarding for Mobile Computers,” in Proceedings of 16th ACM Symposium on Operating Systems Principles, St. Malo, France, October 1997.
[KR01a] Uwe Kubach and Kurt Rothermel, “A Map-Based Hoarding Mechanism for Location-Dependent Information,” in Proceedings of Mobile Data Management, Hong Kong, China, January 8-10 2001, pp 145-157.
[KR01b] Uwe Kubach and Kurt Rothermel, “Exploiting Location Information for Infostation-Based Hoarding,” in Proceedings of ACM MobiCom 2001, Rome, Italy, July 2001, pp 15-27.
[KS92] James J. Kistler and M. Satyanarayanan, Disconnected Operation in the Coda File System,” ACM Transactions on Computer Systems, Vol. 10, No. 1, February 1992, pp 3-25.
[LC01] Chiang Lee and Chao-Chun Chen, “A Data Delivery Strategy in Ubiquitous Computing Systems,” in Proceeding of the 7th International Conference on Database Systems for Advanced Applications (DASFAA01), Hong Kong, April 18-20, 2001, pp 210-217.
[LLXZ02] Dik Lun Lee, Wang-Chien Lee, Jianliang Xu, and Baihua Zheng, “Data Management in Location-Dependent Information Services,”IEEE Pervasive Computing, Vol. 1, No. 3, July-September 2002, pp 65-72.
[MBPK00] Sanjay Kumar Madria, Bharat Bhargava, Evaggelia Pitoura, and Vijay Kumar, “Data Organization Issues for Location-Dependent Queries in Mobile Computing,” in Proceedings of ADBISDASFAA 2000, Prague, Czech Republic, September 2000, pp 142-156.
[OKAD01] Bahattin Ozen, Ozgur Kilic, Mehmet Altinel, and Asuman Dogac, “Highly Personalized Information Delivery to Mobile Clients,” in Proceedings of ACM MobiDE 2001, USA, 2001, pp 35-42.
[PGM98] Vittoria de Person`e, Vincenzo Grassi, and Antonio Morlupi, “Modeling and Evaluation of Prfetching Policies for Context-Aware Information Services,” in Proceedings of ACM MobiCOM 1998, Dallas,Texas, USA, 1998, pp 55-65.
[RD99] Qun Ren and Magaret H. Dunham, “Using clustering for effective management of a semantic cache in mobile computing,” in Proceedings of ACM MobiDE 1999, Seattle, Washington, USA, 1999, pp94-101.
[RD00] Qun Ren and Magaret H. Dunham, “Using Semantic Caching to Manage Location Dependent Data in Mobile Computing,” in Proceedings of ACM MobiCOM 2000, Boston, MA, USA, 2000, pp 210-221.
[RDK03] Qun Ren, Magaret H. Dunham, and Vijay Kumar “Semantic Caching and Query Processing,” IEEE Transactions on Knowledge and Data Engineering, Vol. 15, No. 1, January/February 2003, pp192-210.
[SAW95] Bill Schilit, Norman Adams, and Roy Want, “Context-Aware Computing Applications,” in Proceedings of Workshop on Mobile Computing Systems and Applications, 1995, pp 85-90.
[SD02] Ayse Y. Seydim and Magaret H. Dunham, “A Location Dependent Benchmark with Mobility Behavior,” in Proceedings of International Database Engineering and Applications Symposium , Edmonton, Canada, July 2002, pp 74-83.
[SDK01] Ayse Y. Seydim, Magaret H. Dunham, and Vijay Kumar, “Location Dependent Query Processing,” in Proceedings of ACM MobiDE 2001, USA, 2001, pp 47-53.
[SDK01b] Ayse Y. Seydim, Magaret H. Dunham, and Vijay Kumar, “An Architecture for Location Dependent Query Processing,” in Proceedings of IEEE DEXA 2001, Munich, Germany, September 2001, pp549-555.
[SUE00] Yucel Saygin, Ozgur Ulusoy, and Ahmed K.Elmagarmid, “Association Rules for Supporting Hoarding in Mobile Computing Environment,”in Proceedings of RIDE, February 2000.
[TCO01] Kian-Lee Tan, Jun Cai, and Beng Chin Ooi, “An Evaluation of Cache Invalidation Strategies in Wireless Environment,” IEEE Transactions on Parallel and Distribute Systems, Vol. 12, No. 8, August 2001.
[TLAC95] Carl Tait, Hui Lei, Swarup Acharya, and Henrry Chang, “Intelligent File Hoarding for Mobile Computers,” in Proceedings of ACM Conference on Mobile Computing and Networking, Berkeley, CA, November 1995, pp 119-125.
[XHLL01] Jianliang Xu, Qinglong Hu, Wang-Chien Lee, and Dik Lun Lee, “An Optimal Cache Replacement Policy for Wireless Data Dissemination under Cache Consistency,” in Proceedings of ICPP 2001,Valencia, Spain, September 2001, pp 267-274.
[XTL02] Jianliang Xu, Xueyan Tang, and Dik Lun Lee, “Performance Analysis of Location-Dependent Cache Invalidation Schemes for Mobile Environments,” IEEE Transactions on Knowledge and Data Engineering,Vol. 15, No. 2, March/April 2003.
[XTLH99] Jianliang Xu, Xueyan Tang, Dik Lun Lee, and Qinglong Hu,“Cache Coherency in Location-Dependent Information Services for Mobile Environment,” in Proceedings of MDA 1999, Hong Kong,December 1999, pp 182-193.
[XZZL02] Jianliang Xu, Baihua Zheng, Manli Zhu, and Dik Lun Lee, “Research Challenges in Information Access and Dissemination in a Mobile Environment,” in Proceedings of Pan-Yellow-Sea International Workshop on Information Technologies for Network Era (PYIWIT’02), Saga, Japan, March 2002, pp 1-8.
[ZL01a] Baihua Zheng and Dik Lun Lee, “Processing Location-
Dependent Queries in a Multi-cell Wireless Environment,” in Proceedings of ACM MobiDE 2001, Santa Barbara, CA, USA, May 2001,pp 54-58.
[ZL01b] Baihua Zheng and Dik Lun Lee, “Semantic Caching in Location-Dependent Query Processing,” in Proceedings of SSTD 2001, Redondo Beach, CA, USA, July 2001, pp 97-113.
[ZLL03] Baihua Zheng,Wang-Chien Lee, and Dik Lun Lee, “Selecting the Best Valid Scopes for Wireless Dissemination of Location-Dependent Data,” in Proceedings of the 18th ACM Symposium on Applied Computing (SAC03), Melbourne, Florida, USA, March 2003.
[ZXL02] Baihua Zheng, Jianliang Xu, and Dik Lun Lee, “Cache Invalidation and Replacement Policies for Location-Dependent Data in Mobile Environments,” in IEEE Transactions on Computers, Vol.51, No. 10, October 2002, pp 1141-1153.