In this thesis I will study relatedness measures between pair of nodes (pages) in the graph of Wikipedia. The literature contains many of such measures, but very often they are not time/space efficient and/or they don't allow to compare any pair of nodes.
Here I will propose new measures that overcome those limitations. They will be constructed over the clustering produced by an algorithm called "Layered Label Propagation" and I will show that they allow to reach comparable (or better) results with some of the best known ones by using, under certain conditions, less memory.
I will also present how, by using an algorithm called "Locality Sensitive Hashing", a subset of them could be used to solve some common search problems in a time/space efficient way. And I will also extend the work done in the paper "Compressed Indexes for String Searching in Labeled Graphs" by using them to solve a similar problem.