Method and apparatus for searching an index structure for TV-Anytime Forum metadata having location information for defining a multi-key

• US 7,444,357 B2
• Filed: 05/14/2004
• Issued: 10/28/2008
• Est. Priority Date: 07/23/2002
• Status: Expired due to Fees

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Shin, Hyoseop
• Primary Examiner(s): Mofiz; Apu
• Assistant Examiner(s): LU, CHARLES EDWARD
• Application Number:
  US10/845,211
• Publication Number:
  US 20040210571A1
• Time in Patent Office: 1,628 Days
• Field of Search: 707/102, 707/103.R, 707/100, 707/104.1
• US Class Current: 1/1
• CPC Class Codes: G06F 16/81 Indexing, e.g. XML tags; Data structures therefor; Storage structures
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing
• CPC Class Codes: Y10S 707/99948 Application of database or data structure, e.g. distributed, multimedia, or image

Abstract

An index structure of metadata provided for searching for information on contents and a method for providing indices of the metadata, and a method and an apparatus for searching for the metadata using the index structure of the metadata are provided, in which the index structure of the metadata includes values of multi-keys and identification information of the metadata corresponding to the values of the multi-keys, wherein the multi-keys are structured by a combination of predetermined fields of the metadata.

Claims

1. A method of searching for metadata divided into fragments and stored in a computer-readable storage medium, using an index having a key index list section having a list of multi-keys and location information for defining the multi-keys, a key index section, and a sub-key index section, the method comprising:

searching for and locating a multi-key in the index, wherein the multi-key meets search conditions of a combination of fields of the metadata; and

extracting a fragment of the metadata from the computer-readable storage medium by using the located multi-key, wherein the multi-key is a plurality of keys used simultaneously to locate and extract the fragment of metadata;

wherein with respect to comparison of values of a multi-key in size, the multi-key comprises fields (k1, k2, k3. . . kn) of the metadata which are prioritized (k1>

k2>

k3>

. . . Kn), and the combined fields are compared in sequence, starting from a first field having a highest order of priority, wherein the values are compared on an arithmetic basis where the values of the multi-key are alphabetical,

wherein for two multi-key values, (a1, a2, . . . , an) and (b1, b2. . . , bn);

(a1, a2, . . . , an) is larger than (b1, b2, . . . , bn) if and only if there exists an integer i (0<

i<

n−

1) such that for every j (0<

i<

n−

1), aj=bj and ai<

bi;

(a1, a2, . . . , an) is smaller than (b1, b2, . . . , bn) if and only if there exists an integer i (0<

i<

n−

1) such that for every j (0<

i<

n−

1), aj=bj and ai <

bi; and

(a1, a2, . . . , an) is equal to (b1, 2, . . . , bn) if and only if for every i (0<

i<

n−

1), ai=bi.

2. The method as claimed in claim 1, wherein the searching for the multi-key comprises:

determining location information corresponding to the combination of fields of the metadata; and

searching for the multi-key corresponding to the determined location information corresponding to the combination of fields of the metadata.

3. The method as claimed in claim 1, wherein the searching of the multi-key comprises searching for a value of the multi-key meeting the search conditions.

4. The method as claimed in claim 3, wherein:

the searching of the value comprises searching for the value among values of the multi-key from the index, and

the extracting of the fragment comprises extracting the fragment of the metadata using identification information of the fragment corresponding to the value of the multi-key.

5. The method as claimed in claim 4, wherein in response to a plurality of values of the multi-key meeting the search conditions, the extracting of the fragment comprises extracting ones of the fragments of the metadata corresponding to the values of the multi-key meeting the search conditions.

6. The method as claimed in claim 4, wherein the searching of the value comprises:

searching for a representative key value meeting the search conditions, among representative key values of the index corresponding to ranges of values of the multi-key; and

searching for the value among a range of values corresponding to the representative key value.

9. A computer-readable medium comprising computer-executable instructions for performing the operations recited in claim 1.

7. A method of searching for metadata divided into fragments and stored in a computer-readable storage medium, using an index having a key index list section having a list of multi-keys and location information for defining the multi-keys, a key index section, and a sub-key index section, the method comprising:

searching for and locating a value of a multi-key in the index, wherein the key meets search conditions for a combination of fields of the metadata; and

extracting a fragment of the metadata from the computer-readable storage medium corresponding to the located multi-key value, wherein the multi-key is a plurality of keys used simultaneously to locate and extract the fragment of metadata;

wherein with respect to comparison of values of a multi-key in size, the multi-key comprises fields (k1, k2, k3, . . . kn) of the metadata which are prioritized (k1<

k2<

k3<

. . . Kn), and the combined fields are compared in sequence, starting from a first field having a highest order of priority, wherein the values are compared on an arithmetic basis where the values of the multi-key are alphabetical,

wherein for two multi-key values, (a1, a2, . . . , an) and (b1, b2, . . . , bn);

(a1, a2, . . . , an) is larger than (b1, b2, . . . , bn) if and only if there exists an integer i (0<

i<

n−

1) such that for every j (0<

j<

n−

1), aj=bj and ai<

bi;

(a1, a2, . . . , an) is smaller than (b1, b2, . . . , bn) if and only if there exists an integer i (0<

i<

n−

1) such that for every j (0<

j<

n−

1), aj=bj and ai<

bi; and

(a1, a2, . . . , an) is equal to (b1, b2, . . . , bn) if and only if for every i (0<

i<

n−

1), ai=bi.

8. The method as claimed in claim 7, wherein in response to a plurality of values of the multi-key meeting the search conditions, the extracting of the fragment comprises extracting ones of the fragments of the metadata corresponding to the values of the multi-key meeting the search conditions.

10. A computer-readable medium comprising computer-executable instructions for performing the operations recited in claim 7.

11. An apparatus for searching for metadata divided into fragments, using an index having a key index list section having a list of multi-keys and location information defining the multi-keys, a key index section, and a sub-key index section, the apparatus comprising:

a central processing unit (CPU);

an input unit receiving search conditions; and

a control unit using the CPU to search the index of the metadata for a multi-key corresponding to the search conditions of a combination of fields of the metadata, and extracting a fragment of the metadata using the searched multi-key, wherein the multi-key is a plurality of keys used simultaneously to locate and extract the fragment of metadata;

wherein with respect to comparison of values of a multi-key in size, the multi-key comprises fields (k1, k2, k3. . . kn) of the metadata which are prioritized (k1<

k2<

k3<

. . . Kn), and the combined fields are compared in sequence, starting from a first field having a highest order of priority, wherein the values are compared on an arithmetic basis where the values of the multi-key are alphabetical,

wherein for two multi-key values, (a1, a2, . . . , an) and (b1, b2, . . . , bn);

(a1, a2, . . . , an) is larger than (b1, b2, . . . , bn) if and only if there exists an integer i (0<

i<

n−

1) such that for every j (0<

j<

n−

1), aj=bj and ai<

bi;

(a1, a2, . . . , an) is smaller than (b1, b2, . . . bn) if and only if there exists an integer i (0<

i<

n−

1) such that for every j (0<

j<

n−

1), aj=bj and ai<

bi; and

(a1, a2, . . . , an) is equal to (b1, b2, . . . , bn) if and only if for every i (0<

i<

n−

1), ai=bi.

12. The apparatus as claimed in claim 11, wherein the control unit searches for a value of the multi-key meeting the search conditions among values of the multi-key from the index, and extracts the fragment using identification information of the fragment corresponding to the value of the multi-key.

13. The apparatus as claimed in claim 12, wherein in response to a plurality of values of the multi-key meeting the search conditions, the control unit extracts ones of the fragments of the metadata corresponding to the values of the multi-key meeting the search conditions.

14. The apparatus as claimed in claim 12, wherein the control unit searches for a representative value meeting the search conditions, among representative values of the index corresponding to ranges of values of the multi-key, and searches for the value among a range of values corresponding to the representative key value.

15. The apparatus as claimed in claim 11, wherein the location information is expressed in XPath.

16. The apparatus as claimed in claim 11, wherein at least a part of the location information is expressed as a predetermined code.

17. The apparatus as claimed in claim 11, wherein the metadata is metadata as defined in the TVA Forum.

18. An apparatus for searching for metadata divided into fragments, using an index having a key index list section having a list of multi-keys and location information defining the multi-keys, a key index section, and a sub-key index section, the apparatus comprising:

a central processing unit (CPU);

an input unit receiving search conditions; and

a control unit using the CPU to search the index of the metadata for a value of a multi-key corresponding to the search conditions of a combination of fields of the metadata, and extracting a fragment of the metadata using the searched value, wherein the multi-key is a plurality of keys used simultaneously to locate and extract the fragment of metadata;

wherein with respect to comparison of values of a multi-key in size, the multi-key comprises fields (k1, k2, k3. . . kn) of the metadata which are prioritized (k1<

k2<

k3<

, . . . Kn), and the combined fields are compared in sequence, starting from a first field having a highest order of priority, wherein the values are compared on an arithmetic basis where the values of the multi-key are alphabetical,

wherein for two multi-key values, (a1, a2, . . . , an) and (b1, b2, . . . , bn);

(a1, a2, . . . , an) is larger than (b1, b2, . . . , bn) if and only if there exists an integer i (0<

i<

n−

1) such that for every j (0<

j<

n−

1), aj=bj and ai<

bi;

(a1, a2, . . . , an) is smaller than (b1, b2, . . . , bn) if and only if there exists an integer i (0<

i<

n−

1) such that for every j (0<

j<

n−

1), aj=bj and ai<

bi; and

(a1, a2, . . . , an) is equal to (b1, b2, . . . , bn) if and only if for every i (0<

i<

n−

1), ai=bi.

19. The apparatus as claimed in claim 18, wherein the control unit searches for the value of the multi-key meeting the search conditions among values of the multi-key from the index, and extracts the fragment using identification information of the fragment corresponding to the value of the multi-key.

20. The apparatus as claimed in claim 19, wherein the control unit searches for a representative value meeting the search conditions, among representative values of the index corresponding to ranges of values of the multi-key, and searches for the value among a range of values corresponding to the representative key.

21. The apparatus as claimed in claim 18, wherein in response to a plurality of values of the multi-key meeting the search conditions, the control unit extracts ones of the fragments of the metadata corresponding to the values of the multi-key meeting the search conditions.

22. The apparatus as claimed in claim 18, wherein at least a part of the location information is expressed as a predetermined code.

23. The apparatus as claimed in claim 18, flirt her comprising:

a receiving unit receiving the metadata and the index of the metadata;

a storage unit storing therein the metadata and the index of the metadata; and

an output unit outputting the search result by the control unit.

24. An apparatus for searching for metadata divided into fragments, using an index having a key index list section having a list of multi-keys and location information defining the multi-keys, a key index section, and a sub-key index section, the apparatus comprising:

a central processing unit (CPU);

an input unit receiving search conditions of at least two keys of the metadata; and

a control unit using the CPU to select from a list comprising a plurality of combinations of location information of a fragment and location information defining at least two keys within the fragment, a combination corresponding to the search conditions, wherein the multi-key is a plurality of keys used simultaneously to locate and extract the fragment of metadata;

wherein with respect to comparison of values of a multi-key in size, the multi-key comprises fields (k1, k2, k3. . . kn) of the metadata which are prioritized (k1<

k2<

k3<

, . . . Kn), and the combined fields are compared in sequence, starting from a first field having a highest order of priority, wherein the values are compared on an arithmetic basis where the values of the multi-key are alphabetical,

wherein for two multi-key values, (a1, a2, . . . , an) and (b1, b2, . . . , bn);

(a1, a2, . . . , an) is larger than (b1, b2, . . . , bn) if and only if there exists an integer i (0<

i<

n−

1) such that for every j (0<

j<

n−

1), aj=bj and ai<

bi;

(a1, a2, . . . , an) is smaller than (b1, b2, . . . , bn) if and only if there exists an integer i (0<

i<

n−

1) such that for every j (0<

j<

n−

1), aj=bj and ai<

bi; and

(a1, a2, . . . , an) is equal to (b1, b2, . . . , bn) if and only if for every i (0<

i<

n−

1), ai=bi.

25. The apparatus as claimed in claim 24, wherein the control unit further extracts one or more fragments of the metadata corresponding to identification information on the metadata identified by the selected combination.

26. The apparatus as claimed in claim 24, wherein one of the location information on the fragment and the location information defining the at least two keys is expressed as a predetermined code.