Fast keyword lookup

Question

I'm writing a program that matches a user submitted query against a list of keywords. The list has about 2000 words and performance is most important.

Old

Is it faster to store this list in a SQL table or hard code it in the source code? The list does not need to be updated often.

If SQL table is faster when which data types would be the best? (Int, Nvarchar?)

If hardcoded list is faster what data type would be the best? (List?)

Any suggestions?

what is the best in-memory data structure for fast lookups?

Answer 1

The list does not need to be updated often

I say if it ever needs to be updated it does not belong in the source code.

Answer 2

It doesn't matter for the performance where you store this data.

If you start your program, you load the string-array once from which datastore you stored it. And then you can use this array all the time until you quit the program.

Answer 3

The hardcoded list is faster. A database hit to retrieve the list will undoubtedly be slower than pulling the list from an in-memory object.

As for which datatype to store the values in, an array would probably be faster and take up less memory than a List, but trivially so.

Answer 4

If the list is largely static and you can afford to spend some time in prep (i.e. on application start), you'd probably be best off storing the list of keywords in a text file, then using say a B* tree to store the keywords internally (assuming you only care about exact match and not partial matching or Levenshtein distance).

Answer 5

IMO, If the list doesn't get update often, store it on a file(text/xml) then cached it in your application so that it would be faster for the next requests.

Answer 6

Okay, to respond to your edit (and basically lifting my comment into an answer):

1. Specify in advance the performance that you are expecting.

2. Code your application against a sorted array and using a binary search to search the array for a keyword. This is very simple to implement and gives decent performance. Then profile to see if it matches the performance that you demand. If this performance is acceptable, move on. The worst-case performance here is O(m log n) where n is the number of keywords and m is the maximum length of your keywords.

3. If the performance in step two is not acceptable, use a trie (also known as a prefix tree). The expected performance here is m where m is the maximum length of your keywords. Profile to see if this meets your expected performance. If it does not, revisit your performance criteria; they might have been unreasonable.

4. If you are still not meeting your performance specifications, consider using a hashtable (in .NET you would use a HashSet<string>. While a hashtable will have worse worst-case performance, it could have better average case performance (if there are no collisions a hashtable lookup is O(1) while the hash computing function is O(m) where m is the maximum length of your keywords). This might be faster (on average) but probably not noticeably so.

You might even consider skipping directly to the last step (as it's less complex than the former). It all depends on your needs. Tries have the advantage that you can easily spit out the closest matching keyword, for example.

The important thing here is to have a specification of your performance requirements and to profile! Use the simplest implementation that meets your performance requirements (for maintainability, readability and implementability (if it's not, it's a word now!))