Модель клеточного зонда

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

Обзор [ править ]

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

Модель предназначена для доказательства нижних оценок сложности задач структуры данных .Один тип таких проблем имеет две фазы: фазу предварительной обработки и фазу запроса. Входными данными для первого этапа, этапа предварительной обработки, является набор данных, на основе которых можно построить некоторую структуру из ячеек памяти. Входными данными для второй фазы, фазы запроса, является параметр запроса. Запрос должен обратиться к структуре данных, чтобы вычислить результат; например, может быть задан запрос, чтобы определить, был ли параметр запроса включен в исходный набор входных данных. Другой тип проблем включает в себя как операции обновления, изменяющие структуру данных, так и операции запроса. Например, обновление может добавить элемент в структуру или удалить его. В обоих случаях сложность ячейки-зонда структуры данных характеризуется количеством ячеек памяти, к которым осуществляется доступ во время предварительной обработки, запроса и (если применимо) обновления.Сложность проверки ячейки — это нижняя граница временной сложности соответствующих операций на машине с произвольным доступом, где передача памяти является частью операций, учитываемых при измерении времени.

Примером такой проблемы является динамическая задача частичной суммы . ^[1]^[2]

История [ править ]

Статья Эндрю Яо 1981 года «Следует ли сортировать таблицы?» ^[3] рассматривается как внедрение модели «ячейка-зонд». Яо использовал его, чтобы предоставить минимальное количество «зондов» ячеек памяти или доступов, необходимых для определения того, существуют ли данные запроса в таблице, хранящейся в памяти. В 1989 году Фредман и Сакс инициировали исследование нижних границ зонда ячейки для задач динамической структуры данных (т. е., включая обновления и запросы) и ввели обозначение CPROBE( b ) для модели зонда ячейки, предполагая, что ячейка памяти (слово ) состоит из b бит. ^[4]

результаты Заметные

Поиск таблиц [ править ]

Их ^[3] рассматривается проблема статической структуры данных, когда необходимо построить структуру данных («таблицу») для представления набора $S$ из $n$ элементы из $1,\dots ,m$ . Параметр запроса представляет собой число $x\leq m$ и запрос должен сообщить, есть ли $x$ есть в таблице. Яо показал, что пока размер таблицы ограничен независимо от $m$ и $m$ достаточно велик, запрос должен выполнить $\lceil \log(n+1)\rceil$ зонды в худшем случае. Это показывает, что отсортированная таблица вместе с бинарным поиском запросов является оптимальной схемой.

суммы Динамические частичные

Динамическая задача частичной суммы определяет две операции Обновление $(k,v)$ , которое устанавливает значение в массиве $A$ с индексом $k$ равным $v$ , и Sum $(k),$ который возвращает сумму значений в $A$ с индексами от 0 до $k$ . Наивная реализация потребовала бы $O(1)$ время для Обновление и $O(n)$ время для Сумма . ^[5]

Вместо этого значения могут храниться в виде листьев дерева, внутренние узлы которого хранят сумму по поддереву, корнем которого является этот узел. В этой структуре обновление Требуется $O(\log n)$ время для обновления каждого узла в пути от листа до корня и Сумма аналогично требует $O(\log n)$ время, чтобы пройти дерево от листа до корня, суммируя значения всех поддеревьев слева от индекса запроса.

Улучшив результат Фредмана и Сакса, Михай Патрашку использовал модель клеточного зонда и аргумент передачи информации, чтобы показать, что задача частичных сумм требует $\Omega \left(\log n\right)$ время на операцию в худшем случае (т. е. худший из запросов и обновлений должен занимать такое время), предполагая $b=\Omega (\log n)$ бит на слово. ^[1]^[2] Далее он продемонстрировал кривую компромисса между временем обновления и временем запроса и исследовал случай, когда обновления ограничиваются небольшим количеством (около $\delta =o(b)$ биты).

Обслуживание несвязного набора (Union-Find) [ править ]

В структуре данных непересекающихся наборов структура представляет собой набор непересекающихся наборов; существует операция обновления, называемая Union, которая объединяет два набора, и операция запроса, называемая Find, которая идентифицирует набор, к которому принадлежит данный элемент. Фредман и Сакс доказали, что в модели CPROBE(log n ) любое решение этой проблемы требует $\Omega (m\alpha (m,n))$ зонды в худшем случае (даже в ожидании) на выполнение $n-1$ профсоюзы и $m\geq n$ находит. ^[4] Это показывает, что классическая структура данных, описанная в статье о структуре данных с непересекающимися множествами, является оптимальной.

Приблизительный поиск ближайшего соседа [ править ]

Задача поиска точного ближайшего соседа заключается в определении ближайшей из набора входных точек к заданной точке запроса. Часто рассматривается приближенная версия этой проблемы, поскольку многие приложения этой проблемы находятся в пространствах очень больших размерностей, а решение проблемы в больших размерностях требует экспоненциального времени или пространства по отношению к размерности. ^[6]

Чакрабарти и Регев доказали, что задача приближенного поиска ближайшего соседа на кубе Хэмминга с использованием полиномиальной памяти и $d^{O(1)}$ размер слова требует наихудшего времени запроса $\Omega \left({\frac {\log \log d}{\log \log \log d}}\right)$ . В этом доказательстве использовалась модель клеточного зонда и методы теории информации, учитывающие сложность связи .

клеточного зонда в сравнении с машинами произвольного доступа Модель

В модели ячейки-зонда ограничение диапазона значений, которые могут храниться в ячейке, имеет первостепенное значение (в противном случае можно было бы закодировать всю структуру данных в одной ячейке). Идеализированная машина произвольного доступа, используемая в качестве вычислительной модели в информатике, не накладывает ограничений на содержимое каждой ячейки (в отличие от слова RAM ). Таким образом, нижние границы зонда ячейки применимы к слову RAM, но не применимы к идеализированному RAM. Однако некоторые методы определения нижних границ ячейки-зонда могут быть перенесены в идеализированное ОЗУ с помощью алгебраического набора команд и получения аналогичных результатов нижних границ. ^[7]

Внешние ссылки [ править ]

Статья в Словаре алгоритмов и структур данных NIST о модели клеточного зонда.

Ссылки [ править ]

^ Jump up to: Перейти обратно: ^а ^б Патрашку, Михай ; Демейн, Эрик Д. (2006). «Логарифмические нижние границы в модели клеточного зонда». SIAM Journal по вычислительной технике . 35 (4): 932–963. arXiv : cs/0502041 . Бибкод : 2005cs........2041P . дои : 10.1137/s0097539705447256 . S2CID 2202874 .
^ Jump up to: Перейти обратно: ^а ^б Патрашку, Михай . «Нижние границы динамических частичных сумм» (PDF) . Проверено 9 апреля 2014 г.
^ Jump up to: Перейти обратно: ^а ^б Яо, Эндрю Чи-Чи (июль 1981 г.). «Нужно ли сортировать таблицы?» . Дж. АКМ . 28 (3): 615–628. дои : 10.1145/322261.322274 .
^ Jump up to: Перейти обратно: ^а ^б Фредман, Майкл; Сакс, Майкл (1989). «Сложность клеточного зондирования динамических структур данных». Материалы двадцать первого ежегодного симпозиума ACM по теории вычислений - STOC '89 . Том. 21. С. 345–354. дои : 10.1145/73007.73040 . ISBN 0897913078 . S2CID 13470414 .
^ Затлукал, Кевин (10 ноября 2010 г.). «Заметки о «логарифмических нижних границах в модели ячейки-зонда» » (PDF) . Проверено 9 апреля 2014 г.
^ Чакрабарти, Амит; Регев, Одед (2004). «Оптимальная нижняя граница рандомизированного клеточного зонда для приблизительного поиска ближайших соседей». 45-й ежегодный симпозиум IEEE по основам информатики . стр. 473–482. дои : 10.1109/FOCS.2004.12 . ISBN 0-7695-2228-9 . S2CID 3004976 .
^ Бен-Амрам, Амир М.; Галил, Цви (2002). «Нижние границы динамических структур данных в алгебраической оперативной памяти». Алгоритмика . 32 (3): 364–395. дои : 10.1007/s00453-001-0079-6 . S2CID 22324845 .

[patrascu2006-1] Jump up to: Перейти обратно: ^а ^б Патрашку, Михай ; Демейн, Эрик Д. (2006). «Логарифмические нижние границы в модели клеточного зонда». SIAM Journal по вычислительной технике . 35 (4): 932–963. arXiv : cs/0502041 . Бибкод : 2005cs........2041P . дои : 10.1137/s0097539705447256 . S2CID 2202874 .

[patrascu_morin-2] Jump up to: Перейти обратно: ^а ^б Патрашку, Михай . «Нижние границы динамических частичных сумм» (PDF) . Проверено 9 апреля 2014 г.

[yao81-3] Jump up to: Перейти обратно: ^а ^б Яо, Эндрю Чи-Чи (июль 1981 г.). «Нужно ли сортировать таблицы?» . Дж. АКМ . 28 (3): 615–628. дои : 10.1145/322261.322274 .

[FS89-4] Jump up to: Перейти обратно: ^а ^б Фредман, Майкл; Сакс, Майкл (1989). «Сложность клеточного зондирования динамических структур данных». Материалы двадцать первого ежегодного симпозиума ACM по теории вычислений - STOC '89 . Том. 21. С. 345–354. дои : 10.1145/73007.73040 . ISBN 0897913078 . S2CID 13470414 .

[zatloukal2010-5] Затлукал, Кевин (10 ноября 2010 г.). «Заметки о «логарифмических нижних границах в модели ячейки-зонда» » (PDF) . Проверено 9 апреля 2014 г.

[chakrabarti2004-6] Чакрабарти, Амит; Регев, Одед (2004). «Оптимальная нижняя граница рандомизированного клеточного зонда для приблизительного поиска ближайших соседей». 45-й ежегодный симпозиум IEEE по основам информатики . стр. 473–482. дои : 10.1109/FOCS.2004.12 . ISBN 0-7695-2228-9 . S2CID 3004976 .

[7] Бен-Амрам, Амир М.; Галил, Цви (2002). «Нижние границы динамических структур данных в алгебраической оперативной памяти». Алгоритмика . 32 (3): 364–395. дои : 10.1007/s00453-001-0079-6 . S2CID 22324845 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]