Kinetic data structure

Kinetic data structures are used on systems where there is a set of values that are changing as a function of time, in a known fashion. So the system has some values, and for each value ${\displaystyle v}$, it is known that ${\displaystyle v=f(t)}$. Kinetic data structures allow queries on a system at the current virtual time ${\displaystyle t}$, and two additional operations:

• ${\displaystyle {\textrm {advance}}(t)}$: Advances the system to time ${\displaystyle t}$.
• ${\displaystyle {\textrm {change}}(v,f(t))}$: Alters the trajectory of value ${\displaystyle v}$ to ${\displaystyle f(t)}$, as of the current time.

Additional operations may be supported. For example, kinetic data structures are often used with a set of points. In this case, the structure typically allows points to be inserted and deleted.

A kinetic data structure allows the values stored in it to change continuously with time. In principle, this can be approximated by sampling the position of the points at fixed intervals of time, and deleting and re-inserting each point into a "static" (traditional) data structure. However, such an approach is vulnerable to oversampling or undersampling, depending on what interval of time is used, and can also be wasteful of computational resources.

The following general approach can be used to construct kinetic data structures:[5]

1. Store a data structure on the system at the current time ${\displaystyle t}$. This data structure allows queries on the system at the current virtual time.
2. Augment the data structure with certificates. Certificates are conditions under which the data structure is accurate. The certificates are all true now, and the data structure will only cease to be accurate when one of the certificates is no longer true.
3. Compute the failure time of each certificate, the time when it will cease to be true.
4. Store the certificates in a priority queue, keyed by their failure times
5. To advance to time ${\displaystyle t}$, look at the certificate with the lowest failure time from the priority queue. If the certificate fails before time ${\displaystyle t}$, pop it from the queue and fix the data structure so it is accurate at the time of failure, and update the certificates. Repeat this until the certificate with the lowest failure time in the priority queue fails after time ${\displaystyle t}$. If the certificate with the lowest failure time in the priority queue fails after time ${\displaystyle t}$, then all certificates are true at time ${\displaystyle t}$ so the data structure can correctly answer queries at time ${\displaystyle t}$.

When using the certificates approach, there are four measures of performance. We say a quantity is small if it is a polylogarithmic function of ${\displaystyle n}$, or is ${\displaystyle O(n^{\epsilon })}$ for arbitrarily small ${\displaystyle \epsilon }$, where ${\displaystyle n}$ is the number of objects:

The performance of a certain kinetic data structure may be analyzed for certain types of trajectories. Typically, the following types of trajectories are considered:

• Affine:(Linear functions) ${\displaystyle f(t)=at+b}$
• Bounded-degree algebraic:(Polynomial functions of bounded degree) ${\displaystyle f(t)=\sum _{i=0}^{n}a_{i}t^{i}}$ for some fixed ${\displaystyle n}$.
• Pseudo-algebraic: Trajectories such that any certificate of interest flips between true and false ${\displaystyle O(1)}$ times.

• Kinetic tournament
• Kinetic sorted list
• Kinetic heap
• Kinetic convex hull
• Kinetic closest pair
• Kinetic minimum spanning tree
• Kinetic Euclidean minimum spanning tree