en>BattyBot: fixed CS1 errors: dates & General fixes using AWB (9803)

2013-12-21T13:59:42Z

fixed CS1 errors: dates & General fixes using AWB (9803)

New page

[[File:Kinetic heap overview.png|right]]
A '''Kinetic Heap''' is a [[kinetic data structure]], obtained by the [[Kinetic data structure#Certificates Approach|kinetization]] of a [[heap (data structure)|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|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 {{math|<var>B</var>}} is a [[child node]] of {{math|<var>A</var>}}, then the priority of the element in {{math|<var>A</var>}} must be higher than the priority of the element in {{math|<var>B</var>}}. This heap property is enforced using [[kinetic data structure#Certificates Approach|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 [{{math|<var>A</var>><var>B</var>}}] for every pair of nodes{{math|<var>A</var>}}, {{math|<var>B</var>}} such that {{math|<var>B</var>}} is a child node of {{math|<var>A</var>}}. If the value stored at a node {{math|<var>X</var>}} is a function {{math|f<var>X</var>(<var>t</var>)}} of time, then this certificate is only valid while {{math|f<var>A</var>(<var>t</var>) > f<var>B</var>(<var>t</var>)}}. Thus, the failure of this certificate must be scheduled in the event queue at a time {{math|<var>t</var>}} such that {{math|f<var>A</var>(<var>t</var>) > f<var>B</var>(<var>t</var>)}}.

All certificate failures are scheduled on the "event queue", which is assumed to be an efficient priority queue whose operations take {{math|O(log <var>n</var>)}} time.

=== Dealing with certificate failures ===
[[File:Kinetic heap swap.png|right]]
When a certificate [{{math|<var>A</var>><var>B</var>}}] fails, the data structure must swap {{math|<var>A</var>}} and {{math|<var>B</var>}} in the heap, and update the certificates that each of them was present in.

For example, if <math>B</math> (call its [[child nodes]] <math>Y,Z</math>) was a child node of <math>A</math> (call its child nodes<math>B,C</math> and its [[parent node]] <math>X</math>), and the certificate [{{math|<var>A</var>><var>B</var>}}] fails, then the data structure must swap<math>B</math> and <math>A</math>, then replace the old certificates (and the corresponding scheduled events) [{{math|<var>A</var>><var>B</var>}}], [{{math|<var>A</var><<var>X</var>}}], [{{math|<var>A</var>><var>C</var>}}], [{{math|<var>B</var>><var>Y</var>}}], [{{math|<var>B</var>><var>Z</var>}}] with new certificates [{{math|<var>B</var>><var>A</var>}}], [{{math|<var>B</var><<var>X</var>}}], [{{math|<var>B</var>><var>C</var>}}], [{{math|<var>A</var>><var>Y</var>}}] and [{{math|<var>A</var>><var>Z</var>}}].

Thus, assuming [[Degeneracy (mathematics)|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:
* {{math|'''create-heap'''(<var>h</var>)}}: create an empty kinetic heap {{math|<var>h</var>}}
* {{math|'''find-max'''(<var>h, t</var>)}} (or '''find-min'''): - return the {{math|max}} (or {{math|min}} for a {{math|min-heap}}) value stored in the heap {{math|<var>h</var>}} at the current virtual time {{math|<var>t</var>}}.
* {{math|'''insert'''(<var>X</var>, f<var>X</var>, <var>t<var>)}}: - insert a key {{math|<var>X</var>}} into the kinetic heap at the current virtual time {{math|<var>t</var>}}, whose value changes as a continuous function {{math|f<var>X</var>(<var>t</var>)}} of time {{math|<var>t</var>}}. The insertion is done as in a normal heap in {{math|O(log <var>n</var>)}} time, but {{math|O(log <var>n</var>)}} certificates might need to be changed as a result, so the total time for rescheduling certificate failures is {{math|O(log 2 <var>n</var>)}}
* {{math|'''delete'''(<var>X</var>, <var>t</var>)}} - delete a key {{math||<var>X</var>}} at the current virtual time {{math|<var>t</var>}}. The deletion is done as in a normal heap in {{math|O(log <var>n</var>)}} time, but {{math|O(log <var>n</var>)}} certificates might need to be changed as a result, so the total time for rescheduling certificate failures is {{math|O(log 2 <var>n</var>)}}.

== Performance ==
Kinetic heaps perform well according to the four metrics ([[kinetic data structure#Performance|responsiveness]], [[kinetic data structure#Performance|locality]], [[kinetic data structure#Performance|compactness]] and [[kinetic data structure#Performance|efficiency]]) of kinetic data structure quality defined by Basch et al.<ref name="mobile"/> The analysis of the first three qualities is straightforward:
* '''[[kinetic data structure#Performance|Responsiveness]]:'''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.
* '''[[kinetic data structure#Performance|Locality]]:''' 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.
* '''[[kinetic data structure#Performance|Compactness]]:''' Each edge in the heap corresponds to exactly one scheduled event, therefore the number of scheduled events is exactly {{math||<var>n</var>-1}} where {{math|<var>n</var>}} is the number of nodes in the kinetic heap. Thus, kinetic heaps are compact.

=== Analysis of efficiency ===
The efficiency of a kinetic heap in the general case is largely unknown.<ref name="mobile"/><ref name="heap analysis"/><ref name="hanger"/>However, in the special case of [[Kinetic data structure#Types of Trajectories|affine motion]] {{math|f(<var>t</var>) {{=}} a<var>t</var> + b}} of the priorities, kinetic heaps are known to be very efficient.<ref name="heap analysis"/>

==== 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 {{math|O(<var>n</var>log<var>n</var>)}} for a tree of height {{math|O(log<var>n</var>)}} <ref name="heap analysis"/>

==== Affine motion, with insertions and deletions ====
If {{math|<var>n</var>}} insertions and deletions are made on a kinetic heap that starts empty, the maximum number of events processed is <math>O(n \sqrt{n\log n})</math>.<ref name="sweep"/> However, this bound is not believed to be tight,<ref name="heap analysis"/> and the only known lower bound is <math>\Omega(n\log n)</math>.<ref name="sweep"/>

== Variants ==
This article deals with "simple" kinetic heaps as described above, but other variants have been developed for specialized applications,<ref name="tarjan"/> such as:
* [[Fibonacci kinetic heap]]
* [[Incremental kinetic heap]]

Other heap-like kinetic priority queues are:
* [[Kinetic heater]]
* [[Kinetic hanger]]

== References ==
{{Reflist| refs=
<ref name="heap analysis">{{cite web | url=http://www.uniriotec.br/~fonseca/kh.pdf | title=Kinetic heap-ordered trees: Tight analysis and improved algorithms | publisher=Information Processing Letters | accessdate=May 17, 2012 | author=da Fonseca, Guilherme D. and de Figueiredo, Celina M. H. | pages=165–169}}</ref>
<ref name="hanger">
{{cite web | url=http://www.uniriotec.br/~fonseca/hanger.pdf | title=Kinetic hanger |publisher=Information Processing Letters | accessdate=May 17, 2012 | author=da Fonseca, Guilherme D. and de Figueiredo, Celina M. H. and Carvalho, Paulo C. P. | pages=151–157}}
</ref>
<ref name="mobile">
{{cite conference | url=http://dl.acm.org/citation.cfm?id=314435 | title=Data structures for mobile data | publisher=Society for Industrial and Applied Mathematics | accessdate=May 17, 2012 | author=Basch, J., Guibas, L. J., Hershberger, J | booktitle=Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms | year=1997 | conference=SODA | pages=747 -756}}
</ref>
<ref name="sweep">
{{cite conference | url=http://dl.acm.org/citation.cfm?id=263089 | title=Sweeping lines and line segments with a heap | publisher=ACM | accessdate=May 17, 2012 | author=Basch, J, Guibas, L. J., Ramkumar, G. D. | booktitle=Proceedings of the thirteenth annual symposium on Computational geometry | year=1997 | conference=SCG | pages=469-471}}
</ref>
<ref name="tarjan">

{{cite conference| url= | title = Faster kinetic heaps and their use
in broadcast scheduling | publisher=ACM | accessdate=May 17, 2012| author = K. H., Tarjan, R. and T. K. | booktitle=Proc. 12th ACM-SIAM Symposium on Discrete Algorithms |pages=836–844| year=2001}}
</ref>

}}
{{cite web |url=http://graphics.stanford.edu/projects/lgl/papers/g-KDS_DS-Handbook-04/g-KDS_DS-Handbook-04.pdf| title=Kinetic Data Structures - Handbook |accessdate=May 17, 2012 | author=Guibas, Leonidas}}


[[Category:Articles created via the Article Wizard]]
[[Category:Kinetic data structures]]
[[Category:Heaps (data structures)]]

Bioconcentration - Revision history

en>BattyBot: fixed CS1 errors: dates & General fixes using AWB (9803)