|
ИСТИНА |
Войти в систему Регистрация |
ФНКЦ РР |
||
Об эффективности кэширования элементов базы данныхдипломная работа (Специалист)
- Научный руководитель: Гасанов Э.Э.
- Автор: Понкратова Ольга Юрьевна
- Тип: Специалист
- Организация, в которой проходила защита: МГУ имени М.В. Ломоносова
- Год защиты: 2013
- Аннотация: В работе Ольги Понкратовой рассматривается задача поиска идентичных объектов для случая, когда имеются два типа памяти – быстрая и более медленная, и когда имеется возможность сохранять в памяти не только элементы базы данных, но и некоторые наиболее часто встречающиеся запросы. При этом считается, что задача решается перебором, и поиск продолжается пока искомый запрос не будет найден. Понятно, что среднее время поиска будет меньше, если более часто появляющиеся запросы будут расположены в памяти раньше. В работе исследуется два случая, когда вероятности появления запросов известны и когда они не известны, но существуют в природе. В первом случае задача решена полностью, то есть показано, что все элементы в памяти должны быть упорядочены в порядке убывания вероятностей и предложен достаточно быстрый алгоритм определения, какие дополнительные запросы должны быть помещены в память, чтобы среднее время поиска было минимальным. Во втором случае если имеется возможность собрать статистику для всех запросов, то вычисляются эмпирические вероятности каждого из запросов и применяется предыдущий алгоритм. Более интересным является случай, когда запросов очень много, а мы имеем возможность ограниченную память для сбора статистик, не достаточную, чтобы собрать информацию о всех запросах. Для этого случая в работе Ольги предложен алгоритм решения нашей задачи и с помощью численных экспериментов показана его эффективность. Также получены теоретические оценки на число перестановок элементов базы данных при данном алгоритме построения оптимального заполнения памяти.
- Добавил в систему: Гасанов Эльяр Эльдарович