High performance XML storage retrieval system and method

• US 20060036631A1
• Filed: 08/10/2004
• Published: 02/16/2006
• Est. Priority Date: 08/10/2004
• Status: Active Grant

• Current Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Original Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Inventors: Cheslow, Robert D.
• Granted Patent: US 7,627,589 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/84 Mapping; Conversion
• CPC Class Codes: G06F 40/143 Markup, e.g. Standard Generalized Markup Language [SGML] or Document Type Definition [DTD]
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

A binary object XML repository for storage and retrieval of data in XML documents includes import manager capabilities for converting file formats to XML. Indexing capabilities encode XML document data in a binary data structure for storage within lexicon(s) in the form of tokens and token types, with a token including data elements corresponding to XML syntax. The lexicon(s) also assigns token identifier numbers, which sequence module(s) store in an original sequence. Postings module(s) map the token identifier numbers to the token identifier'"'"'s position in the original sequence.

Claims

1. A binary object XML repository for storage and retrieval of data in XML documents comprising:

at least one import manager module for converting at least one file format to XML;

at least one indexer module for encoding XML document data in a binary data structure;

at least one lexicon module for storing at least one token and at least one token type and assigning at least one token identifier number, wherein said token includes data elements corresponding to XML syntax;

at least one sequence module for storing said at least one token identifier number in an original sequence; and

at least one postings module for mapping said at least one token identifier number to said token identifier'"'"'s position in said original sequence.

2. The binary object XML repository according to claim 1, wherein encoding XML data in a binary data structure comprises streaming through said XML document and breaking data into pieces corresponding to XML syntax.

3. The binary object XML repository according to claim 2, wherein said at least one token type comprises at least one member selected from the group consisting of element, end tag, attribute name, attribute value, CDATA section start, CDATA section end, CDATA token, CDATA whitespace, comment, and XML declaration.

4. The binary object XML repository according to claim 1, wherein converting at least one file format to XML is performed by at least one filter, wherein said at least one filter comprises at least one shared dynamically linked library written to an API specification.

5. The binary object XML repository according to claim 1, wherein assigning said at least one token identifier number comprises assigning at least one unique integer value to said at least one token.

6. The binary object XML repository according to claim 1, further comprising:

at least one regenerator module for retrieving said at least one token for a specified scope in said sequence, wherein said specified scope includes an XML fragment defined by a start and an end tag; and

at least one XML grammar state machine module for using said token type information to compute the syntax for regenerating XML.

7. The binary object XML repository according to claim 6, wherein said at least one postings module inverts the information from a list of tokens in an XML data element to map at least one selected token to at least one XML data element in which it appears.

8. The binary object XML repository according to claim 1, wherein storing at least one token and at least one token type and assigning at least one token identifier number comprises:

reading a token from said XML document and assigning a token type, wherein one type is assigned for each token; and

storing said token as part of the token identifier.

9. The binary object XML repository according to claim 6, wherein using said token type information to compute the syntax for regenerating XML comprises:

reading the next token identifier from the token sequence;

retrieving the token and token type for a token identifier from the lexicon; and

inserting said token into the output stream with the markup syntax appropriate for type.

10. A method for storage and retrieval of information in a binary object XML repository having an import manager module, an indexer module, a lexicon module, a sequence module, and a postings module comprises:

importing an XML document;

encoding XML data in a binary data structure;

storing at least one token and at least one token type and assigning at least one token identifier number, wherein said at least one token includes data elements corresponding to XML syntax;

storing said at least one token identifier number in an original sequence; and

mapping said at least one token identifier number to said token identifier'"'"'s position in said original sequence.

11. The method for storage and retrieval of information in a binary object XML repository according to claim 10, wherein importing an XML document comprises converting at least one file format to XML.

12. The method for storage and retrieval of information in a binary object XML repository according to claim 10, wherein encoding XML data in a binary data structure comprises parsing the text markup of said XML document to identify at least one token and at least one token type.

13. The method for storage and retrieval of information in a binary object XML repository according to claim 10, wherein storing at least one token and at least one token type and assigning at least one token identifier number comprises:

reading a token from said XML document and assigning a token type, wherein one type is assigned for each token; and

storing said token as part of the token identifier.

14. The method for storage and retrieval of information in a binary object XML repository according to claim 13, wherein assigning said at least one token identifier number comprises assigning at least one unique integer value to said at least one token.

15. The method for storage and retrieval of information in a binary object XML repository according to claim 10, wherein said at least one token type comprises at least one member selected from the group consisting of element, end tag, attribute name, attribute value, CDATA section start, CDATA section end, CDATA token, CDATA whitespace, comment, and XML declaration.

16. The method for storage and retrieval of information in a binary object XML repository according to claim 11, wherein converting at least one file format to XML is performed by at least one filter, wherein said at least one filter comprises at least one shared dynamically linked library written to an API specification.

17. The method for storage and retrieval of information in a binary object XML repository according to claim 10, further comprising determining whether a complete XML document has been processed.

18. The method for storage and retrieval of information in a binary object XML repository according to claim 17, further comprising completing the document processing process when said complete XML document has been processed, comprising:

inverting data element and token identifier lists to create token identifier/data element postings; and

saving the data files.

19. The method for storage and retrieval of information in a binary object XML repository according to claim 17, further comprising continuing the document processing process when said complete XML document has not been processed, comprising:

determining if said token is included in the lexicon module;

retrieving said token identifier from said lexicon if said token is included in said lexicon, appending said token identifier to said token sequence, and storing said token identifier in the list for the current element; and

storing said token and said token type in the lexicon if said token is not included in said lexicon, assigning a unique token identifier to said token, appending said token identifier to the token sequence, and storing said token identifier in the list for the current data element.

20. The method for storage and retrieval of information in a binary object XML repository according to claim 10, further comprising:

initiating document regeneration for a specified scope, wherein said scope comprises an XML fragment defined by a start tag and an end tag; and

using said token type information to compute the syntax for regenerating XML.

21. The method for storage and retrieval of information in a binary object XML repository according to claim 20, wherein using said token type information to compute the syntax for regenerating XML comprises:

reading the next token identifier from the token sequence;

retrieving the token and token type for a token identifier from the lexicon; and

inserting said token into the output stream with the markup syntax appropriate for type.

22. The method for storage and retrieval of information in a binary object XML repository according to claim 20, further comprising inverting the information from a list of tokens in an XML data element to map at least one selected token to at least one XML data element in which it appears.

23. The method for storage and retrieval of information in a binary object XML repository according to claim 20, further comprising continuing regeneration processing if said end of scope has not been reached.

24. An article of manufacture comprising a computer usable medium having computer readable program code embodied in said medium which, when said program code is executed by said computer causes said computer to perform method steps for storage and retrieval of information in a binary object XML repository having an import manager module, an indexer module, a lexicon module, a sequence module, and a postings module comprises:

importing an XML document;

encoding XML data in a binary data structure;

storing at least one token and at least one token type and assigning at least one token identifier number, wherein said at least one token includes data elements corresponding to XML syntax;

storing said at least one token identifier number in an original sequence; and

mapping said at least one token identifier number to said token identifier'"'"'s position in said original sequence.