【摘 要】
：
频繁项查询在网络监控、网络入侵检测、关联规则挖掘等方面是一项非常重要的技术.该技术在静态的不确定数据中已经得到了深入的研究.但随着数据流特征和不确定性表现的日益明显，在不确定数据流环境下的查询已经成为一项新的研究课题.因此基于数据流普遍采用的滑动窗口模型，提出了一种高效的概率Top-K频繁项查询算法sTopK-UFI.该算法避免了每次窗口更新都重新计算查询答案，而是利用现有的计算结果进行增量更新，
【机 构】
：
Software College, Northeastern University, Shenyang 110819; School of Information Science and Engine
论文部分内容阅读
频繁项查询在网络监控、网络入侵检测、关联规则挖掘等方面是一项非常重要的技术.该技术在静态的不确定数据中已经得到了深入的研究.但随着数据流特征和不确定性表现的日益明显，在不确定数据流环境下的查询已经成为一项新的研究课题.因此基于数据流普遍采用的滑动窗口模型，提出了一种高效的概率Top-K频繁项查询算法sTopK-UFI.该算法避免了每次窗口更新都重新计算查询答案，而是利用现有的计算结果进行增量更新，从而减少查询代价.另外，该算法基于窗口中的现有数据对未来可能成为频繁项的元素进行预测，并利用泊松分布计算元素成为频繁项的概率上下界，提出相应的过滤策略，可以显著减少检测数据的数量，提高查询效率.实验结果表明，所提出算法可以有效地减少候选集、降低搜索空间、改善在不确定数据流上的查询性能.
其他文献
数据库外包是将数据库管理工作外包给专业第三方,而数据库外包中需要解决的关键问题之一是查询结果的验证。提出了外包追加型数据库的问题。根据外包追加型数据库的特点,在现有验证数据结构的基础上,提出了一种新型验证数据结构Min-Max Hash Tree,可以有效地解决客户对查询结果进行验证的问题。对于数据所有者端,给出了基本的数据发送算法；对于服务提供商端,分别给出了一次性查询和连续查询的查询算法和查询
集合相似连接(set similarity join)是指在给定的数据集中，按照基于集合间覆盖关系的相似度计算方法来衡量数据之间的相似度、并找出所有相似度不小于给定阈值的数据对的操作。集合相似连接作为一种新的基本操作在很多领域中有重要应用。随着社会网络、移动应用以及在线服务的发展，使得数据收集的效率和规模得到了很大的提高，同时给相似连接操作带来新的挑战。根据集合相似的必要条件，提出了相似集合之间的
物化是列存储数据仓库查询中必不可少的操作，物化策略和物化技术直接影响到查询执行的性能，因此设计一种适应于列存储系统的物化策略和相关技术尤为重要.针对延迟物化可能重复读取数据块的缺陷，提出了基于带值路径的物化技术，简称VPM.首先，定义了一个描述物理执行中间结果的结构——传递块，该结构将用于重构的位置信息与实际列值相分离.在此基础上，对于给定的物理查询树，根据其操作节点是否需要某一列的值进行路径标记
应用需求的发展衍生各种查询类型,Top-k查询是交互环境下一种重要查询类型。由于数据的不确定性,传统数据上的Top-k查询技术和方法不能直接应用于不确定数据查询。在已有不确定数据上Top-k查询算法的基础上,提出基于二叉树的不确定数据上Top-k查询算法BTreeU-Topk；为了提高算法执行效率,对二叉树进行修剪操作进而提出BTreeOPTU-Topk和BTreePU-Topk算法。实验结果表明
为用户缓存实视图可以有效提高其OLAP查询的性能。但是，已有的缓存管理策略由于没有考虑用户在进行OLAP分析时的数据访问特性，在处理实视图动态选择问题时无法获得好的性能。提出了视图路径和视图树的概念，并以视图树作为客户端缓存中的实视图组织方式。提出了“逆路径增长法”来快速计算新到达查询的视图路径，提高了查询的响应速度。对于视图树的动态调整问题，以“保留路径”为参照，设计了合理有效的视图替换策略。实
由于资源描述框架(resource description framework,RDF)具有表达灵活、简洁等优点,已被接受为表达元数据及万维网上数据互联的规范.近年来,其数据量在以飞快的速度增长.相应地,要求存储RDF数据的系统应具有高扩展性.介绍了一个高可扩展的RDF数据存储系统TripleBit.为尽可能降低存储空间消耗,采用了增量压缩和变长整数编码方法.并采用了数据分块的存储方法,既使得存储
针对索引维护时间和空间效率低的问题,提出了一种基于分配空间自学习的在线动态索引混合更新机制(on-line dynamic index hybrid update,ODIHU).ODIHU根据Zipf分布原理对长短列表数量分布进行估计,并采用基于历史分配空间的自适应学习机制对长短列表空间进行有效管理,然后对短列表采用立即合并更新方式,长列表采用上限Y相邻多路合并的更新方式维护,实现索引更新与查询性
指出不确定性和模糊性在时空语义上的区别；提出不确定移动对象的模糊时空范围查询问题，即查询条件中时间、空间范围的外延是模糊的，无清晰的边界，而目标对象的位置不确定；用模糊集表示模糊查询条件，概率密度函数表示移动对象在各自不确定区域内的可能位置分布；给出了不确定对象关于模糊查询条件匹配度的计算方法；设计了基于α截集的无效对象排除和有效对象确认规则及查询算法。算法规则适用于任意概率密度分布。现有的确定或
空间查询处理已经广泛地应用于基于位置的服务、设施选址等领域。提出一种新的空间查询：主题相关区域查询(topic-relevant region queries,T2R),该查询可以用于位置选址等空间决策分析。给定一个由空间特征对象集合R定义的主题T、查询窗口q,T2R查询返回不交叠的k个与主题最相关的区域,区域与主题的相关程度由区域内特征对象的数量结合其重要性进行计算。为了有效处理T2R查询,提出
近年来，图模型广泛应用于生物信息、计算化学、语义网等领域。目前，“过滤-验证”机制被广泛用于子图包含查询，即首先根据图数据的特征构造索引，然后根据索引产生候选集，最后对候选集中的每一个图进行子图同构验证。在这类算法中，“过滤”阶段是关注的重点，力争过滤掉更多的数据；而“验证”阶段则只是单纯地进行候选图子图同构检测，并没有进一步优化查询性能的可能。因此，提出了一种新的子图包含查询的迭代处理机制：“选