Kinetic priority queue

A Kinetic Priority Queue is an abstract kinetic data structure. It is a variant of a priority queue designed to maintain the maximum (or minimum) priority element (key-value pair) when the priority of every element is changing as a continuous function of time. Kinetic priority queues have been used as components of several kinetic data structures, as well as to solve some important non-kinetic problems such as the k-set problem and the connected red blue segments intersection problem.

Implementations

The operations supported are:

$create-queue (q)$ : create an empty kinetic priority queue $q$
$find-max (q, t)$ (or find-min): - return the $max$ (or $min$ for a $min-queue$ ) value stored in the queue $q$ at the current virtual time $t$ .
$insert (X, f X, t)$ : - insert a key $X$ into the kinetic queue 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$ .

There are several variants of kinetic priority queues, which support the same basic operations but have different performance guarantees. Some of the most common implementations are kinetic heaps which are simple to implement but don't have tight theoretical performance bounds, and their randomized variants - kinetic heaters and kinetic hangers - which are easier to analyze. There is also a heap-like structure based on the dynamic convex hull data structure[1] which achieves better performance for affine motion of the priorities, but doesn't support curved trajectories. The kinetic tournament is another commonly used implementation. It achieves, deterministically, the same performance bounds as the heater or hanger, however it is less local and responsive than the heap-based data-structures.

Time complexities of kinetic priority queue implementations [2]
Trajectory of element priorities	Kinetic heap	Kinetic hanger, heater & tournament	Dynamic convex hull
Lines	$O(n\log ^{2}n)$	$O(n\log ^{2}n)$	$O(n\log n)$
Line segments	$O(m{\sqrt {n}}\log ^{\frac {3}{2}}n)$	$O(m\alpha (n)\log ^{2}n)$	$O(m\log n\log \log n)$
$δ$ -intersecting curves	$O(n^{2}\log n)$	$O(\lambda _{\delta }(n)\log n)$	n/a

Here, $\alpha (x)$ denotes the inverse Ackermann function. $\delta$ -intersecting curves refer to curves where each pair has at most $\delta$ intersections, and $\lambda _{\delta }(n)$ refers to a term in the Davenport-Schinzel sequence, which gives the maximum size of the upper envelope of $n$ $\delta -$ intersecting curves. $n$ is the largest number of elements in the queue at any given time, while $m$ refers to the total number of elements that are ever in the queue.

Applications

Kinetic priority queues are used as part of other kinetic data structures/algorithms such as kinetic closest pair, kinetic max-cut[3] or kinetic clustering.[4]

They can also be used to solve problems such as broadcast scheduling[5] or the connected red blue segments intersection problem.[6]

gollark: Except the actual U+0000 codepoint.

gollark: I don't think UTF-8 allows them.

gollark: I guess you might want it for aligning, but char length is technically wrong and you need (ÆÆÆÆÆÆÆÆÆÆÆÆÆÆÆÆÆÆÆÆÆAAAA) graphemes.

gollark: Unless you actually need *character* length, which you probably don't much, that should be fine really.

gollark: Or the accursed thing python does.

References

Brodal, G.S.; Jacob, R. (2002). "Dynamic planar convex hull". Proc. The 43rd Annual IEEE Symposium on Foundations of Computer Science. FCS. pp. 617–626. arXiv:1902.11169. doi:10.1109/SFCS.2002.1181985.
da Fonseca, Guilherme D. and de Figueiredo, Celina M. H. and Carvalho, Paulo C. P. "Kinetic hanger" (PDF). Information Processing Letters. pp. 151–157. Archived from the original (PDF) on May 24, 2015. Retrieved May 17, 2012.CS1 maint: multiple names: authors list (link)
Czumaj, Arthur; Frahling, Gereon; Sohler, Christian (2007). Efficient kinetic data structures for MaxCut (PDF). Canadian Conference on Computational Geometry. Retrieved May 17, 2012.
Li, Yifan; Han, Jiawei; Yang, Jiong. "Clustering moving objects". Proceedings of the tenth ACM SIGKDD international conference on knowledge discovery and data mining. SIGKDD. ACM. pp. 617–622.
K. H., Tarjan, R. and T. K. (2001). "Faster kinetic heaps and their use in broadcast scheduling". Proc. 12th ACM-SIAM Symposium on Discrete Algorithms. ACM. pp. 836–844. CiteSeerX 10.1.1.12.2739.CS1 maint: multiple names: authors list (link)
Basch, Julien; Guibas, Leonidas; Ramkumar, G. (1996). Reporting red-blue intersections between two sets of connected line segments. Springer Berlin / Heidelberg. CiteSeerX 10.1.1.55.98. doi:10.1007/3-540-61680-2_64. ISBN 978-3-540-61680-1.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[dch-1] Brodal, G.S.; Jacob, R. (2002). "Dynamic planar convex hull". Proc. The 43rd Annual IEEE Symposium on Foundations of Computer Science. FCS. pp. 617–626. arXiv:1902.11169. doi:10.1109/SFCS.2002.1181985.

[hanger-2] Fonseca, Guilherme D. and de Figueiredo, Celina M. H. and Carvalho, Paulo C. P. "Kinetic hanger" (PDF). Information Processing Letters. pp. 151–157. Archived from the original (PDF) on May 24, 2015. Retrieved May 17, 2012.CS1 maint: multiple names: authors list (link)

[max-cut-3] Czumaj, Arthur; Frahling, Gereon; Sohler, Christian (2007). Efficient kinetic data structures for MaxCut (PDF). Canadian Conference on Computational Geometry. Retrieved May 17, 2012.

[clustering-4] Li, Yifan; Han, Jiawei; Yang, Jiong. "Clustering moving objects". Proceedings of the tenth ACM SIGKDD international conference on knowledge discovery and data mining. SIGKDD. ACM. pp. 617–622.

[tarjan-5] K. H., Tarjan, R. and T. K. (2001). "Faster kinetic heaps and their use in broadcast scheduling". Proc. 12th ACM-SIAM Symposium on Discrete Algorithms. ACM. pp. 836–844. CiteSeerX 10.1.1.12.2739.CS1 maint: multiple names: authors list (link)

[red-blue-6] Basch, Julien; Guibas, Leonidas; Ramkumar, G. (1996). Reporting red-blue intersections between two sets of connected line segments. Springer Berlin / Heidelberg. CiteSeerX 10.1.1.55.98. doi:10.1007/3-540-61680-2_64. ISBN 978-3-540-61680-1.