Thesis (M.Phil.)--Hong Kong University of Science and Technology, 2005. / Includes bibliographical references (leaves 19-20). Also available in electronic version.

Thesis (Ph. D.)--Carnegie Mellon University, 2005. / "May 2005." Includes bibliographical references.

Thesis (Ph. D.)--University of Florida, 2001. / Title from first page of PDF file. Document formatted into pages; contains x, 100 p.; also contains graphics. Vita. Includes bibliographical references (p. 95-99).

Thesis (Ph. D.)--University of Texas at Austin, 2007. / Vita. Includes bibliographical references.

This thesis introduces and explores the notion of bicontext, an order-enriched category equipped with a unary endofunctor of order two called reverse. The purpose is threefold. First, the important categories that arise in Scott-Strachey denotational semantics have this additional structure, where by the constructions used to solve "data-type equations" are both limits and colimits simultaneously. Second, it yields a pleasant "set-theoretic" treatment of algebraic data-types in terms of bicontexts of (1, 1) relations rather than pairs of continuous functions. The theory provides a general way of relating bicontexts which serves to connect these particular ones. Third, the least solutions of data-type equations often have an associated principle of structural induction. Properties in such solutions become arrows in the appropriate bicontext, making the defining functor directly applicable to them. In this way the structural induction can be derived systematically from the functor.

Orientador: Orlando Lee / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-09T17:25:07Z (GMT). No. of bitstreams: 1 Neves_PatriciaTakaki_M.pdf: 4451114 bytes, checksum: c4fcf2f5d76f36075020307255c1470c (MD5) Previous issue date: 2007 / Resumo: O problema de encontrar caminhos mínimos em um grafo com pesos nas arestas é considerado fundamental em otimização combinatória. Diversos problemas do mundo real podem ser modelados dessa forma: percurso mais curto/rápido entre duas cidades, transmissão de dados em uma rede de computadores, reconhecimento de voz, segmentação de imagens entre outros. O algoritmo proposto por Dijkstra em 1959 resolve o problema de caminhos mínimos em grafos sem arestas de peso negativo, o que não chega a ser restritivo na maior parte das aplicações. Desde então, o algoritmo tem sido refinado com o uso de estruturas de dados cada vez mais sofisticadas, reduzindo seu tempo de execução de pior caso (ao menos, do ponto de vista teórico). Recentemente, problemas de caminhos mínimos têm aparecido no contexto de Sistemas de Informação Geográfica (SIG). Neste modelo, o usuário faz consultas ao sistema para encontrar o trajeto mais curto (ou rápido) entre dois pontos especificados (problema ponto-a-ponto ou problema P2P). Além disso, pode haver várias consultas. Instâncias neste tipo de modelo são relativamente grandes: o mapa rodoviário dos Estados Unidos tem mais de 20 milhões de vértices (cada vértice representa intersecções de vias). Mesmo as implementações mais sofisticadas do algoritmo de Dijkstra não apresentam um desempenho prático capaz de atender às demandas que esse tipo de modelo requer. A pesquisa recente tem tentado reduzir este gap entre a teoria e a prática. Várias técnicas de aceleração de algoritmos têm sido propostas e implementadas: busca bidirecional, algoritmo A*, alcance (reach), landmarks e muitos outros. Algumas dessas técnicas têm restrições de domínio e outras podem ser usadas em qualquer contexto. Neste trabalho, estudamos algumas variações da versão original do algoritmo de Dijkstra, caracterizadas pelas diferentes estruturas de dados. Implementamos quatro dessas variações e realizamos testes experimentais utilizando os mapas do mundo real. Nosso objetivo foi analisar o desempenho prático dessas. Dedicamos também uma atenção especial ao problema P2P, apresentando algumas das principais técnicas de aceleração / Abstract: The problem of finding shortest paths in a weighted graph is a fundamental one in combinatorial optimization. Several real world problems can be modeled in this way: shortest or fastest tour between two cities, data transmission on a computer network, voice recognition, image segmentation among others. The algorithm proposed by Dijkstra in 1959 solves this problem when the graph has no edge with negative weight, which is not a serious restriction in most applications. Since then, the algorithm has been improved with the use of sophisticated data structures, reducing the worst case running time (at least, from a theoretical viewpoint). Recently shortest path problems has appeared in the context of Geographic Information System (GIS). In this model, the user asks the system to find out the shortest path between two given points (point-to-point problem or P2P problem). Moreover, there can be several queries. Instances in this model are relatively large: the road network map of the United States has more than 20 million vertices (each vertex represents an intersection of two roads). Even the fastest implementations of Dijkstra's algorithm do not have a performance in practice which is satisfactory to meet the requirements of this model. Recent research has tried to reduce this gap between theory and practice. Several speed-up techniques for these algorithms have been proposed and implemented: bidirectional search, algorithm A*, reach, landmarks and many others. Some of them are domain-restricted and others are applicable in any context. In this work, we studied some variants of Dijkstra's algorithm characterized by its different data structures. We have implemented four of those variants and performed experimental tests using real-world maps. Our goal was to analyze their practical performance. We also paid special attention to the P2P problem, and presented some of the main speed-up techniques / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

The Digital Library Research Laboratory (DLRL) has collected over 1.5 billion tweets for the Integrated Digital Event Archiving and Library (IDEAL) and Global Event Trend Archive Research (GETAR) projects. Researchers across varying disciplines have an interest in leveraging DLRL's collections of tweets for their own analyses. However, due to the steep learning curve involved with the required tools (Spark, Scala, HBase, etc.), simply converting the Twitter data into a workable format can be a cumbersome task in itself. This prompted the effort to build a framework that will help in developing code to analyze the Twitter data, run on arbitrary tweet collections, and enable developers to leverage projects designed with this general use in mind. The intent of this thesis work is to create an extensible framework of tools and data structures to represent Twitter data at a higher level and eliminate the need to work with raw text, so as to make the development of new analytics tools faster, easier, and more efficient. To represent this data, several data structures were designed to operate on top of the Hadoop and Spark libraries of tools. The first set of data structures is an abstract representation of a tweet at a basic level, as well as several concrete implementations which represent varying levels of detail to correspond with common sources of tweet data. The second major data structure is a collection structure designed to represent collections of tweet data structures and provide ways to filter, clean, and process the collections. All of these data structures went through an iterative design process based on the needs of the developers. The effectiveness of this effort was demonstrated in four distinct case studies. In the first case study, the framework was used to build a new tool that selects Twitter data from DLRL's archive of tweets, cleans those tweets, and performs sentiment analysis within the topics of a collection's topic model. The second case study applies the provided tools for the purpose of sociolinguistic studies. The third case study explores large datasets to accumulate all possible analyses on the datasets. The fourth case study builds metadata by expanding the shortened URLs contained in the tweets and storing them as metadata about the collections. The framework proved to be useful and cut development time for all four of the case studies. / Master of Science

Hidden undesired functionality is an unavoidable reality in any complex hardware or software component. Undesired functionality — deliberately introduced Trojan horses or accidentally introduced bugs — in any component of a system can be exploited by attackers to exert control over the system. This poses a serious security risk to systems — especially in the ever growing number of systems based on networks of computers. The approach adopted in this dissertation to secure systems seeks immunity from hidden functionality. Specifcally, if a minimal trusted computing base (TCB) for any system can be identifed, and if we can eliminate hidden functionality in the TCB, all desired assurances regarding the operation of the system can be guaranteed. More specifcally, the desired assurances are guaranteed even if undesired functionality may exist in every component of the system outside the TCB. A broad goal of this dissertation is to characterize the TCB for various systems as a set of functions executed by a trusted security kernel. Some constraints are deliberately imposed on the security kernel functionality to reduce the risk of hidden functionality inside the security kernel. In the security model adopted in this dissertation, any system is seen as an interconnection of subsystems, where each subsystem is associated with a security kernel. The security kernel for a subsystem performs only the bare minimal tasks required to assure the integrity of the tasks performed by the subsystem. Even while the security kernel functionality may be different for each system/subsystem, it is essential to identify reusable components of the functionality that are suitable for a wide range of systems. The contribution of the research is a versatile data-structure — Ordered Merkle Tree (OMT), which can act as the reusable component of various security kernels. The utility of OMT is illustrated by designing security kernels for subsystems participating in, 1) a remote fle storage system, 2) a generic content distribution system, 3) generic look-up servers, 4) mobile ad-hoc networks and 5) the Internet’s routing infrastructure based on the border gateway protocol (BGP).

No description available.

No description available.