Index structure of metadata, method for providing indices of metadata, and metadata searching method and apparatus using the indices of metadata

• US 20040139091A1
• Filed: 07/22/2003
• Published: 07/15/2004
• Est. Priority Date: 07/23/2002
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Shin, Hyoseop
• Granted Patent: US 7,343,381 B2
• Time in Patent Office: Days
• US Class Current: 707/100
• 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 value of the multi-key, wherein the multi-keys are structured by combination of predetermined fields of the metadata.

Claims

1. An index structure of metadata comprising:

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.

2. The index structure as claimed in claim 1, further comprising a list of the multi-keys.

3. The index structure as claimed in claim 2, further comprising a representative key value representing a first predetermined range of the values of the multi-keys.

4. The index structure as claimed in claim 3, wherein the representative key value comprises at least one of a maximum value, a minimum value or an intermediate value among the values within the first predetermined range.

5. The index structure as claimed in claim 3, wherein the metadata comprises fragments divided by a second predetermined range in a tree data structure, wherein a first field constituting a first multi-key corresponds to any one of the information constituting the fragments.

6. The index structure as claimed in claim 5, wherein the identification information of the metadata comprises identification information of the fragments.

7. The index structure as claimed in claim 5, wherein the list of the multi-keys includes location information of a first fragment to which the first field constituting the first multi-key belong, in the data structure, and location information of the first field in the first fragment.

8. The index structure as claimed in claim 7, wherein the location information is expressed in XPath.

9. The index structure as claimed in claim 1, wherein comparison of the values of the multi-keys in size serves to compare the size of the values of the multi-keys by the fields having a different size of value first appearing by assigning the order of priority (k1>

k2>

k3>

. . . kn) to a plurality of the combined fields constituting the multi-key (k1, k2, k3 . . . kn) and comparing the combined fields in sequence, starting from a first multi-key field having a highest order of priority, wherein

the values of two multi-keys are determined to be of the same size where there is no field having the different size of value, and

the size of the combined fields is determined through an arithmetic comparison where a value of a concerned field is numerical or through a lexicographical order where the value of the concerned field is alphabetical.

10. The index structure as claimed as in claim 1, wherein the metadata has a structure of metadata as defined in TVA.

11. A method of providing an index of metadata comprising:

structuring multi-keys by combining predetermined fields of the metadata;

wherein the index of the metadata comprises values of the multi-keys and identification information of the metadata corresponding to the values of the multi-keys.

12. The method as claimed in claim 11, wherein the index of the metadata comprises a list of the multi-keys.

13. The method as claimed in claim 12, wherein the index of the metadata further comprises a representative key value representing a first predetermined range of values of the multi-keys.

14. The method as claimed in claim 13, wherein the representative key value comprises at least one of a maximum value, a minimum value or an intermediate value among the values within the first predetermined range.

15. The method as claimed in claim 13, wherein the metadata comprises fragments divided by a second predetermined range in a tree data structure, wherein a first field constituting a first multi-key corresponds to any one of information constituting the fragments.

16. The method as claimed in claim 15, wherein the identification information of the metadata refers to identification information of the fragments.

17. The method as claimed in claim 15, wherein the list of the multi-keys includes location information of a first fragment to which the first field constituting the first multi-key belong, in the data structure, and location information of the first field in the first fragment.

18. The method as claimed in claim 17, wherein the location information is expressed in XPath.

19. The method as claimed in claim 11, wherein the values of the multi-keys are arranged in sequence on the basis of size according to a predetermined rule.

20. The method as claimed in claim 19, wherein comparison of the values of the multi-keys in size serves to compare the size of the value of the multi-keys by the fields having a different size of value first appearing by assigning the order of priority (k1>

k2>

k3>

. . . kn) to a plurality of the combined fields constituting the multi-key (k1, k2, k3 . . . kn) and comparing the combined fields in sequence, starting from a first combined field having a highest order of priority, wherein

the values of two multi-keys are determined to be of the same size where there is no field having the different size of value, and

the size of the combined fields is determined through an arithmetic comparison where a value of a concerned field is numerical or through a lexicographical order where the value of the concerned field is alphabetical.

21. The method as claimed in claim 11, wherein the metadata has a structure of metadata as defined in TVA.

22. A method of searching for metadata comprising the steps of:

(a) inputting search conditions;

(b) searching for a value of a multi-key corresponding to the input search conditions from a metadata index; and

(c) extracting a concerned metadata by use of the searched value of the multi-key.

23. The method as claimed in claim 22, wherein the multi-key is structured by a combination of predetermined fields of the metadata.

24. The method as claimed in claim 22, wherein the metadata index comprises values of the multi-key and identification information of the metadata corresponding to the values of the multi-key.

25. The method as claimed in claim 24, wherein the metadata index comprises a list of multi-keys.

26. The method as claimed in claim 25, wherein the metadata further comprises a representative key value representing a first predetermined range of the values of the multi-key.

27. The method as claimed in claim 26, wherein the representative key value comprises at least one of a maximum value, a minimum value or an intermediate value among the values within the first predetermined range.

28. The method as claimed in claim 26, wherein the metadata comprises fragments divided by a second predetermined range in a tree data structure, wherein a first field constituting the multi-key corresponds to any one of the information constituting the fragments.

29. The method as claimed in claim 28, wherein the identification information of the metadata refers to identification information of the fragments.

30. The method as claimed in claim 28, wherein the list of the multi-keys comprises location information of a first fragment to which the first field constituting the multi-key belong, in the data structure, and location information of the first field in the first fragment.

31. The method as claimed in claim 30, wherein the location information is expressed in XPath.

32. The method as claimed in claim 22, wherein the metadata has a structure of metadata as defined in TVA.

33. The method as claimed in claim 22, wherein in the step of searching for the value of the multi-key, the value of the multi-key having the same size in comparison to a value of the input search conditions is searched.

34. The method as claimed in claim 33, wherein comparison of the values of the multi-key in size serves to compare the size of the value of the multi-key by a field having a different size of value first appearing by assigning the order of priority (k1>

k2>

k3>

. . . kn) to a plurality of fields constituting the multi-key (k1, k2, k3 . . . kn) and comparing the fields in sequence, starting from a field having a highest order of priority, wherein

the values of two multi-keys are determined to be of the same size where there is no field having the different size of value, and

the size of the fields is determined through an arithmetic comparison where the value of a concerned field is numerical or through a lexicographical order where the value of the concerned field is alphabetical.

35. The method as claimed in claim 24, wherein the step (c) of extracting the concerned metadata comprises the steps of:

(c1) extracting the identification information of the metadata corresponding to the value of the searched multi-key in the metadata index; and

(c2) extracting the concerned metadata by use of the extracted identification information.

36. The method as claimed in claim 26, wherein the step (b) of searching for the value of the multi-key comprises the steps of:

(b1) searching for the representative key value meeting the input search conditions; and

(b2) searching for the value of the multi-key meeting the input search conditions among the values of the multi-key in the range representing the representative key value.

37. The method as claimed in claim 30, wherein the step (b) of searching for the value of the multi-key comprises the steps of:

(b3) searching for the multi-key meeting the search conditions in the multi-key list; and

(b4) searching for the multi-key meeting the search conditions as inputted among the values of the multi-key indexed by the searched multi-key.

38. The method as claimed in claim 37, wherein the step (b3) of searching for the multi-key comprises the steps of:

(b3-1) determining the location information of the first fragment to which the first field of the search conditions belong in the data structure, and location information of the first field in the first fragment; and

(b3-2) searching for the multi-key structured with the fields having the location information corresponding to the location information determined above, from the multi-key list.

39. The method as claimed in claim 37, wherein the step (b4) of searching for the multi-key meeting the search conditions as inputted among the values of the multi-key indexed by the searched multi-key comprises the steps of:

(b4-1) searching for the representative value meeting the input search conditions; and

(b4-2) searching for the value of the multi-key meeting the input search conditions among the values of the multi-key represented by the representative key.

40. An apparatus for searching for metadata, comprising:

an input unit allowing a user to input search conditions therewith; and

a control unit which searches for a value of a multi-key meeting the input search conditions in a metadata index, and extracts a concerned metadata by use of the searched value of the multi-key.

41. The apparatus as claimed in claim 40, wherein the multi-key is structured by a combination of predetermined fields of the metadata.

42. The apparatus as claimed in claim 40, wherein the metadata index comprises values of the multi-key and identification information of the metadata corresponding to the values of the multi-key.

43. The apparatus as claimed in claim 42, wherein the metadata index comprises a list of multi-keys.

44. The apparatus as claimed in claim 43, wherein the metadata further comprises a representative key value representing a first predetermined range of the values of the multi-key.

45. The apparatus as claimed in claim 44, the representative key value comprises at least one of a maximum value, a minimum value or an intermediate value among the values within the first predetermined range.

46. The apparatus as claimed in claim 44, wherein the metadata comprises fragments divided by a second predetermined range in a tree data structure, wherein a first field constituting the multi-key corresponds to any one of information constituting the fragments.

47. The apparatus as claimed in claim 46, wherein the identification information of the metadata refers to identification information of the fragments.

48. The apparatus as claimed in claim 46, wherein the list of the multi-keys comprises location information of a first fragment to which the first field constituting the multi-key belong, in the data structure, and location information of the first field in the first fragment.

49. The apparatus as claimed in claim 48, wherein the location information is expressed in XPath.

50. The apparatus as claimed in claim 40, wherein the metadata has a structure of metadata as defined in TVA.

51. The apparatus as claimed in claim 40, wherein the control unit searches, from the metadata index, for the value of the multi-key that is identical in size obtained by comparison of the value for the input search conditions and the value of the multi-key.

52. The apparatus as claimed in claim 51, wherein comparison of the values of the multi-key in size serves to compare the size of the value of the multi-key by a field having a different size of value first appearing by assigning the order of priority (k1>

k2>

k3>

. . . kn) to a plurality of fields constituting the multi-key (k1, k2, k3 . . . kn) and comparing the fields in sequence, starting from a first field having a highest order of priority, wherein

the values of two multi-keys are determined to be of the same size where there is no field having the different size of value, and

the size of the fields is determined through an arithmetic comparison where a value of a concerned field is numerical or through a lexicographical order where the value of the concerned field is alphabetical.

53. The apparatus as claimed in claim 42, wherein the controller extracts identification information of the metadata corresponding to the searched value of the multi-key in the metadata index, and extracts the concerned metadata by use of the extracted identification information.

54. The apparatus as claimed in claim 44, wherein the controller searches for the representative key value meeting the input search conditions, and searches for the value of the multi-key meeting the input search conditions among the values of the multi-key in the first predetermined range represented by the representative key value.

55. The apparatus as claimed in claim 48, wherein the controller searches for the multi-key meeting the search conditions from the multi-key list, and searches for the value of the multi-key meeting the input search conditions among the values of the multi-key indexed by the searched multi-key.

56. The apparatus as claimed in claim 55, wherein the controller determines location information within the data structure of the fragment to which the fields of the search conditions belong, and location information of the fields within the fragment, and searches for the multi-key structured with fields having the location information corresponding to the determined location information, from the multi-key list.

57. The apparatus as claimed in claim 55, wherein the controller searches for the representative key value meeting the input search conditions, and searches for the values of the multi-key meeting the input search conditions among the values of the multi-key in the range of being represented by the representative key value.

58. The apparatus as claimed in claim 40, further comprising:

a receiving unit receiving the metadata and the metadata index;

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

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