滑动窗口上数据流副本近似检测算法及其空间复杂度下界研究

项目名称： 滑动窗口上数据流副本近似检测算法及其空间复杂度下界研究

项目编号： No.61402008

项目类型： 青年科学基金项目

立项/批准年度： 2014

项目学科： 自动化技术、计算机技术

项目作者： 王修君

作者单位： 安徽工业大学

项目金额： 24万元

中文摘要： 滑动窗口上数据流副本近似检测算法是通过构建高效的内存摘要结构来存储当前滑动窗口中的数据信息，以达到仅需单遍扫描就能近似回答查询元素是否在当前窗口中出现的目的。本项目的研究内容为：基于通信复杂度理论，研究滑动窗口上副本近似检测问题的空间复杂度紧下界；基于随机过程理论，研究数据流摘要结构和近似检测算法。项目将从三个方面开展研究工作：给出任意一个确定性数据流副本近似检测算法所需空间的紧下界，前提条件是给定滑动窗口大小、用户允许的错误率、数据流元素和查询元素分布；设计出一种空间复杂度近似为紧下界的确定性数据流副本近似检测算法；设计出一种可以高效存储并返回非确定性数据流中概率信息的副本近似检测算法。本项目的理论结果将为衡量数据流副本检测算法的空间性能提供可靠的理论依据，本项目设计的算法可直接应用于网络数据检测系统中，能在节省存贮空间的同时提高检测的效率。

中文关键词： 数据流；副本近似检测；空间复杂度；下界；布隆过滤器

英文摘要： An approximate duplicate detection algorithm over sliding windows can only scan the data stream once. The algorithm needs to construct memory-efficient sketch structure to store the elements that occurs in the current sliding window. Based on the sketch s

英文关键词： data stream；approximated duplicate detectioin；space complexity；lower bound；Bloom filter