stringtranslate.com

Informe de alcance

En geometría computacional y teoría de bases de datos , una consulta de informe de rango solicita una lista de los puntos que coinciden con la consulta. La consulta suele especificarse mediante una forma geométrica, que contiene todos los puntos que deben coincidir, y se denomina rango. El informe de rango es un caso especial de búsqueda de rango , en el que las consultas pueden devolver otros tipos de información agregada sobre los puntos de un rango.

Las consultas de informes de rangos se manejan a menudo mediante la creación de una estructura de datos a partir de una colección de puntos que pueden responder a las consultas de manera eficiente. Debido a que el tamaño de salida en el peor de los casos para una consulta de informes de rangos, medido como una función del tamaño del conjunto de datos n , puede ser n en sí mismo, gran parte de la investigación sobre estructuras de datos de informes de rangos ha investigado algoritmos sensibles a la salida , donde el tiempo de consulta se analiza en términos tanto de n como de la cantidad de puntos informados (a menudo denotados como k ).

Por ejemplo, para datos unidimensionales (numéricos) con rangos de consulta que son intervalos , las consultas de informes de rango se pueden manejar almacenando los datos en una matriz ordenada. Con esta estructura, se puede usar la búsqueda binaria para encontrar el punto más cercano al inicio de un intervalo de consulta y luego escanear la matriz desde ese punto en adelante para enumerar todos los puntos en el intervalo. El almacenamiento de esta estructura de datos utiliza un espacio O ( n ) (lineal) y maneja consultas en tiempo O (log n + k ) por consulta.

Referencias