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:

  1. Search for every single letter.
  2. Check which queries have maxed out the 1000 result limit.
  3. For each of those, make 26 new queries, appending every letter of the alphabet to them.
  4. 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.)

  • $\begingroup$ I am not persuaded by your argument that it is suboptimal. To show that it is suboptimal, you'd have to describe another algorithm that is strictly superior. It doesn't seem so obvious to me. More broadly, I don't think there will be a single optimal algorithm, without some information on the distribution of strings in the database. There are probably some distributions where this algorithm is the best possible and other distributions where other algorithms are better. $\endgroup$ – D.W. Mar 15 '20 at 23:46
  • $\begingroup$ What metric do you want to use to evaluate how good an algorithm is? Do you want to count the number of queries? Count the sum of the number of strings returned across all queries? Something else? $\endgroup$ – D.W. Mar 15 '20 at 23:46
  • $\begingroup$ Substring indexes are a well-trodden area of stringology. I would suggest looking at suffix trees, suffix arrays, and FM-indexes to start with. $\endgroup$ – Pseudonym Mar 16 '20 at 2:07
  • $\begingroup$ @D.W. The only information about the distribution of strings is that they are valid English words, with the corresponding distribution of letter combinations. For a trivial superior algorithm: "the same thing described above, but discarding the string "qux"". The metric I'm looking for is "minimum query time spent to produce a given number of unique results"; for simplicity, let's say I want specifically 95% of the entries in the DB. $\endgroup$ – Dariush Mar 16 '20 at 2:39
  • $\begingroup$ To use that metric to evaluate an algorithm, we need a model for how the query time relates to the number of queries and the number of strings that each query returns. Can you edit the question to provide that criteria and that model? $\endgroup$ – D.W. Mar 16 '20 at 7:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.