bluuebunny/crossref_metadata_2025 huggingface dataset:
A probabilistic relational algebra for the integration of information retrieval and database systems
Authors: Fuhr Norbert , Rölleke Thomas
Published: July 2002

We present a probabilistic relational algebra (PRA) which is a generalization of standard relational algebra. In PRA, tuples are assigned probabilistic weights giving the probability that a tuple belongs to a relation. Based on intensional semantics, the tuple weights of the result of a PRA expression always conform to the underlying probabilistic model. We also show for which expressions extensional semantics yields the same results. Furthermore, we discuss complexity issues and indicate possibilities for optimization. With regard to databases, the approach allows for representing imprecise attribute values, whereas for information retrieval, probabilistic document indexing and probabilistic search term weighting can be modeled. We introduce the concept of vague predicates which yield probabilistic weights instead of Boolean values, thus allowing for queries with vague selection conditions. With these features, PRA implements uncertainty and vagueness in combination with the relational model.
A text compression scheme that allows fast searching directly in the compressed file
Authors: Manber Udi
Published: July 2002

A new text compression scheme is presented in this article. The main purpose of this scheme is to speed up string matching by searching the compressed file directly. The scheme requires no modification of the string-matching algorithm, which is used as a black box; any string-matching procedure can be used. Instead, the
pattern
is modified; only the outcome of the matching of the modified pattern against the compressed file is decompressed. Since the compressed file is smaller than the original file, the search is faster both in terms of I/O time and precessing time than a search in the original file. For typical text files, we achieve about 30% reduction of space and slightly less of search time. A 30% space saving is not competitive with good text compression schemes, and thus should not be used where space is the predominant concern. The intended applications of this scheme are files that are searched often, such as catalogs, bibliographic files, and address books. Such files are typically not compressed, but with this scheme they can remain compressed indefinitely, saving space while allowing faster search at the same time. A particular application to an information retrieval system that we developed is also discussed.
AGENTS
Authors: Moreira Dilvan de Abreu , Walczowski Les T.
Published: July 2002

The AGENTS system is a set of programs designed to generate automatically the mask-level layout of full custom CMOS, BICMOS, and bipolar leaf cells. The system is formed from four sever programs: the placer, router, database, and broker.

The placer places components in a cell, the router wires the circuits sent to it, the database stores all the information that is dependent upon the fabrication process, such as the design rules, and the Broker makes the services of the other servers available.

These servers communicate over a computer network using the TCP/IP Internet Protocol. The Placer server receives from its client the description and netlist of the circuit to be generated using EDIF (Electronic Design Interchange Format.) The output to its client is the
mask layout of the circuit, again codified in EDIF. The comcept of agents as software components which have the ability to communicate and cooperate with each other is at the heart of the AGENTS system. This concept is not only used at the higher level, for the four servers, but at a lower level as well, inside the Router and Placer servers, where small relatively simple agents work together to accomplish complex tasks. These small agents are responsible for all the reasoning carried out by the two servers, as they hold the basic inference routines and the knowledge needed by the servers. The system's philosophy is that competence should emerge out of the collective behavior of a large number of relatively simple agents. In addition and integrated to these small agents, the system uses a genetic algorithm to improve components' placement before routing.
From programming language design to computer construction
Authors: Wirth Niklaus
Published: July 2002

From NELIAC (via ALGOL 60) to Euler and ALGOL W, to Pascal and Modula-2, and ultimately Lilith, Wirth's search for an appropriate formalism for systems programming yields intriguing insights and surprising results.
A semidiscrete matrix decomposition for latent semantic indexing information retrieval
Authors: Kolda Tamara G. , O'Leary Dianne P.
Published: July 2002

The vast amount of textual information available today is useless unless it can be effectively and efficiently searched. The goal in information retrieval is to find documents that are relevant to a given user query. We can represent and document collection by a matrix whose (
i, j)
entry is nonzero only if the
i
th term appears in the
j
th document; thus each document corresponds to a columm vector. The query is also represented as a column vector whose
i
th term is nonzero only if the
i
th term appears in the query. We score each document for relevancy by taking its inner product with the query. The highest-scoring documents are considered the most relevant. Unfortunately, this method does not necessarily retrieve all relevant documents because it is based on literal term matching. Latent semantic indexing (LSI) replaces the document matrix with an approximation generated by the truncated singular-value decomposition (SVD). This method has been shown to overcome many difficulties associated with literal term matching. In this article we propose replacing the SVD with the semidiscrete decomposition (SDD). We will describe the SDD approximation, show how to compute it, and compare the SDD-based LSI method to the SVD-based LSI methods. We will show that SDD-based LSI does as well as SVD-based LSI in terms of document retrieval while requiring only one-twentieth the storage and one-half the time to compute each query. We will also show how to update the SDD approximation when documents are added or deleted from the document collection.
C++ classes for linking optimization with complex simulations
Authors: Gockenbach Mark S. , Petro Matthew J. , Symes William W.
Published: July 2002

The object-oriented programming paradigm can be used to overcome the incompatibilities between off-the-shelf optimization software and application software. The Hilbert Class Library (HCL) defines the fundamental mathematical objects arising in optimization problems, such as vectors, linear operators, and so forth, as C++ classes, making it possible to write optimization code in a natural fashion, while allowing application software such as simulators to use the most convenient data structures and programming style. In spite of the poor reputation C++ has for runtime performance, the use of mixed-language programming allows performance equal to that achieved by standard Fortran packages, as comparisons with the popular code LBFGS and ARPACK demonstrate.
On optimistic methods for concurrency control
Authors: Kung H. T. , Robinson John T.
Published: July 2002

Most current approaches to concurrency control in database systems rely on locking of data objects as a control mechanism. In this paper, two families of nonlocking concurrency controls are presented. The methods used are “optimistic” in the sense that they rely mainly on transaction backup as a control mechanism, “hoping” that conflicts between transactions will not occur. Applications for which these methods should be more efficient than locking are discussed.
On interpretations of relational languages and solutions to the implied constraint problem
Authors: Jacobs Barry E. , Klug Anthony C. , Aronson Alan R.
Published: July 2002

The interconnection between conceptual and external levels of a relational database is made precise in terms of the notion of “interpretation” between first-order languages. This is then used to obtain a methodology for discovering constraints at the external level that are “implied” by constraints at the conceptual level and by conceptual-to-external mappings. It is also seen that these concepts are important in other database issues, namely, automatic program conversion, database design, and compile-time error checking of embedded database languages. Although this the deals exclusively with the relational approach, it also discusses how these ideas can be extended to hierarchical and network databases.
Performance enhancements to a relational database system
Authors: Stonebraker Michael , Woodfill John , Ranstrom Jeff , Murphy Marguerite , Meyer Marc , Allman Eric
Published: July 2002

In this paper we examine four performance enhancements to a database management system: dynamic compilation, microcoded routines, a special-purpose file system, and a special-purpose operating system. All were examined in the context of the INGRES database management system. Benchmark timings that are included suggest the attractiveness of dynamic compilation and a special-purpose file system. Microcode and a special-purpose operating system are analyzed and appear to be of more limited utility in the INGRES context.
Developing a natural language interface to complex data
Authors: Hendrix Gary G. , Sacerdoti Earl D. , Sagalowicz Daniel , Slocum Jonathan
Published: July 2002

Aspects of an intelligent interface that provides natural language access to a large body of data distributed over a computer network are described. The overall system architecture is presented, showing how a user is buffered from the actual database management systems (DBMSs) by three layers of insulating components. These layers operate in series to convert natural language queries into calls to DBMSs at remote sites. Attention is then focused on the first of the insulating components, the natural language system. A pragmatic approach to language access that has proved useful for building interfaces to databases is described and illustrated by examples. Special language features that increase system usability, such as spelling correction, processing of incomplete inputs, and run-time system personalization, are also discussed. The language system is contrasted with other work in applied natural language processing, and the system's limitations are analyzed.
On the encipherment of search trees and random access files
Authors: Bayer R. , Metzger J. K.
Published: July 2002

The securing of information in indexed, random access files by means of privacy transformations must be considered as a problem distinct from that for sequential files. Not only must processing overhead due to encrypting be considered, but also threats to encipherment arising from updating and the file structure itself must be countered. A general encipherment scheme is proposed for files maintained in a paged structure in secondary storage. This is applied to the encipherment of indexes organized as
B
-trees; a
B
-tree is a particular type of multiway search tree. Threats to the encipherment of
B
-trees, especially relating to updating, are examined, and countermeasures are proposed for each. In addition, the effect of encipherment on file access and update, on paging mechanisms, and on files related to the enciphered index are discussed. Many of the concepts presented may be readily transferred to other forms of multiway index trees and to binary search trees.
Information-Theoretic Limitations of Formal Systems
Authors: Chaitin Gregory J.
Published: July 2002

An attempt is made to apply information-theoretic computational complexity to meta-mathematics. The paper studies the number of bits of instructions that must be given to a computer for it to perform finite and infinite tasks, and also the time it takes the computer to perform these tasks. This is applied to measuring the difficulty of proving a given set of theorems, in terms of the number of bits of axioms that are assumed, and the size of the proofs needed to deduce the theorems from the axioms.
A Space-Economical Suffix Tree Construction Algorithm
Authors: McCreight Edward M.
Published: July 2002

A new algorithm is presented for constructing auxiliary digital search trees to aid in exact-match substring searching. This algorithm has the same asymptotic running time bound as previously published algorithms, but is more economical in space. Some implementation considerations are discussed, and new work on the modification of these search trees in response to incremental changes in the strings they index (the update problem) is presented.
Lower Bounds on Information Transfer in Distributed Computations
Authors: Abelson Harold
Published: July 2002

Lower bounds on the interprocessor communication required for computing a differentiable real-valued function in a distributed network are derived. These bounds are independent of the network interconnection configuration, and they impose no assumptions other than differentiability constraints on the computations performed by individual processors. As a sample application, lower bounds on information transfer in the distributed computation of some-typical matrix operations are exhibited.
Improving database design through the analysis of relationships
Authors: Dey Debabrata , Storey Veda C. , Barron Terence M.
Published: July 2002

Much of the work on conceptual modeling involves the use of an entity-relationship model in which binary relationships appear as associations between two entities. Relationships involving more than two entities are considered rare and, therefore, have not received adequate attention. This research provides a general framework for the analysis of relationships in which binary relationships simply become a special case. The framework helps a designer to identify ternary and other higher-degree relationships that are commonly represented, often inappropriately, as either entities or binary relationships. Generalized rules are also provided for representing higher-degree relationships in the relational model. This uniform treatment of relationships should significantly ease the burden on a designer by enabling him or her to extract more information from a real-world situation and represent it properly in a conceptual design.
A brief history of cellular automata
Authors: Sarkar Palash
Published: July 2002

Cellular automata are simple models of computation which exhibit
fascinatingly complex behavior. They have captured the attention of several generations of researchers, leading to an extensive body of work. Here we trace a history of cellular automata from their beginnings with von Neumann to the present day. The emphasis is mainly on topics closer to computer science and mathematics rather than physics, biology or other applications. The work should be of interest to both new entrants into the field as well as researchers working on particular aspects of cellular automata.
Exploiting space and location as a design framework for interactive mobile systems
Authors: Dix Alan , Rodden Tom , Davies Nigel , Trevor Jonathan , Friday Adrian , Palfreyman Kevin
Published: July 2002

This article considers the importance of context in mobile systems. It considers a range of context-related issues and focus on location as a key issue for mobile systems. A design framework is described consisting of taxonomies of location, mobility, population, and device awareness. The design framework inorms the construction of a semantic model of space for mobile systems. The semantic model is reflected in a computational model built on a distriuted platform that allows contextual information to be shared across a number of mobile devices. The framework support the design of interactive mobile systems while the platform supports their rapid development.
The structure of “THE”-multiprogramming system
Authors: Dijkstra Edsger W.
Published: July 2002

A multiprogramming system is described in which all activities are divided over a number of sequential processes. These sequential processes are placed at various hierarchical levels, in each of which one or more independent abstractions have been implemented. The hierarchical structure proved to be vital for the verification of the logical soundness of the design and the correctness of its implementation.
A relational model of data for large shared data banks
Authors: Codd E. F.
Published: July 2002

Future users of large data banks must be protected from having to know how the data is organized in the machine (the internal representation). A prompting service which supplies such information is not a satisfactory solution. Activities of users at terminals and most application programs should remain unaffected when the internal representation of data is changed and even when some aspects of the external representation are changed. Changes in data representation will often be needed as a result of changes in query, update, and report traffic and natural growth in the types of stored information.

Existing noninferential, formatted data systems provide users with tree-structured files or slightly more general network models of the data. In Section 1, inadequacies of these models are discussed. A model based on
n
-ary relations, a normal form for data base relations, and the concept of a universal data sublanguage are introduced. In Section 2, certain operations on relations (other than logical inference) are discussed and applied to the problems of redundancy and consistency in the user's model.
Remote office work
Authors: Olson Margrethe H.
Published: July 2002

Remote work refers to organizational work that is performed outside of the normal organizational confines of space and time. The term telecommuting refers to the substitution of communications capabilities for travel to a central work location. Office automation technology permits many office workers to be potential telecommuters in that their work can be performed remotely with computer and communications support. This paper examines some behavioral, organizational, and social issues surrounding remote work, particularly work at home.

An exploratory study was conducted of 32 organizational employees who were working at home. Important characteristics of jobs that can be performed at home were: minimum physical requirements, individual control over work pace, defined deliverables, a need for concentration, and a relatively low need for communication. The individuals who worked at home successfully were found to be highly self-motivated and self-disciplined and to have skills which provided them with bargaining power. They also made the arrangement either because of family requirements or because they preferred few social contacts beyond family.
On the inevitable intertwining of specification and implementation
Authors: Swartout William , Balzer Robert
Published: July 2002

Contrary to recent claims that specification should be completed before implementation begins, this paper presents two arguments that the two processes must be intertwined. First, limitations of available implementation technology may force a specification change. For example, deciding to implement a stack as an array (rather than as a linked list) may impose a fixed limit on the depth of the stack. Second, implementation choices may suggest augmentations to the original specification. For example, deciding to use an existing pattern-match routine to implement the search command in an editor may lead to incorporating some of the routine's features into the specification, such as the ability to include wild cards in the search key. This paper elaborates these points and illustrates how they arise in the specification of a controller for a package router.
Password security
Authors: Morris Robert , Thompson Ken
Published: July 2002

This paper describes the history of the design of the password security scheme on a remotely accessed time-sharing system. The present design was the result of countering observed attempts to penetrate the system. The result is a compromise between extreme security and ease of use.
Secure communications over insecure channels
Authors: Merkle Ralph C.
Published: July 2002

According to traditional conceptions of cryptographic security, it is necessary to transmit a key, by secret means, before encrypted massages can be sent securely. This paper shows that it is possible to select a key over open communications channels in such a fashion that communications security can be maintained. A method is described which forces any enemy to expend an amount of work which increases as the square of the work required of the two communicants to select the key. The method provides a logically new kind of protection against the passive eavesdropper. It suggests that further research on this topic will be highly rewarding, both in a theoretical and a practical sense.
Generating beta variates with nonintegral shape parameters
Authors: Cheng R. C. H.
Published: July 2002

A new rejection method is described for generating beta variates. The method is compared with previously published methods both theoretically and through computer timings. It is suggested that the method has advantages in both speed and programming simplicity over previous methods, especially for “difficult” combinations of parameter values.
Automated welfare client-tracking and service integration
Authors: Kling Rob
Published: July 2002

The impacts of an automated client-tracking system on the clients, caseworkers, administrators, and operations of the welfare agencies that use it are reported. The major impact of this system was to enhance the administrative attractiveness of the using agencies in the eyes of funders rather than to increase their internal administrative efficiency. This impact is a joint product of both the technical features of the computer-based system and of the organizational demands placed upon different agencies, administrators, and caseworkers. It illustrates the way “successful” automated information systems fit the political economies of the groups that use them.
Improved event-scanning mechanisms for discrete event simulation
Authors: Wyman F. Paul
Published: July 2002

Simulation models of large, complex “real-world” applications have occasionally earned the reputation of eating up hours of computer time. This problem may be attributed in part to difficulties such as slow stochastic convergence. However, an additional problem lies in the fact that a significant amount of bookkeeping time is required to keep future events in their proper sequence. This paper presents a method for significantly reducing the time spent scanning future events lists in discrete event simulations. Three models are presented, all of which improve in effectiveness as the events-list scan problem becomes more burdensome.
Scanned-display computer graphics
Authors: Noll A. Michael
Published: July 2002

A television-like scanned-display system has been successfully implemented on a Honeywell DDP-224 computer installation. The scanned image is stored in the core memory of the computer, and software scan conversion is used to convert the rectangular coordinates of a point to the appropriate word and bit in an output display array in core storage. Results thus far indicate that flicker-free displays of large amounts of data are possible with reasonably fast graphical interaction. A scanned image of size 240 X 254 points is displayed at a 30 frame-per-second rate.
Verifying security protocols with Brutus
Authors: Clarke E. M. , Jha S. , Marrero W.
Published: July 2002

Due to the rapid growth of the “Internet” and the
“World Wide Web” security has become a very important concern in the design and implementation of software systems. Since security has become an important issue, the number of protocols in this domain has become very large. These protocols are very diverse in nature. If a software architect wants to deploy some of these protocols in a system, they have to be sure that the protocol has the right properties as dictated by the requirements of the system. In this article we present BRUTUS, a tool for verifying properties of security protocols. This tool can be viewed as a special-purpose model checker for security protocols. We also present reduction techniques that make the tool efficient. Experimental results are provided to demonstrate the efficiency of BRUTUS.
TRAC, a procedure-describing language for the reactive typewriter
Authors: Mooers Calvin N.
Published: July 2002

A description of the TRAC (Text Reckoning And Compiling) language and processing algorithm is given. The TRAC language was developed as the basis of a software package for the reactive typewriter. In the TRAC language, one can write procedures for accepting, naming and storing any character string from the typewriter; for modifying any string in any way; for treating any string at any time as an executable procedure, or as a name, or as text; and for printing out any string. The TRAC language is based upon an extension and generalization to character strings of the programming concept of the “macro.” Through the ability of TRAC to accept and store definitions of procedures, the capabilities of the language can be indefinitely extended. TRAC can handle iterative and recursive procedures, and can deal with character strings, integers and Boolean vector variables.
Person-matching by electronic methods
Authors: Phillips William , Bahn Anita K. , Miyasaki Mabel
Published: July 2002

Record linkage in the updating of files is accomplished in many establishments through the use of a preassigned number, such as payroll number, customer number, or social security number. In vital and health records, however, a unique number is generally not preassigned to an individual for purposes of reporting services received to the health department. In order to determine whether different physician reports refer to the same individual, name and other identification must be compared. This is a laborious operation which is subject to various errors because of name misspellings, changes of name upon marriage, and other problems.

We are interested in the maintenance of a psychiatric case register in Maryland, where many of the reports from over a hundred psychiatric agencies refer to the same patient. These records must be linked in order to provide unduplicated counts of individuals under care and longitudinal records of psychiatric history. An earlier paper [1] describes our general procedures for register maintenance by use of a digital computer (Honeywell 800). Here we present in more detail our initial procedures for the person-matching process in order to elicit comments and suggestions from persons who have had experience in matching.
An analysis of the Burrows—Wheeler transform
Authors: Manzini Giovanni
Published: July 2002

The Burrows—Wheeler Transform (also known as Block-Sorting) is at the base of compression algorithms that are the state of the art in lossless data compression. In this paper, we analyze two algorithms that use this technique. The first one is the original algorithm described by Burrows and Wheeler, which, despite its simplicity outperforms the Gzip compressor. The second one uses an additional run-length encoding step to improve compression. We prove that the compression ratio of both algorithms can be bounded in terms of the
k
th order empirical entropy of the input string for any
k
≥ 0. We make no assumptions on the input and we obtain bounds which hold in the worst case that is for every possible input string. All previous results for Block-Sorting algorithms were concerned with the average compression ratio and have been established assuming that the input comes from a finite-order Markov source.
Rethinking the design of the Internet
Authors: Blumenthal Marjory S. , Clark David D.
Published: July 2002

This article looks at the Internet and the changing set of requirements for the Internet as it becomes more commercial, more oriented toward the consumer, and used for a wider set of purposes. We discuss a set of principles that have guided the design of the Internet, called the
end-to-end arguments,
and we conclude that there is a risk that the range of new requirements now emerging could have the consequence of compromising the Internet's original design principles. Were this to happen, the Internet might lose some of its key features, in particular its ability to support new and unanticipated applications. We link this possible outcome to a number of trends: the rise of new stakeholders in the Internet, in particular Internet service providers; new government interests; the changing motivations of a growing user base; and the tension between the demand for trustworthy overall operation and the inability to trust the behavior of individual users.
Database design: composing fully normalized tables from a rigorous dependency diagram
Authors: Smith Henry C.
Published: July 2002

A new simplified methodology for relational-database design overcomes the difficulties associated with nonloss decomposition. It states dependencies between data fields on a dependency list and then depicts them unambiguously as interlinked bubbles and doublebubbles on a dependency diagram. From the dependency diagram, a set of fully normalized tables is derived.
An insertion algorithm for a minimal internal path length binary search tree
Authors: Gerasch Thomas E.
Published: July 2002

This paper presents an insertion algorithm for maintaining a binary search tree with minimal internal path length. The insertion algorithm maintains minimal internal path length by displacing keys when necessary, in an inorder fashion, until a vacant position is found in the last incomplete level of the tree. The algorithm produces trees that are optimal for searching while exhibiting a runtime behavior that is between logarithmic and linear in the number of nodes in the tree, with linear time being its worst-case behavior.
System architectures for computer music
Authors: Gordon John W.
Published: July 2002

Computer music is a relatively new field. While a large proportion of the public is aware of computer music in one form or another, there seems to be a need for a better understanding of its capabilities and limitations in terms of synthesis, performance, and recording hardware. This article addresses that need by surveying and discussing the architecture of existing computer music systems.

System requirements vary according to what the system will be used for. Common uses for computer music systems include composition, performance, research, home entertainment, and studio recording/mixing. This paper outlines system components with this wide diversity of possible uses in mind.

Current synthesis and analysis techniques, and the different way in which these techniques can be implemented in special-purpose hardware, are comprehensively reviewed. Design specifications are given for certain digital-to-analog (and analog-to-digital) converters, disk interfaces, system organization, control hardware and software, and numerical precision.

Several synthesis systems are described in detail, with an emphasis on theoretical developments and innovative design. Commercial synthesizers and other architectures are also briefly mentioned.
Improving locality of reference in a garbage-collecting memory management system
Authors: Courts Robert
Published: July 2002

Modern Lisp systems make heavy use of a garbage-collecting style of memory management. Generally, the locality of reference in garbage-collected systems has been very poor. In virtual memory systems, this poor locality of reference generally causes a large amount of wasted time waiting on page faults or uses excessively large amounts of main memory. An adaptive memory management algorithm, described in this article, allows substantial improvement in locality of reference. Performance measurements indicate that page-wait time typically is reduced by a factor of four with constant memory size and disk technology. Alternately, the size of memory typically can be reduced by a factor of two with constant performance.
The Myth of the Boundaryless Organization
Authors: Newell Sue , Pan Shan L. , Galliers Robert D. , Huang Jimmy C.
Published: July 2002

Technology does not make cultural and business boundaries disappear simply because it exists.
An extension of the relational data model to incorporate ordered domains
Authors: Ng Wilfred
Published: July 2002

We extend the relational data model to incorporate partial orderings into data domains, which we call the ordered relational model. Within the extended model, we define the partially ordered relational algebra (the PORA) by allowing the ordering predicate ⊑ to be used in formulae of the selection operator (σ). The PORA expresses exactly the set of all possible relations that are invariant under order-preserving automorphism of databases. This result characterizes the expressiveness of the PORA and justifies the development of Ordered SQL (OSQL) as a query language for ordered databases. OSQL provides users with the capability of capturing the semantics of ordered data in many advanced applications, such as those having temporal or incomplete information. Ordered functional dependencies (OFDs) on ordered databases are studied, based on two possible extensions of domain orderings: pointwise ordering and lexicographical ordering. We present a sound and complete axiom system for OFDs in the first case and establish a set of sound and complete chase rules for OFDs in the second. Our results suggest that the implication problems for both cases of OFDs are decidable and that the enforcement of OFDs in ordered relations are practically feasible. In a wider perspective, the proposed model explores an important area of object-relational databases, since ordered domains can be viewed as a general kind of data type.
A combinatorial strongly polynomial algorithm for minimizing submodular functions
Authors: Iwata Satoru , Fleischer Lisa , Fujishige Satoru
Published: July 2002

This paper presents a combinatorial polynomial-time algorithm for minimizing submodular functions, answering an open question posed in 1981 by Grötschel, Lovász, and Schrijver. The algorithm employs a scaling scheme that uses a flow in the complete directed graph on the underlying set with each arc capacity equal to the scaled parameter. The resulting algorithm runs in time bounded by a polynomial in the size of the underlying set and the length of the largest absolute function value. The paper also presents a strongly polynomial version in which the number of steps is bounded by a polynomial in the size of the underlying set, independent of the function values.
Some optimal inapproximability results
Authors: Håstad Johan
Published: July 2002

We prove optimal, up to an arbitrary ε > 0, inapproximability results for Max-E
k
-Sat for
k
≥ 3, maximizing the number of satisfied linear equations in an over-determined system of linear equations modulo a prime
p
and Set Splitting. As a consequence of these results we get improved lower bounds for the efficient approximability of many optimization problems studied previously. In particular, for Max-E2-Sat, Max-Cut, Max-di-Cut, and Vertex cover.
Controllable morphing of compatible planar triangulations
Authors: Surazhsky Vitaly , Gotsman Craig
Published: July 2002

Two planar triangulations with a correspondence between the pair of vertex sets are compatible (
isomorphic
) if they are topologically equivalent. This work describes methods for morphing compatible planar triangulations with identical convex boundaries in a manner that guarantees compatibility throughout the morph. These methods are based on a fundamental representation of a planar triangulation as a matrix that unambiguously describes the triangulation. Morphing the triangulations corresponds to interpolations between these matrices.We show that this basic approach can be extended to obtain better control over the morph, resulting in valid morphs with various natural properties. Two schemes, which generate the linear trajectory morph if it is valid, or a morph with trajectories close to linear otherwise, are presented. An efficient method for verification of validity of the linear trajectory morph between two triangulations is proposed. We also demonstrate how to obtain a morph with a natural evolution of triangle areas and how to find a smooth morph through a given intermediate triangulation.
Runtime identification of cache conflict misses
Authors: Collins Jamison D. , Tullsen Dean M.
Published: July 2002

This paper describes the miss classification table, a simple mechanism that enables the processor or memory controller to identify each cache miss as either a conflict miss or a capacity (non-conflict) miss. The miss classification table works by storing part of the tag of the most recently evicted line of a cache set. If the next miss to that cache set has a matching tag, it is identified as a conflict miss. This technique correctly identifies 88% of misses.Several applications of this information are demonstrated, including improvements to victim caching, next-line prefetching, cache exclusion, and a pseudo-associative cache. This paper also presents the adaptive miss buffer (AMB), which combines several of these techniques, targeting each miss with the most appropriate optimization, all within a single small miss buffer. The AMB's combination of techniques achieves 16% better performance than any single technique alone.
Audience-specific online community design
Authors: Andrews Dorine C.
Published: July 2002

Not all people are easily drawn to the virtual community. Research indicates people of a certain age and lifestyle are indeed reluctant to interact online under any circumstances.
The mutual exclusion problem
Authors: Lamport Leslie
Published: July 2002

The theory developed in Part I is used to state the mutual exclusion problem and several additional fairness and failure-tolerance requirements. Four “distributed”
N
-process solutions are given, ranging from a solution requiring only one communication bit per process that permits individual starvation, to one requiring about
N
! communication bits per process that satisfies every reasonable fairness and failure-tolerance requirement that we can conceive of.
Self-organizing linear search
Authors: Hester J. H. , Hirschberg D. S.
Published: July 2002

Algorithms that modify the order of linear search lists are surveyed. First the problem, including assumptions and restrictions, is defined. Next a summary of analysis techniques and measurements that apply to these algorithms is given. The main portion of the survey presents algorithms in the literature with absolute analyses when available. The following section gives relative measures that are applied between two or more algorithms. The final section presents open questions.
Program style analysis: a natural by-product of program compilation
Authors: Redish K. A. , Smyth W. F.
Published: July 2002

Analyzing program style may be properly considered an integral part of program compilation—as successfully implemented in two style-analysis tools for Fortran 77: AUTOMARK and ASSESS. The authors look forward to the day when all major language compilers routinely provide a standard style-analysis vector for users to interpret as they see fit.
Computerization, productivity, and quality of work-life
Authors: Kraut Robert E. , Dumais Susan T. , Koch Susan
Published: July 2002

The impact of a computerized record system on the work lives of customer service representatives in a large utility company is examined. The results suggest alternate methods for thinking about and measuring technological impact.
The constituent object parser: syntactic structure matching for information retrieval
Authors: Metzler Douglas P. , Haas Stephanie W.
Published: July 2002

The Constituent Object Parser is a shallow syntactic parser designed to produce dependency tree representations of syntactic structure that can be used to specify the intended meanings of a sentence more precisely than can the key terms of the sentence alone. It is intended to improve the precision/recall performance of information retrieval and similar text processing applications by providing more powerful matching procedures. The dependency tree representation and the relationship between the intended use of this parser and its design is described, and several problems concerning the processing of ambiguous structures are discussed.
A logical design methodology for relational databases using the extended entity-relationship model
Authors: Teorey Toby J. , Yang Dongqing , Fry James P.
Published: July 2002

A database design methodology is defined for the design of large relational databases. First, the data requirements are conceptualized using an extended entity-relationship model, with the extensions being additional semantics such as ternary relationships, optional relationships, and the generalization abstraction. The extended entity-relationship model is then decomposed according to a set of basic entity-relationship constructs, and these are transformed into candidate relations. A set of basic transformations has been developed for the three types of relations: entity relations, extended entity relations, and relationship relations. Candidate relations are further analyzed and modified to attain the highest degree of normalization desired.

The methodology produces database designs that are not only accurate representations of reality, but flexible enough to accommodate future processing requirements. It also reduces the number of data dependencies that must be analyzed, using the extended ER model conceptualization, and maintains data integrity through normalization. This approach can be implemented manually or in a simple software package as long as a "good" solution is acceptable and absolute optimality is not required.
Comparing representations with relational and EER models
Authors: Batra D. , Hoffler J. A. , Bostrom R. P.
Published: July 2002

The diffusion of technology to end users who can now develop their own information systems raises issues concerning the cost, quality, efficiency, and accuracy of such systems.
Separating and collapsing results on the relativized probabilistic polynomial-time hierarchy
Authors: Ko Ker-I
Published: July 2002

The probabilistic polynomial-time hierarchy (BPH) is the hierarchy generated by applying the BP-operator to the Meyer-Stockmeyer polynomial-time hierarchy (PH), where the BP-operator is the natural generalization of the probabilistic complexity class BPP. The similarity and difference between the two hierarchies BPH and PH is investigated. Oracles
A
and
B
are constructed such that both PH(
A
) and PH(
B
) are infinite while BPH(
A
) is not equal to PH(
A
) at any level and BPH(
B
) is identical to PH(
B
) at every level. Similar separating and collapsing results in the case that PH(
A
) is finite having exactly
k
levels are also considered.
Nutrition, Activity, and Health in Children
Authors: Dufour Darna L.
Published: July 2002

This chapter reviews current understanding of the associations between physical activity and nutrition in children 1 to 10 years of age. In general, both undernutrition and overnutrition are accompanied by lower levels of physical activity than in controls. In children of normal nutritional status, an association between physical activity and body composition has been difficult to demonstrate. It is clear that levels of physical activity in children are responsive to the physical and social environments, as well as to a child's nutritional status. In children of normal nutritional status, the level of physical activity increases with age in young children and then decreases in early adolescence, and males tend to be more physically active than females in a given population. Although there is a perception that children are less physically active than they were in the past, trends in physical activity through time are not known.
EVOLUTIONARY ECOLOGY OF HUMAN REPRODUCTION
Authors: Voland Eckart
Published: July 2002

▪ Abstract  Evolutionary ecology of human reproduction is defined as the application of natural selection theory to the study of human reproductive strategies and decision-making in an ecological context. The basic Darwinian assumption is that humans—like all other organisms—are designed to maximize their inclusive fitness within the ecological constraints to which they are exposed. Life history theory, which identifies trade-off problems in reproductive investment, and evolutionary physiology and psychology, which analyzes the adaptive mechanisms regulating reproduction, are two crucial tools of evolutionary reproductive ecology. Advanced empirical insights have been obtained mainly with respect to the ecology of fecundity, fertility, child-care strategies, and differential parental investment. Much less is known about the ecology of nepotism and the postgenerative life span. The following three theoretical aspects, which are not well understood, belong to the desiderata of future improvement in evolutionary human reproductive ecology: (a) the significance of and the interactions between different levels of adaptability (genetic, ontogenetic, and contextual) for the adaptive solution of reproductive problems; (b) the dialectics of constraints and adaptive choices in reproductive decisions; and (c) the dynamics of demographic change.
Form and Ideology: Arabic Sociolinguistics and Beyond
Authors: Haeri Niloofar
Published: July 2002

▪ Abstract  The aim of this review is to contribute to a dialogue between anthropologists and sociolinguists who work on the Arab world. One of the most distinctive features of the Arab world is that Classical Arabic co-exists with national vernaculars such as Egyptian, Syrian, Jordanian, and so on. The first is the language of writing, education, and administration, whereas the latter are the media of oral exchanges, nonprint media, poetry, and plays. The proximity or distance between the “Classical” and the “colloquials,” whether the latter are also “Arabic” or have been so accepting of foreign borrowings that they ceased to be so, whether they are languages or “inferior dialects” are all contentious issues that continue to be debated within the Arab world. In fact, such debates have become inseparable from the central concerns and dilemmas of social and intellectual movements in this century. After providing a broad outline of work in Arabic sociolinguistics, the review moves to the literature on education. Debates on education are intimately linked with larger questions regarding colonialism, nationalism, and modernization. The last part of the review is devoted to anthropological works on the region. The complexities of the sociolinguistic settings in the Arab world provide promising and challenging grounds for contributions to anthropological theory.
DNA DAMAGE AND REPAIR IN PLANTS
Authors: Britt Anne B.
Published: July 2002

▪ Abstract  The biological impact of any DNA damaging agent is a combined function of the chemical nature of the induced lesions and the efficiency and accuracy of their repair. Although much has been learned from microbes and mammals about both the repair of DNA damage and the biological effects of the persistence of these lesions, much remains to be learned about the mechanism and tissue-specificity of repair in plants. This review focuses on recent work on the induction and repair of DNA damage in higher plants, with special emphasis on UV-induced DNA damage products.