A Kinetic Tournament is a kinetic data structure that functions as a

priority queue In computer science, a priority queue is an abstract data-type similar to a regular queue or stack data structure in which each element additionally has a ''priority'' associated with it. In a priority queue, an element with high priority is se ...

for elements whose priorities change as a continuous function of time. It is implemented analogously to a "tournament" between elements to determine the "winner" (maximum or minimum element), with the certificates enforcing the winner of each "match" in the tournament. It supports the usual priority queue operations - ''insert'', ''delete'' and ''find-max''. They are often used as components of other kinetic data structures, such as

kinetic closest pair A kinetic closest pair data structure is a kinetic data structure that maintains the closest pair of points, given a set ''P'' of ''n'' points that are moving continuously with time in a metric space. While many Kinetic data structure#Performance, ...

Implementation

A kinetic tournament is organized in a

binary tree In computer science, a binary tree is a k-ary k = 2 tree data structure in which each node has at most two children, which are referred to as the ' and the '. A recursive definition using just set theory notions is that a (non-empty) binar ...

-like structure, where the leaves contain the elements, and each

internal node In computer science, a tree is a widely used abstract data type that represents a hierarchical tree structure with a set of connected nodes. Each node in the tree can be connected to many children (depending on the type of tree), but must be con ...

contains the larger (or smaller) of the elements in its child nodes. Thus, the

root In vascular plants, the roots are the organs of a plant that are modified to provide anchorage for the plant and take in water and nutrients into the plant body, which allows plants to grow taller and faster. They are most often below the sur ...

of the tree contains the maximum (or minimum) element at a given time. The validity of the structure is enforced by creating a certificate at each node, which asserts that the element in the node is the larger of the two children. When this certificate fails, the element at the node is changed (to be the element in the other child), and a new certificate representing the new invariant is created. If the element this node was a winner at its parent node, then the element and certificates at the parent must be recursively updated too.

Analysis

This is a O(''n'') space, responsive, local, compact and efficient data-structure. *

Responsiveness Responsiveness as a concept of computer science refers to the specific ability of a system or functional unit to complete assigned tasks within a given time. For example, it would refer to the ability of an artificial intelligence system to unde ...

: A certificate failure will cause the creation of a new certificate to replace the old one, which must be put into the

event queue In computer science, message queues and mailboxes are software-engineering components typically used for inter-process communication (IPC), or for inter-thread communication within the same process. They use a queue for messaging – th ...

. It may also trigger changes to the O(log''n'') certificates at its parent nodes. Each certificate change requires a delete and insert operation in the priority queue of events. Each of these takes O(log ''n'') time, so the responsiveness, the total time required to process a certificate failure, is

O(\lg^2 n)

. While this is considered responsive in general, it is less responsive than other kinetic priority queues such as

kinetic heap A Kinetic Heap is a kinetic data structure, obtained by the kinetization of a heap. It is designed to store elements (keys associated with priorities) where the priority is changing as a continuous function of time. As a type of kinetic priority ...

s which respond to certificate failures with O(1) certificate changes. *

Locality Locality may refer to: * Locality (association), an association of community regeneration organizations in England * Locality (linguistics) * Locality (settlement) * Suburbs and localities (Australia), in which a locality is a geographic subdivi ...

: Each element is involved in O(log''n'') certificates (for example, the maximal element is involved in a certificate at each of its parents all the way up to the root node). Again, while this is considered local, a

is much more local. *

Compactness In mathematics, specifically general topology, compactness is a property that seeks to generalize the notion of a closed and bounded subset of Euclidean space by making precise the idea of a space having no "punctures" or "missing endpoints", i ...

: This is a very compact structure, containing O(''n'') certificates - exactly one for every edge in the tree. * Efficiency: Kinetic heaps are very efficient, with the number of internal events (certificate changes) being only a factor of O(log ''n'') more than the number of external events. Specifically, for a collection of space-time trajectories where each pair intersects at most times, the kinetic tournament processes events in time, where is a Davenport-Schinzel sequence. Additionally, insertions and deletions cause O(log''n'') certificate changes each. Each certificate change takes O(log''n'') time, which is determined by the time required to execute the event queue update.

References

{{Reflist * Basch, J. 1999. Kinetic data structures. Ph.D. thesis, Dept. Computer Science, Stanford University

Kinetic data structures