计算机工程

作者：张航, 熊浩然, 何震瀛

单位：复旦大学计算机科学技术学院, 上海 200433

关键词：不确定时间序列,Top-<i>k</i>查询,窗口,聚合查询,有序列表,阈值

基金：国家重点研发计划(2021YFB3300502)

近年来, 如何分析挖掘不确定时间序列数据逐渐受到业界关注。Top-k查询作为数据库领域研究的热点问题, 旨在从大规模数据中检索出最符合用户查询条件的前k项结果。然而, 尽管Top-k查询在其他领域已被广泛应用, 针对不确定时间序列的Top-k查询研究仍然较少。这种查询可以有效帮助用户从不确定时间序列提取重要信息。提出一种新的Top-k查询问题——不确定时间序列Top-k窗口聚合查询, 并针对该问题给出高效的查询方法。这个查询可以作为一个基础工具, 辅助用户探索和分析不确定时间序列数据。现有能够支持这个查询的方法均存在查询效率较低或所需存储空间过高的问题。针对该问题, 提出一种基于子窗口拼接策略的两级Top-k查询方法, 并提出高效计算阈值上界方法解决基于子窗口拼接策略引入的阈值计算复杂难题。该方法能够以较少的预计算存储空间, 高效支持不确定时间序列Top-k窗口聚合查询。为了验证所提方法的有效性, 在真实和人造数据集上进行实验。实验结果表明, 所提方法与基于TA的Top-k查询方法相比, 明显降低了预计算列表的存储空间; 与基于遍历的FSEC-S方法相比, 所提方法以及使用计算阈值上界优化方法的平均查询效率分别提升了7.27倍和20.04倍。

来源：2025年第7期

《计算机工程》期刊编辑部

查看计算机工程杂志2025年第7期