How to figure out if a number is present in a very large dataset

See more:

algorithm

I was wondering as to what would be a suitable answer to the question "Given a very large set of numbers write a service that will return back if a number is present within 500 ms". There would be trillions of numbers. This question was supposed to test my knowledge of scalability and architecture. I answered I would break up the set of numbers into multiple buckets and assign a set to a specific server, very much like a HashMap dividing up it's keys into buckets. In each server, the server would maintain something like a bit array which would mark out if a number is present. He asked me what what if the numbers are very sparse, in which case I will use a balanced binary search tree like red black or AVL tree. I guess there would be multiple solutions to this problem. I was wondering as to what would be the other answers