Describes the data model that is used to implement the SIM content management server (CMS), an SGML/XML-native content server that is designed to support extremely fast data access to and dynamic updating of 100-GByte collections under high loads. This paper describes the requirements for supporting text-intensive applications and for building XML/SGML document management solutions. The SIM CMS employs a data model that is designed to directly support SGML and XML; this model is described, and a comparison with other models based on general-purpose database management systems is made.

Queries to text collections are resolved by ranking the documents in the collection and returning the highest-scoring documents to the user. An alternative retrieval method is to rank passages, that is, short fragments of documents, a strategy that can improve effectiveness and identify relevant material in documents that are too large for users to consider as a whole. However, ranking of passages can considerably increase retrieval costs. In this article we explore alternative query evaluation techniques, and develop new tecnhiques for evaluating queries on passages. We show experimentally that, appropriately implemented, effective passage retrieval is practical in limited memory on a desktop machine. Compared to passage ranking with adaptations of current document ranking algorithms, our new “DO-TOS” passage-ranking algorithm requires only a fraction of the resources, at the cost of a small loss of effectiveness.

No abstract available.

Ranking techniques are effective at finding answers in document collections but can be expensive to evaluate. We propose an evaluation technique that uses early recognition of which documents are likely to be highly ranked to reduce costs; for our test data, queries are evaluated in 2% of the memory of the standard implementation without degradation in retrieval effectiveness. Cpu time and disk traffic can also be dramatically reduced by designing inverted indexes explicitly to support the technique. The principle of the index design is that inverted lists are sorted by decreasing within-document frequency rather than by document number, and this method experimentally reduces cpu time and disk traffic to around one third of the original requirement. We also show that frequency sorting can lead to a net reduction in index size, regardless of whether the index is compressed. © 1996 John Wiley & Sons, Inc.

Advanced database applications require facilities such as text indexing, image storage, and the ability to store data with a complex structure. However, these facilities are not usually included in traditional database systems. In this paper we describe Atlas, a nested relational database system that has been designed for text-based applications. The Atlas query language is TQL, an SQL-like query language with text operators. The query language is supported by signature file text indexing techniques, and by a parser that can be configured for different text formats and even some foreign languages. Atlas can also be used to store images and audio.>

There is a simple method for integrating information retrieval and hypertext. This consists of treating nodes as isolated documents and retrieving them in order of similarity. If the nodes are structured, in particular, if sets of nodes collectively constitute documents, we can do better. This paper shows how the formation of the hypertext, the retrieval of nodes in response to content based queries, and the presentation of the nodes can be achieved in a way that exploits the knowledge encoded as the structure of the documents. The ideas are then exemplified in an SGML based hypertext information retrieval system.

Our work involves the study of the extent to which natural language processing techniques aid the automatic indexing and retrieval of documents. In this paper we describe the use of signature files in large text retrieval systems. We show that good performance can be obtained without requiring the significant overheads required for the inverted file technique. We examine the use of syntactic analysis of the text in all stages of retrieval and argue that an initial Boolean query should be performed that provides a subset of documents, which are then ranked. We then give an algorithm for generating such queries, taking into account the syntactic structure of the queries.

A new signature file method for accessing information from large databases containing both formatted and free text data is presented. The new method, called the multiorganizational scheme is proposed for indexing very large databases containing hundreds of thousands or possibly millions of records. With this method, records are grouped into blocks and signatures are formed for each block of records. These signatures are stored in a block descriptor file using a storage device called the bit slice organization. By forming multiple block descriptor files, each based on a possibly different grouping of records into blocks, it is possible to efficiently determine record matches on query. Both computational results based on a mathematical model as well as experimental results using a library database are presented. These results show that the method provides effective access to large text databases. © 1990 John Wiley & Sons, Inc.

A method is presented for extending a conventional DBMS (database management system) for geographic applications. The interface language SQL is augmented to allow formulation of queries involving both spatial and nonspatial selection criteria. A novel indexing structure is supported to facilitate query retrieval that is based on spatial proximity. To enable hybrid queries to be evaluated efficiently, an extended optimization strategy is proposed that evaluates minimal implementation effort.>

Both single-level and two-level indexed descriptor schemes for multikey retrieval are presented and compared. The descriptors are formed using superimposed coding techniques and stored using a bit-inversion technique. A fast-batch insertion algorithm for which the cost of forming the bit-inverted file is less than one disk access per record is presented. For large data files, it is shown that the two-level implementation is generally more efficient for queries with a small number of matching records. For queries that specify two or more values, there is a potential problem with the two-level implementation in that costs may accrue when blocks of records match the query but individual records within these blocks do not. One approach to overcoming this problem is to set bits in the descriptors based on pairs of indexed terms. This approach is presented and analyzed.

A modification of linear hashing is proposed for which the conventional use of overflow records is avoided. Furthermore, an implementation of linear hashing is presented for which the amount of physical storage claimed is only fractionally more than the minimum required. This implementation uses a fixed amount of in-core space. Simulation results are given which indicate that even for storage utilizations approaching 95 percent, the average successful search cost for this method is close to one disk access.

A decimal arithmetic unit is proposed for both integer and floating-point computations. To achieve comparable speed to a binary arithmetic unit, the decimal unit is based on a redundant number representation. With this representation no loss of compactness is made relative to binary coded decimal (BCD) form. In this paper the hardware required for the implementation of the basic operations of addition, subtraction, multiplication and division are described and the properties of floating-point arithmetic based on a redundant number representation are investigated.

An alternative technique for the implementation of variable step-size multistep formulas is developed for the numerical solution of ordinary differential equations.Formulas based on this technique have the property that their leading coefficients are constant; thLs LS important for methods which solve stiff systems.In addition, both theoretmal and empirical results indicate that methods based on this techmque have stability properties similar to those of the corresponding variable coefficient implementations.As a particular example, we have nnplemented the backward differentiation formulas m this form, and the numerical results look very promising.

A code based on Enrlght's second-derivative formulas is described for the numermal solution of stiff ODEs A predictor-corrector approach Is taken, and a fixed leadmg coefficmnt technique is used to unplement the variable step-size formulas This strategy is efficient for stiff systems, and the underlying algorithm IS stable and convergent.The code has been designed consistently with the well-known Adams routine STEP, and advantage Is taken of the mmflarlty between Adams' formulas and Ennght's formulas for an effiment lmplementatmn.