Similitud Bsqueda sin rupturas: el OMNI -Familia de All- Purpose Mtodos de acceso

El diseo de un nuevo mtodo de acceso al interior de un comercial DBMS es engorroso y caro. Proponemos una familia de mtodos de acceso a mtricas que son rpidos y fciles de implementar en la parte superior de los mtodos de acceso existentes, tales como recorrido secuencial , R trees y Delgado -rboles. La idea es elegir un conjunto de objetos como focos y evaluar todas las otro objeto con sus distancias de este conjunto. Mostramos cmo definir el conjunto de cardinalidad focos , cmo elegir los focos adecuados, y la forma de realizar las bsquedas por rangos y vecino ms cercano utilizando ellos, sin falsos despidos . Los focos aumentar la poda de los clculos de distancia durante el procesamiento de consultas. Adems ndice que las distancias de cada objeto en la focos para reducir la desigualdad comparaciones incluso triangulares. Los experimentos en conjuntos de datos reales y sintticos muestran que nuestros mtodos igualan o superan a los mtodos existentes. Son hasta hasta 10 veces ms rpidos, y realizar hasta 10 veces menos distancia clculos y accesos de disco. Adems, escalar bien, exhibiendo el rendimiento sub - lineal con el tamao creciente base de datos.

1. Introduccin
El crecimiento de las aplicaciones multimedia en los ltimos aos ha empujaron los sistemas de gestin de bases de datos para apoyar la ms diversa y datos complejos, tales como imgenes dinmicas y estticas, el tiempo series, huellas dactilares, las secuencias de protenas, etc Por lo general, este tipo de los datos se busca mediante la bsqueda de informacin similar a la que el usuario tiene a la mano. Suponemos que el dis-similitud (o distancia) funcin que se utiliza en las comparaciones es una funcin de medicin (vase Seccin 2). Como la evaluacin similitud de objetos multimedia puede ser costoso y consume tiempo, tenemos en cuenta el nmero de clculos de distancia como un factor a ser reducido. Nuestra tcnica de elegir una serie de objetos de la base de datos como " focos " , de la que los clculos de distancia para responder a las consultas pueden ser podados . Se demuestra que esta tcnica se puede utilizar con otras estructuras de indexacin existentes , mejorando su rendimiento en trminos de clculos de distancia . A esto le llamamos "Omni -concept " , debido a que el foco se puede utilizar tanto como puntos de referencia mundiales para cualquier objeto de la base de datos y se utiliza para mejorar cualquier subyacente estructura del ndice . Su uso con una estructura de ndice existente genera una nueva estructura del ndice , lo que lleva a una nueva clase de mtodos de ndice, que llamamos el "Omni - familia " . Este documento hace las siguientes aportaciones: 1. Se proporciona una tcnica completa y prctica para reducir la nmero de clculos de la distancia necesaria para responder similitud consultas, utilizando un conjunto de unos pocos objetos seleccionados de la base de datos . Cuando el costo de clculo de la distancia es alta , esta

tcnica da un buen rendimiento incluso si la consulta se recuperan mucho ms ms del diez por ciento del conjunto de datos. 2. En l se explica cmo definir un nmero suficiente de objetos para ser utilizado como Omnifocos, con la mejor solucin de compromiso entre el aumento los requisitos de memoria y clculos de distancia decreciente. 3. Se describe un algoritmo de bajo costo para seleccionar Omnifoci adecuados. 4. Se muestran los resultados de la aplicacin del concepto de Omni con secuencial exploracin y R- rboles, alcanzando un mximo de diez veces menos clculos de distancia, accesos de disco y el tiempo global. El resto del trabajo se estructura de la siguiente manera. la siguiente seccin resume algunos conceptos relacionados. Seccin 3 encuestas de las principales estructuras de ndices actuales y muestra cmo utilice la desigualdad triangular para aumentar el rendimiento. Tambin hay una descripcin de los conjuntos de datos utilizados en nuestros experimentos. Seccin 4 introduce el concepto de Omni y presenta tanto una manera de elegir el nmero de focos y un algoritmo para elegir ellos. Seccin 5 describe cmo explotar el concepto de Omni con acceso existente mtodos, a saber, el anlisis secuencial, rboles B + y R- rboles. Seccin 6 presenta experimentos que muestran el comportamiento de los dos miembros de la Omni- familia y una comparacin con los actuales mtodos de acceso. Seccin 7 presenta las conclusiones de este trabajo.

2. Fondo
En esta seccin se presentan las definiciones bsicas que delimitan el alcance de este trabajo. 2.1. Espacios mtricas y consultas de similitud Definicin 1 (funcin de medida de distancia): Dado un conjunto de objetos S = {S1, S2, ..., SN} de un dominio S, una funcin d () que tiene las siguientes propiedades: 1. Simetra: d (s1, s2) = d (s2, s1) 2. No negatividad: 0 <d (s1, s2) <, s1 s2 y d (S1, S1) = 0 3. Tringulo de la desigualdad: d (s1, s3) d (s1, s2) + d (s2, s3) se llama una funcin de distancia mtrica . Un espacio mtrico es un par M = <S, d()> que sigue el mencionado propiedades. Conjuntos de datos espaciales a raz de una distancia de Lp- mtrica funcin (como distancias euclidianas) son casos especiales de espacios mtricos. Se consideraron dos tipos de consultas de similitud: consultas de rango y consultas vecinos ms cercanos, que se definen de la siguiente manera. Definicin 2 (consulta Range): Dado un objeto de consulta SqS, y la bsqueda de la mxima distancia rq, la respuesta es el subconjunto de S tal que RQUERY (Sq ,rq) ={Si|Si S:d ( Si, sq )rq }. Un ejemplo de una consulta de gama en un conjunto de datos con la palabra Funcin de distancia Ledit es: " Busca las palabras que estn dentro de la distancia 3 de la palabra ' Alemania ' ".

Definicin 3 (consulta vecino ms cercano): Dada una consulta objeto SqS, el vecino ms cercano es el subconjunto unitario de S tales que NNquery (Sq)={ SnS| SiS : d(Sn,Sq)d(Si,Sq ) } . Una variacin comn es la consulta vecino k - ms cercano. Lo encuentra el k N objetos ms cercanos a Sq del conjunto de datos . Un ejemplo de una consulta k- vecino ms cercano, con k = 5 es: " Seleccione las 5 palabras ms cercano a ' Alemania ' ". Una propiedad til para disminuir el nmero de distancia clculos es la desigualdad triangular. Genricamente, una mtrica Mtodo de acceso, MAM, divide el conjunto de datos en regiones o nodos y elige los objetos estratgicos para ser representantes de cada regin. Los representantes, los objetos de su regin y sus distancias a los representantes se almacenan en los nodos. la nodos se organizan jerrquicamente formando un rbol . Cuando una consulta se emite, el objeto de consulta se compara primero con los representantes de los nodos, y a continuacin, la desigualdad triangular se utiliza para podar clculo de la distancia entre el objeto y objetos de la consulta nodo. En este trabajo se muestra que la propiedad de la desigualdad triangular puede ser utilizado para podar los clculos de distancia con focos fijos (poda mundial), la obtencin de mejores resultados que el uso de representantes de los nodos (poda local). 2.2. Dimensionalidad intrnseca El comportamiento de un conjunto de datos en las consultas puede ser estimado por su dimensionalidad. Varios trabajos han sido presentados en este tema, se trata de la llamada "maldicin de dimensionalidad. algunos de ellos asumir que la dimensionalidad incorporacin del conjunto de datos define este comportamiento. Si eso fuera cierto, sera mejor responder a las consultas de bases de datos con alta dimensionalidad incrustacin realizando un recorrido secuencial sencillo [22][5]. Sin embargo, la incrustar dimensionalidad no indica el comportamiento correcto del conjunto de datos cada vez, debido a un conjunto de datos puede habitar un Porcin "pequea " del espacio de inclusin. Por otra parte, mtrica conjuntos de datos no tienen una dimensionalidad incrustado en absoluto. Una mejor manera de cuantificar el comportamiento de un conjunto de datos es considerar su intrnseca dimensionalidad. Se muestra en [14] que el concepto de intrnseco (o fractal) dimensionalidad da una mejor precisin en la estimacin de la selectividad para las consultas de los vecinos ms cercanos que la dimensin de inclusin. Un desarrollo equivalente est hecho para las bsquedas por rangos en [16]. Para entender el papel de la dimensionalidad intrnseca en las consultas , considerar , por ejemplo, un conjunto de datos que representa los puntos a lo largo de una lnea. Una lnea tiene una dimensin intrnseca, sino que no importa si la lnea est incrustado en un 2 - , 3 - o cualquier ndimensional espacio. Por lo tanto, la estimacin de la selectividad de las consultas en una lnea en un Espacio de 3 dimensiones usando la dimensin incrustacin da una la figura mucho ms grande que los objetos reales en el conjunto de datos. Utilizamos la correlacin fractal dimensin D2 como una aproximacin de la dimensin intrnseca de un conjunto de datos [3][16] . Algoritmos para estimar la dimensin fractal de correlacin de vectores conjuntos de datos en tiempo lineal se representa en [12] y [19]. Para mtrica conjuntos

de datos, un algoritmo cuadrtico necesita ser utilizado [15] . Tabla 1 resume los smbolos utilizados en este trabajo. Tabla 1 - Resumen de los smbolos y definiciones. Smbolos Definiciones S dominio de objetos S conjunto de objetos en el dominio S N nmero de objetos en el conjunto de datos S D2 correlacin dimensin fractal del conjunto de datos S Sq un objeto de consulta (o centro de consulta) Si,Sj objetos de S rq radio de una consulta gama K el nmero de vecinos en una consulta NN F la base Omni-focos fk un foco de S en F l Nmero de focos en F d() funcin de distancia dfk(Si) distancia de un objeto si centrarse fk

3. trabajos relacionados
El diseo de los mtodos de acceso eficientes ha sido durante mucho tiempo un objetivo de muchos investigadores. Mtodos de acceso multidimensionales se han propuesto en la literatura, y un excelente estudio es dado en [13]. Sin embargo, la mayora de estos mtodos slo funcionan para datos vectoriales. En cuanto a los conjuntos de datos de imgenes, algunos trabajos han utilizado los objetos seleccionados como puntos de referencia para podar los clculos de distancia [4] y organizar estructuras de ndices [17]. El trabajo seminal de Burkhard y Keller [ 9 ] proporciona diferentes tcnicas interesantes para particionar un conjunto de datos de medicin donde el proceso recursivo se materializa como un rbol . La primera particiones tcnica de un conjunto de datos por la eleccin de un representante de el conjunto y la agrupacin de los elementos con respecto a su distancia de ella . Los segundos particiones tcnica el conjunto original en un fija el nmero de subconjuntos y elige un representante de cada de los subconjuntos . El representante y la distancia mxima por el representante de un punto del subconjunto correspondiente son Tambin mantiene para admitir las consultas de vecinos ms cercanos . La mtrica rbol de Uhlmann [ 20 ] y el rbol atalaya ( vp tree ) de Yanilos [ 23 ] son de alguna manera similar a la primera tcnica de [ 9 ] como que se particionar los elementos en dos grupos de acuerdo a un representante, llamado un punto de vista. En [ 23 ] el rbol de VP ha sido generalizado a un rbol de mltiples vas . Con el fin de reducir el nmero de los clculos de distancia , Baeza -Yates et al [ 2 ] sugiere el uso de el mismo punto de observacin en todos los nodos que pertenecen a la misma nivel. Entonces , un rbol binario degenera en una simple lista de vista puntos . Otro mtodo [20] es la hiper - plano generalizado rbol ( gh - rbol ) , que divide el conjunto de datos en dos por recoger dos puntos como representantes y asignar el resto a la representante ms cercano . Bozkaya y Ozsoyoglu [7]

[6] propuso una extensin del rbol de vp llamado rbol de multi- punto de ventaja ( mvp -tree ), que elige en un m forma inteligente los puntos de vista de un nodo que tiene una convergencia de salida de m2 . La zona de acceso geomtrica rbol ( GNAT ) de Brin [8] se puede ver como un refinamiento de la segunda tcnica presentada en [9] . Guarda las distancias entre pares de representantes, adems de la representante y la distancia mxima. Estas distancias se pueden utilizar para podar el espacio de bsqueda utilizando la desigualdad del tringulo. Una excelente encuesta de los rboles de mtricas se puede encontrar en [10]. Algunos mtodos para conjuntos de datos presentados anteriormente son mtricas esttica, en el sentido de que la estructura de datos se construye una vez, y la nueva inserciones no son compatibles. El M-rbol de la Ciaccia, Patella y Zezulla [11] fue el primero MAM para superar esta deficiencia. El rbol-M es un rbol de altura-equilibrada en la que los elementos de datos son almacenado en las hojas. El Slim-tree [18] es otra dinmica MAM, lo que reduce la cantidad de superposicin entre los nodos del rbol. Con un proceso de slim-down" de un rbol, que conduce a un menor nmero de los accesos a disco para responder a las consultas de similitud.

4. El Omni-concepto y definiciones
En esta seccin se presenta la tcnica propuesta, que utiliza un conjunto de focos mundial para podar los clculos de distancia. Este concepto se puede utilizar ya sea solo, potenciando exploracin secuencial o con MAM existentes, generando as el Omni-familia de la indexacin mtodos. Los elementos de la Omni-concepto se presentan como siguiente. Definicin 4 - Omni- focos base ( F ) : Dado un espacio mtrico M = <S,d()>, una base Omni - focos es un conjunto F = { f1 , f2 , ... , fl | fk S , fk fj , l N } donde cada fk es un enfoque ( o punto focal ) de S , y l es el nmero de atencin en la base de Omni- focos . Definicin 5 - Omni- coordenadas : Teniendo en cuenta el objeto si S y la base de F Omni- focos , el Omni- Ci coordenadas de un objeto Si es el conjunto de las distancias entre tomos de Si a cada foco en F , que es Ci = {< fk,d(fk,Si)> , fk F}. Para distinguir la distancia d(fk,Si) como coordenadas , se utiliza la notacin dfk (si) = d ( fk , si) . la cardinalidad de Ci es el mismo nmero l de los focos en el Omnifoci F base. Cuando se inserta un nuevo objeto en el conjunto de datos, sus Omnicoordinates son evaluados y almacenados. Durante una bsqueda, el Omni- coordenadas se utilizan para podar los clculos de distancia a travs de la propiedad de la desigualdad del tringulo. El costo de usar focos proviene de dos fuentes: el tiempo de calcular el Omni- coordenadas de cada objeto en S , y el espacio de memoria en una estructura de datos para almacenar el Omni coordenadas . Consideramos que tanto el Omni- coordenadas y los conjuntos de datos son almacenado en el disco. Los discos son baratos, as que el espacio de memoria no es un cuestin. Sin embargo, el aumento de uso de disco requiere ms accesos a disco , ralentizar el proceso de respuesta de consulta. Suponiendo que se necesitan pocos focos, tanto los costos se pueden mantener bajo. Reivindicamos los clculos de distancia adicionales necesarias entre los objetos y los focos dar sus

frutos durante el proceso de consulta. La prueba prctica se muestra en la Seccin 6 corrobora esto. Para analizar el uso de la memoria, debemos tener en cuenta la demanda desde el Omni coordenadas relativas a la memoria necesaria para almacenar los objetos en s. Los objetos complejos y grandes, tales como imgenes y audio, necesitan gran memoria, por lo que el espacio necesario para mantener unos nmeros adicionales que las distancias tienda es relativamente insignificante. Sin embargo, el aumento de la memoria necesaria para almacenar la Omni coordenadas con objetos ms pequeos es a primera vista ms significativo. Nosotros sostenemos el correspondiente aumento de los accesos al disco no es relevante, ya que los clculos de distancia de poda compensa la reduccin de accesos a disco. De esta manera, mundial focos reduce drsticamente el nmero de clculos de distancia, sin cualquier otro costo importante. Es tambin digno de mencin que el costo de implementacin de los conceptos de Omni es baja, debido a la simplicidad de la estructura y las operaciones necesarias. 4.1. La base Omni- focos Las cuestiones de la eleccin de la base de F focos y su cardinalidad l estn estrechamente relacionados. Hay una compensacin entre el nmero de focos y el espacio y el tiempo invertido para procesarlos. Por lo tanto , se Es importante para maximizar la ganancia con el nmero mnimo de focos . Para descubrir un nmero tal que tenemos el siguiente concepto. Definicin 6 - mnimo que circunscribe Regin Omni (MBOR): dada la base de Omni - focos F={f1 ,f2,... , fl } y una coleccin de objetos A = { x1 , x2 , ... , xn } c S , el MBOR de A se define como la interseccin de los intervalos de mtrica RA = |Ii, donde Ii = [min ( d (xj,fi) ), max (d(xj,fi) ) ] , 1 i l , 1 j n. Como podemos ver en la figura 1, cada enfoque define una mtrica sub - espacio " ring". Un MBOR es el subconjunto de S contenida en el hiper - volumen que el Omni- coordenadas identifica como incluido la respuesta de una consulta, es decir, la regin en la que los objetos no pueden ser podado por los focos. Tenga en cuenta que una MBOR siempre incluye todas objetos del conjunto de respuestas (no hay despidos falsos), aunque que puede incluir objetos que no estn en el conjunto de respuesta, (hay falsas alarmas) para una etapa final de refinamiento se debe aplicar. Slo de este refinamiento paso de la distancia real de que el candidato se calcula objeto para el objeto de consulta.

Figura 1 - espacio activo definido por: (a) uno de los focos; (b) dos focos.

Un enfoque es adecuado si se reduce el MBOR notablemente. Teniendo en cuenta conjuntos de datos espaciales, es inherente que el intrnseca dimensin y la funcin de distancia definen un lmite para el buen nmero de focos. Figura 2 ( a) ilustra esta idea mostrando una lnea (un conjunto de datos de una sola dimensin ) incrustado en una de dos dimensiones espacio teniendo en cuenta la funcin de distancia L2 , donde una consulta gama se poda por uno de los focos ( Figura 2 ( b ) ) y dos focos ( Figura 2 ( c ) ). Teniendo en cuenta la familia de Lp- mtrica de funciones de distancia, el doble de la dimensin intrnseca sera suficiente para maximizar el beneficio. Seleccin de ms focos de dos veces la dimensin intrnseca de la conjunto de datos , independientemente de la dimensin de inmersin , no conduce a ninguna o una pequea reduccin en el MBOR. Dos focos conducen a la reduccin mxima del MBOR si que son " ortogonal " , muy separados , y coincidiendo con el origen con el centro de consulta. Sin embargo, ya que los focos estn predefinidos , que no puede asumir ortogonalidad . Adems, en los conjuntos de datos mtricos no es siempre es posible crear objetos "artificiales" para actuar lo ms alejados focos, por lo que la reduccin mxima no siempre se puede lograr. en de esta manera uno de los focos ms se puede utilizar para " distribuir " la sobrecarga de tener focos no en una posicin ideal para cada consulta. El uso de este adicional enfoque, la nueva reduccin media mxima se produce si estn lejos aparte y a igual distancia el uno del otro. Estos requisitos son ms fciles de conseguir en un espacio mtrico. Por lo tanto, un buen nmero de para la cardinalidad de l sera entre el nmero entero que contiene la dimensin intrnseca D2+1 y 2*D2+ 1. Tenga en cuenta que aunque utilizamos conjuntos de datos espaciales para lograr estos resultados, con exclusin de las consideraciones funcin de distancia, la mismo proceso deductivo se puede repetir utilizando conjuntos de datos mtricos, por lo que son vlidas para cualquier conjunto de datos mtrica. Por lo tanto, se propone la tras gua prctica para elegir la base de Omni- focos: Elija D2+ 1 igualmente espaciados focos, que son los ms lejos posible el uno del otro, que rodea la otra objetos de la base de datos.

Figura 2 - Una consulta de rango con el centro de cuadrados y rq en un radio de conjunto de datos. La sombra ilustra los objetos incluidos en la MBOR. (a) No se centran, por lo que todo el conjunto de datos es el candidato conjunto de respuestas. (b) Un foco F1. (c) dos focos F1 y F2. La nica informacin acerca de los objetos necesarios para obtener el focos es la distancia entre ellos, que se conoce en el sistema mtrico espacios. Dos focos se eligen para conjuntos de datos con una dimensin intrnseca uno o menos, correspondientes a los ms alejados par de objetos del conjunto de datos. Recursos de datos con 1 <D22 dar lugar a tres focos definir un tringulo equiltero; conjuntos de datos con 2 <D23 se conducir a cuatro focos que definen un tetraedro, y as sucesivamente.

4.2. Cmo elegir los focos: el algoritmo de HF Aqu se describe la aplicacin algortmica de la directrices propuestas. El algoritmo debe elegir slo los objetos dentro del conjunto de datos para ser focos porque a veces es imposible para sintetizar un objeto del conjunto de datos, por ejemplo, una nueva huella digital. Esto conduce a focos no est idealmente ubicado, ni que rodea el conjunto de datos ni el posicionamiento de los vrtices de un tetraedro. En segundo lugar, el algoritmo para encontrar la "mejor" focos tiene complejidad O (N! / (Nl)!), donde N es el nmero de objetos en el conjunto de datos, y l es la nmero de focos.

Figura 3 - Dada focos F1 y f2, seleccione la tercera entre S1, S2, S3 y S4. Lo mejor es s4. Te mostramos un algoritmo prctico requiere O(N) Distancia clculos, que tratan de encontrar los focos cerca del casco de la conjunto de datos, el algoritmo de HF. Este algoritmo comienza a buscar un par de objetos distantes. Para ello, se elige al azar un objeto s1, encontrar el objeto ms lejano f1 de este objeto, y configurarlo como el primer enfoque. Despus, se encuentra el objeto ms lejano de f2 f1, estableciendo como el segundo foco, y el almacenamiento de la distancia entre como borde. El prximo objetivo ser el objeto que tiene el ms similar distancias a los focos previamente elegido (vase la Figura 3). Para ello, utilizando los focos ya elegido, para cada objeto si an no escogido como un enfoque, calcular el siguiente error:

Ahora, seleccione como el prximo objetivo de la IS objeto que produjo el mnimo error i. Este ltimo paso se repite hasta que se selecciona el nmero necesario de focos. HF-Algoritmo: la bsqueda de los focos del conjunto de datos S Entrada: el conjunto de datos S y el nmero de focos l Salida: focos conjunto F comenzar 1. Elige al azar un objeto si 0S. 2. Encuentre la f1 objeto ms lejano de si. Inserte f1 en . 3. Encontrar el objeto ms lejano de f2 f1. Inserte f2 en . 4. Establezca borde d = (f1, f2), que se utiliza para calcular error i. 5. Si bien hay focos que se encuentran, hacer: 6. Para cada Si S, Si F: calculan error i 7. Seleccione Si S tal que Si F y error i es mnimo. 8. Inserte Si en F. Fin. Figura 4 - HF-El algoritmo para encontrar el conjunto de focos.

El algoritmo de HF requiere l * N distancia clculos y se muestra en la Figura 4. Tenga en cuenta que los clculos de distancia requieren en los pasos 3 y 6 de la Figura 4 corresponden a distancias de cada objeto de especial atencin, por lo que se calculan las distancias de todos modos , ya que son parte de la Omni - coordenadas de cada objeto. Por lo tanto, los clculos adicionales distancia realizadas por este algoritmo son slo las que se producen en el paso 2, que representa el slo N clculos adicionales distancia . Por lo tanto , el algoritmo de HF tambin prepara el Omni- coordenadas de un conjunto de datos ( en los pasos 3 y 6). El algoritmo de HF no requiere el conjunto de datos completo a elegir Omni- coordenadas. Los experimentos han demostrado que una buena focos se puede obtener en un muestreo bien distribuido. Los objetos pueden ser insertado o suprimido sin cambiar la base Omni - focos. Adems, la base Omni - focos se puede cambiar sin afectar a la underlaying mtodo de ndice, en el coste de volver a calcular los Omnicoordinates.

5. Los miembros de la familia OmniEl concepto de Omni es efectivo para clculos de distancia de poda en tanto vecino ms cercano y consultas de rango. Aqu presentamos cmo utilizar el Omni -conceptos, junto con anlisis secuencial, rboles B y R- rboles. 5.1. El Omni- secuencial Para realizar un anlisis secuencial el conjunto de datos se lee. La algoritmos para responder a las consultas de similitud son simples: Consultas Rango: Lea todo el conjunto de datos comparando el objeto de consulta cuadrados con cada objeto en Si el conjunto de datos. cuando la distancia resultante es menor o igual a la rq radio de consulta , Si es colocado en el conjunto de respuestas. Consultas vecino K ms cercanos: Asigne la primera k objetos de el conjunto de datos a un conjunto de respuestas de trabajo, segn sus distancias para el objeto de consulta Sq La distancia ms grande se utiliza como la corriente rc radio de bsqueda. Entonces, cada uno de los objetos restantes Si se lee y se en comparacin con Sq Siempre que la distancia es menor que la corriente consulta de radio rc, el objeto ms lejano en el conjunto de respuestas de trabajo es sustituido por el presente si, y rc se actualiza en consecuencia. El tratamiento de ambas consultas termina cuando el conjunto de datos que se ha ledo. En ambos casos, el nmero de clculos de distancia N es el nmero de objetos en el conjunto de datos. Aplicando el concepto de Omni a exploraciones secuenciales requiere un segundo archivo para almacenar el Omni- coordenadas, compuesta por registros N, uno para cada Omni - coordenada. Hemos llamado a la exploracin secuencial modificado por el concepto de Omni, Omni-secuencial. En este nuevo mtodo de acceso, una gama consulta con rq radio de consulta se ejecuta como en una convencional exploracin secuencial, con los siguientes dos modificaciones. En primer lugar,

calcular la distancia dfk (sq) del objeto de consulta cuadrados a cada centrarse fk, creando el Omni-coordenadas dfk (sq) de Sq. En segundo lugar, preceder al clculo de la distancia del objeto de consulta Sq entre Si objeto del conjunto de datos por el siguiente clculo: para cada fk F hacer: si | dfk (Si) - dfk (Sq) |> rq continuacin, vaya el clculo de la distancia. Las modificaciones en el algoritmo de k-vecinos ms cercanos estn similares. Para ambos tipos de consultas, un objeto del conjunto de datos es recuperada del archivo y en comparacin con el objeto de consulta solamente cuando no se puede enfocar podarlo. Esto permite una gran reduccin de los el nmero de clculos de distancia, como se muestra en la Seccin 6. 5.2. El rbol OmniR Aqu se muestra cmo almacenar la Omni- coordenadas usando uno R -tree , a travs de la estructura del ndice mtrica llamamos OmniR -tree. Los beneficios de utilizar un rbol de OmniR sobre R -rboles son de dos tipos: primero, que permite el uso de I -rboles incluso para conjuntos de datos no vectoriales; segundo, por vectores conjuntos de datos que permite reducir la dimensionalidad de los MBR de la R - rbol para el nmero de focos adoptadas . la nmero de focos est relacionada con la dimensin intrnseca y no a la generalmente mayor dimensin incorporacin utilizado por un R tree normal. Por lo tanto, la dimensionalidad del conjunto de datos visto como Omni-coordenadas ser menor, mejorar el rendimiento de la R-tree. Los algoritmos para hacer la insercin, la particin de nodo, el rango consultas, etc en OmniR rboles son los mismos utilizados en la llanura R rboles. Sin embargo, el algoritmo para realizar consultas k vecinos ms cercanos- necesita ser reemplazado. Hay dos enfoques. El primero uno es estimar un radio final , como se describe para el rbol de OmniB. Este enfoque se puede utilizar con cualquier aplicacin de R - rbol, por lo que no se adapta al uso de R -trees con Omniconcepts. El segundo enfoque utiliza el algoritmo de vecinos ms prximo, utilizada en rboles de mtricas. En este caso, un profundo - bsqueda se realiza primero a encontrar k -candidatos. El algoritmo contina reduciendo el radio siempre que se sustituya el vecino ms, hasta que todas las entradas que se solapa con la radio en la consulta ha sido probado. Se utiliz este acercarse a evaluar los datos presentados en la siguiente seccin. Estos enfoques no garantiza despidos falsos, un elemento esencial propiedad de que la costumbre ms cercano algoritmo vecinos del R-tree no se puede garantizar si se utiliza con Omni -concepts. OmniR -rboles tambin utilizan dos estructuras de datos para almacenar la base de datos: un rbol de R para almacenar el Omni- coordenadas y una directa paginado acceder a archivos para almacenar los objetos en el conjunto de datos (almacenamiento de mltiples objetos por pgina). Cada vez que un nodo de hoja en el rbol - R se recupera, y Omni- coordenadas almacenados en este nodo clasificar objetos, se debe calcular la distancia real. Por lo tanto, cada clasificacin objeto debe ser recuperada a partir del archivo secuencial. Para reducir disco accesos en el archivo de la secuencia, es til almacenar los objetos siguiendo el orden en que aparecen en los nodos de hoja del rbol - R. Esta reordenacin no necesita ser hecho despus de cada actualizacin en-el rbol de R, pero es valiosa despus de grandes actualizaciones.

6. Experimentos
Para evaluar la eficacia de la Omni - concepto, nos trabajado en una variedad de conjuntos de datos, tanto reales y sintticas. Debido a restricciones de espacio, se muestra aqu nicamente los resultados de la siguiente conjuntos de datos.

Figura 5 - Resultados para el nmero de clculos de distancia (columna de la izquierda) y para el tiempo (columna derecha) la consulta de la Eigenfaces conjunto de datos al aumentar el nmero de focos. (a, d) Consulta Rango de radio rq = 0,04 (7% del conjunto de datos calificar). (b, e) consulta Rango de radio rq = 0,08 (31% del conjunto de datos calificar. (c, f) 10 vecinos ms cercanos. EnglishWords - Un conjunto de 25.143 objetos del Ingls lenguaje, utilizando la funcin de distancia Ledit. Eigenfaces - Un conjunto de 11 900 vectores cara de la Informedia proyecto [ 21 ] en la Universidad Carnegie Mellon. Cada cara fue procesada con el mtodo Eigenfaces, lo que resulta en un 16 - dimensional vector. Emplea la funcin de distancia euclidiana. Sinthetic30D - Un conjunto de datos sinttico con 250.000 objetos y treinta atributos, con una dimensin intrnseca de 9,45. Nosotros utilizarlo con la funcin de distancia euclidiana. 6.1. El nmero de focos que se utilizar Aqu nos muestran que el nmero de focos est relacionada con la dimensionalidad intrnseca del conjunto de datos. Debido a limitaciones de espacio, se muestran los resultados de un nico conjunto de datos como los otros conjuntos de datos presenta un comportamiento similar. La Figura 5 muestra el nmero de distancia clculos y el tiempo necesario para responder a rango (para radios 0,04 y 0,08) y las bsquedas del vecino k - ms cercanas ( para k = 10 ) , como un funcin del nmero de focos emplea . Los grficos muestran la Indexacin Omni- secuencial del conjunto de datos Eigenfaces , que exhibe una dimensin intrnseca de 4,67 . En la primera columna de la figura 5 podemos ver que el aumento del nmero de focos hasta siete siempre reduce el nmero de clculos de distancia, y despus de esto , este nmero comienza a aumentar de nuevo . La segunda columna de la figura 5 muestra que el tiempo reduce progresivamente cuando se utiliza un mximo de cinco focos , a continuacin, comienza a subir de nuevo . El costo de una distancia eucldea clculo en el conjunto de datos Eigenfaces , es pequeo. Con funciones de distancia ms costosos , el tiempo de respuesta sera ms estrechamente seguir a la de el nmero de clculos de distancia . Sin embargo, estas parcelas corrobora la dimensin intrnseca de la conjunto de datos como una buena referencia para el nmero de focos.

6.2. Comparando Omni- familia con otras estructuras Se compararon dos mtodos de ndice de la Omni- familia, la Omni- secuencial y el rbol OmniR, con recorrido secuencial, RTree y Slim -tree. Los conjuntos de datos utilizados fueron el conjunto de datos mtrica EnglishWords y los Eigenfaces conjunto de datos espaciales. la figura 6 muestra los resultados para el tiempo ( en segundos ), el nmero de la distancia clculos y el nmero de accesos a disco . Los resultados son el nmero medio de clculos de distancia y de disco accede para las consultas de 500 500 consultas de rango y los vecinos ms prximos. Los resultados de las bsquedas por rangos en el conjunto de datos Eigenfaces (Figuras6(a,b,c)) se presentan en escala logartmica para visualizar una ms amplia gama de radios . Tiempo mostrado son totales para responder a 500 preguntas ( Figuras 6 ( d y j ) ) . Los miembros de la familia Omni se ensayaron usando seis focos para ambos conjuntos de datos, como la dimensionalidad intrnseca de el EnglishWords es de 4.75 y de las Eigenfaces es 4,67. Es Cabe sealar que el nmero de clculos de distancia para el Omni - secuencial y para el rbol de OmniR son la misma. Es por la misma focos se utiliza para ambas estructuras. Las medidas de tiempo (Figuras 6 ( a, d , g y j ) ) y la distancia clculos ( las figuras 6 ( b , e, h y k ) ) muestran que la variacin Omni del mtodo del ndice siempre gana sobre las planas , logrando una velocidad de ms de diez veces para radios pequeos ( donde se produce la mayora de las consultas ) en consultas de rango . No podemos mostrar clculo de la distancia de R -rboles, ya que su funcionamiento se basa en comparaciones de rectngulos delimitadores. La reduccin en el nmero de los clculos de distancia es hasta cuatro veces menos en cercano consultas de los vecinos y ms de diez veces menos de radios pequeos en consultas de rango. Ambas comparaciones se realizaron con el rbol de Slim, supuestamente un buen mtodo de acceso mtrica. Hay una compensacin entre la disminucin de los clculos de distancia y el aumento de disco Accesos. Sin embargo, esta es la pena pagar como el tiempo total requerido siempre reduce.

Figura 6 - Tiempo de comparacin, el nmero de clculos de distancia y el nmero de accesos a disco de Omni-secuencial, OmniRtree, recorrido secuencial, los mtodos de acceso R-tree y Slimrbol, para consultas de rango y consultas de los vecinos ms cercanos sobre la Eigenfaces e Ingls Palabras conjuntos de datos.

6.3. Escalabilidad El Omni- secuencial y OmniR -tree son escalables en cuanto a el tamao del conjunto de datos. La figura 7 muestra el comportamiento de estos mtodos de indexacin de tiempo (a,d) , el nmero de clculos de distancia (b,e) , y accesos a disco ( c , f ) . Los resultados son la media de 500 consultas de rango con RQ = 0,5 y 500 k-vecinos ms cercanos con k = 10 . Es digno de nota que se eligi la base Omni focos el uso de una muestra aleatoria de percentil diez de la base de datos. Como hemos puede ver en la figura 7, el comportamiento de las estructuras de ndice es lineal para las bsquedas por rangos. Curiosamente, nuestros mtodos presentan sublinear el comportamiento de los vecinos ms cercanos, por lo que estos mtodos una excelente opcin para indexar grandes bases de datos.

Figura 8 - Escalabilidad de OmniR-rboles Omni-secuencial y para la gama (columna izquierda) y los vecinos ms cercanos (columna derecha) consultas, en Syntethic30 conjunto de datos. (a, d) Tiempo. (b, e) Nmero de clculos de distancia. (c, f) Nmero de accesos a disco.

7. Conclusin
Presentamos el Omni- concepto, que tiene la intencin de gama aceleracin y consultas vecinos ms cercanos al disminuir el nmero de clculos de distancia. Se demuestra cmo este nuevo concepto puede utilizarse a mtrico ndice y datos vectoriales con cualquier indexacin mtodo. Por ejemplo, mostramos cmo las palabras de ndice con Rtrees ! Debido a su adaptabilidad, Omni- concepto puede ayudar a mejorar la realizacin de cualquier mtodo ya implementado en aplicaciones tales como sistemas de gestin de bases de datos. Y debido a su simplicidad esto se puede lograr sin lgrimas. Nuestros experimentos mostraron aceleraciones de hasta diez veces en respuestas a las consultas y los resultados equivalentes para reducir clculos de distancia. Por lo tanto, se ampla el alcance de la subrayado mtodo del ndice que ya se utiliza en el DBMS comercial tambin apoyar a los conjuntos de datos mtricos. Hay otras contribuciones importantes as: la gua prctica para definir el nmero de focos, como un equilibrio entre las necesidades de espacio y clculos de distancia; y - el algoritmo de HF para elegir los focos, que es lineal en el tamao del conjunto de datos. Los miembros de la familia Omni- probados en este trabajo son escalables con respecto al tamao del conjunto de datos, que presenta un comportamiento de sub lineal con respecto al tiempo. Creemos que el concepto de Omni ser de gran contribuir a mejorar la sup3port a los datos proporcionados por mtricas sistemas de gestin de bases de datos.