| Optimal Placement of High-Probability Randomly Retrieved Blocks on CLV Optical Discs | | BIBAK | PDF | 1-30 | |
| Daniel Alexander Ford; Stavros Christodoulakis | |||
| Optimal data placement on a CLV (Constant Linear Velocity) format optical
disc has as an objective the minimization of the expected access cost of data
retrieval from the disc when the probabilities of access of data items may be
different. The problem of optimal data placement for optical discs is both
more important and more difficult than the corresponding problem on magnetic
disks. A good data placement on optical discs is more important because data
sets on optical discs such as WORM and CD ROM cannot be modified or moved once
they are placed on the disc. Currently, even rewritable optical discs are best
suited for applications that are archival in nature. The problem of optimal
data placement on CLV format optical discs is more difficult, mainly because
the useful storage space is not uniformly distributed across the disc surface
(along a radius). This leads to a complicated positional performance trade-off
not present for magnetic disks.
We present a model that encompasses all the important aspects of the placement problem on CLV format optical discs. The model takes into account the nonuniform distribution of useful storage, the dependency of the rotational delay on disc position, a parameterized seek cost function for optical discs, and the varying access probabilities of data items. We show that the optimal placement of high-probability blocks satisfies a unimodality property. Based on this observation, we solve the optimal placement problem. We then study the impact of the relative weights of the problem parameters and show that the optimal data placement may be very different from the optimal data placement on magnetic disks. We also validate our model and analysis and give an algorithm for computing the placement of disc sectors. Keywords: Memory structures, Design styles, Mass storage, Operating systems, Storage
management, Secondary storage devices, Database management, Physical design,
Access methods, Information storage and retrieval, Information search and
retrieval, Clustering, Design, Management, Performance, CD-ROM, CLV, Constant
linear velocity, Data placement, MCAV, MCLV, Optical discs, Optical disks,
Physical database design, Retrieval performance | |||
| A Distributed Object-Oriented Database System Supporting Shared and Private Databases | | BIBAK | PDF | 31-51 | |
| Won Kim; Nat Ballou; Jorge F. Garza; Darrell Woelk | |||
| ORION-2 is a commercially available, federated, object-oriented database
management system designed and implemented at MCC. One major architectural
innovation in ORION-2 is the coexistence of a shared database and a number of
private databases. The shared database is accessible to all authorized users
of the system, while each private database is accessible to only the user who
owns it. A distributed database system with a shared database and private
databases for individual users is a natural architecture for data-intensive
application environments on a network of workstations, notably computer-aided
design and engineering systems. This paper discusses the benefits and
limitations of such a system and explores the impact of such an architecture on
the semantics and implementation of some of the key functions of a database
system, notably queries, database schema, and versions. Although the issues
are discussed in the context of an object-oriented data model, the results (at
least significant portions thereof) are applicable to database systems
supporting other data models. Keywords: Database management, Systems, Distributed systems, Design, Experimentation,
Client-server architecture, Federated databases, Object-oriented databases | |||
| Exploiting Parallelism in Pattern Matching: An Information Retrieval Application | | BIBAK | PDF | 52-74 | |
| Victor Wing-Kit Mak; Kuo Chu Lee; Ophir Frieder | |||
| We propose a document-searching architecture based on high-speed hardware
pattern matching to increase the throughput of an information retrieval system.
We also propose a new parallel VLSI pattern-matching algorithm called the Data
Parallel Pattern Matching (DPPM) algorithm, which serially broadcasts and
compares the pattern to a block of data in parallel. The DPPM algorithm
utilizes the high degree of integration of VLSI technology to attain very
high-speed processing through parallelism. Performance of the DPPM has been
evaluated both analytically and by simulation. Based on the simulation
statistics and timing analysis on the hardware design, a search rate of
multiple gigabytes per second is achievable using 2-µm CMOS technology.
The potential performance of the proposed document-searching architecture is
also analyzed using the simulation statistics of the DPPM algorithm. Keywords: Arithmetic and logic structures, Design styles, Parallel, Integrated
circuits, Types and design styles, Algorithms implemented in hardware, VLSI,
Processor architectures, Multiple data stream architecture, SIMD, Computer
systems organization, Performance of systems, Design studies, Modeling
techniques, Data, Files, Sorting/searching, Analysis of algorithms and problem
complexity, Nonnumerical algorithms and problems, Pattern matching, Sorting and
searching, Information storage and retrieval, Information search and retrieval,
Search process, Selection process, Algorithms, Design, Performance, DPPM,
Pattern matcher | |||
| Integrating Expert Systems with Group Decision Support Systems | | BIBAK | PDF | 75-95 | |
| Milam W. Aiken; Olivia R. Liu Sheng; Douglas R. Vogel | |||
| Expert systems are powerful tools that serve as adjuncts to decision making
and have found wide applicability in a variety of areas. Integrating expert
systems with group decision support systems has the potential to enhance the
quality and efficiency of group communication, negotiation, and collaborative
work. This paper examines possible synergies between the two technologies and
provides a survey of current partially-integrated systems. Finally, a
prototype design of a highly-integrated system is described with directions for
further research. Keywords: Information systems applications, Communications applications, Artificial
intelligence, Applications and expert systems, Expert systems, Group decision
support systems, Artificial intelligence, Expert systems, Group decision
support systems, Knowledge-based systems | |||
| Computer-Human Interaction and ACM TOIS | | BIB | 97 | |
| Bob Allen | |||
| A Morphological Analysis of the Design Space of Input Devices | | BIBAK | PDF | 99-122 | |
| Stuart K. Card; Jock D. Mackinlay; George G. Robertson | |||
| The market now contains a bewildering variety of input devices for
communication from humans to computers. This paper discusses a means to
systematize these devices through morphological design space analysis, in which
different input device designs are taken as points in a parametrically
described design space. The design space is characterized by finding methods
to generate and test design points. In a previous paper, we discussed a method
for generating the space of input device designs using primitive and
compositional movement operators. This allowed us to propose a taxonomy of
input devices. In this paper, we summarize the generation method and explore
the use of device footprint and Fitts's law as a test. We then use
calculations to reason about the design space. Calculations are used to show
why the mouse is a more effective device than the headmouse and where in the
design space there is likely to be a more effective device than the mouse. Keywords: Models and principles, User/machine systems, Human factors, Computer
applications, Computer-aided engineering, Computer-aided design, Design, Human
factors, Design knowledge systematization, Design rationale, Design space,
Input devices, Morphological analysis, Semantics | |||
| The Role of Critiquing in Cooperative Problem Solving | | BIBAK | PDF | 123-151 | |
| Gerhard Fischer; Andreas C. Lemke; Thomas Mastaglio; Anders I. Morch | |||
| Cooperative problem-solving systems help users design solutions themselves
as opposed to having solutions designed for them. Critiquing -- presenting a
reasoned opinion about a user's product or action -- is a major activity of a
cooperative problem-solving system. Critics make the constructed artifact
"talk back" to the user. Conditions under which critics are more appropriate
than autonomous expert systems are discussed. Critics should be embedded in
integrated design environments along with other components, such as an
argumentative hypertext system, a specification component, and a catalog.
Critics support learning as a by-product of problem solving. The major
subprocesses of critiquing are goal acquisition, product analysis, critiquing
strategies, adaptation capability, explanation and argumentation, and advisory
capability. The generality of the critiquing approach is demonstrated by
discussing critiquing systems developed in our group and elsewhere.
Limitations of many current critics include their inability to learn about
specific user goals and their intervention strategies. Keywords: Models and principles, User/machine systems, Human factors, Information
storage and retrieval, Information search and retrieval, Computer applications,
Computer-aided engineering, Computer-aided design, Computers and education,
Computer uses in education, Design, Human factors, Cooperative problem-solving
systems, Critics, Critiquing, Design environments, High-functionality computer
systems, Intelligent support systems | |||
| The Use of Eye Movements in Human-Computer Interaction Techniques: What You Look At is What You Get | | BIBAK | PDF | 152-169 | |
| Robert J. K. Jacob | |||
| In seeking hitherto-unused methods by which users and computers can
communicate, we investigate the usefulness of eye movements as a fast and
convenient auxiliary user-to-computer communication mode. The barrier to
exploiting this medium has not been eye-tracking technology but the study of
interaction techniques that incorporate eye movements into the user-computer
dialogue in a natural and unobtrusive way. This paper discusses some of the
human factors and technical considerations that arise in trying to use eye
movements as an input medium, describes our approach and the first eye
movement-based interaction techniques that we have devised and implemented in
our laboratory, and reports our experiences and observations on them. Keywords: Software engineering, Tools and techniques, User interfaces, Models and
principles, User/machine systems, Human factors, Information interfaces and
presentation, User interfaces, Input devices and strategies, Interaction
styles, User interface management system, Design, Human factors, Eye movements,
Eye tracking, Human-computer interaction, State transition diagram, UIMS, Input | |||
| VideoDraw: A Video Interface for Collaborative Drawing | | BIBAK | PDF | 170-184 | |
| John C. Tang; Scott L. Minneman | |||
| This paper describes VideoDraw, a shared drawing tool, and the process by
which it is being designed and developed. VideoDraw is a video-based prototype
tool that provides a shared "virtual sketchbook" among two or more
collaborators. It not only allows the collaborators to see each others'
drawings, but also conveys the accompanying hand gestures and the process of
creating and using those drawings. Its design stems from studying how people
collaborate using shared drawing spaces. Design implications raised by those
studies were embodied in a prototype, which was subsequently observed in use
situations. Further research studying the use of VideoDraw (in comparison with
other collaborative media) will lead to a better understanding of collaborative
drawing activity and inform the continued technical development of tools to
support collaborative drawing. Keywords: Computer-communication networks, Distributed systems, Distributed
applications, Information systems applications, Communications applications,
Teleconferencing, Computer graphics, Graphics systems, Distributed/network
graphics, Design, Collaborative systems, Gestural interfaces, Shared drawing,
User interface, Video technology, Work practice analysis | |||
| Editorial | | BIB | 185 | |
| W. Bruce Croft | |||
| Evaluation of an Inference Network-Based Retrieval Model | | BIBAK | PDF | 187-222 | |
| Howard Turtle; W. Bruce Croft | |||
| The use of inference networks to support document retrieval is introduced.
A network-based retrieval model is described and compared to conventional
probabilistic and Boolean models. The performance of a retrieval system based
on the inference network model is evaluated and compared to performance with
conventional retrieval models. Keywords: Information storage and retrieval, General, Information storage and
retrieval, Information search and retrieval, Retrieval models, Information
storage and retrieval, Miscellaneous, Experimentation, Performance, Theory,
Document retrieval, Inference networks, Network retrieval models | |||
| A Probabilistic Learning Approach for Document Indexing | | BIBAK | PDF | 223-248 | |
| Norbert Fuhr; Chris Buckley | |||
| We describe a method for probabilistic document indexing using relevance
feedback data that has been collected from a set of queries. Our approach is
based on three new concepts: (1) Abstraction from specific terms and documents,
which overcomes the restriction of limited relevance information for parameter
estimation. (2) Flexibility of the representation, which allows the
integration of new text analysis and knowledge-based methods in our approach as
well as the consideration of document structures or different types of terms.
(3) Probabilistic learning or classification methods for the estimation of the
indexing weights making better use of the available relevance information. Our
approach can be applied under restrictions that hold for real applications. We
give experimental results for five test collections which show improvements
over other methods. Keywords: Numerical analysis, Approximation, Least squares approximation, Information
storage and retrieval, Content analysis and indexing, Indexing methods,
Information storage and retrieval, Information search and retrieval, Retrieval
models, Artificial intelligence, Learning, Parameter learning, Experimentation,
Theory, Complex document representation, Linear indexing functions, Linear
retrieval functions, Probablistic indexing, Probabilistic retrieval, Relevance
descriptions | |||
| Search Improvement via Automatic Query Reformulation | | BIBAK | PDF | 249-280 | |
| Susan Gauch; John B. Smith | |||
| Users of online retrieval systems experience many difficulties, particularly
with search tactics. User studies have indicated that searchers use vocabulary
incorrectly and do not take full advantage of iteration to improve their
queries. To address these problems, an expert system for online search
assistance was developed. This prototype augments the searching capabilities
of novice users by providing automatic query reformulation to improve the
search results, and automatic ranking of the retrieved passages to speed the
identification of relevant information. Users' search performance using the
expert system was compared with their search performance on their own, and
their search performance using an online thesaurus. The following conclusions
were reached: (1) the expert system significantly reduced the number of queries
necessary to find relevant passages compared with the user searching alone or
with the thesaurus. (2) The expert system produced marginally significant
improvements in precision compared with the user searching on their own. There
was no significant difference in the recall achieved by the three system
configurations. (3) Overall, the expert system ranked relevant passages above
irrelevant passages. Keywords: Models and principles, User/machine system, Human factors, Information
storage and retrieval, Information search and retrieval, Search process,
Artificial intelligence, Applications and expert systems, Human factors, Expert
systems, Full-text information retrieval, Online search assistance, Query
reformulation, Textbases | |||
| Order-Preserving Minimal Perfect Hash Functions and Information Retrieval | | BIBAK | PDF | 281-308 | |
| Edward A. Fox; Qi Fan Chen; Amjad M. Daoud; Lenwood S. Heath | |||
| Rapid access to information is essential for a wide variety of retrieval
systems and applications. Hashing has long been used when the fastest possible
direct search is desired, but is generally not appropriate when sequential or
range searches are also required. This paper describes a hashing method,
developed for collections that are relatively static, that supports both direct
and sequential access. The algorithms described give hash functions that are
optimal in terms of time and hash table space utilization, and that preserve
any a priori ordering desired. Furthermore, the resulting order-preserving
minimal perfect hash functions (OPMPHFs) can be found using time and space that
are linear in the number of keys involved; this is close to optimal. Keywords: Data, Data storage representations, Hash table representations, Databased
management, Physical design, Access methods, Information storage and retrieval,
Content analysis and indexing, Indexing methods, Information storage and
retrieval, Information storage, File organization, Algorithms, Experimentation,
Dictionary structure, Indexing, Inverted file structures, Minimal perfect
hashing, Perfect hashing, Random graph | |||
| Computer Analysis of User Interfaces Based on Repetition in Transcripts of User Sessions | | BIBAK | PDF | 309-335 | |
| Antonio C. Siochi; Roger W. Ehrich | |||
| It is generally acknowledged that the production of quality user interfaces
requires a thorough understanding of the user and that this involves evaluating
the interface by observing the user working with the system, or by performing
human factors experiments. Such methods traditionally involve the use of
videotape, protocol analysis, critical incident analysis, etc. These methods
require time consuming analyses and may be invasive. In addition, the data
obtained through such methods represent a relatively small portion of the use
of a system. An alternative approach is to record all user input and system
output (i.e., log the user session). Such transcripts can be collected
automatically and noninvasively over a long period of time. Unfortunately this
produces voluminous amounts of data. There is therefore a need for tools and
techniques that allow an evaluator to identify potential performance and
usability problems from such data. It is hypothesized that repetition of user
actions is an important indicator of potential user interface problems.
This research reports on the use of the repetition indicator as a means of studying user session transcripts in the evaluation of user interfaces. The paper discusses the interactive tool constructed, the results of an extensive application of the technique in the evaluation of a large image-processing system, and extensions and refinements to the technique. Evidence suggests that the hypothesis is justified and that such a technique is convincingly useful. Keywords: Software engineering, Tools and techniques, User interfaces, Information
interfaces and presentation, User interfaces, Evaluation/methodology, Human
factors, Measurement, Maximal repeating patterns, Repeated usage patterns,
Transcript analysis, Usability, User interface evaluation, User interface
management systems | |||
| Dynamic Partitioning of Signature Files | | BIBAK | PDF | 336-369 | |
| P. Zezula; F. Rabitti; P. Tiberio | |||
| The signature file access method has proved to be a convenient indexing
technique, in particular for text data. Because it can deal with unformatted
data, many application domains have shown interest in signature file
techniques, e.g., office information systems, statistical and logic databases.
We argue that multimedia databases should also take advantage of this method,
provided convenient storage structures for organizing signature files are
available.
Our main concern here is the dynamic organization of signatures based on a partitioning paradigm called Quick Filter. A signature file is partitioned by a hashing function and the partitions are organized by linear hashing. Thorough performance evaluation of the new scheme is provided, and it is compared with single-level and multilevel storage structures. Results show that quick filter is economical in space and very convenient for applications dealing with large files of dynamic data, and where user queries result in signatures with high weights. These characteristics are particularly interesting for multimedia databases, where integrated access to attributes, text and images must be provided. Keywords: Data, Files, Organization / structure, Database management, Physical design,
Access methods, Information storage and retrieval, Information storage, File
organization, Information systems applications, Office automation, Design,
Performance, Access methods, Dynamic data, Hashing, Information retrieval,
Multimedia data, Performance evaluation, Signature file partitioning | |||
| Inter-Organization Networks, Computer Integration, and Shifts in Interdependence: The Case of the Semiconductor Industry | | BIBAK | PDF | 370-398 | |
| Paul Hart; Deborah Estrin | |||
| Inter-organization computer networks (IONs) provide significant
opportunities for improving coordination between firms engaged in mutually
dependent activities. A field study of the use and impact of IONs in the
semiconductor industry is presented in this paper. Eighty-two interviews were
conducted in twelve firms (seven semiconductor producers and five merchant mask
shops) providing data on current as well as anticipated ION use. We found that
greater efficiencies are possible when IONs are used as substitutes for
conventional media. But more effective ION use is achievable when internal
computer integration within participating firms is implemented. The
implication of this otherwise straightforward observation is that firms using
computer networks only as a substitute for conventional methods of exchange
will not achieve the degree of inter-organization coordination IONs can
support. However, while IONs improve coordination and reduce some production
and transaction costs, they simultaneously increase certain costs associated
with establishing and maintaining contracts with customers. These costs are
new dependencies. Dependencies emerge from using IONs to access computer
resources, and information generated by those resources, located in other
firms. In this way IONs increase interorganization coordination and
vulnerability simultaneously. The long term implication of ION adoption is
that their use shifts the nature of interdependence between participating
firms. Keywords: Integrated circuits, Types and design styles, Gate arrays, Standard cells,
Computer-communication networks, Network operations, Network management,
Computer system implementation, Miscellaneous, Information systems
applications, Communications applications, Electronic mail, Computer
applications, Computers in other systems, Consumer products, Computers and
society, Organizational impacts, Management of computing and information
systems, Project and people management, Systems development, Management,
Performance, Computer integration, Inter-organization computer networks,
Inter-organization relationships | |||
| PROXHY: A Process-Oriented Extensible Hypertext Architecture | | BIBAK | PDF | 399-419 | |
| Charles J. Kacmar; John J. Leggett | |||
| This paper describes the design and prototypical implementation of an
architecture for hypertext systems which is based on the process and
object-oriented models of computation. Hypertext services are provided to
applications through object-based distributed processes which interact using
interprocess communication facilities. By merging the process,
object-oriented, and hypertext models, hypertext data and functionality can be
separated from applications and distributed across a network. This
architecture allows links to cross application boundaries and diverse
applications to be integrated under a common hypertext model. The paper
describes the architecture and application requirements for operating in this
environment. PROXHY, a prototypical implementation of the architecture, is
also discussed. Keywords: Computer-communication networks, Distributed systems, Distributed
applications, Programming techniques, Object-oriented programming, Operating
systems, Organization and design, Distributed systems, Interactive system,
Database management, Systems, Distributed systems, Information storage and
retrieval, Systems and software, Information interfaces and presentation,
Multimedia information systems, Hypertext navigation and maps, Text processing,
Document preparation, Hypertext/hypermedia, Design, Management, Hypermedia
system architecture | |||