• Author / Uploaded
• joel js gomez alanoca

Citation preview

2. TRABAJO RELACIONADO Y ANÁLISIS

2.3 MBR de expansión debido a la velocidad

2.1 Índice para objetos en movimiento

Deje sea el límite inferior y el límite superior de algunos

Existe una gran cantidad de investigaciones sobre el manejo e indexación de datos espaciales y temporales, que finalmente condujeron al estudio. de gestión de datos espacio-temporales. MÁS [15] es uno de esos primeros esfuerzo. Al tratar el tiempo como una dimensión, los objetos en movimiento en un espacio dimensión pueden indexarse en (d + 1) -dimensiones. Por lo tanto, la se puede consultar el estado pronosticado para el futuro cercano de un objeto.

MBR respectivamente en la dimensión i en el tiempo 0, y u

El árbol TPR (el árbol R con parámetros de tiempo) [13] es un popular Índice basado en el árbol R conceptualmente similar a MOST. Vectores de velocidad de objetos o MBR, así como los MBR dinámicos en la actualidad El tiempo se almacena en el árbol. En un nodo no hoja, el vector de velocidad del MBR se determina como el valor máximo de velocidades en cada dirección en el subárbol. Un buen estudio del desempeño de El árbol TPR está en [17]. El TPR * -tree [17] fue propuesto para mejorar el árbol TPR mediante el empleo de un nuevo conjunto de algoritmos de actualización. Para inserciones, TPR * -tree mantiene un QP (cola de prioridad) para registrar el candidatos caminos que han sido inspeccionados. Al visitar los nodos descendientes, TPR * -tree extiende las rutas en QP hasta un global se elige la solución óptima, mientras que el árbol TPR solo elige un local camino óptimo El b* -tree [6] es una estructura B + -tree que indexa objetos en movimiento después de realizar una transformación en espacio unidimensional usando una curva de relleno de espacio. Los objetos se dividen en función del tiempo, pero indexado en el mismo espacio. Se han propuesto índices basados en hash para manejar el movimiento objetos [16], [2]. También se han propuesto combinaciones. por Por ejemplo, en [4], el hash en las celdas de la cuadrícula se usa para administrar mover objetos en la memoria, mientras que el árbol TPR se usa para administrar objetos en movimiento en frío en el disco, como una forma de proporcionar un soporte eficiente para actualizaciones frecuentes 2.2 Concurrencia en el árbol B y el árbol R El árbol B-link [10] se propuso para proporcionar concurrente eficiente transversal y actualización del árbol B +. Cada nodo mantiene un enlace correcto apuntando al nodo hermano derecho en el mismo nivel. Cuando una búsqueda proceso sin acoplamiento de bloqueo se cae en el árbol, aprenderá de cualquier división compite con ella al comparar teclas. Entonces puede visitar el nuevo nodo dividido a lo largo de la cadena de enlace derecha antes de que el nuevo nodo sea instalado en el árbol El árbol R-link [9] emplea una modificación similar para el árbol R. La principal diferencia entre el árbol R y el árbol B + es que las claves en El árbol R no está ordenado. Por lo tanto, LSN (número de secuencia lógica) se introduce en cada nodo y se mantiene en cada entrada del interno nodos La comparación de estos LSN se utiliza para descubrir divisiones de nodos. Una cadena de enlace derecha se utiliza nuevamente para localizar nodos recién divididos.

Velocidad mínima y máxima de los puntos en el MBR en la dimensión yo . Después de t unidades de tiempo, el volumen de este MBR es V = · T, el volumen de MBR puede reescribirse como V = Qd eso]. Por lo tanto,

La probabilidad de que un punto aleatorio acceda a un MBR la consulta de búsqueda, suponiendo distribuciones uniformes, es proporcional a la volumen del MBR. Por lo tanto, el número esperado de MBR a los que se accede en cualquier nivel del árbol de índice es proporcional a la suma de sus volúmenes La tasa del aumento en el número esperado de Los MBR a los que se debe acceder en algún nivel l es O (t d – 1 ), donde t es el tiempo transcurrido yd es la dimensionalidad. Esto muestra que los métodos de indexación tradicionales para objetos en movimiento se deterioran en gran medida debido al problema de superposición si no hay actualización durante mucho tiempo. 3. ESTRUCTURA DE INDICE GENERAL 3.1 Instantáneas de indexación En este artículo, adoptamos la suposición básica del intervalo máximo de actualización de los objetos en movimiento. Bajo tal supuesto, un el objeto en movimiento debe actualizar su movimiento al menos una vez en cada Tui marcas de tiempo Por lo tanto, se construyen una serie de índices de instantáneas en diferentes marcas de tiempo de referencia. La marca de tiempo de referencia del i-ésimo índice es en Tui (i - 0.5). Hay un árbol Buddy * indexado en estas referencias marcas de tiempo para los objetos en movimiento. El detalle de Buddy * -tree será será cubierto más adelante en este documento. La vida útil del ith árbol índice es entre Tui (i - 1) y Tui (i + 1). Por lo tanto, hay dos índices árboles mantenidos al mismo tiempo en nuestro sistema. La figura 1 muestra un ejemplo de los árboles de indexación.

En nuestro sistema, cada objeto es indexado por un Buddy * -tree en un sola marca de tiempo. Supongamos que un objeto actualiza su movimiento en la marca de tiempo tu, será recibido y actualizado por el (⌊tu / Tui⌋ + 1) th Buddy * -tree, de acuerdo con la velocidad y la posición del objeto en el momento de referencia del Buddy * -tree. Si el objeto está indexado previamente por el ith Buddy * -tree pero la nueva actualización se produce en el árbol i + 1, el objeto también se eliminará del árbol i-ésimo como insertado en i + 1 ° árbol. Por ejemplo, si Tui = 120 y un objeto se actualiza en tu = 110, la actualización se realizará el primer Buddy * -tree en la marca de tiempo 60. Si se actualiza nuevamente en tu = 130, el el primer árbol eliminará el objeto, mientras que el segundo árbol en la marca de tiempo 180 insertará el objeto en sí mismo. Se garantiza que el i-ésimo árbol índice debe estar vacío al final de su vida útil, ya que cada objeto se actualizará al menos una vez entre la marca de tiempo Tuii y Tui (i + 1). Si el usuario emite una consulta de rango predictivo q en la marca de tiempo tq, nuestro el sistema transformará las consultas a los dos árboles de índice actualmente mantenido. Como cada objeto se almacena en al menos un árbol, el La unión del resultado de la consulta de rango en estos dos árboles debe ser un resultado completo y válido para la consulta original. El detalle de la consulta. el procesamiento en Buddy * -tree se cubrirá más adelante. 3.2 Amigo * -árbol Dado que consideramos los objetos en movimiento como puntos estáticos para indexar en cada instantánea, y dada la importancia de la actualización rápida, nosotros elija el Buddy-tree [14] como la estructura básica de nuestra propuesta índice. El árbol de índice se construye cortando el espacio de forma recursiva en dos subespacios de igual tamaño con hiperplanos perpendiculares a El eje de cada dimensión. Cada subespacio se divide de forma recursiva hasta que los puntos en el subespacio encajan dentro de una sola página en

para satisfacer nuestras necesidades. Llamamos a la nueva estructura de índice Buddy * -tree. Un árbol de amigos tradicional crea rectángulos delimitadores apretados alrededor los puntos de datos en cada nodo. Dado que estos MBR ajustados son costosos para actualización, elegimos en su lugar utilizar límites sueltos. A esto le llamamos Espacio suelto delimitador (LBS) asociado con el nodo del árbol de índice. También almacenamos las velocidades máximas y mínimas en un nodo para Todos los objetos almacenados en el subárbol del nodo. Para admitir operaciones concurrentes de alto grado en Buddy * -tree, Absorbemos la idea de enlaces correctos entre cada nivel del árbol de enlaces B [10] y árbol R-link [9]. Por lo tanto, en cualquier nivel dado todos los nodos sonencadenado en una lista individualmente vinculada. En [9], los autores extienden el RTree asignando un parámetro adicional LSN como la marca de tiempo para cada nodo, que se utiliza para detectar la división y determinar dónde pare cuando se mueva a la derecha a lo largo de la cadena de enlace correcta. Sin embargo, esto la adición estructural no es necesaria en Buddy * -tree ya que estamos garantizado para no tener superposiciones entre nodos. En cambio, podemos simplemente detecte el nodo desinstalado dividido comparando el actual LBS de los nodos con el antiguo LBS. La figura 2 (a) muestra un ejemplo del Buddy * -árbol en espacio bidimensional, con el correspondiente espacio de datos ilustrado en la Figura 2 (b). La primera letra mayúscula en un el nodo denota el LSB del mismo, seguido de las entradas con la clave LSB (LBS esperado para el nodo secundario) o ungüentos 3.3 Expansión de consultas en Buddy * -Tree En cada instantánea Buddy * -tree index, utilizamos la expansión de consultas en lugar de la expansión MBR para responder consultas. Nuestra idea central es que el movimiento de objetos se puede manejar expandiendo consultas en lugar de perturbar objetos en el índice. Como en muchas otras estructuras de índice de objetos en movimiento, utilizamos interpolación lineal para estimar la posición del objeto en momentos distintos de tref. La posición de un objeto en el tiempo t puede calcularse mediante

En base a esto, podemos ampliar adecuadamente una consulta de la siguiente manera: supongamos que la consulta es q con la ventana de consulta [qxl1, donde d es la dimensión del espacio), y el tiempo de consulta es tq, el ventana de consulta ampliada [eqxl

*-Árbol disco. Hacemos varias modificaciones a esta estructura básica de árbol de amigos.

i son las velocidades mínima y máxima, respectivamente, de los objetos dentro de la ventana de consulta en la dimensión i. Nota que idealmente nos hubiera gustado ampliar la consulta precisamente Las velocidades de los objetos incluidos en la consulta. Althou hacemos

No tengo idea de qué objetos están en el resultado de la consulta, la velocidad máxima y mínima almacenada en los nodos es suficiente para ayudar Encontramos el resultado correcto. El siguiente teorema es sencillo y usado en el próximo TEOREMA 1. Dada una consulta q y un nodo MBR N, la consulta ampliada q′ Debe superponerse a N si N contiene al menos un objeto en el resultado 4. OPERACIONES DE BUDDY * -TREE En esta sección, proporcionamos el algoritmo detallado sobre las operaciones de Buddy * -tree, incluidas las consultas, la inserción y la eliminación. También discutimos cómo lograr una alta concurrencia en Buddy * -tree. Hay tres tipos de bloqueos en los nodos de Buddy * -tree, lea bloqueo, bloqueo de escritura y bloqueo de marca. Si un nodo se lee bloqueado, este nodo puede ser leído por otros hilos pero no puede ser escrito. Si un nodo es escritura bloqueada, no puede ser leída o escrita por ningún otro hilo. Si el el nodo está marcado como bloqueado, todas las operaciones de lectura y escritura, excepto la fusión, se puede ejecutar en él. A continuación, usamos r lock (r unlock), w lock (w desbloqueo) y m bloqueo (m desbloqueo) para denotar las operaciones de bloqueo (desbloqueo) para bloqueo de lectura, bloqueo de escritura y bloqueo de marca 4.1 consultas Entrada: r es la ventana de consulta. N y l son el puntero del nodo a ser examinado y su LBS obtenido de su nodo padre, respeto En Algo 1, proporcionamos el detalle de la búsqueda de rango recursiv /*CODIGO*/ sobre Buddy * -tree. El proceso de búsqueda es similar al de oth estructura de indexación. Para un nodo no hoja en Buddy * -tree, el algoritmo recupera todos los elementos secundarios con superposición con el expandido consulta y poner todos estos elementos secundarios en la lista de nodos para ser visitados más tarde (línea 5 a línea 13). Luego, el algoritmo visita y busca más los nuevos nodos creados por otros hilos en la cadena de enlace derecha de nodo actual (línea 14 a línea 20). Según el teorema 1, el algoritmo de consulta no puede faltar a ningún nodo que contiene al menos un punto en el resultado de la consulta. Por lo tanto, puede siempre genera el resultado correcto en todos los casos. El bloqueo de lectura se ejerce en el nodo cuando el algoritmo de búsqueda de rango intenta recuperar el nodo secundario. Tal cerradura se usa también durante el proceso de búsqueda de nodos desinstalados en la cadena correcta para obtener el LBS correcto. 4.2 Inserción Para insertar un punto en Buddy * -tree, nuestro sistema primero calcula el ubicación del punto en el momento de referencia del árbol. Entonces el Se invoca la operación de búsqueda de ubicación simple para localizar la hoja nodo en Buddy * -tree cuyo LBS cubre el punto. En Algo 2, nosotros presentar la implementación recursiva de cómo insertar una entrada en un

Buddy * -nodo de árbol. Dado el nodo para insertar el punto, el algoritmo primero encuentra el nodo correcto si existen nodos divididos desinstalados (línea 1 a línea 4). Si el nodo para insertar todavía tiene espacio para una nueva entrada, el el algoritmo lo inserta directamente en él (línea 5 a línea 7). De otra manera, se invocan algunas operaciones divididas, seguidas de recursivas operación de inserción en el padre del nodo (línea 9 a línea 18). /*código*/ El bloqueo de escritura se ejerce en un nodo en dos casos. El primer caso sucede cuando el algoritmo intenta insertar una entrada al nodo. El segundo caso ocurre cuando el algoritmo encuentra un desinstalado dividido, mueve el cursor y el bloqueo de escritura a los nodos correctos en la cadena 4.3 Eliminación La operación de eliminación es similar a la operación de inserción. En el primer paso, el nodo hoja que contiene s se ubica primero, seguido de Algo 3 para eliminar la entrada y fusionar su padre si es necesario. En Algo 3, presentamos el proceso detallado de eliminación de una entrada del árbol. El algoritmo primero ubica el nodo correcto por atravesando la cadena derecha (línea 1 a línea 4). La entrada que contiene el punto se elimina directamente si se encuentra en el nodo correcto (línea 5 a la línea 8). Una vez que el nodo resultante tiene muy pocas entradas, fusionando se invoca operaciones si el vecino correcto en la cadena correcta es su /*código*/ amigo en el árbol de amigos *. El proceso de fusión finaliza después de el padre de los dos nodos elimina uno de los amigos (línea 9 a línea 19). Observamos que la operación de fusión puede retrasarse debido a el bloqueo de marca ejercido por la operación de consulta. El bloqueo de escritura se ejerce en la mayoría de los tres nodos del algoritmo, incluyendo el nodo N que contiene s, el vecino derecho de N M y su padre P. 4.4 Análisis de punto muerto No puede haber un punto muerto entre dos hilos en el sistema. Analizamos las situaciones en función de las operaciones de los hilos como sigue. Dos hilos del mismo tipo de operaciones deben estar a salvo de punto muerto, ya que los hilos deben bloquear los nodos en la misma dirección. Para un hilo de consulta y un hilo de inserción, puede no hay fecha límite, ya que el nodo de consulta puede leer el bloqueo como máximo uno nodo al mismo tiempo, mientras que el nodo de inserción puede esperar el lanzamiento de la misma. Para un hilo de inserción y un hilo de eliminación, ellos También están libres de puntos muertos, ya que ambos hilos funcionan de abajo hacia arriba en el árbol. Para un hilo de consulta y un hilo de borrado, en el de primera mano, el bloqueo de lectura del hilo de consulta no puede tener un punto muerto con el bloqueo de escritura del hilo de borrado. Por otro lado, el bloqueo de marca se libera después de que el hilo de consulta ejerce la lectura bloquear, por lo que tampoco puede bloquear el hilo de borrado

5. EVALUACIÓN EXPERIMENTAL Implementamos el árbol Buddy * y comparamos su rendimiento. a la del TPR * -tree y Bx -árbol. Todas estas estructuras fueron implementado en C. Todos los experimentos se realizaron en un solo CPU 3G PentiumIV Computadora personal con 1 G bytes de memoria. Realizamos dos conjuntos de experimentos, uno con un solo hilo de actividad y otro con múltiples hilos concurrentes. En ambos conjuntos de experimentos usamos conjuntos de datos uniformes sintéticos. La posición de cada objeto en el conjunto de datos se elige aleatoriamente en un 1000 × 1000 espacio. Cada objeto se mueve en una dirección elegida al azar con un velocidad elegida al azar que va de 0 a 3. Construimos el índice en el tiempo 0. Los parámetros utilizados en los experimentos se resumen en la Tabla 1, y los valores predeterminados se resaltan en negrita.