I think it does not come from your address book. Rather, it builds the database from each one of us who register with truecaller with thier numbers. So for example: I register with my phone number 123456789, and you register with your phone number 987654321. Both these numbers would be stored on Truecaller's servers and when you get a call from my number 123456789, and even if you don't have my phone number in your phonebook, you still get to see that I am calling you with my name (the details come from the server). You need Wifi/data connection to get truecaller working. That's my understanding , unless I am utterly wrong.