9

I was recently reading a book as prep for an interview and came across the following question:

What will you do when your crawler runs into a honey pot that generates an infinite subgraph for you to wander about?

I wanted to get some solutions to this qn. Personally, I would some form of depth limited search to prevent traversing continuously. Or perhaps use some form of machine learning to detect patterns. Thoughts?

OckhamsRazor
  • 4,824
  • 13
  • 51
  • 88
  • Is your question, "What is the fastest (fewest operations) way to determine if you're traversing an infinite subgraph?" – Jonathan M Jul 21 '11 at 17:58
  • Nope, rather, it is- "is there any way to prevent crawlers from being "tricked" by honeypots" or perhaps "how to detect honeypots" (tried searching for an answer online, unsuccessfully might I add). – OckhamsRazor Jul 21 '11 at 18:01
  • @Jonathan: you need an infinite number of operations for that. it's undecidable – Karoly Horvath Jul 21 '11 at 18:04
  • Honeypots and webcrawlers play a game of one-upsmanship with each other. They each use different tactics to defeat the tactics of the other. So, I'm not sure this question is answerable here. It requires an on-going discussion about tactics. – Jonathan M Jul 21 '11 at 18:08

2 Answers2

7

Most commonly infinite subgraphs are prevented by link depth. So you gain an inital set of urls and you will traverse from each to a finite depth. While limiting the traversing depth you may use some heuristics to dynamically adjust it according to webpage characteristics. More information can be found e.g. here.

Another option would be to try some sort of pattern matching. But depending on the algorithm which produces the subgraph this will be a pretty (very very very)hard task. This will also be at least a pretty expensive operation.

For the interview question(about detecting infinite loops):

If they ask this questiom someone want to hear a reference to the Halting problem

Alan Turing proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist.

fyr
  • 20,227
  • 7
  • 37
  • 53
  • ah, very interesting! so i was "traversing" in the right direction after all! yes, i think you're probably right- they'd want to check if im aware of the halting problem.. good answer- i'll keep the qn open for a few hrs if there's a better solution. – OckhamsRazor Jul 21 '11 at 18:30
  • mmm if I understand correctly this will fail if you have two honey pots with infinity links to each others as there are infinite entry points. – Karoly Horvath Jul 21 '11 at 19:02
4

You could limit the number of retrieved pages. Of course there is a problem with this.. what if the site is really huge? Is wikipedia infinite? :)

A better way is to set the threshold based on how many external sites link to it and how many distinct pages they link to. The larger the number is the bigger your threshold is. This could solve problems with a couple of infinite honeypots which link to each other.

Karoly Horvath
  • 94,607
  • 11
  • 117
  • 176