Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Séance de cours

Hashing sensible à la localité

Dans cours

CS-450: Algorithms II

A first graduate course in algorithms, this course assumes minimal background, but moves rapidly. The objective is to learn the main techniques of algorithm analysis and design, while building a repertory of basic algorithmic solutions to problems in many ...

Description

Cette séance de cours couvre le concept de Locality Sensitive Hashing (LSH) pour la recherche du plus proche voisin, en discutant de la sous-modularité et de la probabilité de collision dans les fonctions de hachage. L'instructeur explique les étapes de prétraitement, la sélection des fonctions de hachage et la minimisation des fonctions définies. La séance de cours explore également les propriétés des fonctions d'ensemble sous-modulaire et leurs applications dans la minimisation des fonctions d'ensemble au sol.

Enseignant·e·s (3)

Alessandro Chiesa

Alessandro Chiesa is a faculty member in computer science. He conducts research in complexity theory, cryptography, and security, with a focus on the theoretical foundations and practical implementations of cryptographic proofs that are short and easy to verify. He is a co-author of several zkSNARK libraries, and is a co-inventor of the Zerocash protocol. He has co-founded Zcash and StarkWare Industries. He is a recipient of a Sloan Research Fellowship (2021), an Okawa Foundation Research Grant (2020), and Google Faculty Research Awards (2018 and 2017). He was included in MIT Technology Review's "35 Innovators Under 35" list in 2018.

Mikhail Kapralov

Ola Nils Anders Svensson

Source officielle

Concepts associés (32)

Fonction sous-modulaire

En optimisation combinatoire, les fonctions sous-modulaires sont des fonctions d'ensemble particulières. Soient E un ensemble et f une fonction qui à tout sous-ensemble X de E associe un réel f(X), on dit que f est sous-modulaire si l'inégalité suivante est vérifiée pour tout sous-ensemble X et Y de E Les fonctions sous-modulaire peuvent être vues comme l'analogue discret des fonctions convexes.

Recherche des plus proches voisins

La recherche des plus proches voisins, ou des k plus proches voisins, est un problème algorithmique classique. De façon informelle le problème consiste, étant donné un point à trouver, dans un ensemble d'autres points, quels sont les k plus proches. La recherche de voisinage est utilisée dans de nombreux domaines, tels la reconnaissance de formes, le clustering, l'approximation de fonctions, la prédiction de séries temporelles et même les algorithmes de compression (recherche d'un groupe de données le plus proche possible du groupe de données à compresser pour minimiser l'apport d'information).

Collision (informatique)

vignette|Schéma d'une collision entre deux résultats d'une fonction de hachage En informatique, une collision désigne une situation dans laquelle deux données ont un résultat identique avec la même fonction de hachage. Les collisions sont inévitables dès lors que l'ensemble de départ (données fournies) de la fonction de hachage est d'un cardinal strictement supérieur à l'ensemble d'arrivée (empreintes). Ce problème est une déclinaison du principe des tiroirs. La conséquence de ces collisions dépend de leurs applications.

Fonction de hachage

Quand il s'agit de mettre dans un tableau de taille raisonnable (typiquement résidant dans la mémoire principale de l'ordinateur) un ensemble de données de taille variable et arbitraire, on utilise une fonction de hachage pour attribuer à ces données des indices de ce tableau. Par conséquent, une fonction de hachage est une fonction qui associe des valeurs de taille fixe à des données de taille quelconque. Les valeurs renvoyées par une fonction de hachage sont appelées valeurs de hachage, codes de hachage, résumés, signatures ou simplement hachages.

Méthode des k plus proches voisins

En intelligence artificielle, plus précisément en apprentissage automatique, la méthode des k plus proches voisins est une méthode d’apprentissage supervisé. En abrégé KPPV ou k-PPV en français, ou plus fréquemment k-NN ou KNN, de l'anglais k-nearest neighbors. Dans ce cadre, on dispose d’une base de données d'apprentissage constituée de N couples « entrée-sortie ». Pour estimer la sortie associée à une nouvelle entrée x, la méthode des k plus proches voisins consiste à prendre en compte (de façon identique) les k échantillons d'apprentissage dont l’entrée est la plus proche de la nouvelle entrée x, selon une distance à définir.

Afficher plus

Séances de cours associées (33)

Recherche du voisin le plus proche: Johnson-Lindenstrauss Lemma

Couvre l'algorithme de recherche le plus proche du voisin et le lemme de Johnson-Lindenstrauss pour la réduction de la dimensionnalité, en explorant les techniques de prétraitement et le hachage sensible à la localité.

Indépendance par paire: hachage et équilibrage de charge

Explore l'indépendance par paire dans le hachage pour éviter les collisions et atteindre l'équilibrage de charge.

Analyse probabiliste: Paradoxe de l'embauche et de l'anniversaire

Explore l'analyse probabiliste dans les algorithmes, couvrant le problème de l'embauche et le paradoxe de l'anniversaire, ainsi que les tables de hachage et les fonctions.

Ingénierie des systèmes décentralisés: DHT de corbeille

Couvre le Chord DHT en ingénierie décentralisée des systèmes, en mettant l'accent sur la fiabilité, la redondance et l'entretien des structures.

Analyse des tables de hachage

Couvre l'analyse des tables de hachage, y compris les opérations de recherche et les collisions attendues.

Afficher plus

Concepts associés (32)

Fonction sous-modulaire

Recherche des plus proches voisins

Collision (informatique)

Fonction de hachage

Méthode des k plus proches voisins

Afficher plus