clarke@csri.toronto.edu (Jim Clarke) (03/16/89)
INFORMATION SYSTEMS SEMINAR SPONSORED JOINTLY BY DCS AND FLIS
(LS = Claude T. Bissell Building, 140 St. George Street)
Thursday, March 23, 2 p.m. in Room LS 225
Christos Faloutsos
University of Maryland
"Access Methods for Tex and Spatial Data Bases"
The talk consists of two parts, examining access methods for text and for
spatial data respectively.
In the first part, we examine efficient searching techniques for text
retrieval applications. We propose a unifying framework, which reveals the
similarities between signature files and an inverted file using a hash
table. Then, we design methods that combine the ease of insertion of the
signature files with the fast retrieval of the inverted files. The results
show that the proposed methods achieve fast retrieval, they require a mod-
est 10%-30% space overhead, (as opposed to 50%-300% overhead for the
inverted files), and they do not require re-writing; thus, they can handle
insertions easily, they permit searches during an insertion and they can be
used with write-once optical disks.
In the second part we examine access methods for multi-dimensional
data, such as boxes, polygons, or even points in a multi-dimensional space.
Spatial objects arise in many applications, including cartography,
computer-aided design (CAD), computer vision, robotics, rule indexing in
knowledge-base systems, etc. We examine such methods with two design goals
in mind: (a) efficiency in terms of search speed and space overhead and (b)
ability to be integrated in a DBMS easily. We propose a method to map mul-
tidimensional objects into points in a 1-dimensional space; thus, tradi-
tional primary-key access methods can be applied, with very few extensions
on the part of the DBMS. The search time of this approach requires a good
distance preserving mapping. We propose such mappings based on fractals;
Simulation experiments on top of a B+-tree showed that a modified Hilbert
curve gives the best results.
--
Jim Clarke -- Dept. of Computer Science, Univ. of Toronto, Canada M5S 1A4
(416) 978-4058
clarke@csri.toronto.edu or clarke@csri.utoronto.ca
or ...!{uunet, pyramid, watmath, ubc-cs}!utai!utcsri!clarke