There is a database of, let's say, 500k English two-word combinations (e.g. "clover arc", "minister horse"). I can search for an arbitrary string and I will get a list of the alphabetically first 1000 entries containing this string; the time each query takes is proportional to the number of results it returns, plus some constant overhead. I have a certain dynamic number of the unique results I want to get (e.g. 400k, 490k, 499k) and I want to spend as little time as possible sending queries to get them. By what algorithm should I craft my queries to achieve this?
One possible naive approach would be as following:
- Search for every single letter.
- Check which queries have maxed out the 1000 result limit.
- For each of those, make 26 new queries, appending every letter of the alphabet to them.
- Go to 2, until all queries give fewer than 1000 results.
However, this is obviously quite suboptimal, since every time we expand the tree the previous results get essentially obsoleted - almost all of them (except for those where the letter combination was at the end of the word) will be present across the queries generated from it, plus there will wasted overhead time on impossible combinations (e.g. we had a maxed-out query of "qu" and on the next level we'll be requesting "quq" and "qux", which will certainly not give any results).
How would you approach this?
(I apologize in advance if this is the wrong SE to ask this kind of question, but I couldn't find a better match.)