BitFunnel es el algoritmo de indexación del motor de búsqueda y un conjunto de componentes utilizados en el motor de búsqueda Bing , [1] que se hicieron de código abierto en 2016. [2] BitFunnel utiliza firmas en segmentos de bits en lugar de un índice invertido en un intento de reducir las operaciones. costo. [3]
Desarrollador (es) | Microsoft |
---|---|
Versión inicial | 2016 |
Repositorio | github |
Escrito en | C ++ |
Plataforma | Windows , macOS , Ubuntu |
Tipo | Algoritmo de indexación de motores de búsqueda |
Licencia | Licencia MIT |
Sitio web | bitfunnel |
Historia
El progreso en la implementación de BitFunnel se hizo público a principios de 2016, con la expectativa de que hubiera una implementación utilizable más adelante ese año. [4] En septiembre de 2016, el código fuente estuvo disponible a través de GitHub . [5] Se publicó un documento sobre el algoritmo y la implementación de BitFunnel a través del Grupo de Interés Especial sobre Recuperación de Información de la Asociación de Maquinaria de Computación en 2017 y ganó el Premio al Mejor Papel. [3] [6]
Componentes
BitFunnel consta de tres componentes principales: [1]
- BitFunnel: el sistema de búsqueda / recuperación de texto en sí
- WorkBench: una herramienta para preparar texto para usar en BitFunnel
- NativeJIT: un componente de software que toma expresiones que utilizan estructuras de datos C y las transforma en código ensamblador altamente optimizado .
Algoritmo
Resumen inicial del problema y la solución
El artículo de BitFunnel describe el "problema de coincidencia", que ocurre cuando un algoritmo debe identificar documentos mediante el uso de palabras clave. El objetivo del problema es identificar un conjunto de coincidencias dado un corpus para buscar y una consulta de términos de palabras clave para comparar. Este problema se resuelve comúnmente a través de índices invertidos , donde cada elemento de búsqueda se mantiene con un mapa de palabras clave. [3]
Por el contrario, BitFunnel representa cada elemento de búsqueda a través de una firma. Una firma es una secuencia de bits que describe un filtro Bloom de los términos de búsqueda en un elemento de búsqueda dado. El filtro de floración se construye mediante hash a través de varias posiciones de bits. [3]
Implementación teórica de firmas de cadenas de bits
La firma de un documento (D) puede describirse como la firma lógica o de su término:
De manera similar, una consulta para un documento (Q) se puede definir como una unión:
Además, un documento D es miembro del conjunto M ' cuando se cumple la siguiente condición:
Luego, este conocimiento se combina para producir una fórmula en la que M ' se identifica mediante documentos que coinciden con la firma de la consulta:
Estos pasos y sus pruebas se analizan en el documento de 2017. [3]
Pseudocódigo para firmas de cadenas de bits
Este algoritmo se describe en el artículo de 2017. [3]
Referencias
- ↑ a b Yegulalp, Serdar (6 de septiembre de 2016). "Componentes de Bing de código abierto de Microsoft para una rápida compilación de código" . InfoWorld .
- ^ Verma, Arpit (7 de septiembre de 2016). "Componentes principales de Microsoft Open Sources del motor de búsqueda Bing, aquí es por qué es importante" . Fossbytes . Consultado el 12 de junio de 2020 .
- ^ a b c d e f Goodwin, Bob; Hopcroft, Michael; Luu, Dan; Clemmer, Alex; Curmei, Mihaela; Elnikety, Sameh; Él, Yuxiong (7 de agosto de 2017). "BitFunnel" . Actas de la 40ª Conferencia Internacional ACM SIGIR sobre Investigación y Desarrollo en Recuperación de Información . Nueva York, NY, EE. UU .: ACM: 605–614. doi : 10.1145 / 3077136.3080789 . ISBN 978-1-4503-5022-8.
- ^ "¿Cuándo se podrá utilizar BitFunnel? · BitFunnel" . bitfunnel.org . Consultado el 12 de junio de 2020 .
- ^ BitFunnel / BitFunnel , BitFunnel, 2020-05-12 , recuperado 2020-06-12
- ^ "Premios SIGIR al Mejor Papel" . ACM . Consultado el 8 de julio de 2020 .
enlaces externos
- BitFunnel · GitHub
- BitFunnel · BitFunnel