Un filtro de cociente es una estructura de datos probabilística que ahorra espacio y se utiliza para comprobar si un elemento es miembro de un conjunto (un filtro de consulta de pertenencia aproximada , AMQ). Una consulta obtendrá una respuesta que especifique que el elemento definitivamente no está en el conjunto o que probablemente esté en el conjunto. El primer resultado es definitivo; es decir , la prueba no genera falsos negativos . Pero con el segundo resultado hay cierta probabilidad, ε, de que la prueba devuelva "el elemento está en el conjunto" cuando, de hecho, el elemento no está presente en el conjunto ( es decir , un falso positivo ). Hay una compensación entre ε, la tasa de falsos positivos, y el tamaño de almacenamiento; aumentar el tamaño de almacenamiento del filtro reduce ε. Otras operaciones AMQ incluyen "insertar" y "eliminar opcionalmente". Cuantos más elementos se agreguen al conjunto, mayor será la probabilidad de falsos positivos.
Una aplicación típica de los filtros de cociente y otros filtros AMQ es servir como proxy de las claves en una base de datos en el disco. A medida que se agregan o eliminan claves de la base de datos, el filtro se actualiza para reflejar esto. Cualquier búsqueda consultará primero el filtro de cociente rápido y luego buscará en la base de datos (presumiblemente mucho más lenta) solo si el filtro de cociente informó la presencia de la clave. Si el filtro devuelve ausencia, se sabe que la clave no está en la base de datos sin que se haya realizado ningún acceso al disco.
Un filtro de cociente tiene las operaciones habituales de AMQ de inserción y consulta. Además, también se puede fusionar y cambiar de tamaño sin tener que volver a generar el hash de las claves originales (evitando así la necesidad de acceder a esas claves desde un almacenamiento secundario). Esta propiedad beneficia a ciertos tipos de árboles de fusión con estructura de registro .
La tabla hash compacta subyacente a un filtro de cociente fue descrita por Cleary en 1984. [1] La primera referencia conocida al uso de la estructura como un filtro AMQ es de Pagh et al. en 2005. [2] En 2009, Dillinger y Manolios optimizaron los metadatos de la estructura, agregaron alojamiento in situ de más elementos y aplicaron la estructura a la verificación del modelo de estado explícito . [3] En 2011, Bender et al. escribieron el nombre "filtro de cociente", describieron varias variantes con diferentes compensaciones de codificación de metadatos, mostraron cómo fusionar y cambiar el tamaño de los filtros de cociente, presentaron una versión optimizada para escritura del filtro de cociente para usar en disco y aplicaron la estructura a problemas de almacenamiento de bases de datos. [4] [5] En 2017, Pandey et al. describieron una versión que usa instrucciones de manipulación de bits de hardware para mejorar el rendimiento, admite actualizaciones simultáneas y agrega soporte para asociar un contador de tamaño variable a cada elemento. [6]
El filtro de cociente se basa en un tipo de tabla hash en la que las entradas contienen solo una parte de la clave más algunos bits de metadatos adicionales. Estos bits se utilizan para tratar el caso en el que claves distintas se convierten en hashes de la misma entrada de la tabla. Por el contrario, otros tipos de tablas hash que tratan tales colisiones mediante la vinculación a áreas de desbordamiento no son compactas porque la sobrecarga debido a la vinculación puede exceder el almacenamiento utilizado para almacenar la clave. [1] En un filtro de cociente, una función hash genera una huella digital de p bits. Los r bits menos significativos se denominan resto, mientras que los q = p - r bits más significativos se denominan cociente, de ahí el nombre de cociente (acuñado por Knuth . [7] ) La tabla hash tiene 2 ranuras q .
Para alguna clave d que genera la huella digital d H , sea su cociente d Q y el resto d R . QF intentará almacenar el resto en la ranura d Q , que se conoce como ranura canónica . Sin embargo, la ranura canónica podría estar ocupada porque varias claves pueden generar la misma huella digital (una colisión dura ) o porque incluso cuando las huellas digitales de las claves son distintas pueden tener el mismo cociente (una colisión suave ). Si la ranura canónica está ocupada, el resto se almacena en alguna ranura a la derecha.
Como se describe a continuación, el algoritmo de inserción garantiza que todas las huellas dactilares que tienen el mismo cociente se almacenen en ranuras contiguas. Este conjunto de huellas dactilares se define como una serie . [4] Nótese que la primera huella dactilar de una serie podría no ocupar su ranura canónica si la serie ha sido forzada a la derecha por alguna serie a la izquierda.
Sin embargo, una ejecución cuya primera huella digital ocupa su ranura canónica indica el inicio de un clúster . [4] La ejecución inicial y todas las ejecuciones posteriores comprenden el clúster, que termina en una ranura desocupada o en el inicio de otro clúster.
Los tres bits adicionales se utilizan para reconstruir la huella digital de una ranura y tienen la siguiente función:
Las distintas combinaciones tienen el siguiente significado:
Podemos comprobar si un filtro cociente contiene alguna clave, d, de la siguiente manera. [4]
Realizamos un hash de la clave para producir su huella digital, d H , que luego dividimos en sus bits q de orden superior, d Q , que constituyen su cociente, y sus bits r de orden inferior, d R , que constituyen su resto. La ranura d Q es la ranura canónica de la clave. Esa ranura está vacía si sus tres bits de metadatos son falsos. En ese caso, el filtro no contiene la clave.
Si la ranura canónica está ocupada, entonces debemos localizar la serie del cociente. El conjunto de ranuras que contienen los residuos que pertenecen al mismo cociente se almacenan de forma contigua y forman la serie del cociente. La primera ranura de la serie puede ser la ranura canónica, pero también es posible que toda la serie se haya desplazado hacia la derecha por la invasión desde la izquierda de otra serie.
Para localizar la secuencia del cociente, primero debemos localizar el inicio del clúster. El clúster consta de un conjunto contiguo de secuencias. Comenzando con la ranura canónica del cociente, podemos escanear hacia la izquierda para localizar el inicio del clúster y luego escanear hacia la derecha para localizar la secuencia del cociente.
Escaneamos hacia la izquierda buscando una ranura con is_shifted es falso. Esto indica el inicio del clúster. Luego escaneamos hacia la derecha manteniendo un conteo continuo de la cantidad de ejecuciones que debemos omitir. Cada ranura a la izquierda de la ranura canónica que tiene is_occupied establecido indica otra ejecución que se debe omitir, por lo que incrementamos el conteo continuo. Cada ranura que tiene is_continuation claro indica el inicio de otra ejecución, por lo tanto, el final de la ejecución anterior, por lo que decrementamos el conteo continuo. Cuando el conteo continuo llega a cero, estamos escaneando la ejecución del cociente. Podemos comparar el resto en cada ranura en la ejecución con d R . Si se encuentra, informamos que la clave está (probablemente) en el filtro; de lo contrario, informamos que la clave definitivamente no está en el filtro.
Tomemos, por ejemplo, la búsqueda del elemento e . Vea el estado 3 en la figura. Calcularíamos hash(e) , lo dividiríamos en su resto, e R y su cociente e Q , que es 4. Al escanear hacia la izquierda desde la ranura 4, encontramos tres ranuras is_occupied , en los índices 4, 2 y 1, lo que indica que la ejecución de e Q es la 3.ª ejecución del clúster. El escaneo se detiene en la ranura 1, que detectamos como el inicio del clúster porque no está vacía ni desplazada. Ahora debemos escanear hacia la derecha hasta la 3.ª ejecución. El inicio de una ejecución se indica mediante is_continuation como falso. La primera ejecución se encuentra en el índice 1, la segunda en el 4 y la tercera en el 5. Comparamos el resto guardado en cada ranura en la ejecución que comienza en el índice 5. Solo hay una ranura en esa ejecución pero, en nuestro ejemplo, su resto es igual a e R , lo que indica que e es de hecho un miembro del filtro, con probabilidad 1 - ε.
La inserción sigue un camino similar a la búsqueda hasta que nos aseguramos de que la clave no está en el filtro. [4] En ese momento, insertamos el resto en una ranura de la ejecución actual, una ranura elegida para mantener la ejecución ordenada. Desplazamos hacia delante los restos en cualquier ranura del clúster en la ranura elegida o después de ella y actualizamos los bits de la ranura.
La figura muestra un filtro de cociente que pasa por una serie de estados a medida que se añaden elementos. En el estado 1 se han añadido tres elementos. El espacio que ocupa cada uno forma una serie de un espacio que también es un grupo distinto.
En el estado 2 se han añadido los elementos c y d . El elemento c tiene un cociente de 1, lo mismo que b . Suponemos que b R < c R , por lo que c R se desplaza a la ranura 2 y se marca como continuación y desplazado . El elemento d tiene un cociente de 2. Dado que su ranura canónica está en uso, se desplaza a la ranura 3 y se marca como desplazado . Además, su ranura canónica se marca como ocupada . Las ejecuciones para los cocientes 1 y 2 ahora comprenden un clúster.
En el estado 3 se ha añadido el elemento a . Su cociente es 1. Suponemos que a R < b R, por lo que los residuos en las ranuras 1 a 4 deben desplazarse. La ranura 2 recibe b R y se marca como continuación y se desplaza . La ranura 5 recibe e R y se marca como desplazada . Las series para los cocientes 1, 2 y 4 ahora forman un grupo, y la presencia de esas tres series en el grupo se indica al marcar las ranuras 1, 2 y 4 como ocupadas .
Bender [4] sostiene que los clústeres son pequeños. Esto es importante porque las búsquedas e inserciones requieren localizar el inicio y la longitud de un clúster completo. Si la función hash genera huellas dactilares distribuidas uniformemente, entonces la longitud de la mayoría de las ejecuciones es O (1) y es muy probable que todas las ejecuciones tengan una longitud O (log m ), donde m es el número de ranuras en la tabla. [4]
Bender [4] calcula la probabilidad de un falso positivo (es decir, cuando el hash de dos claves da como resultado la misma huella digital) en términos del tamaño del resto de la tabla hash y el factor de carga. Recordemos que una huella digital de p bits se divide en un cociente de q bits, que determina el tamaño de la tabla de m = 2 q ranuras, y un resto de r bits. El factor de carga es la proporción de ranuras ocupadas n con respecto al total de ranuras m : . Entonces, para una buena función hash, es aproximadamente la probabilidad de una colisión dura.
La versión de Pandey del filtro de cociente requiere menos espacio que un filtro Bloom comparable cuando la tasa de falsos positivos objetivo es menor a 1/64. [6]
Los filtros de cociente son AMQ y, como tales, proporcionan muchos de los mismos beneficios que los filtros Bloom . Una base de datos grande, como Webtable [8] puede estar compuesta de subtablas más pequeñas, cada una de las cuales tiene un filtro asociado. Cada consulta se distribuye simultáneamente a todas las subtablas. Si una subtabla no contiene el elemento solicitado, su filtro puede completar rápidamente la solicitud sin incurrir en ninguna operación de E/S.
Los filtros de cociente ofrecen dos beneficios en algunas aplicaciones.
El espacio que utilizan los filtros de cociente es comparable al de los filtros Bloom. Sin embargo, los filtros de cociente se pueden fusionar de manera eficiente dentro de la memoria sin tener que volver a insertar las claves originales.
Esto es particularmente importante en algunos sistemas de almacenamiento estructurados en registros que utilizan el árbol de fusión estructurado en registros o árbol LSM. [9] El árbol LSM es en realidad una colección de árboles, pero que se trata como un único almacén de clave-valor. Una variación del árbol LSM es el árbol de fusión de matriz ordenada o SAMT. [10] En esta variación, los árboles componentes de un SAMT se denominan árboles Wanna-B. Cada árbol Wanna- B tiene un filtro de cociente asociado. Una consulta en el SAMT se dirige solo a árboles Wanna - B seleccionados , como lo evidencian sus filtros de cociente.
El sistema de almacenamiento, en su funcionamiento normal, compacta los árboles Wanna- B de SAMT , fusionando árboles Wanna -B más pequeños en árboles más grandes y fusionando sus filtros de cociente. Una propiedad esencial de los filtros de cociente es que se pueden fusionar de manera eficiente sin tener que volver a insertar las claves originales. Dado que, en el caso de conjuntos de datos grandes, los árboles Wanna- B pueden no estar en la memoria, acceder a ellos para recuperar las claves originales implicaría muchas operaciones de E/S.
Por construcción, los valores de un filtro de cociente se almacenan en orden. Cada ejecución está asociada a un valor de cociente específico, que proporciona la parte más significativa de la huella digital; las ejecuciones se almacenan en orden y cada ranura de la ejecución proporciona la parte menos significativa de la huella digital.
De esta manera, trabajando de izquierda a derecha, se pueden reconstruir todas las huellas digitales y la lista resultante de números enteros estará ordenada. Fusionar dos filtros de cociente es entonces una simple cuestión de convertir cada filtro de cociente en una lista de este tipo, fusionar las dos listas y usarlas para completar un nuevo filtro de cociente más grande. De manera similar, podemos reducir a la mitad o duplicar el tamaño de un filtro de cociente sin tener que volver a hacer un hash de las claves, ya que las huellas digitales se pueden volver a calcular utilizando solo los cocientes y los residuos. [4]
{{cite book}}: Mantenimiento de CS1: ubicación ( enlace ){{cite journal}}: Requiere citar revista |journal=( ayuda )
Medios relacionados con Filtro de cociente en Wikimedia Commons