Techniques for compressing a data set in a manner such that the data set is represented as a geometric filter are disclosed. Here, the geometric filter has a small memory footprint, thereby enabling the data set to be indexable without consuming a large amount of memory. One bits can be represented within a bit vector portion of the geometric filter or in an index portion of the geometric filter. Techniques are also provided to determine a level of similarity between two data sets, where the data sets have been compressed such that the data sets are representable as geometric filters. The data sets can be indexed without consuming large amounts of memory, and the similarity determination can be performed rapidly. Approximate minimum spanning trees (MSTs) are also generated to find an optimal compression for the data sets, such that the indexes are smaller and searching operations are faster.