基于马尔可夫预测模型的数据流滑动窗口近似连接缓存管理策略  

Markov-Model-Prediction-Based Buffer Management Policy for Approximate Join on Sliding Window over Data Stream

作　　者：李康宁[1] 卢艳民[1] 陈红[1] 

机构地区：[1]中国人民大学信息学院,北京,100872 中国人民大学数据工程与知识工程教育部重点实验室,北京,100872 　

出　　处：《计算机研究与发展》2006年第z3期130-136,共7页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(60273017);新世纪优秀人才支持计划基金项目;国家"八六三"高技术研究发展计划基金项目

摘　　要：数据流中数据是连续不断、无界、速度变化且以一种序列形式到达的.并且计算复杂关系操作(如连接)所需要的存储空间同样是无限的.许多查询无法得到精确的查询结果.于是高质量的近似查询结果是惟一的选择,即利用现有的缓存空间来优化滑动窗口上的操作以得到最好的近似结果.在很多应用中,缓存中的元组的价值可能不同.对于连接操作而言,一些元组会比另外一些更有利于产生连接结果.提出的基于马尔可夫预测模型的缓存管理策略MBPM充分利用了状态转换环境中的马尔可夫预测模型,并在此基础上提出了基于预测风险的缓存淘汰算法.实验证明,该算法相对于传统的缓存淘汰策略具有很好的性能.

关 键 词：数据流 滑动窗口 近似连接 缓存管理 马尔可夫模型 局部性 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]