FOA Home
All these techniques depend, of course, on being able to compute the SVD
for the Index relation. Given the enormous size of this matrix
-- typically $10^{4}$ keywords by $10^{5}-10^{9}$ documents -- this is a
nontrivial concern. However, the fact these matrices are SPARSE
(i.e., any one document vector has a relatively small fraction of
keywords associated with it) means that special techniques can be used.
Berry in particular has developed methods based on Lanczos anbd subspace
iteration methods in his SVDPack implementation
\cite{Berry92,Berry94,Letsche96}. }
Once the document corpus has finally
been compressed, another serious, recurring computation must be done:
Every time a user issues a query, it must be transformed from the
original space of ``raw'' keywords into the reduced $k$-dimensional
space. This means we must keep the matrix $U_k$ available to transform
each query into the reduced representation. How much memory is required
to store $U_k$? What is the complexity of the computation required to
compute it? Making reasonable assumptions about a query load, estimate
the load this would make on a query server? Can you suggest a parallel
architecture that would be especially appropriate for this purpose?
Another computational issue has to do with the effect of new documents
being added to the collection, and/or older ones being removed. This is
one particular type of DRIFT we might expect in FOA; Section §7.3.2 discusses several others. The
addition or deletion of any one document will affect the SVD statistics
of the entire corpus very slightly, especially if it is a very large
one. As more and more documents are added, how much drift in vocabulary
is likely? How much before it significantly degrades performance?
Top of Page
Computational considerations