43090
ОБЛАКО ТЕГОВ ДЛЯ ИНФОРМАЦИОННОЙ ФИЛЬТРАЦИИ ДАННЫХ
Курсовая
Информатика, кибернетика и программирование
Для параллельных вычислений особенно важен вопрос оценки эффективности. В случае визуализации больших объемов данных, этот вопрос связан с тем, в таких случаях для сокращения времени работы и объема пересылок лучше применять параллельный рендеринг, а в каких фильтрацию данных
Русский
2015-01-19
33.5 KB
9 чел.
ОБЛАКО ТЕГОВ ДЛЯ ИНФОРМАЦИОННОЙ ФИЛЬТРАЦИИ ДАННЫХ
Д.В. Манаков, Р.О. Судариков
ИММ УрО РАН, УрФУ, Екатеринбург
Параллельная фильтрация данных наряду с параллельным рендерингом активно применяется для сокращения объема визуализируемых данных.
Для параллельных вычислений особенно важен вопрос оценки эффективности. В случае визуализации больших объемов данных, этот вопрос связан с тем, в таких случаях для сокращения времени работы и объема пересылок лучше применять параллельный рендеринг, а в каких фильтрацию данных. В результате рендеринга генерируются растровые данные, что в значительной степени ограничивает методы взаимодействия с визуализируемыми объектами. Уменьшение объема данных помогает ускорить работу при обеспечении взаимодействия с вычислительной моделью.
В процессе фильтрации необходим быстрый выбор интересующей информации. Для решения этой задачи можно использовать различные подходы, в частности, реструктуризацию данных, например, по k-дереву, и возможность поэлементной обработки в модели потока данных. Очевидно, что с точки зрения программной реализации в таких случаях удобно применять ассоциативные массивы.
В этой работе для решения задачи фильтрации предложена метафора визуализации и взаимодействия контекстное облако тегов, которое предназначено для эффективной интерпретации результатов поиска в Интернете. Взаимодействие с выбранными и отфильтрованными данными реализовано через обращение к ассоциативным массивам.
Правильное решение проблемы эффективности возможно только на основе формальной модели. “В огромном числе случаев при попытке построить модель какого-либо объекта либо не возможно прямо указать фундаментальные законы, или вариационные принципы, которым он подчиняется. Одним из плодотворных подходов к такого рода объектам является использование аналогий с уже изученными явлениями.” [1]
Визуализация, как объект изучения, несомненно, плохо формализуема, но необходимость, прежде всего, оценки эффективности диктует построении «полумодели» или оснований теории визуализации, начиная с декларативных определений и поиска аналогий.
Одна из возможных аналогий это оптимальное управление, то есть постановка каких-то минимаксных задач для визуализации. Так фильтрацию можно рассмотреть, как интерактивный процесс, целью которого является получение максимума информации с минимальными затратами. Или в общем случае, как нахождение минимума когнитивного расстояния, которое измеряет усилия пользователя, необходимые для преобразования действий по вводу данных и представлений выводимой информации в операции и объекты прикладной области. Для поиска применяется алгоритм MapReduce, если вид отображения выбрать аналогичный этому алгоритму, то возможно когнитивное расстояние уменьшится.
Возможность применения топологического анализа в визуализации продемонстрировано в работе [2], где облако точек отображает трассу программы.
Нами рассматривается возможность применения теории грубых множеств для задач визуализации и обработки информации. Теорию грубых множеств можно рассматривать как одно из развитий идеи Фреге о неопределенности, в частности, в данном подходе нечеткость определяется через границу множества, а не через частичную принадлежность, как в теории нечетких множеств. Если знаний о множестве не достаточно для его строгого определения, то граница не равна нулю, иначе стандартное (четкое) множество. Граница, как топологическое понятие разность между замыканием и внутренностью множества. Важное понятие данной теории гранулярность. Множество представляется в виде совокупности элементарных знаний, например, для визуализации - это графические примитивы.
Задание функций принадлежности для множества можно рассматривать, как способ упорядочения этого множества. Так же очевидно параллель c ассоциативными массивами. Наибольший интерес представляет рассмотрение функций принадлежности грубых множеств, как относительную метрику оценки эффективности. В общем случае, можно рассмотреть нечеткое множество X, где для каждого элемента множества (объекта) задана функция принадлежности X(x)[0,1], которая задает степень принадлежности элемента множеству, в отличие от классической теории, когда элемент точно принадлежит множеству. В частности облако тегов можно рассматривать, как множество слов, которое упорядочивает функция принадлежности, и отражает частотные характеристики.
Вопрос об определении алгоритма по существу равносилен вопросу об определении вычислимой функции. Можно сформулировать теорему об эквивалентности вычислимой функции и функция принадлежности.
Метафора контекстного облака тегов является расширением стандартного облака тегов с заданием нескольких функций принадлежности для множества, включающего результаты поиска. Результаты поиска (нечеткое множество X) представим в виде массива ассоциативных массивов, где центральный элемент массива строка поиска. Формально задаются две функции принадлежности: ширина контекста (количество слов поиска слева и справа от строки поиска) и частота встречаемости слова, зависящая от типа документа с расширением pdf, doc, html соответственно отображается градацией цвета R,G,B. Результаты поиска также включают название документа и гиперссылку, которые выделяются через взаимодействие с конкретным словом (ключом).
Программа реализована на языке Ruby и по архитектуре соответствует облачным вычислениям. Модуль посредник перехватывает результаты поиска через Google API и реструктуризирует данные в виде ассоциативных массивов. В результате взаимодействие в клиентской части строится на основе хеширования, то есть практически без пересчета. Предполагается интеграция разработанной системы с сервером распределенных вычислений Hadoop.
Литература
1. Самарский А.А., Михайлов А.П. Математическое моделирование: Идеи. Методы. Примеры. - М.: Физматлит, 1993, - 320 с.
2. Choudhury, A.N.M.I.; Bei Wang; Rosen, P.; Pascucci, V. Topological analysis and visualization of cyclical behavior in memory reference traces // Pacific Visualization Symposium (PacificVis), 2012 IEEE,vol., no., pp.9-16, Feb. 28 2012-March 2 2012.
Работа выполнена при поддержке программы Президиума РАН № 18 "Алгоритмы и математическое обеспечение для вычислительных систем сверхвысокой производительности", а также проекта 12-П-1-1034 УрО РАН.
А также другие работы, которые могут Вас заинтересовать | |||
13012. | Лабораторні роботи з дисципліни «Основи геоінформатики» | 2.26 MB | |
Лабораторні роботи з дисципліни Основи геоінформатики ЛАБОРАТОРНА РОБОТА №1 Тема: Просторові та атрибутивні дані Мета роботи: ознайомитися зі структурою даних геоінформаційних систем вивчити характеристики кількох різних структур. Підготовка до роб... | |||
13013. | Принципы и особенности построения средств отображения информации, построенные на различных физических принципах | 989 KB | |
План 1.5.1. Принципы и особенности построения средств отображения информации построенные на различных физических принципах. 1.5.2. Системы отображения информации на базе ЭЛТ. 1.5.1. Принципы и особенности построения средств отображения информации построенные на ра... | |||
13014. | Формат сохранения картографической информации и алгоритм работы программы-конвертора | 134.5 KB | |
В задачах цифровой картографии очень важное значение имеет выбор формата представления информации основы БКД АГК. К географическим базам данных манипулирующим большими массивами информации и принадлежащим системам работающим в режиме реального времени предъявляют... | |||
13015. | Алгоритм визуализации картографической информации. Методы формирования картографических срезов | 83 KB | |
Для получения картографического изображения некоторой прямоугольной области земной поверхности задаваемой географическими координатами на экране устройства отображения предлагается метод суть которого состоит в следующем: Сначала задаются элементы содержания в ... | |||
13016. | ОРГАНІЗАЦІЯ ОБЛІКУ ВИТРАТ ТА МЕТОДИКА АНАЛІЗУ СОБІВАРТОСТІ ПОСЛУГ | 757 KB | |
Метою дипломної роботи є вироблення теоретико-методичних положень щодо формування системи обліку та управління виробничими витратами. А також удосконалення методики калькулювання собівартості, що дасть змогу спростити процедуру обліку операційних витрат виробництва. | |||
13017. | Принципы построения баз картографических данных в агротехнических геоинформационных комплексах | 425 KB | |
План 6.1. Модель графических данных. 6.2. Логическая и физическая организация баз картографических данных 6.1. Модель графических данных Процесс проектирования БГД представляет собой сложный процесс определения отображения: Предметная область Схема вну... | |||
13018. | Понятие агротехнических геоинформационных комплексов | 195.5 KB | |
Введение. Понятие агротехнических геоинформационных комплексов. Данный курс лекций является обобщением результатов исследований и разработок проведённых под руководством автора и относится к области построения интерактивных геоинформационных комплексов опер... | |||
13019. | Исследованию по факту пожара в МБОУ «Майминская СОШ №2» | 780.09 KB | |
Анализ особенностей осмотра места происшествия связанного с пожаром, изучение и анализ документов, составляемых в связи с пожарами – заключения технического специалиста, постановления об отказе в возбуждении уголовного дела, исследование практики в этой области. | |||
13020. | Проектирование АГК как сложной человеко-машинной системы | 185.5 KB | |
Проектирование АГК как сложной человекомашинной системы. Системный подход В.М.Глушкова является достаточно хорошей основой для создания компонентов АГК работающих в статике. Однако основной чертой таких комплексов является их работа в динамике. Они должны успевать... | |||