Buscar:   
Centro de Investigación de la Web D.C.C. - 

		Universidad de Chile

Areas de investigación

Bases de Datos y Recuperación de Información
El procesamiento de la información es un gran problema en la actualidad, porque muchos problemas interrelacionados aparecen en base a la necesidad de:

  1. Integrar datos de diferentes fuentes.
  2. Navegar a través de información.
  3. Aprender y adquirir información a partir de los datos.
  4. Predecir.
  5. Apoyar la toma de decisiones
  6. Visualizar información computacionalmente.
  7. Almacenar, acceder y procesar información digital.
  8. Manejar información no tradicional (por ejemplo, ambiental, geográfica, cartográfica, etc).
  9. Confrontar la falta de estructura en nuevos tipos de datos, como objetos complejos o la Web.

Todos estos problemas tienen distintas restricciones que definen distintos tipos de bases de datos. Nuestra investigación se focaliza en los tres últimos problemas, los que incluyen recuperación de información multimedial, información espacial, datos semiestructurados y agentes Web. En el corazón de estos problemas está la búsqueda combinatorial de patrones, área que estudia desde un punto de vista combinatorial cómo buscar un conjunto de patrones dado en estructuras regulares y discretas tales como secuencias (strings) y grafos. Esta área debe distinguirse de la búsqueda de patrones clásica, que considera elementos continuos y usa técnicas diferentes.


Sistemas Distribuidos y Redes
Llamamos sistema distribuido a cualquier sistema multi-procesador donde cada procesador tiene una memoria local, no compartida con el resto de los procesadores. La única forma de comunicación entre los procesadores es el envío de mensajes a través de una red de comunicaciones. Para dar una interfaz de más alto nivel al programador, se requiere construir un ambiente de ejecución distribuido de software.

El foco principal es en problemas de la Ciencia de la Computación, dejando de lado la implementación de hardware y la red física. Sin embargo, se podría incluir la investigación en protocolos para redes particulares. Un tema esencial en este área es la escalabilidad del sistema. Con el éxito de la Internet, nos enfrentamos con la posibilidad de una red global distribuida que cubre el planeta completo (también llamado mega-programación). Otro tema básico es el paralelismo. Después de dos décadas de investigación en hardware y software paralelos, han surgido nuevas aproximaciones al tema. Por una parte, el hardware ha convergido a computadores independientes interconectados por una red. En un nivel global, esto se ve en la Internet, y a nivel local en las redes locales de PCs. Por otra parte, la programación de algoritmos portables no puede tomar en cuenta ningún detalle del hardware. Por ello, es interesante explorar nuevos modelos de programación paralela de modo de determinar cuáles son más adecuados para aplicaciones masivas en Internet.


Búsqueda combinatoria en imágenes y audio.
La comunidad de procesamiento de señales, tradicionalmente ha enfocado el problema de medir la similaridad entre dos imágenes o secuencias de audio (o partes de ellas) salvando pequeñas diferencias debido a la escala, orientación, iluminación, estiramiento, etc. (en el primer caso) y de tiempos, volumen, tono, ruido, etc. (en el segundo caso). Siempre se ha usado un enfoque de procesamiento de señales continuas. Un enfoque alternativo reciente al calce de audio e imágenes es combinatorio más que de procesamiento de señales. El audio o la imagen se ven como un texto en una o dos dimensiones, donde se buscan patrones en una o dos dimensiones. Se han obtenido varios resultados sobre búsqueda de imágenes permitiendo rotaciones, escalamientos, diferencias en los valores de los puntos y estiramientos, en muchos de los cuales hemos estado involucrados. Lo mismo ha ocurrido en búsqueda en archivos musicales usando técnicas derivadas de biología computacional. Aunque el grado de flexibilidad que se obtiene es aún inferior al del enfoque de procesamiento de señales, se han conseguido algoritmos de búsqueda mucho más rápidos. Estos resultados son alentadores y planeamos continuar trabajando en esta línea.


Búsqueda combinatoria en audio.
Al igual que en las imágenes, se ha intentado el enfoque combinatorio en audio, usando técnicas derivadas del conocimiento adquirido en el área de búsqueda de patrones en secuencias biológicas. Esto es especialmente interesante en datos MIDI, donde se puede buscar con las técnicas clásicas de procesamiento de señales. Dado que hemos estado involucrados por mucho tiempo en el desarrollo de este tipo de algoritmos de búsqueda de patrones, planeamos trabajar en aplicarlos a la búsqueda en audio. Búsqueda aproximada en texto. El texto, por otro lado, se puede considerar como un medio donde se puede buscar por similaridad, en vez de buscar cadenas exactas. La búsqueda aproximada en texto lo ve como una cadena de símbolos y busca recuperar las ocurrencias de patrones incluso cuando no están correctamente escritas (en el patrón o en el texto). Esto permite básicamente recuperarse de errores de ortografía, tipeo, reconocimiento óptico de caracteres, etc. Nosotros hemos trabajado por mucho tiempo en este problema y planeamos seguir trabajando en algoritmos más rápidos y su adaptación a la problemática particular de las máquinas de búsqueda en la Web.


Métodos de acceso por similaridad
En todos los casos mencionados antes, el problema no se soluciona sólo con desarrollar algoritmos rápidos y precisos para comparar imágenes, secuencias de audio, textos, etc. Dada una consulta, existirán millones de elementos en la base de datos multimedial, y no podemos compararlos uno a uno. Más aún, las consultas pueden ser más complejas que sólo una medida de similaridad, dado que pueden involucrar relaciones complejas entre varios objetos. Se necesitan métodos de acceso eficientes que permitan recuperar rápidamente los elementos que satisfacen los criterios de la consulta. Sólo con esa tecnología podemos esperar ver la Web como una base de datos multimedial. Planeamos contribuir a esta investigación en varios aspectos. Respondiendo consultas estructurales. Una consulta estructural es aquella expresada por un conjunto de objetos espaciales y un conjunto de relaciones entre cada par de estos objetos. Consultas basadas en ejemplos, dibujos o comandos extendidos del SQL en Sistemas de Información Geográficos son ejemplos de consultas estructurales. Los objetos en estas consultas no son necesariamente descritos por sus extensiones espaciales en un espacio Euclidiano, sino por sus características distinguibles (como por ejemplo, color, textura, forma y tamaño), o por sus clasificaciones semánticas (por ejemplo, edificios y caminos). Las relaciones espaciales son usualmente un subconjunto de relaciones topológicas, de orientación y distancia. Responder a una consulta estructural implica encontrar instancias de objetos en las bases de datos que satisfacen las restricciones espaciales. A diferencia de trabajos previos en esta área, nosotros planeamos combinar el significado de los con sus características e interrelaciones espaciales para el procesamiento de la consulta. Algoritmos de búsqueda en espacios métricos. La búsqueda por similaridad es un tema de investigación que abstrae varios de los ya mencionados. El problema se puede expresar como sigue: dado un conjunto de objetos de naturaleza desconocida, una función de distancia definida entre ellos que mide cuán diferentes son, y dado otro objeto llamado la consulta, encontrar todos los elementos del conjunto suficientemente similares a la consulta. Varios de los problemas que hemos mencionado se pueden convertir en problemas de espacios métricos:

  1. Encontrar imágenes o secuencias de audio o video "cercanas" a una consulta de muestra.
  2. Búsqueda aproximada en texto.
  3. En recuperación de información, donde se define una similaridad entre documentos y se quiere recuperar los más similares a una consulta.
  4. En aplicaciones de inteligencia artificial, para etiquetado usando el punto conocido más cercano.
  5. En reconocimiento de patrones y agrupamiento (clustering).
  6. En compresión con pérdida (audio, imágenes, video) para encontrar rápidamente el marco (frame) más parecido visto antes; etc.

Todas estas aplicaciones son importantes para buscar en la Web ya que:

  1. Permite indexar la Web para permitir búsquedas por imágenes y secuencias de audio similares.
  2. Permite recuperarse de la mala calidad de los textos que existen en la Web.
  3. Permite encontrar rápidamente páginas Web relevantes a una consulta.
  4. Permiten entender el contenido de las imágenes y la semántica de los textos para obtener búsquedas más sofisticadas.
  5. Permite obtener mejor compresión de datos multimediales, lo que es esencial para la transmisión por una red lenta como Internet. La búsqueda en espacios métricos es bastante nueva como área.

Por esta razón, es aún bastante inmaduro y abierto al desarrollo de nuevos algoritmos y aplicaciones. Hemos trabajado intensivamente en este área en los últimos años y planeamos continuar en el marco de este proyecto.


Manejando información semiestructurada
El uso generalizado de la Web ha convertido a HTML en un estándar de factor para intercambiar documentos. HTML es una simplificación de SGML, un lenguaje de especificación de texto estructurado diseñado originalmente con el objetivo de que fuera un lenguaje universal para intercambiar y manipular texto estructurado. Una derivación reciente de SGML, XML, está ganando espacio rápidamente en la comunidad. Es bastante posible que XML reemplace a HTML en el futuro, y se están haciendo grandes esfuerzos para estandarizarlo, definir un lenguaje de consulta apropiado, etc. La estructura que se puede derivar de un texto en ningún caso es similar a la relacional, que se puede separar en campos y registros fijos y tabulada acordemente. Los textos tienen una estructura más compleja y difusa, que en el caso de la Web es un grafo. El diseño e implementación de lenguajes de consulta y manipulación para bases de datos textuales estructuradas, incluyendo para la Web, es un área de investigación muy activa. Existen actualmente varias propuestas para un lenguaje de consulta sobre XML. Nosotros hemos contribuido al área de búsqueda en texto estructurado y al caso particular de implementar XQL eficientemente. Planeamos continuar trabajando en lenguajes de consulta eficientes sobre XML, desarrollando prototipos para consultar datos en XML. La capacidad de consultar eficientemente XML (y HTML como un caso simplificado) abrirá la puerta a mejoras de las máquinas de búsqueda Web actuales, tales como incorporar predicados sobre la estructura de los documentos.


Modelación Matemática y Simulación de la Web
La última década se ha caracterizado por una creciente demanda por aplicaciones basadas en Internet que sean capaces de recuperar y procesar eficientemente información esparcida en inmensos repositorios tales como la Web. Sin embargo, es sabido que realizar predicciones detalladas del comportamiento de tales aplicaciones es extremadamente difícil puesto que la Internet no solo crece a una tasa exponencial sino que también experimenta cambios dramáticos en uso y topología durante el tiempo. Cómo realizar análisis de desempeño razonables de elementos de software interactuando con un sistema tan grande y complejo es una pregunta abierta. Toda la problemática tiene similitud con las condiciones de escala en física estadística donde los fenómenos interesantes sólo surgen en modelos suficientemente grandes. Un modelo que sea lo suficientemente grande y bueno tiene alguna probabilidad de exhibir esas raras y críticas fluctuaciones que parecen surgir regularmente en la Internet real. Es claro que los enfoques analíticos dejan de ser adecuados rápidamente en tales situaciones. Por lo tanto, una simulación validada mediante datos empíricos es potencialmente la única herramienta que puede permitir el análisis de diseños alternativos bajo distintos escenarios. Actualmente, el problema de modelar y simular la Internet global está recibiendo poca atención. Como resultado, no se ha realizado trabajo alguno en el desarrollo de ambientes de simulación realistas para la predicción del desempeño de sistemas de recuperación de la información que operen en la Internet. En lo inmediato, anticipamos oportunidades únicas de investigación productiva en el desarrollo de estrategias más convenientes para recorrer la Web completa y sus modelos de simulación asociados que permitan que estas estrategias sean analizadas y rediseñadas antes de su implementación real y prueba. Los modelos de simulación adecuados pueden ciertamente permitirnos explorar tendencias futuras en la siempre cambiante Internet o en el presente, bajo condiciones que son imposibles de reproducir a voluntad en la red real. Un problema específico es comprender la estructura y características de la Web, incluyendo tanto su comportamiento temporal como su comportamiento de uso. Esto último implica el análisis de registros (logs) y minería de datos. Otro problema importante es recorrer la Web para obtener páginas nuevas y actualizadas. Este es un problema difícil de asignación de tareas que puede ser modelado matemáticamente y simulado.


Ambientes de Computación Distribuida
La compleja distribución del poder de cálculo en la Internet hace imposible usar los paradigmas tradicionales de programación para desarrollar aplicaciones para todo Internet. Nuestro grupo de investigación ha estudiado nuevas aproximaciones al problema utilizando el paradigma de Agentes Móviles. La idea principal es programar pequeños agentes que migran de un computador a otro, utilizando pequeñas fracciones de la CPU en cada etapa, recolectando información y tomando decisiones basadas en su conocimiento acumulado. De vez en cuando, pueden volver a su computador de origen, para depositar sus resultados en una Base de Datos. Aunque existe bastante investigación en el mundo en torno a los agentes, sorprendentemente, existen muy pocas plataformas disponibles que los implementen. Nosotros hemos construido una plataforma en Java (llamada Reflex) que provee un ambiente de agentes móviles funcional, que sirve para probar estas ideas con comportamientos dinámicos. Los agentes móviles son un paradigma poderoso para realizar mega-computación en Internet, sin embargo, muchos puntos están aún abiertos para tener una plataforma confiable y robusta: los agentes deben ser robustos (tolerantes a fallas), manejar objetos remotos (invocación remota de métodos, recolección de basura), migrar con su estado entre máquinas heterogéneas (migración de threads), deben soportar objetos replicados (consistencia, buscador de objetos) y deben ser adaptables a condiciones cambiantes (de redes de alta velocidad a redes inalámbricas). Por otra parte, es deseable que colecciones locales muy grandes de datos complejos tales como documentos multimediales de la Web, sean manejados en tiempos de ejecución razonables por servidores dedicados. Los agentes y usuarios reales siempre requivirán el menor tiempo de respuesta posible. La computación paralela puede ser entonces una herramienta efectiva para el desarrollo de servidores de alto desempeño que sean capaces de procesar miles de peticiones por minuto. Las aplicaciones basadas en la Web presentan nuevos desafíos en esta materia. Por ejemplo, hasta ahora se ha realizado poca investigación en el procesamiento paralelo eficiente de consultas sobre documentos de la Web. Para servidores transaccionales, anticipamos nuevos tópicos de investigación tales como la sincronización eficiente de secuencias de operaciones de lectura/escritura originadas desde un gran número de agentes/clientes concurrentes que utilizan los servicios del servidor. Las similitudes con el problema de la sincronización de eventos en simulación paralela son evidentes y es interesante estudiar la manera en que nuevas técnicas desarrolladas en esta área pueden ser aplicadas.


Compresion e indexacion de texto

El de esta área es explorar las relaciones entre la compresion de texto y sus indices, ya que ambas se basan en explotar las regularidades del texto. Esta es una linea de investigacion que ha recibido mucho empuje en los ultimos años.

     
 

Departamento de Ciencias de la Computación
Universidad de Chile
Blanco Encalada #2120
Santiago, Chile

iniciativa cientifica milenio Preguntas/Comentarios: ciw@dcc.uchile.cl
Ultima modificación:
Servicios de búsqueda por: Ir a todocl.cl

El Centro de Investigación de la Web (CIW) es posible gracias al Programa Iniciativa Científica Milenio
Iniciativa Científica Milenio, Ministerio de Planificación y Cooperación - Gobierno de Chile

Valid HTML 4.01! Valid CSS!


dcc