Out-of-order event processing in kinetic data structures

M.A. Abam, P.K. Agarwal, M. Berg, de, H. Yu

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

Samenvatting

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.
Originele taal-2Engels
TitelAlgorithms - ESA 2006 (Proceedings 14th Annual European Symposium, Zürich, Switzerland, September 11-13, 2006)
RedacteurenY. Azar, T. Erlebach
Plaats van productieBerlin
UitgeverijSpringer
Pagina's624-635
ISBN van geprinte versie3-540-38875-3
DOI's
StatusGepubliceerd - 2006

Publicatie series

NaamLecture Notes in Computer Science
Volume4168
ISSN van geprinte versie0302-9743

Vingerafdruk Duik in de onderzoeksthema's van 'Out-of-order event processing in kinetic data structures'. Samen vormen ze een unieke vingerafdruk.

Citeer dit