An optimal yet fast pruning algorithm to reduce latency in multiview prediction structures

We propose a new algorithm for the design of prediction structures with low delay and limited penalty in the rate-distortion performance for multiview video coding schemes. This algorithm constitutes one of the elements of a framework for the analysis and optimization of delay in multiview coding schemes that is based in graph theory. The objective of the algorithm is to find the best combination of prediction dependencies to prune from a multiview prediction structure, given a number of cuts. Taking into account the properties of the graph-based analysis of the encoding delay, the algorithm is able to find the best prediction dependencies to eliminate from an original prediction structure, while limiting the number of cut combinations to evaluate. We show that this algorithm obtains optimum results in the reduction of the encoding latency with a lower computational complexity than exhaustive search alternatives.

Analysis of the suitability of existing medical ontologies for building a scalable semantic interoperability solution supporting multi-site collaboration in oncology

Semantic interoperability is essential to facilitate efficient collaboration in heterogeneous multi-site healthcare environments. The deployment of a semantic interoperability solution has the potential to enable a wide range of informatics supported applications in clinical care and research both within as ingle healthcare organization and in a network of organizations. At the same time, building and deploying a semantic interoperability solution may require significant effort to carryout data transformation and to harmonize the semantics of the information in the different systems. Our approach to semantic interoperability leverages existing healthcare standards and ontologies, focusing first on specific clinical domains and key applications, and gradually expanding the solution when needed. An important objective of this work is to create a semantic link between clinical research and care environments to enable applications such as streamlining the execution of multi-centric clinical trials, including the identification of eligible patients for the trials. This paper presents an analysis of the suitability of several widely-used medical ontologies in the clinical domain: SNOMED-CT, LOINC, MedDRA, to capture the semantics of the clinical trial eligibility criteria, of the clinical trial data (e.g., Clinical Report Forms), and of the corresponding patient record data that would enable the automatic identification of eligible patients. Next to the coverage provided by the ontologies we evaluate and compare the sizes of the sets of relevant concepts and their relative frequency to estimate the cost of data transformation, of building the necessary semantic mappings, and of extending the solution to new domains. This analysis shows that our approach is both feasible and scalable.

Advanced Characterisation of a Coffee Fermenting Tank by Multi-distributed Wireless Sensors: Spatial Interpolation and Phase Space Graphs

The fermentation stage is considered to be one of the critical steps in coffee processing due to its impact on the final quality of the product. The objective of this work is to characterise the temperature gradients in a fermentation tank by multi-distributed, low-cost and autonomous wireless sensors (23 semi-passive TurboTag® radio-frequency identifier (RFID) temperature loggers). Spatial interpolation in polar coordinates and an innovative methodology based on phase space diagrams are used. A real coffee fermentation process was supervised in the Cauca region (Colombia) with sensors submerged directly in the fermenting mass, leading to a 4.6 °C temperature range within the fermentation process. Spatial interpolation shows a maximum instant radial temperature gradient of 0.1 °C/cm from the centre to the perimeter of the tank and a vertical temperature gradient of 0.25 °C/cm for sensors with equal polar coordinates. The combination of spatial interpolation and phase space graphs consistently enables the identification of five local behaviours during fermentation (hot and cold spots).

Application of Independent Components Analysis with the JADE algorithm and NIR hyperspectral imaging for revealing food adulteration

In recent years, Independent Components Analysis (ICA) has proven itself to be a powerful signal-processing technique for solving the Blind-Source Separation (BSS) problems in different scientific domains. In the present work, an application of ICA for processing NIR hyperspectral images to detect traces of peanut in wheat flour is presented. Processing was performed without a priori knowledge of the chemical composition of the two food materials. The aim was to extract the source signals of the different chemical components from the initial data set and to use them in order to determine the distribution of peanut traces in the hyperspectral images. To determine the optimal number of independent component to be extracted, the Random ICA by blocks method was used. This method is based on the repeated calculation of several models using an increasing number of independent components after randomly segmenting the matrix data into two blocks and then calculating the correlations between the signals extracted from the two blocks. The extracted ICA signals were interpreted and their ability to classify peanut and wheat flour was studied. Finally, all the extracted ICs were used to construct a single synthetic signal that could be used directly with the hyperspectral images to enhance the contrast between the peanut and the wheat flours in a real multi-use industrial environment. Furthermore, feature extraction methods (connected components labelling algorithm followed by flood fill method to extract object contours) were applied in order to target the spatial location of the presence of peanut traces. A good visualization of the distributions of peanut traces was thus obtained

Systematic analysis of the decoding delay in multiview video

We present a framework for the analysis of the decoding delay in multiview video coding (MVC). We show that in real-time applications, an accurate estimation of the decoding delay is essential to achieve a minimum communication latency. As opposed to single-view codecs, the complexity of the multiview prediction structure and the parallel decoding of several views requires a systematic analysis of this decoding delay, which we solve using graph theory and a model of the decoder hardware architecture. Our framework assumes a decoder implementation in general purpose multi-core processors with multi-threading capabilities. For this hardware model, we show that frame processing times depend on the computational load of the decoder and we provide an iterative algorithm to compute jointly frame processing times and decoding delay. Finally, we show that decoding delay analysis can be applied to design decoders with the objective of minimizing the communication latency of the MVC system.

Multi-sensor background subtraction by fusing multiple region-based probabilistic classifiers

In the recent years, the computer vision community has shown great interest on depth-based applications thanks to the performance and flexibility of the new generation of RGB-D imagery. In this paper, we present an efficient background subtraction algorithm based on the fusion of multiple region-based classifiers that processes depth and color data provided by RGB-D cameras. Foreground objects are detected by combining a region-based foreground prediction (based on depth data) with different background models (based on a Mixture of Gaussian algorithm) providing color and depth descriptions of the scene at pixel and region level. The information given by these modules is fused in a mixture of experts fashion to improve the foreground detection accuracy. The main contributions of the paper are the region-based models of both background and foreground, built from the depth and color data. The obtained results using different database sequences demonstrate that the proposed approach leads to a higher detection accuracy with respect to existing state-of-the-art techniques.

New definitions of margin for multi-class Boosting algorithms

La familia de algoritmos de Boosting son un tipo de técnicas de clasificación y regresión que han demostrado ser muy eficaces en problemas de Visión Computacional. Tal es el caso de los problemas de detección, de seguimiento o bien de reconocimiento de caras, personas, objetos deformables y acciones. El primer y más popular algoritmo de Boosting, AdaBoost, fue concebido para problemas binarios. Desde entonces, muchas han sido las propuestas que han aparecido con objeto de trasladarlo a otros dominios más generales: multiclase, multilabel, con costes, etc. Nuestro interés se centra en extender AdaBoost al terreno de la clasificación multiclase, considerándolo como un primer paso para posteriores ampliaciones. En la presente tesis proponemos dos algoritmos de Boosting para problemas multiclase basados en nuevas derivaciones del concepto margen. El primero de ellos, PIBoost, está concebido para abordar el problema descomponiéndolo en subproblemas binarios. Por un lado, usamos una codificación vectorial para representar etiquetas y, por otro, utilizamos la función de pérdida exponencial multiclase para evaluar las respuestas. Esta codificación produce un conjunto de valores margen que conllevan un rango de penalizaciones en caso de fallo y recompensas en caso de acierto. La optimización iterativa del modelo genera un proceso de Boosting asimétrico cuyos costes dependen del número de etiquetas separadas por cada clasificador débil. De este modo nuestro algoritmo de Boosting tiene en cuenta el desbalanceo debido a las clases a la hora de construir el clasificador. El resultado es un método bien fundamentado que extiende de manera canónica al AdaBoost original. El segundo algoritmo propuesto, BAdaCost, está concebido para problemas multiclase dotados de una matriz de costes. Motivados por los escasos trabajos dedicados a generalizar AdaBoost al terreno multiclase con costes, hemos propuesto un nuevo concepto de margen que, a su vez, permite derivar una función de pérdida adecuada para evaluar costes. Consideramos nuestro algoritmo como la extensión más canónica de AdaBoost para este tipo de problemas, ya que generaliza a los algoritmos SAMME, Cost-Sensitive AdaBoost y PIBoost. Por otro lado, sugerimos un simple procedimiento para calcular matrices de coste adecuadas para mejorar el rendimiento de Boosting a la hora de abordar problemas estándar y problemas con datos desbalanceados. Una serie de experimentos nos sirven para demostrar la efectividad de ambos métodos frente a otros conocidos algoritmos de Boosting multiclase en sus respectivas áreas. En dichos experimentos se usan bases de datos de referencia en el área de Machine Learning, en primer lugar para minimizar errores y en segundo lugar para minimizar costes. Además, hemos podido aplicar BAdaCost con éxito a un proceso de segmentación, un caso particular de problema con datos desbalanceados. Concluimos justificando el horizonte de futuro que encierra el marco de trabajo que presentamos, tanto por su aplicabilidad como por su flexibilidad teórica. Abstract The family of Boosting algorithms represents a type of classification and regression approach that has shown to be very effective in Computer Vision problems. Such is the case of detection, tracking and recognition of faces, people, deformable objects and actions. The first and most popular algorithm, AdaBoost, was introduced in the context of binary classification. Since then, many works have been proposed to extend it to the more general multi-class, multi-label, costsensitive, etc... domains. Our interest is centered in extending AdaBoost to two problems in the multi-class field, considering it a first step for upcoming generalizations. In this dissertation we propose two Boosting algorithms for multi-class classification based on new generalizations of the concept of margin. The first of them, PIBoost, is conceived to tackle the multi-class problem by solving many binary sub-problems. We use a vectorial codification to represent class labels and a multi-class exponential loss function to evaluate classifier responses. This representation produces a set of margin values that provide a range of penalties for failures and rewards for successes. The stagewise optimization of this model introduces an asymmetric Boosting procedure whose costs depend on the number of classes separated by each weak-learner. In this way the Boosting procedure takes into account class imbalances when building the ensemble. The resulting algorithm is a well grounded method that canonically extends the original AdaBoost. The second algorithm proposed, BAdaCost, is conceived for multi-class problems endowed with a cost matrix. Motivated by the few cost-sensitive extensions of AdaBoost to the multi-class field, we propose a new margin that, in turn, yields a new loss function appropriate for evaluating costs. Since BAdaCost generalizes SAMME, Cost-Sensitive AdaBoost and PIBoost algorithms, we consider our algorithm as a canonical extension of AdaBoost to this kind of problems. We additionally suggest a simple procedure to compute cost matrices that improve the performance of Boosting in standard and unbalanced problems. A set of experiments is carried out to demonstrate the effectiveness of both methods against other relevant Boosting algorithms in their respective areas. In the experiments we resort to benchmark data sets used in the Machine Learning community, firstly for minimizing classification errors and secondly for minimizing costs. In addition, we successfully applied BAdaCost to a segmentation task, a particular problem in presence of imbalanced data. We conclude the thesis justifying the horizon of future improvements encompassed in our framework, due to its applicability and theoretical flexibility.

Multi-distributed wireless sensors for monitoring a long distance transport in a reefer container

The study of the temperature gradients in cold stores and containers is a critical issue in the food industry for the quality assurance of products during transport and for minimising losses. This work presents an analysis of the temperatures during the refrigerated transport of 4,320 kg of blueberries in a reefer (set point temperature at ?1ºC) on a container ship from Montevideo (Uruguay) to Verona (Italy). The monitoring was performed by using semi-passive RFID loggers (TurboTag cards). The objective was to carry out a multi-distributed supervision using low-cost, wireless and autonomous sensors for the characterisation of the distribution and spatial gradients of temperatures during a long distance transport. Data analysis shows spatial (phase space) and temporal sequencing diagrams and reveals a significant heterogeneity of temperature at different locations in the container, which highlights the ineffectiveness of a temperature control system based on a single sensor, as is usually done.

Análisis e implementación de estrategias de rutado dinámico basado en CTP para redes de sensores inalámbricas multi-salto

Una red de sensores inalámbrica es un conjunto de dispositivos electrónicos que se comunican entre sí sin la necesidad de una infraestructura, recogiendo información del entorno en el que han sido desplegados, procesándola y transmitiéndola hasta una estación base mediante saltos sucesivos entre los nodos de la red (multi-salto). Durante las dos últimas décadas, este campo ha sido muy desarrollado en la comunidad científica, debido a las ventajas que ofrece el despliegue de una red inalámbrica en un entorno con el fin de estudiarlo y/o controlarlo. La ausencia de una infraestructura, junto con el reducido tamaño de los nodos, permite este estudio sin que dicho entorno se vea significativamente afectado por factores externos como pueda ser la presencia humana, permitiendo además aumentar el número de nodos que componen la red o cambiar la posición de algunos de ellos sin que sea necesario reconfigurarla manualmente. El principal reto que presentan las redes de sensores inalámbricas es su autonomía. En general, se requiere que un nodo tenga la capacidad de funcionar durante largos períodos de tiempo (varios meses o incluso un año) antes de que su batería se agote. Esto hace de la gestión del consumo energético un aspecto crítico en el diseño de la red y sus nodos. En el presente trabajo se busca optimizar este consumo mediante la gestión del proceso de comunicación y enrutamiento de la red. Con este fin, se implementa el protocolo CTP (Collection Tree Protocol) en la plataforma Cookies desarrollada en el Centro de Electrónica Industrial (CEI) de la UPM. CTP es un protocolo de rutado centrado en los datos, que utiliza una topología en árbol, con el nodo coordinador o estación base como raíz del mismo, para la transmisión de la información desde los sensores hasta la estación base. Además, no utiliza direcciones predeterminadas, dotando a la red de la flexibilidad requerida para hacer frente a inconsistencias y/o variaciones en la densidad y tamaño de la red. La ruta escogida se basa en un gradiente de rutado decreciente, ETX (Expected Transmission Count), que representa la calidad de la conexión entre un nodo y su nodo padre. Este gradiente de enrutamiento se obtiene mediante una conversión directa a partir del LQI (Link Quality Indication) definido por el estándar IEEE 802.15.4. Esta conversión directa supone una aproximación utilizando valores umbral del LQI. Un nodo escogerá el siguiente salto que realizará el paquete a enviar seleccionando de entre sus vecinos a aquél que tenga el menor ETX, evitando de esta forma la aparición de bucles. Otro de los aspectos que supone un gran consumo es el proceso de mantenimiento de la estructura de la red, pues requiere el envío periódico de señales de control o beacons a lo largo de toda la red. El protocolo CTP aprovecha el algoritmo de goteo (Trickle Algorithm), para gestionar el mantenimiento: durante la formación de la red y cuando se detecte alguna inconsistencia, se incrementa la frecuencia de emisión de los beacons, permitiendo así una rápida propagación de las señales de control para crear o reparar las conexiones entre los nodos. En cambio, cuando la topología de la red es estable, esta frecuencia de emisión se reduce significativamente, limitándose a asegurar que la topología se mantiene estable y favoreciendo así el ahorro de energía.

Metodología para la evaluación de la calidad de la localización de puertos secos

La estructura económica mundial, con centros de producción y consumo descentralizados y el consiguiente aumento en el tráfico de mercancías en todo el mundo, crea considerables problemas y desafíos para el sector del transporte de mercancías. Esta situación ha llevado al transporte marítimo a convertirse en el modo más económico y más adecuado para el transporte de mercancías a nivel global. De este modo, los puertos marítimos se configuran como nodos de importancia capital en la cadena de suministro al servir como enlace entre dos sistemas de transporte, el marítimo y el terrestre. El aumento de la actividad en los puertos marítimos produce tres efectos indeseables: el aumento de la congestión vial, la falta de espacio abierto en las instalaciones portuarias y un impacto ambiental significativo en los puertos marítimos. Los puertos secos nacen para favorecer la utilización de cada modo de transporte en los segmentos en que resultan más competitivos y para mitigar estos problemas moviendo parte de la actividad en el interior. Además, gracias a la implantación de puertos secos es posible discretizar cada uno de los eslabones de la cadena de transporte, permitiendo que los modos más contaminantes y con menor capacidad de transporte tengan itinerarios lo más cortos posible, o bien, sean utilizados únicamente para el transporte de mercancías de alto valor añadido. Así, los puertos secos se presentan como una oportunidad para fortalecer las soluciones intermodales como parte de una cadena integrada de transporte sostenible, potenciando el transporte de mercancías por ferrocarril. Sin embargo, su potencial no es aprovechado al no existir una metodología de planificación de la ubicación de uso sencillo y resultados claros para la toma de decisiones a partir de los criterios ingenieriles definidos por los técnicos. La decisión de dónde ubicar un puerto seco exige un análisis exhaustivo de toda la cadena logística, con el objetivo de transferir el mayor volumen de tráfico posible a los modos más eficientes desde el punto de vista energético, que son menos perjudiciales para el medio ambiente. Sin embargo, esta decisión también debe garantizar la sostenibilidad de la propia localización. Esta Tesis Doctoral, pretende sentar las bases teóricas para el desarrollo de una herramienta de Herramienta de Ayuda a la Toma de Decisiones que permita establecer la localización más adecuada para la construcción de puertos secos. Este primer paso es el desarrollo de una metodología de evaluación de la sostenibilidad y la calidad de las localizaciones de los puertos secos actuales mediante el uso de las siguientes técnicas: Metodología DELPHI, Redes Bayesianas, Análisis Multicriterio y Sistemas de Información Geográfica. Reconociendo que la determinación de la ubicación más adecuada para situar diversos tipos de instalaciones es un importante problema geográfico, con significativas repercusiones medioambientales, sociales, económicos, locacionales y de accesibilidad territorial, se considera un conjunto de 40 variables (agrupadas en 17 factores y estos, a su vez, en 4 criterios) que permiten evaluar la sostenibilidad de las localizaciones. El Análisis Multicriterio se utiliza como forma de establecer una puntuación a través de un algoritmo de scoring. Este algoritmo se alimenta a través de: 1) unas calificaciones para cada variable extraídas de información geográfica analizada con ArcGIS (Criteria Assessment Score); 2) los pesos de los factores obtenidos a través de un cuestionario DELPHI, una técnica caracterizada por su capacidad para alcanzar consensos en un grupo de expertos de muy diferentes especialidades: logística, sostenibilidad, impacto ambiental, planificación de transportes y geografía; y 3) los pesos de las variables, para lo que se emplean las Redes Bayesianas lo que supone una importante aportación metodológica al tratarse de una novedosa aplicación de esta técnica. Los pesos se obtienen aprovechando la capacidad de clasificación de las Redes Bayesianas, en concreto de una red diseñada con un algoritmo de tipo greedy denominado K2 que permite priorizar cada variable en función de las relaciones que se establecen en el conjunto de variables. La principal ventaja del empleo de esta técnica es la reducción de la arbitrariedad en la fijación de los pesos de la cual suelen adolecer las técnicas de Análisis Multicriterio. Como caso de estudio, se evalúa la sostenibilidad de los 10 puertos secos existentes en España. Los resultados del cuestionario DELPHI revelan una mayor importancia a la hora de buscar la localización de un Puerto Seco en los aspectos tenidos en cuenta en las teorías clásicas de localización industrial, principalmente económicos y de accesibilidad. Sin embargo, no deben perderse de vista el resto de factores, cuestión que se pone de manifiesto a través del cuestionario, dado que ninguno de los factores tiene un peso tan pequeño como para ser despreciado. Por el contrario, los resultados de la aplicación de Redes Bayesianas, muestran una mayor importancia de las variables medioambientales, por lo que la sostenibilidad de las localizaciones exige un gran respeto por el medio natural y el medio urbano en que se encuadra. Por último, la aplicación práctica refleja que la localización de los puertos secos existentes en España en la actualidad presenta una calidad modesta, que parece responder más a decisiones políticas que a criterios técnicos. Por ello, deben emprenderse políticas encaminadas a generar un modelo logístico colaborativo-competitivo en el que se evalúen los diferentes factores tenidos en cuenta en esta investigación. The global economic structure, with its decentralized production and the consequent increase in freight traffic all over the world, creates considerable problems and challenges for the freight transport sector. This situation has led shipping to become the most suitable and cheapest way to transport goods. Thus, ports are configured as nodes with critical importance in the logistics supply chain as a link between two transport systems, sea and land. Increase in activity at seaports is producing three undesirable effects: increasing road congestion, lack of open space in port installations and a significant environmental impact on seaports. These adverse effects can be mitigated by moving part of the activity inland. Implementation of dry ports is a possible solution and would also provide an opportunity to strengthen intermodal solutions as part of an integrated and more sustainable transport chain, acting as a link between road and railway networks. In this sense, implementation of dry ports allows the separation of the links of the transport chain, thus facilitating the shortest possible routes for the lowest capacity and most polluting means of transport. Thus, the decision of where to locate a dry port demands a thorough analysis of the whole logistics supply chain, with the objective of transferring the largest volume of goods possible from road to more energy efficient means of transport, like rail or short-sea shipping, that are less harmful to the environment. However, the decision of where to locate a dry port must also ensure the sustainability of the site. Thus, the main goal of this dissertation is to research the variables influencing the sustainability of dry port location and how this sustainability can be evaluated. With this objective, in this research we present a methodology for assessing the sustainability of locations by the use of Multi-Criteria Decision Analysis (MCDA) and Bayesian Networks (BNs). MCDA is used as a way to establish a scoring, whilst BNs were chosen to eliminate arbitrariness in setting the weightings using a technique that allows us to prioritize each variable according to the relationships established in the set of variables. In order to determine the relationships between all the variables involved in the decision, giving us the importance of each factor and variable, we built a K2 BN algorithm. To obtain the scores of each variable, we used a complete cartography analysed by ArcGIS. Recognising that setting the most appropriate location to place a dry port is a geographical multidisciplinary problem, with significant economic, social and environmental implications, we consider 41 variables (grouped into 17 factors) which respond to this need. As a case of study, the sustainability of all of the 10 existing dry ports in Spain has been evaluated. In this set of logistics platforms, we found that the most important variables for achieving sustainability are those related to environmental protection, so the sustainability of the locations requires a great respect for the natural environment and the urban environment in which they are framed.

Automated detection and classification of brain injury lesions on structural magnetic resonance imaging

El daño cerebral adquirido (DCA) es un problema social y sanitario grave, de magnitud creciente y de una gran complejidad diagnóstica y terapéutica. Su elevada incidencia, junto con el aumento de la supervivencia de los pacientes, una vez superada la fase aguda, lo convierten también en un problema de alta prevalencia. En concreto, según la Organización Mundial de la Salud (OMS) el DCA estará entre las 10 causas más comunes de discapacidad en el año 2020. La neurorrehabilitación permite mejorar el déficit tanto cognitivo como funcional y aumentar la autonomía de las personas con DCA. Con la incorporación de nuevas soluciones tecnológicas al proceso de neurorrehabilitación se pretende alcanzar un nuevo paradigma donde se puedan diseñar tratamientos que sean intensivos, personalizados, monitorizados y basados en la evidencia. Ya que son estas cuatro características las que aseguran que los tratamientos son eficaces. A diferencia de la mayor parte de las disciplinas médicas, no existen asociaciones de síntomas y signos de la alteración cognitiva que faciliten la orientación terapéutica. Actualmente, los tratamientos de neurorrehabilitación se diseñan en base a los resultados obtenidos en una batería de evaluación neuropsicológica que evalúa el nivel de afectación de cada una de las funciones cognitivas (memoria, atención, funciones ejecutivas, etc.). La línea de investigación en la que se enmarca este trabajo de investigación pretende diseñar y desarrollar un perfil cognitivo basado no sólo en el resultado obtenido en esa batería de test, sino también en información teórica que engloba tanto estructuras anatómicas como relaciones funcionales e información anatómica obtenida de los estudios de imagen. De esta forma, el perfil cognitivo utilizado para diseñar los tratamientos integra información personalizada y basada en la evidencia. Las técnicas de neuroimagen representan una herramienta fundamental en la identificación de lesiones para la generación de estos perfiles cognitivos. La aproximación clásica utilizada en la identificación de lesiones consiste en delinear manualmente regiones anatómicas cerebrales. Esta aproximación presenta diversos problemas relacionados con inconsistencias de criterio entre distintos clínicos, reproducibilidad y tiempo. Por tanto, la automatización de este procedimiento es fundamental para asegurar una extracción objetiva de información. La delineación automática de regiones anatómicas se realiza mediante el registro tanto contra atlas como contra otros estudios de imagen de distintos sujetos. Sin embargo, los cambios patológicos asociados al DCA están siempre asociados a anormalidades de intensidad y/o cambios en la localización de las estructuras. Este hecho provoca que los algoritmos de registro tradicionales basados en intensidad no funcionen correctamente y requieran la intervención del clínico para seleccionar ciertos puntos (que en esta tesis hemos denominado puntos singulares). Además estos algoritmos tampoco permiten que se produzcan deformaciones grandes deslocalizadas. Hecho que también puede ocurrir ante la presencia de lesiones provocadas por un accidente cerebrovascular (ACV) o un traumatismo craneoencefálico (TCE). Esta tesis se centra en el diseño, desarrollo e implementación de una metodología para la detección automática de estructuras lesionadas que integra algoritmos cuyo objetivo principal es generar resultados que puedan ser reproducibles y objetivos. Esta metodología se divide en cuatro etapas: pre-procesado, identificación de puntos singulares, registro y detección de lesiones. Los trabajos y resultados alcanzados en esta tesis son los siguientes: Pre-procesado. En esta primera etapa el objetivo es homogeneizar todos los datos de entrada con el objetivo de poder extraer conclusiones válidas de los resultados obtenidos. Esta etapa, por tanto, tiene un gran impacto en los resultados finales. Se compone de tres operaciones: eliminación del cráneo, normalización en intensidad y normalización espacial. Identificación de puntos singulares. El objetivo de esta etapa es automatizar la identificación de puntos anatómicos (puntos singulares). Esta etapa equivale a la identificación manual de puntos anatómicos por parte del clínico, permitiendo: identificar un mayor número de puntos lo que se traduce en mayor información; eliminar el factor asociado a la variabilidad inter-sujeto, por tanto, los resultados son reproducibles y objetivos; y elimina el tiempo invertido en el marcado manual de puntos. Este trabajo de investigación propone un algoritmo de identificación de puntos singulares (descriptor) basado en una solución multi-detector y que contiene información multi-paramétrica: espacial y asociada a la intensidad. Este algoritmo ha sido contrastado con otros algoritmos similares encontrados en el estado del arte. Registro. En esta etapa se pretenden poner en concordancia espacial dos estudios de imagen de sujetos/pacientes distintos. El algoritmo propuesto en este trabajo de investigación está basado en descriptores y su principal objetivo es el cálculo de un campo vectorial que permita introducir deformaciones deslocalizadas en la imagen (en distintas regiones de la imagen) y tan grandes como indique el vector de deformación asociado. El algoritmo propuesto ha sido comparado con otros algoritmos de registro utilizados en aplicaciones de neuroimagen que se utilizan con estudios de sujetos control. Los resultados obtenidos son prometedores y representan un nuevo contexto para la identificación automática de estructuras. Identificación de lesiones. En esta última etapa se identifican aquellas estructuras cuyas características asociadas a la localización espacial y al área o volumen han sido modificadas con respecto a una situación de normalidad. Para ello se realiza un estudio estadístico del atlas que se vaya a utilizar y se establecen los parámetros estadísticos de normalidad asociados a la localización y al área. En función de las estructuras delineadas en el atlas, se podrán identificar más o menos estructuras anatómicas, siendo nuestra metodología independiente del atlas seleccionado. En general, esta tesis doctoral corrobora las hipótesis de investigación postuladas relativas a la identificación automática de lesiones utilizando estudios de imagen médica estructural, concretamente estudios de resonancia magnética. Basándose en estos cimientos, se han abrir nuevos campos de investigación que contribuyan a la mejora en la detección de lesiones. ABSTRACT Brain injury constitutes a serious social and health problem of increasing magnitude and of great diagnostic and therapeutic complexity. Its high incidence and survival rate, after the initial critical phases, makes it a prevalent problem that needs to be addressed. In particular, according to the World Health Organization (WHO), brain injury will be among the 10 most common causes of disability by 2020. Neurorehabilitation improves both cognitive and functional deficits and increases the autonomy of brain injury patients. The incorporation of new technologies to the neurorehabilitation tries to reach a new paradigm focused on designing intensive, personalized, monitored and evidence-based treatments. Since these four characteristics ensure the effectivity of treatments. Contrary to most medical disciplines, it is not possible to link symptoms and cognitive disorder syndromes, to assist the therapist. Currently, neurorehabilitation treatments are planned considering the results obtained from a neuropsychological assessment battery, which evaluates the functional impairment of each cognitive function (memory, attention, executive functions, etc.). The research line, on which this PhD falls under, aims to design and develop a cognitive profile based not only on the results obtained in the assessment battery, but also on theoretical information that includes both anatomical structures and functional relationships and anatomical information obtained from medical imaging studies, such as magnetic resonance. Therefore, the cognitive profile used to design these treatments integrates information personalized and evidence-based. Neuroimaging techniques represent an essential tool to identify lesions and generate this type of cognitive dysfunctional profiles. Manual delineation of brain anatomical regions is the classical approach to identify brain anatomical regions. Manual approaches present several problems related to inconsistencies across different clinicians, time and repeatability. Automated delineation is done by registering brains to one another or to a template. However, when imaging studies contain lesions, there are several intensity abnormalities and location alterations that reduce the performance of most of the registration algorithms based on intensity parameters. Thus, specialists may have to manually interact with imaging studies to select landmarks (called singular points in this PhD) or identify regions of interest. These two solutions have the same inconvenient than manual approaches, mentioned before. Moreover, these registration algorithms do not allow large and distributed deformations. This type of deformations may also appear when a stroke or a traumatic brain injury (TBI) occur. This PhD is focused on the design, development and implementation of a new methodology to automatically identify lesions in anatomical structures. This methodology integrates algorithms whose main objective is to generate objective and reproducible results. It is divided into four stages: pre-processing, singular points identification, registration and lesion detection. Pre-processing stage. In this first stage, the aim is to standardize all input data in order to be able to draw valid conclusions from the results. Therefore, this stage has a direct impact on the final results. It consists of three steps: skull-stripping, spatial and intensity normalization. Singular points identification. This stage aims to automatize the identification of anatomical points (singular points). It involves the manual identification of anatomical points by the clinician. This automatic identification allows to identify a greater number of points which results in more information; to remove the factor associated to inter-subject variability and thus, the results are reproducible and objective; and to eliminate the time spent on manual marking. This PhD proposed an algorithm to automatically identify singular points (descriptor) based on a multi-detector approach. This algorithm contains multi-parametric (spatial and intensity) information. This algorithm has been compared with other similar algorithms found on the state of the art. Registration. The goal of this stage is to put in spatial correspondence two imaging studies of different subjects/patients. The algorithm proposed in this PhD is based on descriptors. Its main objective is to compute a vector field to introduce distributed deformations (changes in different imaging regions), as large as the deformation vector indicates. The proposed algorithm has been compared with other registration algorithms used on different neuroimaging applications which are used with control subjects. The obtained results are promising and they represent a new context for the automatic identification of anatomical structures. Lesion identification. This final stage aims to identify those anatomical structures whose characteristics associated to spatial location and area or volume has been modified with respect to a normal state. A statistical study of the atlas to be used is performed to establish which are the statistical parameters associated to the normal state. The anatomical structures that may be identified depend on the selected anatomical structures identified on the atlas. The proposed methodology is independent from the selected atlas. Overall, this PhD corroborates the investigated research hypotheses regarding the automatic identification of lesions based on structural medical imaging studies (resonance magnetic studies). Based on these foundations, new research fields to improve the automatic identification of lesions in brain injury can be proposed.

Automated wordlength optimization framework for multi-source statistical interval-based analysis of nonlinear systems with control-flow structures

El uso de aritmética de punto fijo es una opción de diseño muy extendida en sistemas con fuertes restricciones de área, consumo o rendimiento. Para producir implementaciones donde los costes se minimicen sin impactar negativamente en la precisión de los resultados debemos llevar a cabo una asignación cuidadosa de anchuras de palabra. Encontrar la combinación óptima de anchuras de palabra en coma fija para un sistema dado es un problema combinatorio NP-hard al que los diseñadores dedican entre el 25 y el 50 % del ciclo de diseño. Las plataformas hardware reconfigurables, como son las FPGAs, también se benefician de las ventajas que ofrece la aritmética de coma fija, ya que éstas compensan las frecuencias de reloj más bajas y el uso más ineficiente del hardware que hacen estas plataformas respecto a los ASICs. A medida que las FPGAs se popularizan para su uso en computación científica los diseños aumentan de tamaño y complejidad hasta llegar al punto en que no pueden ser manejados eficientemente por las técnicas actuales de modelado de señal y ruido de cuantificación y de optimización de anchura de palabra. En esta Tesis Doctoral exploramos distintos aspectos del problema de la cuantificación y presentamos nuevas metodologías para cada uno de ellos: Las técnicas basadas en extensiones de intervalos han permitido obtener modelos de propagación de señal y ruido de cuantificación muy precisos en sistemas con operaciones no lineales. Nosotros llevamos esta aproximación un paso más allá introduciendo elementos de Multi-Element Generalized Polynomial Chaos (ME-gPC) y combinándolos con una técnica moderna basada en Modified Affine Arithmetic (MAA) estadístico para así modelar sistemas que contienen estructuras de control de flujo. Nuestra metodología genera los distintos caminos de ejecución automáticamente, determina las regiones del dominio de entrada que ejercitarán cada uno de ellos y extrae los momentos estadísticos del sistema a partir de dichas soluciones parciales. Utilizamos esta técnica para estimar tanto el rango dinámico como el ruido de redondeo en sistemas con las ya mencionadas estructuras de control de flujo y mostramos la precisión de nuestra aproximación, que en determinados casos de uso con operadores no lineales llega a tener tan solo una desviación del 0.04% con respecto a los valores de referencia obtenidos mediante simulación. Un inconveniente conocido de las técnicas basadas en extensiones de intervalos es la explosión combinacional de términos a medida que el tamaño de los sistemas a estudiar crece, lo cual conlleva problemas de escalabilidad. Para afrontar este problema presen tamos una técnica de inyección de ruidos agrupados que hace grupos con las señales del sistema, introduce las fuentes de ruido para cada uno de los grupos por separado y finalmente combina los resultados de cada uno de ellos. De esta forma, el número de fuentes de ruido queda controlado en cada momento y, debido a ello, la explosión combinatoria se minimiza. También presentamos un algoritmo de particionado multi-vía destinado a minimizar la desviación de los resultados a causa de la pérdida de correlación entre términos de ruido con el objetivo de mantener los resultados tan precisos como sea posible. La presente Tesis Doctoral también aborda el desarrollo de metodologías de optimización de anchura de palabra basadas en simulaciones de Monte-Cario que se ejecuten en tiempos razonables. Para ello presentamos dos nuevas técnicas que exploran la reducción del tiempo de ejecución desde distintos ángulos: En primer lugar, el método interpolativo aplica un interpolador sencillo pero preciso para estimar la sensibilidad de cada señal, y que es usado después durante la etapa de optimización. En segundo lugar, el método incremental gira en torno al hecho de que, aunque es estrictamente necesario mantener un intervalo de confianza dado para los resultados finales de nuestra búsqueda, podemos emplear niveles de confianza más relajados, lo cual deriva en un menor número de pruebas por simulación, en las etapas iniciales de la búsqueda, cuando todavía estamos lejos de las soluciones optimizadas. Mediante estas dos aproximaciones demostramos que podemos acelerar el tiempo de ejecución de los algoritmos clásicos de búsqueda voraz en factores de hasta x240 para problemas de tamaño pequeño/mediano. Finalmente, este libro presenta HOPLITE, una infraestructura de cuantificación automatizada, flexible y modular que incluye la implementación de las técnicas anteriores y se proporciona de forma pública. Su objetivo es ofrecer a desabolladores e investigadores un entorno común para prototipar y verificar nuevas metodologías de cuantificación de forma sencilla. Describimos el flujo de trabajo, justificamos las decisiones de diseño tomadas, explicamos su API pública y hacemos una demostración paso a paso de su funcionamiento. Además mostramos, a través de un ejemplo sencillo, la forma en que conectar nuevas extensiones a la herramienta con las interfaces ya existentes para poder así expandir y mejorar las capacidades de HOPLITE. ABSTRACT Using fixed-point arithmetic is one of the most common design choices for systems where area, power or throughput are heavily constrained. In order to produce implementations where the cost is minimized without negatively impacting the accuracy of the results, a careful assignment of word-lengths is required. The problem of finding the optimal combination of fixed-point word-lengths for a given system is a combinatorial NP-hard problem to which developers devote between 25 and 50% of the design-cycle time. Reconfigurable hardware platforms such as FPGAs also benefit of the advantages of fixed-point arithmetic, as it compensates for the slower clock frequencies and less efficient area utilization of the hardware platform with respect to ASICs. As FPGAs become commonly used for scientific computation, designs constantly grow larger and more complex, up to the point where they cannot be handled efficiently by current signal and quantization noise modelling and word-length optimization methodologies. In this Ph.D. Thesis we explore different aspects of the quantization problem and we present new methodologies for each of them: The techniques based on extensions of intervals have allowed to obtain accurate models of the signal and quantization noise propagation in systems with non-linear operations. We take this approach a step further by introducing elements of MultiElement Generalized Polynomial Chaos (ME-gPC) and combining them with an stateof- the-art Statistical Modified Affine Arithmetic (MAA) based methodology in order to model systems that contain control-flow structures. Our methodology produces the different execution paths automatically, determines the regions of the input domain that will exercise them, and extracts the system statistical moments from the partial results. We use this technique to estimate both the dynamic range and the round-off noise in systems with the aforementioned control-flow structures. We show the good accuracy of our approach, which in some case studies with non-linear operators shows a 0.04 % deviation respect to the simulation-based reference values. A known drawback of the techniques based on extensions of intervals is the combinatorial explosion of terms as the size of the targeted systems grows, which leads to scalability problems. To address this issue we present a clustered noise injection technique that groups the signals in the system, introduces the noise terms in each group independently and then combines the results at the end. In this way, the number of noise sources in the system at a given time is controlled and, because of this, the combinato rial explosion is minimized. We also present a multi-way partitioning algorithm aimed at minimizing the deviation of the results due to the loss of correlation between noise terms, in order to keep the results as accurate as possible. This Ph.D. Thesis also covers the development of methodologies for word-length optimization based on Monte-Carlo simulations in reasonable times. We do so by presenting two novel techniques that explore the reduction of the execution times approaching the problem in two different ways: First, the interpolative method applies a simple but precise interpolator to estimate the sensitivity of each signal, which is later used to guide the optimization effort. Second, the incremental method revolves on the fact that, although we strictly need to guarantee a certain confidence level in the simulations for the final results of the optimization process, we can do it with more relaxed levels, which in turn implies using a considerably smaller amount of samples, in the initial stages of the process, when we are still far from the optimized solution. Through these two approaches we demonstrate that the execution time of classical greedy techniques can be accelerated by factors of up to ×240 for small/medium sized problems. Finally, this book introduces HOPLITE, an automated, flexible and modular framework for quantization that includes the implementation of the previous techniques and is provided for public access. The aim is to offer a common ground for developers and researches for prototyping and verifying new techniques for system modelling and word-length optimization easily. We describe its work flow, justifying the taken design decisions, explain its public API and we do a step-by-step demonstration of its execution. We also show, through an example, the way new extensions to the flow should be connected to the existing interfaces in order to expand and improve the capabilities of HOPLITE.

Validación de sistemas constructivos de los cerramientos de la edificación mediante la aplicación de los métodos de decisión multicriterio : aplicación al catálogo de elementos constructivos del Código Técnico de la Edificación

Como punto de partida para el desarrollo de la Tesis, se mantiene la hipótesis de que es posible establecer métodos de evaluación global sobre el grado de utilidad de los sistemas constructivos correspondientes a los cerramientos de la edificación. Tales métodos habrían de posibilitar, de entre una serie finita de sistemas alternativos, cuáles de ellos son los objetivamente más adecuados para su selección en un entorno de decisión concreto, y habrían de permitir fundamentar la justificación objetiva de tal decisión. Paralelamente a esta hipótesis de carácter general, se planteó desde el inicio la necesidad de comprobación de una hipótesis de partida particular según la cual los sistemas constructivos basados en la utilización de componentes prefabricados, o procesos de puesta en obra con un alto grado de industrialización arrojarían valores de utilidad mayores que los sistemas tradicionales basados en la albañilería. Para la verificación de estas dos hipótesis de partida se ha procedido inicialmente a la selección de un conjunto coherente de doce sistemas de cerramientos de la edificación que pudiese servir como testigo de su diversidad potencial, para proceder a su valoración comparativa. El método de valoración propuesto ha entrado a considerar una serie de factores de diversa índole que no son reducibles a un único parámetro o magnitud que permitiese una valoración de tipo lineal sobre su idoneidad relativa, ni que permitiese establecer un grado de prelación entre los distintos sistemas constructivos alternativos de manera absoluta. Para resolver este tour de force o desafío metodológico se ha acudido a la aplicación de metodologías de valoración que nos permitiesen establecer de forma racional dicha comparativa. Nos referimos a una serie de metodologías provenientes en primera instancia de las ciencias exactas, que reciben la denominación de métodos de ayuda a la decisión multicriterio, y en concreto el denominado método ELECTRE. Inicialmente, se ha planteado la aplicación del método de análisis sobre doce sistemas constructivos seleccionados de tal forma que representasen de forma adecuada las tres categorías establecidas para caracterizar la totalidad de sistemas constructivos posibles; por peso, grado de prefabricación y grado de ventilación. Si bien la combinación de las tres categorías básicas anteriormente señaladas produce un total de 18 subcategorías conceptuales, tomamos finalmente doce subcategorías dado que consideramos que es un número operativo suficiente por extenso para el análisis propuesto y elimina tipos no relevantes. Aplicado el método propuesto, a estos doce sistemas constructivos “testigo”, se constata el mayor grado de utilidad de los sistemas prefabricados, pesados y no ventilados. Al hilo del análisis realizado en la Parte II de la Tesis sobre los doce sistemas constructivos “testigo”, se ha realizado un volcado de los sistemas constructivos incluidos en el Catalogo de Elementos Constructivos del CTE (versión 2010) sobre las dieciocho subcategorías definidas en dicha Parte II para caracterizar los sistemas constructivos “testigo”. Posteriormente, se ha procedido a una parametrización de la totalidad de sistemas constructivos para cerramientos de fachadas incluidos en este Catálogo. La parametrización sistemática realizada ha permitido establecer, mediante el cálculo del valor medio que adoptan los parámetros de los sistemas pertenecientes a una misma familia de las establecidas por el Catálogo, una caracterización comparativa del grado de utilidad de dichas familias, tanto en lo relativo a cada uno de los parámetros como en una valoración global de sus valores, de carácter indicativo. Una vez realizada una parametrización completa de la totalidad de sistemas constructivos incluidos en el Catálogo, se ha realizado una simulación de aplicación de la metodología de validación desarrollada en la Parte II de la presente Tesis, con el objeto de comprobar su adecuación al caso. En conclusión, el desarrollo de una herramienta de apoyo a la decisión multicriterio aplicada al Catálogo de Elementos constructivos del CTE se ha demostrado técnicamente viable y arroja resultados significativos. Se han diseñado dos sistemas constructivos mediante la aplicación de la herramienta desarrollada, uno de fachada no ventilada y otro de fachada ventilada. Comparados estos dos sistemas constructivos mejorados con otros sistemas constructivos analizados Se comprueba el alto grado de utilidad objetiva de los dos sistemas diseñados en relación con el resto. La realización de este ejercicio de diseño de un sistema constructivo específico, que responde a los requerimientos de un decisor concreto viene a demostrar, así pues, la utilidad del algoritmo propuesto en su aplicación a los procesos de diseño de los sistemas constructivos. La tesis incorpora dos innovaciones metodológicas y tres innovaciones instrumentales. ABSTRACT The starting point for the thesis is the hypothesis that it is possible to devise suitability degree evaluation methods of building enclosure systems. Such methods should allow optimizing appraisal, given a specific domain of decision, among a finite number of alternative systems, and provide objective justification of such decision. Along with the above mentioned general assumption, a second hypothesis whereby constructive systems based on the use of prefabricated components, or high industrialization degree work processes, would throw efficiency values higher than traditional masonry systems needed to be tested. In order to validate these two hypothesis a coherent set of twelve enclosure systems that could serve as a reference sample of their potential diversity was selected and a comparative evaluation was carried out. The valuation method proposed has considered several different factors that are neither reducible to a single parameter or magnitude that would allow a linear evaluation of their relative suitability nor allow to establishing an absolute priority ranking between different alternative constructive systems. In order to resolve this tour de force or methodological challenge, valuation methodologies that enable use establishing rational assessments were used. We are referring to a number of methodologies taken from the exact sciences field, usually known as aid methods for multi-criteria decision, in particular the so-called ELECTRE method. Even though the combination of the mentioned three basic categories result in eighteen conceptual sub categories, we are finally considering just twelve since we deem it adequately extended for the our intended purpose and eliminates non relevant instances. The method of analysis was initially applied to the set of twelve selected constructive systems is a way that they could represent adequately the three previously established categories set out to characterize all possible enclosure systems, namely weight, prefabrication degree and ventilation degree. Once the proposed method is applied to the sample systems, the higher efficiency of the prefabricated, heavy and not ventilated systems was confirmed. In line with the analysis in Part II of the thesis on the twelve chosen enclosure systems, it has done an uploading data of construction systems listed in the Catalogue of constructive elements of the CTE (version 2010) according the eighteen subcategories used in this part II to characterize the construction systems taken as sample. Subsequently, a parameterization of all enclosure facade systems included in this catalog has been undertaken. The systematic parameterization has allowed to set, by means of calculating the average values of the parameters of the systems belonging to the same family of those established by the Catalog, a comparative characterization of the efficiency degree of these families, both in relation to each parameter as to an overall evaluation of its values, in a indicative way. After the parameterization of all enclosure systems included in the Catalog, a simulation of validation methodology application developed in Part II of this Thesis has been made, in order to assess its consistency to the referred case. In conclusion, the development of a multi-criteria decision aid tool, applied to the CTE Catalog of constructive elements, has proved to be technically feasible and yields significant results. Two building systems through the application of the developed tool, a non-ventilated façade and a ventilated façade have been designed. Comparing these two improved construction systems with other building systems analyzed, we were able to assess the high degree of objective efficiency of the two systems designed in relation to the rest. The exercise of designing a specific enclosure system that meets the requirements of a particular decision-maker hence shows the suitability of the proposed algorithm applied to the process of enclosure systems design. This Thesis includes two methodological innovations and three instrumental innovations.

Design Parameter Analysis of Point Absorber WEC via an Evolutionary-Algorithm-Based Dimensioning Tool

Wave energy conversion has an essential difference from other renewable energies since the dependence between the devices design and the energy resource is stronger. Dimensioning is therefore considered a key stage when a design project of Wave Energy Converters (WEC) is undertaken. Location, WEC concept, Power Take-Off (PTO) type, control strategy and hydrodynamic resonance considerations are some of the critical aspects to take into account to achieve a good performance. The paper proposes an automatic dimensioning methodology to be accomplished at the initial design project stages and the following elements are described to carry out the study: an optimization design algorithm, its objective functions and restrictions, a PTO model, as well as a procedure to evaluate the WEC energy production. After that, a parametric analysis is included considering different combinations of the key parameters previously introduced. A variety of study cases are analysed from the point of view of energy production for different design-parameters and all of them are compared with a reference case. Finally, a discussion is presented based on the results obtained, and some recommendations to face the WEC design stage are given.

Optimizing communication by compression for Multi-GPU Scalable Breadth-First Searches

Debido al creciente aumento del tamaño de los datos en muchos de los actuales sistemas de información, muchos de los algoritmos de recorrido de estas estructuras pierden rendimento para realizar búsquedas en estos. Debido a que la representacion de estos datos en muchos casos se realiza mediante estructuras nodo-vertice (Grafos), en el año 2009 se creó el reto Graph500. Con anterioridad, otros retos como Top500 servían para medir el rendimiento en base a la capacidad de cálculo de los sistemas, mediante tests LINPACK. En caso de Graph500 la medicion se realiza mediante la ejecución de un algoritmo de recorrido en anchura de grafos (BFS en inglés) aplicada a Grafos. El algoritmo BFS es uno de los pilares de otros muchos algoritmos utilizados en grafos como SSSP, shortest path o Betweeness centrality. Una mejora en este ayudaría a la mejora de los otros que lo utilizan. Analisis del Problema El algoritmos BFS utilizado en los sistemas de computación de alto rendimiento (HPC en ingles) es usualmente una version para sistemas distribuidos del algoritmo secuencial original. En esta versión distribuida se inicia la ejecución realizando un particionado del grafo y posteriormente cada uno de los procesadores distribuidos computará una parte y distribuirá sus resultados a los demás sistemas. Debido a que la diferencia de velocidad entre el procesamiento en cada uno de estos nodos y la transfencia de datos por la red de interconexión es muy alta (estando en desventaja la red de interconexion) han sido bastantes las aproximaciones tomadas para reducir la perdida de rendimiento al realizar transferencias. Respecto al particionado inicial del grafo, el enfoque tradicional (llamado 1D-partitioned graph en ingles) consiste en asignar a cada nodo unos vertices fijos que él procesará. Para disminuir el tráfico de datos se propuso otro particionado (2D) en el cual la distribución se haciá en base a las aristas del grafo, en vez de a los vertices. Este particionado reducía el trafico en la red en una proporcion O(NxM) a O(log(N)). Si bien han habido otros enfoques para reducir la transferecnia como: reordemaniento inicial de los vertices para añadir localidad en los nodos, o particionados dinámicos, el enfoque que se va a proponer en este trabajo va a consistir en aplicar técnicas recientes de compression de grandes sistemas de datos como Bases de datos de alto volume o motores de búsqueda en internet para comprimir los datos de las transferencias entre nodos.---ABSTRACT---The Breadth First Search (BFS) algorithm is the foundation and building block of many higher graph-based operations such as spanning trees, shortest paths and betweenness centrality. The importance of this algorithm increases each day due to it is a key requirement for many data structures which are becoming popular nowadays. These data structures turn out to be internally graph structures. When the BFS algorithm is parallelized and the data is distributed into several processors, some research shows a performance limitation introduced by the interconnection network [31]. Hence, improvements on the area of communications may benefit the global performance in this key algorithm. In this work it is presented an alternative compression mechanism. It differs with current existing methods in that it is aware of characteristics of the data which may benefit the compression. Apart from this, we will perform a other test to see how this algorithm (in a dis- tributed scenario) benefits from traditional instruction-based optimizations. Last, we will review the current supercomputing techniques and the related work being done in the area.