移动实时数据库中的数据广播策略研究
|
摘要
无线通信网络的迅猛发展使得移动计算成为现实。移动支持站点把被频繁请求的数据组织起来,以广播的形式传送给移动客户。
数据广播有许多问题值得研究。
移动实时环境里数据广播的首要问题是广播内容的选择。被频繁请求的热点数据能够及时广播,将会满足大量客户的需求,提高系统效率。传统的频繁元素获取通常采用计数、概要、分位数和散列等技术,时间性能最好的是散列类算法。在伯努利大数定理和马尔科夫不等式的基础上,通过统计散列冲突估算频繁元素出现的次数,利用多个散列函数和散列表可以使得误差被控制到精度许可的范围内。多散列计算可以充分利用现在主流多核微型处理器的计算能力。只需要增加散列函数的数量就可以提高统计精度,而增加的计算时间却很少。
以最少的时间和能源消耗获得最多有用的数据是移动客户在数据广播中获取的最大效益。数据广播调度从客户效益出发,采用基于优先权的调度策略。优先权综合考虑了数据截止期,数据的被请求频率和数据请求的到达时间。通过参数来调整它们的权重,使得调度策略能够在满足数据请求成功率的基础上,权衡平均访问时间和调谐时间。在调度策略的实施过程中将同一客户请求的数据尽可能地放在一起调度播出。数据组织结构里增加了热点数据指示器,移动客户在侦听信道的时候,可以根据自己设备的电源情况,有选择地下载各级热点数据,提高缓存命中率,降低上行信道负荷和平均访问时间,提高系统的处理能力。
实时系统中数据访问偏斜时,数据广播的索引技术鲜有研究。建立索引一方面要考虑数据的访问概率,另一方面要考虑数据的时间限制；同时构建索引的算法本身的时间复杂度要低。近似最优二叉索引树参考静态最优查找树的构造思想,在处理节点概率权重时引入实时加权,快速构造出查找效果近似最优的二叉索引树。其查找过程类似于折半查找,平均查找长度和logN成正比,即调谐时间至多logN个时间单位。因为考虑数据访问概率,被频繁访问的数据放在广播序列的前端,缩短了平均调谐时间；因为考虑了实时加权,时限较短的数据也放在了广播序列的前端,提高了实时系统中数据请求的成功率。
The rapid development of wireless communication network makes mobile computing to be reality. The mobile supporting station organizes data which are requested frequently and transmit them to mobile clients by broadcast mode.
There are many issues worth to be researched in data broadcasting.
It is the primary problem that how to determine data to be broadcasted. The data requested frequently broadcasting in time will satisfied with the needs of many mobile clients. The classic technologies to get frequent elements usually adopt to counting, sketching, quantile and hashing algorithms and the hashing algorithm performs best in time aspect. Based on Bernoulli large number theorem and Markov inequality, the number of frequent element that appeared is estimated by the conflicts of hashing. It makes the error to be fallen in the scope that be permitted that use a large number of hashing functions and hashing tables. Multi-hashing makes full use of the computing ability of multi-core CPUs which are popular at present. Adding hashing functions can raise the precision, but hardly increase the time.
It is the most benefit which mobile clients obtained from broadcast to take the most data available by the least time and power consumed. For the benefits of mobile clients the data broadcast scheduling adopts to priority scheme and adjusts the weights of data deadline, requested frequency and reach time. The scheduling is satisfied with the data request success ratio firstly, and then trades off average access time and average tuning time. With the implement of scheduling, the data requests of the same clients are arranged to responsed at adjacent broadcast frames as much as possible. The structure of data organization appends hot data indicators. When mobile clients listen the broadcast channel, they may download all kinds of hot data according to their power. The hit rate of cache is increased and the load of uplink channel is decreased, so as to reduce average access time. The throughput of broadcast system is improved.
Indexing technology is hardly studied when data access is skew in real time system. On one hand indexing considers the probability of data accessed, on the other hand indexing needs to satisfy data real-time constraints, and meanwhile, the time complexity of arithmetic computing for indexing must be low. The nearly optimal binary index tree NOBIT is based on the idea of static optimal search tree. We introduce real-time weight when it deals with nodes probabilities weight so as to quickly construct a binary index tree with nearly optimal performance. The search process of NOBIT is similar to binary search, and its average time complexity is O(logN). The NOBIT considers the probability of accessed data and data which are accessed frequently are put into the front part of broadcast sequence so that average tuning time is shortened. Meanwhile, the NOBIT takes the real-time constraints of accessed data into account and data with rigid time constraints also are put into the front part of broadcast sequence so that success rate of data requested is improved.
数据广播有许多问题值得研究。
移动实时环境里数据广播的首要问题是广播内容的选择。被频繁请求的热点数据能够及时广播,将会满足大量客户的需求,提高系统效率。传统的频繁元素获取通常采用计数、概要、分位数和散列等技术,时间性能最好的是散列类算法。在伯努利大数定理和马尔科夫不等式的基础上,通过统计散列冲突估算频繁元素出现的次数,利用多个散列函数和散列表可以使得误差被控制到精度许可的范围内。多散列计算可以充分利用现在主流多核微型处理器的计算能力。只需要增加散列函数的数量就可以提高统计精度,而增加的计算时间却很少。
以最少的时间和能源消耗获得最多有用的数据是移动客户在数据广播中获取的最大效益。数据广播调度从客户效益出发,采用基于优先权的调度策略。优先权综合考虑了数据截止期,数据的被请求频率和数据请求的到达时间。通过参数来调整它们的权重,使得调度策略能够在满足数据请求成功率的基础上,权衡平均访问时间和调谐时间。在调度策略的实施过程中将同一客户请求的数据尽可能地放在一起调度播出。数据组织结构里增加了热点数据指示器,移动客户在侦听信道的时候,可以根据自己设备的电源情况,有选择地下载各级热点数据,提高缓存命中率,降低上行信道负荷和平均访问时间,提高系统的处理能力。
实时系统中数据访问偏斜时,数据广播的索引技术鲜有研究。建立索引一方面要考虑数据的访问概率,另一方面要考虑数据的时间限制；同时构建索引的算法本身的时间复杂度要低。近似最优二叉索引树参考静态最优查找树的构造思想,在处理节点概率权重时引入实时加权,快速构造出查找效果近似最优的二叉索引树。其查找过程类似于折半查找,平均查找长度和logN成正比,即调谐时间至多logN个时间单位。因为考虑数据访问概率,被频繁访问的数据放在广播序列的前端,缩短了平均调谐时间；因为考虑了实时加权,时限较短的数据也放在了广播序列的前端,提高了实时系统中数据请求的成功率。
The rapid development of wireless communication network makes mobile computing to be reality. The mobile supporting station organizes data which are requested frequently and transmit them to mobile clients by broadcast mode.
There are many issues worth to be researched in data broadcasting.
It is the primary problem that how to determine data to be broadcasted. The data requested frequently broadcasting in time will satisfied with the needs of many mobile clients. The classic technologies to get frequent elements usually adopt to counting, sketching, quantile and hashing algorithms and the hashing algorithm performs best in time aspect. Based on Bernoulli large number theorem and Markov inequality, the number of frequent element that appeared is estimated by the conflicts of hashing. It makes the error to be fallen in the scope that be permitted that use a large number of hashing functions and hashing tables. Multi-hashing makes full use of the computing ability of multi-core CPUs which are popular at present. Adding hashing functions can raise the precision, but hardly increase the time.
It is the most benefit which mobile clients obtained from broadcast to take the most data available by the least time and power consumed. For the benefits of mobile clients the data broadcast scheduling adopts to priority scheme and adjusts the weights of data deadline, requested frequency and reach time. The scheduling is satisfied with the data request success ratio firstly, and then trades off average access time and average tuning time. With the implement of scheduling, the data requests of the same clients are arranged to responsed at adjacent broadcast frames as much as possible. The structure of data organization appends hot data indicators. When mobile clients listen the broadcast channel, they may download all kinds of hot data according to their power. The hit rate of cache is increased and the load of uplink channel is decreased, so as to reduce average access time. The throughput of broadcast system is improved.
Indexing technology is hardly studied when data access is skew in real time system. On one hand indexing considers the probability of data accessed, on the other hand indexing needs to satisfy data real-time constraints, and meanwhile, the time complexity of arithmetic computing for indexing must be low. The nearly optimal binary index tree NOBIT is based on the idea of static optimal search tree. We introduce real-time weight when it deals with nodes probabilities weight so as to quickly construct a binary index tree with nearly optimal performance. The search process of NOBIT is similar to binary search, and its average time complexity is O(logN). The NOBIT considers the probability of accessed data and data which are accessed frequently are put into the front part of broadcast sequence so that average tuning time is shortened. Meanwhile, the NOBIT takes the real-time constraints of accessed data into account and data with rigid time constraints also are put into the front part of broadcast sequence so that success rate of data requested is improved.
引文
[1]Tomasz Imielinski, B.R.Badrinath. Mobile Wireless Computing:Challenges in Data Management. Communications of the ACM,1994,37(10):18-28
[2]Tomasz Imielinski, S.Viswanathan, B.R.Badrinath. Power Efficient Filtering of Data on Air. in:Proceedings of the 4th International Conference on Extending Database Technology on Advances in Database Technology. Cambridge United Kingdom, 1994.245-258
[3]Tomasz Imielinski, S.Viswanathan, B.R.Badrinath. Energy Efficient Endexing on Air. ACM SIGMOD Record,1994,23(2):25-36
[4]Tomasz Imielinski, S.Viswanathan, B.R.Badrinath. Data on Air:Organization and Access. IEEE Transactions on Knowledge and Data Engneering,1997,9(3):353-372
[5]Dunham M H, Helal A. Mobile Computing and Databases:Anything New?. ACM SIGMOD Record,1995,24(4):5-9
[6]Jim Gray, Pat Helland, Patrick O'Neil et al. The Dangers of Replication and a Solution. in:Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data. J. Widom. SIGMOD '96. ACM. New York:ACM Press,1996.173-182.
[7]Jim Gray, Prakash Sundaresan, Susanne Englert et al. Quickly Generating Billion-Record Synthetic Databases. in:Proceedings of the 1994 ACM SIGMOD International Conference on Management of Data. Minnesota:ACM Press,1994. 243-252
[8]K.Stathatos, N.RoussoPoulos, J.S.Baras.Adaptive Data Broadcast in Hybrid Networks. in:Proeeedings of 23rd International Conference on Very Large DataBases. San Francisco:Morgan Kaufmann Publishers,1997.326-335
[9]J.X.Yu, T.sakata, K.Tan. Statistical Estimation of Access Frequencies in Data Broadcasting Environments. Wireless Networks,2000,6(2):89-98
[10]A.Carzaniga, D.S.Rosenblum, A.L.Wolf. Design and Evaluation of a Wide-Area Event Notification Service. ACM Transactions on Computer Systems,2001,19(3): 332-383
[11]P.T.Eugster, P.A.Felber, R.Guerraoui et al. The Many Faces of Publish/Subscribe. ACM Computing Surveys,2003,35(2):114-131
[12]Brian Babcock, Shivnath Babu, Mayur Datar,et al. Models and Issues in Data Stream Systems. In:Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems. Madison, Wisconsin:ACM PODS, 2002.1-16
[13]金澈清,钱卫宁,周傲英.流数据分析与管理综述.软件学报,2004,15(8)：1172-1181
[14]Gregory Piatetsky-Shapiro, Charles Connell. Accurate Estimation of the Number of Tuples Satisfying a Condition. In:International Conference on Management of Data Proceedings of the 1984 ACM SIGMOD international conference on Management of data. New York:ACM,1984.256-276
[15]Babcock B, Datar M, Motwani R, et al. Maintaining Variance and K-Medians over Data Stream Windows. in:Proceeding of the 22nd ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems. San Diego:ACM Press, 2003.234-243
[16]Datar M, Gionis A, Indyk P, Motwani R. Maintaining stream statistics over sliding windows. In:Eppstein D, ed. Proc. of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms. San Francisco:ACM/SIAM,2002.635-644
[17]Gibbons PB, Tirthapura S. Distributed streams algorithms for sliding windows. in: Proceeding of the 14th Annual ACM Symposium on Parallel Algorithms and Architectures. Winnipeg:ACM Press,2002.63-72
[18]AC Gilbert, Y.Kotidis, Muthukrishnan S, et al. Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries. in:Apers PMG, Atzeni P, Ceri S, et al eds. VLDB 2001, Proc. of the 27th International Conference on Very Large Data Bases. Roma:Morgan Kaufmann,2001.79-88
[19]Matias Y, Vitter JS, Wang M. Dynamic Maintenance of Wavelet-Based Histograms. in: Abbadi AE, Brodie ML, Chakravarthy S, et al, eds. VLDB 2000, Proc. of the 26th Int'l Conf. on Very Large Data Bases. Cairo:Morgan Kaufmann,2000.101-110
[20]J.S. Vitter. Random Sampling with a Reservoir. ACM Transactions on Mathematical Software (TOMS),1985,11(1):37-57.
[21]S.Chaudhuri, R.Motwani, V.Narasayya. On Random Sampling over Joins. in: Proceedings of the 1999 ACM SIGMOD International Conference on Management of Data,1999.263-274
[22]B.Babcock, M.Datar, R.Motwani, Sampling From a Moving Window over Streaming Data. in:Proceedings of The Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms,2002.633-634
[23]A.Das, J.Gehrke, M.Riedewald, Semantic Approximation of Data Stream Joins, IEEE Transactions on Knowledge and Data Engineering,2005,17(1):44-59
[24]P.Indyk, D.Woodruff. Optimal Approximations of The Frequency Moments of Data Streams, in:Proceedings of The Thirty-Seventh Annual ACM Symposium on Theory of Computing,2005.202-208
[25]C.Aggarwal. On Biased Reservoir Sampling in The Presence of Stream Evolution. in: Proceedings of The 32nd International Conference on Very Large Data Bases,2006. 607-618
[26]G. Cormode and S. Muthukrishnan. An Improved Data Stream Summary:The Count-Min Sketch and Its Applications. Algorithms Journal,2005,55(1):58-75
[27]Vladimir Braverman, Rafail Ostrovsky, Carlo Zaniolo. Optimal Sampling from Sliding Windows in:Proceedings of the 28th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems.2009.147-156
[28]Agrawal, R., Srikant, R. Fast Algorithms for Mining Association Rules. in: Proceeding of the 1994 International Conference Very Large Data Bases (VLDB'94),1994.487-499.
[29]Han, J.,Pei, J., Yin, Y. Mining Frequent Patterns Without Candidate Generation.in: Proceeding of 2000 ACM-SIGMOD International Conference Management of Data (SIGMOD'00),2000.1-12.
[30]Pei, J., Han, J.,Mao, R. CLOSET:An Efficient Algorithm for Mining Frequent Closed Itemsets. in:Proc.2000 ACM-SIGMOD Int.Workshop Data Mining and Knowledge Discovery (DMKD'00),2000.11-20
[31]Zaki, M. J., Hsiao, C. J. CHARM:An Effcient Algorithm for Closed Itemset Mining. in:Proceeding SIAM International Conference of Data Mining,2002.457.473.
[32]Muthukrishnan,S.Data streams:algorithms and applications.in:ACM-SIAM Symposium on Discrete Algorithms,2003.20-22
[33]Cormode G.., Korn F., Muthukrishnan, S., et al.Holistic UDAFs at Streaming Speeds. in:ACM SIGMOD International Conference on Management of Data,2004.35-46
[34]Pike, R., Dorward, S., Griesemer, et al. Interpreting the Data:Parallel Analysis with Sawzall. Grids World.2005,13(4):277-298
[35]Manku, G., Motwani, R. Approximate Frequency Counts over Data Streams. in: International Conference on Very Large Data Bases,2002.346-357
[36]A.Chakrabarti, GCormode, A.McGregor. A Near-Optimal Algorithm for Computing the Entropy of a Stream. in:Proceedings of ACM-SIAM Symposium on Discrete Algorithms,2007.328-335
[37]Arasu, A., Manku, G.S. Approximate Counts and Quantiles Over Sliding Windows. in: Proceedings of the Twenty-third ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems,2004.286-296
[38]Datar M., Gionis A., Indyk, P., et al. Maintaining Stream Statistics Over Sliding Windows.in:ACM-SIAM Symposium on Discrete Algorithms,2002.635-644
[39]Lee, L., Ting, H. A Simpler And More Efficient Deterministic Scheme For Finding Frequent Items Over Sliding Windows. in:Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of Database Systems,2006.290-297
[40]Jayram T.S., McGregor A. Muthukrishnan S., et al. Estimating Statistical Aggregates on Probabilistic Data Streams. in:Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems,2007.243-252
[41]Boyer R.S., Moore, J. A fast majority vote algorithm. Technical Report ICSCA-CMP-32, Institute for Computer Science, University of Texas,1981.59-62
[42]Fischer M., Salzburg, S. Finding a Majority Among N Votes:Solution to Problem, J. Algorithms,1982,3(4):376-379
[43]Boyer R.S., Moore,J.S. MJRTY-a Fast Majority Vote Algorithm.in:Automated Reasoning:Essays in Honor of Woody Bledsoe,Automated Reasoning Series,1991. 105-117
[44]Demaine E., Lopez-Ortiz A., Munro J.I. Frequency Estimation of Internet Packet Streams With Limited Space. in:European Symposium on Algorithms,2002.348-360
[45]Karp R., Papadimitriou C., Shenker S. A Simple Algorithm for Finding Frequent Elements in Sets and Bags. ACM Transaction Database System,2003,28(2):51-55.
[46]Bose P., Kranakis E., Morin P., et al. Bounds for frequency estimation of packet streams. in:Proceedings of SIROCCO (2003),2003.33-42
[47]Manku G., Motwani R. Approximate Frequency Counts Over Data Streams. in: International Conference on Very Large Data Bases,2002.346-357
[48]Manku G.S. Frequency counts over data streams. http://www.cse.ust.hk/～/S10P03.ppt
[49]Metwally A.,Agrawal D., Abbadi A.E. Efficient Computation Of Frequent And Top-K Elements in Data Streams. in:International Conference on Database Theory,2005.398-412
[50]Greenwald M., Khanna S. Space-efficient online computation of quantile summaries. in:ACM SIGMOD International Conference on Management of Data,2001.58-66
[51]Shrivastava N., Buragohain C., Agrawal D. et al. Medians and beyond:new aggregation techniques for sensor networks.in:Proceedings of the 2nd international conference on Embedded networked sensor systems,2004.239-249
[52]Hershberger J., Shrivastava N., Suri S., et al. Adaptive spatial partitioning for multidimensional data streams. Algorithmica,2004,46(1):97-117
[53]Cormode G., Korn F., Muthukrishnan S., et al. Spaceand time-efficient deterministic algorithms for biased quantiles over data streams. in:Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, 2006.263-272
[54]Charikar M., Chen K., Farach-Colton M. Finding frequent items in data streams. in: Procedings of the International Colloquium on Automata, Languages and Programming (ICALP),2002.693-703
[55]Cormode G., Muthukrishnan S. An improved data stream summary:the count-min sketch and its applications. J. Algorithms,2005,55(1):,58-75
[56]Cormode G., Muthukrishnan S. What's new:Finding significant differences in network data streams. in:INFOCOM 2004. Twenty-third AnnualJoint Conference of the IEEE Computer and Communications Societies,2004.1534-1545
[57]Schweller R., Li Z., Chen, Y., et al. Reversible sketches:enabling monitoring and analysis over high-speed data streams. IEEE Transanction of Netw. 2007,15(5):1059-1072
[58]Dobra A., Rusu F. Statistical analysis of sketch estimators. in:ACMSIGMOD International Conference on Management of Data,2007.187-198
[59]Graham Cormodem, Marios Hadjieleftheriou. Methods for finding frequent items in data streams. The VLDB Journal,2010,19(1):3-20
[60]严蔚敏,吴伟民.数据结构.(第二版).北京：清华大学出版社,1992.255-278
[61]E.horowitz, S.Sahni. Fundamentals and Data Structures.Washington:Pitmen Publishing Limited.1976.387-391
[62]D.E.Knuth. The Art of Computer Programming, Vol1:Fundamental Algorithms(3th). Addison-Wesley Publishing Company.1998.401-407
[63]D.E.Knuth. The Art of Computer Programming, Vol3:Sorting and Searching(2ed). Addison-Wesley Publishing Company.1996.388-393
[64]Jin C., Qian W., Sha C., et al. Zhou A. Dynamically maintaining frequent items over a data stream. In:Proc. of the 2003 ACM CIKM Int'l Conf. on Information and Knowledge Management. New Orleans:ACM Press,2003.287-294.
[65]http://ita.ee.lbl.gov/html/traces.html
[66]Swarup Acharya,Michael Franklin,Stanley Zdonik.Balancing Push and Pull for Data Broadcast.in:Proceedings of the 1997 ACM SIGMOD international conference on Management of data,1997.183-194
[67]Swarup Acharya, Rafael Alonso,Michael Franklin,et al. Broadcast Disks:Data Management for Asymmetric Communication Environments. in:Proceedings of the ACM SIGMOD Conference, San Jose, CA,1995.199-210
[68]John W. Wong, Broadcast Delivery. Proceedings of the IEEE,1988,76(12):1566-1577
[69]Chi-Jiun Su, Leandros Tassiulas. Broadcast Scheduling for Information Distribution. In:Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies.1997.109-117
[70]S. Hameed and N.H.Vaidya. Efficient algorithms for scheduling data broadcast. ACM/Baltzer Jounral of Wireless Networks,1999,5(3):183-193
[71]N.H.Vaidya and S. Hameed. Scheduling data broadcast in asymmetric communication environments.ACM/Baltzer Jounral of Wireless Networks,1999,5(3):171-182
[72]吴海,石磊,卢炎生.实时环境下一种混合广播调度策略.计算机科学,2009,36(5)： 158-162
[73]Swarup Acharya, S.Muthukrishnan, Scheduling on-demand broadcasts. in:The fourth annual ACM/IEEE international conference on Mobile computing and networking, Dallas,Texas,1998.43-54
[74]D.Aksoy, M.Franklin. Scheduling for large scale on-demand data broadcast.in: Proc.of IEEE INFOCOM, San Francisco,1998.651-659
[75]Bender M.A., Chakrabarti S., Muthukrishnan S. Flow and stretch metrics for scheduling continuous job streams. in:Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms. San Francisco,1998.270-279
[76]Aksoy D., Franklin M. RxW:a scheduling approach for large-scale on-demand broadcast. IEEE/ACM Transactions on Networking,1999,7(6):846-860
[77]Acharya S., Alonso R., Franklin M., et al. Broadcast disks:data management for asymmetric communication environments. in:Proc of ACM SIGMOD Conf. San Jose, California,1995.199-210
[78]孙未未,施伟斌,施伯乐.移动计算环境中数据广播访问时间优化算法.小型微型计算机系统,2003,3(24)：577-579
[79]Sun Wei Wei, Shi Wei Bin, Shi Bo Le. A cost efficient scheduling algorithm of on-demand broadcasts. Wireless Networks,2003,9(3):239-247
[80]Xuan P., Sen S., Gonzalez O., et al. Broadcast on-demand:efficient and timely dissemination of data in mobile environments. in:Proc of the 3rd IEEE Real-Time Technology and Applications Symposium. Montreal, Canada,1997.38-48
[81]Jesus F.C., Ramamritham K. Adaptive dissemination of data in time-critical asymmetric communication environments. Mobile Networks and Applications,2004, 9(5):491-505
[82]Hu J.H., Yeung K.L., Feng G., et al. A novel push-and-pull hybrid data broadcast scheme for wireless information networks.in:Proc of 2000 IEEE Int Conf on Communications,2000.1778-1782
[83]Lee W.C., Hu Q.L., and Lee D.L. A study of channel allocation methods for data dissemination in mobile computing environments. ACM/Baltzer Journal of Mobile Networks and Applications (MONET),1999,4(2):117-129
[84]John A. Stankovic, Marco Spuri, Krithi Ramamritham, et al.Deadline Scheduling for Real-Time Systems-EDF and Related Algorithms. Springer Press,1998,187-189
[85]刘云生,杨进才,廖国琼.移动环境中实时事务数据的广播调度.小型微型计算机系统,2004,25(4)：1534-1537
[86]C.L. Hu, M.S. Chen. Dynamic data broadcasting with traffic awareness, in: Proceedings of the 22nd IEEE International Conference on Distributed Computing Systems (ICDCS'02),2002.112-119
[87]C.L. Hu, M.S. Chen. On-line scheduling sequential objects for dynamic information dissemination. in:Proceedings of 2005 IEEE Global Communications Conference (GLOBECOM'05),2005.105-110
[88]Chin-Lin Hu. Fair Scheduling for On-Demand Time-Critical Data Broadcast. in:ICC '07. IEEE International Conference on Communications.2007.5832-5835
[89]朱香元,李仁发,杨胜,江文.基于优先级的数据广播内容选择算法.计算机工程与应用,2006,42(33)：147-149
[90]Xiao Wu, Victor C.S.Lee, Joseph Kee-Yin Ng. A Preemptive Scheduling Algorithm for Wireless Real-Time On-Demand Data Broadcast. in:Proceedings of the 11th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA'05),2005.18-20
[91]Rinku Dewri, Indrakshi Ray, Indrajit Ray et al. Optimizing on-demand data broadcast scheduling in pervasive environments.in:Proceedings of the 11th international conference on Extending database technology. Nantes, France.2008.559-569
[92]J.Xu, X.Tang,W.Lee. Time-critical on-demand data broadcast:Algorithms, analysis, and performance evaluation. IEEE Transactions on Parallel and Distributed Systems, 2006,17(1):3-14
[93]Victor C.S.Lee,Xiao Wu and Joseph Kee-Yin Ng. Scheduling real-time requests in on-demand data broadcast environments.Real-Time Systems,2006,34(2):83-99
[94]Majid Raissi-Dehkordi, John S.Baras. Broadcast Scheduling for Time-Constrained Information Delivery. in:IEEE GLOBECOM 2007 proceedings,2007.5299-5301
[95]Chung Y.D., Kim M.H. QEM:a scheduling method for wireless broadcast data. in: Proceedings of the 6th Int Conf on Database Systems for Advanced Applications, 1999.135-142
[96]G.Lee, M.S.Yeh, S.C.Lo,et al. A Strategy for Efficient Access of Mulitiple Data Items in Mobile Environment. in:Proc. of the 3rd IEEE Int. Conf. on Mobile Data Management2002.71-78
[97]Chang Y.I., Hsieh W.H. An efficient scheduling method for query-set-based broadcasting in mobile environments. in:Proc of the 24th Int Conf on Distributed Computing Systems Workshops,2004.478-483
[98]Lee G.L., Lo S.C. Broadcast data allocation for efficient access of multiple data items in mobile environments. Mobile Networks and Applications,2003,8(4):365-375
[99]Huang J.L., Chen M.S. Dependent data broadcasting for unordered queries in a multiple channel mobile environment. IEEE Transactions on Knowledge and Data Engineering,2004,16(9):1143-1156
[100]Lien-Fa Lin, Chao-Chun Chen,Chiang Lee. Benefit-oriented data retrieval in data broadcast environments. Wireless Networks,2010,16(1):1-15
[101]Peng Wen Chih, Chen Ming Syan. Design and performance studies of an adaptive cache retrieval scheme in a mobile computing environment. IEEE Transactions on Mobile Computing.2005,4(1):29-40
[102]Gray J., Prakash Sundaresan, Susanne Englert, et al.Quickly Generating Billion-Record Synthetic Databases. in:Proc of the 1994 ACM SIGMOD. Minneapolis, Minnesota,1994.243-252
[103]Ming-Syan Chen, Kun-Lung Wu, Philip S.Yu. Optimizing Index Allocation for Sequential Data Broadcasting in Wireless Mobile Computing. IEEE Transactions On Knowledge and Data Engineering,2003,15(1):161-173
[104]Yon Dohn Chung, Myoung Ho Kim. An index replication scheme for wireless data broadcasting. The Journal of Systems and Software,2000,51(3):191-199
[105]Lo, S.C., Chen, A.L.P. An adaptive access method for broadcast data under an error-prone mobile nvironment. IEEE Transactions on Knowledge and Data Engineering,2000,12(4):609-620
[106]Jun-Hong Shen, Ye-In Chang. A Skewed Distributed Indexing for Skewed Access Patterns on The Wireless Broadcast. The Journal of Systems and Software,2007,80(5):711-723
[107]W.C.Lee, D.L.Lee.Using Signature Techniques for Information Filtering in Wireless and Mobile Environments. Journal of Distributed and Parallel Databases (DPDB), 1996,4(3):205-227
[108]W.C. Lee, D.L. Lee. Signature Caching Techniques for Information Filtering in Wireless Environments. ACM Wireless Networks,1999,4(1):57-67
[109]J.Xu, D.L.Lee, Q. Hu et al. Data Boradcast Handbook of Wierless Networks and Mobile Computing.,New York:JohnWiley& Sons,2002,243-265.
[110]Xu Yang, Athman Bouguettaye. Using a Hybrid Method for Accessing Broadcast Data. in:Proceedings of the 6th international conference on Mobile data management,2005.38-42
[111]李国徽,唐向红.移动环境下数据广播中的混合索引技术.计算机应用研究,2007,24(6)：315-316
[112]Qinglong Hu, Wang-Chien Lee, Dik Lun Lee. A Hybrid Index Technique for Power Efficient Data Broadcast. Distributed and Parallel Databases,2001,9(2):151-177
[113]Donald E. Knuth The Art of Computer Programming, Vol 2 Seminumerical algorithms(3rd Edition). Addison Wesley Longman,1998.405-423
[114]Alfred V.Aho, John E.Hopcroft, Jeffrey D.Ullman. The Design and Analysis of Computer Algorithms(2ed Edition). Addison Wesley Longman,2005.69-74
[115]严蔚敏,吴伟民.数据结构.第二版.北京：清华大学出版社,2003.222-225
[116]Hui Song, Guohong Cao. Cache-Miss-Initiated Prefetch in Mobile Environments. in:Proceedings of the 2004 IEEE International Conference on Mobile Data Management (MDM'04).2004.370-381
[117]G. Cao. A Scalable Low-Latency Cache Invalidation Strategy for Mobile Environments. IEEE Transactions on Knowledge and Data Engineering, 2003,15(5):1251-1265
[118]Wen-Chih Peng, Ming-Syan Chen. Design and Performance Studies of an Adaptive Cache Retrieval Scheme in a Mobile Computing Environment. IEEE Transactions On Mobile Computing,2005,4(1):29-40
[119]Chiranjeev Kumar, GR.Madhuri, Shweta Agrawal.Efficient Bandwidth Utilization in Mobile Environments for Temporal Based Cache Invalidation. in:TENCON 2008 IEEE Region 10 Conference.Hyderabad.2008.1-5
[120]Huaping Shen, Mohan Kumar, Sajal K. Das, et al.Energy-Efficient Caching and Prefetching with Data Consistency in Mobile Distributed Systems.in:Proceedings of the 18th International Parallel and Distributed Processing Symposium (IPDPS'04). 2004.67-76
[121]L. Fan, P. Cao, W. Lin, and Q. Jacobson, Web Prefetching Between Low-Bandwidth Clients and Proxies:Potential and Performance. in:Proceedings of the ACM SIGMETRICS Conference,1999.178-187
[122]S. Gitzenis, N. Bambos. Power-Controlled Data Prefetching/Caching inWireless Packet Networks. in:Proceedings of IEEE INFOCOM 2002,New York,2002.1405-1414
[123]G Cao. Proactive Power-Aware Cache Management for Mobile Computing Systems. IEEE Transactions on Computers,2002,51(6):608-621
[124]Z. Wang, S. K. Das, H. Che et al. SACCS:Scalable Asynchronous Cache Consistency Scheme.in:Proceedings of ICDCS Internation Workshop on Mobile Wireless Networks,2003.797-802
[125]Z. Wang, M. Kumar, S. K. Das et al. Investigation of Cache Maintenance Strategies for Multi-Cell Environments. in:International Conference on Mobile Data Management (MDM),2003.29-44
[126]李国徽,杨兵,陈辉等.移动环境下支持实时事务处理的数据预取.计算机学报,2008,31(10)：1841-1847
[127]Liangzhong Yin, Guohong Cao, Chita Das et al. Power-Aware Prefetch in Mobile Environments.in:Proceedings of the 22 nd International Conference on Distributed Computing Systems (ICDCS'02).2002.571-578
[128]Liangzhong Yin, Guohong Cao.Adaptive Power-Aware Prefetch inWireless Networks.IEEE Transactions on Wireless Communications,2004,3(5):1648-1658
[129]Guohong Cao. Proactive Power-Aware Cache Management for Mobile Computing Systems. IEEE Transactions On Computers,2002,51(6):608-621
[130]Savvas Gitzenis, Nicholas Bambos. Joint Transmitter Power Control and Mobile Cache Management in Wireless Computing. IEEE Transactions on Mobile Computing,2008,7(4):498-512
[131]Bin Chen, Nong Xiao, Zhiping Cai, Ji Wang. DPM:A Demand-driven Virtual Disk Prefetch Mechanism for Mobile Personal Computing Environments.in:The Sixth IFIP International Conference on Network and Parallel Computing,2009.59-66
[132]Hong-Peng Wang, Tie-Jun Zhang, Xiao-Zong Yang. A Data Access Method In Mobile Computing Environment:Using Data Prefetch Technology. in:Parallel Control System Architecture.In:Proceedings of the Fifth International Conference on Machine Learning and Cybernetics, Dalian,2006.4425-4429
[133]Wai-Ho Au, Keith C.,C.Chan. Mining changes in association rules:a fuzzy approach. Fuzzy Sets and System,2005,149(1):87-104
[134]Liangzhong Yin, Guohong Cao, A Generalize Target-Driven Cache Replacement Policy for Mobile Environments. Journal of Parallel and Distributed Computing. 2005,65(5):583-594
[2]Tomasz Imielinski, S.Viswanathan, B.R.Badrinath. Power Efficient Filtering of Data on Air. in:Proceedings of the 4th International Conference on Extending Database Technology on Advances in Database Technology. Cambridge United Kingdom, 1994.245-258
[3]Tomasz Imielinski, S.Viswanathan, B.R.Badrinath. Energy Efficient Endexing on Air. ACM SIGMOD Record,1994,23(2):25-36
[4]Tomasz Imielinski, S.Viswanathan, B.R.Badrinath. Data on Air:Organization and Access. IEEE Transactions on Knowledge and Data Engneering,1997,9(3):353-372
[5]Dunham M H, Helal A. Mobile Computing and Databases:Anything New?. ACM SIGMOD Record,1995,24(4):5-9
[6]Jim Gray, Pat Helland, Patrick O'Neil et al. The Dangers of Replication and a Solution. in:Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data. J. Widom. SIGMOD '96. ACM. New York:ACM Press,1996.173-182.
[7]Jim Gray, Prakash Sundaresan, Susanne Englert et al. Quickly Generating Billion-Record Synthetic Databases. in:Proceedings of the 1994 ACM SIGMOD International Conference on Management of Data. Minnesota:ACM Press,1994. 243-252
[8]K.Stathatos, N.RoussoPoulos, J.S.Baras.Adaptive Data Broadcast in Hybrid Networks. in:Proeeedings of 23rd International Conference on Very Large DataBases. San Francisco:Morgan Kaufmann Publishers,1997.326-335
[9]J.X.Yu, T.sakata, K.Tan. Statistical Estimation of Access Frequencies in Data Broadcasting Environments. Wireless Networks,2000,6(2):89-98
[10]A.Carzaniga, D.S.Rosenblum, A.L.Wolf. Design and Evaluation of a Wide-Area Event Notification Service. ACM Transactions on Computer Systems,2001,19(3): 332-383
[11]P.T.Eugster, P.A.Felber, R.Guerraoui et al. The Many Faces of Publish/Subscribe. ACM Computing Surveys,2003,35(2):114-131
[12]Brian Babcock, Shivnath Babu, Mayur Datar,et al. Models and Issues in Data Stream Systems. In:Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems. Madison, Wisconsin:ACM PODS, 2002.1-16
[13]金澈清,钱卫宁,周傲英.流数据分析与管理综述.软件学报,2004,15(8)：1172-1181
[14]Gregory Piatetsky-Shapiro, Charles Connell. Accurate Estimation of the Number of Tuples Satisfying a Condition. In:International Conference on Management of Data Proceedings of the 1984 ACM SIGMOD international conference on Management of data. New York:ACM,1984.256-276
[15]Babcock B, Datar M, Motwani R, et al. Maintaining Variance and K-Medians over Data Stream Windows. in:Proceeding of the 22nd ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems. San Diego:ACM Press, 2003.234-243
[16]Datar M, Gionis A, Indyk P, Motwani R. Maintaining stream statistics over sliding windows. In:Eppstein D, ed. Proc. of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms. San Francisco:ACM/SIAM,2002.635-644
[17]Gibbons PB, Tirthapura S. Distributed streams algorithms for sliding windows. in: Proceeding of the 14th Annual ACM Symposium on Parallel Algorithms and Architectures. Winnipeg:ACM Press,2002.63-72
[18]AC Gilbert, Y.Kotidis, Muthukrishnan S, et al. Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries. in:Apers PMG, Atzeni P, Ceri S, et al eds. VLDB 2001, Proc. of the 27th International Conference on Very Large Data Bases. Roma:Morgan Kaufmann,2001.79-88
[19]Matias Y, Vitter JS, Wang M. Dynamic Maintenance of Wavelet-Based Histograms. in: Abbadi AE, Brodie ML, Chakravarthy S, et al, eds. VLDB 2000, Proc. of the 26th Int'l Conf. on Very Large Data Bases. Cairo:Morgan Kaufmann,2000.101-110
[20]J.S. Vitter. Random Sampling with a Reservoir. ACM Transactions on Mathematical Software (TOMS),1985,11(1):37-57.
[21]S.Chaudhuri, R.Motwani, V.Narasayya. On Random Sampling over Joins. in: Proceedings of the 1999 ACM SIGMOD International Conference on Management of Data,1999.263-274
[22]B.Babcock, M.Datar, R.Motwani, Sampling From a Moving Window over Streaming Data. in:Proceedings of The Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms,2002.633-634
[23]A.Das, J.Gehrke, M.Riedewald, Semantic Approximation of Data Stream Joins, IEEE Transactions on Knowledge and Data Engineering,2005,17(1):44-59
[24]P.Indyk, D.Woodruff. Optimal Approximations of The Frequency Moments of Data Streams, in:Proceedings of The Thirty-Seventh Annual ACM Symposium on Theory of Computing,2005.202-208
[25]C.Aggarwal. On Biased Reservoir Sampling in The Presence of Stream Evolution. in: Proceedings of The 32nd International Conference on Very Large Data Bases,2006. 607-618
[26]G. Cormode and S. Muthukrishnan. An Improved Data Stream Summary:The Count-Min Sketch and Its Applications. Algorithms Journal,2005,55(1):58-75
[27]Vladimir Braverman, Rafail Ostrovsky, Carlo Zaniolo. Optimal Sampling from Sliding Windows in:Proceedings of the 28th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems.2009.147-156
[28]Agrawal, R., Srikant, R. Fast Algorithms for Mining Association Rules. in: Proceeding of the 1994 International Conference Very Large Data Bases (VLDB'94),1994.487-499.
[29]Han, J.,Pei, J., Yin, Y. Mining Frequent Patterns Without Candidate Generation.in: Proceeding of 2000 ACM-SIGMOD International Conference Management of Data (SIGMOD'00),2000.1-12.
[30]Pei, J., Han, J.,Mao, R. CLOSET:An Efficient Algorithm for Mining Frequent Closed Itemsets. in:Proc.2000 ACM-SIGMOD Int.Workshop Data Mining and Knowledge Discovery (DMKD'00),2000.11-20
[31]Zaki, M. J., Hsiao, C. J. CHARM:An Effcient Algorithm for Closed Itemset Mining. in:Proceeding SIAM International Conference of Data Mining,2002.457.473.
[32]Muthukrishnan,S.Data streams:algorithms and applications.in:ACM-SIAM Symposium on Discrete Algorithms,2003.20-22
[33]Cormode G.., Korn F., Muthukrishnan, S., et al.Holistic UDAFs at Streaming Speeds. in:ACM SIGMOD International Conference on Management of Data,2004.35-46
[34]Pike, R., Dorward, S., Griesemer, et al. Interpreting the Data:Parallel Analysis with Sawzall. Grids World.2005,13(4):277-298
[35]Manku, G., Motwani, R. Approximate Frequency Counts over Data Streams. in: International Conference on Very Large Data Bases,2002.346-357
[36]A.Chakrabarti, GCormode, A.McGregor. A Near-Optimal Algorithm for Computing the Entropy of a Stream. in:Proceedings of ACM-SIAM Symposium on Discrete Algorithms,2007.328-335
[37]Arasu, A., Manku, G.S. Approximate Counts and Quantiles Over Sliding Windows. in: Proceedings of the Twenty-third ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems,2004.286-296
[38]Datar M., Gionis A., Indyk, P., et al. Maintaining Stream Statistics Over Sliding Windows.in:ACM-SIAM Symposium on Discrete Algorithms,2002.635-644
[39]Lee, L., Ting, H. A Simpler And More Efficient Deterministic Scheme For Finding Frequent Items Over Sliding Windows. in:Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of Database Systems,2006.290-297
[40]Jayram T.S., McGregor A. Muthukrishnan S., et al. Estimating Statistical Aggregates on Probabilistic Data Streams. in:Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems,2007.243-252
[41]Boyer R.S., Moore, J. A fast majority vote algorithm. Technical Report ICSCA-CMP-32, Institute for Computer Science, University of Texas,1981.59-62
[42]Fischer M., Salzburg, S. Finding a Majority Among N Votes:Solution to Problem, J. Algorithms,1982,3(4):376-379
[43]Boyer R.S., Moore,J.S. MJRTY-a Fast Majority Vote Algorithm.in:Automated Reasoning:Essays in Honor of Woody Bledsoe,Automated Reasoning Series,1991. 105-117
[44]Demaine E., Lopez-Ortiz A., Munro J.I. Frequency Estimation of Internet Packet Streams With Limited Space. in:European Symposium on Algorithms,2002.348-360
[45]Karp R., Papadimitriou C., Shenker S. A Simple Algorithm for Finding Frequent Elements in Sets and Bags. ACM Transaction Database System,2003,28(2):51-55.
[46]Bose P., Kranakis E., Morin P., et al. Bounds for frequency estimation of packet streams. in:Proceedings of SIROCCO (2003),2003.33-42
[47]Manku G., Motwani R. Approximate Frequency Counts Over Data Streams. in: International Conference on Very Large Data Bases,2002.346-357
[48]Manku G.S. Frequency counts over data streams. http://www.cse.ust.hk/～/S10P03.ppt
[49]Metwally A.,Agrawal D., Abbadi A.E. Efficient Computation Of Frequent And Top-K Elements in Data Streams. in:International Conference on Database Theory,2005.398-412
[50]Greenwald M., Khanna S. Space-efficient online computation of quantile summaries. in:ACM SIGMOD International Conference on Management of Data,2001.58-66
[51]Shrivastava N., Buragohain C., Agrawal D. et al. Medians and beyond:new aggregation techniques for sensor networks.in:Proceedings of the 2nd international conference on Embedded networked sensor systems,2004.239-249
[52]Hershberger J., Shrivastava N., Suri S., et al. Adaptive spatial partitioning for multidimensional data streams. Algorithmica,2004,46(1):97-117
[53]Cormode G., Korn F., Muthukrishnan S., et al. Spaceand time-efficient deterministic algorithms for biased quantiles over data streams. in:Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, 2006.263-272
[54]Charikar M., Chen K., Farach-Colton M. Finding frequent items in data streams. in: Procedings of the International Colloquium on Automata, Languages and Programming (ICALP),2002.693-703
[55]Cormode G., Muthukrishnan S. An improved data stream summary:the count-min sketch and its applications. J. Algorithms,2005,55(1):,58-75
[56]Cormode G., Muthukrishnan S. What's new:Finding significant differences in network data streams. in:INFOCOM 2004. Twenty-third AnnualJoint Conference of the IEEE Computer and Communications Societies,2004.1534-1545
[57]Schweller R., Li Z., Chen, Y., et al. Reversible sketches:enabling monitoring and analysis over high-speed data streams. IEEE Transanction of Netw. 2007,15(5):1059-1072
[58]Dobra A., Rusu F. Statistical analysis of sketch estimators. in:ACMSIGMOD International Conference on Management of Data,2007.187-198
[59]Graham Cormodem, Marios Hadjieleftheriou. Methods for finding frequent items in data streams. The VLDB Journal,2010,19(1):3-20
[60]严蔚敏,吴伟民.数据结构.(第二版).北京：清华大学出版社,1992.255-278
[61]E.horowitz, S.Sahni. Fundamentals and Data Structures.Washington:Pitmen Publishing Limited.1976.387-391
[62]D.E.Knuth. The Art of Computer Programming, Vol1:Fundamental Algorithms(3th). Addison-Wesley Publishing Company.1998.401-407
[63]D.E.Knuth. The Art of Computer Programming, Vol3:Sorting and Searching(2ed). Addison-Wesley Publishing Company.1996.388-393
[64]Jin C., Qian W., Sha C., et al. Zhou A. Dynamically maintaining frequent items over a data stream. In:Proc. of the 2003 ACM CIKM Int'l Conf. on Information and Knowledge Management. New Orleans:ACM Press,2003.287-294.
[65]http://ita.ee.lbl.gov/html/traces.html
[66]Swarup Acharya,Michael Franklin,Stanley Zdonik.Balancing Push and Pull for Data Broadcast.in:Proceedings of the 1997 ACM SIGMOD international conference on Management of data,1997.183-194
[67]Swarup Acharya, Rafael Alonso,Michael Franklin,et al. Broadcast Disks:Data Management for Asymmetric Communication Environments. in:Proceedings of the ACM SIGMOD Conference, San Jose, CA,1995.199-210
[68]John W. Wong, Broadcast Delivery. Proceedings of the IEEE,1988,76(12):1566-1577
[69]Chi-Jiun Su, Leandros Tassiulas. Broadcast Scheduling for Information Distribution. In:Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies.1997.109-117
[70]S. Hameed and N.H.Vaidya. Efficient algorithms for scheduling data broadcast. ACM/Baltzer Jounral of Wireless Networks,1999,5(3):183-193
[71]N.H.Vaidya and S. Hameed. Scheduling data broadcast in asymmetric communication environments.ACM/Baltzer Jounral of Wireless Networks,1999,5(3):171-182
[72]吴海,石磊,卢炎生.实时环境下一种混合广播调度策略.计算机科学,2009,36(5)： 158-162
[73]Swarup Acharya, S.Muthukrishnan, Scheduling on-demand broadcasts. in:The fourth annual ACM/IEEE international conference on Mobile computing and networking, Dallas,Texas,1998.43-54
[74]D.Aksoy, M.Franklin. Scheduling for large scale on-demand data broadcast.in: Proc.of IEEE INFOCOM, San Francisco,1998.651-659
[75]Bender M.A., Chakrabarti S., Muthukrishnan S. Flow and stretch metrics for scheduling continuous job streams. in:Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms. San Francisco,1998.270-279
[76]Aksoy D., Franklin M. RxW:a scheduling approach for large-scale on-demand broadcast. IEEE/ACM Transactions on Networking,1999,7(6):846-860
[77]Acharya S., Alonso R., Franklin M., et al. Broadcast disks:data management for asymmetric communication environments. in:Proc of ACM SIGMOD Conf. San Jose, California,1995.199-210
[78]孙未未,施伟斌,施伯乐.移动计算环境中数据广播访问时间优化算法.小型微型计算机系统,2003,3(24)：577-579
[79]Sun Wei Wei, Shi Wei Bin, Shi Bo Le. A cost efficient scheduling algorithm of on-demand broadcasts. Wireless Networks,2003,9(3):239-247
[80]Xuan P., Sen S., Gonzalez O., et al. Broadcast on-demand:efficient and timely dissemination of data in mobile environments. in:Proc of the 3rd IEEE Real-Time Technology and Applications Symposium. Montreal, Canada,1997.38-48
[81]Jesus F.C., Ramamritham K. Adaptive dissemination of data in time-critical asymmetric communication environments. Mobile Networks and Applications,2004, 9(5):491-505
[82]Hu J.H., Yeung K.L., Feng G., et al. A novel push-and-pull hybrid data broadcast scheme for wireless information networks.in:Proc of 2000 IEEE Int Conf on Communications,2000.1778-1782
[83]Lee W.C., Hu Q.L., and Lee D.L. A study of channel allocation methods for data dissemination in mobile computing environments. ACM/Baltzer Journal of Mobile Networks and Applications (MONET),1999,4(2):117-129
[84]John A. Stankovic, Marco Spuri, Krithi Ramamritham, et al.Deadline Scheduling for Real-Time Systems-EDF and Related Algorithms. Springer Press,1998,187-189
[85]刘云生,杨进才,廖国琼.移动环境中实时事务数据的广播调度.小型微型计算机系统,2004,25(4)：1534-1537
[86]C.L. Hu, M.S. Chen. Dynamic data broadcasting with traffic awareness, in: Proceedings of the 22nd IEEE International Conference on Distributed Computing Systems (ICDCS'02),2002.112-119
[87]C.L. Hu, M.S. Chen. On-line scheduling sequential objects for dynamic information dissemination. in:Proceedings of 2005 IEEE Global Communications Conference (GLOBECOM'05),2005.105-110
[88]Chin-Lin Hu. Fair Scheduling for On-Demand Time-Critical Data Broadcast. in:ICC '07. IEEE International Conference on Communications.2007.5832-5835
[89]朱香元,李仁发,杨胜,江文.基于优先级的数据广播内容选择算法.计算机工程与应用,2006,42(33)：147-149
[90]Xiao Wu, Victor C.S.Lee, Joseph Kee-Yin Ng. A Preemptive Scheduling Algorithm for Wireless Real-Time On-Demand Data Broadcast. in:Proceedings of the 11th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA'05),2005.18-20
[91]Rinku Dewri, Indrakshi Ray, Indrajit Ray et al. Optimizing on-demand data broadcast scheduling in pervasive environments.in:Proceedings of the 11th international conference on Extending database technology. Nantes, France.2008.559-569
[92]J.Xu, X.Tang,W.Lee. Time-critical on-demand data broadcast:Algorithms, analysis, and performance evaluation. IEEE Transactions on Parallel and Distributed Systems, 2006,17(1):3-14
[93]Victor C.S.Lee,Xiao Wu and Joseph Kee-Yin Ng. Scheduling real-time requests in on-demand data broadcast environments.Real-Time Systems,2006,34(2):83-99
[94]Majid Raissi-Dehkordi, John S.Baras. Broadcast Scheduling for Time-Constrained Information Delivery. in:IEEE GLOBECOM 2007 proceedings,2007.5299-5301
[95]Chung Y.D., Kim M.H. QEM:a scheduling method for wireless broadcast data. in: Proceedings of the 6th Int Conf on Database Systems for Advanced Applications, 1999.135-142
[96]G.Lee, M.S.Yeh, S.C.Lo,et al. A Strategy for Efficient Access of Mulitiple Data Items in Mobile Environment. in:Proc. of the 3rd IEEE Int. Conf. on Mobile Data Management2002.71-78
[97]Chang Y.I., Hsieh W.H. An efficient scheduling method for query-set-based broadcasting in mobile environments. in:Proc of the 24th Int Conf on Distributed Computing Systems Workshops,2004.478-483
[98]Lee G.L., Lo S.C. Broadcast data allocation for efficient access of multiple data items in mobile environments. Mobile Networks and Applications,2003,8(4):365-375
[99]Huang J.L., Chen M.S. Dependent data broadcasting for unordered queries in a multiple channel mobile environment. IEEE Transactions on Knowledge and Data Engineering,2004,16(9):1143-1156
[100]Lien-Fa Lin, Chao-Chun Chen,Chiang Lee. Benefit-oriented data retrieval in data broadcast environments. Wireless Networks,2010,16(1):1-15
[101]Peng Wen Chih, Chen Ming Syan. Design and performance studies of an adaptive cache retrieval scheme in a mobile computing environment. IEEE Transactions on Mobile Computing.2005,4(1):29-40
[102]Gray J., Prakash Sundaresan, Susanne Englert, et al.Quickly Generating Billion-Record Synthetic Databases. in:Proc of the 1994 ACM SIGMOD. Minneapolis, Minnesota,1994.243-252
[103]Ming-Syan Chen, Kun-Lung Wu, Philip S.Yu. Optimizing Index Allocation for Sequential Data Broadcasting in Wireless Mobile Computing. IEEE Transactions On Knowledge and Data Engineering,2003,15(1):161-173
[104]Yon Dohn Chung, Myoung Ho Kim. An index replication scheme for wireless data broadcasting. The Journal of Systems and Software,2000,51(3):191-199
[105]Lo, S.C., Chen, A.L.P. An adaptive access method for broadcast data under an error-prone mobile nvironment. IEEE Transactions on Knowledge and Data Engineering,2000,12(4):609-620
[106]Jun-Hong Shen, Ye-In Chang. A Skewed Distributed Indexing for Skewed Access Patterns on The Wireless Broadcast. The Journal of Systems and Software,2007,80(5):711-723
[107]W.C.Lee, D.L.Lee.Using Signature Techniques for Information Filtering in Wireless and Mobile Environments. Journal of Distributed and Parallel Databases (DPDB), 1996,4(3):205-227
[108]W.C. Lee, D.L. Lee. Signature Caching Techniques for Information Filtering in Wireless Environments. ACM Wireless Networks,1999,4(1):57-67
[109]J.Xu, D.L.Lee, Q. Hu et al. Data Boradcast Handbook of Wierless Networks and Mobile Computing.,New York:JohnWiley& Sons,2002,243-265.
[110]Xu Yang, Athman Bouguettaye. Using a Hybrid Method for Accessing Broadcast Data. in:Proceedings of the 6th international conference on Mobile data management,2005.38-42
[111]李国徽,唐向红.移动环境下数据广播中的混合索引技术.计算机应用研究,2007,24(6)：315-316
[112]Qinglong Hu, Wang-Chien Lee, Dik Lun Lee. A Hybrid Index Technique for Power Efficient Data Broadcast. Distributed and Parallel Databases,2001,9(2):151-177
[113]Donald E. Knuth The Art of Computer Programming, Vol 2 Seminumerical algorithms(3rd Edition). Addison Wesley Longman,1998.405-423
[114]Alfred V.Aho, John E.Hopcroft, Jeffrey D.Ullman. The Design and Analysis of Computer Algorithms(2ed Edition). Addison Wesley Longman,2005.69-74
[115]严蔚敏,吴伟民.数据结构.第二版.北京：清华大学出版社,2003.222-225
[116]Hui Song, Guohong Cao. Cache-Miss-Initiated Prefetch in Mobile Environments. in:Proceedings of the 2004 IEEE International Conference on Mobile Data Management (MDM'04).2004.370-381
[117]G. Cao. A Scalable Low-Latency Cache Invalidation Strategy for Mobile Environments. IEEE Transactions on Knowledge and Data Engineering, 2003,15(5):1251-1265
[118]Wen-Chih Peng, Ming-Syan Chen. Design and Performance Studies of an Adaptive Cache Retrieval Scheme in a Mobile Computing Environment. IEEE Transactions On Mobile Computing,2005,4(1):29-40
[119]Chiranjeev Kumar, GR.Madhuri, Shweta Agrawal.Efficient Bandwidth Utilization in Mobile Environments for Temporal Based Cache Invalidation. in:TENCON 2008 IEEE Region 10 Conference.Hyderabad.2008.1-5
[120]Huaping Shen, Mohan Kumar, Sajal K. Das, et al.Energy-Efficient Caching and Prefetching with Data Consistency in Mobile Distributed Systems.in:Proceedings of the 18th International Parallel and Distributed Processing Symposium (IPDPS'04). 2004.67-76
[121]L. Fan, P. Cao, W. Lin, and Q. Jacobson, Web Prefetching Between Low-Bandwidth Clients and Proxies:Potential and Performance. in:Proceedings of the ACM SIGMETRICS Conference,1999.178-187
[122]S. Gitzenis, N. Bambos. Power-Controlled Data Prefetching/Caching inWireless Packet Networks. in:Proceedings of IEEE INFOCOM 2002,New York,2002.1405-1414
[123]G Cao. Proactive Power-Aware Cache Management for Mobile Computing Systems. IEEE Transactions on Computers,2002,51(6):608-621
[124]Z. Wang, S. K. Das, H. Che et al. SACCS:Scalable Asynchronous Cache Consistency Scheme.in:Proceedings of ICDCS Internation Workshop on Mobile Wireless Networks,2003.797-802
[125]Z. Wang, M. Kumar, S. K. Das et al. Investigation of Cache Maintenance Strategies for Multi-Cell Environments. in:International Conference on Mobile Data Management (MDM),2003.29-44
[126]李国徽,杨兵,陈辉等.移动环境下支持实时事务处理的数据预取.计算机学报,2008,31(10)：1841-1847
[127]Liangzhong Yin, Guohong Cao, Chita Das et al. Power-Aware Prefetch in Mobile Environments.in:Proceedings of the 22 nd International Conference on Distributed Computing Systems (ICDCS'02).2002.571-578
[128]Liangzhong Yin, Guohong Cao.Adaptive Power-Aware Prefetch inWireless Networks.IEEE Transactions on Wireless Communications,2004,3(5):1648-1658
[129]Guohong Cao. Proactive Power-Aware Cache Management for Mobile Computing Systems. IEEE Transactions On Computers,2002,51(6):608-621
[130]Savvas Gitzenis, Nicholas Bambos. Joint Transmitter Power Control and Mobile Cache Management in Wireless Computing. IEEE Transactions on Mobile Computing,2008,7(4):498-512
[131]Bin Chen, Nong Xiao, Zhiping Cai, Ji Wang. DPM:A Demand-driven Virtual Disk Prefetch Mechanism for Mobile Personal Computing Environments.in:The Sixth IFIP International Conference on Network and Parallel Computing,2009.59-66
[132]Hong-Peng Wang, Tie-Jun Zhang, Xiao-Zong Yang. A Data Access Method In Mobile Computing Environment:Using Data Prefetch Technology. in:Parallel Control System Architecture.In:Proceedings of the Fifth International Conference on Machine Learning and Cybernetics, Dalian,2006.4425-4429
[133]Wai-Ho Au, Keith C.,C.Chan. Mining changes in association rules:a fuzzy approach. Fuzzy Sets and System,2005,149(1):87-104
[134]Liangzhong Yin, Guohong Cao, A Generalize Target-Driven Cache Replacement Policy for Mobile Environments. Journal of Parallel and Distributed Computing. 2005,65(5):583-594