After prompting the user for the ok, the mobile app would upload the entire address book to the server. I would check for matches and return a maximum of 25% of total contacts as being valid (randomly so you wouldn't know which numbers really didn't exist). If there were more hits they would be placed into a queue and sent periodically as "your friend has joined!" notices which also increased engagement.
Subsequent checks were done by again uploading the entire address book, however I would check against the previously stored phonebook (numbers only hashed with a per user salt) and limit the number of valid hits returned based on the delta of the address book. So if you kept sending 1000 new numbers every time, you wouldn't get any new matches.
It was also rate limited per account (which required a verified phone number). All the logic took less than a few hours to think up and implement. Here you go Snapchat, now fix your shit.