A new service from Veveo aims to make it easy for mobile users to browse the Web’s videos on their handsets.

VTap, announced this week after two and half years of stealth production, uses a character-based incremental search to let users search, browse and select Web videos from more than 100,000 video Web sites across the Internet and play them on their iPhones or Microsoft Windows Mobile phones. Results are returned with every character entered, starting with just the first letter of the title or actor’s name.

“Our basic hypothesis is that the propensity of people to enter words using these small phones’ keyboards isn’t very high,” said Guru Pai, vice president of marketing for Veveo. “Each character you enter is really a search query for us. Each time you enter a character, we start returning results.”

Pai said that their objective was to fix two problems in the media world. First and foremost was the challenge of content discovery over mobile, or “input and display” devices, he said. Web-connected phones technically have access to the same content users might get on a PC, yet because they don’t have full-fledged keyboards or a big enough screen, they can’t access any of that content. Even if users could access the content, Pai said, the second problem arose with video encoding barriers.

“In the case of mobile phones, there is another problem that exists, which is that most video is encoded in a form that may not be supported by that device,” said Pai. “So we make sure that the source and the player get managed in the network so that you can actually see those videos.”

After users makes the initial search, they can browse a list of selected videos, clustered into folders in a hierarchical organization of the most relevant matches. By browsing into the folder, users can select the specific web clip they want to view.

“One of the common questions people ask is, ‘Isn’t this similar to things like Google?’ And the difference is that Google just suggests queries for you,” said Pai. “We, on the other hand, are giving you the results right up front. With Google, you have to pick from a list and hit ‘send’ or select it, and it’ll give you a list of results. So it is actually suggesting a query for you, not giving you results. So it is fundamentally different computer science and algorithms that are at work here.”

Veveo currently has no plans to launch a Web site version of vTap in the future, said Pai. Curious Web browsers without an iPhone or Microsoft Windows mobile phone can go to vtap.com to try out a test-drive application of the service. Pai said the service should have broad support for more Java phone models within the next couple of months.

“We’d love for things to happen in a lot more devices and a lot more networks,” said Pai. “But we’re going to do it one step at a time. We are pretty psyched about the future.”