Implementing a good autocomplete?

I'm running a Rails 3 app, where I have a jQuery autocomplete box, which returns results based on Google Places Autocomplete. Now, I also want it to return results from places present in my local db based on the string entered.

I've set up everything I need to to be able to return the places I want from my local db. At present, it returns EVERY place in my local DB, but I need to implement an algorithm开发者_运维问答 to match the entered string to locations. Now, my question is, is there a good standard algorithm I can use to get autocomplete results, (hopefully on par with google places autocomplete) ? Don't worry about the implementation details, just the algorithm.

If there is a readymade solution for this in Rails, that would be great!

---

I have something similar setup (tasks that are valid for work_items), here is a rough sketch what I had to do:

1. Install rails3-jquery-autocomplete that implements most of the needed functionality.
2. Implement in your view something like: f.autocomplete_field :task, autocomplete_task_title_work_items_path, :id_element => "#task_id"
3. Include in your controller that implements the actions for the view the following line at the beginning: autocomplete :task, :title, :limit => 1000, :full => true

You should find some documentation at GitHub for rails-jquery-autocomplete with some more options and explanations.

---

If you have the geocoordinates of the location you can use a spatial index or a space-filling-curve to look for all locations in a quadrant. Or you can try the harvesine formula for a more exact match.