Как Google использует MinHash и кластеризацию для определения и каноникализации дубликатов вакансий в Google Jobs

Термины и определения

Binning Factors (Факторы группировки)

Структурированные характеристики вакансии (например, Название, Локация, Работодатель), используемые на первом этапе для быстрого отбора потенциально похожих кластеров (кандидатов).

Characteristics (Характеристики)

Атрибуты объявления: Job ID, Title, Location, Description, Salary, Employment Type, Associated Entity.

Hash Function (Хэш-функция)

Алгоритм (например, MD5 упоминается в патенте), преобразующий шингл в числовое значение фиксированной длины (message digest или hash value).

Job Posting Cluster (Кластер объявлений о вакансиях)

Группа объявлений, идентифицированных как дубликаты друг друга. Имеет идентификатор (Cluster ID).

Master Job Posting (Главное объявление о вакансии)

Одно объявление внутри кластера, выбранное как репрезентативное (каноническое). Используется для сравнения с новыми вакансиями и отображается в результатах поиска.

MinHash (Мин-хэш / Цифровой отпечаток / Fingerprint)

Компактное представление текста вакансии, состоящее из набора минимальных хэш-значений, полученных после применения правил пермутации. Используется для быстрой оценки схожести.

Permutation Rules (Правила пермутации)

Набор правил для перемешивания хэш-значений при генерации MinHash. В патенте упоминается использование операции XOR (исключающее ИЛИ).

Shingle (Шингл / N-gram)

Подстрока документа, представляющая собой последовательность из N токенов (например, фраза из 4 последовательных слов). Базовый элемент для анализа схожести текста.

Similarity Index (Индекс схожести)

Числовая метрика схожести двух вакансий. В патенте используется коэффициент Жаккара (Jaccard similarity coefficient), рассчитанный на основе сравнения MinHash отпечатков.

Similarity Threshold (Порог схожести)

Предопределенное значение (например, 0.9, 0.95), при превышении которого две вакансии считаются дубликатами.

Ключевые утверждения (Анализ Claims)

Claim 1 (Независимый пункт): Описывает базовый метод дедупликации.

1. Система получает данные о новом объявлении (с характеристиками).
2. Система обращается к данным существующего Job Posting Cluster.
3. В кластере есть Master Job Posting, являющееся репрезентативным.
4. Система определяет, является ли новое объявление дубликатом, сравнивая его с Master Job Posting.
5. Система сохраняет новое объявление, связывая его с существующим или новым кластером.

Ядром изобретения является использование Master Job Posting как единственной точки сравнения для всего кластера, что повышает эффективность процесса дедупликации.

Claim 5 (Зависимый от 1): Детализирует процесс определения дубликатов (Шаг 4 из Claim 1), описывая реализацию MinHash.

1. Конвертация данных в набор элементов (шинглов).
2. Применение permutation rules к этим элементам для создания набора пермутаций (генерация MinHash).
3. Определение Similarity Index на основе этих пермутаций.
4. Сравнение Similarity Index с порогом (Similarity Threshold).

Claim 6 (Зависимый от 1): Дополнительно детализирует процесс конвертации.

Включает генерацию элементов данных (шинглов) и применение hash function к каждому элементу.

Claim 9 (Независимый пункт): Описывает систему и добавляет этап предварительного отбора (Binning).

1. Получение нового объявления.
2. Доступ к множеству кластеров.
3. Идентификация кластеров-кандидатов на основе характеристик нового объявления (этап фильтрации/Binning).
4. Определение дублирования путем сравнения с Master Job Posting кластера-кандидата.

Этот пункт защищает двухэтапный процесс: быстрый отбор кандидатов (Binning) и последующее детальное сравнение (MinHash).

Где и как применяется

Изобретение применяется на этапе обработки и структурирования входящих данных в вертикальном поиске (например, Google Jobs).

CRAWLING – Сканирование и Сбор данных
Система получает сырые данные о вакансиях через краулинг веб-страниц (с микроразметкой JobPosting) или через прямые API/фиды.

INDEXING – Индексирование и извлечение признаков
Это основной этап применения патента. В процессе индексации данных для вертикального индекса происходит:

1. Извлечение признаков: Парсинг сырых данных и извлечение Characteristics (Title, Location, Description и т.д.).
2. Дедупликация: Выполнение алгоритма сравнения (Binning и MinHashing).
3. Кластеризация и Каноникализация: Присвоение Cluster ID и выбор/обновление Master Job Posting.

RANKING / RERANKING
На этапах ранжирования система использует результаты дедупликации. Ранжируется только Master Job Posting как представитель всего кластера, что улучшает качество и чистоту выдачи.

Входные данные:

• Сырые данные нового объявления о вакансии.
• База данных существующих кластеров и их Master Job Postings (включая их MinHash отпечатки).
• Набор предопределенных Permutation Rules и Similarity Threshold.

Выходные данные:

• Обработанное объявление с присвоенным Cluster ID (существующим или новым).
• Обновленный статус Master Job Posting (если произошла замена).

На что влияет

• Конкретные типы контента: Влияет на обработку объявлений о вакансиях (Job Postings). Технология также применима к другим вертикалям с синдицированным контентом (Товары, Недвижимость).
• Конкретные ниши или тематики: Индустрия онлайн-рекрутинга, агрегаторы вакансий, карьерные разделы сайтов компаний.

Когда применяется

• Условия применения: Алгоритм применяется каждый раз, когда система получает новое или обновленное объявление о вакансии.
• Триггеры активации: Запускается конвейером приема данных (data ingestion pipeline). Детальный анализ (MinHash) активируется только при наличии кластеров-кандидатов после этапа Binning.
• Асинхронные процессы: Патент также упоминает асинхронный процесс проверки истечения срока действия вакансий (Posting Expiration) и удаления их из кластеров.

Пошаговый алгоритм

Процесс дедупликации объявления о вакансии:

1. Получение и парсинг: Система получает новое объявление и извлекает его характеристики (Characteristics).
2. Идентификация кандидатов (Binning): Система использует Binning Factors (например, Title, Location, Employer) для быстрого поиска существующих кластеров, чьи Master Job Postings имеют совпадающие значения. Формируется список кластеров-кандидатов.
3. Конвертация в шинглы (Shingling): Текстовый контент (например, Description) нового объявления преобразуется в набор шинглов (Shingles). В патенте упоминается использование 4 последовательных токенов (4-grams). Пунктуация удаляется.
4. Хэширование: К каждому шинглу применяется хэш-функция (например, MD5) для генерации хэш-значений.
5. Генерация отпечатка (MinHashing):
   1. К набору хэш-значений применяется множество предопределенных Permutation Rules (например, с помощью операции XOR).
   2. Для каждой пермутации определяется минимальное хэш-значение.
   3. Набор этих минимальных значений формирует цифровой отпечаток (Fingerprint) вакансии.
6. Расчет схожести: Система сравнивает отпечаток новой вакансии с отпечатками Master Job Postings из списка кандидатов. Рассчитывается Similarity Index (коэффициент Жаккара) как доля совпадающих минимальных хэш-значений.
7. Проверка порога: Similarity Index сравнивается с Similarity Threshold (например, 0.9).
8. Принятие решения и кластеризация:
   1. Если порог превышен: Вакансия признается дубликатом и добавляется в соответствующий кластер. Система оценивает, должна ли новая вакансия заменить текущий Master Job Posting (например, если она из более авторитетного источника или более свежая).
   2. Если порог не превышен ни с одним кандидатом: Вакансия признается уникальной. Создается новый кластер, и эта вакансия назначается его Master Job Posting.

Какие данные и как использует

Данные на входе

Система использует комбинацию структурированных и неструктурированных данных, используя разные поля на разных этапах.

Для этапа Binning (Фильтрация кандидатов):

• Структурные и Географические факторы (Binning Factors):
  • Job Title (Название).
  • Job Location (Локация).
  • Associated Entity (Работодатель).
  • Employment Type (Тип занятости), Salary (Зарплата), Shift/Schedule (График) – используются для более точного отбора.

Для этапа MinHashing (Расчет схожести):

• Контентные факторы:
  • Job Description (Описание): Основной текст для генерации отпечатка.

Для выбора Master Job Posting:

• Технические факторы (Метаданные):
  • Источник данных (Source): Сайт работодателя может иметь приоритет перед агентством.
  • Время получения/обновления данных.

Какие метрики используются и как они считаются

• Шинглы (Shingles / N-grams): Последовательности токенов. В патенте упоминается пример использования 4 последовательных токенов.
• Хэш-значения: Результат применения хэш-функции (например, MD5) к шинглам.
• MinHash Fingerprint: Набор из N минимальных хэш-значений, полученных после применения N правил пермутации (например, XOR).
• Индекс схожести (Similarity Index): Рассчитывается как коэффициент Жаккара между двумя MinHash отпечатками.