Модель клетки-зонда

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

Обзор

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

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

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

История

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

Формальное определение

Учитывая набор данных, создайте структуру, состоящую из ячеек памяти, каждая из которых может хранить биты. Затем, когда задан элемент запроса, определите, правильно ли он, обратившись к ячейкам памяти. Такой алгоритм называется алгоритмом проверки ошибок, использующим ячейки с размером слова . ^[4] ${\ displaystyle S}$ ${\ displaystyle c}$ ${\ displaystyle w}$ ${\ displaystyle s}$ ${\ displaystyle s \ in S}$ ${\ displaystyle 1- \ varepsilon}$ ${\ displaystyle t}$ ${\ Displaystyle \ varepsilon}$ ${\ displaystyle t}$ ${\ displaystyle c}$ ${\ displaystyle w}$

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

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

Задача динамической частичной суммы определяет две операции Update $(k, v),$ которые концептуально задают значение в массиве $A$ по индексу $k$ равным $v$ , и Sum $($ $k$ $),$ которая возвращает сумму значений в $A$ по индексам.От 0 до $k$ . Такая реализация потребует времени для обновления и времени для Sum . ^[5] ${\ displaystyle O (1)}$ ${\ Displaystyle О (п)}$

Вместо этого, если значения хранятся в виде листьев в дереве, внутренние узлы которого хранят значения поддерева с корнем в этом узле. В этой структуре Update требуется время для обновления каждого узла в пути от листа к корню, а Sum аналогичным образом требует времени для обхода дерева от листа к корню, суммируя значения всех поддеревьев слева от индекса запроса. ${\ Displaystyle О (\ журнал п)}$ ${\ Displaystyle О (\ журнал п)}$

Михай Пэтрашку использовал модель клеточного зонда и аргумент передачи информации, чтобы показать, что проблема частичных сумм требует времени на операцию. ^[1]^[2] ${\ Displaystyle \ Omega \ влево (\ журнал п \ вправо)}$

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

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

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

внешние ссылки

Словарь алгоритмов и структур данных NIST, посвященный модели ячейки-зонда

использованная литература

^ ^a ^b Патрашку, Михай ; Демейн, Эрик Д. (2006). «Логарифмические нижние границы в модели клетки-зонда». SIAM Journal on Computing . 35 (4): 932–963. arXiv : cs / 0502041 . Bibcode : 2005cs ........ 2041P . DOI : 10.1137 / s0097539705447256 .
^ ^a ^b Патрашку, Михай . «Нижние границы для динамических частичных сумм» (PDF) . Проверено 9 апреля 2014 года .
↑ Яо, Эндрю Чи-Чи (июль 1981). «Следует ли сортировать таблицы?». J. ACM . 28 (3): 615–628. DOI : 10.1145 / 322261.322274 .
^ а б Чакрабарти, Амит; Регев, Одед (2004). «Оптимальная рандомизированная нижняя граница зонда ячейки для приблизительного поиска ближайшего соседа». Материалы 45-го ежегодного симпозиума IEEE по основам информатики : 473–482.
^ Zatloukal, Кевин (10 ноября 2010). «Заметка о„логарифмических Нижних границах в сотовом Probe модели “ » (PDF) . Проверено 9 апреля 2014 года .

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

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

[yao81-3] Яо, Эндрю Чи-Чи (июль 1981). «Следует ли сортировать таблицы?». J. ACM . 28 (3): 615–628. DOI : 10.1145 / 322261.322274 .

[chakrabarti2004-4] а б Чакрабарти, Амит; Регев, Одед (2004). «Оптимальная рандомизированная нижняя граница зонда ячейки для приблизительного поиска ближайшего соседа». Материалы 45-го ежегодного симпозиума IEEE по основам информатики : 473–482.

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

[1]