Модель клетки-зонда - Cell-probe model
В информатике модель ячейки-зонда - это модель вычислений, аналогичная машине с произвольным доступом , за исключением того, что все операции бесплатны, за исключением доступа к памяти. Эта модель полезна для доказательства нижних оценок алгоритмов для задач структуры данных.
Обзор
Модель клеточно-зонд является незначительной модификацией машины с произвольным доступом модели, сам по себе незначительной модификации машины счетчика модели , в которой вычислительные затратах только присвоенная доступ единиц памяти называется клетки.
В этой модели вычисления представлены как задача запроса набора ячеек памяти. Проблема состоит из двух этапов: этапа предварительной обработки и этапа запроса. Входными данными на первом этапе, этапе предварительной обработки, является набор данных, из которых можно построить некоторую структуру из ячеек памяти. Входными данными для второй фазы, фазы запроса, являются данные запроса. Проблема состоит в том, чтобы определить, были ли данные запроса включены в исходный набор входных данных. Операции бесплатны, за исключением доступа к ячейкам памяти.
Эта модель полезна при анализе структур данных. В частности, модель четко показывает минимальное количество обращений к памяти для решения проблемы, в которой хранятся данные, по которым мы хотели бы выполнить некоторый запрос. Примером такой проблемы является динамическая проблема частичной суммы .
История
В статье Эндрю Яо 1981 года «Следует ли сортировать таблицы?» Яо описал модель проверки ячеек и использовал ее, чтобы дать минимальное количество «проверок» или обращений к ячейкам памяти, необходимых для определения того, существует ли данный элемент данных запроса в таблице. хранится в памяти.
Формальное определение
Учитывая набор данных, создайте структуру, состоящую из ячеек памяти, каждая из которых может хранить биты. Затем, когда задан элемент запроса, определите, правильно ли он, обратившись к ячейкам памяти. Такой алгоритм называется алгоритмом проверки ошибок с использованием ячеек с размером слова .
Заметные результаты
Динамические частичные суммы
Задача динамической частичной суммы определяет две операции Update ( k, v ), которые концептуально устанавливают значение в массиве A по индексу k равным v , и Sum ( k ), которая возвращает сумму значений в A по индексам. От 0 до k . Такая реализация потребует времени для обновления и времени для Sum .
Вместо этого, если значения хранятся в виде листьев в дереве, внутренние узлы которого хранят значения поддерева с корнем в этом узле. В этой структуре Update требуется время для обновления каждого узла в пути от листа к корню, а Sum аналогичным образом требует времени для обхода дерева от листа к корню, суммируя значения всех поддеревьев слева от индекса запроса.
Михай Пэтрашку использовал модель клеточного зонда и аргумент передачи информации, чтобы показать, что проблема частичных сумм требует времени на операцию.
Приблизительный поиск ближайшего соседа
Задача точного поиска ближайшего соседа состоит в том, чтобы определить ближайшую точку в наборе входных точек к заданной точке запроса. Приближенная версия этой проблемы часто рассматривается, поскольку многие приложения этой проблемы находятся в пространствах очень высокой размерности, и решение проблемы в больших размерностях требует экспоненциального времени или пространства по отношению к размерности.
Чакрабарти и Регев доказали, что задача поиска приближенного ближайшего соседа на кубе Хэмминга с использованием полиномиальной памяти и размера слова требует времени запроса в худшем случае, равного . Это доказательство использовало модель клетки-зонда и теоретические методы информации для сложности коммуникации.
