Lecture

Data Summarization: Minhashing and Locality-Sensitive Hashing

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

In course

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

This lecture covers the concepts of Jaccard similarity, minhashing, and locality-sensitive hashing for data summarization. It explains how to find similar items using Jaccard similarity and bitvectors, and how to reduce false positives and negatives in similarity detection. The lecture also delves into the construction of hash functions and the application of cosine distance for document similarity.

Instructor

Anastasia Ailamaki

Expertise Database management systems, scientific applications, computer architecture Teaching & PhD PhD Students Hamish Nicholson, Anna Herlihy, Yi Jiang, Eleni Zapridou, Georgiy Konstantinovich Lebedev, Ioanna Tsakalidou Past EPFL PhD Students Farhan Tauheed, Radu Ioan Stoica, Manos Athanassoulis, Pinar Tözün, Adrian Daniel Popescu, Ioannis Alagiannis, Renata Borovica-Gajic, Danica Porobic, Iraklis Psaroudakis, Manos Karpathiotakis, Matthaios Alexandros Olma, Mirjana Pavlovic, Eleni Tzirita Zacharatou,

Official source

Related concepts (30)

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 ).

Positive and negative predictive values

The positive and negative predictive values (PPV and NPV respectively) are the proportions of positive and negative results in statistics and diagnostic tests that are true positive and true negative results, respectively. The PPV and NPV describe the performance of a diagnostic test or other statistical measure. A high result can be interpreted as indicating the accuracy of such a statistic. The PPV and NPV are not intrinsic to the test (as true positive rate and true negative rate are); they depend also on the prevalence.

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.

Perfect hash function

In computer science, a perfect hash function h for a set S is a hash function that maps distinct elements in S to a set of m integers, with no collisions. In mathematical terms, it is an injective function. Perfect hash functions may be used to implement a lookup table with constant worst-case access time. A perfect hash function can, as any hash function, be used to implement hash tables, with the advantage that no collision resolution has to be implemented.

Related lectures (43)

Dictionary Operations

Covers operations and methods related to dictionaries in Python, including creating, updating, and handling key errors.

Hashing and Sorting Techniques in Database Systems

Provides an overview of hashing and sorting techniques in database management systems, focusing on their implementation and performance optimization.

Performance Evaluation: Bootstrap and Performance Metrics

Explores machine learning model evaluation using leave-one-out, bootstrap, and performance metrics like recall and precision.

Probabilistic Analysis: Hiring & Birthday Paradox

Explores probabilistic analysis in algorithms, covering the hiring problem and the birthday paradox, along with hash tables and functions.

Two-Phase Construction: Arrays & Hash Tables