La présente invention appartient au domaine général du traitement de l'information. Elle concerne plus particulièrement des procédés permettant de déterminer des structures anonymes de données à partir de données « personnelles », ainsi que des procédés permettant de compter des éléments distincts dans des ensembles de données personnelles. Elle concerne également un dispositif de traitement et un système informatique configurés pour mettre en œuvre lesdits procédés.

On entend généralement par « données personnelles » des données qui concernent des personnes identifiées directement ou indirectement.

Les données personnelles peuvent être de différentes natures, et concerner indifféremment des personnes physiques ou morales. Il s'agit par exemple de données médicales, de données universitaires, de données qui reflètent certaines caractéristiques d'individus acquises sur ou via un ou plusieurs réseaux de communication, telles que des données d'un graphe social d'individus représentant un réseau de connexions et de relations de ces individus (couramment désigné par « réseau social »), des données extraites de comptes rendus d'appels réalisés dans un réseau de télécommunications (représentatives de la mobilité des individus entre les différentes antennes relais du réseau), des données de navigation des individus sur le réseau public Internet (et notamment les sites visités et les transitions d'un site à l'autre), des données relatives à l'utilisation par des individus de divers objets connectés, etc.

On comprend bien dès lors que rendre publiques ce type de données peut porter atteinte à la vie privée des individus concernés. Or, avec le développement aujourd'hui des réseaux de télécommunications et des services de plus en plus nombreux qui s'appuient sur ces réseaux (réseaux sociaux, objets connectés, etc.), on assiste à une augmentation spectaculaire des données personnelles qui s'échangent via ou sur ces réseaux.

Il existe aujourd'hui, dans l'état de la technique, différentes méthodes permettant d'anonymiser (i.e. de rendre anonymes) des données personnelles mémorisées dans une base de données. Par opposition aux données personnelles, des données anonymes telles que celles qui peuvent être obtenues via ces méthodes désignent des données à partir desquelles il est impossible de : (i) cibler un individu, (ii) savoir si des données sont liées à un unique individu, et (iii) inférer des informations sur un individu. Ainsi, l'anonymisation de données consiste à modifier le contenu ou la structure des données personnelles afin de rendre difficile, au moins théoriquement, l'identification des individus concernés à partir des données anonymisées.

En ayant accès à de telles données anonymisées, par exemple si une entité qui en possède décide de les rendre publiques, il devient alors possible de réaliser des opérations de comptage avec un risque restreint de dévoiler des informations sensibles sur lesdits individus. En particulier, un intérêt certain est porté (en raison de grandes masses de données qu'il devient possible de collecter) à des opérations visant à compter le nombre de données distinctes dans un ensemble de données anonymisées, afin de réaliser des études statistiques sur des évènements réalisés par les individus concernés durant une durée déterminée.

A titre d'exemple nullement limitatif, de telles études statistiques peuvent concerner la caractérisation de flux de populations dans un espace géographique donné, par exemple pour déterminer quelles actions peuvent être mises en œuvre pour réguler de tels flux (modification d'une ou plusieurs signalisations, construction d'une ou plusieurs nouvelles infrastructures visant à faciliter les déplacements, etc.) ou bien encore par exemple pour évaluer l'attractivité dudit espace géographique. Ainsi, un exemple d'application peut consister à analyser des structures de données obtenues après anonymisation de numéro de téléphone d'individus enregistrés pendant une durée déterminée dans une gare de trains (autrement dit, dans cet exemple d'application, un évènement réalisé par un individu consiste en un appel téléphonique passé ou reçu depuis ladite gare).

Il convient de noter que la problématique du comptage de données anonymisées a déjà été étudiée abondamment. En particulier, il a déjà été proposé différentes méthodes pour construire des structures de données à partir desquelles il est possible de réaliser des opérations de comptage de manière relativement efficace. Ainsi, on connait par exemple les filtres de Bloom, les estimateurs de Flagolet-Martin ainsi que les structures dites de k-valeurs minimum (« k-minimum values » dans la littérature anglo-saxonne, encore abrégé « KMV »). De telles structures sont par exemples décrites dans le document : « Cardinality estimation : An experimental survey », Proceedings of the VLDB Endowment, 11(4) : 499-512, 2017.

Il n'en reste pas moins que chacune de ces structures présentent des désavantages. Ainsi, pour un ensemble de données personnelles donné, un filtre de Bloom contient l'ensemble des valeurs de hachage de ces données personnelles, ce qui ne permet pas de garantir une confidentialité très efficace face à une attaque par exemple de type force brute.

Une structure KMV, bien que plus compacte (seules les k plus petites valeurs de hachage sont contenues dans une structure KMV), hérite du même désavantage d'anonymisation que celui mentionné ci-avant pour un filtre de Bloom.

Enfin, en ce qui concerne un estimateur de Flagolet-Martin, celui-ci ne permet pas de réaliser des opérations de comptage de données distinctes dans des unions ou des intersections d'ensembles, et ce quel que soit le niveau d'anonymisation qu'un tel estimateur peut présenter. Or cela est particulièrement pénalisant lorsqu'il s'agit de réaliser des études statistiques faisant intervenir différents groupes d'individus (exemple : déterminer combien de personnes ont voyagé en train entre deux villes pendant une période donnée de la journée, à partir de deux ensembles de données, chaque ensemble contenant des données personnelles de personnes présentes dans une gare desdites deux villes). En définitive, il ressort de ce qui précède que les structures de données proposées jusqu'alors sont déficientes en ce qu'elles ne permettent pas de faire, de manière simultanée, des opérations de comptage de données distinctes dans des ensembles, et en particulier dans des intersections et des unions d'ensembles, et à la fois de contrôler le niveau d'anonymisation sur ces opérations.

La présente invention a pour objectif de remédier à tout ou partie des inconvénients de l'art antérieur, notamment ceux exposés ci-avant, en proposant une solution qui permette, en comparaison avec les solutions de l'état de la technique, de réaliser des opérations de comptage visant à estimer le nombre d'éléments distincts dans des ensembles de données, en particulier dans des intersections et des unions d'ensembles de données, avec un meilleur compromis en termes de compacité (nombre de données traitées pour fournir une excellente estimation de comptage) et de garantie forte de confidentialité.

A cet effet, et selon un premier aspect, l'invention concerne un procédé de détermination, dit « premier procédé », d'une structure de données à partir d'au moins une donnée d, ladite au moins une donnée étant une donnée personnelle relative à un individu et mémorisée au cours d'un processus de mémorisation de durée déterminée suite à la réalisation d'un évènement par ledit individu. En outre, ledit procédé comporte une étape d'initialisation d'une structure de données L à un ensemble vide ainsi qu'un ensemble E_DET d'étapes de :

- détermination d'une valeur W_{d} égale à b x h(d) + (1-b) x h(V), où :

• h est une fonction de hachage à valeurs discrètes comprises entre 0 et 1,

• b est une variable de Bernoulli de paramètre p, avec

M étant le cardinal de l'image de la fonction de hachage h, et r étant un majorant du nombre de fois où la donnée d peut être mémorisée au cours de ladite durée, et E étant un nombre strictement positif,

• V est une variable aléatoire uniforme indépendante de b, et, si la valeur W_{d} n'appartient pas à la structure L,

- insertion de la valeur W_{d} dans la structure L si le cardinal de ladite structure L est inférieur à un nombre k donné, - sinon, si le cardinal de la structure L est supérieur à k et si la valeur W_{d} est inférieure à la plus grande valeur de la structure L, insertion de la valeur W_{d} dans la structure L par remplacement de ladite plus grande valeur

Ainsi, ledit premier procédé permet d'obtenir une structure de données L plus compacte que l'ensemble de données dont elle est issue, et formée uniquement de valeurs distinctes entre elles, tout en assurant une confidentialité différentielle d'ordre E à ces valeurs (en raison de l'intervalle dans lequel est choisi le paramètre p).

On note qu'une telle structure de données L diffère d'une structure conventionnelle de type KMV dans la mesure où la présence d'une donnée dans ladite structure L est garantie avec une probabilité p (ce qui conduit dès lors à assurer une confidentialité différentielle d'ordre c), là où la structure KMV comporte, par construction, toutes les valeurs de hachage des valeurs distinctes de l'ensemble de données considéré au départ. Ainsi, la structure de données L obtenue au moyen du premier procédé possède un niveau de confidentialité bien meilleure que celui proposé par une structure KMV conventionnelle.

On comprend par ailleurs que le gain en compacité procuré par l'obtention de ladite structure de données L offre la possibilité de réaliser des opérations de comptage (estimation du nombre d'éléments distincts dans un ensemble de données, dans une union d'ensembles de données ou bien encore dans une intersection d'ensembles de données) de manière très efficace (rapidité de calculs, gain de stockage en mémoire, etc.).

Dans des modes particuliers de mise en œuvre, le procédé de détermination peut comporter en outre l'une ou plusieurs des caractéristiques suivantes, prises isolément ou selon toutes les combinaisons techniquement possibles.

Dans des modes particuliers de mise en œuvre, la structure de données L est déterminée à partir d'une pluralité de données, les étapes dudit ensemble E_DET d'étapes étant itérées pour chaque donnée de ladite pluralité de données, la structure de données considérée pour l'insertion d'une donnée lors d'une itération courante de l'ensemble d'étapes E_DET correspondant à la structure de données dans laquelle a été insérée une donnée lors d'une itération de l'ensemble d' étapes E_DET précédant ladite itération courante.

Dans des modes particuliers de mise en œuvre, ledit ensemble E_DET d'étapes est mis en œuvre :

- après que toutes les données de ladite pluralité de données sont mémorisées, ou

- de manière dynamique, après chaque mémorisation d'une donnée de ladite pluralité de données.

Dans des modes particuliers de mise en œuvre, ledit procédé comporte, lors de l'exécution de l'étape d'insertion par remplacement, une étape d'incrémentation d'une valeur dite « valeur de dénombrement » N, ladite valeur de dénombrement N étant représentative, à l'issue du procédé, du nombre total de fois où ladite étape d'insertion par remplacement a été exécutée lors de la mise en œuvre du procédé

Dans des modes particuliers de mise en œuvre, ladite valeur de dénombrement N est initialisée à zéro ou bien initialisée à une réalisation d'une variable aléatoire de Laplace centrée.

Selon un deuxième aspect, l'invention concerne un procédé de détermination, dit « deuxième procédé », d'une structure de données, dite « deuxième structure de données » L2, à partir d'une première structure de données L1 obtenue par application d'un algorithme de k'-valeurs minimales à des données, une donnée étant une donnée personnelle relative à un individu et mémorisée au cours d'un processus de mémorisation de durée déterminée suite à la réalisation d'un évènement par ledit individu, la mise en œuvre dudit algorithme de k'-valeurs minimales utilisant une fonction de hachage h à valeurs discrètes comprises entre 0 et 1. En outre, ledit procédé comporte des étapes de :

- détermination d'une valeur DI égale au quotient de k'-l par la plus grande valeur de la première structure Ll,

- échantillonnage uniforme d'un nombre DI de valeurs dans l'image de la fonction de hachage h, de sorte à obtenir un ensemble L_D1 comprenant lesdits DI valeurs échantillonnées,

- échantillonnage uniforme d'un nombre D2 de valeurs dans l'ensemble L_D1, D2 étant égal à la partie entière du produit [1-p] x Dl, avec

M étant le cardinal de l'image de la fonction de hachage h, et E étant un nombre strictement positif,

- sélection d'un nombre D3 de plus petites valeurs parmi lesdites D2 valeurs échantillonnées, D3 étant égal à la partie entière du produit [1-p] x k, où k est un nombre donné inférieur à k',

- échantillonnage uniforme d'un nombre D4 de valeurs entre la plus grande valeur de la première structure Ll et 1, de sorte à obtenir un ensemble L_D4 comprenant lesdits D4 valeurs échantillonnées, D4 étant égale à Dl-k,

- échantillonnage uniforme d'un nombre D5 de valeurs dans l'union des ensembles L_D1 et L_D4, D5 étant égal à la partie entière du produit p x Dl,

- sélection d'un nombre D6 de plus petites valeurs parmi lesdites D5 valeurs échantillonnées, D6 étant égal à k-D3,

- regroupement desdites plus petites valeurs sélectionnées lors desdites sélections, de sorte à former ladite deuxième structure L2. Ledit deuxième procédé hérite des mêmes avantages que ceux mentionnés ci-avant en référence audit premier procédé.

Selon un troisième aspect, l'invention concerne un procédé d'insertion d'au moins une donnée dans une structure de données L, ladite au moins une donnée étant une donnée personnelle relative à un individu et mémorisée au cours d'un processus de mémorisation de durée déterminée suite à la réalisation d'un évènement par ledit individu. En outre, ledit procédé comporte des étapes de :

- obtention d'une structure de données L déterminée selon un premier procédé de détermination selon le premier aspect ou un deuxième procédé de détermination selon le deuxième aspect,

- mise en œuvre, pour ladite au moins une donnée à insérer, d'un ensemble d'étapes identique à l'ensemble E_DET d'étapes d'un premier procédé de détermination selon le premier aspect.

Ledit troisième procédé hérite des mêmes avantages que ceux mentionnés ci-avant en référence audit premier procédé.

Dans des modes particuliers de mise en œuvre, le procédé d'insertion peut comporter en outre l'une ou plusieurs des caractéristiques suivantes, prises isolément ou selon toutes les combinaisons techniquement possibles.

Dans des modes particuliers de mise en œuvre, une pluralité de données est considérée pour l'insertion dans la structure L, ladite étape de mise en œuvre étant itérée pour chacune des données à insérer, la structure de données considérée pour l'insertion d'une donnée lors d'une itération courante de l'étape de mise en œuvre correspondant à la structure de données dans laquelle a été insérée une donnée lors d'une itération de l'étape de mise en œuvre précédant ladite itération courante.

Dans des modes particuliers de mise en œuvre, ledit ensemble identique audit ensemble E_DET d'étapes du premier procédé de détermination est mis en œuvre :

- après que toutes les données de ladite pluralité de données sont mémorisées, ou

- de manière dynamique, après chaque mémorisation d'une donnée de ladite pluralité de données.

Dans des modes particuliers de mise en œuvre, lorsque la structure de données L obtenue a été déterminée selon un premier procédé de détermination selon le premier aspect, de sorte à obtenir une valeur de dénombrement N correspondant au nombre total de fois où l'étape d'insertion par remplacement a été exécutée, le procédé d'insertion comporte également, lors de l'exécution de l'étape identique à l'étape d'insertion par remplacement dudit premier procédé de détermination, une étape d'incrémentation de ladite valeur de dénombrement N.

Selon un quatrième aspect, l'invention concerne un procédé d'estimation du nombre de données distinctes dans un ensemble de données, une donnée étant une donnée personnelle relative à un individu et mémorisée au cours d'un processus de mémorisation de durée déterminée suite à la réalisation d'un évènement par ledit individu. Ledit procédé comporte des étapes de :

- obtention d'une structure de données déterminée selon un procédé de détermination ou d'insertion tels que décrits précédemment, le cardinal de ladite structure obtenue étant égal à k,

- détermination d'une valeur Q égale au quotient de k-1 par la plus grande valeur de la structure de données obtenue,

- détermination d'un estimateur G du nombre de données distinctes de l'ensemble de données en fonction de Q.

Dans des modes particuliers de mise en œuvre, l'estimateur G est égal à g ^-1 (Q), où g ¹ est une fonction inverse d'une fonction g d'inconnue P et ayant pour expression : g(J3) = (M — /?) x p x a + /? x [b + (/? — 1) x a — (/? — 1) x a x b] expression dans laquelle :

• si les nombres d'occurrences respectifs des données dudit ensemble de données sont tous égaux à une même valeur R donnée, r_moy est égal à R,

• sinon, et si la structure de données est déterminée selon un premier procédé ou un procédé d'insertion tels que décrits précédemment, de sorte à obtenir une valeur de dénombre N, r_moy est égal à la partie entière du quotient de N par Q.

Selon un cinquième aspect, l'invention concerne un procédé d'estimation du nombre de données distinctes dans une union d'une pluralité d'ensembles de données, une donnée étant une donnée personnelle relative à un individu et mémorisée au cours d'un processus de mémorisation de durée déterminée suite à la réalisation d'un évènement par ledit individu. Ledit procédé comporte des étapes de :

- obtention, pour chaque ensemble de données, d'une structure de données déterminée selon un procédé de détermination ou d'insertion tels que décrits précédemment,

- sélection d'un nombre D7 de plus petites valeurs d'une structure correspondant à l'union des structures de données obtenues, D7 étant égal à la plus petite valeur parmi les cardinaux respectifs desdites structures de données obtenues,

- détermination d'une valeur QJJNION égale au quotient de D7-1 par la plus grande valeur parmi lesdites plus petites valeurs sélectionnées, - détermination d'un estimateur GJJNION du nombre de données distinctes de ladite union d'ensembles de données en fonction de QJJNION.

Dans des modes particuliers de mise en œuvre, l'estimateur G_UNION est égal à g ^_1 (Q_UNION), où g ¹ est une fonction inverse d'une fonction g d'inconnue P et ayant pour expression : g(J3) = (M — /?) x p x a + /? x [b + (/? — 1) x a — (/? — 1) x a x b] expression dans laquelle :

• si les nombres d'occurrences respectifs des données desdits ensembles de données sont tous égaux à une même valeur R donnée, r_moy est égal à R,

• sinon, et si la structure de données est déterminée selon un premier procédé ou un procédé d'insertion tels que décrits précédemment, de sorte à obtenir une valeur N_SUM égale à la somme des valeurs de dénombrement respectives desdits structures de données, r_moy est égal à la partie entière du quotient de N_SUM par QJJNION.

Selon un sixième aspect, l'invention concerne un procédé d'estimation du nombre de données distinctes dans une intersection d'une pluralité d'ensembles de données, une donnée étant une donnée personnelle relative à un individu et mémorisée au cours d'un processus de mémorisation de durée déterminée suite à la réalisation d'un évènement par ledit individu. Ledit procédé comporte des étapes de :

- obtention, pour chaque ensemble de données, d'une structure de données déterminée selon un procédé de détermination ou d'insertion tels que décrits précédemment,

- sélection d'un nombre D7 de plus petites valeurs d'une structure correspondant à l'union desdites structures de données obtenues, D7 étant égal à la plus petite valeur parmi les cardinaux respectifs desdites structures de données obtenues,

- détermination d'une valeur QJJNION égale au quotient de D7-1 par la plus grande valeur parmi lesdites plus petites valeurs sélectionnées,

- détermination d'une valeur QJNTER égale au quotient du cardinal d'une structure correspondant à l'intersection desdites structures de données obtenues par D7,

- détermination d'un estimateur G_INTER du nombre de données distinctes de ladite intersection d'ensembles de données en fonction de Q_INTER et QJJNION. Dans des modes particuliers de mise en œuvre, les ensembles de données, dits ensembles « A_l,..., A_T », sont au nombre de T et respectivement associés à des paramètres r_l,..., r_T, le cardinal d'une structure de données associée à un ensemble AJ étant égal à kj, et l'estimateur G_INTER ayant pour expression : expression dans laquelle :

• si, pour chaque ensemble AJ, les nombres d'occurrences respectifs des données dudit ensemble AJ sont tous égaux à une même valeur RJ donnée, rj est égal à RJ,

• sinon, et si la structure de données est déterminée selon un premier procédé ou un procédé d'insertion tels que décrits précédemment, de sorte à obtenir pour chaque structure de donnée associée à un ensemble AJ une valeur de dénombrement NJ, le paramètre rj de chaque ensemble AJ est égal à la partie entière du quotient de NJ par une valeur QJ, ladite valeur QJ étant égale au quotient de kJ- 1 par la plus grande valeur de la structure de données obtenue pour ledit ensemble AJ.

Ainsi, les procédés d'estimation tels que décrits précédemment offrent des fonctionnalités supplémentaires de calculs de cardinaux d'intersections et d'union sur des ensembles de données d'utilisateurs tout en garantissant une protection de la vie privée ces utilisateurs. Un tel avantage n'est pas offert par des solutions connues de l'art antérieur.

Il importe de noter que les premier, deuxième et troisième procédés forment des solutions alternatives à la détermination d'une même structure de données. Une telle structure de données constitue un élément technique particulier sur lequel s'appuient les procédés d'estimation tels que décrits précédemment pour estimer le nombre d'éléments distincts dans des ensembles de données, en particulier dans des intersections et des unions d'ensembles de données, avec un meilleur compromis en termes de compacité et de garantie forte de confidentialité. Dit encore autrement, les différents procédés de l'invention sont liés entre eux par un même concept inventif général consistant en la détermination et l'utilisation d'une structure de données selon l'invention pour réaliser de manière précise et confidentielle les opérations de comptage en question.

Selon un septième aspect, l'invention concerne un programme d'ordinateur comportant des instructions pour la mise en œuvre de l'un quelconque des procédés tels que décrits précédemment lorsque ledit programme d'ordinateur est exécuté par un ordinateur.

Ce programme peut utiliser n'importe quel langage de programmation, et être sous la forme de code source, code objet, ou de code intermédiaire entre code source et code objet, tel que dans une forme partiellement compilée, ou dans n'importe quelle autre forme souhaitable. Selon un huitième aspect, l'invention concerne un support d'informations ou d'enregistrement lisible par un ordinateur sur lequel est enregistré un programme d'ordinateur selon le septième aspect.

Le support d'informations ou d'enregistrement peut être n'importe quelle entité ou dispositif capable de stocker le programme. Par exemple, le support peut comporter un moyen de stockage, tel qu'une ROM, par exemple un CD ROM ou une ROM de circuit microélectronique, ou encore un moyen d'enregistrement magnétique, par exemple une disquette (floppy disc) ou un disque dur.

D'autre part, le support d'informations ou d'enregistrement peut être un support transmissible tel qu'un signal électrique ou optique, qui peut être acheminé via un câble électrique ou optique, par radio ou par d'autres moyens. Le programme selon le septième aspect peut être en particulier téléchargé sur un réseau de type Internet.

Alternativement, le support d'informations ou d'enregistrement peut être un circuit intégré dans lequel le programme est incorporé, le circuit étant adapté pour exécuter ou pour être utilisé dans l'exécution du procédé en question.

Selon un neuvième aspect, l'invention concerne un dispositif de traitement comportant des moyens configurés pour mettre en œuvre un procédé tel que décrit précédemment.

Selon un dixième aspect, l'invention concerne un système informatique comportant :

- une base de données dans laquelle est mémorisée au moins une donnée personnelle relative à un individu, ladite au moins une donnée ayant été mémorisée au cours d'un processus de mémorisation de durée déterminée suite à la réalisation d'un évènement par ledit individu,

- un dispositif de traitement selon le neuvième aspect.

D'autres caractéristiques et avantages de la présente invention ressortiront de la description faite ci- dessous, en référence aux dessins annexés qui en illustrent un exemple de réalisation dépourvu de tout caractère limitatif. Sur les figures :

- la figure 1 représente schématiquement, dans son environnement, un mode particulier de réalisation d'un système informatique selon l'invention ;

- la figure 2 représente schématiquement un exemple d'architecture matérielle d'un dispositif de traitement appartenant au système informatique de la figure 1 ;

- la figure 3 représente sous forme d'ordinogramme, les principales étapes d'un procédé, dit « premier procédé », de détermination d'une structure de données selon l'invention ;

- la figure 4 représente, sous forme d'ordinogramme, les principales étapes d'un procédé, dit « deuxième procédé », de détermination d'une structure de données selon l'invention ; - la figure 5 représente, sous forme d'ordinogramme, les principales étapes d'un procédé, dit « troisième procédé », d'insertion d'au moins une donnée dans une structure de données selon l'invention ;

- la figure 6 représente, sous forme d'ordinogramme, les principales étapes d'un procédé, dit « quatrième procédé », d'estimation du nombre de données distinctes dans un ensemble de données selon l'invention ;

- la figure 7 représente, sous forme d'ordinogramme, les principales étapes d'un procédé, dit « cinquième procédé », d'estimation du nombre de données distinctes dans une union d'ensembles de données selon l'invention ;

- la figure 8 représente, sous forme d'ordinogramme, les principales étapes d'un procédé, dit « quatrième procédé », d'estimation du nombre de données distinctes dans une intersection d'un ensemble de données selon l'invention.

La figure 1 représente schématiquement, dans son environnement, un mode particulier de réalisation d'un système informatique 10 selon l'invention.

Dans le mode de réalisation de la figure 1, le système informatique 10 comporte un dispositif de traitement 11 configuré pour réaliser des traitements permettant d'anonymiser un ou plusieurs ensembles de données (un ensemble pouvant comporter une ou plusieurs données), ainsi que de réaliser des opérations de comptage d'éléments distincts dans de tels ensembles de données, en mettant en œuvre divers procédés selon l'invention et décrits plus en détails ultérieurement.

Les données considérées dans le cadre de la présente invention correspondent à des données relatives à un ou plusieurs individus, et mémorisées au cours d'un processus de mémorisation de durée déterminée suite à la réalisation d'un évènement par ledit ou lesdits individus. Par ailleurs, le ou les ensembles de données à partir desquels sont mis en œuvre les procédés selon l'invention sont eux-mêmes compris dans un ensemble de données plus général et noté « X » (X est donc lui-même un ensemble de données) qui regroupe les données personnelles de tous les individus susceptibles de réaliser ledit évènement pendant ladite durée.

Bien qu'aucune limitation ne soit attachée à la nature des données personnelles considérées et au contexte dans lequel elles ont été acquises, on considère dans le présent mode de réalisation que les données personnelles traitées par le système informatique 10 sont extraites de traces de mobilité identifiées dans un réseau de télécommunications mobiles pour une pluralité d'individus. De telles traces de mobilité sont classiquement remontées dans des comptes rendus d'appels établis par le réseau, et traduisent la mobilité des individus lors de communications établies sur le réseau de télécommunications mobile entre différentes antennes relais du réseau, et ce sur une période de temps donnée. De manière plus spécifique, on considère ici que les données personnelles traitées correspondent à des numéros de téléphone mobiles appartenant à un ou plusieurs individus, ces numéros de téléphone ayant été mémorisés dans une base de données 12 illustrée sur la figure 1, après que lesdits individus ont réalisé une ou plusieurs communications téléphoniques alors même qu'ils se trouvaient dans une gare de trains pendant une période de temps déterminée, par exemple entre 16h et 20h.

Autrement dit, pour cet exemple spécifique de mise en œuvre, on comprend qu'un évènement réalisé par un individu consiste en un appel téléphonique passé ou reçu dans une gare de trains, et que le processus de mémorisation en question consiste en le stockage du numéro de téléphone de cet individu dans la base de données 12 au cours de la période de temps concernée.

Dès lors, un ensemble de données destiné à être utilisé dans un procédé selon l'invention, pour cet exemple spécifique de mise en œuvre, correspond à un ensemble de numéros de téléphone. On note également qu'un numéro de téléphone peut apparaitre plusieurs fois dans un tel ensemble de données si l'individu associé à ce numéro de téléphone a passé et/ou reçu plusieurs appels dans la gare pendant ladite période de temps. Enfin, l'ensemble X correspond, dans cet exemple de mise en œuvre, à tous les numéros de téléphone des individus susceptibles de passer et/ou recevoir un appel téléphonique dans ladite gare. En pratique, l'ensemble X est formé des numéros de tous les habitants de la ville dans laquelle se trouve la gare en question. Mais rien n'exclut non plus de considérer un ensemble X plus grand, comme par exemple formé des numéros de téléphone des individus habitant dans le pays dans lequel se situe ladite gare.

Aucune limitation n'est attachée au nombre de gares pouvant être envisagé, comme cela est détaillé ci-après lors de la description de procédés permettant de fournir des estimations de comptage dans des unions et/ou intersections d'ensemble de données. Bien entendu, on comprend également que la période de temps allant de 16h à 20h (et donc de durée déterminée égale à 4h) n'est donnée ici qu'à titre d'exemple, et que tout autre valeur peut être envisagée.

De manière plus générale, le fait de considérer des données personnelles sous la forme de numéro de téléphone ne constitue qu'un exemple particulier d'application de l'invention, et d'autres exemples peuvent bien entendu être envisagés, comme cela est également décrit ultérieurement au travers de différentes applications techniques de l'invention.

La figure 2 représente schématiquement un exemple d'architecture matérielle du dispositif de traitement 11 appartenant au système informatique 10 de la figure 1, pour la mise en œuvre de différents procédés selon l'invention.

Tel qu'illustré par la figure 2, le dispositif de traitement 11 dispose de l'architecture matérielle d'un ordinateur. Ainsi, le dispositif de traitement 11 comporte, notamment, un processeur 1, une mémoire vive 2, une mémoire morte 3 et une mémoire non volatile 4. Il comporte en outre un module de communication 5. La mémoire morte 3 du dispositif de traitement 11 constitue un support d'enregistrement conforme à l'invention, lisible par le processeur 1 et sur lequel est enregistré une pluralité de programmes d'ordinateur PROG_1, PROG_2, PROG_3, PROG_4, PROG_5, PROG_6 conformes à l'invention, comportant des instructions pour l'exécution d'étapes de procédé selon l'invention. Chacun des programmes PROGJ, i étant un indice entier allant de 1 à 6, définit au moins un module fonctionnel du dispositif de traitement 11, qui s'appuie ou commande les éléments matériels 1 à 5 du dispositif de traitement 11 cités précédemment. Les fonctions exécutées par de tels modules sont précisées ci-après en lien avec la description des procédés pouvant être mis en œuvre lorsque les instructions (sous forme de code) desdits programmes PROGJ sont exécutées par le processeur 1.

Le module de communication 5 permet au dispositif de traitement 11 de communiquer avec la base de données 12, et notamment d'accéder aux données personnelles qui y sont mémorisées. Il peut comprendre par exemple une carte réseau ou tout autre moyen permettant de se connecter à un réseau de communication auxquels appartiennent le dispositif de traitement 11 et la base de données 12, ou bien encore de communiquer sur un bus de données numériques reliant le dispositif de traitement 11 à la base de données 12.

On note que, dans le mode de réalisation de la figure 1, la base de données 12 correspond à un élément distinct du dispositif de traitement 11. Il convient toutefois de noter qu'il ne s'agit là que d'une variante d'implémentation de l'invention, et que rien n'exclut d'envisager que la base de données 12 soit par exemple stockée directement dans une mémoire du dispositif de traitement 11, par exemple dans sa mémoire non volatile 4.

La suite de la description vise à décrire les différents procédés pouvant être mis en œuvre par le dispositif de traitement 11 au moyen respectivement des programmes PROGJ. A cet effet, on considère désormais de manière nullement limitative que le ou les ensembles de données sur lesquels s'appuient ces différents procédés sont issus de la base de données 12 après la fin du processus de mémorisation envisagé au sens de l'invention.

Cela étant, il convient de noter que de telles dispositions ne sont en aucun cas limitatives de l'invention. En particulier, rien n'exclut d'envisager que lesdits procédés soient mis en œuvre de manière dynamique, en parallèle dudit processus de mémorisation et après chaque mémorisation d'une donnée dans la base de données 12.

La figure 3 représente, sous forme d'ordinogramme, les principales étapes d'un procédé de détermination selon l'invention, dit « premier procédé ». Les instructions dédiées à l'exécution des étapes du premier procédé sont contenues dans le programme PROG_1.

Dans son principe général, ledit premier procédé de détermination consiste à générer, à partir d'un ensemble A de données personnelles, une structure de données garantissant une confidentialité différentielle d'ordre E dudit ensemble A, et à partir de laquelle il est possible de réaliser des opérations de comptage d'éléments distincts de manière particulièrement efficace. La méthode d'anonymisation dite de « confidentialité différentielle », plus communément désignée par « privacy différentielle » ou encore par « differential privacy » en anglais, est bien connue de l'homme du métier. Elle permet d'anonymiser des données et est particulièrement appréciée car elle permet de quantifier formellement et rigoureusement le niveau d'anonymat obtenu, autrement dit, le risque de ré-identifier à partir des données anonymes obtenues (i.e. les données contenues dans la structure de données générée au moyen du premier procédé de détermination) les données personnelles relatives aux individus en jeu. Ceci offre avantageusement la possibilité de contrôler le compromis entre utilité des données anonymes obtenues et niveau d'anonymat garanti.

En effet, un niveau d'anonymat trop élevé peut se traduire par une perte d'information utile concernant les données d'origine. Inversement, un jeu de données anonymes trop proche du jeu de données initial dévoile trop d'informations sur les individus concernés. Un tel contrôle est donc important car il permet de savoir si le niveau d'anonymat considéré est raisonnable ou non.

En pratique, la mesure du niveau d'anonymat s'effectue au moyen d'un paramètre, noté E dans le cadre de la présente invention, et traduisant le fait que deux structures de données générées grâce audit premier procédé ont quasiment la même loi de probabilité si les ensembles de données fournis en entrée du premier procédé sont voisins, c'est-à-dire diffèrent par la contribution d'une unique donnée. Le « quasiment » est mesuré par ledit paramètre c : plus c est petit, plus les lois de probabilités sont proches et plus il est difficile de détecter la participation d'un individu particulier dans les structures de données (meilleur est donc l'anonymat atteint), ce qui correspond au but recherché par la confidentialité différentielle. On note que le paramètre c et l'anonymat atteint par l'algorithme varient en sens inverse, i.e. plus c est petit et meilleur est l'anonymat garanti par l'algorithme.

Dans la mesure où la confidentialité différentielle a été étudiée abondamment, elle n'est pas décrite plus avant ici. Pour plus de détails, il est par exemple possible de se référer au document de C. Dwork, F. McSherry, K. Nissim et A. Smith 15 intitulé « Calibrating Noise to Sensitivity in Private Data Analysis », Theory of Cryptography, pages 265-284, 2006.

Ledit premier procédé comporte tout d'abord une étape E10 d'initialisation d'une structure de données L à un ensemble vide, ladite étape E10 d'initialisation est mise en œuvre par un module d'initialisation (non représenté sur les figures) équipant le dispositif de détermination 11 et configuré à cet effet.

L'objectif de l'étape E10 est donc de créer une structure apte à recevoir des données. En pratique, d'un point de vue informatique, la mise en œuvre de ladite étape E10 consiste à instancier une liste vide.

Ledit premier procédé comporte également un ensemble E_DET d'étapes mises en œuvre pour chaque donnée de l'ensemble A. Afin de décrire la mise en œuvre dudit ensemble d'étapes E_DET, on considère une donnée, notée « d », de l'ensemble A. Dès lors, pour ladite donnée d, ledit ensemble d'étapes E_DET comporte une étape E_DET_10 de détermination d'une valeur W_{d} égale à b x h(d) + (1-b) x h(V), où :

• h est une fonction de hachage définie sur l'ensemble X et à valeurs discrètes dans l'intervalle [0,1], par exemple à valeurs uniformément réparties entre 0 et 1,

• b est une variable de Bernoulli de paramètre p, avec

M étant le cardinal de l'image de la fonction de hachage h, et r étant un majorant du nombre de fois où la donnée d peut être mémorisée au cours de ladite durée,

• V est une variable aléatoire uniforme sur l'ensemble X et indépendante de b. Ladite étape E_DET_10 est mise en œuvre par un module de détermination (non représenté sur les figures) équipant le dispositif de détermination 11 et configuré à cet effet.

La valeur du paramètre r intervenant dans l'encadrement du paramètre p est déterminée par l'application envisagée pour ledit premier procédé.

Ainsi, dans le présent mode de mise en œuvre, en considérant, comme mentionné auparavant, qu'une donnée personnelle correspond au numéro de téléphone mobile appartenant à un individu, ce numéro ayant été mémorisé dans la base de données 12 durant une période de 4h (période de temps allant de 16h à 20h) dans une gare de trains déterminée, le paramètre r peut par exemple être fixé à 5. Il est en effet raisonnable de penser qu'un individu ne passe pas et/ou ne reçoit pas plus de cinq appels téléphoniques en l'espace de quatre heures dans ladite gare.

Bien entendu, le choix consistant à considérer r égal à 5 ne constitue qu'une variante d'implémentation de l'invention, et d'autres valeurs sont envisageables dès lors qu'elles reflètent la réalité de l'application envisagée pour la mise en œuvre dudit premier procédé. En particulier, rien n'exclut, pour ce qui concerne le présent mode de mise en œuvre, de considérer une valeur inférieure ou supérieure à 5.

D'une manière générale, l'homme du métier est en mesure de fixer une valeur pour le paramètre r eu égard à l'application envisagée.

La valeur du paramètre M intervenant dans l'encadrement du paramètre p est elle aussi déterminée par l'application envisagée pour ledit premier procédé. Ainsi, en reprenant les considérations évoquées ci-dessus pour le paramètre r, le paramètre M peut par exemple être fixé à un million. Rien n'exclut cependant de considérer une autre valeur pour le paramètre M, cette valeur étant préférentiellement au moins de l'ordre du carré du cardinal de l'ensemble X, de sorte à éviter tout risque de collisions dans l'image de la fonction de hachage h (de telles collisions pouvant en effet être la source d'erreurs d'estimation de cardinaux pour des procédés d'estimation selon l'invention qui sont décrits plus en détails ultérieurement).

Il importe de noter que le fait de choisir p en respectant l'encadrement proposé ci-avant permet avantageusement de garantir une confidentialité différentielle d'ordre E de la structure de données obtenue à l'issue dudit premier procédé, comme l'inventeur a été en mesure de le démontrer.

On note par ailleurs que l'encadrement donné ci-avant pour le paramètre p traduit le niveau de confidentialité que l'on souhaite accorder aux données formant la structure de données obtenue à l'issue dudit premier procédé. Plus précisément, plus p est proche de la valeur 1/2, plus la structure de données obtenue à l'issue du premier procédé protège les données qu'elle contient contre un risque de ré-identification.

Ledit ensemble E_DET d'étapes comporte également, pour ladite donnée d, une première étape E_DET_20 de test consistant à vérifier si la valeur W_{d} appartient ou non à la structure L jusqu'alors déterminée. Ladite première étape E_DET_20 est mise en œuvre par un premier module de test (non représenté sur les figures) équipant le dispositif de détermination 11 et configuré à cet effet.

Dès lors, si la valeur W_{d} n'appartient pas à la structure L (réponse négative à la première étape E_DET_20 de test), ledit ensemble E_DET d'étapes comporte une deuxième étape E_DET_30 de test consistant à vérifier si le cardinal de ladite structure L est inférieur à un nombre k donné. Ladite deuxième étape E_DET_30 est mise en œuvre par un deuxième module de test (non représenté sur les figures) équipant le dispositif de détermination 11 et configuré à cet effet.

Dès lors, si le cardinal de ladite structure L est inférieur à k (réponse positive à la deuxième étape E_DET_30 de test), l'ensemble E_DET d'étapes comporte une étape E_DET_40 d'insertion de la valeur W_{d} dans la structure L.

A contrario, si le cardinal de la structure L est supérieur à k, ledit ensemble E_DET d'étapes comporte une troisième étape E_DET_50 de test consistant à vérifier si la valeur W_{d} est inférieure à la plus grande valeur de la structure L jusqu'alors déterminée. Ladite troisième étape E_DET_50 est mise en œuvre par un troisième module de test (non représenté sur les figures) équipant le dispositif de détermination 11 et configuré à cet effet.

Dès lors, si la valeur W_{d} est inférieure à la plus grande valeur de la structure L (réponse positive à la troisième étape E_DET_50 de test), l'ensemble d'étapes E_DET comporte une étape E_DET_60 d'insertion de la valeur W_{d} dans la structure L par remplacement de ladite plus grande valeur.

Ledit ensemble E_DET d'étapes a été décrit jusqu'à présent pour une seule donnée d appartenant à l'ensemble A. Les autres données appartenant à l'ensemble A sont traitées de manière similaire, à savoir que les étapes dudit ensemble E_DET d'étapes sont itérées pour chacune desdites autres données de l'ensemble A. Les exécutions de ces itérations s'effectuent de sorte que la structure de données considérée pour l'insertion d'une donnée lors d'une itération courante de l'ensemble d'étapes E_DET correspond à la structure de données dans laquelle a été insérée une donnée lors d'une itération de l'ensemble d'étapes E_DET précédant ladite itération courante.

Etant donné la nature desdites deuxième et troisième étapes de test E_DET_30, E_DET_50, on comprend que le nombre k correspond à une taille qu'il convient de ne pas dépasser pour ladite structure L. Il s'agit donc d'un nombre fixé, et avantageusement inférieur au cardinal de l'ensemble de données A de sorte que la structure de données L obtenue à l'issu du premier procédé est plus compacte que ledit ensemble de données A.

On note également, étant donné la nature de la première étape E_DET_20 de test que la structure de données L obtenue à l'issue du premier procédé ne comporte que des valeurs distinctes entre elles.

En définitive, à l'issue dudit premier procédé, on obtient une structure de données L plus compacte que l'ensemble A dont elle est issue, formée uniquement de valeurs distinctes entre elles, et qui assure une confidentialité différentielle d'ordre E à ces valeurs.

On note qu'une telle structure de données L diffère d'une structure conventionnelle de type KMV dans la mesure où la présence d'une donnée dans ladite structure L est garantie avec une probabilité p (ce qui conduit dès lors à assurer une confidentialité différentielle d'ordre c), là où la structure KMV comporte, par construction, toutes les valeurs de hachage des valeurs distinctes de l'ensemble A. Ainsi, la structure de données L obtenue au moyen du premier procédé possède un niveau de confidentialité bien meilleure que celui proposé par une structure KMV conventionnelle.

On note que le premier procédé de détermination a été décrit jusqu'à présent en considérant qu'un ensemble de données A comporte une pluralité de données. On comprend toutefois qu'il est possible de le mettre en œuvre en ne considérant qu'une seule donnée personnelle (auquel cas, bien entendu, les étapes dudit ensemble d'étapes E_DET ne sont exécutées qu'une seule fois).

On note également que le premier procédé a été décrit ci-avant en référence aux principales étapes exécutées lors de la mise en œuvre dudit premier procédé. Il n'en reste pas moins qu'il reste possible d'envisager des modes plus particuliers de mise en œuvre dudit premier procédé dans lesquels encore d'autres étapes peuvent être exécutées. De tels autres modes de mise en œuvre sont notamment utiles pour la mise en œuvre de procédé de comptage dans des ensembles, comme cela est décrit plus en détails ultérieurement.

Ainsi, dans un mode particulier de mise en œuvre, ledit premier procédé comporte également, pour chaque exécution de l'étape E_DET_60 d'insertion par remplacement, une étape d'incrémentation d'une valeur dite « valeur de dénombrement » N. De cette manière, ladite valeur de dénombrement N est représentative, à l'issue du procédé, du nombre total de fois où ladite étape d'insertion par remplacement a été exécutée lors de la mise en œuvre du procédé.

Ladite valeur de dénombrement N est par exemple initialisée à zéro.

Selon un autre exemple, ladite valeur de dénombrement N est initialisée à une réalisation d'une variable aléatoire de Laplace centrée. Procéder de cette manière se révèle avantageux dans la mesure où l'information obtenue à l'issue du premier procédé, à savoir donc un couple formé de la structure de données L et de ladite valeur de dénombrement N, respecte également le principe de la confidentialité différentielle, comme cela est par exemple expliqué dans le document de Dwork et al. déjà mentionné auparavant.

L'invention ne se limite pas à obtenir une structure de données L telle que celle décrite ci-avant à partir du seul premier procédé. En effet, l'invention propose également, selon un autre aspect, de générer, à partir d'une structure KMV préalablement déterminée pour ledit ensemble A, une structure de données plus compacte que l'ensemble A dont elle est issue, formée uniquement de valeurs distinctes entre elles, et qui assure une confidentialité d'ordre E à ces valeurs. Dit encore autrement, l'invention propose également de transformer une première structure L1 de type KMV en une deuxième structure L2 héritant des mêmes avantages que ceux décrits précédemment en référence à la structure L obtenue à l'issue du premier procédé.

La figure 4 représente, sous forme d'ordinogramme, les principales étapes d'un autre procédé de détermination selon l'invention, dit « deuxième procédé ». Les instructions dédiées à l'exécution des étapes du deuxième procédé sont contenues dans le programme PROG_2.

Pour la description du deuxième procédé de la figure 4, on considère à nouveau un ensemble A comportant une pluralité de données personnelles. On considère également qu'une première structure de données L1 a été obtenue par application d'un algorithme de k'-valeurs minimales aux données de l'ensemble A. On note que la mise en œuvre dudit algorithme de k'-valeurs minimales utilise de manière conventionnelle une fonction de hachage h, cette fonction de hachage étant définie dans le cadre de la présente invention sur l'ensemble X (c'est une fonction de hachage à valeurs discrètes dans l'intervalle [0,1], par exemple à valeurs uniformément réparties entre 0 et 1). On note par ailleurs que le nombre k' correspond, de manière connue en soi, au cardinal de la première structure Ll, et est fixé en fonction de l'application envisagée.

Par exemple, dans le contexte applicatif envisagé ici (appels passés et/ou reçus dans une gare par des individus et pendant une période de temps de 4h), ledit nombre k' peut être pris égal à 100.

De manière générale, on note que le nombre k' est représentatif d'un compromis entre capacité à stocker suffisamment de données pour pouvoir réaliser des estimations de comptage fiables (meilleur quand k' est grand) et la compacité de la structure Ll (meilleure compacité quand k' est petit). Tel qu'illustré par la figure 4, ledit deuxième procédé comporte une étape F10 de détermination d'une valeur DI égale au quotient de k'-l par la plus grande valeur de la première structure Ll. Ladite étape F10 de détermination est mise en œuvre par un module de détermination (non représenté sur les figures) équipant le dispositif de détermination 11 et configuré à cet effet.

Le deuxième procédé comporte également une étape F20 d'échantillonnage uniforme d'un nombre DI de valeurs dans l'image de la fonction de hachage h, i.e. dans h(X), de sorte à obtenir un ensemble L_D1 comprenant lesdites DI valeurs échantillonnées. Ladite étape F20 est mise en œuvre par un premier module d'échantillonnage (non représenté sur les figures) équipant le dispositif de détermination 11 et configuré à cet effet.

Par « échantillonnage uniforme d'une valeur dans un ensemble », on fait classiquement référence au fait de sélectionner aléatoirement une valeur dudit ensemble avec une probabilité uniforme égale à l'inverse du cardinal dudit ensemble. En conséquence, l'échantillonnage uniforme d'une pluralité de valeurs dans ledit ensemble consiste à répéter l'opération précédente (avec remise) autant de fois que le nombre de valeurs de ladite pluralité de valeurs.

Le deuxième procédé comporte également une étape F30 échantillonnage uniforme d'un nombre D2 de valeurs dans l'ensemble L_D1, D2 étant égal à la partie entière du produit de [1-p] par DI (i.e. [1-p] x Dl), avec, de manière similaire à ce qui a été décrit auparavant dans le cadre du premier procédé :

Ladite étape F30 est mise en œuvre par un deuxième module d'échantillonnage (non représenté sur les figures) équipant le dispositif de détermination 11 et configuré à cet effet.

On note que l'encadrement proposé pour le paramètre p dans le cadre dudit deuxième procédé diffère sensiblement de celui proposé dans le cadre du premier procédé en ce que le paramètre r est ici considéré égal à 1. Une telle variation découle du fait que le deuxième procédé utilise comme point de départ la structure Ll qui est une structure KMV conventionnelle, l'objectif étant, notamment, de transformer cette structure Ll en une autre structure fournissant une garantie de confidentialité différentielle. Or, de manière connue en soi, les données contenues dans une structure KMV conventionnelle, et donc a fortiori dans la structure Ll, sont toutes distinctes les unes des autres, de sorte que le nombre maximal de fois où une donnée peut apparaitre dans la structure Ll est égal à 1.

Ledit deuxième procédé comporte également une étape F40 de sélection d'un nombre D3 de plus petites valeurs parmi lesdites D2 valeurs échantillonnées, D3 étant égal à la partie entière du produit [1-p] x k, où k est un nombre donné inférieur à k'. Ladite étape F40 est mise en œuvre par un premier module de sélection (non représenté sur les figures) équipant le dispositif de détermination 11 et configuré à cet effet.

Ledit deuxième procédé comporte également une étape F50 d'échantillonnage uniforme d'un nombre D4 de valeurs entre la plus grande valeur de la première structure L1 et 1, de sorte à obtenir un ensemble L_D4 comprenant lesdites D4 valeurs échantillonnées, D4 étant égale à Dl-k. Ladite étape F50 est mise en œuvre par un troisième module d'échantillonnage (non représenté sur les figures) équipant le dispositif de détermination 11 et configuré à cet effet.

Ledit deuxième procédé comporte également une étape F60 d'échantillonnage uniforme d'un nombre D5 de valeurs dans l'union des ensembles L_D1 et L_D4, D5 étant égal à la partie entière du produit p x Dl. Ladite étape F60 est mise en œuvre par un quatrième module d'échantillonnage (non représenté sur les figures) équipant le dispositif de détermination 11 et configuré à cet effet.

Ledit deuxième procédé comporte également une étape F70 de sélection d'un nombre D6 de plus petites valeurs parmi lesdites D5 valeurs échantillonnées, D6 étant égal à k-D3. Ladite étape F70 est mise en œuvre par un deuxième module de sélection (non représenté sur les figures) équipant le dispositif de détermination 11 et configuré à cet effet.

Ledit deuxième procédé comporte également une étape F80 de regroupement desdites plus petites valeurs sélectionnées lors desdites sélections, de sorte à former une deuxième structure L2.

En définitive, à l'issue dudit deuxième procédé, et de manière similaire à ce qui a été décrit ci-avant pour le premier procédé, on obtient une structure de données L2 plus compacte que l'ensemble A dont elle est issue, formée uniquement de valeurs distinctes entre elles, et qui assure une confidentialité d'ordre E à ces valeurs.

En outre, cette structure de données L2 présente également l'avantage d'être plus compacte que la structure de données L1 étant donné que k est inférieur à k', tout en offrant une garantie de confidentialité beaucoup plus forte.

D'un point de vue théorique, il convient d'observer que le résultat du mécanisme consistant à générer la structure de données L2 à partir de la structure de données L1 satisfait la garantie de confidentialité d'ordre c différentielle dès lors que k' est supérieur à [1-p] x D_A + p x k, où D_A correspond au nombre d'éléments distincts de l'ensemble A. Or, le nombre k' étant donné par le cas d'application du deuxième procédé, on comprend qu'il faut choisir k de sorte que la condition k' est supérieur [1-p] x D_A + p x k soit satisfaite. Les structures de type KMV étant utilisées dans les situations où k' est inférieur à D_A (sinon il suffirait de stocker toutes les données de l'ensemble A pour en compter les éléments distincts), le choix consistant à avoir k inférieur à k' permet donc de garantir la confidentialité différentielle d'ordre c de la structure L2.

On comprend donc que l'invention permet d'obtenir une structure de données compacte et garantissant une confidentialité différentielle d'ordre c de deux manières différentes : soit en créant ladite structure de données directement à partir d'un ensemble brut de données A, soit en transformant une structure de données de type KMV elle-même obtenue à partir dudit ensemble brut de données A.

Selon un autre aspect, l'invention permet également d'enrichir une structure de données indifféremment obtenue selon le premier procédé ou le deuxième procédé, en y insérant une donnée nouvellement mémorisée dans la base de données 12.

La figure 5 représente, sous forme d'ordinogramme, les principales étapes d'un procédé d'insertion de données selon l'invention, dit « troisième procédé ». Les instructions dédiées à l'exécution des étapes du troisième procédé sont contenues dans le programme PROG_3.

Pour la description du troisième procédé de la figure 5, on considère à nouveau un ensemble A comportant une pluralité de données personnelles. On considère également une donnée d_new nouvellement mémorisée dans la base de données, par exemple suite à une nouvelle exécution du processus de mémorisation, ladite donnée d_new correspondant là encore à une donnée personnelle relative à un individu et mémorisée suite à la réalisation d'un évènement (appel téléphonique passé ou reçu dans la gare de trains dans le présent mode de mise en œuvre) par ledit individu.

Ledit troisième procédé comporte dès lors une étape G10 d'obtention d'une structure L déterminée selon ledit premier procédé ou bien selon ledit deuxième procédé.

Dans un mode particulier de mise en œuvre, ladite étape G10 d'obtention consiste en la mise en œuvre du premier procédé ou bien du deuxième procédé en considérant les données de l'ensemble A. Bien entendu, dans le cas où c'est le deuxième procédé qui est mis en œuvre, on comprend que ledit troisième procédé s'appuie sur une première structure obtenue par application d'un algorithme de k'-valeurs minimales à l'ensemble A.

Dans un autre mode particulier de mise en œuvre, ladite structure de données L a été déterminée par le dispositif 11 de détermination au moyen du premier procédé ou du deuxième procédé, et préalablement à ladite étape G10 d'obtention. Dans ce cas, le terme « obtention » fait référence à un accès à une mémoire du dispositif de détermination 11 dans laquelle a été stockée la structure L à l'issue du premier procédé ou du deuxième procédé.

Ledit troisième procédé comporte également une étape G20 de mise en œuvre, pour ladite donnée d_new, d'un ensemble d'étapes identique à l'ensemble E_DET d'étapes dudit premier procédé. Autrement dit, les étapes E_DET_10 à E_DET_60 (le cas échéant) sont exécutées pour ladite donnée d_new.

Bien entendu, ledit troisième procédé ne se limite pas à l'insertion d'une seule donnée dans la structure L. Il est en effet possible d'insérer une pluralité de données dans la structure L en réitérant, de manière similaire à ce qui a été décrit pour le premier procédé, les étapes dudit ensemble E_DET d'étapes pour chacun desdites données à insérer. En outre, lorsque la structure de données L obtenue a été déterminée selon le premier procédé, de sorte à obtenir une valeur de dénombrement N correspondant au nombre total de fois où l'étape E_DET_60 d'insertion par remplacement a été exécutée lors dudit premier procédé, le troisième procédé peut également comporter, suivant un mode particulier de mise en œuvre, une mise à jour de ladite valeur de dénombrement N. Plus précisément, dans ce mode particulier de mise en œuvre, ledit troisième procédé comporte, lors de la mise en œuvre de l'étape G20, et pour chaque exécution de l'étape identique à l'étape E_DET_60 d'insertion par remplacement dudit premier procédé, une étape d'incrémentation de ladite valeur de dénombrement N. Autrement dit, dans ce mode particulier de mise en œuvre, le décompte du nombre de fois où une insertion par remplacement est exécutée est poursuivi.

Il est à noter qu'il a été considéré jusqu'à présent que le dispositif en charge de la mise en œuvre du troisième procédé est le dispositif de détermination 11 de la figure 1. Cela étant, rien n'exclut d'envisager que ledit troisième procédé soit mis en œuvre par un autre dispositif configuré de manière similaire audit dispositif de détermination 11, après que ce dernier ait déterminé la structure L. Dans ce cas, le terme « obtention » pour ladite étape G10 d'obtention fait référence à un transfert de données (émission/réception) entre le dispositif de détermination 11 et ledit autre dispositif. Ce transfert de données est mis en œuvre par le module de communication 5 équipant le dispositif de détermination 11 ainsi que par un module de communication similaire équipant ledit autre dispositif.

L'invention ne se limite pas à l'obtention de structures de données au moyen desdits premier, deuxième et troisième procédés. En effet, l'invention permet également, à partir d'une structure ainsi obtenue, de réaliser des opérations de comptage visant à estimer le nombre d'éléments distincts dans un ensemble de données, ledit ensemble de données pouvant notamment lui-même résulter d'union(s) ou d'intersection(s) d'ensembles de données.

La figure 6 représente, sous forme d'ordinogramme, les principales étapes d'un procédé de comptage selon l'invention, dit « quatrième procédé ». Les instructions dédiées à l'exécution des étapes du quatrième procédé sont contenues dans le programme PROG_4.

Ledit quatrième procédé consiste à estimer le nombre de données distinctes présentes dans l'ensemble A. Pour ce faire, ledit quatrième procédé prend appui sur une structure de données déterminée pour ledit ensemble A au moyen de l'un quelconque desdits premier, deuxième et troisième procédés. Par la suite, le nombre de données distinctes présentes dans l'ensemble A est estimé, notamment, à partir d'une quantité extraite de caractéristiques de la structure de données déterminée.

Pour la description du quatrième procédé de la figure 6, on considère à nouveau un ensemble A comportant une pluralité de données personnelles, comme cela était le cas pour les figures 3, 4 et 5. On note alors qu'étant donné le contexte applicatif considéré ici, estimer le nombre de données distinctes contenues dans l'ensemble A revient à estimer le nombre d'individus ayant passé et/ou reçu des appels téléphoniques dans la gare pendant la période de temps concernée.

Ledit quatrième procédé comporte dans un premier temps une étape H 10 d'obtention d'une structure de données L pour ledit ensemble A, ladite structure de donnée L étant déterminée selon l'un quelconque desdits premier, deuxième et troisième procédé, et le cardinal de ladite structure obtenue étant égal à un nombre k.

Les considérations techniques décrites ci-avant pour l'étape G10 du troisième procédé en ce qui concerne la signification du terme « obtention » s'appliquent ici de la même manière pour l'étape H10.

Pour rappel, la détermination de ladite structure de données L s'effectue au moyen du paramètre p, dont la valeur est choisie de sorte à être majorée par une quantité qui dépend du nombre M, et ce de sorte à garantir la confidentialité différentielle d'ordre E de ladite structure de données L.

Ledit quatrième procédé comporte également une étape H20 de détermination d'une valeur Q égale au quotient de k-1 par la plus grande valeur de la structure de données L (i.e. Q = (k-l)/max(L)). Ladite étape H20 est mise en œuvre par un module de détermination (non représenté sur les figures) équipant le dispositif de détermination 11 et configuré à cet effet.

Ledit quatrième procédé comporté également une étape H30 de détermination d'un estimateur G du nombre de données distinctes de l'ensemble A en fonction de Q.

En définitive, on obtient donc un estimateur G à partir d'une structure de données L qui est plus compacte que l'ensemble A et qui garantit en outre une confidentialité différentielle d'ordre c.

Dans un mode particulier de mise en œuvre, l'estimateur G est égal à g ^-1 (Q), où g ¹ est une fonction inverse d'une fonction g d'inconnue P et ayant pour expression : expression dans laquelle :

Il est à noter que l'expression du coefficient a fait intervenir le coefficient binomial qui peut encore s'écrire, suivant une autre convention : cr ^l _moy

Le paramètre r_moy considéré dans les expressions des coefficients a et b peut prendre différentes valeurs en fonction d'hypothèses faites sur le contexte applicatif envisagé pour ledit quatrième procédé.

Ainsi, on peut par exemple considérer une hypothèse selon laquelle les nombres d'occurrences respectifs des données dudit ensemble A sont tous égaux à une même valeur R donnée. Dans ce cas, le paramètre r_moy est égal à R. Donc en particulier, s'il est raisonnable de supposer que chaque donnée de l'ensemble A n'apparait qu'une seule fois dans ledit ensemble A, on obtient les expressions simplifiées suivantes pour les coefficients a et b :

Selon un autre exemple, on considère une hypothèse selon laquelle l'ensemble A comporte plusieurs données dont les nombres d'occurrences respectifs dans ledit ensemble A diffèrent entre eux. Dans ce cas, le paramètre r_moy est égal à la partie entière du quotient de N par Q. On rappelle ici que N correspond à la valeur de dénombrement mentionnée auparavant, ce qui implique donc que pour mettre en œuvre le quatrième procédé dans le présent exemple, il importe que la structure de données L soit déterminée au moyen d'un mode de mise en œuvre du premier ou troisième procédé permettant d'obtenir ladite valeur N de dénombrement.

Il importe de noter que le fait de considérer une valeur de r_moy égale à la partie entière du quotient de N par Q n'est pas limité à la seule hypothèse considérée dans l'exemple précédent. Ainsi, une telle valeur de r_moy peut par exemple également être utilisée lorsque les nombres d'occurrences respectifs des données dudit ensemble A sont tous égaux à une même valeur, sans pour autant que la valeur commune soit connue.

Par ailleurs, le fait de considérer une détermination de l'estimateur G au moyen de ladite fonction g- ¹ ne constitue qu'une variante particulière de mise en œuvre du quatrième procédé. Cette variante se révèle particulièrement avantageuse pour fournir une estimation très précise du nombre de données distinctes présentes dans l'ensemble A. L'invention couvre néanmoins d'autres modes de mise en œuvre du quatrième procédé, comme par exemple un mode dans lequel l'estimateur G est déterminé égal à Q. La figure 7 représente, sous forme d'ordinogramme, les principales étapes d'un autre procédé de comptage selon l'invention, dit « cinquième procédé ». Les instructions dédiées à l'exécution des étapes du cinquième procédé sont contenues dans le programme PROG_5.

Ledit cinquième procédé consiste à estimer le nombre de données distinctes présentes dans l'union d'une pluralité d'ensembles de données A_l, A_2,..., A_T, T étant un nombre entier strictement supérieur à 1 (un ensemble de donnée AJ, i étant un indice entier compris entre 1 et T, correspondant par exemple à l'ensemble A considéré pour le quatrième procédé).

Ledit cinquième procédé comporte dans un premier temps une étape J 10 d'obtention, pour chaque ensemble de données AJ, d'une structure de données LJ déterminée selon l'un quelconque desdits premier, deuxième et troisième procédé, le cardinal de ladite structure LJ étant égal à un nombre kj (on note que les valeurs k_l, ..., k_T peuvent être, en tout ou partie, distinctes entre elles).

La mise en œuvre de ladite étape J 10 est similaire à celle de l'étape H 10.

Ledit cinquième procédé comporte également une étape J20 de sélection d'un nombre D7 de plus petites valeurs d'une structure dite « structure d'union » L_UNION correspondant à l'union des structures de données L_l, LJ’,..., L_T. Ledit nombre D7 est égal à la plus petite valeur parmi les cardinaux respectifs desdites structures de données L_l, LJ’,..., L_T (i.e. D7 = min(k_l,..., k_T)).

Le cinquième procédé comporte également une étape J30 de détermination d'une valeur QJJNION égale au quotient de D7-1 par la plus grande valeur parmi lesdites D7 plus petites valeurs sélectionnées.

Le cinquième procédé comporte également une étape J40 de détermination d'un estimateur GJJNION du nombre de données distinctes de ladite union d'ensembles de données A_l, AJ’,..., A_T en fonction de QJJNION.

En définitive, on obtient donc un estimateur GJJNION à partir d'une structure de données LJJNION qui est plus compacte que l'union des ensembles de données A_l, A_2,..., A_T, et qui garantit en outre une confidentialité différentielle d'ordre E.

Dans un mode particulier de mise en œuvre, l'estimateur G_UNION est égal à g ^-1 (Q_UNION), où g ¹ est une fonction inverse d'une fonction g d'inconnue P et ayant pour expression : expression dans laquelle :

Le paramètre r_moy considéré dans les expressions des coefficients a et b peut prendre différentes valeurs en fonction d'hypothèses faites sur le contexte applicatif envisagé pour ledit cinquième procédé.

Ainsi, on peut par exemple considérer une hypothèse selon laquelle les nombres d'occurrences respectifs des données desdits ensembles A_l, A_2,..., A_T sont tous égaux à une même valeur R donnée. Dans ce cas, le paramètre r_moy est égal à R.

Selon un autre exemple, on considère une hypothèse selon laquelle ladite union d'ensembles de données A_l, A_2,..., A_T comporte plusieurs données dont les nombres d'occurrences respectifs dans ladite union diffèrent entre eux. Dans ce cas, le paramètre r_moy est égal à la partie entière du quotient d'une valeur N_SUM par QJJNION, ladite valeur N_SUM étant égale à la somme des valeurs de dénombrement respectives desdites structures de données L_l, L_2,..., L_T. On note donc que pour mettre en œuvre le cinquième procédé dans le présent exemple, il importe que chaque structure de données LJ soit déterminée au moyen d'un mode de mise en œuvre du premier ou troisième procédé permettant d'obtenir une valeur de dénombrement NJ associée à ladite structure LJ. On a également que N_SUM est égale à N_1+N_2+...N_T.

Il importe de noter que le fait de considérer une valeur de r_moy égale à la partie entière du quotient de N_SUM par Q_UNION n'est pas limité à la seule hypothèse considérée dans l'exemple précédent. Ainsi, une telle valeur de r_moy peut par exemple également être utilisée lorsque les nombres d'occurrences respectifs des données de ladite union d'ensembles A_l, A_2,..., A_T sont tous égaux à une même valeur, sans pour autant que la valeur commune soit connue. Une telle valeur de r_moy peut également être envisagée dans le cas où les nombres d'occurrences respectifs des données d'un ensemble AJ son tous égaux à une même valeur rj, mais qu'il existe au moins deux indices i et j (j étant donc également compris entre 1 et T) tels que rj diffère de r .

Par ailleurs, le fait de considérer une détermination de l'estimateur GJJNION au moyen de ladite fonction g ¹ ne constitue qu'une variante particulière de mise en œuvre du cinquième procédé. Cette variante se révèle particulièrement avantageuse pour fournir une estimation très précise du nombre de données distinctes présentes dans l'union des d'ensembles de données A_l, A_2,..., A_T. L'invention couvre néanmoins d'autres modes de mise en œuvre du cinquième procédé, comme par exemple un mode dans lequel l'estimateur GJJNION est déterminé égal à Q_UNION.

La figure 8 représente, sous forme d'ordinogramme, les principales étapes d'un autre procédé de comptage selon l'invention, dit « sixième procédé ». Les instructions dédiées à l'exécution des étapes du sixième procédé sont contenues dans le programme PROG_6. Ledit sixième procédé consiste à estimer le nombre de données distinctes présentes dans l'intersection d'une pluralité d'ensembles de données A_l, A_2,..., A_T, T étant un nombre entier strictement supérieur à 1 (un ensemble de donnée AJ, i étant un indice entier compris entre 1 et T, correspondant par exemple à l'ensemble A considéré pour le quatrième procédé).

A titre purement illustratif, en reprenant le contexte applicatif selon lequel une donnée personnelle relative à un individu correspond à un numéro de téléphone dudit individu mémorisé après que celui- ci ait passé ou reçu un appel dans une gare donnée et au cours d'une période de temps donnée, ledit sixième procédé permet avantageusement d'estimer le nombre de personnes ayant voyagé entre deux gares au cours d'une période de temps donnée. Plus particulièrement, si on considère un ensemble A_1 (respectivement A_2) comportant tous les numéros (éventuellement avec répétitions) des individus ayant passé et/ou reçu des appels téléphoniques dans une première gare (respectivement dans une deuxième gare), ledit sixième procédé permet d'estimer le nombre d'éléments distincts compris dans l'intersection de A_1 et A_2.

Ledit sixième procédé comporte dans un premier temps une étape M10 d'obtention, pour chaque ensemble de données AJ, d'une structure de données LJ déterminée selon l'un quelconque desdits premier, deuxième et troisième procédé, le cardinal de ladite structure LJ étant égal à un nombre kj (on note que les valeurs k_l, ..., k_T peuvent être, en tout ou partie, distinctes entre elles).

La mise en œuvre de ladite étape M10 est similaire à celle de l'étape H 10 ou bien encore J 10.

Le sixième procédé comporte également une étape M20 de sélection d'un nombre D7 de plus petites valeurs d'une structure dite « structure d'union » L_UNION correspondant à l'union des structures de données L_l, LJ’,..., L_T. ledit nombre D7 est égal à la plus petite valeur parmi les cardinaux respectifs desdites structures de données L_l, LJ’,..., L_T (i.e. D7 = min(k_l,..., k_T)).

Le sixième procédé comporte également une étape M30 de détermination d'une valeur QJJNION égale au quotient de D7-1 par la plus grande valeur parmi lesdites D7 plus petites valeurs sélectionnées.

Le sixième procédé comporte également une étape M40 de détermination d'une valeur QJNTER égale au quotient du cardinal d'une structure dite « structure d'intersection » LJNTER correspondant à l'intersection desdites structures de données L_l, LJ’,..., L_T par D7.

Le sixième procédé comporte également une étape M50 de détermination d'un estimateur GJNTER du nombre de données distinctes de ladite intersection d'ensembles de données en fonction de QJNTER et de Q_UNION.

En définitive, on obtient donc un estimateur GJNTER à partir d'une structure de données LJNTER qui est plus compacte que l'intersection des ensembles de données AJ, AJ’,..., A_T, et qui garantit en outre une confidentialité différentielle d'ordre E.

Dans un mode particulier de mise en œuvre, l'estimateur GJNTER a pour expression : QJNTER x QJJNION

GJNTER = nf ₌₁ (l - (1 - p) ^r 0

Les paramètres r_l, r_2, r_T correspondent à des nombres respectivement associés aux ensembles de données A_l, A_2, A_T. Chaque paramètre rj considéré dans l'expression de G_INTER peut prendre différentes valeurs en fonction d'hypothèses faites sur le contexte applicatif envisagé pour ledit sixième procédé.

Ainsi, on peut par exemple considérer une hypothèse selon laquelle, pour chaque ensemble AJ, les nombres d'occurrences respectifs des données dudit ensemble AJ sont tous égaux à une même valeur RJ donnée. Dans ce cas, le paramètre rj associé à l'ensemble AJ est égal à RJ.

Selon un autre exemple, on considère une hypothèse selon laquelle au moins un ensemble de données (parmi les ensembles de données A_l,..., A_T) comporte plusieurs données dont les nombres d'occurrences respectifs dans ledit au moins un ensemble diffèrent entre eux. Dans ce cas, le paramètre rj de chaque ensemble AJ est égal à la partie entière du quotient de NJ par une valeur QJ, ladite valeur QJ étant égale au quotient de kj-l par la plus grande valeur de la structure de données LJ obtenue pour ledit ensemble AJ. On note donc que pour mettre en œuvre le sixième procédé dans le présent exemple, il importe que chaque structure de données LJ soit déterminée au moyen d'un mode de mise en œuvre du premier ou troisième procédé permettant d'obtenir une valeur de dénombrement NJ associée à ladite structure LJ.

Il importe de noter que le fait de considérer une valeur de rj égale à la partie entière du quotient de NJ par QJ n'est pas limité à la seule hypothèse considérée dans l'exemple précédent. Ainsi, des dispositions identiques peuvent également s'appliquer lorsque les nombres d'occurrences respectifs des données d'un ensemble AJ sont tous égaux à une même valeur, sans pour autant que la valeur commune soit connue.

Par ailleurs, le fait de considérer une détermination de l'estimateur G_INTER selon ledit mode particulier ne constitue qu'une variante d'implémentation du sixième procédé. Cette variante se révèle particulièrement avantageuse pour fournir une estimation très précise du nombre de données distinctes présentes dans l'intersection des d'ensembles de données A_l, A_2,..., A_T. L'invention couvre néanmoins d'autres modes de mise en œuvre du sixième procédé, comme par exemple un mode dans lequel l'estimateur G_INTER est déterminé égal à au produit entre Q_INTER et QJJNION.

Les différents procédés selon l'invention ont été décrits jusqu'à présent en relation avec un contexte applicatif dans lequel une donnée personnelle relative à un individu correspond à un numéro de téléphone dudit individu mémorisé après que celui-ci ait passé ou reçu un appel dans une gare donnée et au cours d'une période de temps donnée. Néanmoins, l'invention ne se limite à un tel contexte applicatif, et peut être mise en œuvre, en définitive, dans tout contexte dans lequel il est utile de pouvoir estimer précisément, rapidement et de manière anonymisée, le nombre de données distinctes dans un ensemble de données, dans une union d'ensembles de données ou bien encore dans une intersection d'ensembles de données. Ainsi, et de manière plus générale, l'invention trouve une application particulièrement avantageuse dans l'analyse statistique de la fréquentation d'une ou plusieurs zones géographiques, de sorte à permettre, par exemple, de dimensionner des infrastructures en fonction de flux d'individus, d'identifier des emplacements d'intérêt en fonction de profils d'individus, etc.

En outre, l'invention ne se limite pas non plus à la mémorisation de données correspondant à des numéros de téléphones mobiles. L'invention peut par exemple s'appliquer à la mémorisation de données correspondant à des informations de connexion auprès d'un serveur informatique, comme par exemple un serveur Internet de sorte à pouvoir réaliser des analyses statistiques d'un trafic réseau.