Diss. ETH No. 12880
Search Processes
and their Average Case
Analysis
A dissertation submitted to the
SWISS FEDERAL INSTITUTEOF TECHNOLOGY
ZÜRICH
for the degree of
Dr. sc. techn.
presented by
NICOLA GALLI
Dipl. Informatik-Ing. ETH
born 28.5.1971
citizen of Besazio, Switzerland
accepted
on the recommendationof
Prof. Dr. Klaus Simon, examiner
Prof. Dr. Emo Welzl, co-examiner
1998
Abstract
The last decade is characterized
by
a
rapid growth of
the amount of
information stored worldwide. The role of search strategies is, therefore,
a key aspect of the management of data. Many algorithms have been
developed to obtain more and more efficient Solutions where time and
complexity have been mostly considered to measurethe efficiency.
The traditional type of complexity treatment is the so called worst
case analysis. However, this approach is often rather pessimistic. The
space
observed behavior is in many
cases
much better than the worst
case.
Therefore, it is meaningful to analyze the average Performance. But
this approach involves a new problem: A probabilistic model is needed.
The major difficulty is to find a good compromise to get both a general
and
simple model.
In this
First,
thesis,
we
handle two basic
problems
from this
point of view.
graphs. Starting from an average case
analysis of Breadth-First-Search,we propose a general model to investigate a vast class of graph algorithms. This model is also useful to
we
consider the search in
analyze structural properties of random graphs. Then, we consider
search in ordered sets, namely the dictionary problem. We study
the
two
different Solutions: Randomized search trees and Hashing. More precisely, we present a realization of randomizedsearch trees which extends
the traditional Solution [6] in the weighted case and which points out the
affinity with balanced search trees. Then, we propose a perfect hashing
scheme based on the compression of sparse tables. The resulting perfect
hash function is surprisingly simple and efficient (in terms of time and
space complexity).
Riassunto
L'ultimo decennio e stato caratterizzato da una rapida crescita del volu¬
me di informazioni memorizzatein tutto il mondo. II ruolo delle Strate¬
gie
per la ricerca dei dati e quindi divenuto un aspetto determinante
per la loro gestione. Molti algoritmi sono stati sviluppati per ottenere
soluzioni sempre piü efficienti.
Tradizionalmente gli studi
riguardanti
l'efficienza di un algoritmo
tempo di memoriaimpiegati sono
basati sulfanalisi del caso peggiore (worst case analysis). Perö i risultati
si sono rilevati spesso pessimistici se confrontati con valori empirici. Di
conseguenza si e pensato di analizzare il comportamento medio di un
algoritmo (average case analysis). Purtroppo anche questo approccio
non e privo di problemi: infatti richiede un modello probabilistico. La
difficolta, maggiore consiste nel trovare un modello generale e semplice
allo stesso tempo.
In questa tesi trattiamo due problemi in quest'ottica. Per prima cosa
studiamo Pesplorazione di grafi. Partendo dall'analisi di uno degli al¬
goritmi base, vale a dire Breadth-First-Search,proporremo un modello
generale per analizzare una vasta classe di algoritmi su grafi. Questo
modello permette inoltre uno studio della struttura di grafi casuali. In
seguito
-
e
-
misurata soprattutto in termini di
considereremo la ricerca di dati in insiemi ordinati. Studieremo
due soluzioni praticamente opposte: strutture ad albero randomizzate
e hashing. Nel primo caso presenteremo una realizzazione che estende
la soluzione tradizionale [6] e che mostra le affinita con alberi bilanciati
(balanced trees). Inline proporremoun metodo di hashing basato sulla
compressione di matrici sparse. II risultato e sorprendentemente sem¬
plice ed efficiente (sia dal punto di vista del tempo che della memoria).