Database of queries and similarity

You are given a database of queries Q, with 100 millions of queries. Given a query q return all the queries that have a similarity of 50%. Make your own assumptions and write some C++ code for that.