в общедоступных астрономических архивах (см., например, [
Увеличение количества независимых источников информации об известных астрономических объектах (данные наблюдении в разных спектральных диапазонах, полученные в разное время, разными телескопами) критически важно для решения задачи их точнои классификации и измерения физических характеристик. Также важнои практическои задачеи для современных небесных обзоров является поиск новых астрономических объектов в непрерывном потоке данных наблюдении, поступающих в виде астрономических каталогов, непосредственно с телескопа. Для поиска новых небесных объектов новыи каталог, поступившии с телескопа, необходимо сопоставить в реальном времени с астрономическими каталогами, полученными ранее. Таким образом, задача сопоставления астрономических каталогов имеет важное практическое значение для наблюдательнои астрофизики.
Современные объемы данных астрономических каталогов из небесных обзоров требуют распределенного хранения. В свете экспоненциального роста ожидаемого объема данных астрономических каталогов в ближаишем будущем, при построении системы для сопоставления астрономических каталогов необходимо заложить требование ее горизонтальнои масштабируемости.
Целью настоящеи работы является разработка распределённого
горизонтальномасштабируемого метода сопоставления астрономических каталогов. Предложенныи здесь метод
сопоставления каталогов разрабатывался для встраивания в распределённую систему обработки и
анализа больших массивов астрономических данных [
Статья построена следующим образом. В следующем разделе дана формальная постановка задачи сопоставления астрономических каталогов и сделан обзор имеющихся подходов к ее решению. Далее описан предлагаемыи нами распределенныи метод сопоставления астрономических каталогов на платформе Apache Spark. Затем представлены выполненные эксперименты, которые подтверждают точность и горизонтальную масштабируемость предложенного метода. В последнем разделе представлены наши выводы. Задача сопоставления астрономических каталогов и методы ее решения
В настоящеи работе будет рассматриваться классическая задача сопоставления (кроссотождествления) двух астрономических каталогов по небесным координатам, которая может быть формализована следующим образом.
Определения: • Астрономический объект – кортеж, состоящий из идентификатора, сферических координат RA (прямое восхождение) и DEC (склонение), и прочих характеристик небесного объекта: X= [ , , , [ ]]; • Каталог астрономических объектов – двумерная таблица, строками которой являются астрономические объекты.
Дано: • , – каталоги астрономических объектов; • ( , ) = ℎ ( , ) - функция углового расстояния на сфере между астрономическими объектами X и Y; • – максимально допустимое угловое расстояние между отождествлёнными объектами (радиус сопоставления). Наити каталог астрономических объектов С: = { [ , ]: ∈ , ∈ , ∀
∈ : ∀ ∈ : ( , ) < ( , ), ( , ) < ( , ) < ( , ), }. • • Качество сопоставления оценивается по следующим метрикам: Точность (precision) = & ; Полнота (recall) = &
,
где числа , и & представляют собои, соответственно: точное
число сопоставлении (пар объектов из двух каталогов), наиденное число сопоставлении
предложенным нами методом и наиденное число сопоставлении одновременно являющимися
точными. Для поиска точных сопоставлении двух каталогов, в качестве эталона, мы будем
использовать популярную программу TOPCAT [
Отметим, что в такои постановке задача сопоставления двух астрономических каталогов сводится к задаче поиска для каждого объекта первого каталога ближаишего соседа внутри радиуса сопоставления среди всех объектов второго каталога. Ниже рассмотрены несколько распространенных методов сопоставления астрономических каталогов, которые находят применение в современных астрономических исследованиях.
В статье [
Современные реляционные СУБД позволяют строить пространственныи индекс на
разнообразных древовидных иерархических структурах данных (например, R-деревьях - см. [
Эффективным решением для построения распределенных алгоритмов сопоставления
каталогов является разбиение небеснои сферы на неперекрывающиеся области и сопоставление
объектов в каждои области независимо от других. При таком подходе необходимо предусмотреть
дополнительную обработку объектов из разных областеи, расположенных рядом с границеи (далее
– граничные эффекты). В статье [
Рис. 1. Первые 4 уровня разбиения HEALPix
В работах [
Система обработки астрономических данных [
Apache Spark предоставляет широкии набор возможностеи для распределённои обработки данных, включая возможность чтения и записи в распространённые распределённые фаиловые системы, кэширование данных в памяти для многоразового использования, удобныи механизм использования сторонних библиотек, возможность работы в интерактивном режиме, а также большои набор встроенных методов обработки данных, включая методы интеллектуального анализа данных. Spark – это масштабируемая платформа анализа данных, которая включает в себя примитивы для вычислении в оперативнои памяти. Основнои абстракциеи Spark являются устоичивые распределенные наборы данных (RDD, англ. Resilient Distributed Datasets).
При разработке распределённого алгоритма сопоставления каталогов астрономических
объектов на базе Apache Spark за основу был взят метод, предложенныи в статье [
Предлагаемыи нами алгоритм сопоставления каталогов состоит из следующих этапов: 1. Считывание объектов из каталогов в распределённые массивы (RDD); 2. Нахождение для каждого объекта индексов HEALPix (клеток) с учётом граничных эффектов и возможнои фильтрациеи; 3. Группировка объектов в новые массивы по ключу – индексу клетки; 4. Соединение по ключу двух сгруппированных массивов; 5. Поиск наилучшего сопоставления между объектами каталогов в пределах каждои клетки; 6. Устранение дубликатов, появившихся при учёте граничных эффектов; 7. Запись отобранных пар объектов в объединённыи каталог.
В качестве языка реализации алгоритма в Apache Spark был выбран язык программирования Java. Ниже подробно рассмотрены этапы, непосредственно реализующие логику метода.
Учёт граничных эффектов. Предложенныи метод позволяет учесть граничные эффекты с минимальными накладными расходами. Учёт границ проводится только для того каталога, для которого ведётся поиск сопоставлении в другом каталоге. Границеи для клетки HEALPix некоторого уровня разбиения назовем все клетки HEALPix более высокого уровня разбиения, окрестность которых не полностью входит внутрь даннои клетки (рис. 2). Каждыи объект нужно поместить во все клетки низкого уровня разбиения, с которыми пересекается окрестность его клетки высокого уровня разбиения. Уровень разбиения для границы выбирается так, чтобы клетка HEALPix данного уровня вмещала не менее четырех площадеи кругов сопоставления объектов (4 ∗ ) в каталогах. Тогда можно гарантировать, что для всех объектов будет наидено глобально наилучшее сопоставление, а не локально лучшее внутри конкретнои клетки. Для выбранного нами радиуса сопоставления каталогов, равного 1 секунде дуги, для учета граничных эффектов был выбран 16 уровень разбиения HEALPix. Следует отметить, что число дубликатов, появившихся в результате учёта граничных эффектов, экспоненциально зависит от разницы между базовым и граничным уровнями разбиения. Например, если при разнице в 12 уровнеи разбиения число дубликатов составляет всего 0.1% от общего числа объектов, то при разнице в 4 уровня дублирование составляет уже 26%, что является значительным показателем.
Рис. 2. Обработка граничных эффектов в предложенном методе
Поиск наилучшего сопоставления внутри клетки. После того, как объекты сгруппированы в массивы по клеткам (с учётом граничных эффектов), каждую клетку можно обрабатывать независимо от других. Чтобы сопоставить каталоги «А» и «B» в клетке разбиения c индексом «i», нужно наити для каждого объекта из «А » ближаишии к нему объект из «В ». Алгоритм состоит из следующих шагов: 1. Сортировка каталога «А » по склонению (dec) 2. ∀ ∈ «В »: бинпоиск ∈ «А »: | . − . | < ; 3. ∀ ∈ «В »: ∀ ∈ «А »: | . − . | < :
Если ( , ) < ( , ), то обновляем ближаишии к объект; 4. На выходе массив , ближаиших к каждому .
Сложность алгоритма сопоставления – (( + ) log ), где , – число объектов 1 и 2 каталога, расположенных в клетке с индексом «i».
Устранение дубликатов. Дубликаты появляются в результате учёта граничных эффектов. Для каждого объекта первого каталога может возникнуть от 1 до 4 сопоставлении из второго каталога. Для устранения дубликатов требуется сгруппировать массив пар объектов по ключу – идентификатору первого объекта из пары, выбрать объект, ближаишии к искомому объекту в его группе, и записать его в результирующии массив. Эксперименты подтверждают качество обработки граничных эффектов предложенным методом, благодаря чему полнота и точность метода составляют 100% в рамках формальнои постановки задачи.
На рис. 3 представлено сравнение скорости работы TOPCAT и предложенного метода на локальнои машине. Предложенныи метод на одном ядре процессора работает быстрее в 2.8 раза за счёт эффективного соединения каталогов и поиска ближаиших соседеи. При выделении программе всех четырёх ядер процессора скорость работы возросла ещё в 3.7 раз.
Так как алгоритм использует разбиение HEALPix, возникла необходимость в оценке скорости работы в зависимости от используемого уровня разбиения. Число клеток HEALPix находится в степеннои зависимости от уровня разбиения, а число объектов в однои клетке обратно пропорционально числу клеток. Число клеток напрямую влияет на степень параллелизма алгоритма, а число объектов в клетке влияет на время обработки каждого из параллельных вычислителеи. Также следует отметить, что из-за неравномерности покрытия неба цифровыми обзорами, в некоторых клетках может содержаться значительно больше объектов, чем в остальных. Таким образом, критическии путь алгоритма зависит от баланса между размером клетки и числом объектов в неи. На третьем уровне разбиение HEALPix содержит 768 клеток, рассматривать уровни ниже не имеет смысла из-за недостаточнои степени параллелизма. На 12 уровне разбиение содержит более 200 миллионов клеток, что практически равносильно числу объектов в исходных каталогах, и уровни выше рассматривать не имеет смысла, так как из-за них будет происходить повышение объёма данных, а не его понижение. Наилучшую скорость алгоритм показал при использовании HEALPix уровня 5 (рис. 4). Число клеток на данном уровне составило 12288, что является хорошим ресурсом параллелизма. Время сопоставления каталогов SDSS и GALEX составило 673 секунды. Число дублеи при учёте граничных эффектов составило 0.4%. 1722 619
169
References