Copy Link
Add to Bookmark
Report
IRList Digest Volume 4 Number 45
IRList Digest Saturday, 27 August 1988 Volume 4 : Issue 45
Today's Topics:
Query - NY Times Collection
Abstracts - Dissertations selected by S. Humphrey [Part 2 of 5]
News addresses are
Internet: fox@fox.cs.vt.edu or fox%fox.cs.vt.edu@dcssvx.cc.vt.edu
BITNET: foxea@vtcc1.bitnet (replaces foxea@vtvax3)
----------------------------------------------------------------------
Date: Tue, 2 Aug 88 16:52 EDT
From: krovetz@UMass
Subject: NY Times test collection
Ed,
Bruce Croft told me you might know about a test collection of
articles from the NY Times. He said it was pretty small. Could
it be sent in a mail message?
Thanks,
Bob
[Note: There is an old collection used in some of the SMART
studies that might be available from Cornell - this is the
only one other than the big collections (probably without
queries) of NY Times documents made at several locations.
Let me know if you turn up something and we can put it on
Virginia Disc One (which is now almost ready!) - Ed]
------------------------------
Date: Wed, 3 Aug 88 13:36:58 EDT
From: "Susanne M. HUMPHREY" <humphrey@MCS.NLM.NIH.GOV>
Subject: dissertation abstracts [Note: Part 2 of 5 - Ed.]
.[
AN University Microfilms Order Number ADG87-29523.
AU YU, JUNG-PIN.
IN The University of Iowa Ph.D 1987, 203 pages.
TI LIBRARY SEARCHES OF INFRARED SPECTRA AND MULTICOMPONENT ANALYSIS.
DE Chemistry, Analytical.
AB Odd moments of the cross-correlation function and average
wavenumber methods are used for library searches. The absorbances
of a spectrum are represented by 24 values if the spectrum is
divided into twelve regions. The indirect spectral data base is
split into twelve subsets according to the spectral regions with
the most intense integrated intensities. Only several subsets are
used for a search. Several versions of integrated intensity
filters are applied to pre-select the library entries. The best
method of this work presently has about an 84% chance of locating
an experimental spectrum among the best five matches if this
spectrum is in the library and the correlation coefficient between
them is not less than 0.9000. The average search time per spectrum
is approximately 30 seconds with a Leading Edge Model D computer
equipped with an 8087 co-processor. The search results by the
correlation coefficient method are comapred, and the effects of
baseline shift, noise, and frequency shift are also investigated.
A factor analysis of n-component spectra generates n orthogonal
spectra. Proper combinations of any two of the abstract spectra
can eliminate one component and yield new spectra with n $-$ 1
components. The orthogonal spectra obtained by a factor analysis
of the newly generated spectra have n $-$ 1 components each.
Iterative subtraction processes finally resolved all pure
component spectra. A minimum entropy method and a minimum
pathlength method are used to evaluate the component elimination
procedures.
The relative component fractions of a sample with indeterminate
pathlength can be determined by using normalized pure component
spectra as references. The relative component fractions of a
mixture is constant for each component of all samples. Q matrix
and T matrix methods are investigated. Singular value
decomposition method is found to have utility in the spectral
reconstruction.
.]
.[
AN This item is not available from University Microfilms International
ADG05-62008.
AU CASAS-RAPOSO, IGNACIO ANTONIO.
IN University of Toronto (Canada) Ph.D 1986.
TI PROPHET: A LAYERED ANALYTICAL MODEL FOR PERFORMANCE PREDICTION OF
DATABASE SYSTEMS.
DE Computer Science.
AB The efficiency and performance of database systems is
substantially affected by many decisions which are required
throughout the development stages. Unfortunately, the impact on
performance of many design alternatives is not yet well
understood. In this thesis we propose an analytical performance
model of database systems that provides a means of quantitative
comparison of design alternatives. Four levels of abstraction are
distinguished for design choices, models of representation, and
related performance measures. Queuing network models are used at
the bottom, most concrete level. Several subproblems within the
layered framework are studied in detail including schema and
internal access plans models and a performance model for database
buffer management. We also extend and refine several existing
modeling techniques such as schema-to-internal database mappings
and models of internal database structures. All the proposed
submodels are integrated within a generalized framework for
database performance analysis, named PROPHET, with detailed models
of computation at the four layers of abstraction. The
applicability and feasibility of the framework is illustrated with
applications to several present-day commercial DBMSs, including
IMS, MISTRESS and SYSTEM 2000. We also describe the design and
implementation of a specialization of our generalized framework to
SYSTEM 2000 environments. We report preliminary results of the
validation of the SYSTEM 2000 performance predictor against data
measured in an actual operational environment.
.]
.[
AN University Microfilms Order Number ADG88-00136.
AU CHIN, YU-TUNG.
IN University of Rhode Island Ph.D 1987, 194 pages.
TI SYSTEM DESIGN AND IMPLEMENTATION OF A COMPUTERIZED RHODE ISLAND
WATER RESOURCES INFORMATION SYSTEM.
DE Computer Science.
AB Water resources data from various federal and state agencies of
Rhode Island were collected, analyzed and reorganized. The nature
of the data was studied. A conceptual model representing the
entities and relationships among the data was derived by means of
a semantic data model. The conceptual model was then mapped into a
logical file structure represented by a pseudo Data Definition
Language. A distributed configuration was chosen to implement the
database in order to achieve desired functional performance and
cost effectiveness. Finally, the logical structure was realized by
appropriate Database Management Systems in mainframe and personal
computers.
Programs were developed to support data entry as well as to
maintain integrity and security of the database. Applications of
the system in water resources decision-making and management were
demonstrated by examples.
.]
.[
AN This item is not available from University Microfilms International
ADG05-62262.
AU FALOUTSOS, CHRISTOS NICK.
IN University of Toronto (Canada) Ph.D 1986.
TI SIGNATURE FILES: AN ACCESS METHOD FOR TEXTUAL MESSAGES.
DE Computer Science.
AB Signature files seem to be a promising method for text retrieval
and message retrieval. According to this method the messages are
stored sequentially in one file ("text file") while abstractions
of the messages ("signatures") are stored sequentially in another
file ("signature file"). In order to resolve a query, the
signature file is scanned first and many non-qualifying messages
are immediately rejected. Those non-qualifying messages that pass
the signature test are called false drops and are undesirable.
Careful design of the signature extraction method and the
appropriate signature size can restrict the average number of
false drops. The screening capacity of some signature extraction
methods is examined analytically. New methods are proposed and
their performance is compared with one of the old methods.
Finally, the relationship between the false drop probability and
the information loss during the signature extraction is
investigated.
.]
.[
AN This item is not available from University Microfilms International
ADG05-61631.
AU ICAZA, JOSE IGNACIO.
IN University of Waterloo (Canada) Ph.D 1987.
TI ADAPTIVE SELECTION OF QUERY PROCESSING STRATEGIES.
DE Computer Science.
AB Approximate cost models that are traditionally needed to evaluate
query execution strategies are sometimes unavailable or too
unreliable for particular environments. Our new approach for
strategy selection is based on feeding back the actual costs of
query execution under different strategies, rather than on
assumptions-loaded estimates of these costs. We propose three
different methods for using these feedback costs, under a common
general framework for adaptive systems.
In optimal selection we define the problem of designing an optimal
decision policy for a single query class, where the policy
specifies which strategy to execute for each query. This problem
is mapped to some versions of the bandit problem in statistics,
which can be solved using bayesian statistics and dynamic
programming. We present and analyze a program that derives the
optimal policy.
In approximate selection we use a learning automaton to select
strategies. The learning algorithm by Thathachar and Sastry is
modified to handle the dynamic environments of databases. This
adaptive algorithm is tested using existing databases and query
loads, showing how this approach determines the best execution
strategies over time, and changes which strategies are selected as
the environment changes.
Finally, the method of query class partitioning considers the
problem of evolving optimal query partitionings, in which each
partition includes all queries that have a common optimal
strategy. We present a novel adaptive classification scheme that
uses several learning automata.
.]
.[
AN University Microfilms Order Number ADG88-04134.
AU KEARNS, TIMOTHY G.
IN Air Force Institute of Technology Ph.D 1987, 351 pages.
TI A METHODOLOGY, BASED ON ANALYTICAL MODELING, FOR THE DESIGN OF
PARALLEL AND DISTRIBUTED ARCHITECTURES FOR RELATIONAL DATABASE QUERY
PROCESSORS.
DE Computer Science.
AB The design of faster relational database query processors to
improve the data retrieval capability of a database was the goal
of this research. The emphasis was on evaluating the potential of
parallel implementations to allow use of multiprocessing. First,
the theoretical considerations of applying relational operations
to distributed data was considered to provide an underlying data
distribution and parallel processing environment model. Next,
analytical models were constructed to evaluate various
implementations of the select, project, and join relational
operations and the update operations of addition, deletion, and
modification for a range of data structures and architectural
configurations. To predict the performance of the query processor
for all cases, the individual operator models needed to be
extended to models for complex queries consisting of several
relational operations. The solution to modeling multi-step queries
was the use of a general form to express a query. This normal form
query tree uses combined operations to express relational algebra
equivalent queries in a standard form. This standard tree form was
then used to construct analytical models for multi-step queries.
These models provide the capability to model the potential of
different forms of parallelism in solving complex queries. The
results of the analytical models present a logical design for a
multiprocessor query processor. This logical query processor using
multiple processors and employing parallelism illustrates the
potential for an improved query processor using parallel
processing when the analytical model results of complex queries
are compared to a benchmark of some current database systems.
.]
.[
AN University Microfilms Order Number ADG88-01732.
AU LUCCI, STEPHEN.
IN City University of New York Ph.D 1987, 241 pages.
TI STRING MATCHING: A COMPARATIVE STUDY OF ALGORITHMS, AND ITS RELATION
TO PROBLEMS OF PARALLEL AND DISTRIBUTED COMPUTING.
DE Computer Science.
AB Our purpose in this work is to provide a comparative study of
string matching algorithms and their relationship to problems in
parallel and distributed computing. We begin our discussion in
chapters one and two with the Knuth-Morris-Pratt and Boyer-Moore
algorithms. These optimal serial approaches to string matching
provide a reference point against which their parallel
counterparts in chapters three through five may be judged. Galil's
parallel algorithm in chapter three searches for prefixes of the
pattern of increasing length which occur within the text string.
Vishkin's Algorithm, described in chapter four employs the concept
of duels between various text positions to obtain a sparse set of
indices within the text in which the pattern might begin. In
chapter five the Rabin-Karp Algorithm is outlined. This approach
uses hashing functions called fingerprints, rather than character
comparisons, as its basic operation. It is a serial algorithm
which unlike other serial approaches is readily parallelizable.
In chapter six we outline an architecture for a parallel processor
for Galil's algorithm. The "parallel string processor" (PSP) is an
SIMD computer with 2$\sp{16}$ PEs and a perfect shuffle
interconnection network. In the process of specifying our design
we consider sorting algorithms, connection networks, and various
paradigms for data broadcasting. Hopefully, this work foreshadows
the rapidly unfolding technological breakthroughs that will serve
as a bridge to fifth generation systems.
.]
.[
AN This item is not available from University Microfilms International
ADG03-75884.
AU SHEU, CHEN-YU.
IN University of California, Berkeley Ph.D 1986.
TI QUERY PROCESSING AND COMMUNICATION CONTROL IN OBJECT BASES AND
DISTRIBUTED OBJECT BASES.
DE Computer Science.
.]
.[
AN This item is not available from University Microfilms International
ADG05-62253.
AU TUORI, MARTIN IAN.
IN University of Toronto (Canada) Ph.D 1987.
TI A FRAMEWORK FOR BROWSING IN THE RELATIONAL DATA MODEL.
DE Computer Science.
AB This thesis addresses problems in HCI (Human-Computer Interaction)
with information systems, especially database management systems
(DBMSs). Inexperienced or occasional users are often unable or
unwilling to cope with the linguistic, structural and intentional
demands of traditional interfaces, especially high-level query
languages. The primal form of interaction is looking, or
searching. A four part taxonomy of searching is given (intention,
structure, language and modality), and used as a descriptive basis
for a review of relevant HCI literature and interface approaches.
The most important form of searching for casual use is browsing,
defined here as searching without an explicit goal or intention.
A three-part framework is presented for the design and evaluation
of browsing interfaces--conceptual models of the interface, design
guidelines, and evaluation criteria. A closed-loop model of the
user interface is presented, along with a novel categorization of
relational database interfaces, by the way a user may approach the
information (data-model-oriented, object-oriented, and
domain-oriented) and by structural level (system, database, table
and tuple).
Two selection methods for domain-oriented, table-level browsing
are presented--multidimensional range query and point of view
using nearest neighbours. Their strengths and weaknesses are
examined, and the nearest-neighbours approach developed in detail.
Problems arising from this method are examined, solutions offered,
and an implementation supporting both these methods is presented
and discussed.
The descriptive taxonomy and development framework presented in
this thesis offer a basis for understanding computer-assisted
searching and for assessing the contributions of various interface
approaches. Previous literature on HCI is based on the premise of
well-defined intention; this premise must be rejected in favour of
a model of HCI in which the user's intention is variable.
Computerized information systems capable of supporting a wide
range of users will result from the integration of many interface
approaches; browsing offers a useful approach for initial,
exploratory search, especially by inexperienced or occasional
users.
.]
.[
AN University Microfilms Order Number ADG88-04620.
AU TURBYFILL, CAROLYN.
IN Cornell University Ph.D 1988, 286 pages.
TI COMPARATIVE BENCHMARKING OF RELATIONAL DATABASE SYSTEMS.
DE Computer Science.
AB New and diverse architectures have been developed to meet rising
expectations of both functionality and performance from relational
database systems. A comprehensive, portable, comparative benchmark
is needed to evaluate the performance tradeoffs inherent in these
different architectures. In this thesis, we develop an
experimental framework for systematically evaluating and comparing
relational database systems across diverse architectures. We
describe and motivate the design of a scalable, portable benchmark
for relational database systems, the AS$\sp3$AP benchmark (ANSI
SQL Standard Scalable And Portable). The AS$\sp3$AP benchmark is
designed to provide meaningful measures of database processing
power and to be a useful tool for system designers. We introduce a
new performance metric, the equivalent database ratio, to be used
in comparing systems. The equivalent database ratio is the ratio
of database sizes on two different systems for which equivalent
performance on a set of test queries is obtained.
The benchmark consists of two parts: tests of the access methods
and building blocks, and test of the optimizer. In tests of the
access methods and building blocks, access methods and functions
common to implementations of relational database systems are
tested. The relations and queries used in these tests are designed
to increase the likelihood that the access method or program
branch targeted by the test will actually be chosen by the query
optimizer. The tests of the access methods and building blocks are
used to compute the equivalent database ratio. In tests of the
optimizer, assumptions typically made by query optimizers such as
the uniform distribution of data values or the random placement of
tuples are systematically violated. Comparisons between queries
are used to indicate whether the optimizer has made a correct
choice. Queries are included to illustrate current limitations in
the state of the art in query optimization. For a representative
cross section of access methods, estimates of the best case
response time for the benchmark queries on disk bound systems are
computed. The response time estimates and the systematic
benchmarking methodology provide for clear interpretation of
benchmark results.
.]
[Note: continued in next issue - Ed]
------------------------------
END OF IRList Digest
********************
