Содержание к диссертации
Введение
Глава 1. Обзор технологий поиска научных данных 14
Глава 2. Алгоритмы распределенного поиска сценария событий 28
2.1 Абстрактная модель данных ESSE-CDM 28
2.2 Определение понятия "сценарий событий" 36
2.3 Построение аппарата функций нечеткой логики с дискретной областью значений 43
2.4 Использование нечетких временных интервалов в запросе 52
2.4.1 Логическое представление о каузальных условиях 52
2.4.2 Алгоритм вычисления 53
2.4.3 Немонотонные функции 57
2.4.4 Применение 57
2.5 Распределенный вариант алгоритма поиска 58
Глава 3. Программная реализация сервисов распределенной обработки и поиска данных 66
3.1 Архитектура 66
3.2 Сервис выборки данных и язык запросов 69
3.3 Поисковый сервис и язык запросов 70
3.4 Сервис обработки данных и язык запросов 73
3.5 Совместимость с Грид технологией 76
Глава 4. Примеры использования системы 79
4.1 Интеграция данных 79
4.2 Статистика экстремальных событий и анализ климатических трендов ... 81
4.3 База нечетких правил для экспертной системы 88
Заключение 100
Литература
- Построение аппарата функций нечеткой логики с дискретной областью значений
- Логическое представление о каузальных условиях
- Сервис выборки данных и язык запросов
- Статистика экстремальных событий и анализ климатических трендов
Введение к работе
Объект исследования и актуальность темы
Интенсивное развитие технологий распределенных вычислений и инфраструктуры Грид требуют новых методов параллельной обработки и поиска данных в распределенных системах управления базами данных и базах знаний, а также создания новых инструментальных средств разработки интеллектуальных систем для поддержки принятия решений и обучения. Актуальность этих проблем в настоящее время становится особенно значимой: при интерактивном анализе данных в распределенных сверхбольших базах данных по окружающей среде; для выбора реалистичных сценариев погоды в обучающих программах и виртуальных тренажерах; для оценки степени воздействия окружающей среды на техногенные системы (транспорт, коммуникации) в системах поддержки принятия решений.
В настоящее время наблюдаются быстрые глобальные изменения в окружающей среде, во многом определяя характер деятельности человека. Поэтому большое внимание уделяется сбору, анализу и прогнозу данных об окружающей среде. Полвека насчитывает история глобальных цифровых сетей наблюдений изменений среды и космического зондирования: сейсмология, метеорология, магнитосфера и ионосфера, космическая погода, архивы цифровых изображений и телеметрия со спутников. Выводы Межправительственной группы экспертов ООН по изменению климата, МГЭИК (Intergovernmental Panel on Climate Change, IPCC)1 во многом делаются на основании изучения цифровых моделей, использующие сверхбольшие базы данных по метеорологии, представляющие из себя временные ряды с географической привязкой по станциям или координатам. Оценки МГЭИК публикуются с 1991 г. каждые четыре года [1], пятый доклад
намечен на 2013 г. На совещании центров данных МГЭИК по подготовке пятого доклада в Сиэтле в сентябре 2008 г. предполагается объем научных баз данных для пятого доклада 3 петабайта с зеркальным хранениемв трех центрах данных в США и Западной Европе и с оперативным доступом для 23 ведущих исследовательских центров по метеорологии, экологии, биохимии и численному моделированию [2]. Аналогичные показатели по объемам и топологии имеют центры данных по дистанционному зондированию администарций США по окенанам и атмосфере (NOAA) [3] и ислледованию космического пространства (NASA)4 [4]. В сентябре 2008 г. первый параллельный кластер для научных баз данных объемом более 1 Пбайт был запущен в университете Джона Хопкинса, США. На нем предполагается хранить многомерные массивы данных по астрофизике и по сенсорным сетям для био-экологического мониторинга [5].
Нарастает процесс глобальной информатизации научных исследований на основе Интернета, веб-сервисов и динамических веб-приложений (порталов). На национальном уровне научным сети сегодня имеют емкости до терабит в секунду (Национальный центр добычи данных США в Чикаго)5. Сетевые емкости международных научных сетей (GLORIAD6, Geant7) сегодня находятся на уровне 10-100 Гбит/с с возможностью динамической перестройки топологии и выделения емкости по запросу от приложений. Это создает предпосылки для создания сервисов распределенной параллельной обработки и анализа сверхбольших баз данных (cloud computing). При этом предполагается доставка вычислительных задач на процессоры рядом с данными, а не передача больших объемов данных для обработки на удаленный суперкомпьютер.
Для виртуализации доступа и оптимизации нагрузки на вычислительную и сетевые ресурсы разрабатывается промежуточное программное обеспечение (НПО) и развертывается инфраструктура под собирательным именем Грид [6]. Первоначально Грид охватывал лишь распределенные вычисления, например, распределенную статистическую обработку экспериментальных данных на Большом адроном коллайдере в ЦЕРНе (инфраструктура LCG, позднее EGEE). К настоящему времени существует как минимум три различных пакета ППО и
о п
основанных на них инфраструктуры для грид-вычислений: EGEE , UNICORE и Globus Toolkit 410. Естественно, сложные вычислительные задачи моделирования глобальной циркуляции атмосферы, океана, магнитного поля и потоков частиц в околоземном пространстве, обработки данных дистанционного зондирования находят реализацию на всех доступных грид-инфраструктурах. При этом, в связи с высокой стоимостью вычислительных экспериментов (для климатических моделей нередки вычисления на самых мощных суперкомпьютерах в течение нескольких лет), необходимо не только гарантировать качество больших объемов входных данных, но и долговременно хранить результаты дорогостоящих расчетов с возможностью поиска и анализа данных.
Информационная поддержка сельскохозяйственной деятельности и землепользования, транспорт, туризм уже не могут обойтись без оперативных потоков данных о погоде, космоснимков и электронных карт. Виртуальные игровые миры и профессиональные тренажеры требуют детальных и реалистичных моделей окружающего мира. Это ускоряет доступ и интеграцию данных между различными областями науки и коммерческих приложений.
Чтобы поддерживать такие темпы информатизации, от информационных технологий требуется ускорение темпов развития, что мы сейчас и наблюдаем:
распределенные Грид-вычисления, параллельные ГИС, локальные веб-сервисы на основе VirtualEarth и GoogleMaps, семантический веб, сверхбольшие базы данных и хранилища метаданных.
В итоге, сложилось два полюса в сфере IT: огромный объем исходных данных с одной стороны, и приложения, работающие с этой информацией с другой. Однако, многие терабайты информации не позволяют использовать их напрямую, простым скачиванием и перебором. От приложений требуется более "интеллектуальный" подход к определению области своих интересов. В результате, приходим к необходимости анализа данных не только в научных расчетах, но и в "бытовых" приложениях. Кроме того, со своим развитием, IT все больше стремятся к эмулированию "естественного языка" и человеческого мышления. Экспертные системы и искусственный интеллект развиваются быстрыми темпами. Не последнюю роль в этом играет тот факт, что объем данных растет в экспоненциальной прогрессии, в то время как число экспертов, их обрабатывающих, - в линейной. В связи с этим, условия выбора и анализ данных становится все более сложными, и зачастую, в погоне за "логичностью" теряют свою "математическую строгость". Поэтому все больше возникает потребность в коммуникаторе, который будет предоставлять достижения ІТ-технологии в пользование потребителей, нужен универсальный механизм поиска, анализа и добычи научных данных.
К настоящему времени довольно широкое развитие получил текстовый поиск и текстовое индексирование. Также существуют системы для поиска метаданных, такие например, как Global Change Master Directory (GCMD), разработанная в HACA или Master Environmental Library (MEL), созданная Отделом моделирования Министерства обороны США. Однако, поиск внутри цифровых данных пока неразвит. Весьма показательна ситуация с развитием поисковых систем корпораций Google и Microsoft:
1) Первый уровень: поиск по вебу (google, Yandex и др.)
Второй уровень: специализированный поиск (например, поиск внутри документов и изображений)
Третий уровень: поиск и визуализация данных с географической привязкой (Google Earth, Microsoft VirtualEarth)
На четвертом уровне должен стоять поиск и анализ внутри многомерных массивов научных данных, в первую очередь временных рядов.
Анализ временных рядов можно разделить на два основных вида: анализ трендов и анализ экстремальных выбросов. Первый можно представить как анализ движения во времени центра масс пространства данных, в то время как второй - анализ тенденции движения границ. Он имеет значение при анализе долгосрочных изменений климата. Последний вид также имеет немаловажное значение, поскольку анализирует граничные (предельные) состояния среды, зачастую являющиеся критическими для любой деятельности и инфраструктуры, которые обычно рассчитываются исходя из среднестатистических показателей.
Современная наука во многом междисциплинарная. Например, анализ влияния климата на биосферу, анализ причинных связей в метеорологии и космической погоде. Это накладывает дополнительные требования на систему добычи и анализа данных: во-первых, процесс анализа должен производиться в различных средах совместно, во-вторых, требуется унифицированный интерфейс доступа к данным в разных источниках. Назрела потребность в «глобализации» научных данных.
Актуальность данной работы обусловлена тем, что она посвящена поиску, междисциплинарному анализу (как трендов, так и экстремальных выбросов) и выборке данных в распределенных сверхбольших архивах данных по окружающей среде (междисциплинарной).
Цели и задачи работы
Целью работы являлось разработка системы поиска, анализа и распределенной выборки данных в сверхбольших архивах данных по окружающей среде. Для достижения указанной цели необходимо решить следующие задачи:
Разработать систему алгоритмов для распределенного поиска в сверхбольших архивах научных данных. Предоставить пользователю возможность формулировать запросы к архивам с помощью естественных языковых конструкций
Разработать программное средство, которое бы реализовывало алгоритмы из п. 1, а также поддерживала распределенные выборки и добычи данных в сверхбольших архивах данных по окружающей среде.
Встроить данное ПО в инфраструктуру Грид.
Провести апробацию и оценить эффективность предложенных алгоритмов на различных прикладных задачах
Научная новизна
Для прогноза глобальных изменений климата строится множество теорий. Каждая из них выводит определенные закономерности и сценарии развития событий. Результаты данной работы могут применяться для проверки и отслеживания предполагаемых климатических сценариев. В работе формулируется определение сценария событий окружающей среды в терминах нечеткой логики, которое включает не только значение параметров, но и каузальные связи - изменение значений параметров во времени. В работе также формулируется алгоритм поиска таких сценариев на классе источников, подчиняющихся единой модели данных.
В работе предложен новый подход к системам поиска и анализа данных по окружающей среде. В отличие от аналогичных систем, в которых поиск осуществляется по метаданным и текстовой информации, в данной работе представлен подход к поиску по значениям временных рядов параметров
среды, который оптимизирован для работы со сверхбольшими и распределенными массивами данных в интерактивном режиме. Разработана общая модель представления данных для подобной системы, а также методы оценки качества и сравнения результатов поиска.
Инфраструктура системы совместима с Грид-технологией, что дает возможности пользоваться всеми возможностями Грид: системой авторизации, Грид-инфраструктурой (ресурсы, мощности), и т.п. В работе также реализованы потоковые алгоритмы обработки данных, оптимизированные под работу в сети с большими объемами данных - пользователю не требуется закачивать данные и промежуточные результаты расчетов на свою машину. Это дает возможность использовать результаты работы для расчетов по числовым моделям в Грид-среде.
Практическая значимость работы
В настоящей работе предложен абстрактный уровень веб-сервисов данных для виртуализации баз данных, с помощью которых выбираются временные ряды с параметрами окружающей среды для поиска событий. Интерфейс источника данных реализован в виде плагинов в контейнере OGSA-DAI с простыми XML-схемами ввода и вывода. Следование спецификации OGSA-DAT и использование языка программирования Java/J# позволяет нам погрузить виртуальные веб-сервисы данных в большинство из существующих сегодня контейнеров веб- и грид-сервисов, включая Microsoft , Apache Tomcat/Axis, WSRF Globus Toolkit 4, OMIT, и EGEE gLite.
Представим, например, что пользователю не столько нужны все данные о погоде в Московской области за последние 50 лет, сколько нужны примеры атмосферных фронтов вблизи Москвы. Более того, представим, что пользователю нужны изображения со спутников в момент прохождения атмосферного фронта и оценка, как часто наблюдались эти события вблизи Москвы за последние 10 лет. Ответы на подобные вопросы можно получить с помощью разработанного в рамках настоящей работы ПО. Данная работа
может быть использована также в исследовании глобального изменения климата, в агроклиматологии.
Настоящая работа выполнялась в Геофизическом центре (ГЦ) и в Институте космических исследований (ИКИ) РАН и на факультете вычислительной математики и кибернетики МГУ при поддержке грантов «Система поиска погодных сценариев - СГШС» (Environmental Scenario Search Engine — ESSE) от Исследовательской лаборатории Майкрософт (MSR) в Кембридже, Великобритания, и «Интерактивный ресурс данных по солнечно-земной физике» (Space Physics Interactive Data Resource - SPIDR) от Национального управления по исследованию атмосферы и океана (NOAA) США.
Результаты работы нашли прямое применение в совместных междисциплинарных исследованиях ИКИ РАН и MSR для анализа региональных трендов и зависимостей между изменениями в климате, в растительности. Созданные в работе сервисы поиска и обработки сверхбольших баз данных по истории климата используются совместно с разработанными в ИКИ методами дистанционного зондирования растительности с использованием данных спутниковых наблюдений. Компания Майкрософт осуществляет техническую экспертизу, а также предоставляет необходимые вычислительные ресурсы, включая кластер параллельной обработки данных.
Созданные в результате работы Грид-сервисы OGSA-DAI для поиска и обработки данных установлены на ресурсном центре СКИФ-Грид в ГЦ РАН в Москве и в Национальном геофизическом центре NOAA в Болдере, штат Колорадо и регулярно используются для доступа к архивам данных по климату и космической погоде в системах доступа к распределенным архивам данных NOAA Comprehensive Large Array Stewardship System (CLASS) и Space Physics Interactive Data Resource (SPIDR).
Апробация работы и публикации
Результаты диссертации опубликованы в работах [7]-[13] и обсуждались на следующих конференциях и семинарах:
l)ZhizhinM, EKihn, RRedmon, A Poyda, DMishin, DMedvedev, V Lyutsarev, Integrating and mining distributed environmental archives on Grids, VLDB DMG Workshop, Seul, September 2006
Алексей Пойда, Михаил Жижин, Дмитрий Мишин, Дмитрий Медведев, Сергей Березин, Дмитрий Войцеховский, Василий Люцарев, Эрик Кин. Система поиска погодных сценариев. Пятая Юбилейная Открытая Всероссийская конференция "Современные проблемы дистанционного зондирования Земли из космоса" Москва, ИКИ РАН, 12-16 ноября 2007г.
Zhizhin М, D Medvedev, A Poyda, V Lyutsarev, Grid data mining with CDM active storage, 3rd GRID e-collaboration Workshop for Earth Science and Space 16-17 January 2008, ESRIN, Frascati (Rome), Italy
Пойда A.A. Поиск данных в Грид: соотношение производительности сетей, вычислительных кластеров, хранилищ данных. "Современные информационные технологии для научных исследований" Магадан, 20-24 апреля 2008
Объем и структура работы
Диссертация состоит из введения, четырех глав, заключения, списка литературы (46 наименования) и приложения. Общий объем работы составляет 113 страниц, работа содержит 31 иллюстрацию и 5 таблиц
Благодарности
Автор выражает благодарность Василию Сергеевичу Люцареву, исследовательская лаборатория MSR в Кембридже, за постоянное внимание к работе, продуктивные дискуссии и конструктивную критику, Евгению Аркадьевичу Лупяну, отдел дистанционного зондировании ИКИ РАН, за постановку задачи и интерес к приложениям вычислительных методов
сравнительного анализа климатических данных и дистанционного зондирования и Эрику Кину, NOAA США, за интерес к использованию алгоритмов нечеткой логики для анализа эффектов космической погоды и постановку прикладной задачи. Автор благодарен многим сотрудникам Геофизического Центра РАН за поддержку.
Построение аппарата функций нечеткой логики с дискретной областью значений
При квантовании возникает две проблемы. Во-первых, изменяется результат, по сравнению с непрерывными логическими операторами. Это изменение будет тем заметнее, чем меньше уровней квантования используется. Казалось бы, можно использовать сколь угодно большие таблицы, но здесь мы сталкиваемся с другой проблемой: чем больше таблица, тем больше тратится времени на ее построение. В общем случае, время построение растет квадратично от числа уровней квантования.
Эти две проблемы приводят нас к вопросу: как найти оптимальный вариант. При этом возникает новая проблема: оценить затраченное время мы можем, а как оценить расхождение в результатах?
Чтобы определить, насколько один результат поиска "похож" на другой, нужно ввести норму разногласия между двумя ответами. Мы делим все нормы на два класса: нормы, учитывающие изменение значений релевантности каждого сценария и нормы, учитывающие изменение порядка кандидатов-событий при сортировке последних по убыванию их релевантности. Следует заметить, что, хотя эти два класса отчасти связаны (например, если два ответа полностью совпадают по коэффициентам, то они полностью совпадают по порядку этих коэффициентов), все же они отличаются друг от друга.
Для сравнения результатов поиска мы используем три нормы: DIFF, RMSE, NMSE. Норма, учитывающая порядок кандидатов-событий DIFF( X, Y, size ), может быть вычислена по формуле где X — это таблица размера size, куда в порядке убывания релевантности входят первые size событий, полученные в качестве результата первого запроса. Y — аналогичная таблица для результата второго запроса. TimeX — множество временных точек, представленных в таблице X. TimeY — множество временных точек, представленных в таблице Y. RMSE (root mean square error) — норма, учитывающая только расхождение в значениях релевантности. Общая формула такова: где N — общее число кандидатов в ответе. Но мы модифицировали эту формулу вследствие того, что число кандидатов может быть несколько десятков тысяч. Наша формула выглядит так: где TimeX и TimeY означают тоже, что и в предыдущей формуле. В первом случае мы пробегаем по таблице X (строится, как и в предыдущем примере), а вот соответствие ищем не в таблице Y (так как в ней может не оказаться соответствующего элемента), а во всем результате второго запроса. Поэтому соответствие просто не может не найтись. Затем делаем такую же процедуру относительно таблицы Y, после чего берем среднее арифметическое от найденных величин.
И последняя норма — NMSE (normalized mean square error) — тоже учитывает разницу значений коэффициентов релевантности. Общая формула выглядит так:
С точки зрения пользователя могут потребоваться такие условия как: событие А произошло после события В, событие В произошло незадолго до события А, и т.п. Во всех таких условиях можно выделить три основные составляющие: 1) Слова «до» и «после» 2) Термины состоялось, не состоялось 3) Термины типа «вскоре», «незадолго» и т.п. Мы делим каузальные операторы на две категории: 1) Операторы, не использующие третий вид терминов (назовем их абсолютными) 2) Операторы, использующие третий вид терминов (назовем их относительными, ибо понятия «долго», «быстро» и т.п. могут пониматься по-разному, относительно разных ситуаций) Формализуем операторы каждой категории 1) В первой категории все возможные комбинации приводят к четырем условиям: a. Событие А произошло после события В. b. После события А не происходило событие В c. Событие А произошло до события В d. До события А не происходило события В 2) Во второй категории будут те же 4 условия, но с еще одним заданным параметром, определяющим, степень близости этих событий по времени. Мы используем лингвистические предикаты, с теми же названиями, которые мы используем в лингвистических предикатах для оценки значений параметра (рис. 7), но с другими функциями принадлежности (почему - объясняется ниже). Получится: a. Событие А произошло после события В в течение временного предиката L. b. После события А не происходило событие В в течение временного предиката L c. Событие А произошло до события В в течение временного предиката L d. До события А не происходило события В в течение временного предиката L
Начнем с первой категории. Итак, у нас на входе два временных ряда ФП соответствующие состояниям А и В: A = {a(i), t (і)І І = 1 to n} В = {b(i) , t" (і) I I = 1 to m} На выходе должен получиться один результирующий временной ряд С = (c(i), t "(i)l I = 1 to k} Итак, для вариантов с "а" по "с" первой категории результат определяется формулами: a) k = п f " (і) = t (і) і=1 to n с(і) = AND ( a (і), max{b(f) t" (f) t (і) } ), b) k=n t " (i) = t (i) i=l to n c(i)=AND( a(i), min{l-b(f) t (f) t (i) } ) или c(i)=AND( a(i), l-max{b(f) t"(f) t (i)} ) c) k = n t " (i) = t (i) i=l to n с(і) = AND( а(і), max{b(f) t (f) t (i) } ), d) k=n t (i) = t (i) i=l to n c(i)=AND( a(i), min{l-b(f) I t" (f) t (i) } ) или c(i)=AND( a(i), l-max{b(f) t"(f) t (i)} ) Рассмотрим теперь вторую категорию. Здесь введем функцию R(t , t", L, Т) - [0,1], где Т - временной интервал, принятый за норму (относительно него будут рассматриваться такие понятия, как «давно», «недавно» и т.п.), t и t" — время двух событий, L - временной предикат (VerySmall, Small, Average, Large, VeryLarge). Функция вычисляет степень соответствия того, что временной интервал t " относится к временному интервалу Т с соответствием L.
Логическое представление о каузальных условиях
Алгоритм расчета следующий. Рассматриваем А и В с конца: 1) Заносим во временную переменную Вшах значение 0 (в этой переменной будет хранится значение b(f), минимизирующее значение l-b(f) R для текущего t (i)) 2) Заносим во временную переменную BRmin значение 1 (в этой переменной будет храниться текущее минимальное значение l-b(f) R для текущего t (i)). 3) Устанавливаем указатели аЛ и ЬА на последние элементы А и В соответственно (будем просматривать временные ряды с конца) 4) Вычисляем значение функции r=R(t , t") для текущих позиций. 5) Вычисляем значение z=l-r bA. 6) Если значение z = BRmin, то BRmin = z, Bmax = bA (фиксируем промежуточный минимум, а также ссылку на тот элемент, на котором он достигается) иначе сразу к п.7 7) Перемещаем ЬЛ на позицию вперед 8) Сравниваем t и t" текущих элементов (надо проверить, что мы проверяем события В после события А в момент t ). Если t t"(ecnn это уже не так, то фиксируем промежуточные минимумы как окончательные для этого значения a(i) ) - заносим в текущий аЛ значение (BRmin and аА) и устанавливаем аА на следующий элемент, а ЬА устанавливаем на Bmax, переходим к п. 9. Если нет -к п.4 9) Пересчитываем r=R(t , t") для нового аА и ЬА 10) Заносим значение z=l-r bA в переменную BRmin 11) Устанавливаем ЬА на элемент, соответствующий BRmin-1. 12) К п.4
Суть монотонности, которую мы потребовали в предыдущем разделе в том, что нам приходится начинать с предыдущего элемента, обладающим наибольшей максимальностью, а не сначала.
Напомним, что мы потребовали, чтобы функции принадлежности L были, монотонно убывающими. Но часто хочется найти условия типа "Событие А произошло примерно через X времени после события В". Здесь уже функция никак не может быть монотонной. Но данный сценарий можно переформулировать с помощью временного сдвига и совокупности двух монотонных функций: OR( CAUSE(A, shift(В,X), type A, VerySmall, Т), CAUSE(А, shift(В,X), type С, VerySmall, Т) )
Иными словами, мы берем вместо рядов А и В ряды А и shift(B,X). И в этих уже рядах ищем нечеткое условие "А произошло одновременно с В", которого тоже нет в нашем списке, но которое может быть в свою очередь выражено условием: "(А произошло после В в течение очень короткого промежутка) ИЛИ (А произошло до В в течение очень короткого промежутка)". Такой прием модно рассматривать как нечеткий временной сдвиг.
Итак, коротко подводя вышеизложенное опишем возможные случаи применения наших функций: 1) Для нахождения простого случая каузальности: когда одно событие предшествует другому 2) Для нахождения нормированного случая, когда ищется не только порядок следования событий, но и временной промежуток между ними, который может быть выражен фразами естественного языка "очень давно", "давно" "недавно", "вскоре" и т. п. 3) Для нахождения случая нечеткого временного сдвига, который может быть, например, выражен условием "Событие А произошло примерно через X времени после события В". В частности, X может быть равен нулю и условие примет вид: "Событие А произошло почти одновременно с событием В".
Большие много дисциплинарные архивы данных по необходимости распределены между удаленными хранилищами, поэтому особый интерес приобретает возможность эффективной распределенной обработки данных. Это возможно путем вычисления ряда предикатов и подвыражений на удаленных машинах, с последующей сборкой частичных результатов на одном узле. Попробуем оценить эффективность такой организации рабочего потока. Для простоты будем считать, что у нас два узла и на каждом есть источник данных. Требуется произвести поиск по некоторому алгоритму на некотором суммарном объеме данных V. В первую очередь нас интересует работа со сверхбольшими базами данных, поэтому будем рассматривать линейные алгоритмы. Кроме того, считаем, что линейный алгоритм легко распараллеливается.
Рассмотрим три случая. В первом случае мы половину данных берем с первого узла, половину со второго. Каждую половину обрабатываем на том же источнике, на котором находятся данные. Частичные результаты объединяем на одном из узлов. Это распределенный вариант поиска. Во втором случае мы берем половину данных с первого узла, половину — со второго. Необработанные данные со второго узла пересылаем на первый, где производится обработка всего объема данных целиком. Это распределенная параллельная выборка и нераспределенный последовательный поиск. В третьем же случае мы будем считать, что у нас и выборка и обработка производятся на одном узле. Это локальные последовательные выборка и поиск. Для удобства предположим, что вычислительные характеристики обоих узлов равны.
Сервис выборки данных и язык запросов
На данной диаграмме можно выделить четыре уровня. На первом (нижнем уровне) находятся источники данных, которые мы хотим интегрировать в систему. Это могут быть, например, SQL базы данных, наборы файлов на диске, или удаленные веб-сервисы. Это может быть любой источник данных, но совместимый с общей моделью данных ESSE-CDM хотя бы в одной из четырех основных подмоделей (см. раздел 2.1).
На втором уровне - драйвер, предоставляющий унифицированный интерфейс доступа к данным, не зависящий от особенностей агрегируемого источника. Для нашей системы интерфейс должен обязательно включать функцию выборки данных, которая возвращает запрошенные данные в модели ESSE-CDM в одной из четырех подмоделей (см. раздел 2.1). Так как каждая подмоделей отличается набором подмоделей, то и разновидностей функций запроса данных может быть четыре: Запрос траектории: getData(parameterURI, time_space_point_set) Запрос регулярной сетки: getData(parameterURI, latitudeSet, longitudeSet, time) Запрос произвольного набора точек: getData(parameterURI, space_point_set, time) Запрос станционных данных: getData(parameterURI, station_set, time) Здесь parameterURI - уникальный идентификатор набора данных, описывающих запрашиваемый параметр latitudeSet - набор широтных координат longitudeSet — набор долготных координат time - значения времени time_space_point_set - набор точек в пространстве координат и времени spacejjointset - набор точек в пространстве координат station_set - набор станций
К каждому источнику данных может быть реализован драйвер, поддерживающий сразу несколько функций запроса данных. Один драйвер может быть использован сразу для нескольких источников. Итак, на выходе со второго уровня мы работаем со стандартным интерфейсом и с общей ESSE-CDM моделью данных.
На третьем уровне представлено три сервиса: поисковый сервис (Search Engine), теория которого представлена в предыдущей главе, сервис обработки данных (Data Processor) и сервис доступа к данным (Data Source). Сервис обработки данных предназначен для получения новых данных на основе уже имеющихся, например, для вычисления скорости ветра по U- и V-компонентам. Сервис доступа к данным общается к драйверам источников на втором уровне. Сервисы третьего уровня могут взаимодействовать друг с другом, образуя потоки данных (Рис. 18)
На четвертом уровне производится форматирование результата и доставка ответа пользователю. Результат может быть возвращен в одном из трех форматов: бинарный NetCDF файл, NcML файл в формате XML, либо в виде бинарного потока сериализованной модели ESSE-CDM.
Описав общую архитектуру, остановимся более подробно на каждом из сервисов третьего уровня, ибо это отдельные компоненты, имеющие собственную архитектуру функциональность и собственный протокол запросов.
Сервис выборки данных получает запрос в формате XML и возвращает данные либо в формате NcML либо в формате ESSE-CDM. Как уже упоминалось выше, в драйверах мы определяем четыре вида запросов, отличающихся друг от друга набором параметров. Поэтому, для каждого типа запроса в сервисе выборки данных задается свой формат. Для запроса данных на регулярной географической сетке пример запроса может выглядеть так:
В этом примере запрашивается температура на поверхности земли в точке с координатами (40 СШ? 40" ВД) с 1 февраля по 1 июня 1967-го года. Здесь тройка (source, verticalCoord, name) определяет источник и параметр в источнике. Format задает выходной формат.
Сервис имеет набор метаданных с описанием всех источников, их типов, драйверов и параметров, заданных на этих источниках. Используя эти метаданные, сервис по тройке (source, verticalCoord, name) однозначно определяет: существует ли такой параметр, к какому драйверу обращаться, существуют ли значения параметра на запрашиваемых точках.
Одним из возможных типов параметра являются виртуальные параметры. Это параметры, которые пользователь видит как существующие в базе данных, но на самом деле при доступе к таким параметрам сервис выборки данных должен сформировать запрос на их вычисление из существующих с помощью сервиса обработки по заданной формуле. Сама формула для вычисления виртуальных параметров хранится в метаданных. В качестве примеров виртуальных параметров можно привести направление и скорость ветра, которые вычисляются из имеющихся в метерологических базах данных скоростей ветра в направлении С-Ю и В-3 (U-wind и V-wind).
Статистика экстремальных событий и анализ климатических трендов
Проект CLIVT (Climate induced vegetation change analysis tool) ведется Институтом Космических Исследований при поддержке Microsoft Research Redmond. Целью проекта является ананлиз влияния изменения климата на растительность. В качестве цифрового описания растительности выступают данные по вегетации, полученные с помощью спутниковых снимков на территории России. Описание климата представлено источниками реанализа NCEP и ERA40. Полученные тренды и экстремальные события первом и во втором наборе данных сопоставляются на предмет наличия причинных связей. Для поиска трендов и экстремальных событий в климатических данных мы использовали систему ESSE. Были вычислены следующие параметры: 1. дата перехода среднесуточной температуры воздуха через 3,4,5С весной, если далее 5 значений также выше этого порога (дата начала сезона вегетации); 2. продолжительность сезона вегетации (количество дней от начала сезона до его конца, определяемого как переход через среднесуточную температуру 3,4,5С осенью при 5-ти последующих значениях ниже этого порога); 3. сумма значений температуры воздуха за сезон вегетации, превышающих 3,4,5С 4. сумма ФАР (фотосинтез-активной радиации) за сезон вегетации. Вычисляется по формуле 0,43 Р + 0,57 R, где Р - прямая радиация на горизонтальную поверхность, R - рассеянная радиация. 5. сумма осадков за сезон вегетации; 6. сумма осадков за год; 7. коэффициент увлажнения КУ КУ=0/д (35) где КУ - коэффициент увлажнения; О - сумма осадков за год; д - среднее суточное значение дефицита влажности воздуха в году. 8. Гидротермический коэффициент Г.Т. Селянинова ГТК=0/Т (36) где О — сумма осадков за период вегетации; Т - сумма значений температуры воздуха за сезон вегетации, превышающих 3,4,5 С. ГТК рассчитывается за вегетационный период. Установлено, что ГТК=0,3 соответствует границе пустыни, ГТК=0,5 - границе полупустыни; ГТК=1,0 - границе лесостепи. 9. Биогидротермический потенциал по Рябчикову A.M.: БГШ=В Т/360 Р (37) где В — продуктивная влага (осадки минус сток) (мм) за год; Т — длина периода вегетации в днях - время между началом (при 3,4,5 С) и окончанием (при 3,4,5 С); Р — радиационный баланс за период вегетации (ккал/см ), который соответствует сумме ФАР за сезон вегетации. Считается, что величина БГТП линейно связана с продуктивностью биомассы.
Например, для поиска линейных температурных трендов мы используем температуру воздуха, осредненную по годам. После этого мы ищем тренды путем расчета регрессии и наносим результаты на карту по принципу: красным кружком обозначаем восходящий тренд, синим — нисходящий; чем круче угловой коэффициент тренда, тем больше кружок. Запрос выглядит следующим образом: getCdmData name="getTemperature" value name="parameter" value="airO.SL"/ range name="time" тіп="1976-01-01Т00:00:00UTC" max="2005-12-31T23:59:59UTC" step="21600"/ value name="level" value="0"/ range name="lat" min="-90" max="90" step="5"/ range name="lon" min="-180" max="180" step="5"/ value name="source" value="ncep25g"/ value name="essePackFormat" value=""/
Результаты отличаются, потому что ІРСС в качестве источника данных использовали другой источник данных, а именно европейскую базу CRU, в которую входят наблюдаемые данные, а не реанализ. Но суть не в этом, а в том, что для повторения подобной работы с использованием ESSE потребовалось всего 3,5 минуты.
Еще один пример расчетов температурных аномалий - поиск распределения самых жарких дней по годам. Суть в следующем: находим 10 самых жарких дней с 1976-го по 2006-й года и распределяем их по декадам. Если большинство таковых приходится на последнее десятилетие, - это говорит о возрастании температурного потолка в этой точке, если на первую декаду - о падении. Действуем по следующему алгоритму: получаем данные с помощью сервиса выборки данных, находим 10 самых жарких дней в каждой точке, в среде MATLAB распределяем результаты по декадам и наносим результаты вычисления на карту.
