HCI Bibliography Home | HCI Journals | About TOIS | Journal Info | TOIS Journal Volumes | Detailed Records | RefWorks | EndNote | Hide Abstracts
TOIS Tables of Contents: 030405060708091011121314151617181920212223

ACM Transactions on Information Systems 13

Editors:Robert B. Allen
Standard No:ISSN 1046-8188; HF S548.125 A33
Links:Table of Contents
  1. TOIS 1995 Volume 13 Issue 1
  2. TOIS 1995 Volume 13 Issue 2
  3. TOIS 1995 Volume 13 Issue 3
  4. TOIS 1995 Volume 13 Issue 4

TOIS 1995 Volume 13 Issue 1

Toward a Logical / Physical Theory of Spreadsheet Modeling BIBAKPDF 1-37
  Tomas Isakowitz; Shimon Schocken; Henry C., Jr. Lucas
In spite of the increasing sophistication and power of commercial spreadsheet packages, we still lack a formal theory or a methodology to support the construction and maintenance of spreadsheet models. Using a dual logical/physical perspective, we identify four principal components that characterize any spreadsheet model: schema, data, editorial, and binding. We present a factoring algorithm for identifying and extracting these components from conventional spreadsheets with minimal user intervention, and a synthesis algorithm that assists users in the construction of executable spreadsheets from reusable model components. This approach opens new possibilities for applying object-oriented and model management techniques to support the construction, sharing, and reuse of spreadsheet models in organizations. Importantly, our approach to model management and the Windows-based prototype that we have developed are designed to coexist with, rather than replace, traditional spreadsheet programs. In other words, the users are not required to learn a new modeling language; instead, their logical models and data sets are extracted from their spreadsheets transparently, as a side-effect of using standard spreadsheet programs.
Keywords: Information systems applications, Office automation, Spreadsheets, Information systems applications, Types of systems, Decision support, Simulation and modeling, Model validation and analysis, Simulation and modeling, Model development, Personal computing, Application packages, Spreadsheets, Design, Languages, Theory, Model management
On Modeling Information Retrieval with Probabilistic Inference BIBAKPDF 38-68
  S. K. M. Wong; Y. Y. Yao
This article examines and extends the logical models of information retrieval in the context of probability theory. The fundamental notions of term weights and relevance are given probabilistic interpretations. A unified framework is developed for modeling the retrieval process with probabilistic inference. This new approach provides a common conceptual and mathematical basis for many retrieval models, such as the Boolean, fuzzy set, vector space, and conventional probabilistic models. Within this framework, the underlying assumptions employed by each model are identified, and the inherent relationships between these models are analyzed. Although this article is mainly a theoretical analysis of probabilistic inference for information retrieval, practical methods for estimating the required probabilities are provided by simple examples.
Keywords: Models and principles, Systems and information theory, Information theory, Information storage and retrieval, Content analysis and indexing, Indexing methods, Information storage and retrieval, Information search and retrieval, Query formulation, Retrieval models, Artificial intelligence, Deduction and theorem proving, Uncertainty, "fuzzy," and probabilistic reasoning, Theory, Boolean model, Document representation, Fuzzy set model, Maximum and minimum entropy principles, Probabilistic inference, Probabilistic model, Relevance, Similarity measures, Subjective probability, Uncertain implications, Vector space model
From Text to Hypertext by Indexing BIBAKPDF 69-99
  Airi Salminen; Jean Tague-Sutcliffe; Charles McClellan
A model is presented for converting a collection of documents to hypertext by means of indexing. The documents are assumed to be semistructured, i.e., their text is a hierarchy of parts, and some of the parts consist of natural language. The model is intended as a framework for specifying hypertextual reading capabilities for specific application areas and for developing new automated tools for the conversion of semistructured text to hypertext. In the model, two well-known paradigms -- formal grammars and document indexing -- are combined. The structure of the source text is defined by a schema that is a constrained context-free grammar. The hierarchic structure of the source may thus be modeled by a parse tree for the grammar. The effect of indexing is described by grammar transformations. The new grammar, called an indexing schema, is associated with a new parse tree where some text parts are index elements. The indexing schema may hide some parts of the original documents or the structure of some parts. For information retrieval, parts of the indexed text are considered to be nodes of a hypergraph. In the hypergraph-based information access, the navigation capabilities of hypertext systems are combined with the querying capabilities of information retrieval systems.
Keywords: Mathematical logic and formal languages, Formal languages, Classes defined by grammars or automata, Database management, Logical design, Data models, Information storage and retrieval, Content analysis and indexing, Indexing methods, Information storage and retrieval, Information storage, Information storage and retrieval, Information search and retrieval, Retrieval models Design, Management, Theory, Constrained grammars, Grammars, Hypertext, Properties, Structured text, Text entities, Text types, Transient hypergraphs
Some Inconsistencies and Misidentified Modeling Assumptions in Probabilistic Information Retrieval BIBAKPDF 100-111
  William S. Cooper
Research in the probabilistic theory of information retrieval involves the construction of mathematical models based on statistical assumptions. One of the hazards inherent in this kind of theory construction is that the assumptions laid down may be inconsistent in unanticipated ways with the data to which they are applied. Another hazard is that the stated assumptions may not be those on which the derived modeling equations or resulting experiments are actually based. Both kinds of mistakes have been made in past research on probabilistic information retrieval. One consequence of these errors is that the statistical character of certain probabilistic IR models, including the so-called Binary Independence model, has been seriously misapprehended.
Keywords: Models and principles, User/machine systems, Information storage and retrieval, General, Information storage and retrieval, Information search and retrieval, Retrieval models, Experimentation, Measurement, Performance, Theory, Assumptions, Bibliographic searching, Consistency, Document retrieval, Independence, Logic, Modeling

TOIS 1995 Volume 13 Issue 2

Design and Evaluation of Algorithms for Image Retrieval by Spatial Similarity BIBAKPDF 115-144
  Venkat N. Gudivada; Vijay V. Raghavan
Similarity-based retrieval of images is an important task in many image database applications. A major class of users' requests requires retrieving those images in the database that are spatially similar to the query image. We propose an algorithm for computing the spatial similarity between two symbolic images. A symbolic image is a logical representation of the original image where the image objects are uniquely labeled with symbolic names. Spatial relationships in a symbolic image are represented as edges in a weighted graph referred to as spatial-orientation graph. Spatial similarity is then quantified in terms of the number of, as well as the extent to which, the edges of the spatial-orientation graph of the database image conform to the corresponding edges of the spatial-orientation graph of the query image.
   The proposed algorithm is robust in the sense that it can deal with translation, scale, and rotational variances in images. The algorithm has quadratic time complexity in terms of the total number of objects in both the database and query images. We also introduce the idea of quantifying a system's retrieval quality by having an expert specify the expected rank ordering with respect to each query for a set of test queries. This enables us to assess the quality of algorithms comprehensively for retrieval in image databases. The characteristics of the proposed algorithm are compared with those of the previously available algorithms using a testbed of images. The comparison demonstrated that our algorithm is not only more efficient but also provides a rank ordering of images that consistently matches with the expert's expected rank ordering.
Keywords: Information storage and retrieval, Information search and retrieval, Selection process, Information interfaces and presentation, Multimedia information systems, Pattern recognition, Clustering, Similarity measures, Algorithms, Image databases, Image retrieval, Image retrieval systems, Rotational invariance, Spatial similarity
Feedback Techniques for Continuity and Synchronization in Multimedia Information Retrieval BIBAKPDF 145-176
  P. Venkat Rangan; Srinivas Ramanathan; Srihari Sampathkumar
Future advances in storage and networking technologies will make it feasible to build multimedia on-demand information servers capable of providing services similar to those of a neighborhood videotape rental store over metropolitan area networks. Such multimedia information servers must not only support retrieval of continuous media units (such as video frames and audio samples), but also preserve synchrony among playback of the different media components constituting a multimedia object. We develop techniques for supporting continuous and synchronous retrieval from multimedia servers. We present feedback techniques by which, during retrieval of multimedia objects from a multimedia server to mediaphones, the multimedia server uses lightweight messages called feedback units transmitted periodically back to it (by mediaphones) to detect impending discontinuities as well as asynchronies at mediaphones. The multimedia server then preventively readjusts media transmission so as to avoid either anomaly, and steers the mediaphones back to synchrony. Given the available buffer sizes at mediaphones and the maximum tolerable asynchrony, we present methods to determine the minimum rate at which feedback units must be transmitted so as to maintain both continuity and synchronization. These feedback techniques remain robust even in the presence of playback rate mismatches and network delay jitter, and their initial simulation for video-audio playback yields a feedback rate of one per 1,000 media units to keep the asynchrony within 250ms, showing that the overhead due to feedback transmission is very small. The constant rate feedback techniques developed in this article form the basis of a prototype on-demand information server being developed at the UCSD Multimedia Laboratory.
Keywords: Computer-communication networks, Network architecture and design, ISDN (Integrated Services Digital Network), Information storage and retrieval, Systems and software, Information networks, Information systems applications, Communications applications, Information interfaces and presentation, Multimedia information systems, Design, Experimentation, Performance, Intermedia synchronization, Intramedia continuity, Multimedia, Multimedia on-demand information services, Synchronization
Experiments with Oval: A Radically Tailorable Tool for Cooperative Work BIBAKPDF 177-205
  Thomas W. Malone; Kum-Yew Lai; Christopher Fry
This article describes a series of tests of the generality of a "radically tailorable" tool for cooperative work. Users of this system can create applications by combining and modifying four kinds of building blocks: objects, views, agents, and links. We found that user-level tailoring of these primitives can provide most of the functionality found in well-known cooperative work systems such as gIBIS, Coordinator, Lotus Notes, and Information Lens. These primitives, therefore, appear to provide an elementary "tailoring language" out of which a wide variety of integrated information management and collaboration applications can be constructed by end users.
Keywords: Programming techniques, Visual programming, Programming languages, Language classifications, Very high-level languages, Models and principles, User/machine systems, Information systems applications, Office automation, Information systems applications, Communications applications, Information interfaces and presentation, User interfaces, Evaluation/methodology, Interaction styles, User interface management systems, Information interfaces and presentation, Group and organization interfaces, Experimentation, Human factors, Languages, Computer-supported cooperative work, End-user programming, Groupware, Radical tailorability
Exceptions and Exception Handling in Computerized Information Processes BIBAKPDF 206-233
  Diane M. Strong; Steven M. Miller
Exceptions, situations that cannot be correctly processed by computer systems, occur frequently in computer-based information processes. Five perspectives on exceptions provide insights into why exceptions occur and how they might be eliminated or more efficiently handled. We investigate these perspectives using an in-depth study of an operating information process that has frequent exceptions. Our results support the use of a total quality management (TQM) approach of eliminating exceptions for some exceptions, in particular, those caused by computer systems that are poor matches to organizational processes. However, some exceptions are explained better by a political system perspective of conflicting goals between subunits. For these exceptions and several other types, designing an integrated human-computer process will provide better performance than will eliminating exceptions and moving toward an entirely automated process.
Keywords: Artificial intelligence, Applications and expert systems, Industrial automation, Office automation, Computer applications, Administrative data processing, Business, Computers and society, Organizational impacts, Management of computing and information systems, Installation management, Performance and usage measurement, Management of computing and information systems, System management, Quality assurance, Design, Management, Performance, Exceptions, Exception handling, Process design, Total Quality Management (TQM)

TOIS 1995 Volume 13 Issue 3

Charter BIBA 235
  Robert B. Allen
The ACM Transactions on Information Systems (TOIS) considers the design, performance, and evaluation of computer systems that facilitate the presentation of information in a variety of media, as well as underlying technologies that support these systems. The major themes of TOIS and those topics which distinguish it from other ACM Transactions include:
  • - Information Retrieval and Information Filtering: Algorithms and inference
       mechanisms for search, retrieval, and presentation of information and models
       of user information preferences.
  • - Information Interfaces: Hypertext and hypermedia interfaces, information
       visualization, multimedia presentation, and task and user models for
       information systems.
  • - Natural Language Processing: Computational linguistics and models of natural
       language (including content, syntax, semantics, and dialogue) relevant to
       information systems.
  • - Knowledge and Information Representation: Representation issues for
       supporting information systems including semantic and object-oriented
       databases, knowledge bases, and hypertext/hypermedia document models.
  • - Multimedia Information Systems: Semantics, search, and presentation of media
       including audio, image, video, and virtual reality.
  • - Networked Information Systems: Interfaces and indexing, resource discovery,
       and visualization.
  • - Organizational Interfaces and Social Impact of Information Systems:
       Electronic mail; decision and negotiation support systems; the effects of
       information system use on groups, organizations, and communities; social
       constraints imposed on information systems such as legal and privacy
  • - Design and Evaluation of Information Systems: Design principles for
       information systems, methodologies for evaluating information systems, and
       programming languages relevant to information systems.
  • - Information System Applications: Electronic books, documents, journals,
       movies, and libraries; authoring systems; office information systems;
       geographic information systems; and intelligent tutoring systems.
  • Knowledge-Based Document Retrieval in Office Environments: The Kabiria System BIBAKPDF 237-268
      Augusto Celentano; Maria Grazia Fugini; Silvano Pozzi
    In the off1ce environment, the retrieval of documents is performed using the concepts contained in the documents, information about the procedural context where the documents are used, and information about the regulations and laws that discipline the life of documents within a given application domain. To fulfill the requirements of such a sophisticated retrieval, we propose a document retrieval model and system based on the representation of knowledge describing the semantic contents of documents, the way in which the documents are managed by procedures and by people in the office, and the application domain where the office operates. The article describes the knowledge representation issues needed for the document retrieval system and presents a document retrieval model that captures these issues. The effectiveness of the approach is illustrated by describing a system, named Kabiria, built on top of such model. The article describes the querying and browsing environments, and the architecture of the system.
    Keywords: Software engineering, Tools and techniques, User interfaces, Models and principles, General, Information storage and retrieval, Information search and retrieval, Query formulation, Retrieval models, Search process, Artificial intelligence, Applications and expert systems, Office automation, Artificial intelligence, Knowledge representation formalisms and methods, Semantic networks, Artificial intelligence, Programming languages and software, Expert system tools and techniques, Design, Languages, Browser, Class, Hypertext, Instance, Knowledge base, Link, Object orientation, User interface
    Templar: A Knowledge-Based Language for Software Specifications Using Temporal Logic BIBAKPDF 269-304
      Alexander Tuzhilin
    A software specification language Templar is defined in this article. The development of the language was guided by the following objectives: requirements specifications written in Templar should have a clear syntax and formal semantics, should be easy for a systems analyst to develop and for an end-user to understand, and it should be easy to map them into a broad range of design specifications. Templar is based on temporal logic and on the Activity-Event-Condition-Activity model of a rule which is an extension of the Event-Condition-Activity model in active databases. The language supports a rich set of modeling primitives, including rules, procedures, temporal logic operators, events, activities, hierarchical decomposition of activities, parallelism, and decisions combined together into a cohesive system.
    Keywords: Software engineering, Requirements/specifications, Languages, Methodologies, Software engineering, Design methodologies, Representation Models and principles, General, Artificial intelligence, Knowledge representation formalisms and methods, Representation languages, Temporal logic, Design, Languages, Activities, Events, Rule-based systems, Specification languages, Temporal logic, Time
    Fractal Views: A Fractal-Based Method for Controlling Information Display BIBAKPDF 305-323
      Hideki Koike
    Computer users often must view large amounts of information through video displays which are physically limited in size. Although some methods, which automatically display/erase information units based on their degrees of importance, have been proposed, they lack an ability to keep the total amount of displayed information nearly constant. We propose a new method for information display based on fractal theory. By regarding the information structures used in computers as complex objects, we can abstract these objects as well as control their amount. Using our method, (1) the total amount of information is kept nearly constant even when users change their focuses of attention and (2) this amount can be set flexibly. Through mathematical analysis, we show our method's ability to control the amount. An application to program display is also shown. When this method is applied to the display of structured programs, it provides fisheye-like views which integrate local details around the focal point and major landmarks further away.
    Keywords: Software engineering, Coding, Pretty printers, Models and principles, User/machine systems, Human factors, Human information processing, Information interfaces and presentation, User interfaces, Screen design, Theory and methods, Computer graphics, Methodology and techniques, Text processing, Document preparation, Format and notation, Hypertext/hypermedia, Algorithms, Abstracting methods, Fractals, Information visualization, Program display, UI theory
    A Network Approach to Probabilistic Information Retrieval BIBAKPDF 324-353
      K. L. Kwok
    In this article we show how probabilistic information retrieval based on document components may be implemented as a feedforward (feedbackward) artificial neural network. The network supports adaptation of connection weights as well as the growing of new edges between queries and terms based on user relevance feedback data for training, and it reflects query modification and expansion in information retrieval. A learning rule is applied that can also be viewed as supporting sequential learning using a harmonic sequence learning rate. Experimental results with four standard small collections and a large Wall Street Journal collection (173,219 documents) show that performance of feedback improves substantially over no feedback, and further gains are obtained when queries are expanded with terms from the feedback documents. The effect is much more pronounced in small collections than in the large collection. Query expansion may be considered as a tool for both precision and recall enhancement. In particular, small query expansion levels of about 30 terms can achieve most of the gains at the low-recall high-precision region, while larger expansion levels continue to provide gains at the high-recall low-precision region of a precision recall curve.
    Keywords: Information storage and retrieval, Content analysis and indexing, Indexing methods, Information storage and retrieval, Information search and retrieval, Retrieval models, Experimentation, Artificial neural networks, Document-focused and query-focused relevance feedback, Indexing and retrieval, Item self-learning, Learning, Probabilistic indexing, Probabilistic retrieval, Query expansion, Training
    On Deductive Databases with Incomplete Information BIBAKPDF 354-369
      Q. Kong; G. Chen
    In order to extend the ability to handle incomplete information in a definite deductive database, a Horn clause-based system representing incomplete information as incomplete constants is proposed. By using the notion of incomplete constants the deductive database system handles incomplete information in the form of sets of possible values, thereby giving more information than null values. The resulting system extends Horn logic to express a restricted form of indefiniteness. Although a deductive database with this kind of incomplete information is, in fact, a subset of an indefinite deductive database system, it represents indefiniteness in terms of value incompleteness, and therefore it can make use of the existing Horn logic computation rules. The inference rules for such a system are presented, its model theory discussed, and a model theory of indefiniteness proposed. The theory is consistent with minimal model theory and extends its expressive power.
    Keywords: Models and principles, Systems and information theory, Information theory, Database management, Systems, Query processing, Artificial intelligence, Deduction and theorem proving, Logic programming, Design, Management, Theory, Deductive databases, Horn clause, Incomplete information, Prolog, Query evaluation

    TOIS 1995 Volume 13 Issue 4

    Special Issue on Video Information Retrieval

    Introduction to the Special Issue on Video Information Retrieval BIBPDF 371-372
      Scott Stevens; Thomas Little
    A Video Retrieval and Sequencing System BIBAKPDF 373-407
      Tat-Seng Chua; Li-Qun Ruan
    Video is an effective medium for capturing the events in the real world around us, and a vast amount of video materials exists, covering a wide range of applications. However, widespread use of video in computer applications is often impeded by the lack of effective tools to manage video information systematically. This article discusses the design and implementation of a frame-based video retrieval and sequencing system (VRSS). The system is designed to support the entire process of video information management: segmenting, indexing, retrieving, and sequencing of video data. A semiautomatic tool is developed to divide video sequences into meaningful shots. Each video shot is logged using text descriptions, audio dialogue, and cinematic attributes. A two-layered, concept-based model is used as the basis for accurately retrieving relevant video shots based on users' free-text queries. A cinematic, rule-based, virtual editing tool is also developed to sequence the video shots retrieved for presentation within a specified time constraint. The system has been tested on a video documentary on the NUS (National University of Singapore) engineering faculty. The results of video retrieval experiments are encouraging.
    Keywords: Information storage and retrieval, General, Information interfaces and presentation, Multimedia information systems, Artificial intelligence, Knowledge representation formalisms and methods, Experimentation, Cinematic rules, Frame-based modeling, Multimedia, Video retrieval, Virtual editing
    Motion Recovery for Video Content Classification BIBAKPDF 408-439
      Nevenka Dimitrova; Forouzan Golshani
    Like other types of digital information, video sequences must be classified based on the semantics of their contents. A more-precise and completer extraction of semantic information will result in a more-effective classification. The most-discernible difference between still images and moving pictures stems from movements and variations. Thus, to go from the realm of still-image repositories to video databases, we must be able to deal with motion. Particularly, we need the ability to classify objects appearing in a video sequence based on their characteristics and features such as shape or color, as well as their movements. By describing the movements that we derive from the process of motion analysis, we introduce a dual hierarchy consisting of spatial and temporal parts for video sequence representation. This gives us the flexibility to examine arbitrary sequences of frames at various levels of abstraction and to retrieve the associated temporal information (say, object trajectories) in addition to the spatial representation. Our algorithm for motion detection uses the motion compensation component of the MPEG video-encoding scheme and then computes trajectories for objects of interest. The specification of a language for retrieval of video based on the spatial as well as motion characteristics is presented.
    Keywords: Information storage and retrieval, Information search and retrieval, Information interfaces and presentation, Multimedia information systems, Artificial intelligence, Vision and scene understanding, Motion, Algorithms, Design, Content-based retrieval of video, Motion recovery, MPEG compressed video analysis, Video databases, Video retrieval
    Embedded Video in Hypermedia Documents: Supporting Integration and Adaptive Control BIBAKPDF 440-470
      Dick C. A. Bulterman
    As the availability of digital video becomes commonplace, a shift in application focus will occur from merely accessing video as an independent data stream to embedding video with other multimedia data types into coordinated hypermedia presentations. The migration to embedded video will present new demands on application and support environments: processing of any one piece of video data will depend on how that data relates to other data streams active within the same presentation. This article describes presentation, synchronization, and interaction control issues for manipulating embedded video. First we describe the requirements for embedded video, contrasted against other forms of video use. Next we consider mechanisms for describing and implementing the behavior of embedded-video segments relative to other data items in a document; these relationships form the basis of implementing cooperative control among the events in a presentation. Finally we consider extending the possibilities for tailoring embedded video to the characteristics of the local runtime environment; this forms the basis for adaptive, application-level quality-of-service control of a presentation. In all cases, we describe a mechanism to externalize the behavior of hypermedia presentations containing resource-intensive data requirements so that effective control can be implemented by low-level system facilities based on application-specific requirements. We present our results in terms of the CMIFed authoring/presentation system.
    Keywords: Information interfaces and presentation, Multimedia information systems, Video, Text processing, Document preparation, Multi/mixed media, Algorithms, Design, Experimentation, Adaptive control, Embedded video, Hypermedia documents, Multimedia, Synchronization, Video presentation
    XMovie: Architecture and Implementation of a Distributed Movie System BIBAKPDF 471-499
      Ralf Keller; Wolfgang Effelsberg; Bernd Lamparter
    We describe a system for storing, transmitting, and presenting digital movies in a computer network. The hardware used in the system is standard hardware, as found in typical workstations today; no special hardware is required, but if available it can be used to provide better performance. The XMovie system has several innovative features. First, it contains a new algorithm for the gradual adaptation of the color lookup table during the presentation of the movie to ensure optimal color quality on low-end workstations. Second, it is a multistandard system supporting the compression techniques MPEG, Motion JPEG, and a newly developed extension to the well-known Color Cell Compression method. Third, it contains AdFEC, a new adaptable forward error correction method for our movie transmission protocol.
    Keywords: Computer-communications networks, Network protocols, Protocol architecture, Computer-communications networks, Distributed systems, Distributed applications, Information interfaces and presentation, Multimedia information systems, Video (e.g., tape, disk, DVI), Information interfaces and presentation, User interfaces, Windowing systems, Image processing, Compression (coding), Approximate methods, Algorithms, Performance, Digital video, Distributed multimedia system, Software motion picture, Transmission protocol