UDTR Global Radar

UDTR Global Rights of Nature Radar

Documentary registry of records detected across the scholarly, legal and institutional infrastructures monitored by UDTR.

A global documentary infrastructure designed to achieve the broadest verifiable and scientifically defensible coverage of the Rights of Nature.

← Back to Radar

Learning equivalence hash functions

Identification

Public canonical key
radar:r-4862bdaa90209488b8a849264e1386f5
Authors
Duchesneau, Mathieu
Reported year
2025
Reported language
en
Source type
Dissertation
First detected
2026-11-13T08:39:50.562691+00:00
Last metadata observation
2026-11-13T08:39:50.562691+00:00
Last HTTP verification
Not checked

Documentary abstract — original language

Imaginez héberger une plateforme où les utilisateurs partagent du contenu original, tel que des images, de la musique ou des vidéos. Pour garantir l’intégrité, vous avez besoin d’un algorithme capable de détecter la réinsertion de contenu existant. Cependant, étant donné l’échelle massive des ajouts quotidiens, comparer directement chaque nouvelle publication avec des milliards d’éléments existants est impossible en pratique. Pour les réinsertions exactes, les tables de hachage sont la solution la plus efficace, permettant une détection des doublons en temps constant. Cependant, si la plateforme doit également repérer des réinsertions avec des modifications légères, cette solution ne fonctionne pas. Même une modification minime, comme l’altération d’un seul pixel, entraînera une valeur de hachage différente, associant ainsi le contenu original et modifié à des adresses distinctes dans la table, ce qui empêchera la plateforme de détecter le contenu altéré. De plus, un utilisateur malveillant pourrait effectuer des transformations plus complexes, telles que l’ajustement de la teinte, de la luminosité et de la saturation, ou introduire de légères distorsions ou rotations à l’image. Les approches actuelles pour traiter ce type de problème proviennent de la littérature sur les algorithmes de plus proches voisins approximatifs, où les techniques les plus prometteuses sont basées sur des arbres et des graphes. Cependant, bien qu’efficaces, ces techniques ne peuvent égaler l’efficience d’une simple consultation de table de hachage. Au cœur de ce travail, cette thèse introduit et explore les fonctions d'équihachage, une variante des fonctions de hachage conçue pour associer des instances «équivalentes» à la même empreinte (une chaîne binaire de longueur fixe). Dans notre exemple, une fonction d'équihachage appropriée attribuerait la même empreinte à la fois au contenu original et au contenu modifié, permettant une détection efficace des variations tout en conservant la simplicité et la rapidité de la table de hachage. Les fonctions d'équihachage étendent l'applicabilité de nombreux algorithmes basés sur le hachage. Dans notre exemple, elles élargissent le champ d’application de la recherche dans la table de hachage. Au-delà de cela, elles peuvent également étendre l'applicabilité des algorithmes basés sur les ensembles. Par exemple, étant donné une fonction d'équihachage qui associe tous les portraits d'une même personne à la même empreinte et une collection de portraits, on pourrait déterminer en temps constant si une personne figure dans la collection ou bien compter le nombre d'individus distincts dans celle-ci en temps linéaire. La plupart des exemples les plus intéressants nécessitent l'apprentissage profond pour entraîner la fonction d'équihachage appropriée. Idéalement, ces fonctions produiraient des empreintes identiques pour des instances équivalentes et des empreintes distinctes pour des instances non équivalentes. Cependant, les fonctions d'équihachage apprises ne sont pas idéales, et une partie importante de cette thèse traite des défis liés à leur entaînement, leur évaluation et l'amélioration de leurs performances. Deux métriques clés sont le taux de collision pertinente (Relevant-Collision Rate (RCR)), qui mesure la probabilité que des instances équivalentes partagent la même empreinte, et le taux de collision non pertinente (Irrelevant-Collision Rate (ICR)), qui mesure la probabilité que des instances non équivalentes partagent la même empreinte. Lorsqu'il s'agit de bases de données massives, l’ICR doit être exceptionnellement bas. Sinon, de nombreuses instances non équivalentes partageront la même empreinte, créant toutes sortes de problèmes. Atteindre un ICR faible présente deux défis: estimer avec précision un taux de collision aussi bas et entraîner efficacement des modèles capables de respecter ce critère strict. Pour répondre au premier défi, nous proposons l’intervalle de confiance de Chebyshev, qui tire parti du paradoxe des anniversaires pour estimer efficacement l’ICR. Pour le second défi, nous introduisons l'hypothèse de «challenge-starvation». Cette hypothèse identifie une limitation potentielle dans toutes les approches d'apprentissage contrastif existantes qui pourrait nuire à leur capacité d'obtenir un ICR bas. Pour contourner ce problème, nous présentons la fonction de perte de Shannon-Hamming, une stratégie d'entraînement novatrice qui se concentre exclusivement sur les signaux positifs. Notre fonction de perte améliore l'ICR d'un ordre de grandeur par rapport à ses prédécesseurs contrastifs. De plus, une fonction d'équihachage apprise devrait idéalement présenter un RCR élevé. Cependant, étant donné que la descente de gradient est incompatible avec la nature discrète de l'empreinte et que nous devons équilibrer le RCR avec un ICR exceptionnellement bas, les modèles attribueront parfois des empreintes distinctes à des instances équivalentes. Pour pallier cela, nous proposons l'algorithme de sondage multiple priorisé (prioritized multi-probing) qui exploite l'incertitude du modèle pour générer plusieurs empreintes pour chaque instance. Cette technique peut être utilisée pour améliorer le taux de détection des réinsertions de contenues modifiés dans notre exemple précédent. Nos expériences avec une base de données d'un milliard d'images démontrent la viabilité et le potentiel de notre projet de recherche.

Identifiers

DOI
10.71781/11085
URI
https://hdl.handle.net/1866/40944

Documentary context

Documentary family
Thesis
Source-reported types
Dissertation
Publishers
Université de Montréal

Entity mentions are not evidence of legal recognition. Jurisdiction studied is separate from author affiliation country.

Sources

DataCite · Record 1

Cite this reference

Duchesneau, Mathieu. Learning equivalence hash functions. 2025. https://doi.org/10.71781/11085

JSON · CSL-JSON · BibTeX · RIS · CSV · JSON-LD ·

APA, Chicago, ISO 690: bibliographic formats using available fields. OSCOLA / Bluebook: structured data only; full legal citation compliance is not claimed without verification of required elements.

APA
Duchesneau, Mathieu. (2025). Learning equivalence hash functions. https://doi.org/10.71781/11085
Chicago
Duchesneau, Mathieu. Learning equivalence hash functions. 2025. https://doi.org/10.71781/11085
ISO 690
Duchesneau, Mathieu. Learning equivalence hash functions. 2025. https://doi.org/10.71781/11085

Warning: Undefined array key "last_link_verified" in /home/clients/e27d81e12f04d2bfd747aa264540ac56/sites/_UDTR_APP/legal_library_reference.php on line 31

UDTR Global Rights of Nature Legal Library. Learning equivalence hash functions. Documentary record: https://www.declarationuniverselledesdroitsdelarbre.org/global-rights-of-nature-radar/reference/r-4862bdaa90209488b8a849264e1386f5/ · Last HTTP verification: not performed

Report a correction

Frozen-version metadata

Research dossiers and documentary relations

Source roles

Bibliographic / original publication source · https://umontreal.scholaris.ca/handle/1866/40944

An authority link alone does not verify a legal claim. Abstracts and full texts remain subject to their source terms.

Documentary status

Relevance pending

Library

This identity is not yet included in the Legal Library.

UDTR Global Rights of Nature Legal Library