A query including one or more current search terms is received from a user and executed against a target database. When the query yields a number of results less than a defined search threshold (a.k.a. an “unsuccessful” search), the current search terms are compared with an associations database. The associations database includes associations between search terms in previously-executed queries that yielded less than a threshold number of results and replacement search terms that were substituted to generate a successful query yielding at least the threshold number of results. Upon finding a match between one or more of the search terms and the current search terms, the associations between the search terms and the replacement search terms are used to identify suggested replacement search terms and present them to the user.