Verizon remakes its app store with Chomp’s search help

Verizon Wireless (s vz) has rebuilt its VCast App Store with a new interface and better search capabilities thanks to a partnership with app discovery start-up Chomp. Android (s goog) users who visit the newly renamed Verizon Apps, which is built into about 15 Android devices and will appear on new Android phones, will see a cleaner storefront and have access to a more powerful search tool to find the best apps for them.

Verizon and Chomp originally partnered back in May when Chomp released an app in the VCast App Store that searched both Android Market and Verizon’s app catalog. Verizon’s Todd Murphy, director of customer service at Verizon, told me the next logical step in the relationship was to build Chomp right into the app store, which had a more rudimentary search system.

Chomp allows users to find apps by searching without knowing the name of a particular app. Users can search by what an app does and can find relevant results, which start appearing right as a user begins typing. Chomp looks at all the data associated with an app to bring up results and also gathers information from blogs, social networking sites and other app stores.

Even though Verizon Apps only boasts about 3,000 apps, a drop in the bucket compared to the iOS App Store and Android Market, the company says it felt discovery is still one of the key areas it could improve upon in its store.

“This was one area that we felt was a big issue: accurate discoverability of good content,” Murphy said. “It’s a known problem for customer; they can’t find good applications.”

The Chomp integration is part of a larger effort to ensure that Verizon’s store is a well thought out place to safely buy apps. The company has partnered with malware expert Lookout to make sure every app in its library is cross checked against Lookout’s list of bad apps. And Verizon has instituted parental controls and its own age-ratings. And with Verizon’s carrier billing, it’s tried to make checking out easier.

It seems to be working. Murphy told AllThingsD that three out of every five app downloads in Verizon Apps is paid, which he said is considerably better than Android Market’s rate of  one in 10 app downloads. I’m not sure if that’s correct, but it stands to reason that if you curate a solid selection of the best apps, ensure they’re safe and provide easy check-out, it can prompt people to open up their wallets. That’s right out of Apple’s (s aapl) playbook and it’s interesting to see how Verizon has picked it up. Verizon Apps will also serve up apps for BlackBerry (s RIMM) phones.

I think app discovery is going to have to keep improving because each day there are more apps that hit the market and users are increasingly confounded as to how to find the best apps. Solutions like Chomp, Quixey, Appsfire and others are more appealing to consumers because of the way they help surface good app results. I’ll be curious to see if other app stores integrate these services or buy them outright as the need for better search and discoverability grows.