由於無線通訊網路的發達，以及頻寬的增長，使得在無線通訊網路下存取多媒體資料的行為越來越普及，但頻寬的增長永遠趕不上多媒體資料內容的成長速度。當使用者大量同時存取多媒體資料時，即使是基地台間的固網傳輸亦會發生擁塞的情形，為避免擁塞並減少使用者等待時間，我們應用資料探勘的方法預測出使用者可能前往的目的地及可能需求的資料，預先將預測出來的資料載入至預測出來的地點。一旦使用者果真前往該地點並請求了該資料，即可由快取對使用者做出回應，減少使用者等待時間；若快取已滿又有新的資料欲進入時，則必須啟動快取置換機制。在我們提出的快取置換機制中，有別於一般快取只考慮資料的存取頻率等性質，而特別考量了多媒體資料的特性－資料容量較大，以及這個資料在將來被存取的機率這兩個特性，其中資料在將來被存取的機率這個參數是利用資料探勘方法得到的。由於使用者的環境為無線通訊網路，故使用者會移動，而在不同地點會存取不同的服務，因此應綜合考量使用者所在位置與所請求的服務，據此我們提出一套具預測性的資料配置暨快取置換機制，稱之為PPCR（Predicted Preload and Cache Replacement）。經由實驗證實，我們提出的方法在存取多媒體資料的環境中能有效地減少使用者等待時間，與其他快取置換策略相比較亦有較好的效率。

Accessing multimedia data under wireless communication network is more and more popular because of the increased bandwidth. However, with the bandwidth is getting wider, the multimedia data size is growing even faster. When users request multimedia data at the peak time, even the fixed network translation between base-stations will be overloaded. In this research, we propose a data mining-based method, namely PPCR（Predicted Preload and Cache Replacement）, to predict the users’ future locations and requested multimedia services under wireless communication environments. Based on the mined user access patterns, the predicted service contents will be allocated and pre-loaded into the cache in the predicted locations such that the response time for user’s requests can be reduced. Meanwhile, we also propose a cache replacement mechanism that considers more issues than traditional cache replacement policies, like the multimedia data size and the accessing probability of the data. Though experimental evaluation, PPCR was shown to outperform other methods in reducing the uses’ response time when accessing multimedia data under wireless environments.

[1] R. Agrawal, T. Imieliński, and A. Swami, “Mining Association Rules between Sets of Items in Large Databases,” Proceedings of the ACM SIGMOD Conference on Management of Data, pages 207-216, Washington, D.C., May 1993.

[2] R. Agrawal and R. Srikent, “Fast Algorithms for Mining Association Rules,” Proceedings of the 20th International Conference on Very Large Data Bases, pages 478-499, Santiago, Chile, September 1994.

[3] R. Agrawal and R. Srikent, “Mining Sequential Patterns,” Proceedings of the 11th International Conference on Data Engineering, pages 3-14, Taipei, Taiwan, March 1995.

[4] Ian F. Akyildiz, Janise Mcnair, Joseph S. M. Ho, Huseyin Uzunalioglu, and Weye Wang, “Mobility Management in Next-Generation Wireless System,” Proc. Of the IEEE, Vol. 87, No. 8, August 1999.

[5] S. Ansari, R. Kohavi, L. Mason, and Z. Zheng, “Integrating e-commerce and data mining: Architecture and challenges,” In WEBKDD'2000 workshop: Web Mining for E-Commerce---Challenges and Opportunities.

[6] J. Ayres, J. E. Gehrke, T. Yiu, and J. Flannick, “Sequential Pattern Mining Using Bitmaps,” Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Edmonton, Alberta, Canada, July 2002.

[7] B. Bruegge and B. Bennington, “Applications of Mobile Computing and Communication,” IEEE Personal Communications, Special Issue on Mobile Computing, pages 64-71, February 1996.

[8] P. Cao and S. Irani, “GreedyDual-size: A cost-aware WWW proxy caching algorithm,” Proc. of USENIX Symposium on Internet Technology and Systems, 1997, pp.165-173.

[9] M.-S. Chen, J. Han and P. S. Yu, “Data Mining: An Overview from Database Perspective,” IEEE Transactions on Knowledge and Data Engineering, vol. 8, no. 6, pages 866-883, December 1996.

[10] M.-S. Chen, J.-S. Park and P. S. Yu, “Efficient Data Mining for Path Traversal Patterns,” IEEE Transactions on Knowledge and Data Engineering, vol. 10, no. 2, pages 209-221, March 1998.

[11] Sajal K. Das and Sanjoy K. Sen, “Adaptive Location Prediction Strategies Based on a Hierarchical Network Model in Cellular Mobile Environment,” Second International Mobile Computing Conference (IMCC), Taiwan, March 1996, pp 131-140.

[12] N. Davies, G.S. Blair, K. Cheverst, and A. Friday, “Supporting Collaborative Applications in a Heterogeneous Mobile Environment,” Computer Communication Special Issues on Mobile Computing, 1995.

[13] Dell Company, “ GPRS Technology Overview ,” February 2002.

[14] ELA/TLA., “ Cellular Radio Telecommunication Intersystem Operations,” 1991.

[15] A. Elmagarmid, J. Jain, and T. Furukawa, “ Wireless Client/Server Computing for Personal Information Service and Applications, ” ACM SIGMOD RECORD, vol. 24, no. 4, pages 16-21, December 1995.

[16] G. H. Forman and J. Zahorjan, “ The Challenges of Mobile Computing, ” IEEE Computer, vol. 27, no. 4, pages 28-47, April 1994.

[17] A. Foss, W. Wang, and O. R. Zaane, “A Non-Parametric Approach to Web Log Analysis,” Proc. Web Mining Workshop, in conjunction with the SIAM International Conference on Data Mining, Chicago, IL, USA, April 7, 2001.

[18] Jason Fritts, “Multi-Level Memory Prefetching for Media and Stream Processing,” Proceedings of the 2002 International Conference on Multimedia and Expo, 2002.

[19] J. Han, J. Pei, and Y. Yin, “Mining Frequent Patterns without Candidate Generation,” Proceedings 2000 ACM SIGMOD International Conference on Management of Data, vol. 29, no. 2, pages 1-12, Dallas, Texas, USA, May 2000.

[20] Jiawei Han, Jian Pei, Behzad Mortazavi-Asl, et. al., “FreeSpan: frequent pattern-projected sequential pattern mining,” Proc. of the 6th ACM SIGKDD nt’l Conference on Knowlwdge discovery and data mining (KDD), Boston, Massachusetts, United States, 2000.

[21] Markus Hofmann, T.S. Eugene Ng, Katherine Guo, Sanjoy Paul, Hui Zhang, “Caching Techniques for Streaming Multimedia over the Internet,” Bell Labs Technical Memorandum, April 1999.

[22] J. Jannink, D. Lam, N. Shivakumar, J. Widom, and D. Cox, “ Efficient and Flexible Location Management Techniques for Wireless Communication Systems,” ACM/Baltzer Journal of Mobile Networks and Applications, vol. 3, no. 5, pages 361-374, October 1997.

[23] A. Joshi and R. Krishnapuram, “On mining web access logs,” In Workshop on Research Issues in Data Mining and Knowledge Discovery SIGMOD, pages 63-69, 2000.

[24] Y.-B. Lin, “GSM Network Signaling,” ACM Mobile Computing and Communication, vol. 1, no. 2, pages 11-16, 1997.

[25] Y.-B Lin, “Modeling Techniques for Large-Scale PCS Networks,” IEEE Communications Magazine, 35(2):102-107, February 1997.

[26] G.-H. Li, K.-Y. Lam, and T.-W. Kuo, “Location Update Generation in Cellular Mobile Computing Systems,” Proc. Of International Workshop on Parallel and Distributed Real-time Systems, San Francisco, April 2001.

[27] D. Lee, et al., “On the Existence of a Spectrum of Policies the Subsumes LRU,LFU Policies,” Proc. of ACM SIGMETERICS Conference,1999.

[28] C. Lee and C.-C. Chen, “A Data Delivery Strategy in Ubiquitous Computing Systems,” Proceedings of the 7th International Conference on Database Systems for Advanced Applications, pages 210-217, April 2001.

[29] F. Masseglia, P. Poncelet and M. Teisseire, “ Incremental Mining of Sequential Patterns in Large Databases, ” Actes des 16imes Journes Bases de Donnes Avances (BDA'00), Blois, France, October 2000.

[30] Bamshad Mobasher et al., “Automatic Personalization Based on Web Usage Mining,” CACM August 2000.

[31] M.D.Mulvenna, S.S.Anand, A.G.Buchner, “ Personlization on the Net using Web Mining Introduction,” Communicaitons of the ACM, Volume 43, Number 8 (2000)

[32] J.-S. Park, M.-S. Chen and P. S. Yu, “ An Effective Hash Based Algorithm for Mining Association Rules,” Proceedings of the ACM SIGMOD Conference on Management of Data, pages 157-186, May 1995.

[33] W.-C. Peng and M.-S. Chen, “ A Dynamic and Adaptive Cache Retrieval Scheme for Mobile Computing Systems,” Proceedings 3rd IFCIS Conference on Cooperative Information Systems (CoopIS ’98), pages 251-258, August 1998.

[34] W.-C. Peng and M.-S. Chen, “Mining User Moving Patterns for Personal Data Allocation in a Mobile Computing System,” Proceedings of the 2000 International Conference on Parallel Processing, pages 573-580, Toronto, Canada, August 2000.

[35] J. Pei, J. Han, B. Mortazavi-Asl, and H. Zhu, “ Mining Access Patterns Efficiently from Web Logs,” Proceedings 2000 Pacific-Asia Conference on Knowledge Discovery and Data Mining, pages 396-407, Kyoto, Japan, April 2000.

[36] Reza Rejaie, Jussi Kangasharju, “Mocha: A Quality Adaptive Multimedia Proxy Cache for Internet Streaming,” Proceedings of the International Workshop on Network and Operating Systems Support for Digital Audio and Video, Port Jefferson, New York, June 2001.

[37] L. Rizzo and L. Vicisano, “Replacement Policies for a Proxy Cache,” UCL-CS Research Note RN/98/13,1998.

[38] John T. Robinson, Murthy V. Devarakonda, “Data cache management using frequency-based replacement,” In Proceedings of the ACM conference on Measurement and modeling of computer systems, Univ. of Colorado, Boulder, Colorado, United States, pp134 – 142, 1990.

[39] M. Satyanarayanan, “Mobile Information Access,” IEEE Personal Communications, pages 26-33, February 1996.

[40] R. Srikant and R. Agrawal, “ Mining Sequential Patterns: Generalizations and Performance Improvements,” Proceedings of the 5th International Conference on Extending Database Technology (EDBT), pages 3-17, Avignon, France, March 1996.

[41] N. Shivakumar, J. Jannink, and J. Widom, “ Per-User Profile Replication in Mobile Environments: Algorithms, Analysis and Simulation Results,” ACM/Baltzer Journal on Special Topics in Mobile Networks and Applications, vol. 2, no. 2, pages 129-140, 1997.

[42] Y. Saygin, O. Ulusoy, and A. Elmagarmid, “Association Rules For Supporting Hoarding in Mobile Computing Environments,” Proceedings of the 10th International Workshop on Research Issues in Data Engineering, IEEE Computer Society Digital Library, pages 71-78, fall 2000.

[43] M.-K. Shan and H.-F. Li, “Fast Discovery of Structure Navigation Patterns from Web User Traversals,” SPIE Conference on Data Mining and Knowledge Discovery: Theory, Tools, and Technology IV, 2002.

[44] Y. Saygin and O. Ulusoy, “ Exploiting Data Mining Techniques for Broadcasting Data in Mobile Computing Environments,” IEEE Transactions on Knowledge and Data Engineering, vol. 14, no. 6, November 2002.

[45] Huey-Min Sun, Chia-Mei Chen, LihChyun Shu, “Real-time Scheduling for Multimedia Streams Over Resource-Constrained Networks(S),” RTCSA 2002 Technical Program.

[46] Anthony K. H. Tung, Y. C. Tay and Hongjun Lu, “BROOM: Buffer Replacement using Online Optimization by Mining,” In Proceedings of the 7th International Conference on Information and Knowledge Management, Bethesda, Maryland, USA, pp.185-192, November 3-7, 1998.

[47] O. Wolfson, S. Jajodia, and Y. Huang, “An Adaptive Data Replication Algorithm,” ACM Transaction Database Systems, vol. 22, no. 4, pages 255-314, June 1997.

[48] Hsiao-Kuang Wu, Ming-Hui Jin, Jorng-Tzong Horng, and Cheng-Yi Ke, “Personal Paging Area Design Based On Mobile’s Moving Behaviors,” IEEE INFOCOM 2001.

[49] A. Zaslavsky and Z. Tari, “Mobile Computing: Overview and Current Status, ” Australian Computer Journal, vol. 30, no. 2, May 1998.

[50] Mohammed J. Zaki, “Efficient Enumeration of Frequent Sequences,” Proc. Of the 7th Int’l Conference on Information and Knowledge Management (CIKM), Bethesda, Maryland, USA, November, 1998.

[51] Mohammed J. Zaki, “Sequence mining in categorical domains: incorporating constraints,” Proc. of the 9th Int’l Conference on Information and Knowledge Management (CIKM), McLean, Virginia, United States, 2000.