Areas
Areas
The current areas of research being conducted within the group are:
Digital Image-Video
Digital video image and is an active area of research that attracts the attention of a number of institutional research groups and R & D departments of companies and organizations throughout the world.
The advance of technology, communications and content distribution tools has led to an unprecedented expansion of the use of the image in our daily activities. And this explosion in the use we make of the image (both fixed and moving) on the web is the main vehicle for expansion.
Social networking, blogging platforms like Google Images and YouTube made available to users with tools that help us and also encourage their use. No wonder that some of the image is an important research activity focuses on finding solutions to new problems a few years ago we had not even raised.
It is in this context GIM research develops its main activity. In this section you will find relevant information about this activity, but before we get into it, we will introduce a little more detail, the context of our research.
Multimedia Retrieval
What is Multimedia Information Retrieval?
The multimedia information query by example (Multimedia Information Retrieval, MIR) is a search system to retrieve similar information (videos, images, sounds, etc.) based on its content. In the case of images (Content-Based Image Retrieval, CBIR), the features are treated according to their context in relation with colors, shapes, textures or any other information that may result from the image itself.
Most of the techniques used in CBIR from the viewpoint of image processing are based on the field of Pattern Recognition and Image Analysis, where the main objective is the classification of objects in a number of categories or classes. If we work with videos (Content-Based Video Retrieval, CBVR), the techniques can be very similar, incorporating in addition features such as movement, relations between frames, quick changes between scenes, etc.. (digital video processing).
This does not conflict at all with the classic treatment of this information in databases by metadata (tags) or additional textual information can be entered automatically (eg, date of collection, device characteristics, making parameters , etc.) or manually (author, descriptive labels in the document, etc.).
Information should be indexed to reach an efficent (fast) and effective retrieval. Therefore metadata are meaningless for large image collections and the automatic indexing and retrieval are considered based on what is in the multimedia information according to its content or features (primitive or processed properties).
In these types of searches the subjectivity of human perception greatly affects the outcome of the queries. Thus, the automatic feature extraction through computational methods must take into account this human factor. It is sometimes quite difficult to obtain similar results computationally and the user really wants. This discrepancy is what is called semantic gap. The computational characteristics is not that high semantic content that have the human perceptual characteristics. Hence this is the reason for MIR systems.
MIR Processing
MIR phases of processing
Considering a possible rendition of a full-MIR (figure 1), then spent a brief description of the different phases, considering the object to an image pattern, ie as if that were a CBIR system.
Figure 1.- Representation of a MIR system
1. Digital image (pattern object): A digital image is a two-dimensional representation of an image using bits (ones and zeros). Digital images can be modified using filters, add or delete items, resize, etc. and stored inin a data recording device such as a hard disk . Most digital image formats are composed of a header that contains attributes (dimensions of the image, encoding, etc.), followed by the image data itself. The structure of attributes and the image data is different in each format.
2. Pre-processing (optional): In many cases, digital images that serve as a starting point for a computational analysis, or a human interpretation, show some degradation in quality.
It is therefore necessary improvement, for example by removing unwanted objects within the image, transforming it in such a way as to enhance the efficiency of subsequent processing steps (Figure 2).
2.1. Point or pixel processing: When the resulting value depends only on its value in the corresponding pixel. For example, the operator of the contrast transformation.
2.2. Group processing or local filtering: When the resulting value depends on its neighborhood. For example, operations of convolution, morphological operators, operators of median, etc.
2.3. Global processing: When the resulting value in a point depends on a function dependent on all points of the image. For example, Fourier transform, the wavelet, etc.
Figure 2.- Preprocessed image to highlight the edges of the famous picture of Lena
3. Feature extraction: For humans, most of the scenes are easy to interpret and understand, although they contain much information. For a computer (software and hardware) images are sets of pixels.
Feature extraction is a transformation or a change in the representation of an image. Normally the space or frequency domain, the domain named features that allow us to discriminate between different scenes or objects.
4. Feature selection: It is interesting to select the most important features, reducing the dimensionality and maintaining a high discriminatory capacity.
Not cost effective to design a system that requires many features to differentiate between a few samples. An efficient system is the one with fewer features can successfully differentiate a large number of patterns.
5. Indexing features: Selecting the features that help the system to differentiate a large number of patterns of these features are indexed in a multidimensional database (Figure 3).
Indexing refers to the action of an orderly register in preparing its index information with the purpose to get results quickly and substantially relevant when performing a search.
A multidimensional database is a structure based on dimensional oriented complex queries and high performance. In our case, an attribute or query key for each of the features extracted during the selection phase.
Figure 3.- Multidimensional indexing of images
6. Machine Learning: It is a system capable of classifying an unknown pattern or key pattern in one or more predefined classes. These systems always assume that there is a set of sample patterns of known class training set to provide relevant information to the computer to perform the classification task (Figure 4).
6.1. Un-supervised learning is carried out from a set of patterns, which is not known some class. Sometimes not even know the number of classes. Basically, it means finding clusters. The aim is usually to verify the validity of all classes for a supervised classification.
6.2. Supervised learning requires having a set of patterns which are known to a certain class. This set is called training set. This type of training is called supervised training and supervised classifiers classifiers thus obtained.
Having a training set means that someone has concerned to label the patterns that set. This task is usually performed an expert in the field that will provide recognition and generally is imposed.
Figure 4.- Search for the most similar images to one given
The knowledge of the systems of perception and learning would be helpful for designing computer systems that allow us to search for certain patterns. However, the human visual system is too complex and so far, there is no method to emulate in its entirety. This causes the information processing systems are highly dependent multimedia context to solve.
Activity
The MIR group activity
Within this context, the first national project of the group (Ministry of Education and Science) was Imagine: Picture Manager, more specifically entitled Summary of Characteristics of Middle / High Level Application semantics and indexing methods on Distances in the Process of Search Content-Based Image (Ref. TIN2005-05939).
The result of this project was other national project (Ministry of Science and Innovation), which is currently running vManager: Video Manager, titled From Qatris vManager iManager. Strategies for storing and searching document collections of digital video (Ref. TIN2008-03063). Figures 5, 6, and 7 show images of these projects.
Figure 5.- Logos of the projects Imagina (2005-2008) and vManager (2009-2011)
Figure 6.- Dividing a video into scenes by scenebreaks
In order to contribute in this field, our group started their research at the end of the previous decade, addressing short-range projects that were obtaining oriented results. This allowed us to advance our understanding and mastering the techniques present in the area of storage and retrieval of multimedia documents and particularly in image collections.
The maturity of the results and the conviction to make a real contribution in the development of efficient solutions to search for content in images, led us to create in 2003 the company SICUBO SL, the first spin-off of the University of Extremadura, as a tool to facilitate the transfer of research results from our group and in order to exploit commercially the results derived from our research.
Other companies with which they are actively working group Dnovae Digital Media working in the field of digital video and Quota Solutions working with ERP systems.
Figure 7.- Screenshot of the vManager application showing the results of a similarity search
More detailed information about research activities of our group can be found by accessing the research.
Results
Main results
As a group belonging to the public system of research, one indicator of our work lies in publishing. However, in addition to the public dissemination of knowledge, our group has a practical nature irrevocable transfer of results, so that all our projects are supported by a spirit of transfer, the most efficient way possible, our results to employers. In this regard, the main contributions of the group are that:
|
|
Qatris iManager. Freely distributed CBIR application designed and developed within the research group GIM. Qatris iManager is an application for classifying and searching for content in image collections. The application uses Bayesian logistic regression to automatically classify images that are added to the collection and facilitates the search for similarity in three different areas of color, texture and shape. Additionally it allows to locate images according to a pattern of color and textures given by the user. Qatris iManager is constantly evolving and can be downloaded free for use. |
|
|
Qatris iCatalog. Commercial application to facilitate business document management developed by SL SICUBE ICatalog Qatris incorporates much of the digital imaging algorithms developed by GIM. In particular feature extraction algorithms, detection of shapes using active contours, multidimensional indexing, classification, Bayesian logistic regression, semantic similarity measures and others. Is now thebase packages and Docugest Contalink currently marketed SICUBO, S.L. |
Besides this, a number of experimental tools and applications are available to visitors within our website. The sections of applications and downloads are kept permanently updated with the latest developments of the group.
Representative systems
Other representative systems
In multimedia information retrieval, CBIR systems have progressed significantly in the first decade of the century XXI. In this second decade is the shift to CBVR systems for video retrieval.
Here we give a list of examples of retrieval systems based on content, where the centerpiece is the still image. It is hoped that this list will soon begin to incorporate digital video-based systems.
|
|
Visual Geometry Group. División del grupo de investigación Robotics Research Group de la Universidad de Oxford cuya investigación se centra en reconocimiento visual de imágenes en movimiento como películas o series de televisión. En su página web se encuentran enlaces a sus diferentes investigaciones como:
Para leer otras investigaciones de este grupo pulsa aquí. |
|
|
Image, Processing & Retrieval. Trends. Interesantísimo blog del Dr. Savvas A. Chatzichristofi s. Actualmente se encuentra en el Centro de Investigación y Tecnología Hellas (CE.R.T.H.). Su investigación se centra en la recuperación de imágenes, procesamiento de análisis de imágenes y reconocimiento de patrones. En su blog se encuentra dos aplicaciones:
|
|
|
Tiltomo. Página web donde se prueban nuevos algoritmos de búsqueda, en base a color o textura, de imágenes. En la web tenemos la oportunidad de poder realizar consultas a su colección de imágenes. Tiene la opción de realizar consultas en base a:
La colección de fotos usada son fotos de flickr, aproximadamente unas 140.000. Los algoritmos utilizados en la búsqueda son propietarios y privados. |
|
|
Idée es una compañía privada cuyo principal objetivo es el desarrollo de reconocimiento avanzado de imágenes y software de búsqueda visual. Ha desarrollado varios productos comerciales con éxito como la herramienta web TinEye. En su página web podemos encontrar dos demostraciones de lo que puede hacer su software de búsqueda de imágenes.
|
|
|
TinEye es un buscador de imágenes "inverso" que localiza de dónde procede una imagen, cómo se usa o si existen versiones modificadas de la misma. Utiliza las imágenes de la web como base de datos para comparar. Esta herramienta es muy útil para comprobar el origen de la imagen y si existen más versiones de esta porque esta indexando constantemente en la web (cerca de 2.000.000.000 de imágenes en su base de datos y creciendo constantemente). La forma de búsqueda es subir a su web la imagen a buscar o introducir la URL si la imagen se encuentra ya colgada en la web. Los principales navegadores tienen extensiones para utilizar TinEye de una forma mucho más sencilla. Es un software comercial y se puede usar con objetivos no lucrativos. |
|
|
xcavator.net es un buscador de imágenes profesionales. Las búsquedas son gratuitas pero si nos gusta una imagen encontrada en la web tendremos que pagarla para descargarla y usarla aunque algunas imágenes son libres. La búsqueda comienza escribiendo una o dos etiquetas, a continuación ya podemos elegir el color predominante de nuestra búsqueda o seleccionar una imagen y que se realiza otra búsqueda por similitud a esta. |
|
|
Incogna es un buscador de imágenes web, la principal diferencia con respecto a otros es que utiliza procesadores paralelos para acelerar las búsquedas. Utiliza GPU´s (Unidad de Procesamiento Gráfico) como hardware para realizar las consultas. Las consultas se pueden realizar escribiendo textualmente una o dos etiquetas o pinchando imágenes para una búsqueda de similitud. |
|
|
VIRaL es una aplicación desarrollada por el grupo de investigación IVA (Image and Video Analysis) perteneciente a la universidad de Atenas. La principal característica de VIRaL (Visual Image Retrieval and Localization) es que realiza consultas de imágenes por similitud y devuelve una estimación de la localización de la imagen. Utiliza para ello la característica de geolocalización de la imagen. Realiza búsquedas y las compara con imágenes que se encuentran en Google Maps, de esta manera puede reconocer y estimar la localización de la imagen. Esta herramienta utiliza como base de datos imágenes de flickr. Por ahora solo realiza búsquedas sobre ciudades europeas. |
|
|
ALIPR (Automatic Linguistic Indexing of Pictures Real-Time) es un sistema de indexación lingüística de imágenes en tiempo real automático. ALIPR enseña al ordenador a reconocer el contenido de las fotografías etiquetando de forma automática las imágenes. El enfoque básico ha sido tomar un gran número de fotos (60.000) para etiquetarlas manualmente con variedad de palabras clave que describen sus contenidos. A continuación se crea un modelo estadístico para enseñar al ordenador a reconocer patrones en el color y la textura de estas 100 fotos, así como para asignar esas palabras clave a nuevas fotos que puedan contener valores similares. Actualmente es capaz de etiquetar de forma automática usando 322 palabras de habla inglesa. |
|
|
imense es una empresa privada cuyo objetivo es la venta de software centrado en búsqueda de imágenes por contenido o por etiquetas. Ha desarrollado varias aplicaciones como búsqueda de imágenes (picturesearch), búsqueda por similitud (similarsearch) y autoetiquetado de imágenes (autotagger).
|
|
|
imgSeek es un programa con licencia GPL y para un uso individual desde un ordenador personal. Puede buscar imágenes similares (por su contenido) a una dada o a un esbozo pintado por el usuario. También acepta búsquedas usando palabras clave. Esta herramienta utiliza la transformada de wavelet en el algoritmo de búsqueda de imágenes similares. Es similar a la transformada de Fourier, pero codifica la frecuencia y la información espacial de cada imagen cuando es indexada en la base de datos. En la aplicación se usa la transformada wavelet para mantener unos pocos coeficientes (20) para cada canal de color y extraer de ellos una firma muy pequeña ''para cada imagen". Debido a que la firma es tan pequeña permite una búsqueda muy rápida en la base de datos. Sin embargo, ha demostrado ser un método eficaz para discriminar las imágenes. |
|
|
Ikona es un software que utiliza la arquitectura cliente-servidor para la construcción de un sistema CBIR, diseñado e implementado por el equipo de investigación Imedia perteneciente a INRIA (Institut national de recherche en informatique et en automatique). La parte del servidor de este motor CBIR está escrito en C++ (por razones de velocidad) y la parte cliente está escrito en Java y que normalmente debería funcionar en cualquier arquitectura de computadora que admita Java Runtime Environment (JRE). De forma predeterminada, el servidor realiza "la recuperación por similitud visual", en respuesta a una pregunta, lo que significa que busca todas las imágenes en la base de datos y devuelve una lista de las imágenes similares visualmente a la imagen de la pregunta. Si una base de datos de imagenes ha sido anotada con palabras clave, el servidor puede usar estas palabras clave para una recuperación rápida. Este prototipo permite también consulta de la región y se ha basado en modo híbrido de recuperación de texto-imagen. En el modo región, el usuario puede seleccionar una parte de una imagen y el sistema de búsqueda de imágenes (o partes de imágenes) consultará la parte seleccionada en la base de datos. |
|
|
MI-File (Metric Inverted File for efficient and scalable similarity search, Fichero métrico invertido para la búsqueda de similitud eficiente y escalable) es un motor de búsqueda que utiliza la colección CoPhIR y tiene actualmente indexada 106 millones de imágenes. La idea propuesta para la consulta de imágenes es utilizar el espacio métrico. Si dos objetos están muy cercas en el espacio métrico la visión de estos dos objetos con respecto al mundo que les rodea también es similar. Esto implica que, si tenemos un conjunto de objetos de la base de datos y se ordenan de acuerdo a sus similitud, las ordenaciones obtenidas son también similares. Básicamente es que se puede aproximar la semejanza entre dos objetos arbitrarios, mediante la comparación de la ordenación. De acuerdo a su similitud con estos dos objetos con un grupo de objetos de referencia, en lugar de utilizar la función de la distancia real entre los dos objetos. |
|
|
MUVIS es un framework para la gestión (indexación, navegación, consulta, etc) de colecciones multimedia como audio y vídeo e imágenes fijas. Esta aplicación ha sido desarrollada por un equipo de investigación de la Universidad de Tampere, finlandia. MUVIS hospeda aplicaciones para audio en tiempo real y captura de vídeo, codificación, creación de bases de datos, la conversión multimedia, indexación y recuperación. Proporciona una interfaz bien definida para integrar de forma dinámica (en tiempo de ejecución), extracción de características visuales y auditivas. El framework de MUVIS esta formado por los siguientes componentes:
MUVIS contiene tres aplicaciones diseñadas para el sistema operativo Windows:
|
|
|
PIRIA es el acrónimo del Programa para la Indexación de las imágenes de Investigación por Afinidad (Program for Indexing and Research Images by Affinity). Desarrollado en LIST (Laboratoire d' Intégration des Systèmes et des Technologies, Laboratorio de investigación aplicada en tecnologías de software intensivo), Francia. Es un motor de búsqueda de imágenes basada en contenido, esto significa que el contenido de la imagen (color, textura, formas ...) se analiza para buscar imágenes similares a una consulta de una imagen. Se utilizan varias características de los descriptores de color, la textura y la forma para crear un índice (o firma). La aplicación se encuentra alojada en la web, el visitante selecciona una imagen y acto seguido se devuelve la consulta. La consulta se puede distinguir si queremos realizar segun el color, la forma o la textura. La colección de fotos es la utilizada por el profesor J. Wang. |
|
|
RETIN permite crear de forma interactiva categorizaciones semánticas de imágenes en bases de datos generalistas. Desarrollado por ETIS (Equipes Traitement de l'Information et Systèmes, Equipos de Tratamiento de la Información y Sistemas) una unidad perteneciente a ENSEA, Francia. Inicie la búsqueda haciendo clic en una imagen (que dirige su fondo verde), a continuación, haga clic en el botón "actualizar". Imágenes relevantes se seleccionan haciendo clic en ellos (fondo verde), los irrelevantes haciendo doble clic (fondo rojo). Algunos iteraciones permitirá enriquecer la categoría, lo que muestran las imágenes que pertenecen a la misma categoría en la misma pantalla. |
|
|
SIMBA (Search IMages By Appearance, Búsqueda de IMágenes por Apariencia) es una aplicación para la consulta de imágenes. Ha sido desarrollada en la Universidad de Freiburg, Alemania. El enfoque se basa en características invariantes, es decir, características que no varían si la imagen es transformada por algún grupo de transformación. Schulz-Mirbach presentó un algoritmo para la construcción de invariantes características [Schulz-Mirbach: 1995], que es muy adecuado debido a su robustez ligero deformaciones topológicas e incluso al movimiento independiente de los objetos dentro de la imagen. La principal ventaja es que no requiere la extracción de objetos (segmentación), o puntos distintos (puntos clave) de la imagen, pero se puede aplicar directamente a los datos de la imagen original. Para mejorar la robustez del algoritmo en una aplicación de recuperación de imágenes - sobre todo para apoyar a las coincidencias parciales - se modificó para que la información local se conservará en las características finales. Así se construyó la función de histograma [Siggelkow, Burkhardt: 1998], que son muy similares a los histogramas de color pero tiene en cuenta las características extraídas de una zona local de cada píxel en lugar de usar sólo el valor del color de cada píxel. La información de textura se tiene en cuenta. |
|
|
VITALAS (Video & image Indexing and reTrievAl in the LArge Scale, Indexación y Recuperación en gran escala de Video e imagen) es el resultado de un proyecto europeo de investigación cuyo objetivo es proporcionar una solución avanzada para la indexación, búsqueda y acceso a gran escala de contenidos audiovisuales digitales. El logro de VITALAS se basa en el desarrollo de eficiente de métodos avanzados de la descripción del contenido informativo, aprendizaje robusto hacia la anotación automática de búsqueda y contenido interactivo. Los objetivos del sistema de VITALAS se basan en tres actividades básicas:
El proyecto VITALAS desarrolla nuevos funcionalidades y servicios tecnológicos teniendo en cuenta todos los medios de comunicación (visuales, textuales y audio) para facilitar el acceso a contenidos multimedia de grandes bases de datos. Las funcionalidades del sistema proporciona la base sistemas y tecnologías de multimedia intuitiva, servicios de búsqueda, en la actualidad se enfrenta a un fuerte cuello de botella tecnológico. |
|
|
Windsurf (Wavelet-based INDexing of ImageS Using Region Fragmentation, Indexación basada en wavelet de imágenes usando fragmentación de región) es un proyecto desarrollado por la Universidad de Bolonia, italia. Windsurf es un framework para el procesamiento eficiente de las consultas de imágenes basadas en contenido. Con especial hincapié en el paradigma basado en regiones, windsurf proporciona un entorno donde las diferentes alternativas del paradigma puede ser implementado. Esto permite que las implementaciones de estos se comparen sobre una base justa, desde el punto de vista de la eficacia y eficiencia. Windsurf aborda el problema de la recuperación de imágenes basada en regiones (RBIR), proporcionando técnicas eficientes para el procesamiento de consultas que se plantean en este contexto. Dado que el framework es ampliable, se puede aprovechar las técnicas de procesamiento de consultas en Windsurf por instancias del framework. Para ello, Windsurf proporciona una biblioteca de Java que incluye clases que pueden ser ampliables para realizar el modelo RBIR que se requiera. Está compuesto por cuatro módulos:
|
|
|
Pixolution es una empresa privada ubicada en alemania donde han desarrollado varias aplicaciones para la gestión y búsqueda de imágenes. Su objetivo es reducir el tiempo necesario que el usuario dispone para discriminar en las búsquedas. Han desarrollado tres herramientas:
En este enlace se puede descargar y probar la herramienta ImageSorter, es un programa que permite ordenar visualmente de manera automática las fotos e imágenes del ordenador, así como realizar búsquedas. También se existe una herramienta con igual función que la anterior pero que busca imágenes por internet, pixolu es un prototipo que demuestra las posibilidades de un sistema de búsqueda de imágenes, en él se combina la búsqueda por palabras clave tradicional con la ordenación visual de las imágenes, la búsqueda por similitud visual así como el aprendizaje semiautomático de las relaciones semánticas entre imágenes. |
|
|
Gazopa es un servicio de búsqueda de imágenes similares en la web desarrollado por Hitachi. Los usuarios pueden buscar imágenes de la web usando como referencia la propia foto, bocetos realizados por el usuario, las imágenes que se encuentran en la web y palabras clave. GazoPa permite a los usuarios buscar una imagen similar de características tales como un color o una forma extraída de una imagen en sí misma. Utiliza características de la imagen para buscar otras imágenes similares, una amplia gama de imágenes se pueden recuperar de la web. |
Multidimensional Indexing
Organizing the multidimensional space
Multidimensional indexing structures play an essential role in many applications such as computer graphics, computer vision, computational geometry, image processing, geographic information systems, pattern recognition, document management multimedia computational biology, and so on. In almost all these fields of application, data (records, objects, documents, etc.) usually can be displayed (sometimes only in a approximated form) through multidimensional points, where each dimension represents an attribute from data. In most of the above applications, the volume of data is too heavy to be stored in main memory. In these cases, multi-dimensional indexing facilitates the data storage and helps to boost the process of searching specific data. The main goal of multidimensional indexing techniques is therefore to minimize the number of disk accesses required to respond to queries issued by the user.
An important aspect in this context is the kind of query to be processed on these data. For example, in a relational database that stores information about employees, a typical query may seek employees who live in a city, or who are in an age range, or a combination of them. But imagine that the records from the database store a photo of the employee, how can we solve a query asking about the picture attribute?. It is not trivial to answer the query "show me the employee under this image" especially as the image may not be exactly the same (different light conditions, different approach, different colors, ...) as it is stored in the database. What is most usual in this context is to answer queries by similarity to a given pattern. For example, we can provide the system a pattern image in order to look for a similar image in the database. Or we can have a specific profile and look for objects that fit the profile. In general, we refer these queries as similarity search.
Mapping for the search
The usual way of conducting a similarity search is to transform each object from the database into a multidimensional point (capturing ideally the features defining the object, that is called feature vector) and to model the search as a retrieval of the nearest neighbours ( "nearest neighbor search" or "nn-search") in the multidimensional space. The similarity among objects is usually implemented by means of a distance, so that close objects are considered similar. In specific applications, such as spatial databases, similarity and proximity can be considered synonyms, so that the Euclidean distance is a proper election to measure the similarity between objects. However, in a number of other applications, the choice of a distance able to properly represent the concept of similarity is not so obvious. Different similarity functions have been examined with varying degrees of effectiveness, but the results depend heavily on the domain of application. The choice for the similarity function is directly related to the effectiveness of the process, namely the quality of the response. Although the issue of effectiveness is obviously critical, when the collection of objects is considerably large (the most common scenario) another element of the final search by similarity is the efficiency of the process, namely the time (CPU and I / S) to provide a satisfactory answer to the query. Indexing multidimensional addresses this aspect of the problem.
Metric space division
An extensive collection of multidimensional indexing methods have been proposed in the last two decades. When the similarity function is a metric (strictly positiveness, symmetry and triangular inequality), an option constitute the so-called metric indexes or indexes based on distance, which use the properties of the distance (fundamentally the triangular inequality) to filter objects or entire regions of the space. Among such indexes can categorize those that establish a division of space by means of spheres and those who divide the space by means of hiperplanes. Among the former, we can highlight the Vp-tree, or Vantage Point Tree, the mVP-tree or Multiple Vantage Point, and the M-tree or Metric Tree. Another kind of metric indexes are implemented by means of arrays that store the distance among all points in the space and a set of selected points (pivots) of the search space. Representative methods in this class are AESA and LAESA.
R-tree-based space division
When the similarity function is not a distance, or it varies with the collection of objects in the database, metric indices are inapplicable. In this case, an interesting alternative is to used indexes based on features. In this category we can distinguish between methods that grouped items in the collection by means of bounding boxes (which may overlap) as R-tree and derivatives, and access methods that carry out a partition of the feature space through iso-oriented hyperplanes, such as those based on the kd-tree data structure. Methods based on the R-tree have shown a good performance in low dimensionality (2-D and 3-D) spaces . However, in medium and high dimensional spaces, the overlap among the boxes grows exponentially and the structure becomes inefficient. Different proposals based on this structure are the X-tree, tree-TV and others that use bounding spheres to improve similarity queries, such as the SR-tree. All of them address the problem of high dimensionality in this type of structures.
Kd-tree-based space division
Among the best-known kd-tree-based indexing structures are the KDB-tree, LSD-tree and the hB-tree, which have shown good performance in range searches. But only some of them implements similarity queries. The Q-tree, an indexing method based on the kd-tree and developed within our research group, has shown good performance results in similarity search inside spaces with low and medium dimensionality (up to 25 dimensions).
Alternatively to the above methods, there are those who seek to accelerate the similarity query in bulky and highly dimensional spaces by providing approximate solutions, that is by giving as response objects that, within a certain margin of error, can be considered the closest to the query point. The LHS method (locality sensitive hashing), representative of this class, has shown good performance in some application contexts.
Among the activities of our research group is the study of multidimensional indexing. In this regard within our group we investigate different strategies for solving problems related to the similarity search, mainly in the context of voluminous collections of multimedia documents.
Links
Below are links to interesting resources multidimensional indexing:
- The R-tree Portal. One the best sites with a lot of programming resources about indexing based on R-trees. Thanks to Yannis Theodoridis, University of Piraeus. Greece.
- MESSIF. Metric Similarity Search Implementation Framework Support for the indexing based on metric space.
- Metric Spaces Library.Source code library implementing several indexing algorithms, as well as metric spaces, conforming to an API that permits adding new indexes and spaces.
- Locality-Sensitive Hashing (LSH). Description and code of the LSH algorithm. Thanks to Piotr Indyk, Massachussetts Institute of Technology.
- Implementation of LAESA method. Thanks to Maria Luisa Micó. Departamento de Lenguajes y Sistemas Informáticos University of Alicante.
- Multi-Dimensional Index Simulator, Software package with multi-dimensional access methods based on superimposed space partitioning (KDB-trees, R-trees, the Pyramid Technique, …). Thanks to Ratko Orlandic, Department of Computer Science Illinois Institute of Technology.
- The GiST Indexing Project. A C++ library that provide a template to implement multidimensional index structures. Thanks to Joe Hellerstein and Christos Papadimitriou. University of California at Berkeley.
- The M-tree project. M-tree implementation based on the GiST C++ package. The M-tree is a paginated metric index that can be used for content-based retrieval. Thanks to Paolo Ciaccia, Fausto Rabitti, Pavel Zezula and Marco Patella.
Recomended bibliography
|
Foundations of Multidimensional |
Foundations of Multidimensional and Metric Data Structures. Author: Hanan Samet. An excellent book on spatial and multidimensional access methods in general. Essential at the researcher library. |
|
Indexing Techniques for Advances Database systems |
Indexing Techniques for Advances Database systems. Authors: Elisa Bertino y otros. Review the main structures of indexing by the applications (spatial data, image data, temporary…). A good book, although more deep would be appreciated. |
|
Advanced Database Indexing |
Advanced database Indexing. Authors: Yannis Manolopoulos, Yannis Theodoridis, Vassilis J. Tsotras. Reviewing of indexing structures according to their scope (images, temporary data spatio-temporal data, etc..). A good number of references at the end of each chapter. |
|
Similarity Search |
Similarity Search: The Metric Space Approach. Authors: Pavel Zezula, Giuseppe Amato, Vlastislav Dohnal, Michal Batko. A good book on metric indexing structures. |
High Performance Computing
Main goal of High Performance Computing is to provide scientific applications in the field of physics, engineering, biology, etc. with the computational capacity of advanced computers. Hardware available for scientific applications includes from a few shared memory processors multicore machines up to supercomputers with hundreds of thousands of processors connected by high bandwidth and low latency networks.>
Our research line is about the study of different standards, languages, technologies and tools providing scientific applications with high performance, scalability and reliability needed for running in supercomputers platforms.
As result, an implementation of the MPI standard (Message Passing Interface) version 1.3 has been built, named AzequiaMPI. MPI standard allows the development of parallel applications based on tasks communicating by message passing. Tasks can run in shared and/or distributed memory machines. Most known and used MPI libraries (MPICH2, Open MPI) build each task as an operating system process, however, AzequiaMPI builds each task as a thread. Advantages of this approximation are higher performance exploiting multicore architectures and a lower memory footprint.
|
HP Lusitania supercomputer AzequiaMPI library has been ported to different platforms, including the CenitS Lusitania supercomputer (128 cores in 2x HP Integrity Superdome SX2000) and NEC SX-9 supercomputer in the HLRS (High Performance Supercomputing Center in Stuttgart), with 700 8-cores Nehalem nodes. |
|
SMT310Q. Four C6x cores linked by SDB GIM research group has a 32 cores (4 nodes 8-cores Nehalem) machine connected by Infiniband and Ehternet for developing and evaluation of AzequiaMPI and other software. Initially, AzequiaMPI was developed in Digital Signal Processor multicomputers, consisting in C6000 DSPs by Texas Instruments connected by Sundance Digital Bus (SDB) proprietary network, by Sundance Company. |
|
Xilinx FPGAs cluster AzequiaMPI modular design and its low memory footprint allowed us to port the library to platforms consisting in clusters of Xilinx FPGAs connected by TCP/IP networks. This High Performance Reconfigurable Computing platform uses Xilkernel and Microbaze software processors, and currently, a PowerPC hardware core port is under development. |
Databases and XML
XML Document
The XML standard is a consolidated tool for representation and interchange of information, due to both its flexibility and the management and conversion facilities that the documents offer in this standard. It is used in multiple purposes such as information interchange (SOAP, WSDL, ..), configuration file, XML office documents (Open-Office, Microsoft Word,...) and mainly to store information, where different approaches can be used: in a flat file, in a relational / object-oriented database or more recently in an XML Native Database.
XML information changes throughout time and its management becomes necessary to query past information, to retrieve documents belonging to a specific version or to monitor the changes. In this area we study how to represent, manage and query of XML versions.
We have developed a technique, versionstamp, for managing and querying branched versioning of XML documents, For more information, please use the folloling link:
- Information about our versioning technique. "Representing Versions in XML Documents using Versionstamp". ECDM 2006.
- How to manage versions of XML documents using our technique: "Managing Brach Versioning in Versioned/Temporal XML Documents". XSYM 2007 (VLDB Workshop).
- We have developed two demos of our XML versioning system. Both of them are based in our extension of an XML native database was extended, by means of XQuery modules, to support in a native way versioning features.