bluuebunny/crossref_metadata_2025 huggingface dataset:
Supporting distributed office problem solving in organizations
Authors: Woo Carson C. , Lochovsky Frederick H.
Published: July 2002

To improve the effectiveness of office workers in their decision making, office systems have been built to support (rather than replace) their judgment. However, these systems model office work in a centralized environment, and/or they can only support a single office worker. Office work that is divided into specialized domains handled by different office workers (where cooperation is needed in order to accomplish the work) is not supported. In this paper, we will present a model that supports office problem solving in a logically distributed environment. (In some systems, information is geographically distributed for performance purposes rather than for conceptual need. The term,
logically
, is therefore used to indicate the logical need of organizing information without having to worry about the physical location of the information.) In particular, cooperative tools that can be used to support office workers during the process of their problem solving is discussed.
Selecting MIS projects by steering committee
Authors: McKeen J. D. , Guimaraes Tor
Published: July 2002

Steering committees have recently gained vast acceptance in organizations as the mechanism used to select management information systems (MIS) projects. Because of their widespread adoption and their differences from other selection mechanisms with respect to orientation, steering committees were chosen for study. Data from 92 projects selected from 32 organizations were analyzed. As hypothesized, projects selected by steering committees were found to differ significantly from those chosen via other selection mechanisms. The implications of this result for organizations using steering committees to select MIS projects are presented.
Fast pseudorandom generators for normal and exponential variates
Authors: Wallace C. S.
Published: July 2002

Fast algorithms for generating pseudorandom numbers from the unit-normal and unit-exponential distributions are described. The methods are unusual in that they do not rely on a source of uniform random numbers, but generate the target distributions directly by using their maximal-entropy properties. The algorithms are fast. The normal generator is faster than the commonly used Unix library uniform generator “random” when the latter is used to yield real values. Their statistical properties seem satisfactory, but only a limited suite of tests has been conducted. They are written in C and as written assume 32-bit integer arithmetic. The code is publicly available as C source and can easily be adopted for longer word lengths and/or vector processing.
Efficient routing in optical networks
Authors: Aggarwal Alok , Bar-Noy Amotz , Coppersmith Don , Ramaswami Rajiv , Schieber Baruch , Sudan Madhu
Published: July 2002

This paper studies the problem of dedicating routes to connections in optical networks. In optical networks, the vast bandwidth available in an optical fiber is utilized by partitioning it into several channels, each at a different optical wavelength. A connection between two nodes is assigned a specific wavelength, with the constraint that no two connections sharing a link in the network can be assigned the same wavelength. This paper considers optical networks with and without switches, and different types of routing in these networks. It presents optimal or near-optimal constructions of optical networks in these cases and algorithms for routing connections, specifically permutation routing for the networks constructed here.
Inversive and linear congruential pseudorandom number generators in empirical tests
Authors: Leeb Hannes , Wegenkittl Stefan
Published: July 2002

We present results from a series of empirical tests of pseudorandom number generators. The tests cover a broad range of designs due to bit-oriented, efficient test statistics and a testing procedure inwhich we vary the sample size, dimension, and the statistics' resolution within vast bounds. Inversive generation methods pass the tests for a broader range of thest parameters thatn linear generators with equal period legth. The results exemplify how the lattice structure of linear generatorsf can affect a stochastic simulation and suggest the use of inversive generators for cross-checking the results.
Two heads are better than two tapes
Authors: Jiang Tao , Seiferas Joel I. , Vitányi Paul M. B.
Published: July 2002

We show that a Turing machine with two single-head one-dimensional tapes cannot recognize the set.
The incrementor
Authors: Ressler Sanford
Published: July 2002

Description: The incrementor is a visually compact, flexible, and consistent mechanism for modifying the variables presented to the user. A locator (i.e., mouse) with two buttons is the required input device. The names of the variables appear in the center of one or two pairs of arrows, and the value of the variable appears just below the right arrow and to the left of the up arrow (Figures 1 and 2).
An experimental procedure for simulation response surface model identification
Authors: Schruben Lee W. , Cogliano V. James
Published: July 2002

An experimental method for identifying an appropriate model for a simulation response surface is presented. This technique can be used for globally identifying those factors in a simulation that have a significant influence on the output. The experiments are run in the frequency domain. A simulation model is run with input factors that oscillate at different frequencies during a run. The functional form of a response surface model for the simulation is indicated by the frequency spectrum of the output process. The statistical significance of each term in a prospective response surface model can be measured. Conditions are given for which the frequency domain approach is equivalent to ranking terms in a response surface model by their correlation with the output. Frequency domain simulation experiments typically will require many fewer computer runs than conventional run-oriented simulation experiments.
Rating the major computing periodicals on readability
Authors: Lemos Ronald S.
Published: July 2002

The readability of the ten major computing periodicals is analyzed using the Flesch Reading Ease Index.
Supporting the restructuring of data abstractions through manipulation of a program visualization
Authors: Bowdidge Robert W. , Griswold William G.
Published: July 2002

With a meaning-preserving restructuring tool, a software engineer can change a program's structure to ease future modifications. However, deciding how to restructure the program requires a global understanding of the program's structure, which cannot be derived easily by directly inspecting the source code. We describe a manipulable program visualization—thestar diagram—that supports the restructuring task of encapsulating a global data structure. The star diagram graphically displays information pertinent to encapsulation, and direct manipulation of the diagram causes the underlying program to be restructured. The visualization compactly presents all statements in the program that use the given global data structure, helping the programmer to choose the functions that completely encapsulate it. Additionally, the visualization elides code unrelated to the data structure and to the task and collapses similar expressions to help the programmer identify frequently occurring code fragments and manipulate them together. The visualization is mapped directly to the program text, so manipulation of the visualization also restructures the program. We present the star diagram concept and describe an implementation of the star diagram built upon a meaning-preserving restructuring tool for Scheme. We also describe our creation of star diagram generators for C programs, and we test the scalability of the star diagram using large C and MUMPS programs.
Adjacency detection using quadcodes
Authors: Li Shu-Xiang , Loew Murray H.
Published: July 2002

A method is presented for determining whether two given regions are adjacent, and for finding all the neighbors of different sizes for a given region. Regions are defined as elementary squares of any size. In a companion paper [
2
], we introduce the quadcode and discuss its use in representing geometric concepts in the coded image, such as location, distance, and adjacency. In this paper we give a further discussion of adjacency in terms of quadcodes. Gargantini [
1
] discussed adjacency detection using linear quadtrees. Her discussion was applied to pixels, and a procedure was given to find a pixel's southern neighbor only. This paper considers elementary squares of any size, and gives procedures for both aspects of the problem: for determining whether two given regions are adjacent, and for finding all the neighbors of different sizes for a given region.
Exception-based information flow control in object-oriented systems
Authors: Bertino Elisa , De Capitani Di Vimercati Sabrina , Ferrari Elena , Samarati Pierangela
Published: July 2002

We present an approach to control information flow in object-oriented systems. The decision of whether an information flow is permitted or denied depends on both the authorizations specified on the objects and the process by which information is obtained and transmitted. Depending on the specific computations, a process accessing sensitive information could still be allowed to release information to users who are not allowed to directly access it. Exceptions to the permissions and restrictions stated by the authorizations are specified by means of exceptions associated with methods. Two kinds of exceptions are considered:
invoke exceptions,
applicable during a mehtod execution and
reply exceptions
applicable to the information returned by a method. Information flowing from one object into another or returned to the user is subject to the different exceptions specified for the methods enforcing the transmission. We formally characterize information transmission and flow in a transaction and define the conditions for safe information flow. We define security specifications and characterize safe information flows. We propose an approach to control unsafe flows and present an algorithm to enforce it. We also illustrate an efficient implementation of our controls and present some experimental results evaluating its performance.
Disk file allocation based on the buddy system
Authors: Koch Philip D. L.
Published: July 2002

The buddy system is known for its speed and simplicity. However, high internal and external fragmentation have made it unattractive for use in operating system file layout. A variant of the binary buddy system that reduces fragmentation is described. Files are allocated on up to
t
extents, and inoptimally allocated files are periodically reallocated. The Dartmouth Time-Sharing System (DTSS) uses this method. Several installations of DTSS, representing different classes of workload, are studied to measure the method's performance. Internal fragmentation varies from 2-6 percent, and external fragmentation varies from 0-10 percent for expected request sizes. Less than 0.1 percent of the CPU is spent executing the algorithm. In addition, most files are stored contiguously on disk. The mean number of extents per file is less than 1.5, and the upper bound is
t
. Compared to the tile layout method used by UNIX, the buddy system results in more efficient access but less efficient utilization of disk space. As disks become larger and less expensive per byte, strategies that achieve efficient I/O throughput at the expense of some storage loss become increasingly attractive.
Processing encrypted data
Authors: Ahituv Niv , Lapid Yeheskel , Neumann Seev
Published: July 2002

A severe problem in the processing of encrypted data is that very often, in order to perform arithmetic operations on the data, one has to convert the data back to its nonencrypted origin before performing the required operations. This paper addresses the issue of processing data that have been encrypted while the data are in an encrypted mode. It develops a new approach for encryption models that can facilitate the processing of such data. The advantages of this approach are reviewed, and a basic algorithm is developed to prove the feasibility of the approach.
Linear hashing with overflow-handling by linear probing
Authors: Larson Per-Åke
Published: July 2002

Linear hashing is a file structure for dynamic files. In this paper, a new, simple method for handling overflow records in connection with linear hashing is proposed. The method is based on linear probing and does not rely on chaining. No dedicated overflow area is required. The expansion sequence of liner hashing is modified to improve the performance, which requires changes in the address computation. A new address computation algorithm and an expansion algorithm are given. The performance of the method is studied by simulation. The algorithms for the basic file operations are very simple, and the overall performance is competitive with that of other variants of linear hashing.
Predicting performance in an introductory computer science course
Authors: Butcher D. F. , Muth W. A.
Published: July 2002

A group of 269 first-semester freshmen was used to predict both performance in an introductory computer science course and first-semester college grade point average by using information regarding the students' programs and performance in high school along with American College Testing Program (ACT) test scores.
Design of an external schema facility to define and process recursive structures
Authors: Clemons Eric K.
Published: July 2002

The role of the external schema is to support user views of data and thus to provide programmers with easier data access. This author believes that an external schema facility is best based on hierarchies, both simple and recursive. After a brief introduction to an external schema facility to support simple hierarchical user views, the requirements for a facility for recursive hierarchies are listed and the necessary extensions to the external schema definition language are offered.

Functions that must be provided for generality in definition are node specification and node control. Tree traversal functions must be provided for processing. Definitions of each and examples of use are presented.
Analysis of a heuristic for full trie minimization
Authors: Comer Douglas
Published: July 2002

A trie is a distributed-key search tree in which records from a file correspond to leaves in the tree. Retrieval consists of following a path from one root to a leaf, where the choice of edge at each node is determined by attribute values of the key. For full tries, those in which all leaves lie at the same depth, the problem of finding an ordering of attributes which yields a minimum size trie is NP-complete.

This paper considers a “greedy” heuristic for constructing low-cost tries. It presents simulation experiments which show that the greedy method tends to produce tries with small size, and analysis leading to a worst case bound on approximations produced by the heuristic. It also shows a class of files for which the greedy method may perform badly, producing tries of high cost.
Decompiling CODASYL DML into retional queries
Authors: Katz R. H. , Wong E.
Published: July 2002

A “decompilation” algorithm is developed to transform a program written with the procedural operations of CODASYL DML into one which interacts with a relational system via a nonprocedural query specification. An Access Path Model is introduced to interpret the semantic accesses performed by the program. Data flow analysis is used to determine how FIND operations implement semantic accesses. A sequence of these is mapped into a relational query and embedded into the original program. The class of programs for which the algorithm succeeds is characterized.
Rosolving conflicts in global storage design through replication
Authors: Katz R. H. , Wong E.
Published: July 2002

We present a conceptual framework in which a database's intra- and interrecord set access requirements are specified as a constrained assignment of abstract characteristics (“evaluated,” “indexed,” “clustered,” “well-placed”) to logical access paths. We derive a physical schema by choosing an available storage structure that most closely provides the desired access characteristics. We use explicit replication of schema objects to reduce the access cost along certain paths, and analyze the trade-offs between increased update overhead and improved retrieval access. Finally, we given an algorithm to select storage structures for a CODASYL 78 DBTG schema, given its access requirements specification.
Data abstractions for database systems
Authors: Lockemann Peter C. , Mayr Heinrich C. , Weil Wolfgang H. , Wohlleber Wolfgang H.
Published: July 2002

Data abstractions were originally conceived as a specification tool in programming. They also appear to be useful for exploring and explaining the capabilities and shortcomings of the data definition and manipulation facilities of present-day database systems. Moreover they may lead to new approaches to the design of these facilities. In the first section the paper introduces an axiomatic method for specifying data abstractions and, on that basis, gives precise meaning to familiar notions such as data model, data type, and database schema. In a second step the various possibilities for specifying data types within a given data model are examined and illustrated. It is shown that data types prescribe the individual operations that are allowed within a database. Finally, some additions to the method are discussed which permit the formulation of interrelationships between arbitrary operations.
Limitations of record-based information models
Authors: Kent William
Published: July 2002

Record structures are generally efficient, familiar, and easy to use for most current data processing applications. But they are not complete in their ability to represent information, nor are they fully self-describing.
Optimum reorganization points for linearly growing files
Authors: Tuel William G.
Published: July 2002

The problem of finding optimal reorganization intervals for linearly growing files is solved. An approximate reorganization policy, independent of file lifetime, is obtained. Both the optimum and approximate policies are compared to previously published results using a numerical example.
On the estimation of the number of desired records with respect to a given query
Authors: Yu C. T. , Luk W. S. , Siu M. K.
Published: July 2002

The importance of the estimation of the number of desired records for a given query is outlined. Two algorithms for the estimation in the “closest neighbors problem” are presented. The numbers of operations of the algorithms are
Ο
(
ml
2
) and
Ο
(
ml
), where
m
is the number of clusters and
l
is the “length” of the query.
Restructuring for large databases
Authors: Navathe Shamkant B. , Fry James P.
Published: July 2002

The development of a powerful restructuring function involves two important components—the unambiguous specification of the restructuring operations and the realization of these operations in a software system. This paper is directed to the first component in the belief that a precise specification will provide a firm foundation for the development of restructuring algorithms and, subsequently, their implementation. The paper completely defines the semantics of the restructuring of tree structured databases.

The delineation of the restructuring function is accomplished by formulating three different levels of abstraction, with each level of abstraction representing successively more detailed semantics of the function.

At the first level of abstraction, the schema modification, three types are identified—naming, combining, and relating; these three types are further divided into eight schema operations. The second level of abstraction, the instance operations, constitutes the transformations on the data instances; they are divided into group operations such as replication, factoring, union, etc., and group relation operations such as collapsing, refinement, fusion, etc. The final level, the item value operations, includes the actual item operations, such as copy value, delete value, or create a null value.
A dynamic database reorganization algorithm
Authors: Yao S. B. , Das K. S. , Teorey T. J.
Published: July 2002

Reorganization is necessary in some databases for overcoming the performance deterioration caused by updates. The paper presents a dynamic reorganization algorithm which makes the reorganization decision by measuring the database search costs. Previously, the reorganization intervals could only be determined for linear deterioration and known database lifetime. It is shown that the dynamic reorganization algorithm is near optimum for constant reorganization cost and is superior for increasing reorganization cost. In addition, it can be applied to cases of unknown database lifetime and nonlinear performance deterioration. The simplicity, generality, and efficiency appear to make this good heuristic for database reorganization.
Database abstractions
Authors: Smith John Miles , Smith Diane C. P.
Published: July 2002

Two kinds of abstraction that are fundamentally important in database design and usage are defined. Aggregation is an abstraction which turns a relationship between objects into an aggregate object. Generalization is an abstraction which turns a class of objects into a generic object. It is suggested that all objects (individual, aggregate, generic) should be given uniform treatment in models of the real world. A new data type, called generic, is developed as a primitive for defining such models. Models defined with this primitive are structured as a set of aggregation hierarchies intersecting with a set of generalization hierarchies. Abstract objects occur at the points of intersection. This high level structure provides a discipline for the organization of relational databases. In particular this discipline allows: (i) an important class of views to be integrated and maintained; (ii) stability of data and programs under certain evolutionary changes; (iii) easier understanding of complex models and more natural
query formulation;
(iv)
a more systematic approach to database design;
(v)
more optimization
to be performed at lower implementation levels. The generic type is formalized by a set of invariant properties. These properties should be satisfied by all relations in a database if abstractions are to be preserved. A triggering mechanism for automatically maintaining these invariants during update operations is proposed. A simple mapping of aggregation/generalization hierarchies onto owner-coupled set structures is given.
Analysis of aarchitectural features for enhancing the performance of a database machine
Authors: Ozkarahan E. A. , Sevcik K. C.
Published: July 2002

RAP (Relational Associative Processor) is a “back-end” database processor that is intended to take over much of the effort of database management in a computer system. In order to enhance RAP's performance its design includes mechanisms for permitting features analogous to multiprogramming and virtual memory as in general purpose computer systems. It is the purpose of this paper to present the detailed design of these mechanisms, along with some analysis that supports their value. Specifically, (1) the response time provided by RAP under several scheduling disciplines involving priority by class is analyzed, (2) the cost effectiveness of the additional hardware in RAP necessary to support multiprogramming is assessed, and (3) a detailed design of the RAP virtual memory system and its monitor is presented.
Relations Between Time and Tape Complexities
Authors: Hopcroft John E. , Ullman Jeffrey D.
Published: July 2002

It is shown that if a language
L
is recognized by a (nondeterministic) single-tape Turing machine of time complexity
T
(
n
), then
L
is recognized by a (nondeterministic) offline Turing machine of tape complexity
T
1/2
(
n
). If
T
(
n
) ≥
n
2
;,
L
is recognized by a (nondeterministic) single-tape Turing machine of tape complexity
T
1/2
(
n
). If a language
L
is recognized by a (nondeterministic) offline Turing machine of time complexity (
T
(
n
), then
L
is recognized by a (nondeterministic) offline Turing machine of tape complexity (
T
(
n
) log
n
)
1/2
and by a (nondeterministic) single-tape Turing machine of that tape complexity if
T
(
n
) ≥
n
2
/log
n
.
Some Results on Tape-Bounded Turing Machines
Authors: Hopcroft J. E. , Ullman J. D.
Published: July 2002

Classes of tape-bounded Turing machines similar to the on-line and off-line Turing machines, but without the restrictions that each machine halt and be deterministic, are studied. It is shown that the lower bounds on tape complexity of [1] depend on neither the halting assumption nor determinism. The existence of a dense hierarchy of complexity classes likewise does not depend on the halting assumption, and it is shown that below log
n
tape complexity there exists a dense hierarchy of complexity classes for two-way nondeterministic devices. It is also shown that the complexity classes of one-way, nondeterministic machines below linear large complexity are not closed under complementation and are larger that the corresponding deterministic complexity class.
Nonlinear Regression With Linear Constraints: An Extension of the Magnified Diagonal Method
Authors: Shrager Richard I.
Published: July 2002

A syntax-directed picture analysis system based on a formal picture description scheme is described. The system accepts a description of a set of pictures in terms of a grammar generating strings in a picture description language; the grammar is explicitly used to direct the analysis or parse, and to control the calls on pattern classification routines for primitive picture components. Pictures are represented by directed graphs with labeled edges, where the edges denote elementary picture components and the graph connectivity mirrors the picture component connectivity; blank and don't care “patterns” allow the description of simple relations between visible patterns. The bulk of the paper is concerned with the picture parsing algorithm which is an
n
-dimensional analog of a classical top-down string parser, and an application of an implemented system to the analysis of spark chamber film. The potential benefits of this approach, as demonstrated by the application, include ease of implementation and modification of picture processing systems, and simplification of the pattern recognition problem by automatically taking advantage of contextual information.
Shifting Graphs and Their Applications
Authors: Pippenger Nicholas , Valiant Leslie G.
Published: July 2002

Graphs that in a certain precise sense are rich in sets of vertex-disjoint paths are studied. Bounds are obtained on the minimum number of edges in such graphs, and these are used to deduce nonlinear lower bounds on the computational complexity of shifting, merging, and matching problems.
Space and Time Hierarchies for Classes of Control Structures and Data Structures
Authors: Lipton R. J. , Eisenstat S. C. , DeMillo R. A.
Published: July 2002

Control structures and data structures are modeled by directed graphs. In the control case nodes represent executable statements and arcs represent possible flow of control; in the data case nodes represent memory locations and arcs represent logical adjacencies in the data structure. Classes of graphs are compared by a relation ≤

S.T

where
G
≤

S.T

H
if
G
can be embedded in
H
with at most a
T
-fold increase in distance between embedded nodes by making at most
S
“copies” of any node in
G
. For both control structures and data structures,
S
and
T
are interpreted as space and time constants, respectively. Results are presented that establish hierarchies with respect to ≤

S.T

for (1) data structures, (2) sequential program schemata normal forms, and (3) sequential control structures.
Even Simple Programs Are Hard To Analyze
Authors: Jones Neil D. , Muchnick Steven S.
Published: July 2002

A simple programming language which corresponds in computational power to the class of generalized sequential machines with final states is defined. It is shown that a variety of questions of practical programming interest about the language are of nondeterministic linear space complexity. Extensions to the language are defined (adding arithmetic and array data structures) and their complexity properties are explored. It is concluded that questions about halting, equivalence, optimization, and so on are intractable even for very simple programming languages.
The relationship of MIS steering committees to size of firm and formalization of MIS planning
Authors: Doll William J. , Torkzadeh Golamreza
Published: July 2002

Top-level management and directors of management information systems (MIS) have been urged to oversee information systems (IS) development efforts using MIS steering committees. Although such committees have been shown to assist with planning problems facing the MIS director, little is known about just how such committees relate to the planning process. Drawing on organizational theory literature, a conceptual model is presented that relates firm size and MIS steering committees to four IS planning practices. The results of this survey of 456 MIS directors suggest that use of an MIS steering committee is associated with more formalized and systematic MIS planning. However, some of these relationships are stronger in large firms.
Computing multi-colored polygonal masks in pipeline architecture and its application to automated visual inspection
Authors: Sanz Jorge L. C. , Dinstein Its'hak , Petkovic Dragutin
Published: July 2002

New techniques for computing multicolored polygonal masks for image analysis and computer vision applications are presented. The procedures do not require random access of the image memory. They are based on efficient generation of coordinate-reference images (ramps) and other simple general purpose architectural features such as look-up tables. The techniques presented are, unlike their predecessors, highly parallel and can be efficiently implemented in existing pipeline image processors. In addition, we show an architecture in the form of functional building blocks that will enable us to compute polygonal and other masks much faster than commercially available pipeline systems. Extensive motivation and use of the new algorithms for digital visual inspection applications are given throughout.
A subdivision-based algorithm for the sparse resultant
Authors: Canny John F. , Emiris Ioannis Z.
Published: July 2002

Multivariate resultants generalize the Sylvester resultant of two polynomials and characterize the solvability of a polynomial system. They also reduce the computation of all common roots to a problem in linear algebra. We propose a determinantal formula for the sparse resultant of an arbitrary system of
n
+ 1 polynomials in
n
variables. This resultant generalizes the classical one and has significantly lower degree for polynomials that are sparse in the sense that their mixed volume is lower than their Bézout number. Our algorithm uses a mixed polyhedral subdivision of the Minkowski sum of the Newton polytopes in order to construct a Newton matrix. Its determinant is a nonzero multiple of the sparse resultant and the latter equals the GCD of at most
n
+ 1 such determinants. This construction implies a restricted version of an effective sparse Nullstellensatz. For an arbitrary specialization of the coefficients, there are two methods that use one extra variable and yield the sparse resultant. This is the first algorithm to handle the general case with complexity polynomial in the resultant degree and simply exponential in
n
. We conjecture its extension to producing an exact rational expression for the sparse resultant.
Final examination scheduling
Authors: Broder Sol
Published: July 2002

A method for scheduling final examinations to yield a minimal number of student conflicts is described. The “minimization” is achieved by repetitively evaluating a nonlinear set of equations. Imbedded in the process is a random or Monte Carlo selection of assignments. As in such heuristic techniques, the solution may not be optimum and many solutions may be found which yield locally minimal results. Computer programs are described and empirical results given.
An information-theoretic approach to text searching in direct access systems
Authors: Barton Ian J. , Creasey Susan E. , Lynch Michael F. , Snell Michael J.
Published: July 2002

Using direct access computer files of bibliographic information, an attempt is made to overcome one of the problems often associated with information retrieval, namely, the maintenance and use of large dictionaries, the greater part of which is used only infrequently. A novel method is presented, which maps the hyperbolic frequency distribution of text characteristics onto a rectangular distribution. This is more suited to implementation on storage devices.

This method treats text as a string of characters rather than words bounded by spaces, and chooses subsets of strings such that their frequencies of occurrence are more even than those of word types. The members of this subset are then used as index keys for retrieval. The rectangular distribution of key frequencies results in a much simplified file organization and promises considerable cost advantages.
The working set model for program behavior
Authors: Denning Peter J.
Published: July 2002

Probably the most basic reason behind the absence of a general treatment of resource allocation in modern computer systems is an adequate model for program behavior. In this paper a new model, the “working set model,” is developed. The working set of pages associated with a process, defined to be the collection of its most recently used pages, provides knowledge vital to the dynamic management of paged memories. “Process” and “working set” are shown to be manifestations of the same ongoing computational activity; then “processor demand” and “memory demand” are defined; and resource allocation is formulated as the problem of balancing demands against available equipment.
The economics of designing generalized software
Authors: Milne Frank , Weber Ron
Published: July 2002

The choice of the attributes to be incorporated in a generalized software package is a complex design task, much like the choice of the characteristics of the basic model and the options to be offered when a new automobile is being designed. Some empirical evidence available suggests that the choices made by generalized software designers are not always well founded; for example, some functions included in the software are hardly, if ever, used, while functions that would be used extensively are not available. To assist the designer, we formulate a market model showing the interactions between the producers (designers) of generalized software and the consumers (users) of generalized software. The model provides insight into those factors that affect the demand for a package and the variables to be considered in a profit-maximizing decision.
Control flow and data structure documentation
Authors: Shneiderman Ben
Published: July 2002

Two experiments were carried out to assess the utility of external documentation aids such as macro flowcharts, pseudocode, data structure diagrams, and data structure descriptions. A 223 line Pascal program which manipulates four arrays was used. The program interactively handles commands that allow the user to manage five lists of items. A comprehension test was given to participants along with varying kinds of external documentation. The results indicate that for this program the data structure information was more helpful than the control flow information, independently of whether textual or graphic formats were used.
A user-friendly software environment for the novice programmer
Authors: Eisenstadt Marc
Published: July 2002

SOLO,
a nonnumerical programming language, was developed at The Open University in the U.K. to support a course on Cognitive Psychology. It was designed to acquaint students as painlessly as possible with the computing fundamentals necessary both to grasp
AI
principles as applied in Cognitive Psychology and to actually initiate fairly sophisticated exercises on their own. The language has been used successfully by more than 2500 social science students.
Designing computer system messages
Authors: Shneiderman Ben
Published: July 2002

tive computer systems and studies of their users, we have become increasingly aware of the importance of system messages. Novice users are unimpressed with CPU speeds, disk storage capabilities, or elegant file structures. For them, the system appears only in the form of the messages on their screens or printers. So when novices encounter violent messages such as “FATAL ERROR, RUN ABORTED”, vague phases like “ILLEGAL CMD”, or obscure codes such as “OC7” or “IEH2191”, they are understandably shaken, confused, dismayed, and discouraged from continuing. The negative image that computer systems sometimes generate is, we believe, largely due to the difficulties users experience when they make mistakes or are unsure about what to do next.
Updating a master file—yet one more time
Authors: Inglis J.
Published: July 2002

For several years I have been teaching a file updating algorithm which is essentially the same as that in Dwyer's admirable paper [1]. There is one unjustified objection to the algorithm that perceptive students and people with batch processing experience almost invariably raise and which is not addressed by Dwyer. The objection is based on a situation which arises in a batch processing environment with several users, where key-ordered sequential update is used.
Analysis of future event set algorithms for discrete event simulation
Authors: McCormack William M. , Sargent Robert G.
Published: July 2002

New analytical and empirical results for the performance of future event set algorithms in discrete event simulation are presented. These results provide a clear insight to the factors affecting algorithm performance, permit evaluation of the hold model, and determine the best algorithm(s) to use. The analytical results include a classification of distributions for efficient insertion scanning of a linear structure. In addition, it is shown that when more than one distribution is present, there is generally an increase in the probability that new insertions will have smaller times than those in the future event set. Twelve algorithms, including most of those recently proposed, were empirically evaluated using primarily simulation models. Of the twelve tested, four performed well, three performed fairly, and five performed poorly.
A virtual operating system
Authors: Hall Dennis E. , Scherrer Deborah K. , Sventek Joseph S.
Published: July 2002

Moving to a new system is costly and error-prone. The problem can be reduced through use of a virtual operating system that disentangles computing environments from their underlying operating systems. The authors report on their successful experience in doing this and achieving inter-system uniformity at all three levels of user interface: virtual machine, utilities, and command language.
Optimal program and data locations in computer networks
Authors: Morgan Howard L. , Levin K. Dan
Published: July 2002

An optimization procedure for the allocation of program and data files in a computer network is presented. This algorithm takes into account the dependencies between files and programs such as occur in real heterogeneous computer networks. Insights into whether or not to convert programs from one computer to another can also be gained from the model. A search procedure for the file location problem is described, along with an example and a possible application of the model.
Multiprocessor memory organization and memory interference
Authors: Smith Alan Jay
Published: July 2002

ture of shared memory in a multiprocessor computer system is examined with particular attention to noninterleaved memory. Alternative memory organizations are compared and it is shown that a home memory organization, in which each processor is associated with one or more memories in which its address space is concentrated, is quite effective in reducing memory interference. Home memory organization is shown to be particularly suited to certain specialized computational problems as well as to possess advantages in terms of interference and reliability for general purpose computation. Results for interleaved memory are drawn from previous work and are used for comparison. Trace-driven simulations are used to verify the conclusions of the analysis.
A study of line overhead in the Arpanet
Authors: Kleinrock Leonard , Naylor William E. , Opderbeck Holger
Published: July 2002

The form, extent, and effect of the communication line overhead in the ARPANET are considered. The source of this overhead is separated into various levels of protocol hierarchy and the characteristics of each level are summarized. Then the line efficiency for various models of system use is studied. Some measurements of line efficiency for the ARPANET are presented and by extrapolation these measurements are used to anticipate overhead in a heavily loaded network. Similar results are derived for a recently proposed network protocol and compared with those for the current system.
Security Kernel validation in practice
Authors: Millen Jonathan K.
Published: July 2002

A security kernel is a software and hardware mechanism that enforces access controls within a computer system. The correctness of a security kernel on a PDP-11/45 is being proved. This paper describes the technique used to carry out the first step of the proof: validating a formal specification of the program with respect to axioms for a secure system.
Referencing lists by an edge
Authors: Wise David S.
Published: July 2002

An edge reference into a list structure is a pair of pointers to adjacent nodes. Such a reference often requires little additional space, but its use can yield efficient algorithms. For instance, a circular link between the ends of a list is redundant if the list is always referenced by that edge, and list traversal is easier when that link is null. Edge references also allow threading of nonrecursive lists, can replace some header, cells, and enhance the famous exclusive-or trick to double-link lists.
Analysis and performance of inverted data base structures
Authors: Cárdenas Alfonso F.
Published: July 2002

The need to envision and architecture data base systems in a hierarchical level by level framework is stressed. The inverted data base (file) organization is then analyzed, considering implementation oriented aspects. The inverted directory is viewed realistically as another large data base which itself is subjected to inversion. Formulations are derived to estimate average access time (read only) and storage requirements, formalizing the interaction of data base content characteristics, logical complexity of queries, and machine timing and blocking specifications identified as having a first-order effect on performance. The formulations presented are necessary to be used in conjunction with any index selection criteria to determine the optimum set of index keys.
Indirect threaded code
Authors: Dewar Robert B. K.
Published: July 2002

An efficient arrangement for interpretive code is described. It is related to Bell's notion of threaded code but requires less space and is more amenable to machine independent implementations.
Consecutive storage of relevant records with redundancy
Authors: Ghosh Sakti P.
Published: July 2002

This paper studies the properties of a new class of file organizations (CRWR) where records relevant to every query are stored in consecutive storage locations but the organizations contain redundancy. Some theorems which provide tools for reducing redundancy in CRWR organizations have been also developed. Redundancies obtained by the application of these theorems are compared with that of query-inverted file organizations. Some CRWR organizations with minimum redundancy have also been developed for queries which specify sets of keys.
A fast and usually linear algorithm for global flow analysis (abstract only)
Authors: Graham Susan L. , Wegman Mark
Published: July 2002

ible graphs is presented. The algorithm is shown to treat a very general class of function spaces. For a graph of e edges, the algorithm has a worst case time bound of O(e log e) function operations. It is also shown that in programming terms, the number of operations is proportional to e plus the number of exits from program loops. Consequently a restriction to one-entry one-exit control structures guarantees linearity. The algorithm can be extended to yet larger classes of function spaces and graphs by relaxing the time bound. Examples are given of code improvement problems which can be solved using the algorithm.
TENEX, a paged time sharing system for the PDP - 10
Authors: Bobrow Daniel G. , Burchfiel Jerry D. , Murphy Daniel L. , Tomlinson Raymond S.
Published: July 2002

TENEX is a new time sharing system implemented on a DEC PDP-10 augmented by special paging hardware developed at BBN. This report specifies a set of goals which are important for any time sharing system. It describes how the TENEX design and implementation achieve these goals. These include specifications for a powerful multiprocess large memory virtual machine, intimate terminal interaction, comprehensive uniform file and I/O capabilities, and clean flexible system structure. Although the implementation described here required some compromise to achieve a system operational within six months of hardware checkout, TENEX has met its major goals and provided reliable service at several sites and through the ARPA network.
An environment for research in microprogramming and emulation
Authors: Rosin Robert F. , Frieder Gideon , Eckhouse Richard H.
Published: July 2002

The development of the research project in microprogramming and emulation at State University of New York at Buffalo consisted of three phases: the evaluation of various possible machines to support this research; the decision to purchase one such machine, which appears to be superior to the others considered; and the organization and definition of goals for each group in the project. Each of these phases is reported, with emphasis placed on the early results achieved in this research.
Trace-driven modeling and analysis of CPU scheduling in a multiprogramming system
Authors: Sherman Stephen , Baskett Forest , Browne J. C.
Published: July 2002

Microscopic level job stream data obtained in a production environment by an event-driven software probe is used to drive a model of a multiprogramming computer system. The CPU scheduling algorithm of the model is systematically varied. This technique, called trace-driven modeling, provides an accurate replica of a production environment for the testing of variations in the system. At the same time alterations in scheduling methods can be easily carried out in a controlled way with cause and effects relationships being isolated. The scheduling methods tested included the best possible and worst possible methods, the traditional methods of multiprogramming theory, round-robin, first-come-first-served, etc., and dynamic predictors. The relative and absolute performances of these scheduling methods are given. It is concluded that a successful CPU scheduling method must be preemptive and must prevent a given job from holding the CPU for too long a period.
The design, implementation, and evaluation of a working set dispatcher
Authors: Rodriguez-Rosell Juan , Dupuy Jean-Pierre
Published: July 2002

The behavior of a computer system is largely dependent upon the algorithms employed to allocate the system resources to the processes competing for them. Recent research in time-sharing paging systems has developed the working set model for program behavior, and a resource allocation strategy based on this model has been proposed. Two implementations along these principles have been reported, but it seems that in neither case have further results been announced. This report discusses the design and implementation of a dispatcher based on the working set principle, presents data to permit analysis of its behavior, and indicates future directions of research on methods of controlling a computer system.