Abstract: Geographic data are useful for a large set of applications, such as urban planning and environmental control. These data are, however, very expensive to acquire and maintain. Moreover, their use is often restricted, for lack of dissemination mechanisms. Digital libraries are a good approach for increasing data availability and therefore reducing cost, since they provide efficient storage and access to large volumes of data. Geographic applications can diminish their costs by reusing and sharing data through Geographic Digital Libraries (GDL). One major drawback to this approach is that it creates the necessity of providing facilities for a large and heterogeneous community of users to search and interact with these Geographic Libraries. We present a solution for this problem, based on a framework that allows the design and construction of customizable user interfaces for GDL applications. This framework relies on two main concepts: a Geographic User Interface Architecture and a Geographic Digital Library Model.

Resumo: Aplicações de vídeo apresentam grande demanda de banda passante, por isso sua disponibilização em larga escala requer a utilização de técnicas de redução desta demanda, p. ex. Batching e Piggybacking. Neste artigo, apresentamos um estudo sobre a técnica de Piggybacking, propomos duas extensões à política Algoritmo Snapshot e avaliamos o impacto destas extensões em um sistema de Vídeo sob Demanda.

Using B-trees in a two disk-single processor architecture to efficiently process inclusion spatial queries.

Abstract: In this paper we address the problem of indexing spatial data, in particular two dimensional rectangles. We propose an approach which uses two B-trees, each of them indexing the projected sides of the given rectangles. The approach, which we name 2dMAP21, can also be easily parallelized using two disks - but still a single processor - each holding the trees indexing the projected sides on either axes. We focus on queries of the type ``find all rectangles included within another (reference) rectangle''. Nevertheless, 2dMAP21 can processe other types of queries as well. We compare our approach to the R-tree, known as the most efficient R-tree derivative. Our investigation shows that, if the queries have the same spatial distribution of the data, the non-parallel 2dMAP21 may be a competitive alternative to the R-tree in some cases, whereas the parallelized version of 2dMAP21 outperforms that structure virtually always. 2dMAP21 may consume a little more or less storage space than the R-tree, depending primarily on the spatial distribution on the indexed MBRs. The use of B-trees renders our approach to be actually implementable using commercial DBMSs.

Abstract: In this paper we consider a labour constrained scheduling problem which is a simplification of a practical problem arising in the industry. Jobs are subject to precedence constraints and have specified processing times. Moreover, for each job the labour requirement varies as the job is processed. Given the amount of labour available in each period, the problem is to finish all the jobs as soon as possible (minimise makespan, subject to the precedence and labour constraints). Several Integer Programming (IP) formulations for this problem are discussed and valid inequalities for these different models are introduced. We point out to the major drawbacks in using the IP approach which are essentially due to the weakness of the lower bound relaxations. However, we report computational experiments showing how IP can be used to provide good feasible solutions and we indicate directions for further investigations which may turn IP techniques an interesting tool for solving such a problem.

Abstract: This paper studies the problem of register allocation and scheduling for Dual-Load-Execute (DLE) architectures. These are architectures which can execute an ALU instruction and two memory transfer operations ( load/store) in a single instruction cycle. DLE architectures are extensively used in the design of Digital Signal Processors (DSPs) like the Motorola 56000, Analog Devices ADSP-2100, and NEC PD77016. This work proves the existence of an efficient expression tree code generation algorithm for DLE architectures which have homogeneous register sets. The algorithm is an extension of the Sethi-Ullman algorithm, and produces guaranteed optimal code for a large number of expression trees in the program. The experimental results, using the NEC PD77016 as the target processor, show the efficacy of the approach.

Abstract: This work presents the implementation of a system for displaying three-dimensional animations based in the holographic stereogram technique. It uses chromatic codification for creation of the final image formed by diferent view points. The electronic animated images are pre-computed and stored in a movie file. They may be projected with white light to reach the size of the bigger holographic screens existing nowadays ( ).The final animation is presented at video rates and observed without visual accessories.

Abstract: We report the implementation of a system for displaying three-dimensional animations based on holoprojection. It is based in the holoprojection of two-dimensional slices (produced by a modified ray tracing program) of three-dimensional scenes. The final display is a truly spatial three-dimensional image with continuos horizontal parallax. It makes use of the holographic screen, a special diffractive lens, freeing the viewer from visual accessories.

Abstract: Video services is both a major business driver and a bandwidth consumer for the future broadband integrated network. Understanding different video services requirements is of paramount importance for network design. In this paper, we study Distributed Home Theatre (DHT), a video service which allows distributed users to debate a film. We compare different network designs for the provision of DHT services, and study the interplay between bandwidth reduction and program replication. We evaluate the impact of user distribution, and number of users per session on this interplay. Moreover, we analyze networks with both DHT and video on demand services.

Resumo: O problema da classificação consiste em decidir se um grafo pertence à Classe 1 ou à Classe 2. Uma condição suficiente para pertencer à Classe 2 é ser overfull (O), ou seja, o número de arestas de excede o produto do grau máximo de () por . Se possuir um subgrafo overfull com , dizemos que é subgrafo-overfull (SO). Se, ainda, for um subgrafo gerado pela vizinhança de um vértice de , dizemos que é vizinhança-overfull (NO). Se é O ou NO, é SO. Provamos para uma certa subclasse dos cografos que SO é equivalente a O ou a NO.

Resumo: Apresentamos descrições sucintas de 7 problemas de comparação de seqüências de caracteres, que podem ser resolvidos por programação dinâmica. Alguns desses problemas são particularmente importantes na área de biologia computacional. Com base nessas descrições apresentamos uma formulação geral que captura de maneira uniforme todas as formulações específicas, permitindo assim a implementação de um único programa que resolve todos os problemas. Essa implementação foi realizada e se encontra disponível através da WWW. Descrevemos também um algoritmo associado simples que permite contar o número de soluções ótimas de um dado problema; tal recurso é particularmente útil em aplicações de biologia computacional.

Abstract: We present succinct descriptions of 7 problems on character sequence comparison solvable by dynamic programming. Some of these problems are particularly important in computational biology. Based on these descriptions we present a general formulation for all 7 problems, allowing thus the implementation of a simple program that is able to solve each of those problems, depending on the user's choice. This implementation was written and the corresponding program is available through the WWW. We also describe a simple associated algorithm that efficiently counts all optimal solutions of a given problem. Such a feature is useful in computational biology applications.

Abstract: In this paper, we investigate the effectiveness of selective discard in a multiplexer subject to a long-range dependent process. We consider loss conserving disciplines, and we evaluate the impact of the input process traffic characteristics such as the Hurst parameter and variance into the per class loss rate and the loss gap. We found out that the Complete Sharing discipline is clearly worth adopting whereas Complete Sharing with Guaranteed Queue Minimum may be not. Furthermore, we show that the choice of push out policy may impact significantly the perceived QoS.

Abstract: Let be the complete undirected graph with weights associated to the edges in . We consider the problem of finding the subclique of such that the sum of the weights of the edges in is maximized and , for some . This problem is called the Maximum Edge-Weighted Clique Problem (MEWCP) and is NP-hard. In this paper we investigate the facial structure of the polytope associated to the MEWCP and introduce new classes of facets for this polytope. Computational experiments with a branch-and-cut algorithm are reported confirming the strength of these inequalities. All instances with up to 48 nodes could be solved without entering into the branching phase. Moreover, we show that some of these new inequalities also define facets of the Boolean Quadric Polytope and generalize previously known inequalities for this polytope.

Abstract: The Resource Constrained Project Scheduling Problem (RCPS) is a well known difficult combinatorial optimization problem. Many exact and heuristic approaches for this problem have been reported in the literature. Tabu search is a meta-heuristic designed to guide local search methods to escape the trap of local optimality. It has been lagerly used for solving combinatorial problems. In this report we propose a tabu search approach for Scheduling Problem under Labour Constraints (SPLC). Different neighbourhood strategies are discussed and then implemented. Computational experiments on a 25-instance SPLC data set are reported. The results obtained for benchmark instances are compared with those produced by a Constraint Logic Programming algorithm and show that our approach is at least as good as the best heuristics reported in the literature.

Abstract: We describe an animation system that simulates the dynamics of viscoelastic bodies subject to equality and inequality constraints. We show how Lagrange's method can be used to derive the equations of motion of such bodies from general formulas for the elastic and kinetic energy, the viscous power loss, and mechanical constraints, in terms of generalized coordinates.

We also describe a convenient two-parameter non-linear model for the elastic forces, that agrees with Hooke's law for small deformations, but does not allow the material to be compressed to zero or negative volume. In particular, we derive the equations of motion for elastic bodies modeled by tetrahedral finite elements with affine deformations. Finally, we show how collisions between such bodies can be efficiently and accurately detected by combining Hermite interpolation of the non-penetration constraints with Lin and Manocha's bounding box tests.

Abstract: This paper details an availability service in a service-oriented platform based on OMG/CORBA, for transparent migrating of services, i.e., components or agents. Migration of services is used to move components executing on a mobile host to another host, in case of shutdown or disconnection. A mobile host is treated as any other host going down or failing in an environment where the availability and functionality of the services and tasks wants to be sustained. Transparent location of a new destination host is simplified to the search and contracting of available resources from other hosts.

Bases para splines polinomiais não homogêneos na esfera.

Abstract: We investigate the use of non-homogeneous spherical polynomials for the approximation of functions defined on the sphere . A spherical polynomial is the restriction to of a polynomial in the three coordinates of . Let be the space of spherical polynomials with degree . We show that is the direct sum of and , where denotes the space of homogeneous degree- polynomials in .

We also generalize this result to splines defined on a geodesic triangulation of the sphere. Let denote the space of all functions from to such that (1) the restriction of to each triangle of belongs to ; and (2) the function has order- continuity across the edges of . Analogously, let denote the subspace of consisting of those functions that are within each triangle of . We show that . Combined with results of Alfeld, Neamtu and Schumaker on bases of this decomposition provides on effective characterization of the bases of .

There has been considerable interest recently in the use of the homogeneous spherical splines as approximations for functions defined on . We argue that the non-homogeneous splines would be a more natural choice for that purpose.

B-tree based approach to index transaction time.

Abstract: Transaction time of a record is the time interval when the record is stored in the database. In this paper we present an approach which provides efficient indexing of such kind of temporal data. The approach makes use of two standard B-trees with trivially modified node split policies--which yield a usage ratio of virtually 100% in each tree. We compare the proposed approach, which we name Two-Stage, to the Monotonic B-tree (by Elmasri et al). Our simulations show that the Two-Stage approach yields a structure up to 75% smaller than the Monotonic B-tree, and in all but one of the several investigated scenarios, the Two-Stage approach provided faster (or comparable) query processing time. Our main contribution, however, lies in the fact that the Two-Stage Approach does not require novel data structures but well-known B-trees. As such, and unlike all previous techniques for tackling this problem, it can be implemented using facilitites existing on most commercial DBMSs.

Abstract: We show that faster solutions to unconstrained global optimization problems can be obtained by combining previous accelerations techniques for interval branch-and-bound methods with affine arithmetic, a recent alternative to interval arithmetic that often provides tighter estimates. We support this claim by solving a few well-known optimization problems.

Resumo: Cm é uma linguagem baseada em C, com extensões para permitir programação modular e orientada a objetos, oferecendo funcionalidade equivalente a C++. A versão distribuída de Cm, denominada Cm Distribuído, busca estender a linguagem com mecanismos de programação concorrente e distribuída. Basicamente, pretende-se com ela definir um modelo de programação baseado em objetos distribuídos, que podem residir em diferentes pontos de uma rede, interagindo transparentemente através de chamadas de métodos. Aplicações distribuídas são construídas pela criação e configuração de objetos espalhados por uma rede, servindo como unidades de abstração e distribuição de recursos. Para a transferência de massas de dados para outros objetos, arquivos e periféricos, a linguagem oferece portas de dados, que podem ser tipadas com qualquer tipo complexo especificado na linguagem. Objetos podem ter referências para outros objetos que podem, como as portas de dados, ser configuradas externamente, aumentando sua flexibilidade. Servidores multitarefa podem ser implementados por classes com facilidades de multi-threading, onde cada chamada de método causa a criação de uma nova thread; o controle de concorrência é feito pelo mecanismo de regiões críticas condicionais estendidas.

Resumo: Apresenta a versão revisada da LegoShell, uma linguagem gráfica de programação e configuração de objetos distribuídos. Os elementos básicos são programas (objetos em Cm ou C++), periféricos e arquivos que podem ser interligados por meio de vários tipos de conectores. Cada programa, periférico e arquivo contém portas de acesso a dados. Uma computação (programa) LegoShell é um conjunto de elementos básicos interligados. Cada elemento é um objeto remoto e pode residir em uma máquina distinta numa rede TCP. Programas podem especificar que vão utilizar objetos remotos mas que serão somente determinados na sua configuração (i.e., na LegoShell ou outro programa responsável pela configuração). Um objeto usa um objeto remoto como se ele fosse local. Em essência, com a LegoShell é possível transformar um conjunto de programas comuns (objetos) num programa distribuído composto de objetos cooperantes. Em adição à capacidade de configuração de programas distribuídos, os programas em LegoShell podem ser transformados em programas em Cm Distribuído e programas em Cm Distribuído podem ser visualizados como programas em LegoShell. O programador pode editar um programa em qualquer das duas visões. Diferentemente das outras notações metodológicas, um programa LegoShell é também executável.

Resumo: Apresentamos um linearizador de estruturas complexas. Ele usa uma estratégia diferente da utilizada pelo XDR da Sun Microsystem e seu desempenho chega a ser cinco vezes mais rápido. Em adição, suporta estruturas circulares e referências a partes de estruturas. Mesmo quando o Linear é usado com o suporte a circularidade ligado, ele é, em geral, mais rápido que o XDR para a mesma estrutura sem circularidade.

Resumo: Programas não-triviais escritos na linguagem de programação C exigem o uso de diretivas de pré-processamento é uma espécie de ``linguagem dentro da linguagem''. O pré-processador C (cpp) é essencial para a abstração de código e especialmente para a programação modular. A linguagem Cm, derivada de C e com características para o suporte à orientação a objetos e distribuição, ainda não se utiliza do pré-processamento, em parte por suportar via construções próprias várias das funcionalidades providas por este recurso. Este documento discute aplicações e problemas do cpp, para então analisar como introduzir em Cm facilidades de pré-processamento ainda não suportadas, buscando ainda restringir ao mínimo possível suas desvantagens. Uma proposta preliminar é incluída.

Resumo: Apresentamos um modelo de concorrência a ser utilizado na linguagem de programação distribuída orientada a objetos Cm Distribuído, em desenvolvimento no Laboratório A-HAND. Objetos em Cm Distribuído podem apresentar concorrência possibilitando a execução de várias threads que compartilham dados internos do objeto. O mecanismo de controle de concorrência a ser utilizado baseia-se no modelo de Regiões Críticas Condicionais de Hoare (1978) e denomina-se Regiões Críticas Condicionais Estendidas (RCCE). O objetivo das extensões é dar maior poder à linguagem e mais flexibilidade ao programador.

Abstract: The traffic in the future Broadband Integrated Digital Networks will be highly correlated and neglecting its correlations leads to a dramatic underestimation of its performance. In order to completly specify a queueing network framework we need to define the stochastic processes resulting from the departure of a queue splitting and merging. In this paper we introduce a procedure for modeling the output process of a multiplexer with Markov modulated input and extend this procedure to model ATM multiplexers with selective discard mechanism. Moreover we show frameworks for queueing networks with Markov modulated flows which can be used to estimate end-to-end performance in ATM networks.

Abstract: This paper describes the design of GeoPrO: a distributed programming environment for geometric visualization. We present an overview of its classes that allow for easy extensibility and portability. Due to a client-server architecture, comprised of a kernel, with multiple contexts, applications and visualizers, GeoPrO supports distributed execution over a heterogeneous network. Visualizers are currently available for the planar and the spheric models of the oriented projective geometry, running on SGI workstations, while another is being implemented in Java for multi-platform support.