bluuebunny/crossref_metadata_2025 huggingface dataset:
A NEURAL NETWORK MODEL TO INDEX MEDICAL IMAGES
Authors: CRÉPUT JEAN-CHARLES , CARON ARMAND
Published: July 2002

With the development of computer capabilities, memories and network abilities, we need more efficient and robust algorithms to manage databases and to store and retrieve the relevant information for the user. The aim of this work is to automate the construction of a neural network Information Retrieval System (IRS) adapted to a medical image database. The user builds queries and the system must retrieve the relevant documents or images. Queries are groups of keywords or items associated with relevant images. In our approach, the set of queries and the binary relevance judgments on the documents constitute complex learning data associations.

There are two phases in the automatic construction of the IRS. The indexing phase builds the learning data base and then a specific learning algorithm builds the neural network. For the system to be able to immediately learn these complex data, we have developed a new specific algorithm. It allows a perfect learning of a binary logical table in a stepwise fashion without forgetting the previously learnt logical combinations. Furthermore, this algorithm works very quickly and leads to a parallel implementation for large databases.
THEORETICAL STUDY OF CO ADSORPTION ON Ni(111), Pt(111) AND Pt/Ni(111) SURFACES
Authors: CABEZA G. F. , CASTELLANI N. J. , LÉGARÉ P.
Published: July 2002

CO adsorption on a pseudomorphic Pt overlayer supported by Ni (111) has been studied with the use of extended Huckel calculations. Experimental information on the pure Pt (111) and Ni (111) single crystals was employed to select a consistent parameter set for our bimetallic system. This gives a good description of the chemisorption bond changes between the various systems considered in our study. The CO chemisorption energy on Pt/Ni (111) was found to be lowered in comparison with Pt (111) and Ni (111), in good agreement with experimental data on Pt-rich Pt–Ni surface alloys. This observation could be justified by the electronic changes of the Pt states (valence band broadening and decreasing density at the Fermi level). Indeed, they induce, in comparison with the pure substrates, a repulsion between Pt and CO although the 2π* population of the chemisorbed molecule increases. This points to the necessity of going beyond arguments based on an analysis of the 5σ donation and 2π* backdonation for a complete description of the chemisorption bond.
INFLUENCE OF STEPS ON ATOMIC ADSORPTION AND SEQUENTIAL GROWTH ABOVE VICINAL SURFACES
Authors: PICAUD F. , POUTHIER V. , RAMSEYER C. , GIRARDET C.
Published: July 2002

Two different situations corresponding to out-of-equilibrium growth of an adsorbate and to equilibrium adsorption of a gas are discussed using the vicinal face of a transition metal as the substrate. Monte-Carlo simulations in the kinetic and equilibrium regimes are applied to the ordering of Xe and Ag atoms close to the monatomic steps of the (997) vicinal face of platinum. It is shown that the steps can favor the growth of one or two rows of adatoms (row-by-row growth) in the submonolayer domain, depending on the temperature and on intrinsic parameters connected to the magnitude of the interactions between the adspecies themselves and between these adspecies and the substrate. Such a behavior is consistent with very recent helium atom scattering experiments.
ATOMIC STRUCTURES OF A Cu(111) SURFACE UNDER ELECTROCHEMICAL CONDITIONS: AN IN-SITU STM STUDY
Authors: BROEKMANN P. , WILMS M. , WANDELT K.
Published: July 2002

The atomic structures of a Cu(111) electrode in dilute sulfuric electrolyte have been studied using in-situ STM. At anodic potentials near the copper dissolution the adsorbed sulfate anions form a characteristic anisotropic Moiré pattern. The appearance of the long range Moiré modulation is explained by a sulfate-induced reconstruction (expansion) of the topmost copper layer and the resulting misfit between the first and the second copper layer. For the first time it was possible to image not only the sulfate adsorbate but also the underlying reconstructed copper substrate at the same anodic working potential by a systematical variation of the tunneling parameters. On an atomic scale the observed sulfate structure on Cu(111) is very similar to those found for other fcc(111) surfaces (Au, Pt and Rh). On these electrodes sulfate anions form a regular [Formula: see text] superstructure. For the Cu(111) surface a [Formula: see text]-like unit cell is found which is slightly distorted.

Also for the first time it was possible to image the atomic structure of an electrode during a massive hydrogen evolution current at cathodic potentials. Even under such extreme electrochemical conditions far from the thermodynamic equilibrium an ordered superstructure of hydronium cations is found. At the anodic end of the cyclic voltammogram a pit-etching mechanism is induced by a fast copper corrosion.
HEDGING STRATEGY WITH LANGEVIN EVOLUTION
Authors: MARIANI S. , ROTUNDO G. , TIROZZI B.
Published: July 2002

In recent years there has been much attention paid to pricing and hedging models that are more general than the Black and Scholes' one, whose hypotheses often aren't satisfied by true market data. Sato and Takayasu proposed a market model that can produce price fluctuations with infinite variance from a deterministic behaviour of many market's dealers as it emerged from their simulations. We check the possibility to apply this model to an Italian stock, the "Assicurazioni Generali" and determine the density function of the multiplicative and additive noise appearing in the proposed Langevin equation.

We find also the Lévy distribution for the changes. This distribution is consistent with the histograms and the Kernel estimates. These results are used for hedging following the approach of Sornette and Bouchaud.
LOGNORMAL-MIXTURE DYNAMICS AND CALIBRATION TO MARKET VOLATILITY SMILES
Authors: BRIGO DAMIANO , MERCURIO FABIO
Published: July 2002

We introduce a general class of analytically tractable models for the dynamics of an asset price based on the assumption that the asset-price density is given by the mixture of known basic densities. We consider the lognormal-mixture model as a fundamental example, deriving explicit dynamics, closed form formulas for option prices and analytical approximations for the implied volatility function. We then introduce the asset-price model that is obtained by shifting the previous lognormal-mixture dynamics and investigate its analytical tractability. We finally consider a specific example of calibration to real market option data.
A REVIEW OF THE INSTABILITY PROBLEM FOR FRAME STRUCTURES
Authors: XUE QIANG , MEEK JOHN L.
Published: July 2002

This paper presents large deflection, post-buckling analysis of plane and spatial elastic frames from a dynamic point of view. A co-rotational formulation combined with small deflection beam theory with the inclusion of the effect of axial force is adopted. A constant arc length method combined with the modified Newton–Raphson iteration method and the extrapolation technique to improve the convergence behaviour are employed to trace the non-linear equilibrium path up to the limit point. The change in the sign of the incremental work done is used to determine the occurrence of a limit point. As the limit state being examined is passed, the previous converged solution is adopted to start the non-linear dynamic analysis based on the average acceleration of the Newmark algorithm with a slow rate of load increment and in order to trace the post-buckling load-deflection path. As a result, the snap through problem is overcome without decreasing the external load. Numerical examples are presented to demonstrate the performance of the method.
HUMAN FACE IMAGE PROCESSING TECHNIQUES
Authors: YAN HONG
Published: July 2002

Human face image processing techniques have many applications, such as in security operations, entertainment, medical imaging and telecommunications. In this paper, we provide an overview of existing computer algorithms for face detection and facial feature location, face recognition, image compression and animation. We also discuss limitations of current methods and research work needed in the future.
INTERACTIVE NAVIGATION OF VIRTUAL VESSEL TRACKING WITH 3D INTELLIGENT SCISSORS
Authors: HENG PHENG-ANN , SUN HANQIU , CHEN KWONG-WAI , WONG TIEN-TSIN
Published: July 2002

Vessel tracking is usually needed for various medical usages such as clinical diagnosis and surgery planning. A clear understanding of the patient's actual vessel morphology is very important in planning the surgery. Tracking the vessels/bronchia from scanned medical images such as CT or MRI manually is very tedious and labor-intensive. On the other hand, a fully automatic tracking algorithm may not be very reliable. It may be sensitive to the noise in the volume data. In this paper, we propose a vessel tracking method that finds air-way paths using three-dimensional intelligent scissors. 3D Intelligent Scissors has the ability to extract hollow vessels by climbing along surfaces. Thus, a rough path can be found if the end points of a narrow tunnel are selected. Another advantage of using 3D Intelligent Scissors is that it can successfully extract the path even the actual path is broken. Very often the diameter of a blood vessel may be sometimes smaller than one voxel. Since our algorithm is semi-automatic, it provides sufficient control to accurately find out the desired paths with only minimal user intervention. We have applied the proposed 3D Intelligent Scissors for the application of tracking lung air-ways. A 3D stylus and cutting planes in the virtual volume space are used for selecting the end nodes of vessel paths and revealing the local details on the texture-mapped plane. Our system also provides advanced navigation features to guide visual examination and diagnosis of volumetric air-way paths. These include interactive control of incremental forward, backward, and rotating navigation in reference to the viewing frustum and 3D real-time input.
NON-COMMUTATIVE CURVES AND THEIR ZETA FUNCTIONS
Authors: JØRGENSEN PETER
Published: July 2002

This paper considers non-commutative curves, introduces a divisor class group and a degree map, proves a Riemann-Roch theorem, and solves the Riemann-Roch problem. These results are then used to prove the zeta function of a non-commutative curve over a finite field satisfies the two first Weil conjectures.
Justification of printed music
Authors: Blostein Dorothea , Haken Lippold
Published: July 2002

There is increasing interest in the use of computer systems for editing and printing sheet music [3, 19]. Music processing lags far behind text processing because of the complexities of music notation. Most music published today is still laid out by hand; while computers may be used, decisions about music-symbol placement are made by people. Much research remains to be done into computational methods of encoding the myriad rules of music notation. Individual rules are not difficult to formulate; it is the complex interaction among rules which is difficult to describe and control. In this article we focus on one aspect of music notation: the horizontal spacing of music to produce a right- and left- justified result.
Electronic frontier
Authors: Barlow John P.
Published: July 2002

Imagine discovering a continent so vast that it may have no end to its dimensions. Imagine a new world with more resources than all our future greed might exhaust, more opportunities than there will ever be entrepreneurs to exploit, and a peculiar kind of real estate that expands with development.
Nonoblivious hashing
Authors: Fiat Amos , Naor Moni , Schmidt Jeanette P. , Siegel Alan
Published: July 2002

Nonoblivious hashing, where information gathered from unsuccessful probes is used to modify subsequent probe strategy, is introduced and used to obtain the following results for static lookup on full tables:

(1) An
O
(1)-time worst-case scheme that uses only logarithmic additional memory, (and no memory when the domain size is linear in the table size), which improves upon previously linear space requirements.

(2) An almost sure
O
(1)-time probabilistic worst-case scheme, which uses no additional memory and which improves upon previously logarithmic time requirements.

(3) Enhancements to hashing: (1) and (2) are solved for multikey recors, where search can be performed under any key in time
O
(1); these schemes also permit properties, such as nearest neighbor and rank, to be determined in logarithmic time.
Algorithm 722: Functions to support the IEEE standard for binary floating-point arithmetic
Authors: Cody W. J. , Coonen Jerome T.
Published: July 2002

This paper describes C programs for the support functions
copysign(x,y), logb(x), scalb(x,n), nextafter(x,y), finite(x),
and
isnan(x)
recommended in the Appendix to the
IEEE Standard for Binary Floating-Point Arithmetic.
In the case of
logb
, the modified definition given in the later
IEEE Standard for Radix-Independent Floating-Point Arithmetic
is followed. These programs should run without modification on most systems conforming to the binary standard.
Evaluating hypermedia and learning
Authors: Marchionini Gary , Crane Gregory
Published: July 2002

The Perseus Project has developed a hypermedia corpus of materials related to the ancient Greek world. The materials include a variety of texts and images, and tools for using these materials and navigating the sytem. Results from a three-year evaluation of Perseus use in a variety of college settings are described. The evaluation assessed both this particular system and the application of the technological genre to information management and to learning. The evaluation used a variety of methods to address questions about learning and teaching with hypermedia and to guide the development of early versions of the system. Results illustrate that such environments offer potential for accelerating learning and for supporting new types of learning and teaching; that students and instructors must develop new strategies for learning and teaching with such technology; and that institutions must develop infrastructural support for such technology. The results also illustrate the importance of well-designed interfaces and different types of assignments on user performance.
Using semantic values to facilitate interoperability among heterogeneous information systems
Authors: Sciore Edward , Siegel Michael , Rosenthal Arnon
Published: July 2002

Large organizations need to exchange information among many separately developed systems. In order for this exchange to be useful, the individual systems must agree on the meaning of their exchanged data. That is, the organization must ensure
semantic interoperability
. This paper provides a theory of
semantic values
as a unit of exchange that facilitates semantic interoperability betweeen heterogeneous information systems. We show how semantic values can either be stored explicitly or be defined by
environments
. A system architecture is presented that allows autonomous components to share semantic values. The key component in this architecture is called the
context mediator
, whose job is to identify and construct the semantic values being sent, to determine when the exchange is meaningful, and to convert the semantic values to the form required by the receiver.

Our theory is then applied to the relational model. We provide an interpretation of standard SQL queries in which context conversions and manipulations are transparent to the user. We also introduce an extension of SQL, called Context-SQL (C-SQL), in which the
context
of a semantic value can be explicitly accessed and updated. Finally, we describe the implementation of a prototype context mediator for a relational C-SQL system.
Alexandria Digital Library
Authors: Smith Terence R. , Frew James
Published: July 2002

The goal of the Alexandria Digital Library Project is to develop a distributed system that provides a comprehensive range of library services for collections of spatially indexed and graphical information. While such collections include digitized maps and images as important special components, the Alexandria Digital Library will involve a very wide range of graphical materials and will include textual materials. Users of the Alexandria Digital Library will range from school children to academic researchers to members of the general public. They will be able to retrieve materials from the library on the basis of information content as well by reference to spatial location.
Solving narrow banded systems on ensemble architectures
Authors: Johnsson S. Lennart
Published: July 2002

We present concurrent algorithms for the solution of narrow banded systems on ensemble architectures, and analyze the communication and arithmetic complexities of the algorithms. The algorithms consist of three phases. In phase 1, a block tridiagonal system of reduced size is produced through largely local operations. Diagonal dominance is preserved. If the original system is positive, definite, and symmetric, so is the reduced system. It is solved in a second phase, and the remaining variables obtained through local back substitution in a third phase. With a sufficient number of processing elements, there is no first and third phase. We investigate the arithmetic and communicationcomplexity of Gaussian elimination and block cyclic reduction for the solution of the reduced system on boolean cubes, perfect shuffle and shuffle-exchange networks, binary trees, and linear arrays.

With an optimum number of processors, the minimum solution time on a linear array is of an order that ranges from O(m
2
√Nm) to

O(m
3
+ m
3

log
2
(
N/m
)) depending on the bandwidth, the dimension of the problem, and the times for communication and arithmetic. For boolean cubes, cube-connected cycles, prefect shuffle and shuffle-exchange networks, and binary trees, the minimum time is O(m
3
+m
3
log
2
(N/m)) including the communication complexity
Composing letters with a simulated listening typewriter
Authors: Gould John D. , Conti John , Hovanyecz Todd
Published: July 2002

With a listening typewriter, what an author says would be automatically recognized and displayed in front of him or her. However, speech recognition is not yet advanced enough to provide people with a reliable listening typewriter. An aim of our experiments was to determine if an imperfect listening typewriter would be useful for composing letters. Participants dictated letters, either in isolated words or in consecutive word speech. They did this with simulations of listening typewriters that recognized either a limited vocabulary (1000 or 5000 words)or an unlimited vocabulary. Results suggest that some versions, even upon first using them, could be at least as good as traditional methods of handwriting and dictating. Isolated word speech with large vocabularies may provide the basis for a useful listening typewriter.
Magic conditions
Authors: Mumick Inderpal Singh , Finkelstein Sheldon J. , Pirahesh Hamid , Ramakrishnan Raghu
Published: July 2002

Much recent work has focused on the bottom-up evaluation of Datalog programs [Bancilhon and Ramakrishnan 1988]. One approach, called magic-sets, is based on rewriting a logic program so that bottom-up fixpoint evaluation of the program avoids generation of irrelevant facts [Bancilhon et al. 1986; Beeri and Ramakrishnan 1987; Ramakrishnan 1991]. It was widely believed for some time that the principal application of the magic-sets technique is to restrict computation in recursive queries using equijoin predicates. We extend the magic-sets transformation to use predicates other than equality (
X
>10, for example) in restricting computation. The resulting
ground magic-sets transformation
is an important step in developing an extended magic-sets transformation that has practical utility in “real” relational databases, not only for recursive queries, but for nonrecursive queries as well [Mumick et al. 1990b; Mumick 1991].
Software reuse
Authors: Frakes William , Terry Carol
Published: July 2002

As organizations implement systematic software reuse programs to improve productivity and quality, they must be able to measure their progress and identify the most effective reuse strategies. This is done with reuse metrics and models. In this article we survey metrics and models of software reuse and reusability, and provide a classification structure that will help users select them. Six types of metrics and models are reviewed: cost-benefit models, maturity assessment models, amount of reuse metrics, failure modes models, reusability assessment models, and reuse library metrics.
Eliminating receive livelock in an interrupt-driven kernel
Authors: Mogul Jeffrey C. , Ramakrishnan K. K.
Published: July 2002

Most operating systems use interface interrupts to schedule network tasks. Interrupt-driven systems can provide low overhead and good latency at low offered load, but degrade significantly at higher arrival rates unless care is taken to prevent several pathologies. These are various forms of
receive livelock
, in which the system spends all of its time processing interrupts, to the exclusion of other necessary tasks. Under extreme conditions, no packets are delivered to the user application or the output of the system. To avoid livelock and related problems, an operating system must schedule network interrupt handling as carefully as it schedules process execution. We modified an interrupt-driven networking implementation to do so; this modification eliminates receive livelock without degrading other aspects of system performance. Our modifications include the use of polling when the system is heavily loaded, while retaining the use of interrupts ur.Jer lighter load. We present measurements demonstrating the success of our approach.
Converting thread-level parallelism to instruction-level parallelism via simultaneous multithreading
Authors: Lo Jack L. , Emer Joel S. , Levy Henry M. , Stamm Rebecca L. , Tullsen Dean M. , Eggers S. J.
Published: July 2002

To achieve high performance, contemporary computer systems rely on two forms of parallelism: instruction-level parallelism (ILP) and thread-level parallelism (TLP). Wide-issue super-scalar processors exploit ILP by executing multiple instructions from a single program in a single cycle. Multiprocessors (MP) exploit TLP by executing different threads in parallel on different processors. Unfortunately, both parallel processing styles statically partition processor resources, thus preventing them from adapting to dynamically changing levels of ILP and TLP in a program. With insufficient TLP, processors in an MP will be idle; with insufficient ILP, multiple-issue hardware on a superscalar is wasted. This article explores parallel processing on an alternative architecture, simultaneous multithreading (SMT), which allows multiple threads to complete for and share all of the processor's resources every cycle.

The most compelling reason for running parallel applications on an SMT processor is its ability to use thread-level parallelism and instruction-level parallelism interchangeably. By permitting multiple threads to share the processor's functional units simultaneously, the processor can use both ILP and TLP to accommodate variations in parallelism. When a program has only a single thread, all of the SMT processor's resources can be dedicated to that thread; when more TLP exists, this parallelism can compensate for a lack of per-thread ILP.

We examine two alternative on-chip parallel architectures for the next generation of processors. We compare SMT and small-scale, on-chip multiprocessors in their ability to exploit both ILP and TLP. First, we identify the hardware bottlenecks that prevent multiprocessors from effectively exploiting ILP. Then, we show that because of its dynamic resource sharing, SMT avoids these inefficiencies and benefits from being able to run more threads on a single processor. The use of TLP is especially advantageous when per-thread ILP is limited. The ease of adding additional thread contexts on an SMT (relative to adding additional processors on an MP) allows simultaneous multithreading to expose more parallelism, further increasing functional unit utilization and attaining a 52% average speedup (versus a four-processor, single-chip multiprocessor with comparable execution resources). This study also addresses an often-cited concern regarding the use of thread-level parallelism or multithreading: interference in the memory system and branch prediction hardware.

We find the multiple threads cause interthread interference in the caches and place greater demands on the memory system, thus increasing average memory latencies. By exploiting threading-level parallelism, however, SMT hides these additional latencies, so that they only have a small impact on total program performance. We also find that for parallel applications, the additional threads have minimal effects on branch prediction.
Hyperdocuments as automata
Authors: Stotts P. David , Furuta Richard , Cabarrus Cyrano Ruiz
Published: July 2002

We present a view of hyperdocuments in which each document encodes its own browsing semantics in its links. This requires a mental shift in how a hyperdocument is thought of abstractly. Instead of treating the links of a document as defining a static directed graph, they are thought of as defining an abstract program, termed the
links-automaton
of the document. A branching temporal logic notation, termed HTL*, is introduced for specifying properties a document should exhibit during browsing. An automated program verification technique called
model checking
is used to verify that browsing specifications in a subset of HTL* are met by the behavior defined in the links-automation. We illustrate the generality of these techniques by applying them first to several Trellis documents and then to a Hyperties document.
Augmenting organizational memory
Authors: Ackerman Mark S.
Published: July 2002

A growing concern for organizations and groups has been to augment their knowledge and expertise. One such augmentation is to provide an organizational memory, some record of the organization's knowledge. However, relatively little is known about how computer systems might enhance organizational, group, or community memory. This article presents Answer Garden, a system for growing organizational memory. The article describes the system and its underlying implementation. It then presents findings from a field study of Answer Garden. The article discusses the usage data and qualitative evaluations from the field study, and then draws a set of lessons for next-generation organizational memory systems.
Lower bounds on communication complexity in distributed computer networks
Authors: Tiwari Prasoon
Published: July 2002

The main result of this paper is a general technique for determining lower bounds on the communication complexity of problems on various distributed computer networks. This general technique is derived by simulating the general network by a linear array and then using a lower bound on the communication complexity of the problem on the linear array. Applications of this technique yield optimal bounds on the communication complexity of merging, ranking, uniqueness, and triangle-detection problems on a ring of processors. Nontrivial near-optimal lower bounds on the communication complexity of distinctness, merging, and ranking on meshes and complete binary trees are also derived.
Randomized parallel communications on an extension of the omega network
Authors: Mitra D. , Cieslak R. A.
Published: July 2002

Parallel communication algorithms and networks are central to large-scale parallel computing and, also, data communications. This paper identifies adverse source-destination traffic patterns and proposes a scheme for obtaining relief by means of randomized routing of packets on simple extensions of the well-known omega networks. Valiant and Aleliunas have demonstrated randomized algorithms, for a certain context which we call nonrenewal, that complete the communication task in time
O
(log
N
) with overwhelming probability, where
N
is the number of sources and destinations. Our scheme has advantages because it uses switches of fixed degree, requires no scheduling, and, for the nonrenewal context, is as good in proven performance. The main advantage of our scheme comes when we consider the renewal context in which packets are generated at the sources continually and asynchronously. Our algorithm extends naturally from the nonrenewal context. In the analysis in the renewal context we, first, explicitly identify the maximum traffic intensities in the internal links of the extended omega networks over all source-destination traffic specifications that satisfy loose bounds. Second, the benefits of randomization on the stability of the network are identified. Third, exact results, for certain restricted models for sources and transmission, and approximate analytic results, for quite general models, are derived for the mean delays. These results show that, in the stable regime, the maximum mean time from source to destination is asymptotically proportional to log
N
. Numerical results are presented.
A Time-Sharing Queue with a Finite Number of Customers
Authors: Adiri I. , Avi-Itzhak B.
Published: July 2002

A time-sharing queue serving a finite number of customers is described. It is assumed that both the service time and the time elapsing between termination of service and the next arrival of the same customer at the queue (service station) are exponential. The model was studied by Krishnamoorthi and Wood, but their results are not in complete agreement with the results of this paper. In addition, some new results are presented in terms of steady-state expectations.
Statistical Properties of the Buddy System
Authors: Purdom Paul W. , Stigler Stephen M.
Published: July 2002

The utilization of space and the running speed of the buddy system are considered Equations are derived that give various statistical properties of the buddy system. For the bottom level with Poisson requests and exponential service times the expected amount of space wasted by pairing full cells with empty cells is about 0.513

ρ

1/2
and the mean time between requests from the bottom level to the next level is about 1.880

ρ

1/2
λ
-1
, where
ρ
is the mean number of blocks in use on the bottom level and λ
-1
is the mean time between requests for blocks on the bottom level. The results of a number of simulations of the buddy system are also given and compared with the analytical studies.
On the Complete Covering Problem for
LR
(
k
)Grammars
Authors: Mickunas M. Dennis
Published: July 2002

A direct, one-step transformation is presented for transforming an arbitrary
LR
(
k
) context-free grammar,
G
, to an
LR
(1) grammar,
G
′, which completely covers
G
. Under additional hypotheses,
G
′ may be made
LR
(0).
Record Allocation for Minimizing Expected Retrieval Costs on Drum-Like Storage Devices
Authors: Cody R. A. , Coffman E. G.
Published: July 2002

This paper examines the problem of distributing a set of equal-size records among the sectors of a drum-like storage device in order to exploit known access frequencies and reduce the average access time. A simple catenated search model is defined for which, the problem is shown to be NP-complete. Heuristics are then defined and analyzed in terms of worst-case bounds. It is shown that easily implemented highest-access-frequency-first assignment rules provide an average access time very close to optimal.
Quantifying loop nest locality using SPEC'95 and the perfect benchmarks
Authors: McKinley Kathryn S. , Temam Olivier
Published: July 2002

This article analyzes and quantifies the locality characteristics of numerical loop nests in order to suggest future directions for architecture and software cache optimizations. Since most programs spend the majority of their time in nests, the vast majority of cache optimization techniques target loop nests. In contrast, the locality characteristics that drive these optimizations are usually collected across the entire application rather than at the nest level. Researchers have studied numerical codes for so long that a number of commonly held assertions have emerged on their locality characteristics. In light of these assertions, we use the SPEC'95 and Perfect Benchmarks to take a new look at measuring locality on numerical codes based on references, loop nests, and program locality properties. Our results show that several popular assertions are at best overstatements. For example, although most reuse is within a loop nest, in line with popular assertions, most misses are internest capacity misses, and they correspond to potential reuse between nearby loop nests. In addition, we find that temporal and spatial reuse have balanced roles within a loop nest and that most reuse across nests and the entire program is temporal. These results are consistent with high hit rates (80% or more hits), but go against the commonly held assumption that spatial reuse dominates. Our locality measurements reveal important differences between loop nests and programs, refute some popular assertions, and provide new insights for the compiler writer and the architect.
The duality of database structures and design techniques
Authors: Gillenson Mark L.
Published: July 2002

Attempting to pair database structures with database design techniques that seem incompatible yields some fascinating concepts about the world of database, including foreign keys and multiple relationships.
A fair share scheduler
Authors: Kay J. , Lauder P.
Published: July 2002

Central-processing-unit schedulers have traditionally allocated resources fairly among processes. By contrast, a fair Share scheduler allocates resources so that users get their fair machine share over a long period.
Computer backup pools, disaster recovery, and default risk
Authors: Kahane Yehuda , Neumann Seev , Tapiero Charles S.
Published: July 2002

There is a growing popularity of computer backup pools, where a few members share the ownership, or right for service, of a computer center. Such a center stands by to provide for the lost computing capacity of a member suffering a computer breakdown and disaster recovery. The efficiency of such a solution may be examined from various points of view, such as costs, response time, reliability etc. We focus on the reliability of such an arrangement. Two types of default risks are discussed: the probability that the center itself will break down when needed, so that it would be unable to provide service (this is similar to the traditional measure of a "probability of ruin") and a "perceived probability of ruin" (the probability that a member will be affected by the failure of the center). We borrow the concepts of probability of ruin from the risk management and insurance literature, in order to reach explicit relationships between these probabilities and the pricing of a mutual computer pool. It is shown that the membership fee for each participant must be a function of both the payments of all members and their loss (call for service) distributions, reflecting thereby the simultaneity of and mutual interdependence of members.
Systems, interactions, and macrotheory
Authors: Barnard Philip , May Jon , Duke David , Duce David
Published: July 2002

A significant proportion of early HCI research was guided by one very clear vision: that the existing theory base in psychology and cognitive science could be developed to yield engineering tools for use in the interdisciplinary context of HCI design. While interface technologies and heuristic methods for behavioral evaluation have rapidly advanced in both capability and breadth of application, progress toward deeper theory has been modest, and some now believe it to be unnecessary. A case is presented for developing new forms of theory, based around generic “systems of interactors.” An overlapping, layered structure of macro- and microtheories could then serve an explanatory role, and could also bind together contributions from the different disciplines. Novel routes to formalizing and applying such theories provide a host of interesting and tractable problems for future basic research in HCI.
Improving the aircraft design process using Web-based modeling and simulation
Authors: Reed John A. , Follen Gregory J. , Afjeh Abdollah A.
Published: July 2002

Designing and developing new aircraft systems is time-consuming and expensive. Computational simulation is a promising means for reducing design cycle times, but requires a flexible software environment capable of integrating advanced multidisciplinary and multifidelity analysis methods, dynamically managing data across heterogeneous computing platforms, and distributing computationally complex tasks. Web-based simulation, with its emphasis on collaborative composition of simulation models, distributed heterogeneous execution, and dynamic multimedia documentation, has the potential to meet these requirements. This paper outlines the current aircraft design process, highlighting its problems and complexities, and presents our vision of an aircraft design process using Web-based modeling and simulation.
The legal protection of computer software
Authors: Graham Robert L.
Published: July 2002

As new as the technology itself, a sometimes confusing array of legal protections are now available to safeguard the huge investment of time and money that goes into the development of sophisticated commercial software.
Modularity and the sequential file update problem
Authors: Levy Michael R.
Published: July 2002

The best-known solution to the sequential file update problem is the balanced-line algorithm. Here, the problem is solved using abstract data types and the resulting Cobol program illustrated. It is suggested that the program's modular decomposition aids in the development of the solution.
File archival techniques using data compression
Authors: Pechura Michael
Published: July 2002

The performance of most small computer systems is determined, to a large extent, by the characteristics of their mass storage devices. Data compression can expand the storage capacity of such devices and also slightly increase their speed. Here, a summary of one method of data compression using Huffman variable length coding is presented, along with statistics of effectiveness for various file types and practical techniques for integrating such methods into a small computer system.
An experimental study of the human/computer interface
Authors: Benbasat Izak , Dexter Albert S. , Masulis Paul S.
Published: July 2002

An exploratory study was conducted to analyze whether interface and user characteristics affect decision effectiveness and subject behavior in an interactive human/computer problem-solving environment. The dependent variables were performance and the use of the systems options. Two of the independent variables examined, experience and cognitive style, were user characteristics; the other three, dialogue, command, and default types, were interface characteristics. Results indicate that both user and interface characteristics influence the use of the system options and the request for information in the problem-solving task.
Learning and reasoning by analogy
Authors: Winston Patrick H.
Published: July 2002

We use analogy when we say something is a Cinderella story and when we learn about resistors by thinking about water pipes. We also use analogy when we learn subjects like economics, medicine, and law. This paper presents a theory of analogy and describes an implemented system that embodies the theory. The specific competence to be understood is that of using analogies to do certain kinds of learning and reasoning. Learning takes place when analogy is used to generate a constraint description in one domain, given a constraint description in another, as when we learn Ohm's law by way of knowledge about water pipes. Reasoning takes place when analogy is used to answer questions about one situation, given another situation that is supposed to be a precedent, as when we answer questions about
Hamlet
by way of knowledge about
Macbeth
.
Interference detection among solids and surfaces
Authors: Boyse John W.
Published: July 2002

In many industrial environments it is necessary to determine whether there is interference among components. There are many potential interference problems in products made up of assemblies of components and in product manufacturing and testing. Typically, drawings are used in an attempt to detect such unwanted interferences, but the two-dimensional, static drafting medium does not always show interferences among three-dimensional, moving parts. This paper presents a computer representation for solids and surfaces and algorithms which carry out interference checking among objects so represented. Objects are represented as polyhedra or as piecewise planar surfaces. Two types of interference checking are discussed: detection of intersections among objects in fixed positions and detection of collisions among objects moving along specified trajectories.
Price/performance patterns of U. S. computer systems
Authors: Cale E. G. , Gremillion L. L. , McKenney J. L.
Published: July 2002

Econometric models of the U.S. computer market have been developed to study the relationships between system price and hardware performance. Single measures of price/performance such as “Grosch's Law” are shown to be so oversimplified as to be meaningless. Multiple-regression models predicting system cost as a function of several hardware characteristics do, however, reveal a market dichotomy. On one hand there exists a stable, price predictable market for larger, general purpose computer systems. The other market is the developing one for small business computer systems, a market which is relatively unstable with low price predictability.
Approximating block accesses in database organizations
Authors: Yao S. B.
Published: July 2002

When data records are grouped into blocks in secondary storage, it is frequently necessary to estimate the number of blocks

X
D

accessed for a given query. In a recent paper [1], Cardenas gave the expression

X
D

=
m
(1 - (1 - 1/
m
)

k

), (1) assuming that there are
n
records divided into
m
blocks and that the
k
records satisfying the query are distributed uniformly among the
m
blocks. The derivation of the expression was left to the reader as an exercise.
The notions of consistency and predicate locks in a database system
Authors: Eswaran K. P. , Gray J. N. , Lorie R. A. , Traiger I. L.
Published: July 2002

In database systems, users access shared data under the assumption that the data satisfies certain consistency constraints. This paper defines the concepts of transaction, consistency and schedule and shows that consistency requires that a transaction cannot request new locks after releasing a lock. Then it is argued that a transaction needs to lock a logical rather than a physical subset of the database. These subsets may be specified by predicates. An implementation of predicate locks which satisfies the consistency condition is suggested.
A user authentication scheme not requiring secrecy in the computer
Authors: Evans Arthur , Kantrowitz William , Weiss Edwin
Published: July 2002

In many computer operating systems a user authenticates himself by entering a secret password known solely to himself and the system. The system compares this password with one recorded in a Password Table which is available to only the authentication program. The integrity of the system depends on keeping the table secret. In this paper a password scheme is presented which does not require secrecy in the computer.
All
aspects of the system, including all relevant code and data bases, may be known by anyone attempting to intrude.

The scheme is based on using a function
H
which the would-be intruder is unable to invert. This function is applied to the user's password and the result compared to a table entry, a match being interpreted as authentication of the user. The intruder may know all about
H
and have access to the table, but he can penetrate the system only if he can invert
H
to determine an input that produces a given output.

This paper discusses issues surrounding selection of a suitable
H
. Two different plausible arguments are given that penetration would be exceedingly difficult, and it is then argued that more rigorous results are unlikely. Finally, some human engineering problems relating to the scheme are discussed.
A genealogy of control structures
Authors: Ledgard Henry F. , Marcotty Michael
Published: July 2002

The issue of program control structures has had a history of heated controversy. To put this issue on a solid footing, this paper reviews numerous theoretical results on control structures and explores their practical implications.

The classic result of Böhm and Jacopini on the theoretical completeness of if-then-else and while-do is discussed. Several recent ideas on control structures are then explored. These include a review of various other control structures, results on time/space limitations, and theorems relating the relative power of control structures under several notions of equivalence.

In conclusion, the impact of theoretical results on the practicing programmer and the importance of one-in, one-out control structures as operational abstractions are discussed. It is argued further that there is insufficient evidence to warrant more than if-then-else, while-do, and their variants.
An extensible editor for a small machine with disk storage
Authors: Benjamin Arthur J.
Published: July 2002

A design philosophy for developing a sophisticated utility program is illustrated by the actual design and implementation of a text editor. A versatile data structure is employed so that only a small number of programmed subroutines are necessary for all types of data manipulation. Such a data structure is described, and its merits are illustrated by the ease with which powerful extensions can be implemented in terms of a few basic editing functions.
Compiling fixed-point multiplications
Authors: Bernstein Herbert J.
Published: July 2002

With reference to the article by H. T. Gladwin [1], (Comm.) it should be noted that the technique described is a limited subset of techniques known for many years, particularly to programmers for machines lacking an integer multiply instruction, CDC 6000 PPU's for example. It is easier to present and implement more generally applicable techniques, such as full decomposition into “runs” of 0's and 1's to yield representation as: ∑

L

i
=0

(2

m
(
i
)

- 2

n
(
i
)

) which may be further compressed by replacing such terms as -2

m
+1

+ 2

m

by -2

m

. In decomposing numbers from the right on a CDC 6000 in particular, special techniques are possible [2].

Finally, Gladwin failed to credit the CDC RUN compilers, in use for over six years on the very machines he discussed, for doing a large number of constant multiplies by shifts and adds (subroutine SHM in overlay RUN1).
A controller for a braille terminal
Authors: Rubinstein Richard , Feldman Julian
Published: July 2002

Anderson and Rogers [1] have described a set of modifications which convert a standard model 33 tele-type into a device which produces embossed braille characters. Thus, blind computer users can communicate with a computer without the help of a sighted person to read the output. The disadvantage of this terminal alone is that either the applications program or the operating system of the host computer must have special software to map each output character into a sequence of three characters necessary to emboss its braille equivalent. Such software modification can be expensive and has to be done for each applications program or operating system the blind person wants to use.