A Multiple-Criteria Approach to Ranking Computer Operating Systems

To select an operating system, an organization must consider several essential characteristics during its initial evaluation process. The analytic hierarchy process (AHP) offers an appropriate solution; the author illustrates it with a realistic case study in which an organization evaluates and ranks Windows XP, Linux, and Mac OS X 10.4.     

Labeling Schemes for Tree Representation

This paper deals with compact label-based representations for trees. Consider an n-node undirected connected graph G with a predefined numbering on the ports of each node. The all-ports tree labeling ℒ _all gives each node v of G a label containing the port numbers of all the tree edges incident to v. The upward tree labeling ℒ _up labels each node v by the number of the port leading from v to its parent in the tree. Our measure of interest is the worst case and total length of the labels used by the scheme, denoted M _up (T) and S _up (T) for ℒ _up and M _all (T) and S _all (T) for ℒ _all . The problem studied in this paper is the following: Given a graph G and a predefined port labeling for it, with the ports of each node v numbered by 0,…,deg (v)−1, select a rooted spanning tree for G minimizing (one of) these measures. We show that the problem is polynomial for M _up (T), S _up (T) and S _all (T) but NP-hard for M _all (T) (even for 3-regular planar graphs). We show that for every graph G and port labeling there exists a spanning tree T for which S _up (T)=O(nlog log n). We give a tight bound of O(n) in the cases of complete graphs with arbitrary labeling and arbitrary graphs with symmetric port labeling. We conclude by discussing some applications for our tree representation schemes. A preliminary version of this paper has appeared in the proceedings of the 7th International Workshop on Distributed Computing (IWDC), Kharagpur, India, December 27–30, 2005, as part of Cohen, R. et al.: Labeling schemes for tree representation. In: Proceedings of 7th International Workshop on Distributed Computing (IWDC), Lecture Notes of Computer Science, vol. 3741, pp. 13–24 (2005). R. Cohen supported by the Pacific Theaters Foundation. P. Fraigniaud and D. Ilcinkas supported by the project “PairAPair” of the ACI Masses de Données, the project “Fragile” of the ACI Sécurité et Informatique, and by the project “Grand Large” of INRIA. A. Korman supported in part by an Aly Kaufman fellowship. D. Peleg supported in part by a grant from the Israel Science Foundation.     

Velocity-Guided Tracking of Deformable Contours in Three Dimensional Space

This paper presents a 3D active contour model for boundary detection and tracking of non-rigid objects, which applies stereo vision and motion analysis to the class of energy-minimizing deformable contour models, known as snakes. The proposed contour evolves in three-dimensional space in reaction to a 3D potential function, which is derived by projecting the contour onto the 2D stereo images. The potential function is augmented by a kinetic term, which is related to the velocity field along the contour. This term is used to guide the inter-image contour displacement. The incorporation of inter-frame velocity estimates in the tracking algorithm is especially important for contours which evolve in 3D space, where the added freedom of motion can easily result in loss of tracking. The proposed scheme incorporates local velocity information seamlessly in the snake model, with little computational overhead, and does not require exogenous computation of the optical flow or related quantities in each image. The resulting algorithm is shown to provide good tracking performance with only one iteration per frame, which provides a considerable advantage for real time operation.     

A knowledge based system for the integrated design and manufacture of round broach tools

A complete knowledge based procedure for the design and manufacture of a round hole broach tool is described. The knowledge based design system (KBDS) produces a tool specification from user inputs describing the task to be performed. These design results are then used by the knowledge base to generate a geometric CAD/CAM representation, which can be utilized directly to display a drawing of the tool or to generate a CNC program for producing it. The process of formulating a knowledge-based design system demonstrates: the integration of expertise from experts, handbooks and theory; the awareness of restrictions on the scope of design that can be handled by a given system: the use of failure handling mechanisms to detect design failures and either adjust the emerging design or indicate infeasibility.     

Discrete-time complementary models and smoothing

The fact that the smoothing error is a (wide sense) Markov process is somehow surprising since smoothed estimates depend upon both past and future data. In this paper we first give a simple and general proof of this fact. Then we use the so-called complementary models introduced by Weinert and Desai to derive forwards and backwards markovian models for the smoothing error in state-space models. By exploring the structure of the complementary models we show that, under certain restrictions, only two simple structured models exist, one that runs forwards in time and the other that runs backwards in time. The forwards complementary model leads to the forward Rauch-Tung-Striebel (RTS) smoothing formula and to a backwards markovian model for the error, whereas the backwards model leads to the backward RTS formula and to a forwards error model. The two models for the smoothing error can be derived one from the other by a forward-backward transformation that preserves the sample paths. Finally, by using a combination of the two complementary models we give yet another proof for the two-filter smoothing formula.     

Crankback Prediction in Hierarchical ATM Networks

When an ATM node discovers that it cannot continue the setup of a virtual channel under the requested Quality of Service (QoS), it initiates a backtracking procedure called crankback. We propose a novel scheme, referred to as crankback prediction, that decreases the crankback overhead. Under the proposed scheme, nodes check during the connection admission control procedure whether the establishment of a virtual channel has a good chance to be admitted over the entire designated route. If this is not the case, crankback is initiated even before a particular QoS parameter is violated. The main idea behind the proposed scheme is to allocate a quota to the Peer Groups (PGs) along the message path, and then to suballocate this quota to the child PGs of these PGs. This process continues recursively until reaching the 1-level PG, which contains only physical nodes. The main advantage of the proposed scheme is that it lowers the setup delay and the processing and communication load imposed by signaling messages that establish unused portions of Virtual Channels (VCs)     

A rule-based pilot performance model

A new method of modelling task execution time and its relationship to resource utilization has been developed in this study in order to simulate accurately pilot performance in a single-seat fighter aircraft. By developing the model in a rule-based expert system program, it is suitable for incorporation in an intelligent decision support system to help manage pilot workload and improve total man-machine system performance. This model can also be employed in the design of new aircraft crewstations to analyse new man-machine system interfaces. Validation of the model was accomplished through comparison of critical predicted measures of merit against observed pilot performance in a manned flight simulator.     

Integration of reconfigurable inspection with stream of variations methodology

This paper describes an advanced closed loop quality control methodology for reconfigurable manufacturing systems. The methodology enables rapid root-cause diagnostics for faster ramp-up of reconfigurable systems through integration of the Reconfigurable Inspection Machine (RIM) and the Stream of Variations (SoV) methodology. The RIM enables reconfigurable, rapid, and accurate inspection using non-contact sensors while the SoV methodology is used to quickly analyze the measurements and identify the root-cause of the errors produced during machining.The feasibility of the industrial concept was experimentally validated. A machining error was introduced during machining of an engine head. Measurement information collected by the RIM was processed and used to locate the root-cause of the error using the SoV methodology.     

Real time discrete shading

A shading technique for voxel-based images, termedcongradient shading, is presented. As the surface information is not available in voxel representation, the surface normal must be recovered from the 3D discrete voxel map itself. The technique defines the normal as one of a finite set of neighborhood-estimated gradients and can thus employ precalculated look-up tables. Furthermore, a table-driven mechanism permits changing the light source parameters by merely redefining the look-up table. The technique uses only simple arithmetic operations and is thus suitable for hardware implementation. Since it has been implemented not as a post-processor, but as part of the projection pipeline of the cube architecture, congradient shading can be executed in real time. Two versions of the technique in real time. Two versions of the technique have been conceived and implemented:unidirectional shading, in which the gradient is estimated only from neighborhoods along the scan-lines;bidirectional shading, in which both horizontal and vertical components of the gradient are considered. In spite of the simplicity of the technique, the results are practically indistinguishable from images generated by conventional techniques.This work was supported by the National Science Foundation under grants DCR 8603603, CCR 8743478, CCR 8717016, and MIP 8805130