作者：曹斌; 侯晨煜; 范菁; 程时伟; 邱杰凡时态数据库查询服务最优时间窗口覆盖时间区间timelineindex
摘要：该文提出了最优时间窗口覆盖查询问题,该问题是指给定多个用户和对应的时间区间以及持续时间大小的要求,希望找到既满足持续时间大小要求又能够被最多用户覆盖的时间区间段.该问题的解决能够为现实生活 提供多种服务,比如：安排直播时段、云服务收费等.根据我们的调查发现,该问题属于时态数据库领域, 但是与现有的时态数据库领域问题都不一样,导致目前没有现成的方法能够直接解决最优时间窗口覆盖问题.该文针对该问题设计了一种算法——基于Timeline Index的查询算法（TLI算法）,该算法利用Timeline Index数据结构存储原始数据信息.再通过Timeline Index利用相邻的时间点构造多个时间区间,对于不满足时间大小的时间区间,我们设计了专门的调整机制使它们变成新的满足要求的时间区间.我们通过理论证明该算法的时间复杂度 O（N log N ）,其中 N 是原始数据中记录的数量.最后通过实验分析,发现TLI 算法的运行效率比基准算法普遍快了1个数量级.
注：因版权方要求，不能公开全文，如需全文，请咨询杂志社
