Let $\poly = \{P_0,\dots,P_{n-1}\}$ denote a set of polynomials with complex coefficients. Let $\pts = \{z_0,\dots,z_{n-1}\}\subset \cplx$ denote any set of {\it sample points}. For any $f = (f_0,\dots,f_{n-1}) \in \cplx^n$, the {\it discrete polynomial transform} of f (with respect to $\poly$ and $\pts$) is defined as the collection of sums, $\{\fhat(P_0),\dots,\fhat(P_{n-1})\}$, where $\fhat(P_j) = \langle f,P_j \rangle = \sum_{i=0}^{n-1} f_iP_j(z_i)w(i)$ for some associated weight function w. These sorts of transforms find important applications in areas such as medical imaging and signal processing. In this paper, we present fast algorithms for computing discrete orthogonal polynomial transforms. For a system of N orthogonal polynomials of degree at most $N-1$, we give an $O(N\log^2 N)$ algorithm for computing a discrete polynomial transform at an arbitrary set of points instead of the $N^2$ operations required by direct evaluation. Our algorithm depends only on the fact that orthogonal polynomial sets satisfy a three-term recurrence and thus it may be applied to any such set of discretely sampled functions. In particular, sampled orthogonal polynomials generate the vector space of functions on a distance transitive graph. As a direct application of our work, we are able to give a fast algorithm for computing subspace decompositions of this vector space which respect the action of the symmetry group of such a graph. This has direct applications to treating computational bottlenecks in the spectral analysis of data on distance transitive graphs, and we discuss this in some detail.

We consider the problem of computing the shortest schedule of the intervals [j2−i,(j + 1)2−i), for 0 ⩽ j ⩽ 2i − 1 and 1 ⩽ i ⩽ k such that separation of intersecting intervals is at least R. This problem arises in an application of wavelets to medical imaging. It is a generalization of the graph separation problem for the intersection graph of the intervals, which is to assign the numbers 1 to 2k + 1 − 2 to the vertices, other than the root, of a complete binary tree of height k in such a way as to maximize the minimum difference between all ancestor descendent pairs. We give an efficient algorithm to construct optimal schedules.

This paper considers the problem of representing stacks with catenation so that any stack, old or new, is available for access or update operations. This problem arises in the implementation of list-based and functional programming languages. A solution is proposed requiring constant time and space for each stack operation except catenation, which requires O(log log k ) time and space. Here k is the number of stack operations done before the catenation. All the resource bounds are amortized over the sequence of operations.

Current information retrieval systems focus on the use of keywords to respond to user queries. We propose the additional use of surface level knowledge in order to improve the accuracy of information retrieval. Our approach is based on the database concept of semantic modeling (particularly entities and relationships among entities). We extend the concept of query-document similarity by recognizing basic entity properties (attributes) which appear in text. We also extend query-document similarity using the linguistic concept of thematic roles. Thematic roles allow us to recognize relationship properties which appear in text. We include several examples to illustrate our approach. Test results which support our approach are reported. The test results concern searching documents and using their contents to perform the intelligent task of answering a question.

The problem of computing the convolution of two functions on the sphere by means of a spherical transform is considered. Such convolutions are applicable to surface recognition and the location of both rotated and translated patterns in an image. The authors give convolution theorems that relate the spherical transform to convolution, sampling theorems that allow the exact computation of the transform for band-limited functions, and algorithms with asymptotically improved running time for the exact computation of the harmonic expansion. The net result is an O(n/sup 1.5/(log n)/sup 2/) algorithm for the exact computation of the convolution of two bandlimited functions sampled at n points in accordance with the sampling theorem. The techniques developed are applicable to computing other transforms, such as the Laguerre, Hermite, and Hankel transforms.>

A direct and unified approach is used to analyze the efficiency of batched searching of sequential and tree-structured files. The analysis is applicable to arbitrary search distributions, and closed-form expressions are obtained for the expected batched searching cost and savings. In particular, we consider a search distribution satisfying Zipf's law for sequential files and four types of uniform (random) search distribution for sequential and tree-structured files. These results unify and extend earlier research on batched searching and estimating block accesses for database systems.

This paper presents a combined algorithm to perform batch insertion, deletion, and update for tree structured files. The efficiency of the algorithm is analyzed for performing updates only and insertions only. A cost analysis example is reviewed to demonstrate that batch operations for tree structured files achieve the advantages of a differential database representation and, at the same time, avoid the drawbacks previously attributed to the use of differential files.

This paper is a study of persistence in data structures. Ordinary data structures are ephemeral in the sense that a change to the structure destroys the old version, leaving only the new version available for use. In contrast, a persistent structure allows access to any version, old or new, at any time. We develop simple, systematic, and effiient techniques for making linked data structures persistent. We use our techniques to devise persistent forms of binary search trees with logarithmic access, insertion, and deletion times and O(1) space bounds for insertion and deletion.

This session will consist of a panel discussion of courses in DBMS which involve student projects using commercially available database management systems. A list of panelists and a synopsis of their topics follows.

We show that any group represented by generators that are cycles of bounded degree has O(n2) diameter, i.e., that the longest product of generators required to reach any permutation in the group is O(n2). We also show how such “short” products can be found in polynomial time. The techniques presented are applicable to generalizations of many permutation-group puzzles such as Alexander's Star and the Hungarian Rings.

A compiling system which implements a rela tional DBMS is described. The compiling system is part of a unique architecture designed to simplify DBMS implementation. The architecture specifies an interface defined by basic physical storage constructs for specifying actual data storage structure, and primitive physical navigation operations for implementing data manipulation commands. The compiling system described here maps a relational user view to this interface.

In this paper we describe a general purpose relational data base system from both user's and system's viewpoints. The system is currently being implemented for the microprogrammable computer Interdata 85 at the Department of Computer Science, University of Kansas. The long range goal of this research is to implement a distributed data base system in a computer link where the Interdata 85 is connected to a large computer of different architecture and language capability, the Honeywell 635. Toward this goal, we propose a new physical storage structure called a binary search tree complex or BST complex. Primitives to manipulate BST complexes can be easily implemented for both machines. Queries, data manipulation operations and data definition operations specified by users can be mapped into these BST complex primitives; therefore the translation process can be independent of machine hardware. In this paper, we outline the capability of a user data language UDL-1 and its implementation in terms of BST complexes. A detailed description of all BST complex primitives appears in [LTD].