Soft kinetic data structures
Artur Czumaj, Christian Sohler · 2001
We introduce the framework of soft kinetic data structures (SKDS). A soft kinetic data structure is an approximate data structure that can be used to answer queries on a set of moving objects with unpredictable motion. We analyze the quality of a soft kinetic data structure by giving a competitive analysis with respect to the dynamics of the system. We illustrate our approach by presenting soft kinetic data structures for maintaining classical data structures: sorted arrays, balanced search trees, heaps, and range trees. We also describe soft kinetic data structures for maintaining the Euclidean minimum spanning trees. 1 Introduction. The need of storing and processing continuously moving data arises in a broad variety of applications, including