Registro de huellas dactilares

En informática , una búsqueda por referencia (o "finger search") en una estructura de datos es una extensión de cualquier operación de búsqueda que dicha estructura admita, donde se proporciona una referencia (o "finger") a un elemento de la estructura de datos junto con la consulta. Si bien el tiempo de búsqueda de un elemento se suele expresar como una función del número de elementos en una estructura de datos, los tiempos de búsqueda por referencia dependen de la distancia entre el elemento y la referencia.

En un conjunto de n elementos, la distancia d ( x , y ) (o simplemente d cuando no hay ambigüedad) entre dos elementos x e y es su diferencia de rango. Si x e y son los elementos i y j más grandes de la estructura, entonces la diferencia de rango es | i - j |. Si una búsqueda normal en alguna estructura normalmente tomaría${\displaystyle O(f(n))}$⁠ tiempo, entonces una búsqueda con el dedo x usando el dedo y debería idealmente tomar ⁠${\displaystyle O(f(d))}$Tiempo . Nótese que, dado que d ≤ n , en el peor de los casos, la búsqueda con el dedo es tan ineficiente como la búsqueda normal. Sin embargo, en la práctica, estas búsquedas con el dedo degeneradas realizan más trabajo que las búsquedas normales. Por ejemplo, si f( n ) es log( n ) y la búsqueda con el dedo realiza el doble de comparaciones que la búsqueda normal en el peor de los casos, se deduce que la búsqueda con el dedo es más lenta cuando d > √n . Por lo tanto, la búsqueda con el dedo solo debe usarse cuando se puede esperar razonablemente que el objetivo esté realmente cerca del dedo.

Algunas estructuras de datos populares admiten la búsqueda por dedos sin necesidad de modificar la estructura en sí. En estructuras donde la búsqueda de un elemento x se realiza reduciendo el intervalo en el que se puede encontrar x , la búsqueda por dedos desde y se suele realizar invirtiendo el proceso de búsqueda desde y hasta que el intervalo de búsqueda sea lo suficientemente grande como para contener x , momento en el que la búsqueda continúa con normalidad.

Si se puede realizar una búsqueda de dedos de forma iterativa en un tiempo O ( f ( d )), donde cada iteración toma un tiempo O (1), entonces al proporcionar c dedos diferentes, se puede realizar una búsqueda de dedos en un tiempo O ( c min{ d ( x , y1 ), ..., d ( x , yc ₎ }). Esto se logra iniciando la búsqueda de dedos para los _c dedos e iterando un paso hacia adelante cada uno hasta que el primero termine.

Dada cualquier secuencia A = [ a ₁ , ..., a _m ] de m accesos, se dice que una estructura tiene la propiedad de dedo estático para un dedo fijo f , si el tiempo para realizar A es${\displaystyle O\left(\sum _{i=1}^{m}\log d(f,a_{i})\right)}$^Los árboles splay tienen esta propiedad para cualquier elección de f sin procesamiento adicional en secuencias de accesos suficientemente grandes. [ ^{4 ]}

La búsqueda por dedos permite reutilizar el trabajo realizado en búsquedas anteriores. Por ejemplo, una forma de iterar sobre los elementos de una estructura de datos es simplemente buscarlos por dedos en orden, donde el dedo de una consulta corresponde a la ubicación del resultado de la anterior. Se puede optimizar la estructura de datos mediante este método si se sabe que las búsquedas se realizan con frecuencia cerca de la última.

Un árbol de búsqueda de dedos es un tipo de estructura de datos que permite especificar dedos de forma que todas o algunas de sus operaciones compatibles sean más rápidas al acceder o modificar una ubicación cercana a un dedo. A diferencia de las búsquedas de dedos descritas en este artículo, estos dedos no se proporcionan en el momento de la consulta, sino que se especifican por separado para que todas las operaciones futuras los utilicen. Una ventaja de esto es que el usuario no necesita manipular ni almacenar referencias internas a la estructura; simplemente puede especificar un elemento dentro de ella.