Ya he aprendido otra cosa :D

por Áureo Ares

Filtros Bloom escalables.

abril 7th, 2014

Hace dos semanas publiqué un ejemplo de filtro Bloom básico. En mis aventuras con web scraping el que realmente uso es una versión escalable ya que suele ser muy difícil estimar el número máximo de enlaces que voy a necesitar almacenar.

No existe (que yo sepa) un modo de aumentar el tamaño del array de bits de un filtro Bloom una vez que ya se han empezado a añadir elementos. El modo de implementar un filtro escalable no es ni más ni menos que utilizar más de un filtro a la vez.

Para ello, cada vez que un filtro se llena se crea uno nuevo de mayor capacidad. Los nuevos elementos se van añadiendo al último filtro creado y a la hora de buscar un elemento se busca en todos uno por uno.

La base del filtro escalable es por tanto muy sencilla. La mayor complicación sería escoger el modo de escalar la capacidad de los filtros, es decir, cómo de grande debe ser el nuevo en comparación con el anterior. En su momento me vino a la cabeza la posibilidad de que todos tengan el mismo tamaño e incluso de que fuesen cada vez más pequeños, pero hasta la fecha no se me ha ocurrido ningún extraño caso en el que pueda resultar útil.

Lo normal es utilizar una función lineal o exponencial. Yo he optado por permitir ambas ya que no era ningún esfuerzo pero en la práctica siempre me ha venido mejor la exponencial. Los cálculos son muy sencillos:

 

Añadir y buscar elementos también es muy sencillo:

Lo único destacable es que al buscar es más eficiente recorrer los filtros en orden inverso (del último al primero), ya que de media se tardará menos en encontrar el elemento. Aunque en caso de no encontrarse la búsqueda tardará lo mismo se haga en un sentido u otro.

El código completo comentado se puede ver en Google Code.