О сложности интервального поиска на булевом кубе

1. Общая характеристика работы.

Актуальность темы

В связи с постоянным расширением области компьютерных технологий, одним из актуальных направлений дискретной математики и математической кибернетики являются проблемы оптимизации, хранения и поиска информации.

Все возрастающий поток информационно-вычислительных работ требует дальнейшего совершенствования методов проектирования и разработки баз данных и поисковых систем. Решение этих задач невозможно без тщательного анализа накопленного опыта, построения математической модели баз данных и информационных систем. Исследование математической модели помогает решать задачи, позволяющие повысить эффективность поиска в базах данных. В работах [5, 22, 29, 30, 39, 53, 13] вводились различные формализации информационно-поисковых систем. В данной работе используется информационно-графовая модель, предложенная в [13]. Такая модель данных может найти применение при проектировании физической организации баз данных, а также при разработке интегральных схем, обеспечивающих аппаратную реализацию быстрых алгоритмов поиска.

В данной работе используется такое понимание задачи поиска, при котором предполагается многократное обращение к одним и тем же данным, но, возможно, каждый раз с новыми требованиями к искомым объектам, то есть с разными запросами на поиск. Такие задачи обычно возникают в системах, использующих базы данных. Многократное использование порождает особую проблему — проблему специальной организации данных, направленной на последующее ускорение поиска. Процесс такой специальной организации данных может занимать много времени, что потом окупается в результате многократности поиска. Ценность алгоритма поиска в таком случае определяется варьированием запроса на поиск, например, показателем может служить среднее время поиска на запросе. Классификацию задач поиска на однократные и многократные можно найти в работах [51, 27, 13].

Пусть задано некоторое упорядоченное множество X. На множестве Хп определим отношение частичного порядка следующим образом: если а, Ь € Хп, а = (а1,., ап), Ь = {Ъ ,.,?>"), то будем писать, а ¦< Ь («а предшествует Ь»), если а< < для любого г = 1,., п. Если V С Хп, u, w € Хп, и X w, то задача интервального поиска в Хп заключается в перечислении всех тех элементов у из V, для которых верно и -<у ;

Интервальный поиск имеет очевидное приложение к системам баз данных. В базе данных, содержащей записи о служащих некоторой компании, каждая запись имеет несколько атрибутов, таких, как возраст, жалование и т. д., и может рассматриваться как точка в n-мерном пространстве, в котором каждый атрибут соответствует измерению, а число измерений пространства п равно числу атрибутов. Типичная задача интервального поиска для двух измерений заключается в выявлении всех служащих, чьи возраст и жалованье находятся в заданных интервалах. Это пример взят из [22]. Другой пример можно найти у Д. Кнута [21]. Он рассматривал базу данных городов США с координатами в виде широты и долготы. К такой базе естественен вопрос о перечислении всех городов, попадающих в некоторой прямоугольник-запрос. Это типичная двумерная задача интервального поиска. Подобные задачи возникают также в статистике [48] и автоматизации проектирования [45].

Исследованию задачи интервального поиска в Rn (в другом переводе с английского — регионального поиска) посвящено большое количество работ [22, 27, 33, 35, 36, 37, 38, 41, 42, 43, 44, 46, 47, 49, 50, 52, 55]. Приведем результаты некоторых из них. Алгоритм решения двумерной задачи интервального поиска путем сведения к решению четырех двумерных задач о доминировании можно найти в [22, 27]. Бентли в [33] предложил метод многомерного двоичного дерева (k-D-дерева), исходя из того, что бинарное дерево для одномерной задачи дает хороший результат. Этот метод имеет линейные затраты по памяти, но Ли и Вонг [46] показали, что в худшем случае этот алгоритм дает плохие результаты, так двумерная задача решается за время 0(Vk). Здесь и далее, к равно мощности библиотеки, а оценки приводятся без времени перечисления ответа. В работе [34] Бентли предложил метод прямого доступа, который решает задачу за время 0(log2 А:), но требует затрат по памяти порядка А:3 для двумерной задачи. Гасанов в работе [18] для n-мерной задачи предложил алгоритм, который при затратах памяти порядка А-2″ -1 требует в среднем константное время, а в худшем случае решает задачу за время 0(log2 к). Чтобы уменьшить требуемую память в работе [36] Бентли и Маурером был предложен многоэтапный метод прямого доступа. Он позволяет снижать порядок требуемой памяти, но при этом возрастает константа при логарифме в оценке времени. В работе Гасанова и Кузнецовой [20] предлагается модификация алгоритма Бентли-Маурера, решающего двумерную задачу интервального поиска. Эта модификация позволяет снизить исходное логарифмическое среднее время поиска до константного при сохранении логарифмического времени поиска в худшем случае. При этом этот алгоритм зависит от параметра, при вариации которого объем памяти, необходимый алгоритму, изменяется от 0(к3) до О (к log к), при этом среднее время поиска (без учета времени на перечисление ответа) изменяется от 0(1) до О (log к). В частности, для любого е > 0 при объеме памяти 0(к1+е) достигается среднее время поиска 0(1). С помощью метода дерева интервалов (или дерева регионов) Бентли и Шеймос [37] получили оценку времени поиска.

О (log" А-) при затратах памяти О (Alog" -1 к), где п — размерность задачи интервального поиска. Уиллард [55] и Люкер [49] независимо предложили модификацию дерева интервалов, которая позволила снизить время поиска до O (log21 к) при тех же затратах памяти. Чазелле в [42] для двумерной задачи смог снизить затраты памяти до О (к log2 к/ log2 log2 к), но при этом возросла константа при логарифме в оценке времени. Во всех этих работах оценивается время поиска в худшем случае. И только Болоур описал метод хеширования [41], который он использовал вместо поиска по древовидным структурам в задаче интервального поиска. Применение этого метода позволило получить довольно быстрые в среднем решения задачи интервального поиска при условии, что область запросов находится в заранее определенных границах.

Однако, результаты, полученные для интервального поиска в евклидовом пространстве, нельзя использовать для задачи интервального поиска на булевом кубе Решение задачи интервального поиска на булевом кубе в рамках информационно-графовой модели предполагает сведение ее к задаче синтеза схемы (называемой информационным графом), реализующей систему элементарных конъюнкций. Поэтому методы исследования задачи интервального поиска на булевом кубе гораздо ближе к методам, применяемым при реализации системы к конъюнкций ранга п. Задача реализации произвольной системы к элементарных конъюнкций ранга п контактными схемами была впервые рассмотрена К. Шенноном [54] в 1949 г. Для данной задачи (к = 2″) была построена схема в виде контактного дерева с числом контактов 2″ +1 — 2. В 1958 г. О. Б. Лупанов [23] предложил недревовидную конструкцию с числом контактов, асимтотически равным 2″ = к. Задача построения схемы для системы из к конъюнкций, где к < 2″, впервые была рассмотрена Э. И. Нечипоруком [25, 26] в 1969 г., для к 2п/п им был получен асимптотически оптимальный метод. Дальнейшее продвижение в решении этой задачи было получено в 1975 г. Н. П. Редькиным [28]. Им были получены следующие факты: 1) число контактов в схеме, реализующей к конъюнкций не превосходит minr=i."(2]п/г[-(2г + к — 2)) — 2) если log2 к = б (п) и log2 п = 6(log2 к), то существует схема с асимптотически оптимальным числом контактов, равным кп/ log2 к. А. Е. Андреевым [1, 2, 3, 4] и И. А. Вихлянцевым [11, 12] в 1989 г. было предложено асимптотически оптимальное решение задачи реализации системы к элементарных конъюнкций при условии log2 к ~ п с числом контактов, асимптотически равным к.

В этих работах при решении задачи реализации системы конъюнкций в качестве меры сложности контактной схемы рассматривалось число контактов в ней. Сложность же информационных графов вводится принципиально иным образом и характеризует среднее время поиска соответствующего алгоритма. А поскольку в современных условиях объемы информационных массивов, обрабатываемых электронными устройствами, неуклонно растут, то проблема сокращения времени поиска приобретает особую актуальность.

Таким образом, разработка новых способов хранения и поиска информации, а также способов оценки их средней временной сложности, представляется теоретически и практически интересной.

Цель работы. Рассматривается задача интервального поиска, которая состоит в следующем. Есть некоторое подмножество п-мерного куба, наг зываемое библиотекой. Запрос задает некоторый интервал (подкуб) булева куба. Необходимо перечислить все наборы из библиотеки, попавшие в данный интервал. Целью работы является исследование средней временной сложности задачи интервального поиска при различных ограничениях на структуру данных и базовое множество функций, то есть множество функций, разрешенных к использованию.

Методы исследования. В работе используются методы дискретного анализа, в частности комбинаторики и теории графов, а также методы теории вероятностей, математического анализа, вариационного исчисления.

Научная новизна. Исследования, проведенные в данной работе, направлены на изучение средней временной сложности алгоритмов поиска. Они используют в качестве своей основы информационно-графовую модель данных, предложенную Э. Э. Гасановым в работе [13]. Работы [15, 16, 17, 18, 19, 20] содержат результаты исследований интервального поиска на прямой и на плоскоститакже в работе [13] одна глава посвящена исследованию задачи интервального поиска в п-мерном евклидовом пространстве. Но методы и алгоритмы, предложенные в этих работах, ни коим образом не могут быть использованы для задачи интервального поиска на булевом кубе. В работе [14] введено понятие задачи интервального поиска на булевом кубе и исследовано поведение функции Шеннона в классе древовидных схем в случае, когда нет ограничений на базовое множество функций, то есть разрешается использовать любую булеву функцию, и каждая функция вычисляется со сложностью, равной 1. К сожалению, в этом случае задача вырождается, и оценки носят почти тривиальный характер.

В данной работе впервые проведено глубокое исследование задачи интервального поиска на булевом кубе при реальных ограничениях на базовое множество (рассматривались переменные, элементарные конъюнкции и взвешенные элементарные конъюнкции).

В работе впервые получена асимптотика сложности задачи интервального поиска на булевом кубе в классе сбалансированных древовидных схем для данных базовых множеств. Для множества взвешенных элементарных конъюнкций, то есть в случае, когда каждая элементарная конъюнкция имеет свой вес, зависящий от ее длины, получен критерий того, когда данное множество предпочтительней, чем базовое множество переменных.

Впервые получено асимптотическое поведение функции Шеннона сложности задачи интервального поиска на булевом кубе в классе древовидных схем.

Предложены индуктивные способы построения решающих деревьев. Даны средние оценки временной сложности полученных деревьев.

Практическая ценность. Результаты работы могут быть использованы при проектировании баз данных и информационных систем, при организации поиска и хранения информации.

Основные результаты диссертации, выносимые на защиту.

В работе исследуется следующая задача информационного поиска. Имеется некоторое подмножество V п-мерного булева куба В", называемое библиотекой. На булевом кубе берется произвольный интервал (и, го), где и = (щ,. ., и&bdquo-), ю =. ., ш&bdquo-) и и Ч и), то есть щ < и) х * = 1,., п. Требуется определить все такие элементы у € V, у = (у,. ., уп), называемые записями, для которых выполнено и Ч у Ч ю.

Приведем интерпретацию данной задачи.

• Некто имеет название ценной для него книги, но некоторые буквы в названии от времени стерлись. В городской библиотеке требуется определить, есть ли книги с подходящим названием, и, если есть, выдать их читателю.

• Генетическую информацию можно закодировать буквами, так как она определяется всего четырьмя видами органических молекул. В геноме есть последовательности, называемые консервативными, одинаковые для всех людей и остающиеся неизменными на протяжении многих поколений. Так, например, в настоящее время, при помощи анализа генной информации можно определить пол, некоторые генетически обусловленные заболевания, особенности внешности. Пусть имеется некоторый набор признаков человека, жившего в прошлом. Требуется провести генетическую экпертизу останков и понять, могли ли они принадлежать интересующей нас личности. [31].

• Допустим, мы имеем частично разгаданный кроссворд, в котором все слова имеют одинаковую длину. Отгадываем слово, в котором известны не все буквы. Требуется найти в словаре такие слова, которые потенциально могут быть разгадываемым словом.

Задачу можно решать, если на каждом шаге алгоритма проверять условие и] < у^ < ] € {1,., п} для фиксированного набора компонент записи.

Если множество проверяемых на данном шаге компонент зависит от результатов проверок на предыдущих шагах, то классу таких алгоритмов удобно сопоставить древовидные информационные схемы.

Если же номера проверяемых на одном шаге компонент одинаковы для всех записей, то мы приходим к классу сбалансированных древовидных схем.

Во всех рассматриваемых классах алгоритмов оценивалась средняя временная сложность работы алгоритма. Алгоритмы, описываемые в работе представлены схемами. Эти схемы физически можно реализовать в кремнии в виде чипов. В этом случае, исследуемые меры сложности будут описывать степень нагреваемости чипа в процессе работы электронного устройства.

В работе получены следующие результаты.

1. Получено асимптотическое поведение среднего времени поиска в классе сбалансированных древовидных схем на последовательностях натуральных чисел кх в предположении, что мощность баз данных.

Показано, что для разных последовательностей асимптотическое поведение может быть разным. Полностью описан класс возможных асимптотических поведений. Эти исследования проводились для базисов элементарных конъюнкций, переменных и взвешенных элементарных конъюнкций.

2. Получены оценки функции сложности Шеннона в классе древовидных схем, причем для некоторых значений параметров эти оценки описывают порядок функции Шеннона, а для других значений параметров дают асимптотику логарифма ее сложности.

3. Предложены три индуктивных алгоритма автоматического построения информационных деревьев над базисом переменных. Показана несравнимость этих алгоритмов. Показана неустойчивость алгоритмов к выбору параметра. Получена средняя сложность для двух алгоритмов.

Апробация работы. Результаты настоящей работы докладывались на XIII Международной конференции по проблемам теоретической кибернетики (Казань, 2002 г.), на XIV Международной конференции по проблемам теоретической кибернетики (Пенза, 2005 г.), а также на семинарах механико-математического факультета МГУ им. М. В. Ломоносова: на семинаре «Математические вопросы кибернетики» под руководством академика РАН, проф. д. ф-м.н. О. Б. Лупанова (2005г.), на семинаре «Теория автоматов» под руководством академика, проф., д. ф-м.н. В. Б. Кудрявцева (2005г.), на семинаре «Вопросы сложности алгоритмов поиска» под руководством проф., д. ф-м.н. Э. Э. Гасанова (2002;2004гг.), на семинаре «Моделирование сложных систем и процессов» под руководством к. ф-м.н. А. С. Строгалова (2002г.).

Публикации. По теме диссертации опубликованы 6 печатных работ.

Структура и объем работы. Диссертация состоит из введения и трех глав. Объем диссертации 102 стр.

Список литературы

содержит 57 наименований.

1. Андреев А. Е. О синтезе самокорректирующихся управляющих систем. Доклады АН СССР, 1984, т.277, N3, стр.521−525.

2. Андреев А. Е. Универсальный принцип самокорректирования. Математический сборник, 1985, т.127(169), N6, стр.147−172.

3. Андреев А. Е. О синтезе топологических функциональных сетей. Препринт 1.259 ИПМех АН СССР и МГУ им. Ломоносова, 1985, 67 стр.

4. Андреев А. Е. Метод бесповторной редукции синтеза самокорректирующихся схем. Доклады АН СССР, 1985, том 283, N2, стр. 265−269.

5. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. — М.: Мир, 1979.

6. Блайвас Т. Д. Решение задачи интервального поиска на булевом кубе. Проблемы теоретической кибернетики. Тезисы докладов XIII Международной конференции, Часть I, стр. 22.

7. Блайвас Т. Д. Оптимальное решение задачи интервального поиска на булевом кубе в классе сбалансированных древовидных схем. Интеллектуальные системы, том 7, вып. 1−4, стр. 223−245.

8. Блайвас Т. Д. Алгоритм с жестким порядком проверок построения решающих деревьев для задачи интервального поиска на булевом кубе. Проблемы теоретической кибернетики. Тезисы докладов XIV Международной конференции, стр. 17.

9. Блайвас Т. Д. Сложность поиска по маске для алгоритма с жестким порядком проверок. Интеллектуальные системы, в печати.

10. Блайвас Т. Д. Функция Шеннона сложности интервального поиска на булевом кубе в классе деревьев. Дискретная математика, в печати.

11. Вихлянцев И. А. О реализации систем конъюнкций контактными схемами. Дискретная математика, 1989, том 1, вып.4, стр.3−11.

12. Вихлянцев И. А. О самокорректировании контактных разделительных схемам. Дискретная математика, 1990, том2, вып.1, стр.80−86.

13. Гасанов Э. Э., Кудрявцев В. Б. Теория хранения и поиска информации. Москва, ФИЗМАТЛИТ, 2002.

14. Гасанов Э. Э. О сложности информационного поиска, канд. дисс. Москва, 1985.

15. Гасанов Э. Э. Некоторые задачи поиска, допускающие мгновенное в среднем решение. Фундаментальная и прикладная математика (1995) 1, JV* 1, 123−146.

16. Гасанов Э. Э. Об одномерной задаче интервального поиска. Дискретная математика (1995) 7, № 2, 40−60.

17. Гасанов Э. Э. Мгновенно решаемые задачи поиска. Дискретная математика (1996) 8, 3, 119−134.

18. Гасанов Э. Э., Кузнецова И. В. Оценки функциональной сложности двумерной задачи интервального поиска. Тезисы докладов XII Международной конференции «Проблемы теоретической кибернетики», Нижний Новгород, (17−22 мая 1999 г.), — 47.

19. Гасанов Э. Э., Кузнецова И. В. О функциональной сложности двумерной задачи интервального поиска. Дискретная математика (2002) 14, № 1.

20. Кнут Д. Искусство программирования для ЭВМ. том 3. Сортировка и поиск. — М.: Мир, 1979.

21. Ли Д., Препарата Ф. Вычислительная геометрия. Обзор. // Кибернетический сборник, 1987, том 24, стр.5−96.

22. Лупанов О. Б. О синтезе контактных схем. Доклады АН СССР, 1958, том 119, N1, стр.23−26.

23. Мартин Дж. Организация баз данных в вычислительных системах. — М.: Мир, 1980.

24. Нечипорук Э. И. О топологических принципах самокорректирования. Проблемы кибернетики, 1969, вып.21, стр.5−102.

25. Нечипорук Э. И. О топологических принципах самокорректирования. Доклады АН СССР, 1968, том 179, N4, стр.786−789.

26. Препарата Ф., Шеймос М. Вычислительная геометрия: Введение. — М.: Мир, 1989.

27. Редькян Н. П. О реализации систем конъюнкций контактными схемами. Проблемы кибернетики, 1975, вып. ЗО, стр.263−267.

28. Решетников В. Н. Алгебраическая теория информационного поиска // Программирование. 1979, N3, сгр.68−74.

29. Селтон Г. Автоматическая обработка, хранение и поиск информации. — М.: Советское радио, 1973.

30. Химия и жизнь — XXI век. № 4, 1998 г, Геном человека, стр. 27−30.

31. Яблонский С. В., Лупанов О. Б. Дискретная математика и математические вопросы кибернетики, том 1, Москва, Наука, 1974.

32. Bentley J. L. Multidimensional binary search trees used for associative searching. Commun. Ass. Comput. Mach. (Sept. 1975), 18 509−517.

33. Bentley J. L. Decomposable searching problems, Info. Proc. Lett. (1979), 8 244−251.

34. Bentley J. L., Friedman J. H. Data structures for range searching. Comput. Surveys (1979), 11 397−409.

35. Bentley J. L., Maurer H. A. Efficient worst-case data structures for range searching. Acta Inform. (1980), 13 155−168.

36. Bentley J. L., Shamos M. I. A problem in multivariate statistics: Algorithms, data structure and applications. Proc. 15th Allerton Conf. Commun., Contr., Comput. (1977), 193−201.

37. Bentley J. L., Stanat D. F. Analysis of range searching in quad trees. Inform. Processing Lett. (1975), 3 170−173.

38. Bentley J.L., Saxe J.B. Decomposable searching problems. I. Static-to-dynamic transformation. J. Algorithms, 1980, 1, P.301−358.

39. Blaivas T. The asymptotic behaviour of the complexity of the interval search on the Boolean cube in the class of balanced trees. Discrete Mathematics and Applications. Volume 14, No. 6, pp. 579−592.

40. Bolour A. Optimal retrieval algorithms for small region queries. SI AM J. Comput. (1981) 10, 721−741.

41. Chazelle В. M. Filtering search: a new approach to query-answering. Proc. 24th IEEE Annu. Symp. Found. Comput. Sci. (Nov. 1983), 122−132.

42. Fredman M. L. A lower bound of the complexity of ortogonal range queries. J. ACM. (1981) 28, 696−705.

43. Gabow H. N., Bentley J. L., Tarjan R. E. Scaling and related techniques for geometry problems. Proc. 16th ACM Annu. Symp. Theory Comput. (Apr. 1984) 135−143.

44. Lauter U. 4-dimensional binary search trees as a means to speed up associative searches in design verification of integrated circuits. Jour, of Design Automation and Fault Tolerant Computing, 2 (3), 241−247 (July 1978).

45. Lee D. T., Wong C. K. Worst case analysis for region and partial region searches in multidimensional binary search trees and balansed quad trees. Acta Informatica (1977) 9 23−29.

46. Lee D. T., Wong C. K. Quintari trees: A file structures for multidimensional database system. ACM Trans. Database Syst. (Sept. 1980) 1, JY* 1, 339−353.

47. Loftsgaarden D. O., Queensberry C. P. A nonparametric density function. Ann. Math. Stat. (1965) 36, 1049−1051.

48. Lueker G. S. A data structure for ortogonal range queries. Processing of the 19th Annual IEEE Symposium on Foundations of Computer Science. (1978), 28−34.

49. Lueker G. S., Willard D. E. A data structure for dynamic range queries. Inform. Processing Lett. (Dec. 1982) 15, № 5, 209−213.

50. Preparata F.P., Shamos M.J. Computational Geometry. SpringerVerlag. New-York, 1985.

51. Saxe J. B. On the number of range queries in ?-space. Discrete Applied Mathematics (1979) 1, 217−225.

52. Saxe J.B., Bentley J.L. Transforming static data structures into dynamic structures. Proc 20th IEEE Annu. Symp. Found. Comput. Sci., oct. 1980, P.148−168.

53. Shannon C.E. The synthesis of two-terminal switching circuits. Bell SysLTechn. J., 1949, v.28, N1, P.59−98.

54. Willard D. E. Predicate-oriented database search algorithms. Ph. D. dissertation, Harvard Univ., Cambridge, MA, 1978.