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

Résumé des données : Minhashing et Locality-Sensitive Hashing

Dans cours

CS-422: Database systems

This course is intended for students who want to understand modern large-scale data analysis systems and database systems. It covers a wide range of topics and technologies, and will prepare students to be able to build such systems as well as read and und ...

Description

Cette séance de cours couvre les concepts de similarité Jaccard, de minhashing et de hachage sensible à la localité pour la synthèse des données. Il explique comment trouver des éléments similaires en utilisant la similarité Jaccard et les vecteurs de bits, et comment réduire les faux positifs et les négatifs dans la détection de similarité. La séance de cours se penche également sur la construction des fonctions de hachage et l'application de la distance cosinus pour la similarité des documents.

Cette vidéo est disponible exclusivement sur Mediaspace pour un public restreint. Veuillez vous connecter à Mediaspace pour y accéder si vous disposez des autorisations nécessaires.

Regarder sur Mediaspace

Enseignant·e

Anastasia Ailamaki

Source officielle

Concepts associés (27)

False positives and false negatives

A false positive is an error in binary classification in which a test result incorrectly indicates the presence of a condition (such as a disease when the disease is not present), while a false negative is the opposite error, where the test result incorrectly indicates the absence of a condition when it is actually present. These are the two kinds of errors in a binary test, in contrast to the two kinds of correct result (a and a ).

Indice et distance de Jaccard

L'indice et la distance de Jaccard sont deux métriques utilisées en statistiques pour comparer la similarité et la entre des échantillons. Elles sont nommées d'après le botaniste suisse Paul Jaccard. L'indice de Jaccard (ou coefficient de Jaccard, appelé « coefficient de communauté » dans la publication d'origine) est le rapport entre le cardinal (la taille) de l'intersection des ensembles considérés et le cardinal de l'union des ensembles. Il permet d'évaluer la similarité entre les ensembles.

Similarity measure

In statistics and related fields, a similarity measure or similarity function or similarity metric is a real-valued function that quantifies the similarity between two objects. Although no single definition of a similarity exists, usually such measures are in some sense the inverse of distance metrics: they take on large values for similar objects and either zero or a negative value for very dissimilar objects. Though, in more broad terms, a similarity function may also satisfy metric axioms.

False positive rate

In statistics, when performing multiple comparisons, a false positive ratio (also known as fall-out or false alarm ratio) is the probability of falsely rejecting the null hypothesis for a particular test. The false positive rate is calculated as the ratio between the number of negative events wrongly categorized as positive (false positives) and the total number of actual negative events (regardless of classification). The false positive rate (or "false alarm rate") usually refers to the expectancy of the false positive ratio.

Fonction de hachage parfait

droite|vignette|240x240px| Une fonction de hachage parfait pour les quatre noms John Smith, Lisa Smith, Sam Doe et Sandra Dee. droite|vignette|240x240px| Une fonction de hachage parfait minimal pour les quatre noms John Smith, Lisa Smith, Sam Doe et Sandra Dee. En informatique, une fonction de hachage parfait h pour un ensemble S est une fonction de hachage qui associe des éléments distincts de S à un ensemble de m entiers, sans collisions. En termes mathématiques, c'est une fonction injective.

Afficher plus

Séances de cours associées (33)

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.

Mise en œuvre des ensembles (II)

Couvre la mise en œuvre des ensembles en utilisant une approche naïve et discute des inefficacités de la classe S liste 7.

Fonctions de hachage cryptographiques et chaînes de blocs

Couvre les fonctions de hachage cryptographiques, les codes d'authentification des messages et les chaînes de blocs, y compris les bitcoins, la preuve de travail et les variantes MAC.

Mise en œuvre des ensembles : Hashing

Couvre la mise en œuvre des ensembles à l'aide du hachage et des opérations d'ensemble.

Hashing: Bases et applications

Explore les fondamentaux du hachage, les applications en matière de sécurité et les attaques communes contre les fonctions de hachage.

Afficher plus

Concepts associés (27)

False positives and false negatives

Indice et distance de Jaccard

Similarity measure

False positive rate

Fonction de hachage parfait

Afficher plus