Note: Descriptions are shown in the official language in which they were submitted.
CA 02590517 2007-05-29
Method and System for Providing Ranked Search Results
FIELD OF INVENTION
[0001 ] The present invention relates to a method and system for ranked search
results, and especially to a method and system that improves search queries
using
declarative taxonomies.
BACKGROUND OF THE INVENTION
[0002] There are various search engines available to conduct full text
searches.
However, full text searches often involves ambiguities in their search
queries.
Especially, traditional search technologies often provide incomplete or
irrelevant
results in the Corporate Performance Management (CPM) environments. In the
CPM environments, CPM tools, such as Business Intelligence (BI) tools, are
used to
manage business oriented data and metadata.
[0003] Declarative taxonomies, which are well-defined, external subject
hierarchies,
are often used to disambiguate full text search queries. When searching a
taxonomy
for subjects related to a given set of search terms, full text search engines
can match
from zero to millions of subject items. The resulting "disambiguated" queries
can
contain literally millions of extra search terms. Searching for "popular"
terms in the
business environments, such as "sales", "product" or "revenue", often add too
many
additional subject related terms to be useful.
[0004] Search engines routinely use methods such as "page rank" references and
other statistical and linguistic ranking criteria to create ordered search
results. An
example of such search engines is a page ranking engine that is described in
US
Patent No. 6,526,440 issued to Bharat. However, these search engines are not
sufficient to search complex data like business oriented metadata since they
rely on
ranking algorithms that work with data found primarily in the Global Internet
and not
inside a business.
-1-
CA 02590517 2007-05-29
[0005] Some search engines use taxonomies to improve search results. Creation
of
taxonomies has been carried out by a manual process or by an automated process
based on advanced linguistic analysis. However, business taxonomies are
difficult
and expensive to build manually. Also, linguistic analysis is often
complicated and
thus prone to result in inaccurate outcome.
[0006] In addition, these search engines employ the statistical or linguistic
ranking
algorithms or methods over search results. Accordingly, these methods do not
avoid
the problems that are involved in the search results as described above.
[0007] It is therefore desirable to provide a system that provides better
search
results.
SUMMARY OF THE INVENTION
[0008] It is an object of the invention to provide an improved method and
system for
providing search results using taxonomies.
[0009] The invention uses a subject ranking method that allows subject data to
be
ranked by relevance. In an embodiment, the resulting subjects are then used to
augment an operator query to provide matches about related subjects or
concepts.
[0010] In accordance with an aspect of the present invention, there is
provided a
subject ranking management system for providing ranked search results. The
subject ranking management system comprises a subject hierarchy managing unit,
a
ranking calculation unit, and a result organizing unit. The subject hierarchy
managing unit is provided for determining, using a taxonomy, one or more
parent
subject items for one or more matching subject items that match a given set of
one
or more search terms. The ranking calculation unit is provided for
statistically
ranking relevant subject items including the matching subject items and the
parent
subject items. The result organizing unit is provided for organizing the
relevant
subject items as ranked by the item ranking calculation unit.
-2-
CA 02590517 2007-05-29
[0011] In accordance with another aspect of the invention, there is provided a
method of providing a ranked search result. The method comprises the steps of
determining, using a taxonomy, one or more parent subject items of one or more
matching subject items that match a given set of one or more search terms,
statistically ranking relevant subject items including the matching subject
items and
the parent subject items, and organizing the relevant subject items based on
the
ranking.
[0012] In accordance with another aspect of the invention, there is provided a
computer readable medium storing computer readable code having instructions or
statements for use in the execution in a computer of a method of providing a
ranked
search result. The method comprises the steps of determining, using a
taxonomy,
one or more parent subject items of one or more matching subject items that
match
a given set of one or more search terms, statistically ranking relevant
subject items
including the matching subject items and the parent subject items, and
organizing
the relevant subject items based on the ranking.
[0013] In accordance with another aspect of the invention, there is provided a
compute program product for use in a subject ranking management system for
providing ranked search results, the computer program product having computer
program code embodied in a machine readable medium. The computer program
product comprises a module for determining, using a taxonomy, one or more
parent
subject items of one or more matching subject items that match a given set of
one or
more search terms, a module for statistically ranking relevant subject items
including
the matching subject items and the parent subject items, and a module for
organizing
the relevant subject items based on the ranking.
[0014] This summary of the invention does not necessarily describe all
features of
the invention.
-3-
CA 02590517 2007-05-29
BRIEF DESCRIPTION OF THE DRAWINGS
[0015] These and other features of the invention will become more apparent
from the
following description in which reference is made to the appended drawings
wherein:
Figure 1 is a block diagram showing a subject ranking management system in
accordance with an embodiment of the present invention;
Figure 2 is a block diagram showing an embodiment of the subject ranking
management system;
Figure 2A is a block diagram showing an embodiment of the ranking calculation
unit;
Figure 3 is a block diagram showing an embodiment of a subject hierarchy
managing
unit of the subject ranking management system;
Figure 4 is a diagram showing another embodiment of the subject ranking
management system;
Figure 5 is a diagram showing an example of a subject hierarchy;
Figure 6 is a diagram showing an example of hierarchy scores; and
Figure 7 is a flowchart showing a subject ranking method in accordance with an
embodiment of the present invention.
DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS
[0016] Referring to Figure 1, a subject ranking management system 10 in
accordance with an embodiment of the invention is described. The subject
ranking
management system 10 suitably works with a full-text search engine 30 that
holds a
taxonomy 40. The taxonomy 40 is a declarative taxonomy that represents well-
defined, external hierarchies of topics or subjects. The search engine 30 is
used to
search a target index corpus 50 for search terms or target data that is
related in a
certain manner to the taxonomy 40. The index corpus 50 stores indexes of data
or
terms in documents to be searched. The search engine 30 searches the index
corpus 50 for a given set of search terms contained in a query and generates a
-4-
CA 02590517 2007-05-29
search result containing subject data or items that match the given set of
search
terms.
[0017] The subject ranking management system 10 takes the search result of the
search engine 30 as an intermediate result, and applies ranking to the subject
data
in the intermediate result so that the subject data is ranked by relevance,
rather than
applying ranking to search results that would be generated if the search terms
were
given directly to the index corpus 50. This allows related subjects, or a
subset of
subjects related to the search terms, to be effectively used by the search
engine 30
in a subsequent search of the index corpus 50. Using related subjects in a
subsequent search of the index corpus 50 generally provides additional
relevant
search results that would not otherwise be included in search results
generated from
search terms alone.
[0018] In order to apply ranking to subject data, the subject ranking
management
system 10 employs a statistical subject ranking algorithm or method that
relies
primarily on mathematics, rather than language semantics, to build full text
search
queries, or operator queries Using the subject ranking method, the subject
ranking
management system 10 attempts to reorganize the intermediate results, e.g.,
move
relevant high-level subject items to the top of an intermediate result list.
The subject
ranking management system 10 also attempts to retrieve related terms or
subject
items and add them to the intermediate result list. Such intermediate results
are
used, in turn, to build a more precise and yet wider ranging full-text search
query.
Thus, the subject ranking management system 10 can augment the query so that
the
augmented query is applied against the index corpus 50. These augmented full
text
search queries based on additional terms retrieved from the subject ranking
method
are often better than those based on language semantics. Thus, the full text
search
queries based on the subject ranking method often provide better search
results
against a related target index corpus 50.
-5-
CA 02590517 2007-05-29
[0019] The intermediate results returned to the subject ranking management
system
from the search engine 30 are subject items from the index corpus 50 that
represents the declared taxonomy 40. For example, consider a taxonomy with the
following structure:
Countries
North America
Canada
USA
[0020] There are index items in the index corpus 50 that describe the
following
subject items:
1) the subject name
2) one or more references to original business data
3) Reference to one or more parent subject items also stored in the index
corpus 50
4) Reference to one or more child subject items also stored in the index
corpus 50
[0021] The subject name is ultimately used in the subsequent query to the
index
corpus 50. The references to parent subject items and children subject items
are
primary factor in determining the ranking of each subject item that matched
the
search terms.
[0022] Figure 2 shows an embodiment of the subject ranking management system
10. The subject ranking management system 10 has a subject hierarchy managing
unit 100, a ranking calculation unit 120 and a result organizing unit 140.
[0023] The subject hierarchy manager 100 manages a search result generated by
the search engine 30 for a given set of search terms. The search result
contains
subject items that matched the given set of search terms. The subject
hierarchy
managing unit 100 also finds parent subject items for the matching subject
items
using the taxonomy 40 of the search engine 30. In short, the subject hierarchy
manager 100 returns a ranked set of subject items that match a given set of
search
-6-
CA 02590517 2007-05-29
terms and the parent subject items of the matching subject items. The matching
subject items and their parent items may be collectively called "relevant
subject
items" hereinafter.
[0024] The ranking calculation unit 120 manages calculation of ranking of the
relevant subject items. Figure 2A shows an embodiment of the ranking
calculation
unit 120. The ranking calculation unit 120 has a relevance handler 122 to
determine
ranking order for the relevant subject items.
[0025] The relevance handler 122 orders requests for subject items that match
a
given set of search terms. It also receives from the subject hierarchy
managing unit
100 the information of the parent subject items for the matching subject
items.
[0026] The relevance handler 122 scores the relevant subject items based on
hierarchy relationships to other subject items and the number of references to
the
relevant one of the matched subject items in the original indexed business
data as
represented by the taxonomy 40. The relevance handler 122 performs ranking
score
calculation so as to provide higher scores for more relevant subject items.
[0027] The relevance handler 122 uses a child aggregator 126, a hierarchical
distance handler 128, and a reference aggregator 129. The child aggregator 126
aggregates the child subject items under a matching subject item in order to
calculate a ranking score of the subject item. The relevance aggregator 129
counts
references to a subject item in the original business content as represented
in the
taxonomy 40. The relevance aggregator 129 combines subject items with the same
name into single result items. For example, all items with the name 'sales',
each
referencing different instances of business data, are combined into one item
with
name 'sales' that simultaneously references different business data instances.
Items
with more references are given preference. The hierarchical distance handler
128
determines a hierarchical distance from a matching subject item, i.e., the
number of
ancestors, to calculate a ranking score of each relevant subject item. Subject
items
-7-
CA 02590517 2007-05-29
that are closer to a matching subject item in hierarchical distance, are given
preference to subject items that are further away from a matching subject
item.
[0028] The result organizing unit 140 organizes the relevant subject items as
ranked
by the item ranking calculation unit 120. It typically rolls up subject items
with the
highest ranking scores to the top of a result list. The result organizing unit
140 may
organize the results in a list form, in a form that is easy to view on a
portable device,
or in other form.
[0029] Thus, the subject ranking management system 10 removes the need to
organize subject data exclusively in a tree form, which is a typical form of
taxonomy
presentation used in existing tools. The subject ranking management system 10
allows subjects to be displayed in lists or other types of user interface,
such as, a
type suitable for wireless devices.
[0030] The lists of subjects can also be used as "additional criteria" in
further
searches. To this end, the subject ranking management system 10 may also have
a
search query building unit 160, as shown in Figure 2. The search query builder
160
builds a search query based on the ranked relevant subject items that are
determined as being relevant by the ranking calculation unit 120. Such a
search
query improves result relevance and increases search speed when searching for
terms that have a high number of occurrences in the subject index corpus 50.
[0031] The subject ranking management system 10 uses the declarative taxonomy
40. The taxonomy 40 may be held in the subject ranking management system 10.
The subject ranking management system 10 may use a taxonomy built from
business intelligence metadata, or other types of taxonomies, such as
taxonomies
available for biology, zoology, botany and paleontology.
[0032] As shown in Figure 3, the subject hierarchy managing unit 100 may have
an
augmentation limiter 102. The augmentation limiter 102 limits the number of
parent
-8-
CA 02590517 2007-05-29
levels searched to avoid undesirable reduction in a search speed. It also
limits the
number of ancestors that can affect relevance ranking as the hierarchical
distance
increases.
[0033] Also, the subject hierarchy managing unit 100 may have a parent
identification
handler 104 that provides to each subject in the index corpus 50 an
identification of a
parent subject item using the taxonomy 40. The subject hierarchy managing unit
100 can use the parent identifications to easily determine parent subject
items of
matching subject items. Also, the ranking calculation unit 120 can use the
parent
identifications to determine child subject items under a patent subject item.
[0034] Figure 4 shows the subject ranking method that ranks related subject
items by
relevance. The subject ranking method is a parameterized component. It is
controlled by parameters that cause it to return different result sets for the
same
search terms.
[0035] The subject ranking management system 10 receives a search result
containing subject items that match a given set of search terms (200). The
system
determines parent subject items of the matching subject items, using the
taxonomy 40 (202). Then, the system 10 statistically ranks the relevant
subject
items including the matching subject items and the parent subject items (204).
The
ranking is carried out by determining ranking scores for the relevant subject
items
based on the number of references to a matching subject item, and the item's
relationship to other subject items other relevant subject items (206). The
relevant
subject items are organized based on the ranking (210). The subject ranking
management system 10 may optionally build a new search query using the
relevant
subject items as additional criteria for a further search (212). This
additional criteria
can be applied without any operator action. Subsequent searches based on the
ranked subject items can also be applied by allowing the operator to select
from a list
of ranked subject items.
-9-
CA 02590517 2007-05-29
[0036] The subject ranking by the subject ranking management system 10 is now
further described using an example hierarchy of subject items shown in Figure
5.
The hierarchy of subject items may be held in a full text index of the subject
ranking
management system 10. This hierarchy defines a taxonomy of "is a"
relationships
obtained from business intelligence metadata.
[0037] Each subject items in the full text index may be represented as a
document,
e.g., a full-text index document, with field: type set to subject. Each
document also
contains, among other things, the following fields:
Field Contents
id Unique document ID for this item (a searchable GUID in text form)
name Display name for item
parentld Document ID of a parent in the hierarchy. Null means a top
level-subject. Multiple parent relationships are represented with multiple
child
documents each pointing to different parents.
[0038] This structure makes it easy to find parents of a given subject
document by
simply retrieving the document specified in the parentlD field. It is also
relatively
easy to find children of a given ID by simply executing a full-text search for
documents with the parentlD field equal to the given ID.
[0039] A full text search of the subject hierarchy returns a list of matching
documents.
As mentioned previously, each document contains a parentlD field that points
to the
parent subject. In this example, subject items with term "bag" is searched.
The
search results in subject items matching with the search term "bag" as shown
in
Table 1.
[0040] Table 1
Name ID ParentlD
Sleeping Bags 43 72
-10-
CA 02590517 2007-05-29
Mountain Bag 54 43
Suit Bag 65 76
Carry Bag 98 22
Bag Stuff-Sack 88 66
Bag Ties 86 68
Pillow Bag 55 66
Bag of jokes 69 96
... Nn Mm
[0041] In order to find important topics related to the hierarchy implied in
table 1, the
subject rank management system 10 determines ranking scores for the matching
subject items. Also, the system 10, using the parentlD in Table 1, determines
parent
subject items, as shown in Figure 6, and determines their hierarchy scores. As
shown in Figure 6, some subject items, e.g., Products and Outdoor Equipment,
that
were not matched in the initial search are very relevant to the search term.
[0042] The subject ranking system 10 attempts to move relevant high-level
subjects
to the top of result list. It determines ranking scores of the matching
subject items
and their parent subject items using the subject ranking method. In this
example, the
system 10 uses the following mathematical formula for subject scoring:
R = T + R*Rf+ S1..n(Dn/Df)
where: R = Ranking Score
T= Term score for subject from search engine
Si..,, = Sum of all children from 1 to n
Dn = Hierarchical distance for child n from this item
Df = Distance "boost" factor for each hierarchical distance step
R Number references to data
Rf = Reference "boost" factor for referenced items.
When a subject has no children (i.e., it is a leaf node), its T value is used
directly.
-11-
CA 02590517 2007-05-29
Hierarchy scores are calculated by S1 õ(Dn/Df). Reference scores are
calculated by
R*Rf.
[0043] The number of child elements processed can be controlled by parameter M
where M is the maximum number of children to include in a calculation.
[0044] The validity of this algorithm is determined by experimentation using
any full-
text search engine. Different search engines typically return different values
for T.
The parameters available for experimentation are: Df, Rf and M. Raising Df
increases relevance of child items. This relevance can be limited on the upper
end
by lowering M. Raising Rf increases the importance of references.
[0045] The subject ranking management system 10 can be efficiently implemented
with any full-text search engine by adding the subject document structure with
fields:
Field, id, name, and parentid, as described above. This allows the search
system
to find parent and child relationships using the parentid field, as described
above.
[0046] In one embodiment, the subject ranking management system 10 is used
with
the search engine 30 that implements its own taxonomy 40 using the index
corpus
50. In a different embodiment, the subject ranking management system 10 may be
incorporated with a content management system that indexes content of data
sources and has taxonomy management functionality. An example of such a
content management system is described in Canadian patent application No.
2,514,165 and United States patent application No. 11/494,974, the content of
which
is incorporated herewith by reference.
[0047] Figure 7 shows a subject ranking management system 300 in accordance
with another embodiment of the invention. In this embodiment, the subject
ranking
management system 300 has a taxonomy managing unit 300. The taxonomy
managing unit 310 indexes content, i.e., terms, in one or more metadata
sources
350, and generates a searchable content index 320 storing the indexed terms.
The
-12-
CA 02590517 2007-05-29
content index 320 includes the taxonomy 322 of the indexed terms. The taxonomy
managing unit 310 has a parent identification handier 312 that provides parent
information for each subject item in the taxonomy 322.
[0048] The subject ranking management system of the present invention may be
implemented by any hardware, software or a combination of hardware and
software
having the above described functions. The software code, instructions and/or
statements, either in its entirety or a part thereof, may be stored in a
computer
readable memory. Further, a computer data signal representing the software
code,
instructions and/or statements may be embedded in a carrier wave may be
transmitted via a communication network. Such a computer readable memory and a
computer data signal and/or its carrier are also within the scope of the
present
invention, as well as the hardware, software and the combination thereof.
[0049] While particular embodiments of the present invention have been shown
and
described, changes and modifications may be made to such embodiments without
departing from the scope of the invention. For example, the elements of the
subject
ranking management system are described separately, however, two or more
elements may be provided as a single element, or one or more elements may be
shared with other components in one or more computer systems.
-13-
