Best way to find needle in a haystack for large number of similar records

I am looking for some guidance as to what would be the most ideal method to code this particular search that I will describe below.  Here are the some of the details of the search functionality that I am trying to accomplish:

- my goal is to locate a unique 15-digit number among, amount 5 million uniques;
- search box allows numbers only;
- search box should require a minimum number of digits before searching;

Here is a sample of what the data looks like:

190410020030100
190410020030200
190410020030300
190410020041000
190410020042000

Currently, I am using a blend of Ajax, PHP and jQuery autocomplete to achieve some other search functionality on my page.  Everything is working fine because the data involves smaller numbers of fairly distinct records.  Now, however, I am dealing with a massive amount of highly similar records.  For example, until the user enters 13 of the 15 required digits, there would be too many records retrieved by the search to be able to display them meaningfully to the user.

Does anyone have any ideas to share?  Thanks.

UPDATE:  The comments here seem relevant to this question:
http://forum.jquery.com/topic/jquery-ui-autocomplete-plugin-very-large-dataset