0
$\begingroup$

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.

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

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

$\endgroup$
0
$\begingroup$

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.

You raised some concerns about this approach, but they are all manageable:

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

$\endgroup$
  • $\begingroup$ #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. $\endgroup$ – Sundarram P.V. Jan 24 '16 at 7:58
  • $\begingroup$ @SundarramP.V., #2: I just don't believe you'll see domain names with 5 or 10 components very often. That sounds exceptionally rare. $\endgroup$ – D.W. Jan 24 '16 at 8:16
  • $\begingroup$ #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) $\endgroup$ – Sundarram P.V. Jan 24 '16 at 12:58
  • $\begingroup$ @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. $\endgroup$ – D.W. Jan 24 '16 at 13:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.