Encoding semi-structured data for efficient search and browsing

• US 8,489,597 B2
• Filed: 09/01/2004
• Issued: 07/16/2013
• Est. Priority Date: 02/26/2001
• Status: Active Grant

• Current Assignee: DB Software, Inc.
• Original Assignee: Ori Software Development Ltd
• Inventors: Shadmon, Moshe, Sample, Neal, Cooper, Brian, Franklin, Michael J.
• Primary Examiner(s): Jami, Hares
• Application Number:
  US10/931,035
• Publication Number:
  US 20050033733A1
• Time in Patent Office: 3,240 Days
• Field of Search: 707/101, 707/736, 707/741, 707/742, 707/743, 707/999.3
• US Class Current: 707/736
• CPC Class Codes: G06F 16/81 Indexing, e.g. XML tags; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/835 Query processing
• CPC Class Codes: Y10S 707/955 Object-oriented
• CPC Class Codes: Y10S 707/956 Hierarchical
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

A method for encoding XML tree data that includes the step of encoding the semi-structured data into strings of arbitrary length in a way that maintains non-structural and structural information about the XML data, and enables indexing the encoded XML data in a way that facilitates efficient search and browsing.

Claims

1. A method for encoding semi-structured data, the method implemented by at least one processor and comprising:

a. providing a semi-structured data input, the semi-structured data input being a Markup Language (ML) data or representation thereof; and

b. obtaining an encoded semi-structured data by selectively encoding at least part of the semi-structured data into strings of arbitrary length, the strings of arbitrary length each maintaining both structural information of the semi-structured data and non-structural information, and the so encoded semi-structured data operates as keys to be indexed by an index for efficient access, said index is based on a trie,

wherein the structural information represents at least relations or order between data items provided as input, and

wherein encoding at least part of the semi-structured data includes replacing at least one of the structural information and the non-structural information with a token, the token being associated with the at least one of the structural information and the non-structural information.

2. The method for encoding semi-structured data of claim 1 wherein the strings of arbitrary length maintain Markup Language (ML) paths.

3. The method for encoding semi-structured data of claim 1 wherein said structural information being the markup and relationships between data items, the relationships between data items consisting of parent-child or sibling relationship of said ML data.

4. The method for encoding semi-structured data of claim 1 wherein the strings of arbitrary length maintain Markup Language (ML) paths, said encoding of each of said strings of arbitrary length includes:

(i) converting the structural information of the semi-structured data into a corresponding structural character string, the corresponding structural character string maintains the Markup Language (ML) paths in the semi-structured data input; and

(ii) appending the non-structural data to the structural character string.

5. A method for encoding semi-structured data, the method implemented by at least one processor and comprising:

a. providing a semi-structured data input, the semi-structured data input being a Markup Language (ML) data or representation thereof;

b. obtaining an encoded semi-structured data by selectively encoding at least part of the semi-structured data into strings of arbitrary length, said strings of arbitrary length each maintaining both non-structural information and structural information of the semi-structured data, the encoding including at least associating the structural information with a compressed representation of the structural information; and

c. in response to a query for information of interest, retrieving the information of interest using the strings of arbitrary length,

wherein the structural information represents at least relations or order between data items provided as input, and

wherein encoding at least part of the semi-structured data includes replacing at least one of the structural information and the non-structural information with a token, the token being associated with the at least one of the structural, information and the non-structural information.

6. The method for encoding semi-structured data of claim 5 wherein the strings of arbitrary length maintain Markup Language (ML) paths.

7. The method for encoding semi-structured data of claim 5 wherein said structural information being the markup and relationships between data items, the relationships between data items consisting of parent-child or sibling relationship of said ML data.

8. The method for encoding semi-structured data of claim 5 wherein the strings of arbitrary length maintain Markup Language (ML) paths, said encoding of each of said strings of arbitrary length includes:

(i) converting the structural information of the semi-structured data into a corresponding structural character string, the corresponding structural character string maintains the Markup Language (ML) paths in the semi-structured data input; and

(ii) appending the non-structural data to the structural character string.

9. A method for encoding semi-structured data, the method implemented by at least one processor and comprising:

a. providing a semi-structured data input, the semi-structured data input being a Markup Language (ML) data or representation thereof;

b. obtaining an encoded semi-structured data by selectively encoding at least part of the semi-structured data into keys that each maintain both non-structural information and structural information of the semi-structured data;

c. creating a single index over the keys; and

d. in response to a query for information of interest, the query includes both structural components and non-structural components;

retrieving the information of interest using the index, the retrieval process does not use join operations,

wherein the structural information represents at least relations or order between data items provided as input, and

wherein encoding at least part of the semi-structured data includes replacing at least one of the structural information and the non-structural information with a token, the token being associated with the at least one of the structural information and the non-structural information.

10. The method of claim 9 wherein the index is a layered index.

11. The method of claim 9 wherein the index is a designated index.

12. The method of claim 9 wherein the index is based on a trie.

13. The method of claim 10 wherein the index is a designated index.

14. The method of claim 9 wherein the keys are strings of arbitrary length that maintain non-structural and structural information associated with the semi-structured data.

15. The method of claim 14 wherein the index is a layered index.

16. The method of claim 14 wherein the index is a designated index.

17. The method of claim 14 wherein the index is based on a trie.

18. The method of claim 15 wherein the index is a designated index.

19. The method for encoding semi-structured data of claim 9 wherein the strings of arbitrary length maintain Markup Language (ML) paths.

20. The method for encoding semi-structured data of claim 9 wherein said structural information being the markup and relationships between data items, the relationships between data items consisting of parent-child or sibling relationship of said ML data.

21. The method for encoding semi-structured data of claim 9 wherein the strings of arbitrary length maintain Markup Language (ML) paths, said encoding of each of said strings of arbitrary length includes:

(i) converting the structural information of the semi-structured data into a corresponding structural character string, the corresponding structural character string maintains the Markup Language (ML) paths in the semi-structured data input; and

(ii) appending the non-structural data to the structural character string.