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

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

Обзор

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

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

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

История

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

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

Учитывая набор данных ${ 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}$. ^[4]

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

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

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

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

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

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

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

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

внешняя ссылка

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

Рекомендации