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 queue, it maintains the maximum priority element stored in it. The kinetic heap data structure works by storing the elements as a tree that satisfies the following heap property - if B is a child node of A, then the priority of the element in A must be higher than the priority of the element in B. This heap property is enforced using certificates along every edge so, like other kinetic data structures, a kinetic heap also contains a priority queue (the event queue) to maintain certificate failure times.

Implementation and operations

A regular heap can be kinetized by augmenting with a certificate [A>B] for every pair of nodesA, B such that B is a child node of A. If the value stored at a node X is a function fX(t) of time, then this certificate is only valid while fA(t) > fB(t). Thus, the failure of this certificate must be scheduled in the event queue at a time t such that fA(t) > fB(t).

All certificate failures are scheduled on the "event queue", which is assumed to be an efficient priority queue whose operations take O(log n) time.

Dealing with certificate failures

When a certificate [A>B] fails, the data structure must swap A and B in the heap, and update the 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 nodesB,C and its parent node X), and the certificate [A>B] fails, then the data structure must swapB and A, then replace the old certificates (and the corresponding scheduled events) [A>B], [A<X], [A>C], [B>Y], [B>Z] with new certificates [B>A], [B<X], [B>C], [A>Y] and [A>Z].

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.

Operations

A kinetic heap supports the following operations:

Performance

Kinetic heaps perform well according to the four metrics (responsiveness, locality, compactness and efficiency) of kinetic data structure quality defined by Basch et al.[1] The analysis of the first three qualities is straightforward:

Analysis of efficiency

The efficiency of a kinetic heap in the general case is largely unknown.[1][2][3]However, in the special case of affine motion f(t) = at + b of the priorities, kinetic heaps are known to be very efficient.[2]

Affine motion, no insertions or deletions

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(nlogn) for a tree of height O(logn) [2]

Affine motion, with insertions and deletions

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

Variants

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

Other heap-like kinetic priority queues are:

References

  1. 1 2 Basch, J., Guibas, L. J., Hershberger, J (1997). "Data structures for mobile data". Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms. SODA. Society for Industrial and Applied Mathematics. pp. 747 –756. Retrieved May 17, 2012.
  2. 1 2 3 4 da Fonseca, Guilherme D. and de Figueiredo, Celina M. H. "Kinetic heap-ordered trees: Tight analysis and improved algorithms" (PDF). Information Processing Letters. pp. 165–169. Retrieved May 17, 2012.
  3. da Fonseca, Guilherme D. and de Figueiredo, Celina M. H. and Carvalho, Paulo C. P. "Kinetic hanger" (PDF). Information Processing Letters. pp. 151–157. Retrieved May 17, 2012.
  4. 1 2 Basch, J, Guibas, L. J., Ramkumar, G. D. (1997). "Sweeping lines and line segments with a heap". Proceedings of the thirteenth annual symposium on Computational geometry. SCG. ACM. pp. 469–471. Retrieved May 17, 2012.
  5. K. H., Tarjan, R. and T. K. (2001). "Faster kinetic heaps and their use in broadcast scheduling" (PDF). Proc. 12th ACM-SIAM Symposium on Discrete Algorithms. ACM. pp. 836–844. Retrieved May 17, 2012. line feed character in |title= at position 35 (help)

Guibas, Leonidas. "Kinetic Data Structures - Handbook" (PDF). Retrieved May 17, 2012. 

This article is issued from Wikipedia - version of the Wednesday, July 15, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.