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

  • $\begingroup$ Cross posted from StackExchange: stackoverflow.com/questions/9661104/… $\endgroup$ – Jordan Eldredge Mar 12 '12 at 20:08
  • 1
    $\begingroup$ Welcome! Please avoid cross-posting. $\endgroup$ – krlmlr Mar 12 '12 at 21:24
  • 1
    $\begingroup$ A fuller description of the data available to you might inspire effective replies. One thing I wonder is whether you have any information about whether a user found the character they were looking for or eventually abandoned the search. Perhaps even time stamps could help. Another point: because "correlation" has a specific meaning in statistics which differs from the sense used here, it could mislead some readers. You might consider using an alternative terms such as "association" to describe what you are attempting to measure. $\endgroup$ – whuber Mar 27 '12 at 13:42

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.

  • 1
    $\begingroup$ I do not follow why statistical significance may be relevant to this problem, because significance (a very general concept in hypothesis testing) and strength of association are not the same thing. Could you perhaps explain how you would measure "significance" in this context and how it would "build" over time? $\endgroup$ – whuber Mar 27 '12 at 13:39
  • $\begingroup$ This is the method I have adopted. The autocomplete returns 10 results. Results whose canonical name match the query are returned first, and then (heading of "Did you mean?") any associated characters (ordered by the strength of the correlation between that string and that character). This works well enough. It would be nice (cleaner) to be able to begin removing the matches that are just noise, but I'm not sure how to start calculating the association strength cutoff. It will have to be different for every string. $\endgroup$ – Jordan Eldredge Mar 28 '12 at 4:55

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?


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.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.