# Indexing billion domain names / strings

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
stackoverflow.com, 3456


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


# Assumptions

• 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

# Initial thoughts

• 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.

The standard solution is to build an index: a data structure that maps from search term to all of the records that match that search term. Your index could be a hashmap or a B-tree, for instance. In this case, the search terms are things like "google" or "facebook" or "facebook.com", and each one maps to a list of all records that match it. Thus, facebook.com would be associated with two search terms ("facebook.com" and "facebook") and would be present in two of these lists.

• Yes, search terms like "com" will match many records. You should decide whether searching for "com" is useful or not. If it's not useful, don't include that in the index: build a list of "stopwords" (e.g., com, org, etc.), and don't include any of them in the index. For instance, you might decide that the TLD part of a domain name is not one of its matching search terms.

• Yes, inserting or removing one record will require updating multiple entries in the index. But this just isn't that big a deal. Most domain names have very few components: e.g., "www.google.com" will require changing 2 entries in the index (assuming you have blacklisted "com"), which just isn't that big a deal.

• Hash collisions are dealt with using standard methods for building hash tables and just aren't that big a deal. Or, you can use any other data structure, like a B-tree.

• No, this can't handle mis-spellings. Mis-spellings are an entirely different problem, which require a range of different solutions, and you should ask a separate question about that (but first, study Levenstein distance, metric trees, and data structures for spelling correction and answering nearest-neighbor search in the Levenstein distance metric -- there are a bunch of questions on this site that are relevant).

• No, there is no reason that the hash key needs to be 64 bits. The hash key needs to be at least the number of buckets in your hashtable.

I suggest you read some standard resources on building indices, e.g., in database textbooks, and read about how search engines work. Those topics are well-studied and those techniques will be applicable to your problem.

• #1 You are right regarding stop words, they can be avoided. #2 In the worst case that were to happen often on a lot of entries, is there an alternative approach to avoid it when the number of tokens does increase to 5 or 10? #4 You are right about it as I mistook the number of records to be number of buckets. – Sundarram P.V. Jan 24 '16 at 7:58
• @SundarramP.V., #2: I just don't believe you'll see domain names with 5 or 10 components very often. That sounds exceptionally rare. – D.W. Jan 24 '16 at 8:16
• #2 Number of tokens is not equal to number of components as there are different combinations to support. E.g. typical domain names in my intranet like vcenter-1.qa.wiscn.xyz.com (5 components including TLD) gets translated using the above mentioned scheme to tokens (14 hashable tokens/keys) xyz, xyz.com, wiscn, wiscn.xyz.com, wiscn.xyz, qa, qa.wiscn, qa.wiscn.xyz, qa.wiscn.xyz.com, vcenter-1, vcenter-1.qa, vcenter-1.qa.wiscn, vcenter-1.qa.wiscn.xyz, vcenter-1.qa.wiscn.xyz.com. Also it is not hard to imagine with cdn(*.vo.msecnd.net - azure's & *.ay1.b.yahoo.com) – Sundarram P.V. Jan 24 '16 at 12:58
• @SundarramP.V., I suggest that you calculate the average number of tokens per domain, across your data set, before rejecting this. I suspect that it just won't be that high. And if the number of records is large, I don't think you should expect to find other solutions that are significantly better. – D.W. Jan 24 '16 at 13:05