Holes in joins

A join of two relations in real databases is usually much smaller than their Cartesian product. This means that most of the combinations of tuples in the crossproduct of the respective relations do not appear together in the join result. We characterize these combinations as ranges of attributes that do not appear together. We sketch an algorithm for finding such combinations and present experimental results from real data sets. We then explore two potential applications of this knowledge in query processing. In the first application, we model empty joins as materialized views, we show how they can be used for query optimization. In the second application, we propose a strategy that uses information about empty joins for an improved join selectivity estimation.     

Layout transformation support for the disk resident arrays framework

The Global Arrays (GA) toolkit provides a shared-memory programming model in which data locality is explicitly managed by the programmer. It inter-operates with MPI and supports a variety of language bindings. The Disk Resident Arrays (DRA) model extends the GA programming model to secondary storage. GA and DRA together provide a convenient programming model that encourages locality-aware programming by the user, while presenting a high-level abstraction. High performance depends on the appropriate distribution of the data in the disk-resident arrays. In this paper, we discuss the addition of layout transformation support to DRA. The implementation of an efficient parallel layout transformation algorithm is done on top of existing GA/DRA functions; thus GA/DRA is itself used in implementing the enhanced DRA functionality. Experimental performance data is provided that demonstrates the effectiveness of the new layout transformation functionality. This work was supported in part through funding from the U.S. Department of Energy and the National Science Foundation (award 0121676).     

OCTOR: Subset selection in recursive pattern hierarchies

We present an approach for encoding and specifying selections in recursive pattern hierarchies. Hierarchies of patterns of features or other modeling entities are used in architectural and mechanical CAD to eliminate laborious repetitions from the design process. Yet, often a subset of the repeated occurrences in the model must be edited. Specifying a desired selection is often tedious and difficult. Our approach addresses these two drawbacks simultaneously, offering an effective and intuitive solution which requires only two mouse-clicks to specify any one of a wide range of selections, including selections in recursive hierarchies. The selection has a concise representation that is simple to compute.     

Blowing Bubbles for Multi-Scale Analysis and Decomposition of Triangle Meshes

Tools for the automatic decomposition of a surface into shape features will facilitate the editing, matching, texturing, morphing, compression and simplification of three-dimensional shapes. Different features, such as flats, limbs, tips, pits and various blending shapes that transition between them, may be characterized in terms of local curvature and other differential properties of the surface or in terms of a global skeletal organization of the volume it encloses. Unfortunately, both solutions are extremely sensitive to small perturbations in surface smoothness and to quantization effects when they operate on triangulated surfaces. Thus, we propose a multi-resolution approach, which not only estimates the curvature of a vertex over neighborhoods of variable size, but also takes into account the topology of the surface in that neighborhood. Our approach is based on blowing a spherical bubble at each vertex and studying how the intersection of that bubble with the surface evolves. We describe an efficient approach for computing these characteristics for a sampled set of bubble radii and for using them to identify features, based on easily formulated filters, that may capture the needs of a particular application.     

Cost optimal and nearly zero (nZEB) energy performance calculations for residential buildings with REHVA definition for nZEB national implementation

This study determined cost optimal and nearly zero energy building (nZEB) energy performance levels following the REHVA definition and energy calculation methodology for nZEB national implementation. Cost optimal performance levels – meaning the energy performance leading to minimum life cycle cost – were calculated with net present value method according to the cost optimal draft regulation. The seven-step procedure was developed to conduct cost optimal and nZEB energy performance levels calculations in systematic and robust scientific fashion. It was shown that cost optimal primary energy use can be calculated with limited number of energy simulations as only four construction concepts were simulated and cost calculated. The procedure includes the specification of building envelope components based on specific heat loss coefficient and systems calculation with post processing of energy simulation results, without the need to use iterative approach or optimization algorithm. Model calculations were conducted for Estonian reference detached house to analyse the difference between the cost optimal and nZEB energy performance levels. Cost optimal energy performance level of Estonian reference detached house was 110 kW h/(m² a) primary energy including all energy use with domestic appliances and it was significantly lower than the current minimum requirement of 180 kW h/(m² a).     

A semantic grid infrastructure enabling integrated access and analysis of multilevel biomedical data in support of postgenomic clinical trials on cancer.

This paper reports on original results of the Advancing Clinico-Genomic Trials on Cancer integrated project focusing on the design and development of a European biomedical grid infrastructure in support of multicentric, postgenomic clinical trials (CTs) on cancer. Postgenomic CTs use multilevel clinical and genomic data and advanced computational analysis and visualization tools to test hypothesis in trying to identify the molecular reasons for a disease and the stratification of patients in terms of treatment. This paper provides a presentation of the needs of users involved in postgenomic CTs, and presents such needs in the form of scenarios, which drive the requirements engineering phase of the project. Subsequently, the initial architecture specified by the project is presented, and its services are classified and discussed. A key set of such services are those used for wrapping heterogeneous clinical trial management systems and other public biological databases. Also, the main technological challenge, i.e. the design and development of semantically rich grid services is discussed. In achieving such an objective, extensive use of ontologies and metadata are required. The Master Ontology on Cancer, developed by the project, is presented, and our approach to develop the required metadata registries, which provide semantically rich information about available data and computational services, is provided. Finally, a short discussion of the work lying ahead is included.     

Constructive non-regularized geometry

Solid modelling is concerned with the construction and manipulation of unambiguous computer representations of solid objects. These representations permit us to distinguish the interior, the boundary and the complement of a solid. They are conveniently specified in Constructive Solid Geometry (CSG) by a construction tree that has solid primitives as leaves and rigid body motions or regularized Boolean operations as internal nodes. Algoriths for classifying sets with respect to CSG trees and for evaluating the boundaries of the corresponding solids are known, at least for simple geometric domains. Emerging CAD applications require that we extend the domain of solid modellers to support more general and more structured geometric objects. The focus is on dimensionally non-homogeneous, non-closed pointsets with internal structures. These entities are well suited for dealing with mixed-dimensional (‘non-manifold’) objects in ⁿ that have dangling or missing boundary elements, and that may be composed of several regions. A boundary representation for such objects has been described elsewhere. We propose to specify and represent inhomogeneous objects in terms of Constructive Non-Regularized Geometry (CNRG) trees that extend the domain of CSG by supporting non-regularized primitive shapes as leaves, and by providing more general set-theoretic and topological operators at interior nodes. Filtering operations are also provided that construct CNRG objects from aggregates of selected regions of other CNRG objects. A syntax and semantics of the operators in CNRG are presented, and some basic algorithms for classifying pointsets with respect to the regions of objects represented by CNRG trees are outlined.     

Shared Memory Programming in Metacomputing Environments: The Global Array Approach

The performance of the Global Array shared-memory nonuniform memory-access programming model is explored in a wide-area-network (WAN) distributed supercomputer environment. The Global Array model is extended by introducing a concept of mirrored arrays that thanks to the caching and user-controlled consistency of the shared data structure scan reduce the application sensitivity to the network latency. Latencies and bandwidths for remote memory access are studied, and the performance of a large application from computational chemistry is evaluated using both fully distributed and also mirrored arrays. Excellent performance can be obtained with mirroring if even modest (0.5 MB/s) network bandwidth is available.     

Finally Everyone Can Work With Highly Complex 3D Models

In the past, access to 3D databases was restricted to few specialists having the appropriate CAD skills, software, and graphics hardware. The availability of inexpensive graphics support on personal computers, the Internet’s impact on private and commercial communication, and the emergence of multimedia standards provide the basis for linking CAD databases with other personal productivity and communication tools and for making them accessible to everyone at home, in schools, in hospitals, or in the industry. For example, employees that have no design expertise, customers, and suppliers would benefit from having an easy access to the 3D databases of a company for: collaborative design review, 3D-based multi-media problem reports, collaborative problem solving and tracking, online training and documentation, internet-based part purchasing and subcontracting, demonstration to customers, or advertising. This presentation will address three of the key issues that have so far limited the non-specialist’s access to 3D databases. First-time or occasional non-expert users need to become instant experts in 3D navigation through Virtual Environments or in the interactive manipulation of digital 3D models, so that they may immediately focus on their tasks, and not waste precious time learning and fighting an unnatural user interface. Immersive VR is not the panacea – other more effective techniques show promise. The data complexity found in commercial CAD databases, especially in the automotive, aerospace, and construction industries, significantly exceeds the capabilities of any interactive graphics system. This situation is not likely to change, since the growth of the complexity and availability of 3D models outpaces the performance improvement of personal computers. Research on the automatic simplification of 3D models and on the use of levels of detail to accelerate the rendering of distant portions of the scene is growing rapidly. The still limited bandwidth of internet communication channels prohibits a pervasive access to large amounts of 3D data. Recent 3D compression techniques reduce the storage requirements for polyhedral 3D models by two orders of magnitudes.