Abstract Automated information retrieval relies heavily on statistical regularities that emerge as terms are deposited to produce text. This paper examines statistical patterns expected of a pair of terms that are semantically related to each other. Guided by a conceptualization of the text generation process, we derive measures of how tightly two terms are semantically associated. Our main objective is to probe whether such measures yield reasonable results. Specifically, we examine how the tendency of a content bearing term to clump, as quantified by previously developed measures of term clumping, is influenced by the presence of other terms. This approach allows us to present a toolkit from which a range of measures can be constructed. As an illustration, one of several suggested measures is evaluated on a large text corpus built from an on‐line encyclopedia.

The essence of Scientometrics is precise measurement. Yet the measurements made in Scientometric research is steeped in ambiguity. This article explores the nature of ambiguity in measurement, and probes for mechanisms that allow regularities to be discovered in an environment in which ambiguity is pronounced.

This article examines some consequences for information control of the tendency of occurrences of content-bearing terms to appear together, or clump. Properties of previously defined clumping measures are reviewed and extended, and the significance of these measures for devising retrieval strategies discussed. A new type of clumping measure, which extends the earlier measures by permitting gaps within a clump, is defined, and several variants examined. Experiments are carried out that indicate the relation between the new measure and one of the earlier measures, as well as the ability of the two types of measure to predict compression efficiency.

Abstract Using novel informatics techniques to process the output of Medline searches, we have generated a list of viruses that may have the potential for development as weapons. Our findings are intended as a guide to the virus literature to support further studies that might then lead to appropriate defense and public health measures. This article stresses methods that are more generally relevant to information science. Initial Medline searches identified two kinds of virus literatures—the first concerning the genetic aspects of virulence, and the second concerning the transmission of viral diseases. Both literatures taken together are of central importance in identifying research relevant to the development of biological weapons. Yet, the two literatures had very few articles in common. We downloaded the Medline records for each of the two literatures and used a computer to extract all virus terms common to both. The fact that the resulting virus list includes most of an earlier independently published list of viruses considered by military experts to have the highest threat as potential biological weapons served as a test of the method; the test outcome showed a high degree of statistical significance, thus supporting an inference that the new viruses on the list share certain important characteristics with viruses of known biological warfare interest.

Information Retrieval Systems identify content bearing words, and possibly also assign weights, as part of the process of formulating requests. For optimal retrieval efficiency, it is desirable that this be done automatically. This article defines the notion of serial clustering of words in text, and explores the value of such clustering as an indicator of a word's bearing content. This approach is flexible in the sense that it is sensitive to context: a term may be assessed as content-bearing within one collection, but not another. Our approach, being numerical, may also be of value in assigning weights to terms in requests. Experimental support is obtained from natural text databases in three different languages. © 1998 John Wiley & Sons, Inc.

Many of the most effective compression methods involve complicated models. Unfortunately, as model complexity increases, so does the cost of storing the model itself. This paper examines a method to reduce the amount of storage needed to represent a Markov model with an extended alphabet, by applying a clustering scheme that brings together similar states. Experiments run on a variety of large natural language texts show that much of the overhead of storing the model can be saved at the cost of a very small loss of compression efficiency.

This article examines various kinds of uncertainty. The notion of ambiguity is defined and contrasted with the more familiar notions of randomness and fuzziness. Functional forms resistant to ambiguity are defined, and it is shown how to incorporate a random component, that is itself also resistant to ambiguity, into a resilient, but deterministic, model.

An earlier paper developed a procedure for compressing concordances, assuming that all alements occurred independently. The models introduced in that paper are extended here to take the possiblity of clustering into account. The concordance is conceptualized as a set of bitmaps, in which the bit locations reporesent documents, and the one-bits represent the occurrence of given terms. Hidden Markov Models (HMM's) are used to describe the clustering of the one-bits. However, for computational reasons, the HMM is approximated by traditional Markov models. A set of criteria is developed to constrain the allowable set of n -state models, and a full inventory is given for n ≤ 4. Graph-theoretic reduction and complementation operations are defined among the various models and are used to provide a structure relating the models studied. Finally, the new methods were tested on the concordances of the English Bible and of two of the world's largest full-text retrieval systems: the Tre´sor de la Langue Franc¸aise and the Responsa Project.

Because of concerns about the privacy of its patrons, it is common for libraries to systematically destroy historic information about book circulation. I argue that this information has great potential value for improving retrieval effectiveness, and give two examples of how this information can be used. Further, I show how use-data can be preserved and exploited while still giving a high degree of protection for patron privacy. The methods are analyzed and formulae are derived indicating the tradeoff between retrieval effectiveness and security. A second, contrasting application, indicating how to introduce “fingerprints” into digitized audio-visual material in a tamper-resistant manner, is described. © 1996 John Wiley & Sons, Inc.

InformationRetrieval Systems typically distinguish between content bearing words and terms on a stop list.But "content-bearing " is relative to a collection.For optimal retrieval efficiency, it is desirable to have automated methods for custom building a stop list.This paper defines the notion of serial clustering of words in text, and explores the value of such clustering as an indicator of a word bearing cent ent.The numerical measures we propose may also be of value in assigning weights to terms in requests.Experimental support is obtained from natural text databases in three different languages.

An earlier paper developed a procedure for compressing concordances, assuming that all elements occurred independently. In this paper, the earlier models are extended to take the possibility of clustering into account. The authors suggest several models adapted to concordances of large full-text information retrieval systems, which are generally subject to clustering.>

Much of compression theory assumes knowledge of exact statistics of the alphabet being encoded. In practice, codes are often based on approximations of true statistics. This paper examines the consequences of random fluctuations on coding efficiency. It shows that exact statistics permit more efficient encoding, but when the error is due to random fluctuation, the savings are small and of magnitude of the extra table needed for decoding.>

Article Is Huffman coding dead? (extended abstract) Share on Authors: Abraham Bookstein View Profile , Shmuel T. Klein View Profile , Timo Raita View Profile Authors Info & Claims SIGIR '93: Proceedings of the 16th annual international ACM SIGIR conference on Research and development in information retrievalJuly 1993 Pages 80–87https://doi.org/10.1145/160688.160697Online:01 July 1993Publication History 5citation1,017DownloadsMetricsTotal Citations5Total Downloads1,017Last 12 Months11Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

The authors discuss concordance compression using the framework now customary in compression theory. They begin by creating a mathematical model of concordance generation, and then use optimal compression engines, such as Huffman or arithmetic coding, to do the actual compression. It should be noted that in the context of a static information retrieval system, compression and decompression are not symmetrical tasks. Compression is done only once, while building the system, whereas decompression is needed during the processing of every query and directly affects the response time. One may thus use extensive and costly preprocessing for compression, provided reasonably fast decompression methods are possible. Moreover, compression is applied to the full files (text, concordance, etc.), but decompression is needed only for (possibly many) short pieces, which may be accessed at random by means of pointers to their exact locations. Therefore the use of adaptive methods based on tables that systematically change from the beginning to the end of the file is ruled out. However, their concern is less the speed of encoding or decoding than relating concordance compression conceptually to the modern approach of data compression, and testing the effectiveness of their models.>

This paper considers the problem of compressing a set of bit maps, exploring the possibility of exploiting the structure between as well as within them to compress the whole bit-table. It describes several particularly simple models of bit occurrence. Two of these are based on detailed assumptions of bit-independence. The third uses regression models. The strategy of separating model construction and compression method continues the well-established practice of basing compression on an explicit model of message generation. Flexible encoding is distinguished from adaptive and static approaches.>

block is then encoded using Huffman or arithmetic coding.Preliminary experimental results indicate improvements over previous methods.

Bitmaps are data structures occurring often in information retrieval. They are useful; they are also large and expensive to store. For this reason, considerable effort has been devoted to finding techniques for compressing them. These techniques are most effective for sparse bitmaps. We propose a preprocessing stage, in which bitmaps are first clustered and the clusters used to transform their member bitmaps into sparser ones, that can be more effectively compressed. The clustering method efficiently generates a graph structure on the bitmaps. The results of applying our algorithm to the Bible is presented: for some sets of bitmaps, our method almost doubled the compression savings.

This article is the first of a two-part series on the informetric distributions, a family of regularities found to describe a wide range of phenomena both within and outside of the information sciences. This article introduces the basic forms these regularities take. A model is proposed that makes plausible the possibility that, in spite of marked differences in their appearance, these distributions are variants of a single distribution; heuristic arguments are then given that this is indeed the case. That a single distribution should describe such a wide range of phenomena, often in areas where the existence of any simple description is surprising, suggests that one should look for explanations not in terms of causal models, but in terms of the properties of the single informetric distribution. Some of the consequences of this conclusion are broached in this article, and explored more carefully in Part II. © 1990 John Wiley & Sons, Inc.

This article continues the discussion of the informetric distributions begun in a companion paper. In the earlier paper, the informetric distributions were introduced and found to be variants of a single distribution. It was suggested that this might be explained in terms of that distribution being unusually resilient to ambiguity. In this paper the notion of resilience to ambiguity is made precise. By way of introduction, a number of simple examples of resilience, taken from the social sciences, are discussed. This approach is then applied to the informetric distributions themselves. It is argued that the form taken by the informetric regularities does indeed make them insensitive to the wide range of ambiguities that occur when measuring the output of social activity, and that this ubiquitous form is unusual in having this property. © 1990 John Wiley & Sons, Inc.

Text compression is of considerable theoretical and practical interest. It is, for example, becoming increasingly important for satisfying the requirements of fitting a large database onto a single CD-ROM. Many of the compression techniques discussed in the literature are model based. We here propose the notion of a formal grammar as a flexible model of text generation that encompasses most of the models offered before as well as, in principle, extending the possibility of compression to a much more general class of languages. Assuming a general model of text generation, a derivation is given of the well known Shannon entropy formula, making possible a theory of information based upon text representation rather than on communication. The ideas are shown to apply to a number of commonly used text models. Finally, we focus on a Markov model of text generation, suggest an information theoretic measure of similarity between two probability distributions, and develop a clustering algorithm based on this measure. This algorithm allows us to cluster Markov states, and thereby base our compression algorithm on a smaller number of probability distributions than would otherwise have been required. A number of theoretical consequences of this approach to compression are explored, and a detailed example is given.

: The emergence of the CD-ROM as a storage medium for full-text databases raises the question of the maximum size database that can be contained by this medium. As an example, the problem of storing the Tr'esor de la Langue Fran¸caise on a CD-ROM is examined in this paper. The text alone of this database is 700 MB long, more than a CD-ROM can hold. But in addition the dictionary and concordance needed to access this data must be stored. A further constraint is that some of the material is copyrighted, and it is desirable that such material be difficult to decode except through software provided by the system. Pertinent approaches to compression of the various files are reviewed and the compression of the text is related to the problem of data encryption: specifically, it is shown that, under simple models of text generation, Huffman encoding produces a bit-string indistinguishible from a representation of coin flips. Categories and Subject Descriptors: E.3 E.4 H.3.2 J.5 General terms: ...

The emergence of the CD-ROM as a storage medium for full-text databases raises the question of the maximum size database that can be contained by this medium. As an example, the problem of storing the Trésor de la Langue Française on a CD-ROM is examined in this paper. The text alone of this database is 700 megabytes long, more than a CD-ROM can hold. In addition, the dictionary and concordance needed to access these data must be stored. A further constraint is that some of the material is copyrighted, and it is desirable that such material be difficult to decode except through software provided by the system. Pertinent approaches to compression of the various files are reviewed, and the compression of the text is related to the problem of data encryption: Specifically, it is shown that, under simple models of text generation, Huffman encoding produces a bit-string indistinguishable from a representation of coin flips.

The broad way in which we look at how an IRS functions influences the types of questions we ask about it and the ways we try to improve performance. In the recent past, retrieval methodologies have been based on retrieving documents one at a time. In this paper we are introducing a set oriented view. We observe that this view is quite consistent with the single-document or sequential methods, and define a precise model to capture the set-oriented approach. We then examine a number consequences of the model, such as the limitations implied by a finite index vocabulary. Finally, we discuss various ways in which the set orientation can influence our thinking about IR.

In this paper we study the behavior of an information retrieval system in which index terms are assigned at random to both documents and requests. The random indexing is then modified by means of a feedback mechanism derived from a normal probability model and applied to both the request and document representations. Of interest is the convergence properties of the representation vectors. After few feedback iterations, it is found that well defined clusters form that accurately represent the corelevance structure among the documents—in effect the feedback mechanism has permitted the documents to index themselves. This approach offers an interesting way to extend the dimensionality of the indexing vocabulary. Both this application and a theoretical analysis of the impact of extending the indexing vocabulary are discussed.

Probabilistic document retrieval systems consistent with the two Poisson independence model outperforms the binary independence model if the terms are distributed as described by the model's assumptions. The Two Poisson Effectiveness Hypothesis suggests that retrieval models based upon the two Poisson model will outperform binary independent models when used on a “real-world” database, where independence and two Poisson term occurrence distributions fail to hold, because the added information obtained from incorporating term frequency information will more than compensate for the non-Poisson distributions of terms. Searches of the MED1033 database suggest that if terms are not independent and frequencies of term occurrence are not distributed in a two Poisson manner, the binary independence sequential retrieval model outperforms the two Poisson independence retrieval model.

Article Implications of Boolean structure for probabilistic retrieval Share on Author: Abraham Bookstein Graduate Library School, University of Chicago, 1100 E. 57th St., Chicago, IL Graduate Library School, University of Chicago, 1100 E. 57th St., Chicago, ILView Profile Authors Info & Claims SIGIR '85: Proceedings of the 8th annual international ACM SIGIR conference on Research and development in information retrievalJune 1985 Pages 11–17https://doi.org/10.1145/253495.253505Online:05 June 1985Publication History 3citation223DownloadsMetricsTotal Citations3Total Downloads223Last 12 Months4Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Abstract The fundamental problem of information retrieval is how to decide, on the basis of clues, each of which is an imperfect indicator of docuemnt relevance, which documents to retrieve and the order in which to present them. The most satisfying conceptual approaches have been based on probabilistic decision theoretic models. However, those previously used make a decision about a single document at a time, and extend this to retreiv e multiple docuemnts by ignoring interdocument interaction. The purpose of the articles is to present decision‐theoretic models which intrinsically include the multiple retrieval case. In particular, we argue that information retrieval should be envisioned as a process, in which the information retrieval system responds to a request by presenting documents to the patron in a sequence, gathering feedback as the process proceeds, and using this information to modify future retrieval. A retrieval strategy that naturally results from this model is described. Two examples are examined in detail.

article Free Access Share on The generalized retrieval problem Author: A. Bookstein University of Chicago University of ChicagoView Profile Authors Info & Claims ACM SIGIR ForumVolume 16Issue 1Summer 1981 pp 4–14https://doi.org/10.1145/1013228.511756Published:31 May 1981Publication History 1citation231DownloadsMetricsTotal Citations1Total Downloads231Last 12 Months5Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Abstract A major deficiency of traditional Boolean systems is their inability to represent the varying degrees to which a document may be written on a subject. In this article we isolate a number of criteria that should be met by any Boolean system generalized to have a weighting capability. It is proven that only one weighting rule satisfies these conditions—that associated with fuzzy‐set theory—and that this weighting scheme satisfies most of the other properties associated with Boolean algebra as well. Probabilistic weighting is then introduced as an alternative approach and the two systems compared. In the limit of zero/one weights, all systems considered converge to traditional Boolean retrieval.

Abstract This article concerns the problem of how to permit a patron to represent the relative importance of various index terms in a Boolean request while retaining the desirable properties of a Boolean system. The character of classical Boolean systems is reviewed and related to the notion of fuzzy sets. The fuzzy set concept then forms the basis of the concept of a fuzzy request in which weights are assigned to index terms. The properties of such a system are discussed, and it is shown that such systems retain the manipulability of traditional Boolean requests.

Abstract Attempts have been made to rank the output of a Boolean search in terms of the overlap of index terms in the request and document. As attractive as the merger of two approaches may seem, a closer examination reveals disturbing ambiguities, with equivalent Boolean expressions yielding different weights for the retrieval documents. An alternative approach is suggested.

Abstract The Swets model of information retrieval, based on a decision theory approach, is discussed, with the overall performance measure being the crucial element reexamined in this paper. The Neyman‐Pearson criterion from statistical decision theory, and based on likelihood ratios, is used to determine an optimal range of Z, the variable assigned to each document by the retrieval system in an attempt to discriminate between relevant and nonrelevant documents. This criterion is shown to be directly related to both precision and recall, and is equivalent to the maximization of the expected value of the retrieval decision for a specific query and a given document under certain conditions. Thus, a compromise can be reached between those who advocate precision as a measure, due partially to its ability to be easily measurable empirically, and those who advocate consideration of recall. Several cases of the normal and Poisson distributions for the variable Z are discussed in terms of their implications for the Neyman‐Pearson decision rule. It is seen that when the variances are unequal, the Swets rule of retrieving a document if its Z value is large enough is not optimal. Finally, the situation of precision and recall not being inversely related is shown to be possible under certain conditions. Thus, this paper attempts to extend the understanding of the theoretical foundations of the decision theory approach to information retrieval.

article Free Access Share on Operations Research Applied to Document Indexing and Retrieval Decisions Authors: Abraham Bookstein The University of Chicago, Graduate Library School, 1100 East 57th St, Chicago, IL The University of Chicago, Graduate Library School, 1100 East 57th St, Chicago, ILView Profile , Don Kraft Department of Computer Science, Louisiana State University, Baton Rouge, LA Department of Computer Science, Louisiana State University, Baton Rouge, LAView Profile Authors Info & Claims Journal of the ACMVolume 24Issue 3July 1977 pp 418–427https://doi.org/10.1145/322017.322022Published:01 July 1977Publication History 37citation509DownloadsMetricsTotal Citations37Total Downloads509Last 12 Months14Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Abstract The indexing of a document is among the most crucial steps in preparing that document for retrieval. The adequacy of the indexing determines the ability of the system to respond to patron requests. This paper discusses this process, and document retrieval in general, on the basis of formal decision theory. The basic theoretical approach taken is illustrated by means of a model of word occurrences in documents in the context of a model information system; both models are fully defined in this paper. Though the main purpose of this paper is to provide insights into a very complex process, formulae are developed that may prove to be of value for an automated operating system. The paper concludes with an interpretation of recall and precision curves as seen from the point of view of decision theory.

Abstract This paper considers the problem of allocating resources among various locations in an information system where phases of a process are carried out. The approach taken combines queueing theory and dynamic programming. As an illustration of this approach, two prototype problems are considered in some detail: the distribution of computer terminals among various functions requiring access to a computer, and the distribution of personnel among the various phases of the process of cataloging a book. The technique is found to be both efficient and flexible.

Abstract This paper defines a hash coding model for non‐unique search keys and derives the expected number of accesses needed to retrieve all desired records from a computer storage device. The assumption that the records are stored on the basis of a non‐unique key is often realized in information retrieval environments. The model assumes that the hashing algorithm and, should a collision occur, the skipping algorithm, both distribute the records randomly in memory. The results of this analysis are compared with those from a simulation in which the randomness criterion is not strictly met.

Abstract This paper generalizes the direct‐chaining technique of hash coding in a manner that is useful for storing records on the basis of non‐unique search keys. Such a capability is of particular interest for library automation and information retrieval. Two hash functions are used instead of one, and to take advantage of the information contained in both, a tree structure is substituted for a linear chain. As developed here, this technique can also be used, with improved efficiency, for storing records with unique keys. To represent both environments, two specific models are defined, analyzed, and compared to conventional methods.