|
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:
-
Integrar
datos de diferentes fuentes.
-
Navegar a través de
información.
-
Aprender y
adquirir información a partir de los datos.
-
Predecir.
-
Apoyar la toma de decisiones
-
Visualizar
información
computacionalmente.
-
Almacenar,
acceder y procesar información
digital.
-
Manejar
información no tradicional (por
ejemplo, ambiental, geográfica,
cartográfica, etc).
-
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:
-
Encontrar imágenes o
secuencias de audio o video "cercanas" a una
consulta de muestra.
-
Búsqueda aproximada en
texto.
-
En recuperación de
información, donde se define una
similaridad entre documentos y se quiere
recuperar los más similares a una
consulta.
-
En aplicaciones de
inteligencia artificial, para etiquetado
usando el punto conocido más
cercano.
-
En reconocimiento de patrones
y agrupamiento (clustering).
-
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:
-
Permite indexar la Web para
permitir búsquedas por imágenes
y secuencias de audio similares.
-
Permite recuperarse de la
mala calidad de los textos que existen en la
Web.
-
Permite encontrar
rápidamente páginas Web
relevantes a una consulta.
-
Permiten entender el
contenido de las imágenes y la
semántica de los textos para obtener
búsquedas más
sofisticadas.
-
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.
|