--- title: "Revealing Collection Structure through Information Access Interfaces" authors: - "Marti A. Hearst" - "Jan O. Pedersen" doi: "" url: "https://ijcai.org/proceedings/1995/265" pdf: "https://ijcai.org/proceedings/1995/0265.pdf" venue: "Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence" year: 1995 pages: "2047-2047" track: "Videos" keywords: --- # Revealing Collection Structure through Information Access Interfaces Marti A. Hearst, Jan O. Pedersen *Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence*, pages 2047-2047. ## Abstract ## Full text ## Revealing Collection Structure through Information Access Interfaces Marti A. Hearst Jan 0. Pedersen Xerox Palo Alto Research Center 3333 Coyote Hill Road Palo Alto, CA 94304 (415) 812-4742 {hearst,pedersen }@parc.xerox.com Information Access research at Xerox PARC focuses on amplifying the users' cognitive abilities, rather than trying to completely automate them. This framework emphasizes the participation of the user in a cycle of query formulation, presentation of results, followed by query reformulation, and so on. This framework is in­ tended to help the user iteratively refine a vaguely un­ derstood information need. Since the focus is on query repair, the information presented is typically not docu­ ment descriptions, but rather intermediate information that indicates relationships between the query and the retrieved documents. We have developed information ac­ cess tools intended to supply some of this functionality, and describe two of these here. As an illustration, suppose a user is interested in med­ ical diagnosis software. Assume that initially the user has available a large, unfamiliar information source. In our example, this source is the 2.2 Gigabyte TIPSTER text collection [Harman, 1993]. Because the collection is unfamiliar, the user will be unsure whether it contains relevant information, and if so, how to access it. To address this situation, we have developed a brows­ ing method, called Scatter/Gather [Cutting et al., 1992; 1993], that allows a user to rapidly assess the general contents of a very large collection by scanning through a dynamic, hierarchical representation that is motivated by a table-of-contents metaphor. Initially the system automatically scatters, or clusters, the collection into a small number of document groups, and presents short summaries of the groups to the user. These summaries consist of two types of information: topical titles (titles of documents close to the cluster centroid) and typical terms (terms of importance in the cluster). Based on these summaries, the user selects one or more of the groups for further study. The selected groups are gath­ ered, or unioned, together to form a subcollection. The system then applies clustering again to scatter the new subcollection into a small number of document groups, which are again presented to the user. With each succes­ sive iteration the groups become smaller, and therefore more detailed. The user may, at any time, switch to a more focused search method. Figure 1 shows a portion of the top level clusters on the TIPSTER collection. Figure 1: A portion of a top-level view of the Scat­ ter/Gather algorithm over the TIPSTER corpus. ![Image](https://ijcai.org/proceedings/1995/fulltext/265/image_000000_f24e65f7e9d48a07ce7e291c8b5714d68606b88d1c8203729a32ff9055251cc7.png) By browsing the collection in this manner, the user ob­ tains an idea about the technical contents of the corpus, and can choose whether or not to further explore here or try another text collection. From the titles and terms re­ trieved, it becomes apparent that the collection contains commercially oriented discussions of technology, rather than predominantly academic ones. From this overview information, the user can conclude that this is indeed a promising collection for the user's information need. Once a promising collection has been identified, the user can issue a search. In a typical information retrieval system, documents satifying the query are returned and are rank-ordered according to some function of the num­ ber of hits for each term [Salton, 1988]. But this kind of ranking is opaque to the user; it is not clear how well each term is represented in the retrieved documents. To address these issues, the TileBars interface [Hearst, 1995] allows the user to make informed decisions about which documents and which passages of those doc­ uments to view, based on the distributional behavior of the query terms in the documents. The goal is to simul­ taneously and compactly indicate (i) the relative length of the document, (ii) the frequency of the term sets in the document, and (iii) the distribution of the term sets with respect to the document and to each other. Each document is partitioned in advance into a set of multi­ paragraph subtopical segments using an algorithm called TextTiling [Hearst, 1994]. Figure 2: The TileBar Display on a query about auto­ mated systems for query diagnosis. ![Image](https://ijcai.org/proceedings/1995/fulltext/265/image_000001_9e7c395cf0f1095309dd48caa2a207c4566859b2d88e6846690d4a3b0719010a.png) Figure 2 shows an example run on a query about auto­ mated systems for medical diagnosis, run over the ZIFF portion of the TIPSTER collection. Each large rectangle indicates a document, and each square within the docu­ ment represents a coherent text segment. The darker the segment, the more frequent the term (white indicates 0, black indicates 8 or more hits, the frequencies of all the terms within a term set are added together). The top row of each rectangle correspond to the hits for Term Set 1, the middle row to hits of Term Set 2, and the bottom row to hits of Term Set 3. The first column of each rect­ angle corresponds to the first segment of the document, the second column to the second segment, and so on. The TileBars representation allows the user to sort the retrieved documents according to which aspects of the query are most important. For example, in the figure the query is formulated as: (patient OR medicine OR medical) AND (test OR scan OR cure OR diagnosis) AND (software OR program). This formulation allows the interface to indicate the role played by each concep­ tual part of the query: the medical terms, the diagnosis terms, and the software terms. In Figure 2, the user has indicated that the diagnosis aspect of the query must be strongly present in the retrieved documents, by set­ ting the minimum term distribution percentage to 30% for the second termset. The document whose title begins "VA automation means faster admissions" is quite likely to be relevant to the query, and has all three term sets well-distributed throughout. By contrast, the document whose title begins "It's hard to ghost bust a network ... " is about computer-aided diagnosis, but has only a pass­ ing reference to medical diagnosis, as can be seen by the graphical representation. If the user decides that med­ ical terms should be better represented, the constraint on this term set can be adjusted accordingly. Note that a system that simply ranks the documents does not make these kinds of distinctions available to the user. The graphical representation allows the users to rapidly assess the structure of the retrieved documents with respect to the query, to better aid their decisions about which documents to view, or how to refine the query. ## References 1. [Cutting et a/., 1992] Douglass R. Cutting, Jan 0. Ped- ersen, David Karger, and John W. Tukey. Scat- ter/Gather: A cluster-based approach to browsing large document collections. In Proceedings of the 15th Annual International ACM/SIGIR Conference, pages 318-329, Copenhagen, Denmark, 1992. 2. [Cutting et a/., 1993] Douglass R. Cutting, David Karger, and Jan Peder- sen. Constant interaction-time Scatter/Gather brows- ing of very large document collections. In Proceedings of the 16th Annual International ACM/SIGIR Con- ference, pages 126-135, Pittsburgh, PA, 1993. 3. [Harman, 1993] Donna Harman. Overview of the first Text REtrieval Conference. In Proceedings of the 16th Annual International ACM/SIGIR Conference, pages 36-48, Pittsburgh, PA, 1993. 4. Marti A. Hearst. Multi-paragraph seg- mentation of expository text. In Proceedings of the 32nd Meeting of the Association for Computational Linguistics, June 1994. 5. Marti A. Hearst. Tilebars: Visualiza- tion of term distribution information in full text in- formation access. In Proceedings of the A CM SIGCHI Conference on Human Factors in Computing Systems, Denver, CO, May 1995. ACM. 6. [Salton, 1988] Gerard Salton. Automatic text processing : the transformation, analysis, and retrieval of infor- mation by computer. Addison-Wesley, Reading, MA, 1988.