MECHANISM FOR EFFICIENTLY SEARCHING XML DOCUMENT COLLECTIONS

• US 20100228734A1
• Filed: 02/24/2009
• Published: 09/09/2010
• Est. Priority Date: 02/24/2009
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Murthy, Ravi
• Granted Patent: US 8,650,182 B2
• Time in Patent Office: Days
• US Class Current: 707/741
• CPC Class Codes: G06F 16/258 Data format conversion from or to a database
• CPC Class Codes: G06F 16/81 Indexing, e.g. XML tags; Data structures therefor; Storage structures

Abstract

The techniques presented herein are directed towards providing a user-directed keyword-based search on a large collection of XML documents, and displaying a summary of results to the user. Prior to receiving search requests from a user, an offline analysis of a large collection of XML documents is performed to construct an inverted index of keywords. For each keyword, the index stores a set of location indicators that identify all the instances of the keyword found in the collection of documents. A location indicator may comprise a document identifier, an indication of the position of the node in the hierarchy of nodes within the XML document containing the keyword, and an indication of the pathname of the node containing the keyword. Once the index is constructed, keyword searching can be done efficiently by a keyword lookup in the index. Various display strategies enable the user to see the specific portion of a large XML document containing the keyword and/or path frequency information allowing the user to easily refine the search to specific paths within the collection of documents.

Claims

1. A computer-implemented method:

storing an index, wherein the index contains index entries that index a collection of XML documents that contain words;

wherein each index entry of said index entries includes;

a particular word of said words; and

at least one location indicator, wherein a location indicator includes;

a document identifier that identifies an XML document in the collection of XML documents that contains the particular word; and

at least one of;

(a) an order key that specifies a hierarchical position of a node within the XML document that contains the particular word, or

(b) a path representation representing a path of a node within the XML document that contains the particular word.

2. The method of claim 1, wherein:

the index is stored as a balanced search tree;

the particular word is a key into the index; and

all location indicators included in an index entry are stored together as a single element in the balanced search tree.

3. The method of claim 1, wherein the location indicator:

includes both an order key and a path representation;

wherein the path representation represents a path of a particular node; and

the order key specifies the hierarchical position of the particular node within an XML document.

4. The method of claim 1, wherein a path representation comprises a numeric path identifier, wherein the numeric path identifier is a key into an index of path names.

5. The method of claim 1, wherein the index is stored using delta compression.

6. A computer-implemented method for generating a response to a search request comprising:

receiving a search request comprising one or more words;

for each word of the one or more words;

retrieving from an index, a set of location indicators stored in association with said each word;

wherein a location indicator of the set of location indicators includes;

a document identifier stored in association with a path representation, wherein the path representation is stored in association with an order key;

the document identifier identifying a particular XML document in a collection of XML documents containing said each word;

the path representation representing a path of a node within the XML document that contains said each word; and

the order key specifying the hierarchical position of the node within the XML document; and

displaying a representation of the set of location indicators.

7. The method of claim 6, wherein the displaying step further includes:

for each unique path representation found within the set of location indicators;

counting the number of occurrences of said each unique path representation within the set of location indicators; and

displaying (a) the path represented by said each unique path representation, and

(b) the number of occurrences of said each unique path representation.

8. The method of claim 7 wherein said each unique path representation and said number of occurrences is displayed;

and further comprising;

in response to displaying, receiving a subsequent request to refine the search request, wherein the subsequent request specifies a set of path representations; and

for each particular path representation in the set of path representations, finding a particular set of location indicators, wherein each location indicator in the particular set of location indicators includes said each particular path representation and an order key; and

displaying the order key.

9. The method of claim 8 wherein displaying further comprises displaying a portion of the XML document containing the node located at the hierarchical position specified by the order key.

10. The method of claim 7 wherein displaying:

(a) the path represented by said each unique path representation further comprises;

identifying a first prefix;

associating the first prefix with a set of path representations, wherein the set of path representations is a subset of all the unique path representations for the entire set of XML document and the each path representation in the set of path representations starts with the first prefix; and

displaying the first prefix; and

(b) the number of occurrences of said each unique path representation further comprises;

determining the sum of the number of occurrences for all of the path representations in the set of path representations; and

displaying said sum.

11. The method of claim 10, further comprising the steps of:

identifying a very popular path representation, wherein the very popular path representation starts with said first prefix;

not adding the very popular path to the set of path representations associated with the first prefix; and

displaying the very popular path and the number of occurrences for the very popular path separately from displaying the set of path representations.