Title of Invention

MOBILE ANSWER ENGINE SYSTEM AND METHOD

Abstract The present invention provides an answer engine system, computer program product and method for mobile users to search across multiple verticals without in-depth encoding of domain knowlodge that presents users with relevant results with minimum number of clicks. The present invention uses a deep analysis of the content for delivering answers, as opposed to natural language processing techniques used by other answer engines.
Full Text

FIELD OF THE INVENTION
The present invention relates to the field of answer engines. More particularly, the present invention relates to the field of answer engines for mobile users.
BACKGROUND AND PRIOR ART
Mobile search engines need to ensure that they help users find what they are looking for using an intuitive user interface and the least number of clicks where clicks include both multi-tap key presses (for entering alphanumeric letters) and scrolling action.
Due to the limited screen real-estate on the mobile devices, mobile search engines need to provide high precision. Further, due to the larger proportion of technically uninterested mobile user population, the search engine must have an easy-to-user interface and should not require users to produce keywords identifying relevant matching results.
Researchers have indicated that there will be subtle differences between the use of mobile devices as compared to the PCs/laptops. It is widely expected that the mobile devices are used for making "urgent" and context-aware (temporal, location-based, etc.) queries.
When we analyze the types of queries/questions that can be expected to be asked from mobile devices, it is apparent that "what", "where", "when", "who" questions will be asked more often than the "why" and "how" questions. The last two categories of questions are often asked when the users are "researching" on a topic, which is an unlikely use of mobile devices, at least by the people who have access of PCs/laptops.
The challenge, therefore, is to build a search engine that is able to handle (a) the "what", "where", "who", and "when" questions and (b) returns more precise answers while taking care of the mobile real-estate constraints at the same time.

US6920459 describes a UI-based mechanism that only identifies the relevance based on "confidence level" of various content categories. However the mechanism disclosed in the patent talks about evaluating relevance based on the top-level categories only as opposed to a deep content analysis disclosed in the present invention.
US20020052894 describes a mechanism that identifies and presents all selected categories and keywords to the users. However, the disclosure does not talk about ordering the selected categories/keywords and does not disclose any mechanism of generating questions at the "right level" in the hierarchy of categories.
WO05083597 discloses a method including the steps of providing a query profiler having a taxonomy database; receiving a query from a user; accessing the taxonomy database of the query profiler to identify a plurality of codes that are relevant to the query; augmenting the query using the codes to generate feedback information to the user for query refinement, the feedback information including a plurality of query terms associated with the query and to be selected by the user; presenting the feedback information to the user; receiving one of the query terms from the user; and identifying a source of the query term and presenting to the user. However, the invention is limited to an existing taxonomy of categories and does not accommodate dynamic modifications to the existing taxonomy and the order in which to provide relevant results according to the preferences of a user.
The aforementioned references display all the possible options to the users. Also, as mentioned, none of the references determine good ordering of the options. The prior-art was good enough for access using web browsers that don't have space constraints. But for mobile users who have real-estate (size) constraints on their screens, filtering and ordering of options can help users in reducing the number of clicks to obtain relevant results.
The present invention provides an answer engine system, computer program product and

method for mobile users to search across multiple verticals without in-depth encoding ot domain knowledge that presents users with relevant options, the options being ordered in such a way that users get the most relevant results with minimum number of clicks. The present invention uses a deep analysis of the content for delivering answers, as opposed to natural language processing techniques used by other answer engines. The analysis is enabled by a multi-dimensional and hierarchical organization of data.
STATEMENT OF THE INVENTION
Accordingly the present invention provides an answer engine system, computer program product and method for mobile users.
In one aspect of the invention, the present invention provides a method to generate an ordered list of options for users to choose to help users get most relevant results for their questions. The method of the invention is enabled by a QA (Question-Answer) algorithm. Picking the optimal answers is a NP-complete problem. The QA algorithm uses heuristics to pick the best options to display.
In another aspect of the invention, the present invention provides a method to generate questions across several verticals without in-depth encoding of domain knowledge and without the need for doing language-specific analysis.
In one embodiment, the aforementioned aspects of the invention are enabled by "multi¬dimensional modeling" of data. The data is arranged in terms of entities and the corresponding facets (i.e. Attributes) making it easier to answer "what", "where", "who", and "when" questions.
In another aspect, the present invention provides multi-dimensional navigation and search interface that helps collect more precise input and, therefore, helps identify more relevant results. Users can either input the keyword they want to search or navigate to a category.

If the user navigates to a category, he is presented with the facets that can be used to continue the search process. Alternatively, if the user enters another keyword, the search is restricted to the "context" specified by the user's navigation action, which is the "navigation context" used for further navigation.
Multi-dimensional systems need significant metadata information. The metadata includes identification of useful dimensions, identification and creation of hierarchies of dimension values as well as the data cleansing and transformation activities to keep metadata clean and consistent. In one embodiment of the invention, the present invention uses user-specified metadata information (user-defined tags) to augment and/or modify hierarchy for more appropriate classification of available content.
In another aspect, the present invention provides a method for user intent inferencing based on "relevance feedback" and analysis of content to identify similarity between query terms and searched dimension values.
In another aspect, the present invention provides a method for dynamic trend detection and identifying the most relevant results (appropriately altering result ranking). The method is enabled through a self-learning ranking detection model called the RFM (where RFM means "Recency, Frequency, Monetary") model, which uses the Recency, Frequency, and Monetary aspects of user's past behavior to determine the order in which the results should be displayed to the users. The RFM model helps the answer engine platform of the present invention to dynamically tune it's results based on past activity of the user-base. This allows the search engine of the answer engine platform to "learn" from the community and to adjust it's results to match the expectations of the community. For example, "Recency" and "Frequency" aspects of the model together allow the search engine to be sensitive to the current trends as well as the seasonality of the search requests. The system continually monitors the community's search history and automatically adjusts the order of the results presented to the users.

In another aspect, the present invention provides a system comprising a plurality of users; a SMS/WAP/GPRS access gateway; an answer engine platform; and any content repository comprising of structured and semi-structured mobile content. The platform further comprises of a content delivery module for delivering content through various modes; a multi-modal user interface to assist the content delivery module in delivering the content; a content retrieval module for retrieving relevant content from a repository; a content repository for storing mobile content and relevant information; and a content acquisition module to analyze raw content and update relevant records and metadata information to the content repository. The content repository module further comprises of a content storage for the mobile content available to the mobile subscribers; a metadata repository of the content; a search repository comprising of the search history of the various users using the system; and a security and administration module to provide the functionality of the ability to define users with appropriate permission, policies for security and content access/modification, schedules for data backup, etc.
In another aspect, the present invention provides a computer program product to enable the method of the invention where the computer program product comprises instructions according to the method of the invention.
BRIEF DESCRIPTION OF THE DRAWINGS
The above aspects of the invention are described in detail with reference to the attached drawings, where:
Fig 1 illustrates the overall method of the invention;
Fig 2 illustrates the environment of the system of the invention;
Fig 3 illustrates the data model used to structure the metadata and content;

Figures 4A and 4B illustrate the search algorithm of the method of the invention;
Fig 5 illustrates the data model used to structure the user profile;
Fig 6 illustrates the mechanism used to add entities and dimensions dynamically;
Figures 7A and 7B show preferred interface provided to the users for searching and preferred interface for presenting results along with relevant dimensions;
Figures 8A and 8B show an example illustrating how results and dimensions are presented to a user;
Figures 9A and 9B show how the system captures how personalization information is captured from the user;
Figures 10A, 10B and10C show an example showing the effect of personalization; and Fig 11 illustrates the overall architecture of the system of the invention. DETAILED DESCRIPTION OF THE INVENTION DEFINITIONS
Cube: Entities that are searched for. Examples: restaurants, mobile games, ring tones, etc. Also called "categories" in the following sections.
Dimension: Attributes of the entities that are being searched. Also, called "facets" in the "faceted classification and search" systems. It has been shown that the facets/dimension values help narrow down the search space very quickly and in an intuitive manner.

Hierarchy: Tree-like organization of the dimension values. (The organization can be a "graph" in the most generic scenario.) Example: "Country —> State — > City —> Locality --> Street Address" is a hierarchy. Given this hierarchy specification, every place in the world can be precisely specified and identified. Unlike this example, most hierarchies are defined directly on top of the data itself.
Multi-dimensional modeling concepts: This term corresponds to the following design principles:
• First, identify the "cubes" that one wants to support. In the mobile world, these
can correspond to the categories that are supported by the mobile operator.
Examples: restaurants, mobile games, music, etc. For each "cube", identify all
interesting facets. It should be possible to identify/derive the facets from the
source data and it should be possible to add new facets as and when they are
presented.
• Second, organize data using "cubes" and "dimensions". However, in order to
provide flexibility, treat "cubes" and "dimensions" symmetrically - therefore,
users can search for a restaurant (cube entity) in a specific location (dimension
value) or, alternatively, users can search for the location (cube entity) based on
desired restaurants (dimension value).
• Third, organize the data (i.e., values) within a dimension using hierarchies.
Query: The free text entered by user to search in the data ("Find").
Question: A refinement option generated from the data to 'drill down' from the initial query to get to the answer in fewest clicks.
Result: A summary of a data entry that matches the user query + refinement selected so far. The words "answer" and "result" are used interchangeably in this specification.

DESCRIPTION
Fig 1 illustrates the interaction of a user with the system of the invention. Broadly, the method of the invention comprises the steps of organizing content into cubes, dimensions, and hierarchies (101); the system receiving first input from user (102); the system presenting the most relevant dimension values for user to choose to narrow the search (103); user providing subsequent inputs by selecting available (whether presented or otherwise) dimension values (105) or providing fresh keywords (104); and the system presenting refined set of answers (106).
Fig 2 illustrates the environment of the system. A plurality of users with mobile terminals (201) interact with the system through an operator's network (202). The system comprises of a SMS/WAP/mobile internet (including but not limited to GPRS, 2.5G and 3G) gateway (203) that helps the users to interact with the system. The system further comprises of an answer engine platform (204) that serves the requests of the user.
DATA MODEL: CUBES, DIMENSIONS AND HIERARCHIES
Fig 3 illustrates the data model. According to the data model, there are two kinds of nodes: metadata nodes (Cube1 - Cuben , Dim1 - Dimn, H1 - Hn, L1 - Ln), and data nodes (C1 - Cn, where C refers to any cube, and in the diagram Cl refers to Cubel and so on). Cube and entity nodes ("Cl Entities" and "C2 Entities") have been separated to make it easier to define new cubes over existing data (i.e. entities and dimensions). An entity can be associated with multiple cubes. Further, an entity can be associated with multiple hierarchies.
Each entity can have two kinds of values associated with it: property and attribute. Properties are values that are typically not used for searching and will not be used to locate an entity. Examples: restaurant owner's phone number, restaurant opening/closing times, etc. Attributes are values that can be used for searching but whose frequency is

below the administrator-specified threshold. If required, attributes can be "promoted" to be dimensions. Further, on-the-fly "promotion" (i.e. in real-time; while the user is querying/browsing) of attributes to dimensions is done if a user's profile and search history suggest such a change.
A dimension includes all possible hierarchies (H1, H2, .. Hn). A cube can establish association with multiple hierarchies within a dimension.
Hierarchies are used primarily for navigation purpose. There are two kinds of hierarchies: Level-based hierarchy (L1 - Ln): where the hierarchy is not data-dependent and the hierarchy organization can be specified a-priori.
Value-based hierarchy: where hierarchy is data-dependent and the hierarchy organization cannot be specified a-priori.
MULTI-DIMENSIONAL NAVIGATION AND SEARCH
In order to help alleviate the inconvenience of data entry on the mobile devices, it is important for the mobile answer engine platform to provide multi-dimensional navigation and search (so that the users can simply select the relevant options instead of typing additional terms to refine the earlier search). Multi-dimensional navigation and search paradigm is very well suited for mobile devices because it is based on how humans interact with each other:
If person "A" inquires about a "good restaurant", the respondent (person "B") typically inquires about various facets/dimensions of restaurants to understand what "A" is looking for. Only after understanding the requirements (which help in narrowing down the search space), "B" provides his/her suggestions.
The multi-dimensional search of the present invention allows the system to collect contextually rich and unambiguous input. User-specified input can then be combined

with implicit context (such as the user's location) as well as personalization information (such as user's preferences based on the past activity record) to identify precise matches.
Search Algorithm
Once the search space is organized into cubes, dimensions, and hierarchies, the system enables the users to navigate only the interesting dimensions and navigate down the hierarchies only as far as they want. Hierarchies are critically important for mobile devices - they help use limited amount of mobile real estate and, by enabling users to select values at the appropriate hierarchy levels, they allow users to specify their requirements precisely. The specific requirements enable the system to identify and order most relevant facets that the users can select to narrow the search, and order the answers to effectively use the space available on a mobile. The search algorithm that enables this is disclosed hereinafter.
Figures 4 A and 4B illustrate the search algorithm of the invention. An inverted index is created of the content that is available. When a user inputs keywords to search for his answers, the answer engine uses the inverted index (401) to find out the matching entities (402). Only those matching entities are considered whose relevance is above a pre¬defined threshold level. The relevance is based on standard information retrieval techniques. By default, there could be an administrator-specified threshold for the number of results to be shown. In general, the exact list of the matching entities is not persisted (405). However, if the number of matches is below the administrator-specified threshold, the exact matches can be persisted (404). If the user does want to browse through all the matches, the system can allow display of matching entity nodes (404) as computed in the manner described hereinafter.
For matching entities, dimensions are identified that are below the administrator-specified threshold (407) and attributes that are above the administrator-specified threshold (408). Based on dimensions and attributes identified, attributes are identified

that need to play the role of "dimensions" for the search (409). In other words, the attributes that are above the administrator-specified threshold are promoted to become additional dimensions (that is, in addition to the statically defined dimensions) dynamically for the current search.
The matching cube entities, dimensions, and dimension values are identified and evaluated. If most of the entities are pointing towards a certain portion of the dimension tree, then corresponding cube and dimension are promoted higher in the order as presented to the user (410).
Whenever a dimension is matched (411) based on users inputs, such match assigns higher weight to the matched dimension (412). Assigning higher weights to matched dimensions helps in displaying the matched dimension first during subsequent traversals. Similarly, the matching dimension values are also assigned appropriate weights proper ordering in subsequent searches (413,414).
The matched entities and matched dimension values are used to choose appropriate hierarchies and appropriate dimension levels to pick answers for the users (415). The chosen cubes, dimensions and hierarchies get assigned weights (416). These weights determine the order of cubes, dimensions, and dimension values to be presented to the user (417).
Example: Search for "wine"
It is possible that the possible matches for "wine" are as part of the restaurant entity' s text (that is, as part of the menu and/or review comments, etc.).
The example illustration of the search algorithm is as follows:
In identifying the corresponding dimensions (let's say: cuisine, location, and price).

■ It is likely that the location dimension will be evenly distributed (i.e. all matching
locations have roughly the same probability of occurrence).
■ It is likely that the cuisine dimension nodes will be clustered. For example, Italian
cuisine might have a high correlation with wine.
■ It is possible that the South Indian cuisine might, have negative correlation with
wine.
■ It is likely that the price dimension nodes will be clustered towards the higher end
of the spectrum.
Therefore, in this example, there is:
■ No need to inquire about the price dimension (since we have an indication of the
price range).
■ Need to reconfirm with the user that he is indeed interested in the Italian cuisine
(ask question with all the matching cuisines; cuisines will be ordered based on
their computed importance/relevance).
■ Need to keep track of the matching cuisine types and the matching price range(s).
■ Need to inquire about the location dimension.
In the aforementioned example, neither the order of the dimensions/dimension-values nor the order of the matching results is pre-configured. The choice of useful dimensions, the ordering of the dimensions, the ranking of matching results, etc. are all personalized and, in addition to the usual IR criteria such as the relevance (and score) of matching entities, are based on either the user's previous interactions or, if required, based on the statistical patterns of the people with similar profile.
Personalization
Personalization requires capturing user's profile and using the profile information during search to provide and order results. As illustrated in Fig 6, in a preferred embodiment, the capturing of user's profile is done creating a cube for "user". Person's profile has (a) a

static part; and (b) a dynamic part.
The static part itself has two components:
■ Attributes: Attributes can be used for navigation. Examples of attributes include
but are not limited to hobbies/interests and demographic information (such as the
age).
■ Properties: Properties cannot be used for navigation. Examples of properties
include but are not limited to name, date of birth, and native place.
The dynamic part consists of:
■ The preferred traversal patterns.
o Example: While searching for restaurants, user prefers to search by location (as opposed to cuisine or price), preferred location itself (such as "East Patel Nagar"), etc.
■ Items searched/browsed recently (including the current session).
■ Any relevant session-specific metadata. The session metadata can then be used to
refine the persistent profile information (when appropriate).
Dynamic part can be used to extract "context" of a search. For example, movie search followed by restaurant search can reuse the location values; airline ticket search followed by hotel search can reuse the location information as well as the dates information.
Further, the static and dynamic part together can be used to influence relevance ranking of the hits. Relevance ranking is obtained by computing the statistical "distance" of the hits from the user's static/dynamic profile. By default, higher weights are assigned to the matches with the dynamic profile.
Dimensions tracked for a user's profile are constant and include user's indentity, demographic information, preferences, and user's recent activity. The values and the associates hierarchies (H1 and H2) of the aforementioned dimensions change based on user's interaction with the system and is dynamic.

Multi-dimensional tagging
In order to make the multi-dimensional search and navigation engine work, we need to extract multi-dimensional metadata from the input data. We assume that the input feed indicates which cube/category it belongs to. (For example, if a mobile operator aggregates "mobile games" syndicated from five different content providers, every feed from the content providers will indicate that it corresponds to the "mobile games".) Since we know the "cubes" corresponding to each entity, the challenge is to extract (a) new dimensions, (b) new dimension values (and place them at the appropriate level in the hierarchy) from the source data, and (c) to resolve/merge the data conflicts.
Unfortunately, it is well-known that generating metadata (steps (a) - (c) mentioned above; in addition, identifying semantically similar terms, etc.) is an expensive operation that requires huge investment of time and effort. Also, the text mining and other semantic analysis require a large amount of manual intervention (for "training" the system) and are computationally very expensive.
Therefore, there is a need of a system that augments the automatic semantic analysis techniques with extra metadata. Following sections describe a multi-dimensional tagging system that enables entities to be tagged implicitly (by the system) as well as explicitly (by the users).
However, unlike the "flat tagging" being encouraged by sites such as Technorati, Del.icio.us, etc. (and, in general, low value being ascribed to taxonomies and ontologies), the multi-dimensional tagging system of the present invention places tags in the right context and, thereby, helps generate extremely useful multi-dimensional metadata such as new dimensions, new dimension values, semantically similar terms, etc.

Multi-dimensional metadata generation
User-specified tags (together with appropriate multi-dimensional context) can be combined with statistical analysis to derive useful multi-dimensional metadata. Though this analysis can be applied to detect new dimensions, identify semantically related terms, etc., the present invention discloses two methods of how this can be achieved.
Hierarchy augmentation
Except for a few dimensions (such as the location dimension, time dimension, etc.), the input data typically does not contain deep hierarchies initially. For example, the "genre" for mobile games at "Mobile Gamer: Midlet Review" has hierarchy with depth = 2. As the number of entities belonging to a particular hierarchy level increase, however, there is a need to classify the corresponding entities in a more granular fashion.
Let's consider an example. Assume that the mobile answer engine platform supports "music" cube (category) that corresponds to the various songs and musical pieces syndicated by the mobile operator. Let's assume that one of the "genre" values corresponds to "classical" and within "classical" two possibilities being "indian classical" and "western classical" hierarchy fragment. As more and more Indian classical pieces are added to the system, there will be a need to refine the classification and tag the pieces as either "Hindustani" or "Carnatic" values.
To handle the aforementioned scenario, there are two possibilities. Once the content provider(s) become aware of the need to classify their content more "accurately", they will start classifying the pieces more granularly. Other possibility is that the users themselves might tag appropriate pieces (using their own tags) in order to improve the precision of their results. The present invention provides for an appropriate user interface (UI) so that the tags can be conveniently associated with specific dimensions and, possibly, with specific dimension values.

Hierarchy modification
Consider another example where user actions can be used to modify data organization in hierarchies. If statistically significant amount of users search for a certain keyword from a specific "navigation context", it implies that the keyword being searched for is a "child" of the current context (more precisely, "child" of the appropriate dimension value). For example, if a lot of users search for "shooting" games under the genre "action" but "shooting" games has been placed under the "simulation" games, then it implies that there is a need to classify "shooting" as a child of "action" instead. With the help of a fine-grained personalization system, the present invention allows to present "shooting" to be under "action" or under "simulation" to the appropriate subsets of users.
In another example, it is also possible that the hierarchies used by different input sources might differ from each other. For example, let's assume that mobile game creators "MGC1" have defined a classification "adventure" under "action" and mobile game creators "MGC2" have defined the reverse, as in "action" under "adventure" as hierarchies. Based on the user preferences, the present invention is adapted to display the more popular option to the end-users. This will help the system to resolve conflicts without the need for substantial technological or human resources.
Hierarchy augmentation and hierarchy modification requires adding entities and dimensions appropriate levels in the hierarchy. Fig 6 illustrates the mechanism of the entity and dimension addition. As is evident, adding a new entity (with new dimensions/attributes) does not require any modifications to the existing data structures because an association exists between an entity instance and the corresponding dimension values. It is easy to identify all dimensions associated with a cube because an association exists between a cube and the corresponding dimensions. Based on the hits due to a user-specified search query, certain attributes can behave like "dimensions" in a session.

In one embodiment, the multi-dimensional search and navigation engine is enabled by the aforementioned algorithm that keeps track of an arbitrary sequence of navigation steps and keyword searches. In order to minimize the size of the user's search session, it keeps track of the context in terms of a "navigation context" and a "search context". This infrastructure enables the system to allow the users to mix navigation and search steps as well as support "nested searches" and completely flexible "undo" semantics (where the user can undo navigation steps, remove search keywords, move up/down hierarchies, etc.). The system also ensures that unless the number of matching entities drops below a phone-specific threshold, the results are not presented to user as a flat (long) list of hits. The thresholds are defined based on the available screen space on a phone.
USER INTERFACE
As illustrated in Fig 7A, users can either input the keyword they want to search (701) or navigate to a category (702) (ex: restaurants, movies, ringtones, games etc.). If the user navigates to a category, he is presented with the dimensions that can be used to continue the search process. For example, if a user chooses "games", then he might be presented with the facets available, examples being "genre", "producer", "price range", "expertise level", "latest games", "most popular games" etc. Alternatively, if the user enters another keyword, the search is restricted to the "context" specified by the user's navigation action (this is called as the "navigation context"). Further, the users can also go back and thereby move up the hierarchy and thus relaxing the constraints and, if required, find "related" matches as well. In addition, the user can personalize his search by clicking the link provided (703).
If a user enters a keyword in search of an answer, the user will be presented with relevant results (704) and along with the results, the user is also presented with other dimensions (705) that he might be interested in to narrow his search. The relevant dimensions are chosen in accordance with the aforementioned algorithm. Figures 8A and 8B illustrate one such example, where user intends to search for a song with lyrics containing the

words "aaja aaja" (read as in hindi) (701), the system provides relevant results (801) and provides the user with dimensions in the form of languages of hindi and punjabi (802) in which such songs might exist. This provides the user with a choice to stick to any one language that the user is interested in, if he chooses to.
If the user chooses to personalize his search by clicking the link (703), the system asks the user to input information that can be used to build the user's profile and provide personalized answers to queries. As shown in Fig 9A, in addition to the demographic information (901) captured, the system also captures users interests by asking for tags that would describe the users interests adequately (902). These tags will be used as part of the preferences of the users profiles.
As shown in Fig 9B, the system asks for users relevancy feedback for a particular result (upon user selecting a result) by asking the users to input tags for the result (903) that they is more appropriate. This helps in building the user profile. The user can also provide other suggestions (903) about the system which the system administrator may consider. As part of the suggestions, users are expected to provide feedback as to how relevant the results are.
Figures 10 A, 10B, and 10C illustrate the result of personalization. A user may choose to search for the name of the singer "Balasubramaniam". Let us assume that the system contains ringtones of songs sung by Balasubramaniam in Tamil and Hindi languages. For a set of users whose preferred language is Tamil, the system may throw Tamil results ahead of results in Hindi (1001). For other users who prefer Hindi over Tamil, the system throws up Hindi results ahead of Hindi (1002). However, both the dimensions (languages) are presented to the users so as provide choice to the users. Subsequently, users may choose to browse ringtones of songs in a particular language only by clicking that particular dimension (language).

SYSTEM
Figure 11 is the architecture diagram illustrating the key components of the answer engine platform. The platform comprises of a content delivery module (1160); a multi-modal user interface module (1150); a content retrieval module (1140); a content repository (1130); a content acquisition modulell20; and plurality of content sources (including but not limited to music; video; ringtones; games; information sources like such as yellow pages, events, weather, stock prices, and sports updates; RSS; and themes) (1110).
The content acquisition module (1120) is used to upload the content into the content repository. The important functionality provided by this module is the ability to upload new content into the content repository at regular intervals. This is done by specifying appropriate criteria for identifying the new records in the source repository. In addition, the system allows the system administrator to define the configurable data upload frequency parameter as per the customer's requirements. The source repository can be of varied nature as illustrated in the figure. In addition, the content acquisition module also provides the ability to analyze and understand the underlying customer data. The metadata extracted during the content acquisition phase is uploaded to the metadata repository (1132).
The mobile content as well as it's associated properties including metadata are stored in a content repository (1130). The metadata associated with the content assimilated search system is maintained in a metadata repository (1132). The content repository module comprises of a cotent storage (1131) of the mobile content available to the mobile subscribers; a metadata repository of the content (1132); a search repository (1133) comprising of the search history of the various users using the system; and a security and administration module (1134) to provide the functionality of the ability to define users with appropriate permission, policies for security and content access/modification, schedules for data backup, etc.

The content retrieval module provides the ability to search and navigate the content repository. The content retrieval module comprises of the search engine (1141) implementing the QA algorithm. The content retrieval module further comprises of a personalization module (1142) and a recommendation module (1143) to help in fetching relevant answers.
The personalization module (1142) provides the capability to create implicit profile of users and to continually update the profile based on user's search patterns. The module uses machine learning techniques to construct a model of user's interests. The user's profile (captured in the model) is used to ensure that the results are presented to match user's implicit preferences. The model is updated based on user's interaction with the system; this helps the personalization module to adapt quickly and, therefore, helps users find the relevant content at all times.
The recommendation process enabled by the recommendation module (1143) can be divided into online (real-time) analysis and offline analysis. User's actions in a session are used to personalize the results as well as to provide useful suggestions. Further, user's interactions are processed using an offline system to recommend entities to users based on their past behavior. The module utilizes both the content-based and user-based algorithms to identify entities that can be recommended to the users. The module extracts usage patterns across the whole community of users and identifies the most relevant recommendations based on the user's current activity. As opposed to the personalization module that focuses on the behavior of an individual user, recommendation system performs its analysis based on the interaction patterns across various groups of users as well as the activity recorded for the whole community.
The multi-modal user interface module (1150) provides capabilities to be able to deliver content through varied interfaces by providing text-to-speech, advanced speech recognition, scripting (1152), SMS and UI modules (1153). The multi-model user

interface also provides means for user and session information management (1151). The session information is used by the personalization (1142, for fetching relevant results) and recommendation (1143, for recommending useful dimensions) modules.
The content delivery module provides the facility to deliver content through multiple channels including IVR (1161), WAP (1162), SMS (1163), and HTTP browser (1164). The content delivery module uses the multi-modal user interface module to deliver content to the end user appropriately. For example, to deliver the content through IVR module, the content delivery module uses the text to speech (TTS)/ Advanced speech recognition (ASR) capabilities provided by the multi-model user interface module.
One of the unique requirements of a mobile search engine is the need to be able to work with multi-modal front-ends. More specifically, integration with an IVR (Interactive Voice Response) platform is an important requirement for mobile search engines. The proposed mobile answer engine platform is amenable to voice-activated input because, at any given time, there are a finite number of possible navigational paths. The paths for a given context can be determined by making use of the "navigation context". For example, if the user navigates to the "Games" category, he will be requested to choose from one of the six aforementioned facets (corresponding to the dimensions). These options can be easily converted into voice output; further, since the user must choose from one of these options, the speech to text conversion problem is also made simpler.
Although the present invention has been described with particular reference to specific examples, variations and modifications of the present invention can be effected within the spirit and scope of the following claims.









WHAT IS CLAIMED IS:

1. Method of providing a mobile user with relevant and ordered answers in an answer

engine system, the method using multi-dimensional modeling of data to provide relevant
and ordered answers to user's queries, the method comprising the steps of:
a. organizing content into cubes, dimensions and hierarchies;
b. receiving a first input from a user's mobile terminal;
c. the system asking the user a sequence of relevant and precise questions to find
relevant answers; and
d. presenting relevant and ordered answers to the user's mobile terminal.
2. A method as in claim 1, the method further comprising the steps of:
a. creating an inverted index of content;
b. the answer engine using the inverted index to find out the matching entities for the
input provided by the user, the input being provided at the user's mobile terminal;
c. listing matching entities where only those matching entities are considered whose
relevance is above a pre-defined threshold level;
d. facets are identified that need to play the role of "dimensions" for the search
where dimensions are identified that are below the administrator-specified
threshold and attributes that are above the administrator-specified threshold and
where the matching attributes whose relevance is above the administrator-
specified threshold are promoted to become dimensions dynamically for the
current search;
e. identifying all dimension nodes pointed to by the matching entities;
f. identifying the order of cubes and dimensions by analyzing the matching entities;
g. assigning higher weights to matched dimensions;
h. matching dimension values within identified dimensions using the input provided
by the user;
i. assigning higher weights to matched dimension values; j. choosing appropriate hierarchies and dimension levels to pick answers from; and

k. ordering the answers in accordance with the weights of cubes, dimensions and dimension values.
3. A method as in claim 2, where relevance is based on standard information retrieval
techniques.
4. A method as in claim 2, where the number of results shown is based on an administrator-
specified threshold for the number of results to be shown.
5. A method as in claim 2, where the user can choose to view all the matching results.
6. A method as in claim 2, the method further comprising the step of personalizing search
wherein user information is stored in static and dynamic parts of a user specific data
structure, the static part of the data structure comprising persistent user profile
information including at least name, date of birth, native place, hobbies, interests, and
demography; and the dynamic part of the data structure comprising session specific
metadata.
7. A method as in claim 6, where dynamic part of the user specific data structure is used to
extract context of a search.
8. The method as in claim 7, wherein the relevant set of answers are presented in an order
according to a dynamic ranking mechanism that uses both relevance ranking mechanism
where the relevance is based on statistical distance of answers from the user's static and
dynamic profile information; and a RFM-based model, adapted to automatically detect
trends on user queries and modify the relevance associated with different results.
9. A method as in claim 1, where the first input is a set of keywords input by the user on a
search interface

10. A method as in claim 1, where the first input is a selection of a category chosen by the
user from a list of available categories.
11. A method as in claim 1, where organization of content is language-independent
12. A method as in claim 1, the method further comprising the step of receiving feedback on
relevancy of answers from user.
13. A method as in claim 12, the method further comprising the step of inferencing user
intent by analyzing content to identify similarity between query terms and searched
dimension values based on relevance feedback.
14. A method as in claim 13, the method further comprising the step of suggesting the next
facet to be chosen by the user without the user having to select or enter a facet.
15. The method as in claim 1, where the step of asking a sequence of questions further
comprising the steps of
retaining the context based on user's inputs; and
presenting a set of available facets for the user to choose to further narrow the query.
16. A method as in claim 1, where the repository content is vertical independent
17. A method as in claim 1, the method further comprising the steps of:
a. collecting user defined tags as provided by the users while user is seeking answers
to queries; and
b. analyzing user defined tags for statistical significance and applying user defined
tags to the content for augmenting and modifying the hierarchy of dimensions for
further usage.

18. A method as in claim 15, where the presentation of available facets is on an IVR
interface.
19. The method as in claim 15, the method further comprising the step of user broadening the
context by going up the hierarchy of facets
20. A method as in claim 15, where the presentation of available facets is on a display device
of the mobile.
21. A method as in claim 18, where the information including available facets and the results
are sent to the user's mobile terminal using SMS.
22. A method as in claim 18, where the information including available facets and the results
are sent to the user's mobile terminal, the information formated to be viewed on a WAP
browser.
23. A method as in claim 18, where the information including available facets and the results
are sent to the user's mobile terminal, the information formated to be viewed on a HTTP
browser.
24. A method of augmenting the hierarchy of dimensions of content in an answer engine, the
method comprising the steps of:
a. organizing content of the answer engine into cubes, dimensions, and hierarchies;
b. collecting user defined tags as provided by the users while user is seeking answers
from the answer engine;
c. analyzing user defined tags for statistical significance; and
d. applying user defined tags to the content for further usage.

25. A method of modifying the hierarchy of dimensions of content in an answer engine, the
method comprising the steps of:
a. organizing content of the answer engine into cubes, dimensions, and hierarchies;
b. analyzing previous user queries for statistical significance within a given context
where a user is searching content repeatedly in the same context; and
c. modifying the hierarchy by adding entities and dimensions in the hierarchy in
accordance with user's preferences based on previous queries.
26. An answer engine system to enable users to search relevant and ordered answers, the
system comprising of:
a. a plurality of mobile terminals;
b. an answer engine platform;
c. an operator's network connecting the mobile terminals of users with the answer
engine platform; and
d. a gateway that helps the users to interact with the answer engine system.
27. An answer engine system as in claim 23, where a mobile terminal is a wireless hand-held
device.
28. An answer engine system as in claim 27, where mobile terminal is a wireless mobile
phone.
29. An answer engine system as in claim 27, where mobile terminal is a PDA.
30. An answer engine system as in claim 23, where the gateway is an SMS gateway.
31. An answer engine system as in claim 30, where the gateway is a WAP gateway.
32. An answer engine system as in claim 30, where the gateway is a mobile internet gateway.

33. An answer engine system as in claim 23, the answer engine platform further comprising:
a. a content delivery module for delivering content through various modes;
b. a multi-modal user interface to assist the content delivery module in delivering the
content;
c. a content retrieval module for retrieving relevant content from a repository, the
content retrieval module further comprising of:
i. a search engine for performing search and retrieving relevant answers;
ii. a personalization module to personalize the answers based on a user's
interests; and iii. a recommendation module to make recommendations based on usage patterns
of communities that the user belongs to;
d. a content repository for storing mobile content and relevant information, the
content repository further comprising of:
i. a cotent storage for the mobile content available to the mobile subscribers;
ii. a metadata repository of the content;
iii. a search repository comprising of the search history of the various users using the system; and
iv. a security and administration module to provide the functionality of the ability to define at least users with appropriate permission, policies for security and content access/modification, and schedules for data backup;
e. a content acquisition module to analyze raw content and update relevant records
and metadata information to the content repository; and
f. a plurality of content sources.
34. An answer engine system as in claim 33, where content delivery module is adapted to
deliver content on an IVR interface.
35. An answer engine system as in claim 33, where content delivery is adapted to deliver
content as SMS.

36. An answer engine system as in claim 33, where content delivery is adapted to deliver
content amenable to be viewed on a WAP browser.
37. An answer engine system as in claim 33, where content delivery is adapted to deliver
content amenable to be viewed on a HTTP browser.
38. An answer engine system as in claim 33, where the content source is a music content
source.
39. An answer engine system as in claim 33, where the content source is a video content
source.
40. An answer engine system as in claim 33, where the content source is a ringtone content
source.
41. An answer engine system as in claim 33, where the content source is a games content
source.
42. An answer engine system as in claim 33, where the content source is an information
content source.
43. An answer engine system as in claim 33, where the content source is a RSS content
source.
44. An answer engine system as in claim 33, where the content source is a themes content
source.

45. A computer program product comprising of instructions according to a method of
providing a mobile user with relevant and ordered answers in an answer engine system,
the method using multi-dimensional modeling of data to provide quick and relevant
answers to user's queries, the instructions being:
a. storing content in a multi-dimensional data model in a non-volatile memory, the
multi-dimensional data model comprising cubes, dimensions and hierarchies;
b. receiving a first input from a user's mobile terminal;
c. asking the user a sequence of relevant and precise questions to find relevant
answers; and
d. presenting relevant and ordered answers to the user's mobile terminal.
46. A computer program product as in claim 45, further comprising instructions of:
a. creating an inverted index of content;
b. the answer engine using the inverted index to find out the matching entities for the
input provided by the user, the input being provided at the user's mobile terminal;
c. listing matching entities where only those matching entities are considered whose
relevance is above a pre-defined threshold level;
d. facets are identified that need to play the role of "dimensions" for the search
where dimensions are identified that are below the administrator-specified
threshold and attributes that are above the administrator-specified threshold and
where the matching attributes whose relevance is above the administrator-
specified threshold are promoted to become dimensions dynamically for the
current search;
e. identifying all dimension nodes pointed to by the matching entities;
f. identifying the order of cubes and dimensions by analyzing the matching entities;
g. assigning higher weights to matched dimensions;
h. matching dimension values within identified dimensions using the input provided
by the user;
i. assigning higher weights to matched dimension values; j. choosing appropriate hierarchies and dimension levels to pick answers from; and

k. ordering the answers in accordance with the weights of cubes, dimensions and dimension values.
47. A computer program product as in claim 46, where relevance is based on standard
information retrieval techniques.
48. A computer program product as in claim 46, where the number of results shown is based
on an administrator-specified threshold for the number of results to be shown.
49. A computer program product as in claim 46, where the user can choose to view all the
matching results.
50. A computer program product as in claim 46, further comprising instructions of
personalizing search wherein user information is stored in static and dynamic parts of a
user specific data structure, the static part of the data structure comprising persistent user
profile information including at least name, date of birth, native place, hobbies, interests,
and demography; and the dynamic part of the data structure comprising session specific
metadata.
51. A computer program product as in claim 50, where dynamic part of the user specific data
structure is used to extract context of a search.
52. A computer program product as in claim 51, wherein the relevant set of answers are
presented in an order according to a dynamic ranking mechanism that uses both relevance
ranking mechanism where the relevance is based on statistical distance of answers from
the user's static and dynamic profile information; and a RFM-based model, adapted to
automatically detect trends on user queries and modify the relevance associated with
different results.

53. A computer program product as in claim 45, where the first input is a set of keywords
input by the user on a search interface
54. A computer program product as in claim 45, where the first input is a selection of a
category chosen by the user from a list of available categories.
55. A computer program product as in claim 45, where organization of content is language-
independent
56. A computer program product as in claim 45, further comprising instructions of receiving
feedback on relevancy of answers from user.
57. A computer program product as in claim 56, further comprising instructions of
inferencing user intent by analyzing content to identify similarity between query terms
and searched dimension values based on relevance feedback.
58. A computer program product as in claim 57, further comprising instructions of
suggesting the next facet to be chosen by the user without the user having to select or
enter a facet.
59. The method as in claim 45, where the step of asking a sequence of questions further
comprising the instructions of:
retaining the context based on user's inputs; and
presenting a set of available facets for the user to choose to further narrow the query.
60. A computer program product as in claim 45, where the repository content is vertical
independent

61. A computer program product as in claim 45, further comprising instructions of:
a. collecting user defined tags as provided by the users while user is seeking answers
to queries; and
b. analyzing user defined tags for statistical significance and applying user defined
tags to the content for augmenting and modifying the hierarchy of dimensions for
further usage.
62. A computer program product as in claim 59, where the presentation of available facets is
on an IVR interface.
63. A computer program product as in claim 59, further comprising instructions of user
broadening the context by going up the hierarchy of facets
64. A computer program product as in claim 59, where the presentation of available facets is
on a display device of the mobile.
65. A computer program product as in claim 62, where the information including available
facets and the results are sent to the user's mobile terminal using SMS.
66. A computer program product as in claim 62, where the information including available
facets and the results are sent to the user's mobile terminal, the information formated to
be viewed on a WAP browser.
67. A computer program product as in claim 62, where the information including available
facets and the results are sent to the user's mobile terminal, the information formated to
be viewed on a HTTP browser.
68. A computer program product comprising instructions according to a method of
augmenting the hierarchy of dimensions of content in an answer engine, the computer
program product comprising instructions of:

a. organizing content of the answer engine into cubes, dimensions, and hierarchies;
b. collecting user defined tags as provided by the users while user is seeking answers
from the answer engine;
c. analyzing user defined tags for statistical significance; and
d. applying user defined tags to the content for further usage.
69. A computer program product comprising instructions according to a method of modifying the hierarchy of dimensions of content in an answer engine, the computer program product comprising instructions of:
a. organizing content of the answer engine into cubes, dimensions, and hierarchies;
b. analyzing previous user queries for statistical significance within a given context
where a user is searching content repeatedly in the same context; and
c. modifying the hierarchy by adding entities and dimensions in the hierarchy in
accordance with user's preferences based on previous queries.


Documents:

493-che-2007 correspondence others 02-02-2011.pdf

493-CHE-2007 POWER OF ATTORNEY 01-11-2010.pdf

493-che-2007 amended pages of specification 16-03-2011.pdf

493-CHE-2007 AMENDED CLAIMS 01-11-2010.pdf

493-che-2007 amended claims 16-03-2011.pdf

493-CHE-2007 AMENDED PAGES OF SPECIFICATION 01-11-2010.pdf

493-che-2007 correspondence others 16-03-2011.pdf

493-CHE-2007 CORRESPONDENCE OTHERS 24-01-2011.pdf

493-CHE-2007 EXAMINATION REPORT REPLY RECIEVED 01-11-2010.pdf

493-CHE-2007 FORM-13 01-11-2010.pdf

493-che-2007 form-3 01-11-2010.pdf

493-che-2007 form-5 01-11-2010.pdf

493-che-2007-abstract.pdf

493-che-2007-claims.pdf

493-che-2007-correspondnece-others.pdf

493-che-2007-description(complete).pdf

493-che-2007-drawings.pdf

493-che-2007-form 1.pdf

493-che-2007-form 18.pdf

493-che-2007-form 26.pdf

493-che-2007-form 3.pdf

493-che-2007-form 5.pdf


Patent Number 246912
Indian Patent Application Number 493/CHE/2007
PG Journal Number 12/2011
Publication Date 25-Mar-2011
Grant Date 21-Mar-2011
Date of Filing 12-Mar-2007
Name of Patentee AJAY SETHI
Applicant Address NO. 28, NSR-GIV CENTRE, INDIAN INSTITUTE OF MANAGEMENT, BANNERGHATTA ROAD, BANGALORE, 560076, KARNATAKA, INDIA
Inventors:
# Inventor's Name Inventor's Address
1 AJAY SETHI NO. 28, NSR-GIV CENTRE, INDIAN INSTITUTE OF MANAGEMENT, BANNERGHATTA ROAD, BANGALORE, 560076, KARNATAKA, INDIA
PCT International Classification Number H04 Q 9/00
PCT International Application Number N/A
PCT International Filing date
PCT Conventions:
# PCT Application Number Date of Convention Priority Country
1 NA