I am trying to find any datastructure/algorithm suitable to index & retrieve domain names & its associated documents.
The records that need indexing will typically be like:
www.facebook.com, 123 stackoverflow.com, 1231 www.facebook.com, 124 stackoverflow.com, 3456 cdn.facebook.com, 4566 google.com, 903002 google.co.nz, 2342 google.co.in, 84992 google.com, 902002
The retrieval will involve getting all the document ids(not top K but all of them) for a given search. Since it is content with a structure, people can query using part of domain names.
e.g. search for 'google' will lead to matching of all documents that have google.co.nz,google.co.in & google.com associated with them.
- As far as the distribution goes, less than 30% of the domain names will point to 80% of the documents.
- The number of records being indexed will be in hundreds of billions
- The index will most likely not fit into memory and will have to be stored in file-system
- I thought of a solution where the domain names are tokenised(e.g. www.facebook.com gets tokenised into www,facebook,com,facebook.com,www.facebook.com) and hashed.
- The hash value lookup leads to all the documents that are part of the hash
- Some of the problems I see with this approach are
- The values(document ids) are stored multiple times and some of the TLDs/commonly used subdomains(www) will have almost all the entries in them
- Removing 1 entry will lead to updating multiple entries & their lists.
- Hash collisions can affect the quality of results & hence hash function is quite vital to it
- It won't be possible to address mis-spellings or substring search e.g. *goog*
- The hash key will have to be 64-bit or more depending on the function
The question is what datastructure/algorithm to use to store & search for documents matching a given domain name.
Alternatively, if the above proposed solution is suitable, what can be a good hashing function given this context.