📄Работа №143026
Тема: Реализация алгоритма поиска UCC в рамках платформы Desbordante
Характеристики работы
Тип работы
Дипломные работы, ВКР
Предмет
Математика
Объем:
34 листов
Год:
2023
Просмотров:
144
4600
руб.
🛒 Купить работу
Не подходит эта работа?
Закажите новую по вашим требованиям
Узнать цену на написание
Закажите новую по вашим требованиям
Представленный материал является образцом учебного исследования, примером структуры и содержания учебного исследования по заявленной теме. Размещён исключительно в информационных и ознакомительных целях.
Workspay.ru оказывает информационные услуги по сбору, обработке и структурированию материалов в соответствии с требованиями заказчика.
Размещение материала не означает публикацию произведения впервые и не предполагает передачу исключительных авторских прав третьим лицам.
Материал не предназначен для дословной сдачи в образовательные организации и требует самостоятельной переработки с соблюдением законодательства Российской Федерации об авторском праве и принципов академической добросовестности.
Авторские права на исходные материалы принадлежат их законным правообладателям. В случае возникновения вопросов, связанных с размещённым материалом, просим направить обращение через форму обратной связи.
Настоящий учебно-методический информационный материал размещён в ознакомительных и исследовательских целях и представляет собой пример учебного исследования. Не является готовым научным трудом и требует самостоятельной переработки.
📋 Содержание
Введение 4
1. Постановка задачи 6
2. Обзор 7
2.1. Поиск UCC 7
2.2. Алгоритм HyUCC 10
2.3. Платформа Desbordante 13
3. Реализация 16
3.1. Обычная версия HyUCC 16
3.2. Модифицированная версия HyUCC 20
4. Эксперименты 22
4.1. Методология 22
4.2. Экспериментальное исследование реализаций 24
Заключение 29
Список литературы 30
1. Постановка задачи 6
2. Обзор 7
2.1. Поиск UCC 7
2.2. Алгоритм HyUCC 10
2.3. Платформа Desbordante 13
3. Реализация 16
3.1. Обычная версия HyUCC 16
3.2. Модифицированная версия HyUCC 20
4. Эксперименты 22
4.1. Методология 22
4.2. Экспериментальное исследование реализаций 24
Заключение 29
Список литературы 30
📖 Аннотация
Работа посвящена реализации и оптимизации алгоритма автоматического поиска уникальных комбинаций колонок в рамках платформы наукоёмкого профилирования данных Desbordante. Актуальность задачи обусловлена необходимостью автоматического обнаружения таких закономерностей в табличных данных для решения прикладных проблем, включая интеграцию и сопоставление схем, когда метаданные об уникальности атрибутов изначально отсутствуют. В ходе исследования выполнен обзор существующих алгоритмов, на основе которого для реализации был выбран эффективный алгоритм HyUCC. Методология включала анализ родственного алгоритма поиска функциональных зависимостей HyFD для переиспользования кода, непосредственную интеграцию HyUCC в кодобазу платформы на C++ с созданием универсальных интерфейсов и модуля тестирования, а также последующую оптимизацию производительности через профилирование и внедрение многопоточности. В результате была разработана как обычная, так и модифицированная параллельная версия алгоритма. Экспериментальная оценка на синтетических и реальных наборах данных показала, что обычная реализация в Desbordante в среднем в 21 раз эффективнее аналога в платформе Metanome, а оптимизированная многопоточная версия превосходит обычную в 2.5 раза и потребляет в десять раз меньше памяти, чем параллельная реализация в Metanome. Практическая значимость работы заключается в существенном расширении функциональности открытой платформы Desbordante высокопроизводительным алгоритмом поиска UCC, что позволяет исследователям и инженерам данных эффективнее решать задачи анализа качества и структуры данных. Разработанный код открыт и интегрирован в публичный репозиторий проекта.
📖 Введение
Профилирование данных — это процесс анализа данных, направленный на извлечение метаданных [1]. Его можно разделить на два типа: ненаукоёмкое и наукоёмкое [8]. Профилирование первого типа включает в себя поиск таких метаданных как, например, время создания данных и их авторство. Второй тип направлен на выявление такой гораздо более содержательной информации, как закономерности в данных. Анализируемые данные можно классифицировать на основе логической модели данных, к которой они относятся: графовые, табличные, транзакционные, пространственные и т. д. [3]. Модель данных определяет подходы, которые используются в алгоритмах поиска закономерностей. В данной работе будем рассматривать только табличные данные.
Существует множество способов формализации понятия закономерностей в табличных данных [4,5]. Одним из примеров такой формализации являются хорошо известные функциональные зависимости [11]. Такие формальные описания будем называть примитивами или просто зависимостями. Информация о закономерностях в данных используется для решения таких прикладных задач, как очистка данных (data cleaning), исследование данных (data exploration), реверс-инжиниринг баз данных (database reverse engineering) и оптимизация запросов в системах управления базами данных [1,15]. Поэтому были разработаны и продолжают разрабатываться алгоритмы автоматического поиска зависимостей.
Другим примером закономерности в табличных данных является уникальная комбинация колонок (Unique Column Combination, UCC) — набор атрибутов таблицы, проекция по которым не имеет одинаковых кортежей. UCC называется минимальной, если никакое подмножество ее атрибутов не является UCC. Важным свойством UCC является то, что уникальность комбинации колонок сохраняется при добавлении в неё любых других колонок. Это означает, что при автоматическим поиске UCC, достаточно находить только минимальные. Информация о том, какие комбинации колонок являются уникальными, необходима для решения таких задач, как сопоставление схем (schema matching) [19] или интеграция данных (data integration) [22]. Однако такая информация не всегда доступна, поэтому возможность поиска минимальных UCC над заданной таблицей является важной функциональностью любого профилировщика данных.
Платформа Desbordante [7] является наукоёмким профилировщиком данных с открытым исходным кодом. Она содержит алгоритмы поиска различных примитивов и предоставляет интерфейсы к ним, а также реализует сценарии решения прикладных задач анализа данных. Начальной мотивацией для создания Desbordante послужили недостатки существующей платформы Metanome [6], описанные в работе [8]. К ним относятся, например, не самая оптимальная производительность из-за использования Java в качестве основного языка программирования и отсутствие дружественных к пользователю интерфейсов. Более того, в Metanome алгоритмы поиска примитивов изолированы от реальных задач, то есть платформа не предоставляет ничего кроме самих алгоритмов, что уменьшает ее эффективность в применении к индустриальным задачам. Поэтому одной из целей Desbordante является предоставление возможностей по решению прикладных задач с помощью этих алгоритмов. В данный момент Desbordante активно развивается и нуждается в расширении набора поддерживаемых примитивов, в том числе в поддержке UCC. Это послужило мотивацией для задачи разработки высокопроизводительного алгоритма поиска уникальных комбинаций колонок, поставленной перед автором данной работы.
Существует множество способов формализации понятия закономерностей в табличных данных [4,5]. Одним из примеров такой формализации являются хорошо известные функциональные зависимости [11]. Такие формальные описания будем называть примитивами или просто зависимостями. Информация о закономерностях в данных используется для решения таких прикладных задач, как очистка данных (data cleaning), исследование данных (data exploration), реверс-инжиниринг баз данных (database reverse engineering) и оптимизация запросов в системах управления базами данных [1,15]. Поэтому были разработаны и продолжают разрабатываться алгоритмы автоматического поиска зависимостей.
Другим примером закономерности в табличных данных является уникальная комбинация колонок (Unique Column Combination, UCC) — набор атрибутов таблицы, проекция по которым не имеет одинаковых кортежей. UCC называется минимальной, если никакое подмножество ее атрибутов не является UCC. Важным свойством UCC является то, что уникальность комбинации колонок сохраняется при добавлении в неё любых других колонок. Это означает, что при автоматическим поиске UCC, достаточно находить только минимальные. Информация о том, какие комбинации колонок являются уникальными, необходима для решения таких задач, как сопоставление схем (schema matching) [19] или интеграция данных (data integration) [22]. Однако такая информация не всегда доступна, поэтому возможность поиска минимальных UCC над заданной таблицей является важной функциональностью любого профилировщика данных.
Платформа Desbordante [7] является наукоёмким профилировщиком данных с открытым исходным кодом. Она содержит алгоритмы поиска различных примитивов и предоставляет интерфейсы к ним, а также реализует сценарии решения прикладных задач анализа данных. Начальной мотивацией для создания Desbordante послужили недостатки существующей платформы Metanome [6], описанные в работе [8]. К ним относятся, например, не самая оптимальная производительность из-за использования Java в качестве основного языка программирования и отсутствие дружественных к пользователю интерфейсов. Более того, в Metanome алгоритмы поиска примитивов изолированы от реальных задач, то есть платформа не предоставляет ничего кроме самих алгоритмов, что уменьшает ее эффективность в применении к индустриальным задачам. Поэтому одной из целей Desbordante является предоставление возможностей по решению прикладных задач с помощью этих алгоритмов. В данный момент Desbordante активно развивается и нуждается в расширении набора поддерживаемых примитивов, в том числе в поддержке UCC. Это послужило мотивацией для задачи разработки высокопроизводительного алгоритма поиска уникальных комбинаций колонок, поставленной перед автором данной работы.
✅ Заключение
В ходе работы были достигнуты следующие результаты.
1. Выполнен обзор существующих подходов к автоматическому поиску UCC и выбран один из наиболее эффективных алгоритмов поиска — HyUCC. С целью переиспользования имеющегося кода изучен алгоритм поиска функциональных зависимостей HyFD, как алгоритм того же класса, что и HyUCC, и его реализация в Desbordante.
2. Алгоритм HyUCC реализован для платформы Desbordante (C++). Созданы интерфейсы, общие для любых алгоритмов поиска UCC, модуль тестирования и интерфейс к HyUCC для взаимодействия через Python. При реализации были выделены в отдельные модули и переиспользованы общие части HyUCC и HyFD.
3. С помощью профилирования найдены узкие места и реализована модифицированная версия алгоритма с использованием многопоточности.
4. В рамках экспериментов использованы синтетические и реальные наборы данных, применявшиеся авторами Metanome. Были выявлены следующие факты:
• обычная версия HyUCC, реализованная в платформе Desbordante, в среднем в 21 раз эффективнее реализации в Metanome;
• модифицированная версия алгоритма в среднем в 2.5 раз эффективнее обычной реализации в платформе Desbordante, и в 17 раз — параллельной версии в Metanome;
• модифицированная версия алгоритма потребляет в десять раз меньше памяти, чем многопоточная реализация в Metanome.
Код реализации открыт и доступен в репозитории4.
4https://github.com/Mstrutov/Desbordante
1. Выполнен обзор существующих подходов к автоматическому поиску UCC и выбран один из наиболее эффективных алгоритмов поиска — HyUCC. С целью переиспользования имеющегося кода изучен алгоритм поиска функциональных зависимостей HyFD, как алгоритм того же класса, что и HyUCC, и его реализация в Desbordante.
2. Алгоритм HyUCC реализован для платформы Desbordante (C++). Созданы интерфейсы, общие для любых алгоритмов поиска UCC, модуль тестирования и интерфейс к HyUCC для взаимодействия через Python. При реализации были выделены в отдельные модули и переиспользованы общие части HyUCC и HyFD.
3. С помощью профилирования найдены узкие места и реализована модифицированная версия алгоритма с использованием многопоточности.
4. В рамках экспериментов использованы синтетические и реальные наборы данных, применявшиеся авторами Metanome. Были выявлены следующие факты:
• обычная версия HyUCC, реализованная в платформе Desbordante, в среднем в 21 раз эффективнее реализации в Metanome;
• модифицированная версия алгоритма в среднем в 2.5 раз эффективнее обычной реализации в платформе Desbordante, и в 17 раз — параллельной версии в Metanome;
• модифицированная версия алгоритма потребляет в десять раз меньше памяти, чем многопоточная реализация в Metanome.
Код реализации открыт и доступен в репозитории4.
4https://github.com/Mstrutov/Desbordante
ИЛИ
Поиск аналога
📕 Список литературы
🖼 Скриншоты
🛒 Оформить заказ
⚡ Работу высылаем в течении 5 минут после оплаты.