Out-of-order event processing in kinetic data structures

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

  • Mohammad Abam, Denmark
  • Mark de Berg, Tue, Netherlands
  • Pankaj Agrawal, Duke, United States
  • Hai Yu, Duke, United States
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
Original languageEnglish
JournalAlgorithmica
Volume60
Issue2
Pages (from-to)250-273
Number of pages24
ISSN0178-4617
DOIs
Publication statusPublished - 2011

See relations at Aarhus University Citationformats

ID: 17920021