Rozprawy doktorskie na temat „Data structures”

Concurrent programming is difficult and the effort is rarely rewarded by faster execution. The concurrency problem arises because information cannot pass instantly between processors resulting in temporal uncertainty. This thesis explores the idea that immutable data and distributed concurrency control can be combined to allow scalable concurrent execution and make concurrent programming easier. A concurrent system that does not impose a global ordering on events lends itself to a scalable distributed implementation. A concurrent programming environment in which the ordering of events affecting an object is enforced locally has intuitive concurrent semantics. This thesis introduces Transactional Data Structures which are data structures that permit access to past versions, although not all accesses succeed. These data structures form the basis of a concurrent programming solution that supports database type transactions in memory. Transactional Data Structures permit non-blocking concurrent access to familiar abstract data types such as deques, maps, vectors and priority queues. Using these data structures a programmer can write a concurrent program in C without having to reason about locks. The solution is evaluated by comparing the performance of a concurrent algorithm to calculate the minimum spanning tree of a graph with that of a similar algorithm which uses Transactional Memory and by comparing a non-blocking Producer Consumer Queue with its blocking counterpart.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2011.
This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.
Cataloged from student submitted PDF version of thesis.
Includes bibliographical references (p. 175-180).
As multicores become prevalent, the complexity of programming is skyrocketing. One major difficulty is eciently orchestrating collaboration among threads through shared data structures. Unfortunately, choosing and hand-tuning data structure algorithms to get good performance across a variety of machines and inputs is a herculean task to add to the fundamental difficulty of getting a parallel program correct. To help mitigate these complexities, this work develops a new class of parallel data structures called Smart Data Structures that leverage online machine learning to adapt themselves automatically. We prototype and evaluate an open source library of Smart Data Structures for common parallel programming needs and demonstrate signicant improvements over the best existing algorithms under a variety of conditions. Our results indicate that learning is a promising technique for balancing and adapting to complex, time-varying tradeoffs and achieving the best performance available.
by Jonathan M. Eastep.
Ph.D.

This thesis discusses cache oblivious data structures. These are structures which have good caching characteristics without knowing Z, the size of the cache, or L, the length of a cache line. Since the structures do not require these details for good performance they are portable across caching systems. Another advantage of such structures isthat the caching results hold for every level of cache within a multilevel cache. Two simple data structures are studied; the array used for binary search and the linear list. As well as being cache oblivious, the structures presented in this thesis are space efficient, requiring little additional storage. We begin the discussion with a layout for a search tree within an array. This layout allows Searches to be performed in O(log n) time and in O(log n/log L) (the optimal number) cache misses. An algorithm for building this layout from a sorted array in linear time is given. One use for this layout is a heap-like implementation of the priority queue. This structure allows Inserts, Heapifies and ExtractMaxes in O(log n) time and O(log nlog L) cache misses. A priority queue using this layout can be builtfrom an unsorted array in linear time. Besides the n spaces required to hold the data, this structure uses a constant amount of additional storage. The cache oblivious linear list allows scans of the list taking Theta(n) time and incurring Theta(n/L) (the optimal number) cache misses. The running time of insertions and deletions is not constant, however it is sub-polynomial. This structure requires e*n additional storage, where e is any constant greater than zero.

High-level modeling formalisms are increasingly popular tools for studying complex systems. Given a high-level model, we can automatically verify certain system properties or compute performance measures about the system. In the general case, measures must be computed using discrete-event simulations. In certain cases, exact numerical analysis is possible by constructing and analyzing the underlying stochastic process of the system, which is a continuous-time Markov chain (CTMC) in our case. Unfortunately, the number of states in the underlying CTMC can be extremely large, even if the high-level model is "small". In this thesis, we develop data structures and techniques that can tolerate these large numbers of states.;First, we present a multi-level data structure for storing the set of reachable states of a model. We then introduce the concept of event "locality", which considers the components of the model that an event may affect. We show how a state generation algorithm using our multi-level structure can exploit event locality to reduce CPU requirements.;Then, we present a symbolic generation technique based on our multi-level structure and our concept of event locality, in which operations are applied to sets of states. The extremely compact data structure and efficient manipulation routines we present allow for the examination of much larger systems than was previously possible.;The transition rate matrix of the underlying CTMC can be represented with Kronecker algebra under certain conditions. However, the use of Kronecker algebra introduces several sources of CPU overhead during numerical solution. We present data structures, including our new data structure called matrix diagrams, that can reduce this CPU overhead. Using our techniques, we can compute measures for large systems in a fraction of the time required by current state-of-the-art techniques.;Finally, we present a technique for approximating stationary measures using aggregations of the underlying CTMC. Our technique utilizes exact knowledge of the underlying CTMC using our compact data structure for the reachable states and a Kronecker representation for the transition rates. We prove that the approximation is exact for models possessing a product-form solution.

Abstraction in computer programming provides a means of reducing complexity by emphasising the significant information (program behaviour) whilst suppressing the immaterial (program implementation). This aids program construction, improves reliability and maintainability, and eases the application of formal correctness proofs. The importance of data abstraction in the specification, design and implementation of large systems raises the question as to whether such methods may be applied in the context of programming languages designed before the widespread use of abstraction techniques. The program structuring facilities available in FORTRAN 77 support a form of encapsulation for simple data structures. In light of this mechanism provided by the language, state-based specification was found to be most appropriate. A specification technique incorporating object-oriented techniques is particularly suitable and allows a library of object classes to be specified and then implemented in sequential FORTRAN 77. Refinement extends the object classes so as to provide the commonly occurring generators for use in iterative constructs. Therefore, the advantages of data abstraction methods may be obtained in an early procedural language such as FORTRAN 77. Data abstraction provides data independence : a change in the representation for a particular class of objects affects only the code that implements the associated operations. This allows parallel implementations to be considered, without changes to the original specification or to any user-code. The provision of such parallel data structures is required for the migration of sequential systems onto parallel distributed memory architectures. As an illustration of this approach a general 2P2-2P (for integer P≥3) search tree utilising a pipeline of processors in a distributed memory architecture is shown to provide a means of implementing the object classes. Variations in both the number of processors allocated to the pipeline and the value of P allows the optimal search structure for a given architecture to be determined. These structures are highly efficient leading to improvements in both throughput and response time as processors are added to the array. An efficient parallel implementation of object classes is therefore achieved within the tight interface provided by abstraction.

This thesis describes the use of nuclear magnetic resonance techniques to determine the structures of two proteins in solution, hen egg-white lysozyme and human interleukin-4. Using 2D ¹H methods an extensive set of structural data has been collected for hen lysozyme (1158 NOE distance restraints, 68 o and 24 _?1 dihedral angle restraints) and these data have been used in distance geometry-dynamical simulated annealing calculations to determine an ensemble of NMR structures for the protein. The overall Ca RMSD from the average for a set of 16 calculated structures is 1.8 ± 0.2 A but, excluding 14 residues in exposed disordered regions, this value reduces to 1.3 ± 0.2 Å. Regions of secondary structure, and particularly the four a helices, are well defined (Ca RMSD 0.8 ± 0.3 Å for helices). Detailed comparisons of the NMR structures with crystal structures of the protein have shown the close similarity of the main chain fold and the conformation of interior side chains in solution and in crystals. ³J_aß coupling constant measurement have indicated, however, that the conformational mobility of the side chains of many surface residues is significantly more pronounced than an individual crystal structure would suggest. For human interleukin-4, a strategy involving ¹⁵N and ¹³C labelled recombinant protein together with heteronuclear 3D NMR techniques has been employed to determine the structure of the protein. The work has provided the first structure for this protein, a left-handed four helix bundle with an up-up-down-down connectivity. For an ensemble of 10 final calculated NMR structures there is a Ca RMSD from the average of 1.6 ± 0.4 Å, the definition of the helical core of the protein being particularly good (0.8 ± 0.2 Å). There is, however, some disorder in the long overhand loops of the structure; this reflects the unusually high conformational mobility of these regions. Comparison of the interleukin-4 structure with proteins with related folds, particularly members of the haemopoietic cytokine superfamily, suggests that the fold found here for interleukin-4 may be the adopted structure throughout this cytokine superfamily. In a postscript to this thesis the NMR structure of human interleukin-4 is shown to have a very similar conformation to a crystal structure of the protein which has been solved very recently.

PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO
CONSELHO NACIONAL DE DESENVOLVIMENTO CIENTÍFICO E TECNOLÓGICO
Séries temporais são ferramentas importantes para análise de eventos que ocorrem em diferentes domínios do conhecimento humano, como medicina, física, meteorologia e finanças. Uma tarefa comum na análise de séries temporais é a busca por eventos pouco frequentes que refletem fatos de interesse sobre o domínio de origem da série. Neste trabalho, buscamos desenvolver técnicas para detecção de eventos raros em séries temporais. Formalmente, uma série temporal A igual a (a1, a2,..., an) é uma sequência de valores reais indexados por números inteiros de 1 a n. Dados dois números, um inteiro t e um real d, dizemos que um par de índices i e j formam um evento-(t, d) em A se, e somente se, 0 menor que j - i menor ou igual a t e aj - ai maior ou igual a d. Nesse caso, i é o início do evento e j o fim. Os parâmetros t e d servem para controlar, respectivamente, a janela de tempo em que o evento pode ocorrer e a magnitude da variação na série. Assim, nos concentramos em dois tipos de perguntas relacionadas aos eventos-(t, d), são elas: - Quais são os eventos-(t, d) em uma série A? - Quais são os índices da série A que participam como inícios de ao menos um evento-(t, d)? Ao longo desse trabalho estudamos, do ponto de vista prático e teórico, diversas estruturas de dados e algoritmos para responder às duas perguntas listadas.
Time series are important tools for the anaylsis of events that occur in different fields of human knowledge such as medicine, physics, meteorology and finance. A common task in analysing time series is to try to find events that happen infrequently as these events usually reflect facts of interest about the domain of the series. In this study, we develop techniques for the detection of rare events in time series. Technically, a time series A equal to (a1, a2,..., an) is a sequence of real values indexed by integer numbers from 1 to n. Given an integer t and a real number d, we say that a pair of time indexes i and j is a (t, d)-event in A, if and only if 0 less than j - i less than or equal to t and aj - ai greater than or equal to d. In this case, i is said to be the beginning of the event and j is its end. The parameters t and d control, respectively, the time window in which the event can occur and magnitude of the variation in the series. Thus, we focus on two types of queries related to the (t, d)-events, which are: - What are the (t, d)-events in a series A? - What are the indexes in the series A which are the beginning of at least one (t, d)-event? Throughout this study we discuss, from both theoretical and practical points of view, several data structures and algorithms to answer the two queries mentioned above.

Data structures are vital entities that strongly impact the efficiency of several software applications. Compactness, predictable memory access patterns, and good temporal and spacial locality of the structure's operations are increasingly becoming essential factors in the selection of a data structure for a specific application. In general, the less data we store and move the better for efficiency and power consumption, especially in infrastructure software and applications for hand-held devices like smartphones. In this dissertation, we extensively study a data structure named lattice data structure (LDS) that is as compact and suitable for memory hierarchies as the array, yet with a rich structure that enables devising procedures with better time bounds.

To achieve performance similar to the performance of the optimal O(log(N)) time complexity of the searching operations of other structures, we provide a hybrid searching algorithm that can be implemented by searching the lattice using the basic searching algorithm when the degree of the sortedness of the lattice is less than or equal to 0.9h, and the jump searching algorithm when the degree of the sortedness of the lattice is greater than 0.9h. A sorting procedure that can be used, during the system idle time, to incrementally increase the degree of sortedness of the lattice is given. We also provide randomized and parallel searching algorithms that can be used instead of the usual jump-and-walk searching algorithms.

A lattice can be represented by a one-dimensional array, where each cell is represented by one array element. The worst case time complexity of the basic LDS operations and the average time complexity of some of the order-statistic operations are better than the corresponding time complexities of most of other data structures operations. This makes the LDS a good choice for memory-constrained systems, for systems where power consumption is a critical issue, and for real-time systems. A potential application of the LDS is to use it as an index structure for in-memory databases.

Compact and succinct data structures use space that approaches the information-theoretic lower bound on the space that is required to represent the data. In practice, their memory footprint is orders of magnitude smaller than normal data structures and at the same time they are competitive in speed. A main drawback with many of these data structures is that they do not support dynamic operations efficiently. It can be exceedingly expensive to rebuild a static data structure each time an update occurs. In this thesis, we propose a number of novel compact dynamic data structures including m-Bonsai, which is a compact tree representation, compact dynamic rewritable (CDRW) arrays which is a compact representation of variable-length bit-strings. These data structures can answer queries efficiently, perform updates fast while they maintain their small memory footprint. In addition to the designing of these data structures, we analyze them theoretically, we implement them and finally test them to show their good practical performance. Many data mining algorithms require data structures that can query and dynamically update data in memory. One such algorithm is FP-growth. It is one of the fastest algorithms for the solution of Frequent Itemset Mining, which is one of the most fundamental problems in data mining. FP-growth reads the entire data in memory, updates the data structures in memory and performs a series of queries on the given data. We propose a compact implementation for the FP-growth algorithm, the PFP-growth. Based on our experimental evaluation, our implementation is one order of magnitude more space efficient compared to the classic implementation of FP-growth and 2 - 3 times compared to a more recent carefully engineered implementation. At the same time it is competitive in terms of speed.

Due to the growth of design size and complexity, design verification is an important aspect of the Logic Circuit development process. The purpose of verification is to validate that the design meets the system requirements and specification. This is done by either functional or formal verification. The most popular approach to functional verification is the use of simulation based techniques. Using models to replicate the behaviour of an actual system is called simulation. In this thesis, a software/data structure architecture without explicit locks is proposed to accelerate logic gate circuit simulation. We call thus system ZSIM. The ZSIM software architecture simulator targets low cost SIMD multi-core machines. Its performance is evaluated on the Intel Xeon Phi and 2 other machines (Intel Xeon and AMD Opteron). The aim of these experiments is to: • Verify that the data structure used allows SIMD acceleration, particularly on machines with gather instructions ( section 5.3.1). • Verify that, on sufficiently large circuits, substantial gains could be made from multicore parallelism ( section 5.3.2 ). • Show that a simulator using this approach out-performs an existing commercial simulator on a standard workstation ( section 5.3.3 ). • Show that the performance on a cheap Xeon Phi card is competitive with results reported elsewhere on much more expensive super-computers ( section 5.3.5 ). To evaluate the ZSIM, two types of test circuits were used: 1. Circuits from the IWLS benchmark suit [1] which allow direct comparison with other published studies of parallel simulators.2. Circuits generated by a parametrised circuit synthesizer. The synthesizer used an algorithm that has been shown to generate circuits that are statistically representative of real logic circuits. The synthesizer allowed testing of a range of very large circuits, larger than the ones for which it was possible to obtain open source files. The experimental results show that with SIMD acceleration and multicore, ZSIM gained a peak parallelisation factor of 300 on Intel Xeon Phi and 11 on Intel Xeon. With only SIMD enabled, ZSIM achieved a maximum parallelistion gain of 10 on Intel Xeon Phi and 4 on Intel Xeon. Furthermore, it was shown that this software architecture simulator running on a SIMD machine is much faster than, and can handle much bigger circuits than a widely used commercial simulator (Xilinx) running on a workstation. The performance achieved by ZSIM was also compared with similar pre-existing work on logic simulation targeting GPUs and supercomputers. It was shown that ZSIM simulator running on a Xeon Phi machine gives comparable simulation performance to the IBM Blue Gene supercomputer at very much lower cost. The experimental results have shown that the Xeon Phi is competitive with simulation on GPUs and allows the handling of much larger circuits than have been reported for GPU simulation. When targeting Xeon Phi architecture, the automatic cache management of the Xeon Phi, handles and manages the on-chip local store without any explicit mention of the local store being made in the architecture of the simulator itself. However, targeting GPUs, explicit cache management in program increases the complexity of the software architecture. Furthermore, one of the strongest points of the ZSIM simulator is its portability. Note that the same code was tested on both AMD and Xeon Phi machines. The same architecture that efficiently performs on Xeon Phi, was ported into a 64 core NUMA AMD Opteron. To conclude, the two main achievements are restated as following: The primary achievement of this work was proving that the ZSIM architecture was faster than previously published logic simulators on low cost platforms. The secondary achievement was the development of a synthetic testing suite that went beyond the scale range that was previously publicly available, based on prior work that showed the synthesis technique is valid.

Linear spatial trees are typically constructed in two discrete, consecutive stages: calculating location codes, and sorting the spatial data according to the codes. Additionally, a GPU R-tree construction algorithm exists which likewise consists of sorting the spatial data and calculating nodes' bounding boxes. Current GPUs are approximately three orders of magnitude faster than CPUs for perfectly vectorizable problems. However, the best known GPU sorting algorithms only achieve 10-20 times speedup over sequential CPU algorithms. Both calculating location codes and bounding boxes are perfectly vectorizable problems. We thus investigate the construction of linear quadtrees, R-trees, and linear k-d trees using the GPU for location code and bounding box calculation, and parallel CPU algorithms for sorting. In this endeavor, we show how existing GPU linear quadtree and R-tree construction algorithms may be modified to be heterogeneous, and we develop a novel linear k-d tree construction algorithm which uses an existing parallel CPU quicksort partition algorithm. We implement these heterogeneous construction algorithms, and we show that heterogeneous construction of spatial data structures can approach the speeds of homogeneous GPU algorithms, while freeing the GPU to be used for better vectorizable problems.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2008.
Includes bibliographical references (p. 135-143).
We describe new techniques for proving lower bounds on data-structure problems, with the following broad consequences: * the first [omega](lg n) lower bound for any dynamic problem, improving on a bound that had been standing since 1989; * for static data structures, the first separation between linear and polynomial space. Specifically, for some problems that have constant query time when polynomial space is allowed, we can show [omega](lg n/ lg lg n) bounds when the space is O(n - polylog n). Using these techniques, we analyze a variety of central data-structure problems, and obtain improved lower bounds for the following: * the partial-sums problem (a fundamental application of augmented binary search trees); * the predecessor problem (which is equivalent to IP lookup in Internet routers); * dynamic trees and dynamic connectivity; * orthogonal range stabbing. * orthogonal range counting, and orthogonal range reporting; * the partial match problem (searching with wild-cards); * (1 + [epsilon])-approximate near neighbor on the hypercube; * approximate nearest neighbor in the l[infinity] metric. Our new techniques lead to surprisingly non-technical proofs. For several problems, we obtain simpler proofs for bounds that were already known.
by Mihai Pǎtraşcu.
Ph.D.

Thesis (MScEng)--Stellenbosch University, 2003.
ENGLISH ABSTRACT: AP230 of STEP is an application protocol for structural steel-framed buildings. Product data relating to steel structures is represented in a model that captures analysis, design and manufacturing views. The information requirements described in AP230 were analysed with the purpose of identifying a subset of entities that are essential for the description of simple industrial steel frames with the view to being able to describe the structural concept, and to perform the structural analysis and design of such structures. Having identified the essential entities, a relational database model for these entities was developed. Planning, analysis and design applications will use the database to collaboratively exchange data relating to the structure. The comprehensiveness of the database model was investigated by mapping a simple industrial frame to the database model. Access to the database is provided by a set of classes called the database representative classes. The data-representatives are instances that have the same selection identifiers and attributes as corresponding information units in the database. The datarepresentatives' primary tasks are to store themselves in the database and to retrieve their state from the database. A graphical user interface application, programmed in Java, used for the description of the structural concept with the capacity of storing the concept in the database and retrieving it again through the use of the database representative classes was also created as part of this project.
AFRIKAANSE OPSOMMING: AP230 van STEP is 'n toepassingsprotokol wat staal raamwerke beskryf. Die produkdata ter beskrywing van staal strukture word saamgevat in 'n model wat analise, ontwerp en vervaardigings oogmerke in aanmerking neem. Die informasie vereistes, soos beskryf in AP230, is geanaliseer om 'n subset van entiteite te identifiseer wat noodsaaklik is vir die beskrywing van 'n eenvoudige nywerheidsstruktuur om die strukturele konsep te beskryf en om die struktuur te analiseer en te ontwerp. Nadat die essensiële entiteite geïdentifiseer is, is 'n relasionele databasismodel van die entiteite geskep. Beplanning, analise en ontwerptoepassings maak van die databasis gebruik om kollaboratief data oor strukture uit te ruil. Die omvattenheid van die databasis-model is ondersoek deur 'n eenvoudige nywerheidsstruktuur daarop afte beeld. Toegang tot die databasis word verskaf deur 'n groep Java klasse wat bekend staan as die verteenwoordigende databasis klasse. Hierdie databasis-verteenwoordigers is instansies met dieselfde identifikasie eienskappe as die ooreenkomstige informasie eenhede in die databasis. Die hoofdoel van die databasis-verteenwoordigers is om hulself in die databasis te stoor asook om hul rang weer vanuit die databasis te verkry. 'n Grafiese gebruikerskoppelvlak, geprogrammeer in Java, is ontwikkel. Die koppelvlak word gebruik om die strukturele konsep te beskryf, dit te stoor na die databasis en om dit weer, met behulp van die databasis-verteenwoordigers, uit die databasis te haal.

Pattern recognition is an important area with potential applications in computer vision, Speech understanding, knowledge engineering, bio-medical data classification, earth sciences, life sciences, economics, psychology, linguistics, etc. Clustering is an unsupervised classification process corning under the area of pattern recognition. There are two types of clustering approaches: 1) Non-hierarchical methods 2) Hierarchical methods. Non-hierarchical algorithms are iterative in nature and. perform well in the context of isotropic clusters. Time-complexity of these algorithms is order of (0 (n) ) and above, Hierarchical agglomerative algorithms, on the other hand, are effective when clusters are non-isotropic. The single linkage method of hierarchical category produces a dendrogram which corresponds to the minimal spanning tree, conventional approaches are time consuming requiring O (n2 ) computational time. In this thesis we propose an intelligent partitioning scheme for generating the minimal spanning tree in the co-ordinate space. This is computationally elegant as it avoids the computation of similarity between many pairs of samples me minimal spanning tree generated can be used to produce C disjoint clusters by breaking the (C-1) longest edges in the tree. A systolic architecture has been proposed to increase the speed of the algorithm further. Simulation study has been conducted and the corresponding results are reported. The simulation package has been developed on DEC-1090 in Pascal. It is observed based on the simulation study that the parallel implementation reduces the time enormously. The number of processors required for the parallel implementation is a constant making the approach more attractive. Texture analysis and synthesis has been extensively studied in the context of computer vision, Two important approaches which have been studied extensively by researchers earlier are statistical and structural approaches, Texture is understood to be a periodic pattern with primitive sub patterns repeating in a particular fashion. This has been used to characterize texture with the help of the hierarchical data structure, tree. It is convenient to use a tree data structure as, along with the operations like merging, splitting, deleting a node, adding a node, etc, .it would be useful to handle a periodic pattern. Various functions like angular second moment, correlation etc, which are used to characterize texture have been translated into the new language of hierarchical data structure.

Pattern recognition is an important area with potential applications in computer vision, Speech understanding, knowledge engineering, bio-medical data classification, earth sciences, life sciences, economics, psychology, linguistics, etc. Clustering is an unsupervised classification process corning under the area of pattern recognition. There are two types of clustering approaches: 1) Non-hierarchical methods 2) Hierarchical methods. Non-hierarchical algorithms are iterative in nature and. perform well in the context of isotropic clusters. Time-complexity of these algorithms is order of (0 (n) ) and above, Hierarchical agglomerative algorithms, on the other hand, are effective when clusters are non-isotropic. The single linkage method of hierarchical category produces a dendrogram which corresponds to the minimal spanning tree, conventional approaches are time consuming requiring O (n2 ) computational time. In this thesis we propose an intelligent partitioning scheme for generating the minimal spanning tree in the co-ordinate space. This is computationally elegant as it avoids the computation of similarity between many pairs of samples me minimal spanning tree generated can be used to produce C disjoint clusters by breaking the (C-1) longest edges in the tree. A systolic architecture has been proposed to increase the speed of the algorithm further. Simulation study has been conducted and the corresponding results are reported. The simulation package has been developed on DEC-1090 in Pascal. It is observed based on the simulation study that the parallel implementation reduces the time enormously. The number of processors required for the parallel implementation is a constant making the approach more attractive. Texture analysis and synthesis has been extensively studied in the context of computer vision, Two important approaches which have been studied extensively by researchers earlier are statistical and structural approaches, Texture is understood to be a periodic pattern with primitive sub patterns repeating in a particular fashion. This has been used to characterize texture with the help of the hierarchical data structure, tree. It is convenient to use a tree data structure as, along with the operations like merging, splitting, deleting a node, adding a node, etc, .it would be useful to handle a periodic pattern. Various functions like angular second moment, correlation etc, which are used to characterize texture have been translated into the new language of hierarchical data structure.

Composite materials are steadily replacing traditional materials in a wide range of industry sectors thanks to their remarkable properties. Damage in composite materials exhibits complex failure modes which are difficult to identify by conventional techniques. Composite materials demonstrate complex nonlinear vibration behaviour where conventional vibration-based structural health monitoring (VSHM) methods might not give adequate information for damage identification. This thesis investigates the capabilities of singular spectrum analysis (SSA) as a technique for developing a completely data-based VSHM methodology. The methodology decomposes the vibration responses in a certain number of principal components having in consideration all rotational patterns at any frequency including the nonlinear oscillations. This thesis develops two approaches to use SSA in the time and frequency domain. The methodology has been validated using a numerical system and an experiment with delaminated beams. The results demonstrate the methodology capability for assessing damages at different locations and with different sizes. The progression of damage can also be tracked. Delamination was successfully assessed in composite laminated plates with different delamination locations, in-plane and through different layers. Damage in wind turbine blades was assessed by the damage assessment methodology with a statistical hypothesis inspection phase based on probability distribution functions. Different damage locations and sizes were assessed as well as damage progression. This thesis explores the use of smart materials which enable self-sensing and self-diagnosing of its structural integrity coupled with the data-based VSHM. The results demonstrate the substantial potential of this approach. Overall, the data-based VSHM methodology presented in this thesis is proven to give adequate information about the presence, location and extent of delamination and other defects in different composite laminated structures.

Pervasive computing or ambient computing aims to integrate information systems into the environment, in a manner as transparent as possible to the users. It allows the information systems to be tightly coupled with the physical activities within the environment. Everyday used objects, along with their environment, are made smarter with the use of embedded computing, sensors etc. and also have the ability to communicate among themselves. In pervasive computing, it is necessary to sense the real physical world and to perceive its "context" ; a high level representation of the physical situation. There are various ways to derive the context. Typically, the approach is a multi-step process which begins with sensing. Various sensing technologies are used to capture low level information of the physical activities, which are then aggregated, analyzed and computed elsewhere in the information systems, to become aware of the context. Deployed applications then react, depending on the context situation. Among sensors, RFID is an important emerging technology which allows a direct digital link between information systems and physical objects. Besides storing identification data, RFID also provides a general purpose storage space on objects, enabling new architectures for pervasive computing. In this thesis, we defend an original approach adopting the later use of RFID i.e. a digital memory integrated to real objects. The approach uses the principle where the objects self-support information systems. This way of integration reduces the need of communication for remote processing. The principle is realized in two ways. First, objects are piggybacked with semantic information, related to itself ; as self-describing objects. Hence, relevant information associated with the physical entities are readily available locally for processing. Second, group of related objects are digitally linked using dedicated or ad-hoc data structure, distributed over the objects. Hence, it would allow direct data processing - like validating some property involving the objects in proximity. This property of physical relation among objects can be interpreted digitally from the data structure ; this justifies the appellation "Tangible Data Structures". Unlike the conventional method of using identifiers, our approach has arguments on its benefits in terms of privacy, scalability, autonomy and reduced dependency with respect to infrastructure. But its challenge lies in the expressivity due to limited memory space available in the tags. The principles are validated by prototyping in two different application domains. The first application is developed for waste management domain that helps in efficient sorting and better recycling. And the second, provides added services like assistance while assembling and verification for composite objects, using the distributed data structure across the individual pieces.

This thesis extends the study of the notion of termination equivalence of abstract structures first proposed by Kfoury. The connection with abstract data types (ADTs) is made by demonstrating that many kinds of equivalence between ADT implementations are in fact instances of termination equivalence between their underlying algebras. The results in the thesis extend the original work in two directions. The first is to consider how the termination equivalence of structures is dependent upon the choice of programming formalism. The termination equivalences for all of the common classes of programs and for some new classes of non-computable schemes are studied, and their relative strengths are established. The other direction is a study of a congruence property of equivalences relative to the join or addition datatype building operation. We decide which of the termination equivalences are congruences for all structures and for all computable structures, and for those equivalences which are not, we characterise those congruences closest to them (both stronger and weaker). These programmes of work involved the use of constructions and properties of structures relating to program termination which are of interest in themselves. These are examined and are used to prove some general results about the relative strengths of termination equivalences.

Negli ultimi anni è nato un interesse sempre crescente verso l’analisi statistica di dati spaziali aventi supporto di network. Gli esempi più classici di questa tipologia di eventi sono, ad esempio, gli incidenti stradali, i furti di auto, i crimini, e gli interventi delle ambulanze, mentre le linee che compongono la network rappresentano tipicamente le strade, i fiumi, i binari della ferrovia, oppure le terminazioni nervose. L’analisi di questi fenomeni è interessante sotto diversi punti di vista. Innanzitutto, i modelli statistici presentano diverse problematiche legate al supporto spaziale. Per questo motivo, negli ultimi anni sono stati pubblicati diversi paper che mostrano le difficoltà principali legate alla natura stessa della network. Inoltre, il recente sviluppo di database spaziali open source (quali Open Street Map) ha permesso il download e la creazione di dataset che coprono le reti stradali di quasi tutto il mondo. L’enorme mole di dati e gli (inevitabili) errori geometrici presenti nei database di Open Street Map rappresentano due problematiche ulteriori. Infine, dato che al momento la maggior parte dei pacchetti R per l’analisi di dati su network sono ancora in fase di sviluppo, esistono anche diverse difficoltà computazionali e problemi nell’implementazione di metodologie nuove. Questo lavoro di tesi riassume quattro articoli che presentano strutture dati e metodologie statistiche per l’analisi di dati spaziali aventi supporto di network, considerando sia un approccio di tipo network-lattice che un approccio di tipo point-pattern. Il primo paper presenta una revisione bibliografica dei pacchetti R che implementano classi e funzioni per l’analisi di network stradali, concentrandosi in particolare su stplanr e dodgr. Vengono introdotte le principali routines legate al calcolo di shortest paths e centrality measures utilizzando dataset via via più complessi. Il secondo lavoro presenta un modello di Poisson Dinamico Zero Inflated per la stima di due indici di rischiosità relativi agli incidenti stradali avvenuti nel network di Milano dal 2015 al 2017. L’unità statistica elementare è rappresentata dal singolo segmento di strada, mentre la variabile risposta misura il numero di incidenti avvenuti in ognuno dei tre anni. Viene impiegato un insieme di covariate demografiche e strutturali estratte da Open Street Map e dai dati del censimento italiano avvenuto nel 2011. Il terzo paper introduce un modello Bayesiano gerarchico multivariato per la stima della rischiosità stradale tramite un approccio di tipo network-lattice. Ci si è concentrati sul network stradale della città di Leeds e su due diverse tipologie di incidenti. La componente spaziale è stata modellata tramite un errore casuale di tipo Multivariate CAR, mentre le correlazioni residue sono state catturate tramite un errore casuale non strutturato. Infine, si è anche sviluppata una metodologia nuova per l’analisi di MAUP su dati di tipo network-lattice. Per concludere, il quarto articolo presenta un insieme di risultati preliminari relativi all’analisi spazio-temporale di point pattern su network tramite processi di Poisson non-omogenei. In particolare, si è analizzata la distribuzione degli interventi delle ambulanze nel comune di Milano tra il 2015 ed il 2017, sviluppando un modello a fattori latenti per la componente temporale ed uno stimatore kernel non-parametrico per l’intensità spaziale, riadattato nel caso di dati su reticolo. La tesi si compone anche di tre appendici. Le prima riassume le caratteristiche di base del software e della metodologia INLA, la seconda presenta i materiali addizionali legati al quarto capitolo, mentre la terza appendice introduce un pacchetto R chiamato osmextract, utilizzato per manipolare dati da Open Street Map. Il quinto capitolo conclude la tesi, riassumendo i risultati principali e introducendo alcuni sviluppi futuri.
In the last years, we observed a surge of interest in the statistical analysis of spatial data lying on or alongside networks. Car crashes, vehicle thefts, bicycle incidents, roadside kiosks, neuroanatomical features, and ambulance interventions are just a few of the most typical examples, whereas the edges of the network represent an abstraction of roads, rivers, railways, cargo-ship routes or nerve fibers. This type of data is interesting for several reasons. First, the statistical analysis of the events presents several challenges because of the complex and non-homogeneous nature of the network, which creates unique methodological problems. Several authors discussed and illustrated the common pitfalls of re-adapting classical planar spatial models to network data. Second, the rapid development of open-source spatial databases (such as Open Street Map) provides the starting point for creating road networks at a wide range of spatial scales. The size and volume of the data raise complex computational problems, while common geometrical errors in the network’s software representations create another source of complexity. Third, at the time of writing, the most important software routines and functions (mainly implemented in R) are still in the process of being re-written and readapted for the new spatial support. This manuscript collects four articles presenting data structures and statistical models to analyse spatial data lying on road networks using point-pattern and network-lattice approaches. The first paper reviews classes, vital pre-processing steps and software representations to manipulate road network data. In particular, it focuses on the R packages stplanr and dodgr, highlighting their main functionalities, such as shortest paths or centrality measures, using a range of datasets, from a roundabout to a complete network covering an urban city. The second paper proposes the adoption of two indices for assessing the risk of car crashes on the street network of a metropolitan area via a dynamic zero-inflated Poisson model. The elementary statistical units are the road segments of the network. It employs a set of open-source spatial covariates representing the network’s structural and demographic characteristics (such as population density, traffic lights or crossings) extracted from Open Street Map and 2011 Italian Census. The third paper demonstrates a Bayesian hierarchical model for identifying road segments of particular concern using a network-lattice approach. It is based on a case study of a major city (Leeds, UK), in which car crashes of different severities were recorded over several years. It includes spatially structured and unstructured random effects to capture the spatial nature of the events and the dependencies between the severity levels. It also recommends a novel procedure for estimating the MAUP (Modifiable Areal Unit Problem) for network-lattice data. Finally, the fourth paper summarises a set of preliminary results related to the analysis of spatio-temporal point patterns lying on road networks using non-homogeneous Poisson processes. It focuses on the ambulance interventions that occurred in the municipality of Milan from 2015 to 2017, developing two distinct models, one for the spatial component and one for the temporal component. The spatial intensity function was estimated using a network readaptation of the classical non-parametric kernel estimator. The first two appendices briefly review the basics of INLA methodology, the corresponding R package and the supplementary materials related to the fourth chapter, while the third appendix briefly introduces an R package, named osmextract, that was developed during the PhD and focuses on Open Street Map data. The fifth chapter concludes the manuscript, summarising the main contributions and emphasising future research developments.

Aquesta tesi està dedicada al disseny i a l'anàlisi d'estructures de dades multidimensionals, és a dir, estructures de dades que serveixen per emmagatzemar registres $K$-dimensionals que solen representar-se com a punts en l'espai $[0,1]^K$. Aquestes estructures tenen aplicacions en diverses àrees de la informàtica com poden ser els sistemes d'informació geogràfica, la robòtica, el processament d'imatges, la world wide web, el data mining, entre d'altres.

Les estructures de dades multidimensionals també es poden utilitzar com a indexos d'estructures de dades que emmagatzemen, possiblement en memòria externa, dades més complexes que els punts.

Les estructures de dades multidimensionals han d'oferir la possibilitat de realitzar operacions d'inserció i esborrat de claus dinàmicament, a més de permetre realitzar cerques anomenades associatives. Exemples d'aquest tipus de cerques són les cerques per rangs ortogonals (quins punts cauen dintre d'un hiper-rectangle donat?) i les cerques del veí més proper (quin és el punt més proper a un punt donat?).

Podem dividir les contribucions d'aquesta tesi en dues parts:

La primera part està relacionada amb el disseny d'estructures de dades per a punts multidimensionals. Inclou el disseny d'arbres binaris $K$-dimensionals al·leatoritzats (Randomized $K$-d trees), el d'arbres quaternaris al·leatoritzats (Randomized quad trees) i el d'arbres multidimensionals amb punters de referència (Fingered multidimensional trees).

La segona part analitza el comportament de les estructures de dades multidimensionals. En particular, s'analitza el cost mitjà de les cerques parcials en arbres $K$-dimensionals relaxats, i el de les cerques per rang en diverses estructures de dades multidimensionals.

Respecte al disseny d'estructures de dades multidimensionals, proposem algorismes al·leatoritzats d'inserció i esborrat de registres per als arbres $K$-dimensionals i per als arbres quaternaris. Aquests algorismes produeixen arbres aleatoris, independentment de l'ordre d'inserció dels registres i desprès de qualsevol seqüència d'insercions i esborrats. De fet, el comportament esperat de les estructures produïdes mitjançant els algorismes al·leatoritzats és independent de la distribució de les dades d'entrada, tot i conservant la simplicitat i la flexibilitat dels arbres $K$-dimensionals i quaternaris estàndard. Introduïm també els arbres multidimensionals amb punters de referència. Això permet que les estructures multidimensionals puguin aprofitar l'anomenada localitat de referència en cerques associatives altament correlacionades.

I respecte de l'anàlisi d'estructures de dades multidimensionals, primer analitzem el cost esperat de las cerques parcials en els arbres $K$-dimensionals relaxats. Seguidament utilitzem aquest resultat com a base per a l'anàlisi de les cerques per rangs ortogonals, juntament amb arguments combinatoris i geomètrics. D'aquesta manera obtenim un estimat asimptòtic precís del cost de les cerques per rangs ortogonals en els arbres $K$-dimensionals aleatoris. Finalment, mostrem que les tècniques utilitzades es poden estendre fàcilment a d'altres estructures de dades i per tant proporcionem una anàlisi exacta del cost mitjà de cerques per rang en estructures de dades com són els arbres $K$-dimensionals estàndard, els arbres quaternaris, els tries quaternaris i els tries $K$-dimensionals.
Esta tesis está dedicada al diseño y al análisis de estructuras de datos multidimensionales; es decir, estructuras de datos específicas para almacenar registros $K$-dimensionales que suelen representarse como puntos en el espacio $[0,1]^K$. Estas estructuras de datos tienen aplicaciones en diversas áreas de la informática como son: los sistemas de información geográfica, la robótica, el procesamiento de imágenes, la world wide web o data mining, entre otras.

Las estructuras de datos multidimensionales suelen utilizarse también como índices de estructuras que almacenan, posiblemente en memoria externa, datos complejos.

Las estructuras de datos multidimensionales deben ofrecer la posibilidad de realizar operaciones de inserción y borrado de llaves de manera dinámica, pero además deben permitir realizar búsquedas asociativas en los registros almacenados. Ejemplos de búsquedas asociativas son las búsquedas por rangos ortogonales (¿qué puntos de la estructura de datos están dentro de un hiper-rectángulo dado?) y las búsquedas del vecino más cercano (¿cuál es el punto de la estructura de datos más cercano a un punto dado?).

Las contribuciones de esta tesis se dividen en dos partes:

La primera parte está dedicada al diseño de estructuras de datos para puntos multidimensionales, que incluye el diseño de los árboles binarios $K$-dimensionales aleatorios (Randomized $K$-d trees), el de los árboles cuaternarios aleatorios (Randomized quad trees), y el de los árboles multidimensionales con punteros de referencia (Fingered multidimensional trees).
La segunda parte contiene contribuciones al análisis del comportamiento de las estructuras de datos para puntos multidimensionales. En particular, damos el análisis del costo promedio de las búsquedas parciales en los árboles $K$-dimensionales relajados y el de las búsquedas por rango en varias estructuras de datos multidimensionales.


Con respecto al diseño de estructuras de datos multidimensionales, proponemos algoritmos aleatorios de inserción y borrado de registros para los árboles $K$-dimensionales y los árboles cuaternarios que producen árboles aleatorios independientemente del orden de inserción de los registros y después de cualquier secuencia de inserciones y borrados intercalados. De hecho, con la aleatorización garantizamos un buen rendimiento esperado de las estructuras de datos resultantes, que es independiente de la distribución de los datos de entrada, conservando la flexibilidad y la simplicidad de los árboles $K$-dimensionales y de los árboles cuaternarios estándar. También proponemos los árboles multidimensionales con punteros de referencia, una técnica que permite que las estructuras de datos multidimensionales exploten la localidad de referencia en búsquedas asociativas que se presentan altamente correlacionadas.

Con respecto al análisis de estructuras de datos multidimensionales, comenzamos dando un análisis preciso del costo esperado de las búsquedas parciales en los árboles $K$-dimensionales relajados. A continuación, utilizamos este resultado como base para el análisis de las búsquedas por rangos ortogonales, combinándolo con argumentos combinatorios y geométricos. Como resultado obtenemos un estimado asintótico preciso del costo de las búsquedas por rango en los árboles $K$-dimensionales relajados. Finalmente, mostramos que las técnicas utilizadas pueden extenderse fácilmente a otras estructuras de datos y por tanto proporcionamos un análisis preciso del costo promedio de búsquedas por rango en estructuras de datos como los árboles $K$-dimensionales estándar, los árboles cuaternarios, los tries cuaternarios y los tries $K$-dimensionales.
This thesis is about the design and analysis of point multidimensional data structures: data structures that store $K$-dimensional keys which we may abstract as points in $[0,1]^K$. These data structures are present in many applications of geographical information systems, image processing or robotics, among others. They are also frequently used as indexes of more complex data structures, possibly stored in external memory.

Point multidimensional data structures must have capabilities such as insertion, deletion and (exact) search of items, but in addition they must support the so called {em associative queries}. Examples of these queries are orthogonal range queries (which are the items that fall inside a given hyper-rectangle?) and nearest neighbour queries (which is the closest item to some given point?).

The contributions of this thesis are two-fold:

Contributions to the design of point multidimensional data structures: the design of randomized $K$-d trees, the design of randomized quad trees and the design of fingered multidimensional search trees;
Contributions to the analysis of the performance of point multidimensional data structures: the average-case analysis of partial match queries in relaxed $K$-d trees and the average-case analysis of orthogonal range queries in various multidimensional data structures.


Concerning the design of randomized point multidimensional data structures, we propose randomized insertion and deletion algorithms for $K$-d trees and quad trees that produce random $K$-d trees and quad trees independently of the order in which items are inserted into them and after any sequence of interleaved insertions and deletions. The use of randomization provides expected performance guarantees, irrespective of any assumption on the data distribution, while retaining the simplicity and flexibility of standard $K$-d trees and quad trees.

Also related to the design of point multidimensional data structures is the proposal of fingered multidimensional search trees, a new technique that enhances point multidimensional data structures to exploit locality of reference in associative queries.

With regards to performance analysis, we start by giving a precise analysis of the cost of partial matches in randomized $K$-d trees. We use these results as a building block in our analysis of orthogonal range queries, together with combinatorial and geometric arguments and we provide a tight asymptotic estimate of the cost of orthogonal range search in randomized $K$-d trees. We finally show that the techniques used apply easily to other data structures, so we can provide an analysis of the average cost of orthogonal range search in other data structures such as standard $K$-d trees, quad trees, quad tries, and $K$-d tries.

The main question explored in this thesis is how to define novel parallel random-access data structures for surface and image spatial data with efficient construction, storage, and query memory access patterns. Our main contribution is a set of parallel-efficient methods to evaluate irregular, sparse or even implicit geometries and textures in different applications: a method to decouple shape and shading details from high-resolution meshes, mapping them interactively onto lower resolution simpler domains; an editable framework to map highresolution meshes to simpler cube-based domains, generating a parallel-friendly quad-based representation; a new parallel hashing scheme compacting spatial data with high load factors, which has the unique advantage of exploiting spatial coherence in input data and access patterns
La qüestió principal explorada en aquesta tesi doctoral és la forma de definir noves formes d'accés aleatori paral•lel en estructures de dades amb informació de superfícies i d'imatge. La nostra principal aportació és un conjunt de mètodes paral•lels i eficients per avaluar imatges i geometries irregulars, i proposem: un mètode per a separar la forma i els detalls d'aparença visual partint de malles d'alta resolució, mapejant de manera interactiva la informació en dominis més simples de baixa resolució; un marc d'edició geomètrica per convertir malles irregulars de triangles d'alta resolució en representacions més simples basades en un domini de cubs, generant una estructura fàcilment paral•lelitzable basada en primitives quadrangulars; un nou esquema de hashing paral•lel per a la organització i compactació de dades espacials amb un elevat factor de càrrega, explotant la coherència espacial de les dades d'entrada i els seus patrons d'accés a memòria

Most applications require storing multiple versions of data and involve a lot of temporal semantics in their schema. This requires maintenance and querying of temporal relations. A Bitemporal DBMS will simplify the development and maintenance of such applications by moving temporal support from the application into the DBMS engine. The success of such Bitemporal DBMSs relies mainly on the availability of high performance indices that handle update and search operations efficiently. A successful associative data structure (index) is the one that can efficiently partition the space of the attributes that are used within the keys. Temporal attributes have unique characteristics and should support now-relative intervals. These intervals grow as time grows and thus we need an index that can handle attributes with variable values. The proposed bitemporal index partitions the bitemporal space into four subspaces according to the end value of the temporal intervals. This results in separating those keys that have variable intervals from those that have fixed interval(s). In this thesis we have used on-the-shelf index that successfully indexes spatial attributes. But instead of representing the two temporal dimensions as a rectangle, we have represented them as 4 dimensional points. This results in better partitioning of each subtree space and in better search performance.

Distributed memory parallel architectures support a memory model where some memory accesses are local, and thus inexpensive, while other memory accesses are remote, and potentially quite expensive. In order to achieve efficiency on such architectures, we need to reduce remote accesses. This is particularly challenging for applications that use dynamic data structures.
In this thesis, I present two compiler techniques to reduce the overhead of remote memory accesses for dynamic data structure based applications: locality techniques and communication optimizations. Locality techniques include a static locality analysis, which statically estimates when an indirect reference via a pointer can be safely assumed to be a local access, and dynamic locality checks, which consists of runtime tests to identify local accesses. Communication techniques include: (1) code movement to issue remote reads earlier and writes later; (2) code transformations to replace repeated/redundant remote accesses with one access; and (3) transformations to block or pipeline a group of remote requests together. Both locality and communication techniques have been implemented and incorporated into our EARTH-McCAT compiler framework, and a series of experiments have been conducted to evaluate these techniques. The experimental results show that we are able to achieve up to 26% performance improvement with each technique alone, and up to 29% performance improvement when both techniques are applied together.

The topic of this thesis revolves around the organization of geographical information in permanent memory. Our premise is that a recognized and fully documented direct access storage technique called Multidimensional Paging or Multipaging would provide a well balanced storing structure for this category of data. Since multipaging uses a multidimensional perspective on the information to allocate it to pages in secondary storage then spatial data, which is fundamentally multidimensional by nature, would surely offer a suitable profile.
First, we attempt to evaluate the efficiency of multipaging on static files and to suggest possible modifications to the standard algorithm to better serve spatial data.
Our solution to this problem consists in compressing the pages that overflow. Because geographical information is often a representation of occurences of Nature, we hypothesize that Fractal Geometry, which serves to formalize a mathematical description of such elements, could provide the theoretical background to derive an efficient fractal-based compression algorithm. An appreciable improvement is obtained by compressing the pages of the multipaged administrative regions data that exceed their capacity: $ alpha=0.7272$ and $ pi=1.0$.
The outcome of these experiments led us to elaborate a mixed system based on two relatively different approaches: multipaging and fractal-based data compression. The first part consisted in the implementation of the standard static multipaging algorithm using a relational database management system named Relix. The other approach was developed using the C programming language to accommodate some particularities of the multipaged spatial data. The preliminary results were encouraging and allowed us to establish the parameters for a more formal implementation. Also, it brought out the limits of the compression method in view of the intended usage of the data. (Abstract shortened by UMI.)

Approved for public release; distribution is unlimited
The emergence and recent ubiquity of Smartphones present new opportunities and challenges to forensic examiners. Smartphones enable new mobile application and use paradigms by being constantly attached to the Internet via one of several physical communication media, e.g. cellular radio, WiFi, or Bluetooth. The Smartphone's storage medium represents a potential source of current and historical network metadata and records of prior data transfers. By using known ground truth data exchanges in a controlled experimental environment, this thesis identifies network metadata stored by the Android operating system that can be readily retrieved from the device's internal non-volatile storage. The identified network metadata can ascertain the identity of prior network access points to which the device associated. An important by-product of this research is a well-labeled Android Smartphone image corpus, allowing the mobile forensic community to perform repeatable, scientific experiments, and to test mobile forensic tools.

Modifications have been made to the programs used at Edinburgh for the analysis of the nuclear magnetic resonance spectra of molecules dissolved in liquid crystal solvents. In addition, an investigation has been made into the use of molecular mechanics force fields to calculate vibrational corrections to diffraction and spectroscopic data, necessary if a structural analysis is to be carried out using data from diverse sources. The technique of combined analysis has been applied to the structural determination of the three isomeric difluorobenzenes and to 2-chloropyrimidine, 3,6-dichloropyridazine and 2,6-dichloropyrazine. Data from electron diffraction, microwave spectroscopy and liquid crystal nuclear magnetic resonance spectroscopy have been used in these analyses, with varying degrees of success. The geometries obtained are largely consistent with results obtained for molecules of the same class.

Background: Dynamic programming algorithms provide exact solutions to many problems in computational biology, such as sequence alignment, RNA folding, hidden Markov models (HMMs), and scoring of phylogenetic trees. Structurally analogous algorithms compute optimal solutions, evaluate score distributions, and perform stochastic sampling. This is explained in the theory of Algebraic Dynamic Programming (ADP) by a strict separation of state space traversal (usually represented by a context free grammar), scoring (encoded as an algebra), and choice rule. A key ingredient in this theory is the use of yield parsers that operate on the ordered input data structure, usually strings or ordered trees. The computation of ensemble properties, such as a posteriori probabilities of HMMs or partition functions in RNA folding, requires the combination of two distinct, but intimately related algorithms, known as the inside and the outside recursion. Only the inside recursions are covered by the classical ADP theory. Results: The ideas of ADP are generalized to a much wider scope of data structures by relaxing the concept of parsing. This allows us to formalize the conceptual complementarity of inside and outside variables in a natural way. We demonstrate that outside recursions are generically derivable from inside decomposition schemes. In addition to rephrasing the well-known algorithms for HMMs, pairwise sequence alignment, and RNA folding we show how the TSP and the shortest Hamiltonian path problem can be implemented efficiently in the extended ADP framework. As a showcase application we investigate the ancient evolution of HOX gene clusters in terms of shortest Hamiltonian paths. Conclusions: The generalized ADP framework presented here greatly facilitates the development and implementation of dynamic programming algorithms for a wide spectrum of applications.