Modelo de sonda celular

En informática , el modelo de sonda celular es un modelo de computación similar a la máquina de acceso aleatorio , excepto que todas las operaciones son gratuitas, excepto el acceso a la memoria. Este modelo es útil para demostrar límites inferiores de algoritmos para problemas de estructura de datos.

Descripción general

El modelo de sonda celular es una modificación del modelo de máquina de acceso aleatorio , en el que el costo computacional solo se asigna al acceso a las celdas de memoria.

El modelo está destinado a demostrar límites inferiores en la complejidad de los problemas de estructura de datos . Un tipo de tales problemas tiene dos fases: la fase de preprocesamiento y la fase de consulta. La entrada a la primera fase, la fase de preprocesamiento, es un conjunto de datos a partir del cual se construye alguna estructura a partir de celdas de memoria. La entrada a la segunda fase, la fase de consulta, es un parámetro de consulta. La consulta tiene que consultar la estructura de datos para calcular su resultado; por ejemplo, se puede pedir a una consulta que determine si el parámetro de consulta se incluyó en el conjunto de datos de entrada original. Otro tipo de problema involucra tanto operaciones de actualización, que modifican la estructura de datos, como operaciones de consulta. Por ejemplo, una actualización puede agregar un elemento a la estructura o eliminar uno. En ambos casos, la complejidad de la sonda de celda de la estructura de datos se caracteriza por el número de celdas de memoria a las que se accede durante el preprocesamiento, la consulta y (si es relevante) la actualización. La complejidad de la sonda de celda es un límite inferior en la complejidad temporal de las operaciones correspondientes en una máquina de acceso aleatorio, donde las transferencias de memoria son parte de las operaciones contadas en la medición del tiempo.

Un ejemplo de este tipo de problema es el problema de la suma parcial dinámica . ^{[1] [2]}

Historia

El artículo de Andrew Yao de 1981 "¿Deberían ordenarse las tablas?" ^[3] se considera la introducción del modelo de sonda de celdas. Yao lo utilizó para proporcionar un número mínimo de "sondeos" o accesos de celdas de memoria necesarios para determinar si un dato de consulta dado existe dentro de una tabla almacenada en la memoria. En 1989, Fredman y Saks iniciaron el estudio de los límites inferiores de la sonda de celdas para problemas de estructura de datos dinámicos (es decir, que involucran actualizaciones y consultas), e introdujeron la notación CPROBE( b ) para el modelo de sonda de celdas asumiendo que una celda de memoria (palabra) consta de b bits. ^[4]

Resultados notables

Buscando Tablas

Yao ^[3] consideró un problema de estructura de datos estática donde uno tiene que construir una estructura de datos ("tabla") para representar un conjunto de elementos de . El parámetro de consulta es un número y la consulta tiene que informar si está en la tabla. Un requisito crucial es que la tabla consista exactamente en entradas, donde cada entrada es un entero entre y . Yao demostró que mientras el tamaño de la tabla esté limitado independientemente de y sea lo suficientemente grande, una consulta debe realizar sondeos en el peor de los casos. Esto demuestra que una tabla ordenada junto con la búsqueda binaria de consultas es un esquema óptimo, en este entorno restringido. ${\displaystyle S}$ ${\displaystyle n}$ ${\displaystyle 1,\dots ,m}$ ${\displaystyle x\leq m}$ ${\displaystyle x}$ ${\displaystyle n}$ ${\displaystyle 1}$ ${\displaystyle m}$ ${\displaystyle m}$ ${\displaystyle m}$ ${\displaystyle \lceil \log(n+1)\rceil }$

Vale la pena señalar que en el mismo artículo, Yao ^[3] también demostró que si el problema se relaja para permitir que la estructura de datos almacene entradas, entonces las consultas se pueden realizar utilizando solo dos sondas. ^{[nota 1]} Este límite superior, de manera similar al límite inferior descrito anteriormente, también requiere ser lo suficientemente grande, como una función de . Sorprendentemente, este límite superior usa solo una entrada de tabla adicional a la configuración para la que se aplica el límite inferior. ${\displaystyle n+1}$ ${\displaystyle m}$ ${\displaystyle n}$

Sumas parciales dinámicas

El problema de suma parcial dinámica define dos operaciones Update ( k,v ) que establece el valor en una matriz A en el índice k como v , y Sum ( k ) que devuelve la suma de los valores en A en los índicesDe 0 a k . Una implementación ingenua requeriría tiempo para Update y tiempo para Sum . ^[5] ${\displaystyle O(1)}$ ${\displaystyle O(n)}$

En cambio, los valores se pueden almacenar como hojas en un árbol cuyos nodos internos almacenan la suma sobre el subárbol con raíz en ese nodo. En esta estructura, Update requiere tiempo para actualizar cada nodo en la ruta de la hoja a la raíz, y Sum requiere tiempo de manera similar para recorrer el árbol desde la hoja hasta la raíz sumando los valores de todos los subárboles a la izquierda del índice de consulta. ${\displaystyle O(\log n)}$ ${\displaystyle O(\log n)}$

Mejorando un resultado de Fredman y Saks, Mihai Pătraşcu utilizó el modelo de sonda celular y un argumento de transferencia de información para demostrar que el problema de sumas parciales requiere tiempo por operación en el peor de los casos (es decir, la peor consulta y actualización debe consumir dicho tiempo), asumiendo bits por palabra. ^{[1] [2]} Además, exhibió la curva de compensación entre el tiempo de actualización y el tiempo de consulta e investigó el caso en que las actualizaciones están restringidas a pequeñas cantidades (de bits). ${\displaystyle \Omega \left(\log n\right)}$ ${\displaystyle b=\Omega (\log n)}$ ${\displaystyle \delta =o(b)}$

Mantenimiento de conjuntos disjuntos (Union-Find)

En la estructura de datos de conjuntos disjuntos , la estructura representa una colección de conjuntos disjuntos; hay una operación de actualización, llamada Unión, que une dos conjuntos, y una operación de consulta, llamada Encontrar, que identifica el conjunto al que pertenece un elemento dado. Fredman y Saks demostraron que en el modelo CPROBE(log n ), cualquier solución para este problema requiere sondas en el peor de los casos (incluso en expectativa) para ejecutar uniones y hallazgos. ^[4] Esto muestra que la estructura de datos clásica descrita en el artículo sobre la estructura de datos de conjuntos disjuntos es óptima. ${\displaystyle \Omega (m\alpha (m,n))}$ ${\displaystyle n-1}$ ${\displaystyle m\geq n}$

Búsqueda aproximada de vecino más cercano

El problema de búsqueda del vecino más próximo exacto consiste en determinar el más cercano en un conjunto de puntos de entrada a un punto de consulta dado. A menudo se considera una versión aproximada de este problema, ya que muchas aplicaciones de este problema se dan en espacios de dimensiones muy altas y la resolución del problema en dimensiones altas requiere tiempo o espacio exponencial con respecto a la dimensión. ^[6]

Chakrabarti y Regev demostraron que el problema de búsqueda aproximada del vecino más próximo en el cubo de Hamming utilizando almacenamiento polinomial y tamaño de palabra requiere un tiempo de consulta en el peor de los casos de . Esta prueba utilizó el modelo de sonda celular y técnicas de teoría de la información de la complejidad de la comunicación . ${\displaystyle d^{O(1)}}$ ${\displaystyle \Omega \left({\frac {\log \log d}{\log \log \log d}}\right)}$

El modelo de sonda celular versus máquinas de acceso aleatorio

En el modelo de sonda celular, limitar el rango de valores que se pueden almacenar en una celda es primordial (de lo contrario, se podría codificar toda la estructura de datos en una celda). La máquina de acceso aleatorio idealizada que se utiliza como modelo computacional en Ciencias de la Computación no impone un límite al contenido de cada celda (a diferencia de la RAM de palabras ). Por lo tanto, los límites inferiores de la sonda celular se aplican a la RAM de palabras, pero no a la RAM idealizada. Sin embargo, ciertas técnicas para los límites inferiores de la sonda celular se pueden trasladar a la RAM idealizada con un conjunto de instrucciones algebraicas y se obtienen límites inferiores similares. ^[7]

Enlaces externos

• Entrada del Diccionario de algoritmos y estructuras de datos del NIST sobre el modelo de sonda celular

Referencias

Notas

1. Véase el Teorema 3 del artículo de Yao.

Citas

1. Pătraşcu, Mihai ; Demaine, Erik D. (2006). "Límites inferiores logarítmicos en el modelo de célula-sonda". Revista SIAM de Computación . 35 (4): 932–963. arXiv : cs/0502041 . Código Bibliográfico :2005cs........2041P. doi :10.1137/s0097539705447256. S2CID  2202874.
2. Pătraşcu, Mihai . "Límites inferiores para sumas parciales dinámicas" (PDF) . Consultado el 9 de abril de 2014 .
3. Yao, Andrew Chi-Chih (julio de 1981). "¿Deberían ordenarse las tablas?". J. ACM . 28 (3): 615–628. doi : 10.1145/322261.322274 .
4. Fredman, Michael; Saks, Michael (1989). "La complejidad de la sonda celular en las estructuras de datos dinámicas". Actas del vigésimo primer simposio anual de la ACM sobre teoría de la computación - STOC '89 . Vol. 21. págs. 345–354. doi :10.1145/73007.73040. ISBN 0897913078. Número de identificación del sujeto  13470414.
5. Zatloukal, Kevin (10 de noviembre de 2010). "Notas sobre los "límites inferiores logarítmicos en el modelo Cell-Probe"" (PDF) . Consultado el 9 de abril de 2014 .
6. Chakrabarti, Amit; Regev, Oded (2004). "Un límite inferior óptimo de sonda de celdas aleatorias para la búsqueda aproximada del vecino más cercano". 45.º Simposio anual IEEE sobre fundamentos de la informática . págs. 473–482. doi :10.1109/FOCS.2004.12. ISBN 0-7695-2228-9. Número de identificación del sujeto  3004976.
7. Ben-Amram, Amir M.; Galil, Zvi (2002). "Límites inferiores para estructuras de datos dinámicas en RAM algebraicas". Algorithmica . 32 (3): 364–395. doi :10.1007/s00453-001-0079-6. S2CID  22324845.