User:Ringwith/Kinetic Tournament

A regular heap can be kinetized by augmenting with a certificate $(A>B)$ for every pair of nodes $A,\; B$ such that $B$ is a child node of $A$. If the value stored at a node $X$ is a function $f\_X(t)$ of time, then this certificate is only valid while $f\_A(t)\; >\; f\_B(t)$. Thus, the failure of this certificate must be scheduled in the event queue at a time $t$ such that $f\_B(t)\; =\; f\_A(t)$.

right

When a certificate $(A>B)$ fails, the data structure must swap $A$ and $B$, and update the other certificates that each of them was present in.

For example, if $B$ (call its child nodes $Y,Z$) was a child node of $A$ (call its child nodes$B,C$ and its parent node $X$), and the certificate

Thus, assuming non-degeneracy of the events (no two events happen at the same time), only a constant number of events need to be de-scheduled and re-scheduled even in the worst case.

A kinetic heap supports the following operations:

• $create-heap(h)$ - create an empty kinetic heap $h$
• $find-max(h,\; t)$ (or $find-min$) - return the $max$ (or $min$ for a $min-heap$) value stored in the heap $h$ at the current virtual time $t$
• $insert(X,f\_X,t)$ - insert a key $X$ into the kinetic heap at the current virtual time $t$, whose value changes as a continuous function $f\_X(t)$ of time $t$
• $delete(X,t)$ - delete a key $X$ at the current virtual time $t$

This article deals primarily with "simple" kinetic heaps as described above, but other variants have been developed for specialized applications, such as:

• Fibonacci kinetic heap
• Incremental kinetic heap

Other kinetic priority queues which require linear space and achieve similar performance bounds are:

• Kinetic Heater
• Kinetic Tournament
• Kinetic Hanger

Kinetic heaps perform well according to the four metrics (responsiveness, locality, efficiency and compactness) of kinetic data structure quality defined in Basch etc.

A kinetic heap is responsive, since each certificate failure causes the concerned keys to be swapped and leads to only five certificates being replaced in the worst case.

Each node is present in one certificate each along with its parent node and two child nodes (if present), meaning that each node can be involved in a total of three scheduled events in the worst case, thus kinetic heaps are local.

Each edge in the heap corresponds to exactly one scheduled event, therefore the number of scheduled events is exactly $n-1$ where $n$ is the number of nodes in the kinetic heap. Thus, kinetic heaps are compact.

The efficiency of a kinetic heap in the general case is largely unknown. However, in the special case of affine motion ($f(t)\; =\; at\; +\; b$) of the values, kinetic heaps are known to be very efficient.

In this special case, the maximum number of events processed by a kinetic heap can be shown to be exactly the number of edges in the transitive closure of the tree structure of the heap, which is $O(n\backslash log\; n)$ for a tree of height $O(\backslash log\; n)$.

If $n$ insertions and deletions are made on a kinetic heap that starts empty, the maximum number of events processed is $O(n\; \backslash sqrt\{n\backslash log\; n\})$. However, this bound is not believed to be tight, and the only known lower bound is $\backslash Omega(n\backslash log\; n)$.

Kinetic heaps have been used as part of many algorithms such as dynamic planar convex hull, clustering moving points and continuous nearest neighbor queries, as well as for applications such as broadcast scheduling.

{{Reflist}}

http://graphics.stanford.edu/projects/lgl/papers/g-KDS_DS-Handbook-04/g-KDS_DS-Handbook-04.pdf

http://www.uniriotec.br/~fonseca/kh.pdf

http://www.uniriotec.br/~fonseca/hanger.pdf

http://dl.acm.org/citation.cfm?id=314435

http://dl.acm.org/citation.cfm?id=263089

http://citeseer.ist.psu.edu/viewdoc/download?doi=10.1.1.41.2301&rep=rep1&type=pdf