BACKGROUND

Field of Art

This application relates generally to the field of information retrieval and, in particular, to multi-prefix, multi-tier, dynamic menu and related interactive search techniques that facilitate the retrieval of information within a mobile communications environment.

Description of Related Art

In the last few years, web-enabled mobile telephones have become enormously popular. More web-enabled mobile phones ship each year than do desktop and notebook computers combined. Such mobile phones are similar to desktop and mobile computers in that they offer display screens, a keyboard, and, sometimes, a pointing device. However, because of portability requirements, the capabilities of the displays, keyboards, and pointers on mobile phones are significantly reduced. Displays are relatively small with little area to display content as well as menus, toolbars, and other navigation and status information. The keyboards are often telephone keypads or thumb keyboards. The pointer, when provided, is often a scroll wheel or joystick that can be used to indicate a direction of movement or pressed to indicate a click. Sometimes, the pointer is simply a set of arrow keys on the keyboard. Furthermore, because of speed and latency issues, navigation among web pages is typically much slower on mobile phones than on desktop and notebook computers.

The human interface limitations of mobile phones, combined with slower navigation, significantly constrain a user's ability to interact with web pages. Additionally, Hypertext Markup Language (HTML) forms are difficult to use on mobile phones due to data input and related limitations. These difficulties arise in many ways. For example, the mobile keyboard and pointer are less effective than their counterparts on desktop and personal computers.

Keyboards are less effective because their small form factor makes it more difficult to type characters. In some case, the keyboard is smaller and has fewer keys. The smaller keyboards usually require thumbing: typing with one's thumbs rather than using ten fingers. The reduction in keys makes it more difficult to key in digits and special characters. Some keyboards are telephone dial pads with multiple letters on each key. Various technologies, including triple tap (pressing the same key until the desired letter appears) and predictive text, help to improve the effectiveness of such keyboards, but the effectiveness is still far below that of a full-size keyboard.

The pointer is also less effective. HTML forms often contain multiple input fields and the pointer is used to navigate among them. Pointers on mobile phones, when available, are less effective than pointers or mice used with desktop computers for navigating among input fields, as well as hyperlinks and other screen objects. For example, tabbing between fields using a full-size keyboard enables the field for typing when it has received focus. On a mobile phone, the tabbing is typically done via a directional pad and the field often has to subsequently be selected to be enabled for typing. Additionally, on desktop computers, mice can be used to move from one field to another without having to move through the fields in between. On mobile phones, moving from one field to another is typically done sequentially from one field to the next, without the ability to skip any fields along the way.

However, some web-enabled mobile phones have touchscreens that provide for direct interaction with objects on the display screen. For example, users can touch a screen object directly with their fingertip or a stylus, rather than indirectly navigate to that object via a pointing device. Yet, even this “improved” user interface technique raises usability issues, as the distinction between “selecting” and “activating” an object becomes blurred. Potential solutions for distinguishing the two include providing an icon or other visible identifier on a portion of the object, or discerning the number of times a user clicks or taps it, or the amount of time a user “presses down” on the object.

In any event, the ability to select an object without also activating it becomes particularly important in systems that provide alternative functionality specific to a particular object. For example, when a user activates an HTML hyperlink in a web browser, the program typically navigates to a new web page corresponding to the URL embedded within that hyperlink object. The user, however, might want to examine the URL before making the decision to activate the hyperlink.

A common mechanism for offering a user alternative functionality specific to a selected object is a “context menu.” Context menus provide a user with one or more alternative functions available within a particular “context” or state of a program or device, such as the selection of a particular object. Context menu items can change dynamically as the context changes, as different objects are selected and as a program enters a different state.

In a mobile communications environment, however, providing context menus with which users can quickly interact is easier said than done. The state of an information retrieval system can change frequently, for example, as new search results are received from remote servers (or as information becomes known to the system, such as the time of day or a user's location as indicated by a mobile phone's GPS equipment). In addition to the problem noted above of distinguishing the selection from the activation of an object, other constraints include processing speed and memory limitations on mobile devices, as well as bandwidth and latency limitations inherent in mobile communications networks. These constraints, coupled with the many different types of information that can be retrieved from remote web sites, for example, make it even more difficult to provide context menu items that are customized to particular objects or categories of objects.

In contrast to the “random” full-text searches users often perform on desktop computers in home and office environments (in which multiple iterative searches and analyses of resulting web pages can be completed relatively quickly due to greater bandwidth and local computing resources), users in a mobile communications environment often perform more “targeted” searches for lists, schedules and other information the existence and perhaps even the location of which is often known in advance. Such information must nevertheless be retrieved relatively quickly in order to be useful. For example, common mobile searches include requests for stock quotes, sports scores, movie times and nearby restaurants or coffee shops, to name a few.

Targeted searches are less amenable to the random keyword search techniques commonly employed on existing desktop and mobile devices, in which users enter complete keywords and navigate through results and web pages across a large domain of web sites. Mobile devices, in particular, are in need of solutions in which targeted information can be found relatively quickly with minimal user interaction. Such solutions ideally would still afford users access to both the breadth of a large domain of information (such as the web with its diverse collection of web sites, or a large enterprise database) and the depth of any particular “channel” or information category (which may lend itself to unique functionality, whether within or across one or more web sites or databases).

Some mobile devices support applications that have been customized for highly targeted information retrieval, such as the “Pocket Express” application from Handmark Inc. (http://express.handmark.com/) which provides discrete modules for retrieving news, stock quotes, sports scores and various other specific types of information. Though useful for rapid retrieval of certain specific data, the domain of available information is inherently very limited, in part because each desired category of information requires its own custom module. Such an approach is not very scalable, given the vast array of information channels available via the web. Moreover, without a generic mechanism to locate information by searching within a particular module, users typically are limited to browsing or selecting items from within each module's predefined data structure. For example, users can browse news headlines and select one to retrieve the full story, but they cannot search for particular news stories, much less headlines

Other products have attempted to reduce user interaction to perform targeted searches by enabling users to enter only word prefixes or word fragments, and providing results interactively as a user types characters. See, for example, a presentation at Google (http://video/google.com/videoplay?docid=7012265262667474421&q=type %3Agoogle_engEDU) in this area, or the “vTap” program from Veveo, Inc. (http://wvvw.viap.com), as well as Veveo's various published patent applications, including both PCT publications (W0/2007/062035) and US publications (2008011473, 20080086704, 20070255693, 20070130128, 20070088681, 200701754, 20070050337, 20070005563 and 20060101499). While providing an information retrieval mechanism that is more suitable to targeted searches, such approaches nevertheless lack a generic search mechanism that can be utilized to narrow a search request within a broad domain of information channels (to provide a more focused or targeted search), as well as provide additional functionality specific to particular channels.

Google, in a recent talk (http://ihtc.org/meeting.php?meeting=march08), discussed a “multi-tier” search technique in which a user first searches for a web site (for example, “Wikipedia”), the result of which contains not only a link to that site, but also a search box in which a “second-tier” search can be typed (thus saving the step of clicking on the link and then typing in the second-tier search). Other similar solutions include special search keywords that identify the second-tier site within the search query itself. Such solutions rely, however, on the differing search engines available across various second-tier sites, which not only force users to adapt to different search query formats, but also may provide inferior results when compared to more powerful search engines such as the one provided by Google. A more integrated multitier approach could avoid such anomalies by providing a consistent search mechanism among various tiers (within as well as across particular information channels), particularly one which also offered additional context-specific functionality.

In short, existing technologies have not adequately addressed the problems intrinsic to targeted searches, particularly when conducted in a mobile communications environment. Information must be retrieved more quickly, but with less user interaction, in light of the hardware, user interface, network bandwidth and latency limitations inherent in such an environment. In addition, a more integrated and scalable search mechanism is needed to allow users to request information from a broad domain of information channels and quickly locate desired information within one or more of those channels, preferably with the availability of additional functionality that is tailored to those channels within the context of user requests and other available state information.

SUMMARY

The present invention addresses the problems discussed above by employing novel combinations of various information retrieval techniques designed to facilitate targeted searches, particularly in a mobile communications environment. In one embodiment, multi-prefix search techniques are employed in an effort to minimize a user's data entry requirements. Moreover, user queries can be executed on a remote server interactively, during the query construction process, with results transmitted back for display so as to enable users, prior to entering an entire query, to revise that query or select a desired result.

To facilitate targeted searches, users can employ multi-tier search techniques to constrain queries to one or more information channels. In one embodiment, users can simply select one or more channels from a list, which could include previously designated “favorite” channels. In another embodiment, users can employ multi-prefix searches to locate desired channels as well as desired information within particular channels (and, in some cases, within multiple tiers of one or more such channels).

For example, after locating a “yellow pages” channel with a “first-tier” search (such as “yel pag”), the user might be presented with a “second-tier” opportunity to search for “zip codes.” After entering only a few digits, the user might see the desired zip code result displayed and, upon selecting it, be presented with a “third-tier” opportunity to search for a vendor within that selected zip code. Such a multi-tier approach facilitates targeted mobile searches by reducing user interaction and data entry, and, in another embodiment, by leveraging a consistent multi-prefix search mechanism among multiple tiers.

In one embodiment, a mobile communications device includes a window, which comprises a search area and a results area. An application is launched and a landing page is displayed in a display area of the mobile communications device. The search area includes a search query field. A keystroke is inputted into a search query field and a multi-prefix search is performed. The landing page within the display area is replaced by the results of the search. The results contain a first tier of search results, which can include channels or links to web pages associated with the user input. If the selected search result is a channel, the channel is displayed. If it is a web page, the web page is displayed. In other embodiments, a separate web browser application is launched and the web page is displayed via the web browser application. The channel or the web page may then be searched or explored. If the desired channel is not displayed within the first tier of search results, one or more additional keystrokes may be inputted. Again, the results page refreshes accordingly and additional keystrokes may be entered until the desired channel is displayed.

The above-described embodiments provide for multi-prefix, interactive search capability on a mobile communications device. Prefix delimiters denote the beginning of another search prefix. In some embodiments, space characters may be used as prefix delimiters. In other embodiments, users may input space character keystrokes as well as alphabetic or numeric keystrokes. If a user's query seeks results containing multiple words, the user might enter one or more prefixes of such words separated by spaces to create a multi-prefix search query. The embodiments described above enable users to enter fewer keystrokes to obtain a desired search result. The search is interactive because a user is provided feedback (the displayed search results are refreshed) with each keystroke (or, in another embodiment, after a predefined time lapse between keystrokes). Based on partial query results, a user can determine that a search is complete and obtain the desired search result without having to enter the entire text or word of one or more search terms.

To further leverage targeted searches, in which search results often share common attributes (including similar types of fields and data formats), the data extracted from an information channel (from a given web site, for example, or a portion thereof) can, in one embodiment, be pre-processed for functional as well as aesthetic display purposes. Whether captured as keywords via a “web crawling” engine, or as structured data via higher-level data extraction techniques (with or without the assistance of the proprietor of the data), such channel data typically is or can be organized into separate “records” (such as individual restaurants, books or movies) containing discrete “fields” that represent different types of data (such as titles, dates, addresses and phone numbers) common to some or all records. This is primarily due to the fact that most web sites employ databases (typically standard relational, flat-file or object-oriented databases) as the underlying organizational structure for their data.

In one embodiment, channel data records and fields can be indexed as such in order to enable structured searches based upon these records and fields. In another embodiment, the indexing process ignores data field distinctions but is optimized for multi-prefix searches. The frequency of extracting data from remote information sources (whether for indexing or otherwise) will vary depending upon how frequently such data typically will be updated. For example, sports scores may be updated more frequently than movie listings, which in turn may be updated more frequently than restaurant listings. Whether or not field (or other) metadata is retained during the indexing process (if any), the channel data still may be susceptible to “field recognition” sufficient to enable the performance of discrete actions specific to a particular field. For example, if standard ten-digit phone numbers can be extracted from individual channel data records, such as restaurants, then such extracted data can be used to enable actions specific to a particular record, such as using a mobile phone device to call one of the restaurants displayed in the result list of a user's query.

Having extracted and maintained field data related to one or more channels (or even to particular records within one or more channels), various contextual actions can be enabled as alternatives to simply selecting and activating a particular record (which might activate a hyperlink to a web page related to that record). In one embodiment, “dynamic menus” are employed to enable a wide variety of alternative actions specific to a selected record, including calling a person or a place, sending a selected person an email, SMS or other type of message, utilizing a known location (of a user's mobile device, for example, via GPS data, or of a particular place in the result list of a user's query) to view the location of, or directions to, nearby places, or to obtain a map of a desired area, or even linking to a web page related to a particular aspect of a record (to display, for example, images of a selected person). The possibilities are virtually limitless, as they may involve not only actions of which a mobile communications device is capable (such as initiating phone calls and sending messages), but also actions relating to the channel data being retrieved, which are as numerous as the many different types of information available throughout the Internet.

This relationship, between different fields or types of available data and the actions that relate to such data, can be leveraged, even in a mobile communications environment, not only by pre-processing the channel data itself, but by pre-defining the related actions specific to that channel data (with or without the assistance of the proprietor of the channel data) and transmitting them, in response to user queries, along with the channel data query results. In one embodiment, these actions are transmitted to a user's mobile device in the form of Hypertext Transfer Protocol (“HTTP”) headers that define both the name of a dynamic menu item and the action to be taken if the user selects and/or activates that item (and are followed by the “body” of the transmission including, for example, the results of a user's query). In another embodiment, if the functionality of the client application on the user's mobile device is integrated into a web browser (using, for example, Javascript and an Ajax application), then these HTTP headers can be incorporated into the body of the transmission itself.

For example, if a user employs a multi-prefix query to search a channel containing a collection of restaurant records, the server might return a series of HTTP headers (followed by the resulting restaurant records matching the user's query) representing dynamic menu items that enable the user to initiate a call to a selected restaurant, or obtain a map and directions to that restaurant from a given location. Yet, if that user queried a different channel containing, for example, a collection of movie records, then the HTTP headers delivered with the results of the user's query might represent a different set of dynamic menu items providing actions such as displaying movie reviews, or playing video trailers.

In other embodiments, these dynamic menu items and their associated actions might vary depending not only upon the channel being queried, but upon the particular channel records the user selects. For example, in one embodiment, if a selected record did not contain a value for a particular field (such as a phone number), then any corresponding dynamic menu item relating to that field (such as a “Call Restaurant” item) would not appear, because the action could not be performed. More generic “dynamic dynamic menus” can be implemented, in another embodiment, by integrating menu item names and associated actions as discrete data fields within one or more channel records. As a result, menu item names and actions will vary as a user selects different records, even within a given channel. In yet another embodiment, certain actions, such as dialing a selected restaurant, can be invoked without requiring a user to display, select or activate a dynamic menu item. Instead, a user might simply press a key or push a button on the user's mobile device (such as the “Talk” button) to which such actions have been mapped. As noted above, dynamic menu items might also vary depending upon any particular state of a user's query or other known information, such as whether a user has logged into a particular web site (in which case a “Log In” menu item and associated action might alternate with a “Log Out” menu item and action, depending upon the user's login state).

In other embodiments, information channels can be implemented as a type of “smart bookmark” in a mobile web browser. After a user selects (or searches for) one or more channels, the user may perform a “second-tier” search constrained to that channel utilizing, for example, an interactive multi-prefix query. A mobile search engine can provide similar functionality, whether or not integrated into a mobile web browser. Such functionality can be enabled, in one embodiment, by pre-processing channel data as described above at a remote server from which search results are transmitted. Moreover, dynamic menus can be implemented in a manner similar to that described above by transmitting menu items and associated actions along with such interactive search results. In yet another embodiment, such functionality can be implemented as a standalone application limited to one or more predefined channels.

When a consistent targeted search mechanism (such as one that employs the interactive multi-prefix and multi-tier information retrieval techniques described above) is coupled with a dynamic menu mechanism that provides context-specific functionality (tailored, for example, to particular channels, records within or across those channels, or other state information), users are presented with a consistent search interface among multiple tiers across and within information channels, and need not learn different or special search syntax. Moreover, due to the constraints of a mobile communications environment, data entry requirements are limited, enabling users to enter fewer keystrokes and perform fewer query iterations, which in turn reduces network bandwidth in both directions, due in part to the interactive nature of the multi-prefix search mechanism. As a result, users can obtain desired results quickly, or revise queries, even before completing an intended query.

For example, a user with a particular preference for Starbucks coffee might want to locate the closest Starbucks coffee shop quickly while traveling in an unfamiliar city, and then call that shop to ensure the user's order is ready upon arrival. Upon entering a few keystrokes into a mobile phone device, a local yellow pages channel can be located (assuming a “favorite” Starbucks channel was not present) and queried for a nearby Starbucks coffee shop, perhaps using the phone's GPS data by default as a base location. Due to a consistent multi-prefix search interface, data entry is limited, and channel-specific functionality can then be invoked. For example, a phone number field, associated with the user's selected Starbucks record, can then be leveraged via a simple mechanism, such as a phone button or dynamic menu item, to enable the user to call the desired Starbucks coffee shop and place an order. Another dynamic menu item might provide a map and directions to that Starbucks, enabling the user to arrive in time to pick up that order. Most importantly, all of this functionality can be provided within the context of a highly constrained mobile communications environment.

The features and advantages described in the specification are not all inclusive, and, in particular, many additional features and advantages will be apparent to one of ordinary skill in the art in view of the drawings, specification and claims. Moreover, it should be noted that the language used in the specification has been principally selected for readability and instructional purposes, and may not have been selected to delineate or circumscribe the disclosed subject matter.

