The problem of detecting straight lines arises frequently in image processing and computer vision. Here we consider the problem of extracting lines from range images and more generally from sets of three-dimensional (3D) points. The problem is stated as follows. Given a set Γ of points in 3D space and a non-negative constant , determine the line that is at a distance at most ε from the maximal number of points of . The extraction of multiple lines is achieved iteratively by performing this best line detection and removing at each iteration the points that are close to the line found. We consider two approaches to solve the problem. The first is a simple approach that selects the best line among a randomly chosen subset of lines each defined by a pair of edge points. The second approach, based on tabu search, explores a larger set of candidate lines thus obtaining a better fit of the lines to the points. We present experimental results on different types of three-dimensional data (i) range images of polyhedral objects (ii) secondary structures (helices and strands) of large molecules.

This paper presents a CAD technology mapping algorithm for LUT-based FPGAs. Since interconnections in an FPGA must be accomplished with limited routing resources, routability is the most important objective in a technology mapping algorithm. To optimize routability, the goal of the algorithm is the production of a design with a minimum interconnection. The Min-cut algorithm is first used to partition a graph representing a Boolean network into clusters so that the total number of interconnections between clusters is minimum. To decrease further the number of interconnections needed, clusters are then merged into larger clusters by a pairing technique. This algorithm has been tested on the MCNC benchmark circuits. Compared with other LUT-based FPGA mapping algorithms, the algorithm produces better routability characteristics.

This paper presents a new framework for synthesizing look-up table (LUT) networks. Some of the existing LUT network synthesis methods are based on one or two functional (Boolean) decompositions. Our method also uses functional decompositions, but we try to use various decomposition methods, which include algebraic decompositions. Therefore, this method can be thought of as a general framework for synthesizing LUT networks by integrating various decomposition methods. We use a cost database file which is a unique characteristic in our method. We also present comparisons between our method and some well-known LUT network synthesis methods, and evaluate the final results after placement and routing. Although our method is rather heuristic in nature, the experimental results are encouraging.

A multi-grid finite-difference time-domain (FDTD) method was applied for numerical dosimetry analysis in the human head for 5 GHz band portable terminals. By applying fine FDTD grids to the volumes in the human head where the highest electromagnetic (EM) absorption occurs and coarse grids to the remaining volumes of the head, the spatial peak specific absorption rate (SAR) assessment was achieved with a less computation memory and time. The accuracy of applying the multi-grid FDTD method to the spatial peak SAR assessment was checked in comparison with the results obtained from the usual uniform-grid method, and then the spatial peak SARs for three typical situations of a person using a 5.2 GHz band portable terminal were calculated in conjunction with an anatomically based human head model.

Decentralized XML databases are often used in Electronic Commerce (EC) business models such as e-brokers on the Web. To flexibly model such applications, we need a modeling language for EC business processes. To this end, we have adopted a query language approach and have designed a query language, called XBML, for decentralized XML databases used in EC businesses. In this paper, we explain and validate the functionality of XBML by specifying e-broker business models and describe the implementation of the XBML server, focusing on the distributed query processing.

In the theory of average-case NP-completeness, Levin introduced the polynomial domination and Gurevich did the average polynomial domination. Ben-David et al. proved that if P-samp (the class of polynomial-time samplable distributions) is polynomially dominated by P-comp (the class of polynomial-time computable distributions) then there exists no strong one-way function. This result will be strengthened by relaxing the assumption from the polynomial domination to the average polynomial domination. Our results also include incompleteness for average polynomial-time one-one reducibility from (NP,P-samp) to (NP,P-comp). To derive these and other related results, a prefix-search algorithm presented by Ben-David et al. will be modified to survive the average polynomial domination.

Stability of slotted ALOHA systems with retransmission cutoff, in which a packet is discarded after the certain number of unsuccessful transmissions, is investigated on slow-frequency-hopped channels with the aid of the catastrophe theory. The result of this paper can be viewed as extension of the result derived by Kim. The balance function is first formulated. Then, the cusp point and the bifurcation sets are numerically evaluated. We visualize how retransmission cutoff effects on bistable region. Using the result, we can design parameters of slotted ALOHA systems with retransmission cutoff such that the system operates with the unique stable equilibrium point.

Over recent years, "Internet-able" applications and architectures have been used to support domains where there are multiple interconnected systems that are both decentralized and autonomous. In enterprise-level data management domains, both the schema of the data repository and the individual query needs of the users evolve over time. To handle this evolution, the resulting architecture must enforce the autonomy in systems that support the client needs and constraints, in addition to maintaining the autonomy in systems that support the actual data schema and extraction mechanisms. At the MITRE Corporation, this domain has been identified in the development of a composite data repository for the Center for Advanced Aviation System Development (CAASD). In the development of such a repository, the supporting architecture includes specialized mechanisms to disseminate the data to a diverse evolving set of researchers. This paper presents the motivation and design of such an architecture to support these autonomous data extraction environments. This run-time configurable architecture is implemented using web-based technologies such as the Extensible Markup Language (XML), Java Servlets, Extensible Stylesheets (XSL), and a relational database management system (RDBMS).

Focusing on a distributed control service-control-node (SCP) that houses a database (DB) distributed across multiple modules, this paper proposes an autonomous distributed SCP architecture using multicasting access to the distributed DB, and highlights its application areas. We assume as a basic condition that neither the network nor the other modules in the system are aware of the DB configuration. Based on this condition, we propose two basic methods: a unicast approach in which the DB management module that is selected at random by the network routes the DB access request to the module where the target data resides (Method A), and a multicast method in which DB access requests are broadcast to all modules (Method B). A quantitative evaluation is made of the number of required modules and required communications performance between modules which is determined by the capacity of the main memory and processing capacity of the processors. Based on the results, we conclude that Method B better exploits the advantages of module autonomous distribution technology within the limits that the economy of inter-module communication overhead is not impaired. Furthermore, in the event a module fails in Method B, a scheme is proposed in which the defective module is cut out of the multicast group, and multicasting continues. This could be implemented most effectively using a separate route under hardware control that is independent of the on-line communications route between modules.

An improved arithmetic coding which provides an encoder with finite calculation precision for source sequences over a countable alphabet is presented. Conventional arithmetic coding theoretically has infinite precision for real variables. However any algorithm implemented on a computer has finite precision. This implies that conventional arithmetic codes can only encode sequences over a finite alphabet. The improved arithmetic coding presented here has a computational complexity which is roughly proportional to the length of the source sequence for a given source.

In this paper, an effective index structure for dynamic main memory database systems, which we call the T2-tree, is presented. A notion of a thread pointer is introduced to overcome some of the limitations of the T-tree and the T*-tree. There are several advantages to this structure. First, the T2-tree reduces the number of rotate operations and the overhead required for balancing the tree by restraining new node creation and deletion. Second, the T2-tree shows good performance for sequential search of range queries as these requests can be effectively handled using the successor pointer. Finally, the T2-tree allows for higher space utilization amplicating the aforementioned benefits. These advantages are obtained with minimal changes to the existing T-tree structure. Experimental studies showing evidence of the benefits of the T2-tree are also presented.

Particulate media composed of very small particles were studied to determine high-density recording performance and thermal stability. Studied media included metal particulate media with mean particle length of 71, 102 and 148 nm, and Ba ferrite particulate media with mean diameter of 22, 28 and 50 nm. Using a loss-term simulation program, taking into account gap-loss, spacing-loss and particle length loss, the recording capability (D20 of 265 kFRPI for MP and 290 kFRPI for Ba ferrite media) was estimated. Thermal stability was evaluated from magnetization time decay measurements. It was found that MP media with large Ku values and 71 nm particles were satisfactorily stable, and the particle volume is still large enough in respect of thermal stability. However, 22-nm Ba ferrite media were less stable, primarily because of small Ku values and particle volume. It was also clarified that positive inter-particle interaction accelerates magnetization time decay, in the presence of a large reverse field.

In order to enhance the performance, many database management systems (DBMSs) execute transactions at isolation level 2 rather than at isolation level 3, the strict two phase locking, even if it sacrifices consistency to a certain degree. Cursor stability, a variant of isolation level 2 in relational DBMSs (RDBMSs), has been widely used as a useful technique for obtaining concurrency achievable at level 2 without much sacrificing consistency. However, cursor stability is much less usable in object-relational DBMSs (ORDBMSs) because navigational applications in ORDBMSs can suffer from critical inconsistency problems such as dangling pointers, lost updates, and reading inconsistent complex objects. In this paper, we propose a new isolation level, navigation stability, that prevents the inconsistency problems of cursor stability for navigational applications, while avoiding significant degradation of the concurrency of level 3. First, we analyze the inconsistency problems of cursor stability for navigational applications. Second, we define navigation stability as an extension of cursor stability and show that it solves those inconsistency problems of cursor stability in ORDBMSs. Third, through extensive simulation, we show that navigation stability significantly enhances the performance compared with level 3. For workloads consisting of transactions of long duration, compared with level 3, the throughput of navigation stability is enhanced by up to 200%; the average response time reduced by as much as 55%; and the abort ratio reduced by as much as 77%. From these results, we conclude that navigation stability is a useful isolation level in ORDBMSs that can be used in place of isolation level 3 to improve the performance and concurrency without significant sacrifice of consistency.

This paper is concerned with the controller synthesis for feedback systems with saturation based on the LPV system representation. The LPV system representation, combined with use of the detailed structure of saturation nonlinearity, enables us to reduce the conservativeness. In this paper, we develop a new iterative algorithm for designing a linear time-invariant controller which locally stabilizes the nonlinear closed-loop system and achieves the prescribed quadratic control performance. The present design method provides an explicit expression for a guaranteed domain of attraction, and maximizes the estimated region of the plant states for which the stability and the prescribed quadratic performance are satisfied. A numerical example shows the effectiveness of the present design method.

This short paper is a written version of one part of the plenary address given at the November 1999 NOLTA symposium held at the Hilton Waikoloa Village in Hawaii. I was invited by Professor Shin'ichi Oishi, a general vice-chairman of the symposium, to give a survey of some of my own research. I was happy to do that--in the context of a description of what Bell Labs.' research environment was like in its math center in the 1960's, and why I feel that today's young researchers are often too constrained in that they are typically not encouraged to try to do really interesting work. Here the emphasis is on only the origins of input-output stability theory.

The Active HYpermedia Delivery System (AHYDS) facilitates the access to multimedia information over a large-scale network and wide spectrum of media. We developed intelligent access facilities that build on the access paradigms supported by current web applications. This facility generalizes not only different kinds of logical data models (relational, object, hyperlink), but also access mechanisms of multimedia applications to make them customizable and scalable. This paper proposed the distributed management mechanism of the AHYDS platform. The major contribution of this paper is the mechanism for distributed multimedia delivery management over large-scale network and heterogeneous environment. We also propose the mechanism to manage huge multimedia data.

A model of interactive videoconference is proposed for investigating the interactivity of the videoconference. Through running a prototype videoconferencing system over ATM networks, we observed that the system stability would degrade abruptly if the interaction demand from conferees exceeds what the system control can support. By using the proposed model, we formulate the problem of achieving high interactivity and stability as maximizing interactivity by tuning system parameters subject to some stability constraints. Solving the problem is non-trivial since it involves unpredictable network delays. We thus develop practical approaches that can choose and dynamically adjust, according to the network condition, the values of system parameters to meet the stability constraints and improve the interactivity. Finally, we validate our approaches and provide guidelines on choosing the parameter values by conducting experiments and simulations.

In distributed network systems, it is one of the most important problems how to assign the files to servers in view of cost and delay. It is obvious that there is a trading-off relationship between costs and delays in these systems. In order to evaluate the optimization that the total cost is minimized subject to the total delay, we have presented the Optimal File Allocation Model as 0-1 integer programming, and have investigated the general characteristics in distributed systems. In this model, we have introduced many cost and delay parameters to evaluate the total cost and delay in the system more exactly. In constructing practical systems, it is necessary to investigate the weight and the contribution of each parameter to the total cost. It is very useful to show how to estimate cost and delay parameters on the basis of this analysis. In this paper, we analyze the sensitivity of these parameters and make clear the influence between principal parameters.

A new IDDQ testable design method is proposed for static CMOS PLA circuits. A testable PLA circuit of NOR-NOR type is designed using this method. It is shown that all bridging faults in NOR planes of the testable designed PLA circuit can be detected by IDDQ testing with 4 sets of test input vectors. The test input vectors are independent of the logical functions to be realized in the PLA circuit. PLA circuits are designed using this method so that the quiescent supply current generated when they are tested will be zero. Thus, high resolution of IDDQ tests for the PLA circuits can be obtained by using the testable design method. Results of IDDQ tests of PLA circuits designed using this testable design method confirm not that the expected output can be generated from the circuits but that the circuits are fabricated without bridging faults in NOR planes. Since bridging faults often occur in state-of-the-art IC fabrication, the testable design is indispensable for realizing highly reliable logic systems.

The chemical stability of the constituent elements in polycrystalline Sr-Bi-Ta-O thin film with various Bi content prepared by metalorganic chemical vapor deposition (MOCVD) was investigated by X-ray photoelectron spectroscopy (XPS). Moreover, that of the epitaxial films was also investigated to estimate the effect of the grain boundary in polycrystalline films. Therefore, only the Bi element drastically changed from Bi3+ state to Bi0 one by the Ar sputtering. This change increased with increasing the Ta/Bi mole ratio in the film from 0.64 to 1.67. This result was observed not only for the polycrystalline films but also for the epitaxial films, suggesting that this is the grain character not grain boundary one. The stability and the leakage character of the film strongly depend on the constituent of the film.