What module do I need to improve magento search?

Question

I would like to improve search functionality on our magento website: AND instead of OR in the default search field. Search suggestions and spelling corrections would be great.

Searching for this, I found the following modules: Elastic Search (http://www.magentocommerce.com/magento-connect/elasticsearch.html) and Sphinx Search Pro.

Elastic search is "search in the cloud", but I have no idea what that means here. Our magento installation is installed on AWS EC2, so in the cloud, but I don't see how that makes a difference. Search is performed on the database, or does it work otherwise, from cache or somehow?

What is the best module to use? Any other tips?