首页> 外文期刊>Algorithmica >Out-of-Order Event Processing in Kinetic Data Structures
【24h】

Out-of-Order Event Processing in Kinetic Data Structures

机译:动态数据结构中的无序事件处理

获取原文
获取原文并翻译 | 示例

摘要

We study the problem of designing kinetic data structures (KDS's for short) when event times cannot be computed exactly and events may be processed in a wrong order. In traditional KDS's this can lead to major inconsistencies from which the KDS cannot recover. We present more robust KDS's for the maintenance of several fundamental structures such as kinetic sorting and kinetic tournament trees, which overcome the difficulty by employing a refined event scheduling and processing technique. We prove that the new event scheduling mechanism leads to a KDS that is correct except for finitely many short time intervals. We analyze the maximum delay of events and the maximum error in the structure, and we experimentally compare our approach to the standard event scheduling mechanism.
机译:我们研究了设计动力学数据结构(简称KDS)的问题,因为事件时间无法准确计算,事件可能以错误的顺序处理。在传统的KDS中,这可能导致严重的不一致,KDS无法从中恢复。我们提出了更健壮的KDS,用于维护一些基本结构,例如动力学排序和动力学锦标赛树,它们通过采用改进的事件调度和处理技术克服了这一难题。我们证明,新的事件调度机制导致KDS正确,除了有限的短时间间隔。我们分析了事件的最大延迟和结构中的最大错误,并通过实验将我们的方法与标准事件调度机制进行了比较。

著录项

  • 来源
    《Algorithmica》 |2011年第2期|p.250-273|共24页
  • 作者单位

    MADALGO Center, Aarhus University, Aarhus, Denmark;

    Department of Computer Science, TU Eindhoven, Eindhoven, The Netherlands;

    Department of Computer Science, Duke University, Durham, NC 27708, USA;

    Department of Computer Science, Duke University, Durham, NC 27708, USA;

  • 收录信息 美国《科学引文索引》(SCI);美国《工程索引》(EI);
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类
  • 关键词

    Kinetic data structures; Robust computation;

    机译:动力学数据结构;稳健计算;

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号