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 decrease 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.
Summary: Video applications have a high demand for bandwidth, so their availability on a large scale requires the use of techniques to reduce this demand, p. ex. Batching and Piggybacking. In this article, we present a study on the Piggybacking technique, we propose two extensions to the Algorithm Snapshot policy and evaluate the impact of these extensions on a Video on Demand system.
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 ''. However, 2dMAP21 can process 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 consumes 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 labor 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 labor requirement varies as the job is processed. Given the amount of labor available in each period, the problem is to finish all the jobs as soon as possible (minimize makespan, subject to the precedence and labor 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 perform 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 on 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 on 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 Theater (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.
Summary: The classification problem is to decide whether a graph
belongs to Class 1 or to Class 2. A sufficient condition for
belong to Class 2 é
to be overfull (O), that is, the number of
exceeds the product of the maximum degree of
(
) By
. It
own a subgraph overfull
com
, we say that
é subgraph-overfull (SO). If still,
is a subgraph generated by the neighborhood of a vertex of
, we say that
é neighborhood-overfull (DO NOT). If
é O ou DO NOT,
é SO. We proved for a certain subclass of the cographs that SO it's equivalent to O or DO NOT.
Summary: We present brief descriptions of 7 string comparison problems, which can be solved by dynamic programming. Some of these problems are particularly important in the field of computational biology. Based on these descriptions, we present a general formulation that uniformly captures all specific formulations, thus allowing the implementation of a single program that solves all problems. This implementation was carried out and is available through the WWW. We also describe a simple associated algorithm that allows counting the number of optimal solutions for a given problem; such a feature is particularly useful in computational biology applications.
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 Click 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 taboo search approach for Scheduling Problem under Labor Constraints (SPLC). Different neighborhood 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, ie, 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.
Abstract: We investigate the use of non-homogeneous spherical polynomials for the approximation of functions defined on the sphere
. polynomial spherical 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
indicates 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
consisted 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.
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.
Summary: Cm is a C-based language, with extensions to allow modular and object-oriented programming, offering functionality equivalent to C ++. The distributed version of Cm, called Cm Distributed, seeks to extend the language with concurrent and distributed programming mechanisms. Basically, it is intended to define a programming model based on distributed objects, which can reside in different points of a network, interacting transparently through method calls. Distributed applications are built by creating and configuring objects spread over a network, serving as units of abstraction and distribution of resources. For the transfer of masses of data to other objects, files and peripherals, the language offers data ports, which can be typed with any complex type specified in the language. Objects can have references to other objects that can, like data ports, be configured externally, increasing their flexibility. Multitasking servers can be implemented by classes with multi-threading facilities, where each method call causes the creation of a new thread; concurrency control is done by the extended conditional critical regions mechanism.
Summary: Features the revised version of LegoShell, a graphical language for programming and configuring distributed objects. The basic elements are programs (objects in Cm or C ++), peripherals and files that can be connected through various types of connectors. Each program, peripheral and file contains data access ports. A LegoShell computation (program) is a set of interconnected basic elements. Each element is a remote object and can reside on a separate machine on a TCP network. Programs can specify that they will use remote objects but that will only be determined in their configuration (ie, in LegoShell or another program responsible for the configuration). An object uses a remote object as if it were local. In essence, with LegoShell it is possible to transform a set of common programs (objects) into a distributed program composed of cooperating objects. In addition to the ability to configure distributed programs, LegoShell programs can be turned into Distributed Cm programs and Distributed Cm programs can be viewed as LegoShell programs. The programmer can edit a program in either view. Unlike other methodological notations, a LegoShell program is also executable.
Summary: We present a linearizer of complex structures. It uses a different strategy than the one used by Sun Microsystem's XDR and its performance is up to five times faster. In addition, it supports circular structures and references to parts of structures. Even when Linear is used with circularity support turned on, it is, in general, faster than XDR for the same structure without circularity.
Summary: Non-trivial programs written in the C programming language require the use of pre-processing directives is a kind of `` language within language ''. The C preprocessor (cpp) is essential for code abstraction and especially for modular programming. The Cm language, derived from C and with features to support object orientation and distribution, still does not use pre-processing, in part because it supports several of the features provided by this resource via its own constructions. This document discusses cpp applications and problems, and then analyzes how to introduce pre-processing facilities in Cm that are not yet supported, while also trying to restrict their disadvantages to a minimum. A preliminary proposal is included.
Summary: We present a competition model to be used in distributed programming language oriented to Cm Distributed objects, under development at the A-HAND Laboratory. Objects in Distributed Cm can have concurrency allowing the execution of several threads that share the object's internal data. The concurrency control mechanism to be used is based on Hoare's Conditional Critical Regions (1978) model and is called Extended Conditional Critical Regions (RCCE). The purpose of the extensions is to give more power to the language and more flexibility to the programmer.
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 queuing 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.
Instituto de Computação :: State University of Campinas
PO Box 6176 • Av. Albert Einstein, 1251 - Cidade Universitária • CEP 13083-970 • Campinas / SP - Brazil • Phone: [19] 3521-5838 |