Idioma:

Out-of-Order Event Processing in Kinetic Data Structures

Abam, Mohammad Ali ; Agarwal, Pankaj K. ; de Berg, Mark ; Yu, Hai Erlebach, Thomas ; Azar, Yossi

Algorithms – ESA 2006, 2006, p.624-635 [Periódico revisado por pares]

Sem texto completo

Citações Citado por

Título:
Out-of-Order Event Processing in Kinetic Data Structures
Autor: Abam, Mohammad Ali ; Agarwal, Pankaj K. ; de Berg, Mark ; Yu, Hai
Erlebach, Thomas ; Azar, Yossi
Assuntos: Algorithmics. Computability. Computer arithmetics ; Applied sciences ; Computer science; control theory; systems ; Delaunay Triangulation ; Event Processing ; Event Time ; Exact sciences and technology ; Failure Time ; Geometric Error ; Theoretical computing
É parte de: Algorithms – ESA 2006, 2006, p.624-635
Descrição: 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.
Títulos relacionados: Lecture Notes in Computer Science
Editor: Berlin, Heidelberg: Springer Berlin Heidelberg
Idioma: Inglês

Links

Voltar para lista de resultados

Anterior Resultado 2 Avançar Ir para próxima página