Ordered Boolean List (OBL): reducing the footprint for evaluating Boolean expressions

An Expanded Boolean Expression (EBE) does not contain any XOR or EQUAL operators. The occurrence of each variable is a different literal. We provide a linear time algorithm that converts an EBE of n literals into a logically equivalent Ordered Boolean List (OBL) and show how to use the OBL to evaluate the EBE in n steps and O(log log n) space, if the values of the literals are each read once in the order prescribed by the OBL. (An evaluation workspace of 5 bits suffices for all EBEs of up to six billion literals.) The primary application is the SIMD architecture, where the same EBE is evaluated in parallel for different input vectors when rendering solid models on the GPU directly from their Constructive Solid Geometry (CSG) representation. We compare OBL to the Reduced Ordered Binary Decision Diagram (ROBDD) and suggest possible applications of OBL to logic verification and to circuit design.     

Preventing risky driving: A novel and efficient brief intervention focusing on acknowledgement of personal risk factors

Impulsive personality is an important predictor of risky driving. Acknowledging their impulsive tendencies may help novice drivers to drive more safely. The aim of this study was to evaluate the efficacy of a novel brief intervention targeting novice drivers’ risky behavior in traffic, taking into account potential moderator effects. Driving school students (n = 1866) were divided into an intervention group and a control group. The intervention consisted of a lecture and group work (1.5 h). Subjects’ traffic offenses and crashes were monitored during the following year using police and traffic insurance fund databases. The groups were similar in their baseline characteristics. The intervention group had half as many speeding violations in the year following the intervention compared with the controls. The proportion of speeders was significantly lower in the intervention group compared with the control group in subgroups of subjects with medium cognitive abilities and low or medium BIS-11 impulsiveness levels. In alpha_2A-adrenoceptor gene (ADRA2A) G allele carriers, general traffic risk and speeding decreased in response to the intervention, unlike in subjects with the CC genotype. It is concluded that brief interventions that are integrated into the driving education program and focus on personal psychological risk factors may be effective for improving traffic safety.     

Hoops: 3D Curves as Conservative Occluders for Cell-Visibility

Most visibility culling algorithms require convexity of occluders. Occluder synthesis algorithms attempt to construct large convex occluders inside bulky non-convex sets. Occluder fusion algorithms generate convex occluders that are contained in the umbra cast by a group of objects given an area light. In this paper we prove that convexity requirements can be shifted from the occluders to their umbra with no loss of efficiency, and use this property to show how some special non-planar, non-convex closed polylines that we call hoops can be used to compute occlusion efficiently for objects that have no large interior convex sets and were thus rejected by previous approaches.     

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.     

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.     

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.