Structure de données cinétique

Les structures de données kinétiques sont utilisées sur des systèmes où il existe un ensemble de valeurs qui changent en fonction du temps, de manière connue et calculable. Donc, les valeurs du systèmes sont des fonctions du temps ${\displaystyle v=f(t)}$ . Les structures de données cinétiques permettent des requêtes sur un système pour n'importe quelle valeur du temps ${\displaystyle t}$, et deux opérations supplémentaires:

• ${\displaystyle {\textrm {advance}}(t)}$ : Avance le système au temps ${\displaystyle t}$ .
• ${\displaystyle {\textrm {change}}(v,f(t))}$ : Modifie la trajectoire de la valeur ${\displaystyle v}$ à ${\displaystyle f(t)}$, à partir de l'instant courantactuelle.

Des opérations supplémentaires peuvent être prises en charge. Par exemple, les structures de données kinétiques sont souvent utilisées sur des nuages de points. Dans ce cas, la structure permet également d'insérer et de supprimer des points.

Une structure de données kinétiques permet aux valeurs qui y sont stockées d'évoluer continuellement suivant le temps. En principe, cette évolution peut être approximée en échantillonnant la position des points à des intervalles de temps fixes, et en supprimant et en réinsérant chaque point dans une structure de données "statique" (traditionnelle). Cependant, une telle approche peut entrainer des problèmes de suréchantillonnage ou de sous-échantillonnage, suivant que le pas de temps choisi est trop petit ou trop grand, ce qui engendre des baisses de performances ou des problèmes de précision.

L'approche générale suivante peut être utilisée pour construire des structures de données cinétiques:

1. Initialiser une structure de données qui stocke les informations du système à l'instant ${\displaystyle t}$ . Cette structure de données permet des requêtes sur le système au temps courant.
2. Ajouter à la structure des données avec des certificats. Les certificats sont des conditions qui permettent d'affirmer que les données de la structure sont exactes. Tant que les certificats restent vrais, les informations de la structure sont fiables.
3. Calculez le temps d'échec de chaque certificat, le moment où il cessera d'être vrai.
4. Stockez les certificats dans une queue de priorité, en fonction de leurs instants d'échec
5. Pour avancer dans le temps ${\displaystyle t}$, il suffit de déterminer le certificat ayant l'instant d'échec le plus proche à partir de la queue de priorité. Si le certificat échoue avant l'heure ${\displaystyle t}$, il faut le sortir de la queue de priorité, et mettre a jour la structure des données afin qu'elle soit fiable au moment de l'échec, et mettez à jour les autres certificats. L'opération est a répéter jusqu'à ce que le certificat avec le temps d'échec le plus proche dans la file d'attente prioritaire atteigne le temps ${\displaystyle t}$ . Si le certificat avec le temps d'échec le plus bas dans la file d'attente prioritaire échoue avec le temps ${\displaystyle t}$, alors tous les certificats sont vrais à la fois ${\displaystyle t}$ afin que la structure de données puisse répondre correctement aux requêtes au temps ${\displaystyle t}$ .

Avec l'approche utilisant des certificats, il existe quatre mesures de la performance possibles. On dit qu'une quantité est petite si c'est une fonction polylogarithmique de ${\displaystyle n}$, ou encore si elle est en ${\displaystyle O(n^{\epsilon })}$ pour ${\displaystyle \epsilon }$ arbitrairement petit, où ${\displaystyle n}$ est le nombre d'objets:

Les performances d'une structure de données cinétiques peuvent être analysées pour certains types de trajectoires. En règle générale, les types de trajectoires suivants sont considérés:

• Affine : (fonctions linéaires)${\displaystyle f(t)=at+b}$
• Algébrique de degré borné : (Fonctions polynomiales de degré borné)${\displaystyle f(t)=\sum _{i=0}^{n}a_{i}t^{i}}$ pour certains fixes ${\displaystyle n}$ .
• Pseudo-algébrique : trajectoires telles que tout certificat d'intérêt bascule entre vrai et faux${\displaystyle O(1)}$ fois.

• Tournoi cinétique
• Liste triée cinétique
• Tas cinétique
• Coque cinétique convexe
• Paire cinétique la plus proche
• Arbre couvrant minimum cinétique
• Arbre couvrant minimum euclidien cinétique