Brevet FR3077146A1 — publié le 20190726

RECALCUL DE RÉSULTATS PRÉCALCULÉS D'INTERROGATION DOMAINE DE L'INVENTION L'invention présente concerne de façon générale la technologie de base de données. Plus spécifiquement, elle vise à recalculer des résultats précalculés de recherche stockés comme enregistrements de base de données. CONTEXTE Un problème courant en matière de technologie de base de données est d'assurer des temps de réponse courts aux interrogations de bases de données ou aux requêtes qui exigent un traitement complexe, long et des ressources importantes, p. ex. en raison de larges volumes de données. Ce traitement consommateur de puissance de calcul doit par exemple être mis en oeuvre en 15 réponse à des soi-disant « interrogations ouvertes » qui contiennent très peu d'informations saisies (p. ex. seulement un ou deux paramètres parmi une douzaine de paramètres possibles sont spécifiés et/ou la valeur spécifiée des fourchettes de valeur est large) et, par conséquent, renvoient en général un grand nombre de résultats. Les possibilités d'accélérer le traitement des données en augmentant la performance du matériel sont limitées. Ainsi, l'attention est portée 20 sur l'amélioration des mécanismes sous-jacents du traitement complexe, long et requérant des ressources importantes afin de répondre à ces interrogations. Une approche générale pour raccourcir les temps de réponse est de préparer des résultats à renvoyer en réponse à des requêtes attendues (p. ex. en calculant ou en collectant à l'avance ces 25 résultats) et de conserver les résultats d'interrogation correspondants dans une réserve de résultats précalculés d'interrogation. Il s'ensuit que les requêtes ne sont pas actuellement traitées et les réponses basées sur la base importante des données d'origine, mais sont orientées vers la réserve de résultats précalculés d'interrogation. 30 Recalculer un large nombre de résultats précalculés d'interrogation est une tâche qui requiert une quantité substantielle de ressources de calcul. Ainsi, des mécanismes de recalcul sont recherchés pour effectuer le recalcul des résultats précalculés d'interrogation avec efficacité. 2 Demande de brevet n°18 50581 A5013307FRPOOMm EP 2913764 concerne le recalcul de résultats précalculés de recherche où les ressources de calcul nécessaires pour recalculer un résultat précalculé de recherche i dépendent généralement du fait de recalculer, ou pas, d'autres résultats précalculés de recherche associés aux résultats précalculés de recherche i qui sont recalculés pendant le même cycle de calcul. Par conséquent, 5 les ressources de calcul pour recalculer les résultats précalculés de recherche ne sont donc pas statiques, mais varient selon la sélection d'un ensemble de résultats précalculés de recherche devant être recalculés au cours d'un cycle de calcul. EP 2913764 propose un processus d'estimation itératif selon lequel un contrôleur de recalcul sélectionne de façon itérative un nombre de résultats précalculés de recherche pour être recalculés par la plateforme de calcul 10 pendant un intervalle de temps donné formant un cycle de recalcul. Le nombre de résultats précalculés de recherche est limité par les ressources de calcul disponibles pendant l'intervalle de temps donné. Après l'initialisation des ressources de calcul ci nécessaires pour recalculer chaque résultat précalculé de recherche i avec une valeur supposant le calcul de i indépendamment du calcul d'autres résultats précalculés de recherche sélectionnés pour un recalcul pendant l'intervalle de temps donné, une première portion des résultats précalculés de recherche est sélectionnée pour le recalcul dans une première itération de sélection, dans laquelle cette première portion sélectionnée ne nécessite qu'un pourcentage en dessous de 100 % des ressources globales de calcul disponibles pour le recalcul dans l'intervalle de temps donné. Les ressources de calcul ci nécessaires pour recalculer chaque résultat précalculé de recherche i sont ensuite réévaluées en prenant en compte les résultats précalculés de recherche associés au résultat précalculé de recherche i qui ont été sélectionnés pour un recalcul. D'autres itérations pour sélectionner d'autres portions n'ayant pas encore été sélectionnées de résultats précalculés de recherche et pour réévaluer les ressources de calcul ci nécessaires pour recalculer chaque résultat précalculé de recherche i sont alors effectuées si moins de 100 % des ressources globales de calcul disponibles pour un recalcul dans l'intervalle de temps donnés ont été épuisées. RÉSUMÉ Selon un premier aspect, un dispositif de calcul est fourni pour recalculer des résultats précalculés d'interrogation stockés sur un serveur de base de données. Les résultats précalculés d'interrogation sont composés d'une pluralité de parts. Chaque part inclut un certain nombre de résultats précalculés d'interrogation. Les ressources de calcul du dispositif de calcul, nécessaires pour recalculer un résultat précalculé 3 Demande de brevet n°18 50581 A5013307FRPOOMm d'interrogation d'une première part, dépendent du fait de recalculer, ou pas, d'autres résultats précalculés de la première part qui sont recalculés au cours d'un intervalle de temps donné en formant un cycle de calcul actuel. L'intervalle de temps donné forme un cycle de recalcul actuel. Le dispositif de calcul est agencé pour recevoir une requête de recalcul des résultats 5 précalculés d'interrogation pour au moins une première part. Le dispositif de calcul est par ailleurs agencé pour déterminer un nombre de résultats précalculés d'interrogation dans la première part devant être recalculée dans le cycle de recalcul actuel sur la base d'un algorithme d'apprentissage par renforcement. Le nombre déterminé de résultats précalculés de recherche est limité par les ressources de calcul disponibles du dispositif de calcul pendant 10 l'intervalle de temps donné. Le dispositif de calcul est par ailleurs agencé pour recalculer le nombre déterminé de résultats précalculés d'interrogation dans la première part. Selon un second aspect un procédé correspondant exécuté par un dispositif de calcul est fourni. 15 Selon un troisième aspect, un programme informatique stocké sur un support de stockage est fourni qui, lorsqu'il est exécuté par un dispositif de calcul, équipe le dispositif de calcul avec la fonctionnalité correspondante. BRÈVE DESCRIPTION DES GRAPHIQUES 20 L'invention présente sera décrite en faisant référence aux graphiques qui l'accompagnent. Des numéros de référence similaires font généralement référence à des éléments fonctionnellement identiques ou similaires. 25 FIG. 1 décrit de façon schématique un exemple de système de base de données stockant des résultats précalculés interrogation. FIG. 2 est une représentation visuelle d'un effet de diminution de la probabilité de validité des résultats précalculés d'interrogation dans le temps. 30 4 FIG. 3 illustre des ressources de calcul variantes, nécessaires pour recalculer différentes parts exemplaires de résultats précalculés d'interrogation. FIG. 4 est un schéma plus détaillé d'un système de recalcul tel qu'il est décrit dans les présentes. 5 FIG. 5 montre les éléments basiques du système d'apprentissage par renforcement. FIG. 6 illustre deux exemples d'un calcul agrégé d'indicateurs de performance clés. 10 FIG. 7 montre un exemple de la mise à jour d'une fonction de valeur. FIG. 8 est un flux séquentiel schématique avec des processus de haut niveau mis en oeuvre par le dispositif de calcul et son sous-système décrits dans les présentes. 15 FIG. 9 illustre une approche itérative basée sur l'apprentissage par renforcement pour déterminer un nombre optimal de résultats précalculés d'interrogation devant être recalculés pendant un cycle de calcul. FIG. 10 est une vue exemplaire schématique de l'architecture interne du tableau de la base de 20 données et/ou d'une requête d'un client. DESCRIPTION DÉTAILLÉE Afin de pouvoir gérer des interrogations de bases de données ou des lots de requêtes de calcul 25 qui exigent des calculs sur la base d'importants volumes de données sous-jacentes, les résultats de recherche correspondant à des interrogations attendues sont généralement précalculés et stockés comme enregistrements de base de données dans une base de données. Cette base de données est interrogée par des entités demandeuses (telles que des clients, des applications, des navigateurs installés sur des terminaux d'utilisateurs, etc.) au cours d'une recherche et des 30 résultats précalculés de recherche qui remplissent les critères indiqués par l'interrogation sont renvoyés au client en réponse à l'interrogation. Par la suite, le terme « interrogation » est utilisé comme terme général incluant tout type de requêtes d'extraction d'informations telles que des interrogations transactionnelles, des requêtes pour des calculs de lots et d'autres formes. 5 FIG. 1 illustre un tel environnement de base de données 1 à un niveau abstrait. Une donnée basique, également dénommée ci-après « donnée de calcul » est conservée dans et/ou accédée par un dispositif de calcul 3 qui est connecté à un contrôleur de recalcul 2. Ce dernier émet des ordres de recalcul au dispositif de calcul 3 qui, à son tour, transmet les résultats correspondants 5 à la plateforme de recherche 4 et, qui plus est, au contrôleur de recalcul 2 qui stocke aussi les résultats précalculés de recherche pour des raisons de contrôle de recalcul. Les utilisateurs finaux 5 tels que les applications sur des terminaux d'utilisateurs accèdent aux résultats précalculés de recherche à partir de la plateforme de recherche 4. Comme indiqué par la FIG. 1, une ou plusieurs plateformes de recherche 4 peuvent être présentes dans l'environnement 1. Si 10 une pluralité de plateformes 4 est présente, les résultats précalculés de recherche peuvent être stockés d'une manière distribuée entre plusieurs des plateformes de recherche 4 et le contrôleur de recalcul 2 peut contrôler les recalculs de tous les résultats précalculés de recherche distribués entre les plateformes de recherche 4. La plateforme de recherche 4 peut aussi offrir un ensemble hétérogène de requêtes précalculées de recherche, p. ex. des plateformes de recherche 4 15 stockent des requêtes précalculées de recherche concernant un transport aérien, d'autres plateformes de recherche 4 stockent des requêtes précalculées de recherche liées aux assurances et d'autres plateformes de recherche 4 stockent des requêtes précalculées (ou préextraites) liées à des sites Web sur Internet. Un tel environnement hétérogène peut être contrôlé par un seul contrôleur de recalcul 2 ou par une pluralité de contrôleurs de recalcul 2. Autrement, la pluralité 20 des plateformes de recherche 4 peut être utilisée pour refléter les mêmes résultats précalculés de recherche, par exemple, pour des raisons de redondance. L'approche de précalcul des résultats de recherche et de leur stockage sur la plateforme de recherche accessible aux clients demandeurs conduit à la situation générale que les données de 25 calcul peuvent changer dans le temps et, par conséquent, les résultats précalculés de recherche deviennent obsolètes ou invalides (les deux termes sont utilisés comme synonymes dans les présentes). Les résultats précalculés de recherche qui sont toujours d'actualité, c.-à-d. qui correspondent à des calculs équivalents correspondants en temps réel (des résultats qui seraient actuellement calculés à la demande sans disposer de résultats précalculés de recherche) sont 30 dénommés résultats précalculés de recherche « exacts » ci-après dans les présentes. Par conséquent, lorsque la plateforme de recherche qui stocke les résultats précalculés de recherche représente correctement l'état actuel sous-jacent du domaine de données des résultats d'interrogation en antémémoire, c.-à-d. que les données de calcul, les résultats précalculés de recherche stockés sur la plateforme de recherche sont - en général - exacts. 6 Généralement, pour permettre à la plateforme de recherche de renvoyer des résultats corrects, on voudra conserver un niveau élevé de corrélation entre les résultats précalculés de recherche qui sont fournis par l'entité d'interrogation en réponse à des interrogations de la base de données 5 et leurs équivalents de calcul en temps réel. En même temps, il est néanmoins souhaitable de minimiser la consommation de ressources de calcul occasionnée par les recalculs, c.-à-d. d'éviter tout recalcul non nécessaire tel que les recalculs de résultats d'interrogation en antémémoire qui sont toujours d'actualité. Les ressources de calcul sont limitées et généralement il n'y a pas assez de ressources de calcul pour recalculer tous les résultats 10 précalculés de recherche à tout moment. Par conséquent, il faut trouver un compromis entre l'exactitude des résultats précalculés d'interrogation et l'utilisation de la puissance de calcul disponible. Afin de rendre le recalcul plus efficace, des métriques sont définies pour évaluer la « nécessité » 15 ou « l'absence de nécessité » d'un recalcul. Par exemple, relancer un recalcul global, massif chaque jour n'en vaut peut-être pas la peine, si moins de la moitié des résultats calculés d'interrogation s'avèrent être obsolètes. D'autre part, si des catégories de résultats d'interrogation sont connues pour changer fréquemment, les recalculer plusieurs fois par jour peut s'avérer bénéfique en termes d'exactitude. Par conséquent, une façon effective d'évaluer 20 ou d'estimer l'exactitude des résultats de recherche est nécessaire, en prenant généralement en compte à la fois les gains attribuables _à l'exactitude et le coût du recalcul. Dans ce but, des mécanismes modèlent la validité décroissante des résultats précalculés d'interrogation dans le temps. Deux de ces fonctions exemplaires d'exactitude probable diminuant dans le temps sont illustrées par la FIG. 2. La fonction 10 représente un résultat précalculé de recherche qui reste 25 potentiellement plus exact (ou plus précisément, demeure à une probabilité élevée d'être valide dans le temps) qu'un autre résultat précalculé de recherche associé à la fonction 11. Par exemple, le résultat précalculé de recherche représenté par la fonction 10 a 70 % de probabilité d'être encore valide 35 heures après son dernier recalcul alors que la validité de l'autre résultat précalculé de recherche caractérisé par la fonction 11 ne va pas au-delà de 50 % environ 35 30 heures après son dernier recalcul. Les fonctions 10 et 11 peuvent aussi représenter des ensembles entiers de résultats précalculés de recherche et indiquer ensuite des proportions des ensembles de résultats précalculés de recherche vraisemblablement valides à un moment dans le passé depuis le dernier recalcul de l'ensemble. 7 Souvent, les considérations de recalcul des résultats précalculés d'interrogation supposent que le recalcul de tout résultat précalculé de recherche par le dispositif de calcul 3 exige substantiellement la même quantité de ressources de calcul sans tenir compte du fait que les résultats précalculés de recherche sont calculés séparément, ensemble avec des résultats 5 précalculés d'interrogation associés (p. ex. de mêmes origine, destination et dates adjacentes) ou tout autre résultat non associé d'interrogation. Cependant, en pratique cette supposition ne peut généralement pas être faite, car certains résultats précalculés d'interrogation et/ou leurs données sous-jacentes correspondantes de calcul sont, par exemple, interdépendants. Recalculer ces résultats précalculés d'interrogation interdépendants ensemble (c.-à-d. pendant 10 un même cycle de recalcul) pourrait inclure des effets synergiques et pourrait ainsi être plus efficace que de les recalculer séparément. Par conséquent, quand des résultats précalculés d'interrogation interdépendants sont recalculés ensemble les coûts de calcul par résultat précalculé d'interrogation individuel sont généralement moindres que le coût de calcul par résultat précalculé d'interrogation individuel requis s'ils sont recalculés séparément (c.-à-d. au 15 cours de différents cycles de recalcul. Pour faciliter la compréhension des résultats précalculés de recherche interdépendants, un exemple particulier va maintenant être présenté. Cet exemple provient d'une application particulière de l'environnement de base de données distribuée 1 dans l'industrie du voyage (c.- 20 à-d. que la base de données 4 stocke des résultats précalculés de recherche liés au voyage et les met à la disponibilité des utilisateurs finaux. Cependant, l'exemple suivant n'est pas supposé limiter les résultats précalculés de recherche interdépendants à une telle application de données liée au voyage. Au lieu de cela, des conditions similaires ou analogues permettant un recalcul synergique, et donc plus efficace de résultats précalculés de recherche interdépendants, sont 25 présents dans des systèmes de base de données indépendants du contenu des ensembles de données précalculés. En général, on peut dire que tout processus de recalcul des résultats précalculés de recherche vise à une mutualisation de sous-tâches de recalcul qui doivent être exécutées couramment pour tout résultat précalculé de recherche d'un ensemble de résultats précalculés de recherche. Ainsi, le recalcul groupé des résultats précalculés de recherche qui 30 ont de telles sous-tâches de recalcul en commun est généralement plus favorable que le recalcul groupé de requêtes précalculées de recherche qui ne partagent pas des sous-tâches de recalcul similaires. 8 Dans un mode de réalisation particulier, les requêtes précalculées de recherche sont pour des d'enregistrements de données de vols aller-retour, chacun spécifiant une origine de voyage et une destination, et une date de départ et d'arrivée (ou une durée de séjour relative à la date de départ comme alternative à la date d'arrivée). Dans cet exemple, la base de données 4 contient 5 des recommandations précalculées de voyage aller-retour pour toute paire origine-destination et toute paire départ-date d'arrivée devant être couvertes. Le tableau 1 indique un petit extrait de recommandations précalculées de voyage conservées dans la base de données 4, l'extrait étant des recommandations de voyage pour la paire de villes Nice-Boston (« NCE-BOS ») et pour des dates de départ du ler juillet au 5 juillet avec une durée de séjour maximum de cinq 10 jours, l'abréviation « pc-fr x» signifie « nombre x de recommandations précalculées de voyage ». NCE-BOS Dep. 1 JUL. Dep. 2 JUIL. Dep. 3 JUIL. Dep. 4 JUIL. Dep. 5 JUIL. Ret. 2 JUIL. pc-fr 0 -- -- -- -- Ret. 3 JUIL. pc-fr 1 pc-fr 5 -- -- -- Ret. 4 JUIL. pc-fr 2 pc-fr 6 pc-fr 10 -- -- Ret. 5 JUIL. pc-fr 3 pc-fr 7 pc-fr 11 pc-fr 15 -- Ret. 6 JUIL. pc-fr 4 pc-fr 8 pc-fr 12 pc-fr 16 pc-fr 20 Ret. 7 JUIL. -- pc-fr 9 pc-fr 13 pc-fr 17 ±pc-fr 21 Ret. 8 JUL. -- -- pc-fr 14 pc-fr 18 pc-fr 22 Ret. 9 JUIL. -- -- -- pc-fr 19 pc-fr 23 Ret. 10 JUIL. -- -- -- -- pc-fr 24 Tableau 1 Le recalcul d'une recommandation précalculée particulière de voyage, par exemple pc-fr 9 15 relative à une date de départ le 2 juillet et une date de retour le 7 juillet, est plus ou moins effectué par le dispositif de calcul 3 par les sous-tâches suivantes : 1: Récupération des routes géographiques possibles entre Nice et Boston incluant des arrêts/correspondances intermédiaires, par exemple : Nice-Paris-Boston, Nice-Londres- 20 Boston, Nice-New York-Boston, Nice-Paris-New York-Boston, etc. 9 2: L'identification de tous les vols possibles sur toutes les routes récupérées par l'activité 1: par exemple, Air France 123 et Emirates 7123 pour le segment Nice-Paris, Air France 456 et American Airlines 564 et United Airlines 125 pour le segment Paris- 5 New York, etc. a. Cette activité est effectuée pour la portion de départ du voyage à la date de départ le 2 juillet (sous-tâche 2a) et b. pour la portion de retour du voyage à la date de retour le 7 juillet (sous-tâche 2b) parce que les vols ne sont généralement pas disponibles tous les jours. 10 3: La vérification de la disponibilité de tous les vols par les activités 2a et 2b, c.-à-d. le 2 juillet pour la portion de départ du voyage (= sous-tâche 3a) et le 7 juillet pour la portion de retour du voyage (= sous-tâche 3b). 15 4: La récupération des tarifs qui sont appliqués à ces vols à ces dates. Un tarif typique est une règle qui produit un prix pour l'ensemble du voyage. Cependant, les tarifs peuvent aussi être valides pour les portions de départ et de retour du voyage à leurs dates respectives auquel cas ils peuvent être récupérés une fois pour la portion de départ (- sous-tâche 4a) et une fois pour la portion de retour du voyage (= sous-tâche 4b). Les 20 tarifs ont des restrictions pour les dates de départ, pour les dates de retour, sur les vols applicables, et beaucoup d'autres. Les tarifs peuvent être combinés, réduits dans des cas spécifiques et ainsi de suite. 5: La meilleure solution, c.-à-d. la correspondance au meilleur prix est retenue, renvoyée 25 par le dispositif de calcul 3 et stockée par la base de données 4 sous pc-fr 9. Ces sous-tâches sont effectuées d'une manière similaire pour toute recommandation précalculée de voyage. En effectuant le recalcul pour l'ensemble complet des recommandations précalculées de voyage (pc-fr 0 à pc-fr 24), plusieurs sous-tâches de recalcul peuvent être 30 mutualisées. L'exécution de la sous-tâche 1 est nécessaire une seule fois pour l'ensemble complet des recommandations de voyage pc-fr 0 à pc-fr 24 parce que toutes ces recommandations précalculées de voyage appartiennent à la même paire de villes origine-destination, Nice-Boston. Ainsi, la sous-tâche 1 n'a pas besoin d'être réeffectuée pour chaque résultat précalculé de recherche pc-fr 0 à pc-fr 24. 10 Les sous-tâches 2a, 3a et la sous-tâche 4 sont, d'un autre côté, spécifiques à une date de départ. Elles peuvent donc être réutilisées pour toutes les recommandations précalculées de voyage relatives à une et même date de départ. Ceci est indiqué par le tableau 2 pour les 5 recommandations précalculées de voyage pc-fr 5 à pc-fr 9 relatives à la date de départ du 2 juillet : NCE-BOS Dep. 1 JUIL. Dep. 2 JUIL. Dep. 3 JUIL. Dep. 4 JUIL. Dep. 5 JUIL. Ret. 2 JUIL. pc-fr 0 -- -- -- -- Ret. 3 JUIL. pc-fr 1 Sous-tâches -- -- -- communes : 2a, 3a, 4a Ret. 4 JUIL. pc-fr 2 pc-fr 10 -- -- Ret. 5 JUIL. pc-fr 3 pc-fr 11 pc-fr 15 -- Ret. 6 JUIL. pc-fr 4 pc-fr 12 pc-fr 16 pc-fr 20 Ret. 7 JUIL. -- pc-fr 13 pc-fr 17 pc-fr 21 Ret. 8 JUIL. -- -- pc-fr 14 pc-fr 18 pc-fr 22 Ret. 9 JUIL. -- -- -- pc-fr 19 pc-fr 23 Ret. 10 JUIL. -- -- -- -- pc-fr 24 Tableau 2 10 De la même façon, les sous-tâches 2b, 3b et 4b sont spécifiques à une date de retour, par conséquent, elles sont couramment effectuées pour les recommandations précalculées de voyage relatives à une et même date de retour. Ceci est illustré par le tableau 3 pour les recommandations précalculées de voyage pc-fr 9, pc-fr 13, pc-fr 17 et pc-fr 21, toutes étant relatives à la date de retour du 7 juillet. 15 11 NCE-BOS Dep. 1 JUIL. Dep. 2 JUIL. Dep. 3 JUIL. Dep. 4 JUIL. Dep. 5 JUIL. Ret. 2 JUIL. pc-fr 0 -- -- -- -- Ret. 3 JUIL. pc-fr 1 pc-fr 5 -- -- -- Ret. 4 JUIL. pc-fr 2 pc-fr 6 pc-fr 10 -- -- Ret. 5 JUIL. pc-fr 3 pc-fr 7 pc-fr 11 pc-fr 15 -- Ret. 6 JUIL. pc-fr 4 pc-fr 8 pc-fr 12 pc-fr 16 pc-fr 20 Ret. 7 JUIL. -- Sous-tâches communes : 2b, 3b, 4b Ret. 8 JUIL. -- -- pc-fr 14 pc-fr 18 pc-fr 22 Ret. 9 JUIL. -- -- -- pc-fr 19 pc-fr 23 Ret. 10 JUIL. -- -- -- -- pc-fr 24 Tableau 3 5 Ainsi, pour résumer, seule une partie de la sous-tâche 4, notamment la récupération des tarifs qui ne sont pas valides pour toute la portion de départ du voyage et pour toute la portion de retour du voyage, mais qui sont spécifiques aux sous-ensembles ou aux recommandations particulières de voyage, doit être effectuée séparément pour chaque recommandation précalculée de voyage alors que d'autres sous-tâches peuvent être effectuées en commun pour 10 toutes les recommandations précalculées de voyage relatives à la même paire de villes origine-destination (vrai pour la sous-tâche 1) ou au moins pour les recommandations de voyages relatives à la même date de départ (sous-tâches 2a, 3a et 4a) ou à la même date de retour (sous-tâches 2b, 3b et 4b). Par conséquent, plus les recommandations précalculées sont liées à une paire de villes origine-destination et plus les recommandations précalculées de voyage liées à 15 une date de départ et une date de retour respectivement plus les ressources de calcul peuvent être économisées en mutualisant ces sous-tâches entre les requêtes respectives précalculées de vols. Cette relation entre les effets synergiques croissants et un nombre croissant de 20 recommandations précalculées de voyage relatives à une paire de villes origine-destination et à 12 une date de départ ou de retour est aussi représentée visuellement par la FIG. 3. La FIG. 3 montre six graphiques d'ensembles de recommandations précalculées de voyage, chaque ensemble appartenant à une paire de villes origine-destination et formant un exemple d'une part de résultats précalculés d'interrogation tels qu'ils sont utilisés dans les présentes. En nombre 5 décroissant de recommandations précalculées de voyage associé à une paire de villes, le graphique 36 est relatif à la paire de villes New York-Buffalo, le graphique 37 à New York-Minsk, le graphique 38 à New York-Hilo, Hawaï, le graphique 39 à New York-Bilbao, le graphique 40 à New York -Male et finalement, le graphique 41 à New York-Mauritius. L'axe x du diagramme de la FIG. 3 dénote le nombre de recommandations précalculées de voyage 10 alors que l'axe y trace une mesure des ressources de recalcul nécessaires pour effectuer unrecalcul des recommandations précalculées de voyage, notamment le temps machine (CPU). D'un côté, la FIG. 3 montre qu'un recalcul de certains ensembles de recommandations précalculées exige plus de ressources de calcul que d'autres. Par exemple, le recalcul de 15 recommandations précalculées de voyage de l'ensemble 41 incluant des recommandations précalculées de voyage pour des vols entre New York et Mauritius est généralement plus coûteux que le recalcul des recommandations précalculées de voyage de l'ensemble 36 incluant des recommandations précalculées de voyage pour des vols entre New York et Buffalo. Cette différence générale de la quantité de ressources de calcul nécessaires pour recalculer des 20 recommandations précalculées de voyage est prise en compte par l'inclusion des coûts de recalcul C dans l'indicateur de recalcul comme on vient de l'expliquer en détail ci-dessus. Cependant, les graphiques de la FIG. 3 indiquent aussi que les coûts de recalcul varient avec le nombre de recommandations précalculées de voyage d'un ensemble en cours de recalcul. En général, plus les recommandations précalculées de voyage relatives à un ensemble sont 25 recalculées ensemble, moins de ressources de calcul sont nécessaires pour recalculer chaque recommandation précalculée de voyage. Par exemple, le graphique 36 indique que recalculer au 32 les recommandations précalculées de voyage pour l'ensemble New York-Buffalo- exige environ 1000 ms de CPU, c.-à-d. à peu près 31,25 ms de CPU par recommandation précalculée de voyage, alors que le recalcul au 170 de recommandations précalculées de voyage nécessite 30 environ 5000 ms de CPU, c.-à-d. seulement 29,4 ms environ de CPU par recommandation précalculée de voyage. Par rapport au graphique 38 relatif à la paire de villes New York-Hilo, recalculer au 35 les recommandations précalculées de voyage de cet ensemble nécessite environ 10 000 ms de CPU, c.-à-d. 286 ms de CPU par recommandation précalculée de voyage alors que le recalcul, au 140, des recommandations précalculées de voyage de cet ensemble exige 13 environ 25 000 ms de CPU, c.-à-d. seulement 178,5 ms de CPU par recommandation précalculée de voyage. Par conséquent, il est clair que les recommandations précalculées de voyage appartenant à une paire de villes origine-destination (l'exemple présent d'une part) sont interdépendantes en matière de ressources informatiques requises pour leur recalcul comme 5 expliqué ci-dessus. En d'autres termes, les ressources de calcul nécessaires pour recalculer un résultat précalculé de recherche i dépendent généralement du fait de recalculer, ou pas, d'autres résultats précalculés de recherche relatifs au résultat précalculé de recherche i au cours du même cycle 10 de calcul. Ainsi, les ressources de calcul pour recalculer les résultats précalculés de recherche ne sont pas statiques, mais varient selon la sélection de l'ensemble de résultats précalculés de recherche devant être recalculé au cours du cycle de calcul. Donc, unmécanisme est recherché pour déterminer de façon dynamique un nombre optimal de 15 résultats précalculés d'interrogation d'une part devant être recalculée durant un cycle de calcul (désigné ci-après « nombre de recalculs ») pour optimiser l'utilisation efficace des ressources de recalcul. En même temps, le mécanisme devrait minimiser le gaspillage de ressources de calcul dû au recalcul de résultats précalculés d'interrogation qui sont toujours valides et n'ont besoin d'aucun recalcul. Par ailleurs, le mécanisme ne devrait pas compromettre la stabilité du 20 dispositif de recalcul, mais en assurer la robustesse. Il est proposé de supplémenter le système 1 de la FIG.1 avec un module additionnel, désigné ci-après comme sous-système d'auto réglage de calcul 6 (FIG.4). La fonction du sous-système d'auto réglage de calcul 6 est de déterminer automatiquement et de façon autonome ainsi que 25 d'affiner le nombre de résultats précalculés interdépendants d'interrogation qui doivent être calculés afm de recalculer plus de résultats précalculés de recherche avec les mêmes ressources de calcul. Pour remplir cette fonction, le sous-système d'auto réglage de calcul 6 incorpore une base de données de connaissance experte et est couplé à deux autres sous-systèmes, notamment - au dispositif de calcul 3 auquel le sous-système d'auto réglage de calcul 6 apporte un 30 nombre optimal (un ensemble) de résultats précalculés de recherche devant être recalculés pour une demande de recalcul donnée provenant du contrôleur de recalcul 2. En termes de fonctionnalités, le sous-système d'auto réglage de calcul 6 peut être considéré comme formant une partie du dispositif de calcul 3. 14 - Un serveur de statistiques 7 qui agit comme fournisseur de statistiques pour affiner la base de connaissance interne du sous-système d'auto réglage de calcul 6. Le contrôleur de recalcul 2 déclenche régulièrement le recalcul de résultats précalculés 5 d'interrogation en envoyant au 16 des demandes de recalcul (potentiellement basée sur des plannings de recalcul 12) au dispositif de calcul 3. Par exemple, à un moment dans le temps, le contrôleur de recalcul 2 décide de recalculer une ou plusieurs parts particulières des résultats précalculés d'interrogation (également désignée comme ladite « au moins une première part ») et déclenche un recalcul de ladite une ou de plusieurs parts. Chaque fois que le contrôleur de 10 recalcul 2 demande au 16 le recalcul de certains résultats précalculés d'interrogation au cours d'un nouveau cycle de calcul, le dispositif de calcul 3 récupère des données pertinentes du sous-système d'auto réglage 6 pour décider de la politique pour déterminer le nombre de résultats précalculés d'interrogation devant être recalculés dans les parts respectives des résultats précalculés d'interrogation. Un processus de mécanisme de sauvegarde 22 fournit une certaine 15 qualité de décision du nombre de résultats précalculés d'interrogation devant être recalculés ce qui peut conduire à un réalignement potentiel dynamique de la décision dans le cas actuel et dans le temps. Un processus asynchrone 24 collecte, à partir du sous-système serveur de statistiques 7, les données statistiques de calculs antérieurs (qui ont été postés au 20 sur le sous-système serveur de statistiques 7) pour affiner les décisions dans le temps. Les recalculs du 20 dispositif de calcul 3 lui-même sont basés sur d'autres données de calcul, dans l'exemple de la FIG. 4 les plannings de vol ou de voyage, les données de disponibilité et de tarifs, stockés dans le système de base de données 8. On notera que celle-ci n'est pas un exemple limitatif du système de base de données distribuée. Le mécanisme présenté dans les présentes est applicables à tous les cas d'utilisation de résultats d'interrogation précalculés, ou en 25 antémémoire, dans lesquels le précalcul ou la conservation en antémémoire implique des synergies entre les résultats interdépendants d'interrogation de la manière exemplaire définie dans les détails ci-dessus par rapport aux FIGS. 2 et 3. Il n'existe pas de modèle qui pourrait être immédiatement utilisé pour attribuer un nombre 30 optimal de recalculs à une part donnée de résultats précalculés d'interrogation afin de recalculer les résultats précalculés d'interrogation de la part durant un cycle de calcul. D'un côté, les effets synergiques de recalcul d'un nombre de résultats précalculés d'interrogation associé dépendent du cas d'utilisation spécifique du système de base de données et des caractéristiques des résultats précalculés d'interrogation en termes de leur interdépendance et validité décroissante 15 dans le temps. De l'autre côté, le nombre optimal de résultats précalculés associés d'interrogation devant être recalculés dépend aussi de la stratégie de recalcul employée (p. ex. toujours recalculer les résultats précalculés d'interrogation ayant la moindre probabilité d'être à jour). Par ailleurs, des options peuvent être incluses dans le déclenchement de calcul 16 à 5 partir du contrôleur de recalcul 2. qui ont une influence - à priori inconnue - sur les résultats précalculés d'interrogation pouvant être plus importants pour être valides/exacts que d'autres. Afin d'adresser ces obstacles, il est donc généralement proposé dans les présentes d'utiliser un algorithme d'apprentissage qui optimise de façon dynamique la décision de nombre de résultats 10 précalculés d'interrogation au cours d'un cycle de calcul dans le temps, indépendamment desdites influences a priori inconnues mentionnées auparavant. Cependant, il ne semble pas possible d'utiliser des algorithmes d'apprentissage supervisés standards, c.-à-d. un algorithme basé uniquement sur la connaissance d'un expert tel qu'un réseau neuronal puisqu'il n'y a pas de connaissance du nombre de recalculs optimal pour une part donnée de résultats précalculés 15 d'interrogation. Ces algorithmes exigeraient un entraînement sur une base de données associant les déclenchements de calcul 16 à partir du contrôleur de recalcul 2 avec leurs meilleurs nombres respectifs de recalculs pour chaque part devant être recalculée. Cependant, la connaissance experte requise n'est généralement pas disponible. 20 Une autre façon de construire cette base de données serait d'utiliser une approche de force brute pour permuter tous les nombres possibles de recalculs pour un déclenchement de calcul donné 16 venant du contrôleur de recalcul 2. Cela pourrait amener à determiner quel nombre de recalculs est le plus approprié pour le déclenchement de calcul 16. Cependant, cette approche présente plusieurs problèmes, car elle demanderait beaucoup de temps et de matériel pour 25 rassembler toutes ces statistiques. Par ailleurs, elle établit seulement des nombres de recalculs statiques et il pourrait donc y avoir des incohérences entre le statut actuel de cette base de données et le moment où elle est employée par le dispositif de calcul 3. Cela exposerait le système 1 dans son ensemble (FIG.1) à une élévation potentielle de rejets techniques, c.-à-d. des états d'échec provoqués par des déclenchements de calcul 16 en provenance du contrôleur 30 de recalcul 2, en cas de changements des résultats précalculés d'interrogation. Par conséquent il est proposé de former l'algorithme d'apprentissage de façon continue au cours du traitement de chaque déclenchement de calcul 16 venant du contrôleur de recalcul 2. Un algorithme façonné par des tests et des erreurs semble approprié pour noter le résultat d'une 16 décision de nombre de recalculs en réponse au déclenchement de calcul 16. La notation pourrait par exemple utiliser des seuils d'un nombre d'indicateurs de performance clés pour juger la qualité de la décision. Les algorithmes de la famille d'apprentissage par renforcement semblent être les plus appropriés pour cette tâche. 5 Par conséquent, le dispositif de calcul 3 est amélioré par le module d'auto réglage 6 pour implémenter un algorithme d'apprentissage par renforcement afin de déterminer un nombre optimal de résultats précalculés d'interrogation dans une part devant être recalculée au cours d'un cycle de calcul. Plus spécifiquement, le dispositif de calcul 3 reçoit une requête au 16 pour 10 recalculer des résultats précalculés d'interrogation pour au moins une première part. Le dispositif de calcul 3, plus spécifiquement le sous-système d'auto réglage 6 détermine un nombre de résultats précalculés d'interrogation dans la première part devant être recalculée dans le cycle de recalcul actuel sur la base d'un algorithme d'apprentissage par renforcement. Le nombre déterminé de résultats précalculés est limité par les ressources de calcul du dispositif 15 de calcul qui sont disponibles pendant l'intervalle de temps donné. Le dispositif de calcul 3 recalcule ensuite le nombre déterminé de résultats précalculés d'interrogation dans la première part pendant le cycle de calcul. Dans certains modes de réalisation, l'algorithme d'apprentissage RL décrit dans les présentes 20 prend en compte les indicateurs de performance clés (KPIs) et examine les effets des décisions respectives de nombre de résultats précalculés d'interrogation devant être recalculés en fonction des KPIs durant un cycle de calcul. Une connaissance experte peut être utilisée pour déterminer, par ex., les options de déclenchements de calcul 16 du contrôleur de recalcul 2 qui n'ont pas d'influence sur les KPIs - ceci pouvant être utilisé pour réduire la dimensionnalité de l'espace 25 d'apprentissage. Dans certains modes de réalisation, les KPIs incluent un ou plusieurs des facteurs suivants : la somme des nombres des résultats précalculés d'interrogation, le temps écoulé pour recalculer les résultats précalculés interrogation devant être recalculés dans l'intervalle de temps donné, 30 les ressources maximum de calcul pour recalculer des résultats précalculés d'interrogation indiqués dans la demande et la mémoire maximum requise pour recalculer des résultats précalculés d'interrogation qui sont indiqués dans la demande. Dans certains modes de réalisation, les valeurs des KPIs sont agrégées en une valeur agrégée de KPIs, ce qui est expliqué de façon détaillée ci-dessous. Dans certains modes de réalisation, le KPI peut être 17 déterminé selon une hiérarchie, avec des KPIs plus généraux composés d'un nombre de KPIs plus spécifiques. Cela permet une évaluation à fine granularité de l'effet technique, c.-à-d. un usage efficace des ressources de calcul dû à un nombre optimal de résultats précalculés d'interrogation sélectionnés pour le recalcul. L'agrégation de KPI est alors à chaque niveau de 5 hiérarchie, où le nombre de KPIs plus spécifiques est agrégé pour former le KPI plus général et les KPIs plus généraux sont agrégés pour établir une valeur de récompense commune pour une certaine action comme ce sera expliqué de façon plus détaillée ci-dessous. Avant de se tourner vers des options de conception plus détaillée pour un algorithme RL dans 10 le but de résoudre le problème technique mentionné ci-dessus, une vue globale de certains concepts de RL est d'abord présentée. Les mécanismes d'apprentissage par renforcement sont aussi décrits, par exemple dans le livre « Reinforcement Learning » de Richard S. Sutton et Andrew G. Barto, publié par MIT Press en 1998. Les mécanismes RL utilisent des termes de pointe ayant une signification établie et sont utilisés dans les présentes avec cette signification 15 établie pour décrire l'algorithme de détermination d'un nombre optimal de recalculs, incluant (voir FIG.5) : - l'agent : le module qui apprend et prend des décisions, le dispositif de calcul 3 avec le sous-système d'auto réglage 6 qui définissent le nombre de recalculs. - l'environnement : tous les faits extérieurs à l'agent avec lesquels l'agent interagit à 20 chacun des points discrets d'une séquence dans le temps. L'environnement influence les décisions de l'agent et il est influencé par les décisions de l'agent. - la tâche : une spécification complète d'un environnement, un cas de problème d'apprentissage par renforcement. - une observation : la détermination d'un état de l'environnement à un point discret dans 25 le temps. Dans les présentes, l'état comprend des paramètres variés tels que le contenu d'une requête de déclenchement de calcul 16 (une indication d'une ou de plusieurs parts devant être recalculée et potentiellement d'autres options de recalcul), l'état de recalcul (le calcul a-t-il été accompli avec succès ?), les KPIs du recalcul (dans quelle mesure le calcul s'est-il bien achevé ? Plus spécifiquement : les coûts de CPU, la consommation 30 de mémoire, etc.). - l'action : une décision prise par l'agent à partir d'un ensemble d'actions disponibles dans l'état actuel de l'environnement. Dans les présentes : il s'agit de déterminer le nombre de résultats précalculés d'interrogation d'une ou de plusieurs parts devant être recalculées pendant le cycle actuel de recalcul. 18 - la politique : le mappage des états de l'environnement aux probabilités de sélection de chaque action possible. - la fonction de récompense : la fonction qui détermine une récompense pour chaque action sélectionnée par l'agent. Dans les présentes, la fonction de récompense utilise 5 des seuils de KPI. Par exemple, une action qui cause un rejet technique de l'environnement produira une mauvaise récompense. Dans certains modes de réalisation, la fonction de récompense attribue une valeur à une action prise par le sous-système d'auto réglage 6 sur la base des ICPIs agrégés récupérés à partir du serveur de statistiques 7. 10 - la valeur de fonction : un tableau qui associe un ensemble d'actions avec leurs récompenses estimées. Le but de l'agent est de maximiser les récompenses non pas immédiatement, mais sur le long terme. 15 Une caractéristique générale de RL est le compromis entre exploration et exploitation : - En mode exploration, l'agent essaie de nouvelles sortes d'action pour voir dans quelles mesures elles sont efficaces. L'efficacité d'une action est immédiatement fournie par la récompense renvoyée à l'agent en réponse à l'action sélectionnée. 20 - En mode exploitation, l'agent fait usage d'actions qui sont connues pour produire une récompense élevée en utilisant l'histoire des récompenses dérivées de la fonction de valeur. Plus spécifiquement pendant chaque phase d'exploitation, le nombre de recalculs est déterminé c'est-à-dire, selon la base de données de connaissance experte actuellement connue pour produire le plus de récompenses. Le but est de maximiser les 25 récompenses sur le long terme (mathématiquement, cela signifie que la somme de toutes les récompenses sur une durée de vie infinie est maximisée). Généralement parlant, en mode exploitation, l'algorithme essaie de tirer profit de ce qu'il a appris alors que le mode exploration peut être vu comme un « investissement » pour rechercher d'autres opportunités afin d'optimiser encore plus la détermination du nombre de recalculs. 30 En mode exploration et exploitation, l'agent tire continuellement des enseignements de son environnement. Cependant, l'exploration et l'exploitation doivent être équilibrées. Trop de concentration sur l'exploration ou sur l'exploitation produira de mauvais résultats. L'agent peut explorer pour découvrir de nouvelles stratégies qui pourraient potentiellement produire une 19 récompense très élevée, mais trop explorer peut s'avérer dangereux, car l'agent n'utilise jamais sa connaissance de l'environnement. Une stratégie pour équilibrer ces deux modes afin de résoudre un problème technique particulier discuté dans les présentes sera présentée par ailleurs ci-dessous. 5 Certaines particularités du concept de la fonction de récompense pour implémenter le dispositif de calcul 3 avec le sous-système 6 vont maintenant être décrites. Le problème principal qui doit être évité est celui des rejets techniques, c.-à-d. les états d'échec du dispositif de calcul 3 causés par un nombre inapproprié de recalculs qui produisent un message de rejet pour un 10 déclenchement de calcul 16. Par conséquent une pénalité élevée est attribuée à l'agent dans ce cas. D'un autre côté, l'agent ne doit pas surréagir. Des instabilités du dispositif de calcul 3 qui généreraient des rejets techniques et qui ne seraient pas dues aux actions prises par l'agent sont 15 possibles. Dans ce but, dans certains modes de réalisation, les nombres de recalculs qui se sont traduits par des rejets techniques (ReNbTR) sont associés à des nombres de recalculs qui n'ont pas abouti à un rejet technique (RcNbOK). Par conséquent, dans certains modes de réalisation, le premier terme de la fonction de récompense est défini par la formule suivante : ReNbTRld\ PENALITETR(RcNbO 20 avec PENALITE(X)= exp(X), c.-à-d. une fonction exponentielle. Par ailleurs, un ensemble de seuils de KPI est utilisé dans certains modes de réalisation. Ces seuils de KPI sont des limites que les actions de l'agent ne doivent pas dépasser. Par conséquent, ces seuils de KPI doivent être déterminés judicieusement, par ex., avec l'aide des experts du 25 domaine du système 1 (FIG.1), selon le cas d'usage particulier du système 1. Afin d'accroître les actions sécurisées de l'agent, un niveau additionnel de sécurité est mis en place dans certains modes de réalisation. Le seuil est pris comme un pourcentage donné du seuil actuel à partir duquel un rejet technique serait actuellement généré (« seuil dur »). Cela produit 30 trois états possibles : acceptable (sous le seuil), avertissement (au-dessus du seuil, mais toujours sous le seuil dur) et rejet technique (au-delà du seuil dur). De cette façon, une marge de sécurité est introduite sous le seuil dur : SEU/Liepix = MARG- -EsEtm.(Kpix) * SEUIL DURKplx 20 avec 0 0 constant RECOMPENSE (X) = avec INR1 > PR * NR, X> 1,NR 1, oearge de Code les variables a, ER and CL sont réglées avec une approche empirique (p. ex. en utilisant la connaissance d'un expert de domaine) pour obtenir le comportement souhaité. 25 30 23 Les paramètres de vitesse d'apprentissage doivent assurer que, dans le cas de l'intégration d'une récompense négative, la fonction de valeur n'est pas trop dégradée, car elle peut être due à une certaine instabilité du système : Vkl_1(Wi) Cl fois et explorer ensuite une fois avec un autre nombre de recalculs plus important. 28 3. 5 % C2 fois et explorer ensuite une fois avec un nombre de recalculs plus important. 4. 90 % C3 de fois et explorer ensuite une fois avec un nombre de recalculs plus important. Les variables Cl, C2, C3 et C4 doivent être réglées avec une approche empirique pour obtenir le comportement souhaité (par exemple, en termes de vitesse de convergence). 10 En réponse à la détermination que l'agent est autorisé à explorer dans le cycle de calcul actuel, le nombre de recalculs plus important pour l'exploration doit être décidé. Il est supposé que : - La récompense calculée pour un nombre donné de recalculs est meilleure lorsque les KPIs, après la décision pour le nombre donné de recalculs, sont plus proches du seuil 15 des KPIs que pour le dernier nombre de recalculs. - L'évolution de la récompense n'est pas proportionnelle au nombre de recalculs (sousadditivité), p. ex. : RECOMPENSE(2 * W) 5 2 * RECOMPENSE(W) 20 Du fait que dans certains modes de réalisation, le système a une approche conservatrice pour éviter les états d'échec, la convergence vers le meilleur recalcul pour une part donnée est faite prudemment, étape par étape, dans certains modes de réalisation. Dans certains modes de réalisation, le nouveau nombre de recalculsWnouveau est donné par : - RECOMPENSEmAx Wi Wnouveau= Vk(Wi) 25 où Vk (Wi) est la fonction de valeur du dernier nombre de recalculs exploité Wk. C'est une valeur strictement positive puisque le mode RL actuel est un mode d'exploration qui a été permis par la comparaison avec la récompense maximum. Cette approche est appliquée de façon itérative pour déterminer le nombre de recalculs pour la prochaine phase d'exploration. Sur de multiples nombres de phases d'exploration, l'emploi respectif de cette formule dans 30 chacune des phases d'exploration pour déterminer Wnouveau/ étape par étape forme une approche itérative qui amène le nombre de recalculs de plus en plus près de la récompense agrégée maximum RECOMPENSE., et ainsi, pour sélectionner le nombre de recalculs d'une manière optimisée afin d'utiliser de façon efficace les ressources disponibles de recalcul. 29 La FIG. 9 donne un exemple de cette sélection d'équilibrage entre le mode exploitation et le mode exploration. Cet exemple détaille l'évolution de la fonction de valeur d'une part donnée de résultats précalculés d'interrogation. 5 Initialement (FIG. 9A), lorsqu'une part doit être recalculée pour la première fois, il n'existe aucun nombre antérieur de recalculs pour la part. Dans ce cas, le mode exploration est sélectionné par défaut. Dans certains modes de réalisation, le sous-système d'auto réglage 6 peut émettre un avertissement au 14 au contrôleur de recalcul 2. Le contrôleur de recalcul 2 10 peut ensuite inclure un nombre de recalculs par défaut dans les requêtes futures relatives à cette part au 16. L'agence sélectionne un nombre donné conservateur (c.-à-d. relativement bas) de recalculs pour la part comme le représente visuellement la FIG. 9 A. Une valeur de récompense pour cette action est calculée sur la base de la fonction de récompense expliquée en détail ci-dessus. Le dispositif de calcul 3 recalcule ensuite les résultats précalculés d'interrogation de la 15 part dans le cycle de calcul conformément au nombre déterminé de recalculs. Ce nombre déterminé de recalculs est stocké sur le serveur de statistiques 7. En réponse à la réception par le dispositif de calcul 3 d'un autre déclenchement de calcul 16 pour recalculer les résultats précalculés d'interrogation de la part dans un cycle de calcul suivant 20 (toujours FIG. 9A), le dernier nombre de recalculs est récupéré à partir du serveur de statistiques 7. L'agent détermine ensuite que le dernier nombre de recalculs était en dessous de la récompense maximum, par exemple dans une fourchette de 50-75 % de la récompense maximum selon le cas 2 ci-dessus. Conformément à l'algorithme d'équilibrage ci-dessus, l'agent détermine le mode RL d'exploitation pour les intervalles C2, dans l'exemple de la 25 FIG. 9B pour trois cycles de calcul supplémentaires. Ceci assure que le nombre de recalculs antérieur est une solution stable (mais pas encore nécessairement un choix optimal). Dans ce cas, C2 recalculs similaires de la part avec les mêmes résultats précalculés d'interrogation seront effectués avant de procéder à une nouvelle exploration. 30 Au recalcul C2+1' de la part (FIG. 9B), une nouvelle exploration est déterminée avec un nombre de recalculs plus élevé, comme expliqué précédemment. Il en résulte un nombre de recalculs plus élevé avec une valeur de récompense plus élevée. Durant les recalculs suivants, le mode RL d'exploitation est à nouveau sélectionné (toujours FIG. 9B). Cette fois, la valeur de récompense pour le nombre de recalculs plus élevé est dans le cas 3, donc les prochains 30 recalculs C3 de la part sont faits en mode exploitation. Comme dans la FIG. 9A, cela assure que le nombre de recalculs explorés est stable. Cette sélection alternative d'une exploration suivie par un nombre d'exploitations est réitérée 5 ultérieurement de la même manière pour déterminer le nombre optimal de recalculs pour cette part particulière (FIG. 9C). L'algorithme de sélection de mode entrera dans le cas 4, ou le nombre d'exploitations ultérieures C4 est le plus élevé. Par conséquent, de nouveaux nombres de recalculs potentiellement plus optimaux sont maintenant explorés moins souvent que dans les itérations précédentes. 10 À un point dans le temps, un nouveau nombre de recalculs explorés peut entrer dans la zone d'avertissement, c.-à-d. que le seuil de KPI pour un ou plusieurs KPIs est dépassé, produisant une valeur de récompense négative (FIG. 9D). Comme expliqué auparavant, dans certains modes de réalisation, il s'agit d'un avertissement, car le seuil a été calculé à un pourcentage 15 donné en dessous du seuil dur. Cela signifie que le nombre de recalculs a atteint (en fait même dépassé) la phase dans laquelle on ne peut attendre que peu d'amélioration de la récompense. Par conséquent le nombre de recalculs est stabilisé à la dernière valeur qui a produit les meilleures récompenses. Cependant, cette stabilisation signifie seulement que l'exploration est faite moins souvent, mais jamais exclue. En effet, il est souhaitable de continuer l'exploration 20 de temps en temps, car un système dans son ensemble n'est pas stationnaire et peut changer dans le temps, p. ex., lorsque les résultats précalculés d'interrogation, stockés par la plateforme de recherche 4, changent. Une autre phase d'exploration permet au système 1 de découvrir et de s'actualiser avec ces changements et développements. 25 La FIG. 9E représente une situation spéciale qui pourrait indiquer une dégradation du système 1 dans lequel une réinitialisation pourrait être appropriée. Les raisons possibles pour une dégradation des performances sont un changement substantiel des résultats précalculés de recherche, un changement du plan de la base de données ou du modèle de la plateforme de recherche 4, du dispositif de calcul 3 et/ou du contrôleur de recalcul résultant en une 30 fonctionnalité modifiée/affinée ou une réserve modifiée des résultats précalculés d'interrogation. Le terme dégradation indique que le nombre optimal de recalculs peut être réduit à ces changements comparés avec l'état du système 1 avant les changements. 31 Dans le scénario de la FIG. 9E, de multiples récompenses renvoyées ultérieurement pour des nombres de recalculs explorés ultérieurement sont négatifs bien que le système 1 ait été stable durant une certaine longueur de temps précédente. Après plusieurs intégrations de récompenses, la fonction de valeur pour le poids est toujours négative. La chute des récompenses en valeurs 5 négatives implique ensuite qu'il n'y a pas d'autres raisons apparentes qu'une possible dégradation. Par conséquent, cela indique que la fonction de valeur est probablement inexacte ou pour le moins n'est plus appropriée pour intégrer les changements dans le système. Un nouveau nombre de recalculs est ensuite déterminé par l'analyse de la fonction de valeur pour le nombre actuel de recalculs afin de déterminer le nouveau point de départ. Par exemple, le 10 sous-système d'auto réglage 6 peut commencer à partir d'une valeur donnée initiale par défaut du nombre de recalculs comme décrit ci-dessus dans le cas d'une part recalculée pour la première fois. Dans un autre exemple, le sous-système d'auto réglage 6 peut effectuer une « approche dichotomique », c.-à-d. utiliser le tout dernier nombre de recalculs qui a produit une récompense positive et, pour le réduire encore plus, p. ex. en le divisant p. ex. par deux. 15 Des détails du réajustement du nombre de recalculs vont être décrits maintenant. Dans certains modes de réalisation, le dispositif de calcul 3 n'a pas assez de ressources de calcul pour recalculer une part entière d'une partie de la part qui a fait l'objet d'une requête pour être 20 recalculée par le contrôleur de recalcul 2 dans un seul cycle de recalcul. Dans ces modes de réalisation, les mécanismes décrits dans les présentes peuvent être employés pour diviser la part, ou la partie de la part faisant l'objet d'une demande, en tranches optimales qui sont recalculées par le dispositif de calcul 3 au cours d'une pluralité de cycles de calcul. Ici le nombre de recalculs déterminé par les mécanismes décrits dans les présentes indique la taille 25 d'une tranche devant être recalculée dans chaque cycle. Par ailleurs, dans certains modes de réalisation, les résultats précalculés d'interrogation sont arrangés en cellules avec deux dimensions. Un exemple non limitatif a déjà été mentionné ci-dessus en référence à la FIG.3 où les recommandations de voyage tarifées sont précalculées et 30 stockées dans une part respective pour chaque paire d'origine et de destination. Dans cet exemple non limitatif, les deux dimensions sont les données de départ et de durée du séjour. Dans ces modes de réalisation, un nombre de recalculs indique une partie d'une part ayant la forme d'un carré (c.-à-d. qu'elle indique un tapie de deux nombres, un pour chaque dimension. 32 La détermination de ce nombre de recalculs selon les mécanismes décrits ci-dessus respecterait d = piaf ond(-517) s = p1ancl7Jer(7) dans laquelle d est la fourchette de jours de départ [un départ dans les prochains d jours, la première dimension] et s est la fourchette de durée du séjour [une durée de séjour de 1 à s jours, la seconde dimension] et W est un poids optimal recommandé par la base de données de connaissances expertes [c.-à-d. que dans l'état actuel de l'algorithme RL, il est censé produire la plus haute récompense]. Cependant, en fonction de la fourchette de dates de départ et de la fourchette de durées de séjour demandées dans le déclenchement de calcul 16, cette solution 10 peut amener à de petites tranches de recalculs à la fin de la [partie de la] part devant être recalculée. L'algorithme suivant apporte une division améliorée de la partie de la part devant être recalculée en tranches par le dispositif de calcul 3, chacune des tranches doit être recalculée au cours d'une 15 pluralité de cycles de calcul, notamment pour choisir un nombre de recalculs ayant la forme d'un parallélogramme comme suit : - Déterminer une fourchette de durées de séjour s qui est proche de,r17V et diviser la fourchette de durées de séjour indiquée dans la requête 16 venant du contrôleur de recalcul 2 jusqu'à arriver à des morceaux aussi égaux que possible. 20 - Déterminer le nombre le plus élevé possible de recalculs étant un carré de s - d avec la tranche la moins non pleine [c.-à-d. la dernière tranche de la partie de la part devant être recalculée est la plus proche du nombre de recalculs (c.-à-d. la taille des autres tranches) et avec s> d afm d'optimiser l'usage efficace des ressources de calcul (si s> d, moins de dates de départ doivent être recalculées durant chaque 25 cycle de calcul, p. ex. le recalcul d'un carré de 3d - 15s est moins coûteux que le recalcul d'un carré de 15 d - 3s). Les nombres déterminés s et d sont fixés à plancEler (--sR ) et donc ont : Nitr-y SR S = piaf ond( nc sR)) et d = plancDer(7). plaherEe. 30 Implicitement, cet algorithme considère que la fourchette de durées de séjour indiquée dans la requête 16 est plus petite que la fourchette de dates de départ indiquée dans la requête et que la 33 fourchette de durées de séjour indiquée est donc celle qui doit être divisée. Si d'un autre côté, la durée de séjour indiquée dans la requête 16 est égale ou plus élevée que la fourchette de durée de séjour, le même algorithme doit être appliqué avec une durée indiquée de séjour échangée et un jour indiqué de départ échangé, et donc s et d échangés. 5 Comme exemple, le contrôleur de recalcul 2 demande au dispositif de calcul 3 de recalculer une part particulière pour les prochains 31 jours de départ avec une fourchette de durées de séjour de 16 [c.-à-d. toutes les durées de séjour étant de 1 à 16 jours]. Par conséquent, dans l'ensemble, un carré de 31 16 = 496 de résultats précalculés d'interrogation doivent être 10 recalculés. La plateforme de calcul a suffisamment de ressources de calcul pour recalculer 50 résultats précalculés d'interrogation par cycle de recalcul. La solution naïve mentionnée ci-dessus produirait un nombre de recalculs de 7d -7s = 49 qui résulterait en 8 tranches de 7d 7s, ainsi que 7 tranches non pleines, notamment 4 tranches de 15 2d- 7s, 2 tranches de 7d-4s, et une tranche finale de 2d-4s, afin de compléter le recalcul des 496 résultats précalculés d'interrogation. Le nombre moyen de recalculs au-delà de ces 15 cycles de calcul est de seulement 33. L'approche plus sophistiquée dessinée ci-dessus conduit à une division de 6d 8s. Ce qui résulte en 12 tranches, notamment 11 tranches de 6d-8s et une tranche restante non pleine de 1 d -7s, et un nombre moyen global de recalculs de 41. 20 Cette approche peut-être généralisée à d'autres cas d'usage avec les résultats précalculés d'interrogation ayant d'autres dimensions ou un nombre différent de dimensions [p. ex. trois dimensions]. 25 Enfin, la FIG.10 est un exemple de représentation schématique d'un système informatique 100 agencé en dispositif de calcul pour exécuter un ensemble d'instructions, afin d'amener le système informatique 100 à mettre en oeuvre une quelconque des méthodologies implémentant la détermination d'un nombre optimal de recalculs pour une part afin de recalculer un nombre optimal de résultats précalculés d'interrogation au cours d'un cycle de calcul, comme décrit ci- 30 dessus. Le système informatique 100 inclut un processeur 102, une mémoire principale 104 et une interface de réseau 108 qui communiquent les uns avec les autres via un bus 101. Le système informatique 100 inclut par ailleurs une mémoire statique 106, p. ex. non amovible flash et/ou un disque dur et/ou une carte micro ou mini SD amovible qui stockent de façon permanente les instructions permettant au système informatique 100 de mettre en oeuvre ses 34 Demande de brevet n°18 50581 A5013307FRPOOMm fonctions, en particulier d'exécuter l'algorithme d'apprentissage par renforcement pour sélectionner le nombre de recalculs en réponse à la réception d'un déclenchement de calcul 16. En outre, le système informatique 100 peut inclure une interface d'utilisateur 110 prise en charge par un module de contrôle d'interface d'utilisateur correspondant. 5 Dans certains exemples, les instructions programmées pour mettre en oeuvre les routines afin de déterminer le nombre de recalculs sont également stockées sur la mémoire statique 106. Lorsque les instructions sont exécutées, les données de processus résident dans la mémoire principale 104 et/ou dans le processeur 102. Les instructions peuvent par ailleurs être 10 transmises ou reçues comme signal propagé par le dispositif d'interface de réseau 108 à partir de/vers un serveur de logiciels dans un réseau local ou sur Internet. Le dispositif d'interface de réseau 108 peut-être une interface de réseau sans fil [telles qu'une interface Wifi et/ou Bluetooth] et/ou une interface de réseau mobile 2G/3G/4G/5G. 15 Les mécanismes décrits dans les présentes pour déterminer un nombre optimal de recalculs augmentent l'efficacité du recalcul de résultats précalculés d'interrogation qui sont composés d'une pluralité de parts avec un certain nombre respectif de résultats précalculés, dans lequel les ressources de calcul du dispositif de calcul, nécessaires pour recalculer un résultat précalculé d'interrogation résultent en une première part qui dépend, ou pas du fait de recalculer d'autres 20 résultats précalculés de la première part pendant un intervalle de temps donné formant un cycle de recalcul actuel. L'utilisation, de la manière décrite ci-dessus, de l'algorithme d'apprentissage par renforcement optimise l'usage des ressources de calcul du dispositif de calcul 3 en permettant le recalcul de plus de résultats précalculés d'interrogation avec la même quantité de ressources de calcul que si l'algorithme n'était pas utilisé. Les mécanismes sont indépendants 25 du cas d'usage particulier du dispositif de calcul et peuvent être employés par tout système qui recalcule des résultats précalculés d'interrogation ayant une interdépendance en termes de ressources de calcul requises pour les recalculer, comme décrit à titre d'exemple ci-dessus par référence à l'exemple de la FIG. 3. 30 Bien que certains produits et procédés construits selon les enseignements de l'invention aient été décrits dans les présentes, la portée de couverture de ce brevet ne leur est pas limitée. Au contraire, ce brevet couvre tous les modes de réalisation des enseignements de l'invention, soit littéralement, REVENDICATIONS1. Un dispositif de calcul pour recalculer des résultats précalculés d'interrogation stockés sur un serveur de base de données, dans lequel les résultats précalculés d'interrogation sont composés d'une pluralité de parts, dans lequel chaque part inclut un certain nombre de résultats précalculés d'interrogation, dans lequel les ressources de calcul du dispositif de calcul qui sont nécessaires pour recalculer un résultat précalculé d'interrogation d'une première part dépendent du fait de recalculer, ou pas, d'autres résultats précalculés d'interrogation pendant un intervalle de temps donné formant un cycle de recalcul actuel, le dispositif de calcul étant agencé pour : - recevoir une demande de recalcul des résultats précalculés d'interrogation pour au moins une première part ; - déterminer un nombre de résultats précalculés d'interrogation dans la première part devant être recalculée dans le cycle de recalcul actuel sur la base d'un algorithme d'apprentissage par renforcement, le nombre déterminé de résultats précalculés de recherche étant limité par les ressources de calcul disponibles du dispositif de calcul pendant l'intervalle de temps donné ; et - recalculer le nombre déterminé de résultats précalculés d'interrogation dans la première part pendant le cycle de recalcul. 20 2. Le dispositif de calcul selon la revendication 1, dans lequel la demande de recalcul de résultats précalculés d'interrogation pour au moins une première part indique des résultats précalculés d'interrogation pour ladite au moins une première part qui doit être recalculée et le dispositif de calcul est agencé pour déterminer le nombre de résultats précalculés 25 d'interrogation dans la première part devant être recalculée sur la base des résultats précalculés d'interrogation indiqués pour ladite au moins une première part. 3. Le dispositif de calcul selon la revendication 1 ou la revendication 2 étant agencé pour déterminer le nombre de résultats précalculés d'interrogation dans la première part devant 30 être recalculée en étant agencé pour - récupérer une indication des résultats précalculés d'interrogation pour ladite au moins une première part qui a été recalculée au cours d'un intervalle de temps antérieur ; 36 - déterminer l'application d'un mode d'exploitation de l'algorithme d'apprentissage par renforcement ou l'application d'un mode d'exploration de l'algorithme d'apprentissage par renforcement ; et - en réponse à la détermination d'appliquer le mode d'exploitation, déterminer le 5 nombre de résultats précalculés d'interrogation dans la première part devant être recalculée au cours du cycle de calcul actuel sur la base d'une valeur de fonction de l'algorithme d'apprentissage par renforcement pour le nombre de résultats précalculés d'interrogation indiqué par l'indication récupérée, la fonction de valeur associant des sélections possibles de résultats précalculés d'interrogation dans 10 ladite au moins une première part pour un recalcul avec des récompenses respectives estimées. 4. Le dispositif de calcul selon la revendication 3, dans lequel les récompenses estimées associées par la fonction de valeur sont spécifiées par une fonction de récompense de 15 l'algorithme d'apprentissage par renforcement qui attribue une valeur agrégée d'une pluralité d'indicateurs de performance clés à une sélection correspondante de résultats précalculés d'interrogation de ladite au moins une première part. S. Le dispositif de calcul selon la revendication 4, dans lequel la valeur agrégée d'indicateurs de performance clés est basée sur au moins un des indicateurs de performance clés suivants: la somme des nombres de résultat précalculés d'interrogation devant être recalculés, le temps écoulé de recalcul des résultats précalculés d'interrogation devant être recalculés au cours de l'intervalle de temps donné, les ressources de calcul maximum pour recalculer les résultats précalculés d'interrogation indiqués dans la demande et la mémoire maximum requise pour recalculer les résultats précalculés d'interrogation indiqués dans la demande. 6. Le dispositif de calcul selon l'une quelconque des revendications 3 à 5 étant agencé pour déterminer l'application du mode d'exploitation de l'algorithme d'apprentissage par renforcement ou l'application du mode d'exploration de l'algorithme d'apprentissage par renforcement en étant agencé pour - déterminer la récompense donnée par sa fonction de valeur pour les résultats précalculés d'interrogation indiqués par l'indication récupérée ; 37 - déterminer un nombre de cycles de recalcul pour appliquer le mode d'exploitation de l'algorithme d'apprentissage par renforcement basé sur une comparaison de la récompense déterminée avec un seuil de récompense ; - appliquer le mode d'exploitation de l'algorithme d'apprentissage par renforcement 5 pendant le cycle de recalcul actuel et les cycles de recalcul ultérieurs donnés par le nombre déterminé de cycles de recalcul. 7. Le dispositif de calcul selon la revendication 6, dans lequel le seuil de récompense est défini par des pourcentages donnés de valeurs de seuil respectivement pour chacun de la 10 pluralité des indicateurs de performance clés pour lesquels le recalcul pendant l'intervalle de temps donné résulterait en un état d'erreur du dispositif de calcul. 8. Le dispositif de calcul selon la revendication 6 ou 7 étant agencé pour - en réponse à la détermination d'appliquer le mode d'exploration, adapter de façon 15 itérative le nombre de résultats précalculés d'interrogation indiqués par l'indication récupérée sur la base au moins du nombre de résultats précalculés d'interrogation indiqués par l'indication récupérée, la fonction de valeur de l'algorithme d'apprentissage par renforcement pour le nombre de résultats précalculés d'interrogation indiqué par l'indication récupérée et le seuil de récompense. 20 9. Le dispositif de calcul selon l'une quelconque des revendications 1 à 8 étant agencé pour stocker le nombre déterminé de résultats précalculés d'interrogation dans la première part sur un serveur de statistiques pour une détermination ultérieure du nombre de résultats précalculés d'interrogation devant être recalculés au cours d'un cycle ultérieur de calcul. 25 10. Un procédé pour le recalcul de résultats précalculés d'interrogation stockés sur un serveur de base de données, dans lequel les résultats précalculés d'interrogation sont composés d'une pluralité de parts, dans lequel chaque part inclut un certain nombre de résultats précalculés d'interrogation, dans lequel les ressources de calcul d'un dispositif de calcul, 30 nécessaires pour recalculer un résultat précalculé d'interrogation d'une première part, dépendent du fait de recalculer, ou pas, d'autres résultats précalculés d'interrogation de la première part au cours d'un intervalle de temps donné formant un cycle de recalcul actuel, le procédé comprenant, au niveau du dispositif de calcul : 38 - la réception d'une demande de recalcul de résultats précalculés d'interrogation pour au moins une première part ; - la détermination d'un nombre de résultats précalculés d'interrogation dans la première part devant être recalculée au cours du cycle de recalcul actuel sur la base d'un algorithme d'apprentissage par renforcement, le nombre déterminé de résultats précalculés de recherche étant limité aux ressources disponibles de calcul du dispositif de calcul pendant l'intervalle de temps donné ; et - le recalcul du nombre déterminé de résultats précalculés d'interrogation dans la première part au cours du cycle de recalcul. 11. Un produit-programme informatique comprenant des instructions de code de programme stockées sur un support lisible par ordinateur pour mettre en oeuvre les étapes du procédé conformément la revendication 10 lorsque ledit programme fonctionne sur un ordinateur