In this thesis, we study the notion of graph summarization, which is a fundamental task of finding a compact representation of the original graph called the summary. Graph summarization can be used for reducing the footprint of the input graph, better visualization, anonymizing the identity of users, and query answering. There are two different frameworks of graph summarization we consider in this thesis, the utility-based framework and the correction set-based framework. In the utility-based framework, the input graph is summarized until a utility threshold is not violated. In the correction set-based framework a set of correction edges is produced along with the summary graph. In this thesis we propose two algorithms for the utility-based framework and one for the correction set-based framework. All these three algorithms are for static graphs (i.e. graphs that do not change over time). Then, we propose two more utility-based algorithms for fully dynamic graphs (i.e. graphs with edge insertions and deletions). Algorithms for graph summarization can be lossless (summarizing the input graph without losing any information) or lossy (losing some information about the input graph in order to summarize it more). Some of our algorithms are lossless and some lossy, but with controlled utility loss. Our first utility-driven graph summarization algorithm, G-SCIS, is based on a clique and independent set decomposition, that produces optimal compression with zero loss of utility. The compression provided is significantly better than state-of-the-art in lossless graph summarization, while the runtime is two orders of magnitude lower. Our second algorithm is T-BUDS, a highly scalable, utility-driven algorithm for fully controlled lossy summarization. It achieves high scalability by combining memory reduction using Maximum Spanning Tree with a novel binary search procedure. T-BUDS outperforms state-of-the-art drastically in terms of the quality of summarization and is about two orders of magnitude better in terms of speed. In contrast to the competition, we are able to handle web-scale graphs in a single machine without performance impediment as the utility threshold (and size of summary) decreases. Also, we show that our graph summaries can be used as-is to answer several important classes of queries, such as triangle enumeration, Pagerank and shortest paths. We then propose algorithm LDME, a correction set-based graph summarization algorithm that produces compact output representations in a fast and scalable manner. To achieve this, we introduce (1) weighted locality sensitive hashing to drastically reduce the number of comparisons required to find good node merges, (2) an efficient way to compute the best quality merges that produces more compact outputs, and (3) a new sort-based encoding algorithm that is faster and more robust. More interestingly, our algorithm provides performance tuning settings to allow the option of trading compression for running time. On high compression settings, LDME achieves compression equal to or better than the state of the art with up to 53x speedup in running time. On high speed settings, LDME achieves up to two orders of magnitude speedup with only slightly lower compression. We also present two lossless summarization algorithms, Optimal and Scalable, for summarizing fully dynamic graphs. More concretely, we follow the framework of G-SCIS, which produces summaries that can be used as-is in several graph analytics tasks. Different from G-SCIS, which is a batch algorithm, Optimal and Scalable are fully dynamic and can respond rapidly to each change in the graph. Not only are Optimal and Scalable able to outperform G-SCIS and other batch algorithms by several orders of magnitude, but they also significantly outperform MoSSo, the state-of-the-art in lossless dynamic graph summarization. While Optimal produces always the most optimal summary, Scalable is able to trade the amount of node reduction for extra scalability. For reasonable values of the parameter $K$, Scalable is able to outperform Optimal by an order of magnitude in speed, while keeping the rate of node reduction close to that of Optimal. An interesting fact that we observed experimentally is that even if we were to run a batch algorithm, such as G-SCIS, once for every big batch of changes, still they would be much slower than Scalable. For instance, if 1 million changes occur in a graph, Scalable is two orders of magnitude faster than running G-SCIS just once at the end of the 1 million-edge sequence. / Graduate

La finalidad de este trabajo de investigación se genera gracias a la necesidad de buscar una forma más efectiva de gestionar programaciones de obra durante la etapa de estructuras en dos hospitales ubicados en la región San Martín, para ello se realiza un análisis en ambas obras, dado que en una de ellas se trabajó bajo el sistema tradicional y la segunda bajo los lineamientos del Last Planner, esto con el objetivo de determinar cuál es más eficiente. en ese sentido se desarrolla un comparativo del ya conocido sistema Last Planner en el campo de la construcción versus el enfoque tradicional de planeamiento (cronograma Gantt, ruta crítica), tal como se describirá en los capítulos 3 y 4. En el capítulo 1, se detallan los aspectos generales del presente trabajo, se señala el problema, las diferentes hipótesis, el objetivo general y los objetivos específicos, así como la metodología a seguir y los resultados esperados. En el capítulo 2, se detalla todo el marco teórico del sistema del planificador último, considerada como un elemento que forma parte del enfoque “construcción sin pérdidas” o “Lean Construction que apareció en los años 90 y cuya procedencia fue el resultado de la aplicación de “Lean Production” y de los principios para la dirección de proyectos. En el capítulo 3, se realiza el análisis de cada obra, la primera bajo el sistema tradicional y la segunda por los principales conceptos y herramientas del sistema Last Planner y establecer una base teórica sólida que sirva de apoyo al trabajo de investigación. En los capítulos 4 y 5, se realizó el comparativo en la ejecución de ambos hospitales, obteniendo como resultado un mejor desarrollo en control de la programación en el hospital B, el cual como se explicó, se trabajó bajo los lineamientos del sistema Last Planner, sin embrago se debe tener en cuenta también que no se pudo llegar a los valores esperados debido a factores climatológicos propios de la zona de trabajo, de todas maneras estuvo por encima de los valores obtenidos en los indicadores del hospital A, desarrollado bajo el sistema tradicional. Finalmente, el material del trabajo de investigación, servirá de apoyo para realizar la aplicación del sistema del planificador último para distintos proyectos de construcción. / The purpose of this research work is generated by the need to find the most efficient way to manage the work schedule during the structures stage in two hospitals located in the San Martín region, for which an analysis is carried out in both works, given that one of them worked under the traditional system and the second under the guidelines of the Last Planner, this with the aim of determining which is more efficient. In this sense, a comparative of the Last Planner system in construction versus the traditional planning approach is developed (Gantt schedule, critical path), as will be described in chapters 3 and 4. In Chapter 1, the general aspects of this work are detailed, the problem, the different hypotheses, the general objective and the specific objectives are indicated, as well as the methodology to be followed and the expected results. In Chapter 2, the entire theoretical framework of the Last Planner system is detailed, a tool that is part of the “lossless construction” or “Lean Construction” philosophy that emerged in the 1990s and came from the adaptation of “Lean Production” and the foundations for project management. In Chapter 3, the analysis of each work is carried out, the first under the traditional system and the second for the main concepts and tools of the Last Planner System in order to generate a solid theoretical base to support this research work. In Chapters 4 and 5, a comparison was made in the execution of both hospitals, obtaining as a result a better development in programming control in hospital B, which, as explained, worked under the guidelines of the Last Planner System, However, it should also be taken into account that the expected values could not be reached due to climatic factors typical of the work area, in any case it was above the values obtained in the hospital A indicators, developed under the traditional system. Finally, the material of this research work will serve as a starting point for the application of the latest planner system in different construction project. / Trabajo de investigación

Honeywell Technology Solutions Lab, India / Weather is a major contributing factor in aviation accidents, incidents and delays. Doppler weather radar has emerged as a potent tool to observe weather. Aircraft carry onboard radars but their range and angular resolution are limited. Networks of ground-based weather radars provide extensive coverage of weather over large geographic regions. It would be helpful if these data can be transmitted to the pilot. However, these data are highly voluminous and the bandwidth of the ground-air communication links is limited and expensive. Hence, these data have to be compressed to an extent where they are suitable for transmission over low-bandwidth links. Several methods have been developed to compress pictorial data. General-purpose schemes do not take into account the nature of data and hence do not yield high compression ratios. A scheme for extreme compression of weather radar data is developed in this thesis that does not significantly degrade the meteorological information contained in these data. The method is based on contour encoding. It approximates a contour by a set of systematically chosen ‘control points’ that preserve its fine structure up to a certain level. The contours may be obtained using a thresholding process based on NWS or custom reflectivity levels. This process may result in region and hole contours, enclosing `high' or `low' areas, which may be nested. A tag bit is used to label region and hole contours. The control point extraction method first obtains a smoothed reference contour by averaging the original contour. Then the points on the original contour with maximum deviation from the smoothed contour between the crossings of these contours are identified and are designated as control points. Additional control points are added midway between the control point and the crossing points on either side of it, if the length of the segment between the crossing points exceeds a certain length. The control points, referenced with respect to the top-left corner of each contour for compact quantification, are transmitted to the receiving end. The contour is retrieved from the control points at the receiving end using spline interpolation. The region and hole contours are identified using the tag bit. The pixels between the region and hole contours at a given threshold level are filled using the color corresponding to it. This method is repeated till all the contours for a given threshold level are exhausted, and the process is carried out for all other thresholds, thereby resulting in a composite picture of the reconstructed field. Extensive studies have been conducted by using metrics such as compression ratio, fidelity of reconstruction and visual perception. In particular the effect of the smoothing factor, the choice of the degree of spline interpolation and the choice of thresholds are studied. It has been shown that a smoothing percentage of about 10% is optimal for most data. A degree 2 of spline interpolation is found to be best suited for smooth contour reconstruction. Augmenting NWS thresholds has resulted in improved visual perception, but at the expense of a decrease in the compression ratio. Two enhancements to the basic method that include adjustments to the control points to achieve better reconstruction and bit manipulations on the control points to obtain higher compression are proposed. The spline interpolation inherently tends to move the reconstructed contour away from the control points. This has been somewhat compensated by stretching the control points away from the smoothed reference contour. The amount and direction of stretch are optimized with respect to actual data fields to yield better reconstruction. In the bit manipulation study, the effects of discarding the least significant bits of the control point addresses are analyzed in detail. Simple bit truncation introduces a bias in the contour description and reconstruction, which is removed to a great extent by employing a bias compensation mechanism. The results obtained are compared with other methods devised for encoding weather radar contours.

It is well known that communication systems employing multiple transmit and multiple receive antennas provide high data rates along with increased reliability. It has been shown that coding across both spatial and temporal domains together, called Space-Time Coding (STC), achieves, a diversity order equal to the product of the number of transmit and receive antennas. Space-Time Block Codes (STBC) achieving the maximum diversity is called full-diversity STBCs. An STBC is called information-lossless, if the structure of it is such that the maximum mutual information of the resulting equivalent channel is equal to the capacity of the channel. This thesis deals with high-rate and information-lossless STBCs obtained from certain matrix algebras called Crossed-Product Algebras. First we give constructions of high-rate STBCs using both commutative and non-commutative matrix algebras obtained from appropriate representations of extensions of the field of rational numbers. In the case of commutative algebras, we restrict ourselves to fields and call the STBCs obtained from them as STBCs from field extensions. In the case of non-commutative algebras, we consider only the class of crossed-product algebras. For the case of field extensions, we first construct high-rate; full-diversity STBCs for arbitrary number of transmit antennas, over arbitrary apriori specified signal sets. Then we obtain a closed form expression for the coding gain of these STBCs and give a tight lower bound on the coding gain of some of these STBCs. This lower bound in certain cases indicates that some of the STBCs from field extensions are optimal m the sense of coding gain. We then show that the STBCs from field extensions are information-lossy. However, we also show that the finite-signal-set capacity of the STBCs from field extensions can be improved by increasing the symbol rate of the STBCs. The simulation results presented show that our high-rate STBCs perform better than the rate-1 STBCs in terms of the bit error rate performance. Then we proceed to present a construction of high-rate STBCs from crossed-product algebras. After giving a sufficient condition on the crossed-product algebras under which the resulting STBCs are information-lossless, we identify few classes of crossed-product algebras that satisfy this sufficient condition and also some classes of crossed-product algebras which are division algebras which lead to full-diversity STBCs. We present simulation results to show that the STBCs from crossed-product algebras perform better than the well-known codes m terms of the bit error rate. Finally, we introduce the notion of asymptotic-information-lossless (AILL) designs and give a necessary and sufficient condition under which a linear design is an AILL design. Analogous to the condition that a design has to be a full-rank design to achieve the point corresponding to the maximum diversity of the optimal diversity-multiplexing tradeoff, we show that a design has to be AILL to achieve the point corresponding to the maximum multiplexing gain of the optimal diversity-multiplexing tradeoff. Using the notion of AILL designs, we give a lower bound on the diversity-multiplexing tradeoff achieved by the STBCs from both field extensions and division algebras. The lower bound for STBCs obtained from division algebras indicates that they achieve the two extreme points, 1 e, zero multiplexing gain and zero diversity gain, of the optimal diversity-multiplexing tradeoff. Also, we show by simulation results that STBCs from division algebras achieves all the points on the optimal diversity-multiplexing tradeoff for n transmit and n receive antennas, where n = 2, 3, 4.

This master's thesis deals with lossless video compression. This thesis includes basic concepts and techniques used in image representation. The reader can find an explanation of basic difference between lossless video compression and lossy video compression and lossless video compression limitations. There is also possible find a description of the basic blocks forming the video codec (every block is described in detail). In every block there are introduced its possible variants. Implemented lossless videocodec was compared with common lossless videocodecs.

Dans le format multiple-view video plus depth, les cartes de profondeur peuvent être représentées comme des images en niveaux de gris et la séquence temporelle correspondante peut être considérée comme une séquence vidéo standard en niveaux de gris. Cependant les cartes de profondeur ont des propriétés différentes des images naturelles: ils présentent de grandes surfaces lisses séparées par des arêtes vives. On peut dire que l'information la plus importante réside dans les contours de l'objet, en conséquence une approche intéressante consiste à effectuer un codage sans perte de la carte de contour, éventuellement suivie d'un codage lossy des valeurs de profondeur par-objet. Dans ce contexte, nous proposons une nouvelle technique pour le codage sans perte des contours de l'objet, basée sur la déformation élastique des courbes. Une évolution continue des déformations élastiques peut être modélisée entre deux courbes de référence, et une version du contour déformée élastiquement peut être envoyée au décodeur avec un coût de codage très faible et utilisé comme information latérale pour améliorer le codage sans perte du contour réel. Après que les principales discontinuités ont été capturées par la description du contour, la profondeur à l'intérieur de chaque région est assez lisse. Nous avons proposé et testé deux techniques différentes pour le codage du champ de profondeur à l'intérieur de chaque région. La première technique utilise la version adaptative à la forme de la transformation en ondelette, suivie par la version adaptative à la forme de SPIHT. La seconde technique effectue une prédiction du champ de profondeur à partir de sa version sous-échantillonnée et l'ensemble des contours codés. Il est généralement reconnu qu'un rendu de haute qualité au récepteur pour un nouveau point de vue est possible qu’avec la préservation de l'information de contour, car des distorsions sur les bords lors de l'étape de codage entraînerait une dégradation évidente sur la vue synthétisée et sur la perception 3D. Nous avons étudié cette affirmation en effectuant un test d'évaluation de la qualité perçue en comparant, pour le codage des cartes de profondeur, une technique basée sur la compression d'objects et une techniques de codage vidéo hybride à blocs. / In multiple-view video plus depth, depth maps can be represented by means of grayscale images and the corresponding temporal sequence can be thought as a standard grayscale video sequence. However depth maps have different properties from natural images: they present large areas of smooth surfaces separated by sharp edges. Arguably the most important information lies in object contours, as a consequence an interesting approach consists in performing a lossless coding of the contour map, possibly followed by a lossy coding of per-object depth values. In this context, we propose a new technique for the lossless coding of object contours, based on the elastic deformation of curves. A continuous evolution of elastic deformations between two reference contour curves can be modelled, and an elastically deformed version of the reference contours can be sent to the decoder with an extremely small coding cost and used as side information to improve the lossless coding of the actual contour. After the main discontinuities have been captured by the contour description, the depth field inside each region is rather smooth. We proposed and tested two different techniques for the coding of the depth field inside each region. The first technique performs the shape-adaptive wavelet transform followed by the shape-adaptive version of SPIHT. The second technique performs a prediction of the depth field from its subsampled version and the set of coded contours. It is generally recognized that a high quality view rendering at the receiver side is possible only by preserving the contour information, since distortions on edges during the encoding step would cause a sensible degradation on the synthesized view and on the 3D perception. We investigated this claim by conducting a subjective quality assessment test to compare an object-based technique and a hybrid block-based techniques for the coding of depth maps.

Batteries account for 50% of the overall cost of solar home systems (SHS). The battery packs degrade over time and when they reach 70% state of health (SOH), the whole SHS is discarded. In the predominantly rural off-grid context, battery replacements are expensive and impractical. The customers are often dozens of km away from any sales point. Furthermore, recycling schemes are often limited in the developing world, meaning that old batteries are sometimes discarded in unsafe ways. As the market grows, the environmental impact of this will only get larger. Solaris Offgrid, a premier name in the Solar Offgrid industry, is innovating two solutions designed to tackle this issue; a smart multi-battery packmanager and an easy to recycle battery pack design with cell by cell management. The current study is based on a lossless cell balancing design, where in the charge and discharge cycles of each cell in the string are monitored and to efficiently avoid overcharge and over-discharge. Implementing this strategy reduces the degradation of these batteries which extends the battery life of SHS. A sensitivity analysis is performed to analyze the environmental benefit gained by implementing lossless cell balancing. The thesis provides a literature study on the different battery terminologies, types of batteries used in SHS and, various cell-balancing techniques used today. This is followed by the design of a lossless cell balancing technique with minimal losses. / Batterierna står för 50 % av den totala kostnaden för solcellsanläggningar (SHS). Batteripaketen försämras med tiden och när de når 70 % av sitt hälsotillstånd kasseras hela solcellssystemet. På den övervägande landsbygden utanför elnätet är det dyrt och opraktiskt att byta ut batterierna. Kunderna befinner sig ofta tiotals kilometer från varje försäljningsställe. Dessutom är återvinningssystemen ofta begränsade i utvecklingsländerna, vilket innebär att gamla batterier ibland kasseras på ett osäkert sätt. I takt med att marknaden växer kommer miljöeffekterna av detta att bli allt större. Solaris Offgrid, som är ett ledande företag inom industrin för solcellsanläggningar, utvecklar två lösningar för att lösa detta problem: en smart batteripackförvaltare för flera batterier och en lätt återvinningsbar batteripackkonstruktion med cellvis hantering. Den aktuella studien bygger på en “förlustfri” cellbalanseringskonstruktion, där laddnings- och urladdningscyklerna för varje cell i strängen övervakas och effektivt undviker överladdning och överladdning. Genom att tillämpa denna strategi minskas degraderingen av dessa batterier, vilket förlänger batteritiden för SHS. En känslighetsanalys utförs för att analysera den miljöfördel som uppnås genom att införa förlustfri cellbalansering. Avhandlingen innehåller en litteraturstudie om olika batteriterminologier, typer av batterier som används i SHS och olika tekniker för cellbalansering som används idag. Detta följs av utformningen av en teknik för förlustfricellbalansering med minimala förluster.

<p dir="ltr">Ion mobility spectrometry (IMS), with its unparalleled ability to separate and filter ions based on their overall size before channeling them into a Mass Spectrometer, has placed itself as a cornerstone of the modern Analytical Chemistry field. IMS provides an orthogonal separation, aiding in the identification and analysis processes of various compounds. While there have been many inventions for ion mobility (IM) devices with exponential growth in the separation capability in the past few years, there is very little emphasis on the theoretical explanation. For example, most modern IMS devices often use a high ratio of electric field to gas concentration (E/n) as it provides better separation capabilities. However, the interaction between ion and gas at such E/n cannot be explained by current IM theories as they ignore several critical factors such as the increase in ion’s energy due to energetic collisions, the energy loss/transferred in the internal degree of freedoms, and change in the ion’s structure, requiring empirical data to identify ions after separation. The thesis presented here contributes towards bridging this gap by elucidating the complex interplay of forces and interactions that govern the ion separation process, thereby explaining on how these mechanisms can be further exploited for refined separation and advancing the computational approach to identify the separated ion.</p><p dir="ltr">To explain the ion-gas interaction under high E/n, this research extends the Two-Temperature Theory (2TT) up to the fourth order approximation. The central idea of the 2TT is to solve moments of the Boltzmann equation for the ion’s velocity distribution involving ion-gas collisions. The research shows a decreasing error between each subsequent approximations, indicating convergence. This advancement is demonstrated through the development and application of our in-house program, IMoS, and validated against experimental data for small ions in monoatomic gases. This research also justifies the mechanisms of increasing and decreasing mobility as the electric field is increased by explaining the interplay between the interaction potential and the collision energy.</p><p dir="ltr">Subsequent chapters investigate the impact of internal degrees of freedom (rotational and vibrational) on ion mobility. This includes pioneering work with the Structures for Lossless Ion Manipulations (SLIM) device to separate isotopomers, alongside computational advancements in simulating these effects, leading to the development of IMoS 2.0. In IMoS 2.0 software an ion is placed in a virtual drift tube with electric field, where it is free to rotate and translate upon collision. The research notably uncovers the role of rotational degrees of freedom in isotopomer separation, a previously underexplored area.</p><p dir="ltr">To ascertain the effect of the vibrational DoF and differentiate from the ion’s structural expansion and heating resulting from energetic collisions, a combined simulation of ion mobility and molecular dynamics (IM-MD) was performed. This analysis revealed that structural expansion plays a dominant role for the cause of deviation at high E/n, to such an extent that the vibrational DoF (or inelastic collisions) can normally be disregarded. Moreover, the research also indicates that using a combination of IM-MD simulation, one can identify accurate gas-phase structure of the ion at any temperature from a pool of probable structures.</p><p dir="ltr">Guided by these conclusions, the research now takes a significant step forward by aiming to accurately characterize protein structures in the gas phase using IM-MD simulation. Traditional MD simulations provide larger structures since the force field is not optimized for the gas-phase simulation. To address this, a biasing force towards the center of the protein is applied, compressing it. This method efficiently explores multiple feasible configurations, including those obscured by energy barriers. This strategy generated structures that closely align with the experimental evidence.</p>

This thesis deals with lossless and losing methods of data compressions and their possible applications in the measurement engineering. In the first part of the thesis there is a theoretical elaboration which informs the reader about the basic terminology, the reasons of data compression, the usage of data compression in standard practice and the division of compression algorithms. The practical part of thesis deals with the realization of the compress algorithms in Matlab and LabWindows/CVI.

This thesis is focused on subject of image compression using wavelet transform. The first part of this document provides reader with information about image compression, presents well known contemporary algorithms and looks into details of wavelet compression and following encoding schemes. Both JPEG and JPEG 2000 standards are introduced. Second part of this document analyzes and describes implementation of image compression tool including inovations and optimalizations. The third part is dedicated to comparison and evaluation of achievements.