Mining search logs to improve autocomplete suggestions? I have logs from an autocomplete form, which I would like to leverage to increase the intelligence of the results it returns.
I have a project that revolves around users selecting opera characters from a database of ~15,000 unique characters. My difficulty is that each character appears in the database as only one name but it may also be known to the public by any number of other colloquial names.
I have had been lucky enough to receive a modest amount of traffic and currently have ~20,000 rows of logs of strings which my users have typed and the opera character they ended up selecting.
If a user doesn't find the character they are searching for with their first string, they will often try the character by another name. When they are successful, this data correlates the characters' colloquial names with the character itself. I am hoping to leverage this data to enable my autocomplete form to match against these colloquial names.
Unfortunately along with the useful correlations there are many (perhaps more) random correlations. Often when a user's attempt(s) do not return the result they are looking for, instead of trying the character by another name, they simply try (and locate) a completely different character.
I have read a number of scholarly papers on the subject of using search logs to improve natural language search queries, but none of the methods seem to have much application in this narrow case.
Are there known methods that would be useful for this application?
My project can be viewed at http://fachme.com
 A: Interesting project. The technique that comes to mind my mind is association mining. 
This technique can automatically discover many many patterns in data of this kind. It is often used in retail market research, where the question is "If a shopper bought 10 products, which of them were purchased 'together' and which just happen to be in the same basket?" For example, if everyone is buying bandages and anti-biotic ointment together, then I might want to put those products next to each other in the store. 
The drawback is that this technique cannot capture the temporal information in your data, since it only looks at the basket of search queries made by a user, not their order.
I don't know much about mining temporal data, but perhaps someone who does can suggest a temporal form of association mining?
A: it is a matter of ordering correlations based on statistical significance, and generating enough data over time to define that significance. the noise (random correlations) will be filtered out as more people search for, and correlate, terms and characters.
auto-complete should return the top n results as a user is entering their query. initially, it might display 5 colloquial correlations and 5 random correlations (if n=10). these correlations will probably be weighted the same in the beginning as there may only be one correlation per term in your database (they might display alphabetically or randomly to your users). your correlations will build significance over time as users naturally select the more appropriate suggestions from auto-complete. as this happens, the less significant (read: random) correlations will sink to the bottom thus further reinforcing the significance of those at the top as they become relatively more visible to your users.
keep in mind that there is no shortcut to statistical significance. by nature, it requires a large enough sample set to exist in the first place. 
A: Is there a similarity measure that you can use for character names? Besides that, I feel that you will need some kind of feedback here: Basically, you need to prove or disprove every correlation (here: equivalence) that you are assuming from the data.
Imagine that a user enters A' to find character A, and then B' to find character B. If you assume that A' = B', you need to prove or disprove this. Why not presenting the next user that is searching for B' the character A first? And, vice versa, present a user looking for A' the B result as option. This, plus some machine-learning/clustering techniques I'm afraid I cannot tell you much about, should help you solve the problem.
