Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke



Publications [#235487] of Pankaj K. Agarwal

Papers Published

  1. Abam, MA; Agarwal, PK; Berg, MD; Yu, H, Out-of-order event processing in kinetic data structures, Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4168 LNCS (2006), pp. 624-635, ISSN 0302-9743
    (last updated on 2018/11/20)

    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 two fundamental structures, kinetic sorting and 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. © Springer-Verlag Berlin Heidelberg 2006.
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320