Random Projections for Similarity Search in Boolean Retrieval

This paper discusses the problem of similarity search in a large database which can be represented by the Boolean conceptual model. Such databases may include text databases or large customer transaction databases. We analyze the effect of using random projections in this database in order to perform similarity search. We provide a theoretical analysis of the degradation in the quality of the solution when the dimensions are sampled. We show that random projections are most effective for retrieval problems in which the data is very high dimensional and is densely populated across the different attributes. These results illustrate that random projection is most effective for problems which are most difficult from the perspective of similarity search.