Methods of encoding and combining integer lists in a computer system, and computer software product for implementing such methods

• US 7,246,124 B2
• Filed: 12/13/2000
• Issued: 07/17/2007
• Est. Priority Date: 11/29/2000
• Status: Expired due to Fees

• Current Assignee: Virtual Key Graph
• Original Assignee: Virtual Key Graph
• Inventors: Koskas, Elie Ouzi
• Primary Examiner(s): LEROUX, ETIENNE PIERRE
• Application Number:
  US09/736,683
• Publication Number:
  US 20020093522A1
• Time in Patent Office: 2,407 Days
• Field of Search: 707/1, 707/2, 707/3, 707/4, 707/100, 707/101, 707/102, 707/205, 707/10, 707/200, 711/103, 715/533, 341/50, 341/63, 341/95, 341/67, 345/752, 345/700
• US Class Current: 707/737
• CPC Class Codes: G06F 16/284 Relational databases

Abstract

A range covering integers of an input list is divided into subsets according to a predetermined pattern. The encoding produces coding data including, for each subset containing at least one integer of the input list, data representing the position of this subset in the pattern, and data representing the position of each integer of the input list within this subset. This encoding process may be iterated in several coding layers. It supports very efficient methods for combining the coded integer lists.

Claims

1. A method of encoding integer lists in a computer system, wherein a range covering integers of an input list is divided into subsets according to a predetermined pattern, the position of each subset in the pattern being represented by an integer rank, the method comprising:

for each input list of a plurality of integer lists, executing a routine on a processor of the computer astern for producing an output comprising coding data, the coding data including, for each subset containing at least one integer of the input list, the rank of said subset in the pattern and a bitmap segment in which each bit is associated with a respective integer of the subset to indicate whether said integer belongs to the input list,

and storing the coding data in a computer memory coupled to a processor, the coding data stored in a coding data container comprising records stored in a computer readable medium and having respective addresses, each record of the coding data container having a first field for storing an integer rank related to the pattern, a second field for storing an address value for another record of the data container and a third field for storing a bitmap segment.

2. A method according to claim 1 wherein the encoding of a non-empty input list comprises the steps of:

a/ selecting an available record of the coding data container;

b/ selecting a subset containing at least one integer of the input list to which no record has been allocated;

c/ allocating the selected record to the selected subset;

d/ storing the rank and the bitmap segment of the coding data produced for the selected subset in the first and third fields of the selected record, respectively;

e/ if every subset containing at least one integer of the input list has a record allocated thereto, storing an end value in the second field of the selected record; and

f/ if at least one subset containing at least one integer of the input list has no record allocated thereto, storing the address of an available record of the coding data container in the second field of the selected record, selecting said available record and repeating from step b/.

3. A method according to claim 2, wherein the coding data container has a first file comprising the first and second fields of the records and a second file comprising the third fields of the records, the first and second files being accessible separately.

4. A method according to claim 2, further comprising the step of grouping the records stored in the data container, so that the records allocated to the subsets for any encoded integer list have contiguous addresses.

5. A method according to claim 1, wherein the subsets are consecutive intervals consisting of the same number of integers.

6. A method according to claim 5, wherein said number of integers is a whole power of 2.

7. A method of encoding integer lists in a computer system, comprising n successive coding layers, n being a number at least equal to two,

wherein for each coding layer, a respective integer range is divided into subsets according to a predetermined pattern, wherein, in the pattern of each layer, the subsets are consecutive intervals consisting of the same number of integers, said number of integers being a whole power of 2 for each layer, wherein for each coding layer, a respective integer range is divided into subsets according to a predetermined pattern, wherein, in the pattern of each coding layer, the subsets are consecutive intervals consisting of the same number of integers, said number of integers being a whole power of 2 for each Layer,

and wherein each coding layer comprises the following steps executed as at least one routine on a processor of the computer system for processing an input list of integers within the respective integer range:

producing coding data including, for each subset containing at least one integer of the input list, data representing the position of each integer of the input list within said subset and, at least if said layer is the last coding layer, data representing the position of said subset in the pattern;

storing the coding data in a computer readable medium operatively coupled to a processor of the computer system; and

if said layer is not the last coding layer, forming a further integer list representing the position, in the pattern of said layer, of each subset containing at least one integer of the input list, and providing said further integer list as an input list of the next layer.

8. A method according to claim 7, wherein the coding data produced for each layer are stored in first and second files having a common addressing mechanism, whereby for each subset containing at least one integer of the input list of said layer, the data representing the position of said subset in the pattern are stored in the first file at a first address and the data representing the position of each integer of the input list within said subset are stored in the second file at a second address corresponding to said first address according to the common addressing mechanism.

9. A method according to claim 7, wherein the coding data produced from one integer list input in the first layer are stored in at least one file allocated to said one integer list.

10. A method according to claim 7, wherein the coding data produced from one integer list input in the first layer are stored in the computer readable medium as at least one record chain in a coding data container defined as a portion of a computer memory unit allocated to a plurality of integer lists.

11. A method according to claim 10, further comprising the step of grouping the records of the data containing that the records of each chain have contiguous addresses.

12. A method according to claim 7, wherein n≧

2, wherein for each integer k such that 1≦

k≦

n, at least one layer k data container having a plurality of records is provided as a portion of a storage unit in a computer memory, each record of a layer k data container being associated with a layer k integer rank representing the position of a subset in the layer k pattern, and wherein each record of a layer k data container associated with a layer k rank representing the position of a subset in the layer k pattern has a first field for containing data designating the position within said subset of any integer of a layer k input list relating to a layer 1 input list, whereby a combination of said layer k rank with any position designated by the data contained in said first field determines a layer k−

1 rank with which a respective record of the layer k−

1 data container is associated if k>

1, and an integer of said layer 1 input list if k=1.

13. A method according to claim 12, wherein each record of the layer n data container associated with a layer n rank further has a second field for containing said layer n rank.

14. A method according to claim 12, wherein, for 1≦

k≦

n, said data contained in the first field of a record of the layer k data container and designating the position of any integer of a layer k input list within a subset comprise a bitmap segment in which each bit is associated with a respective integer of said subset to indicate whether said integer belongs to said layer k input list.

15. A method according to claim 14, wherein, for 1≦

k≦

n, each record of the layer k data container associated with a layer k rank further has a second field for containing said layer k rank.

16. A method according to claim 15, wherein each data container comprising at least two files where the first and second fields of the records of said data container are respectively stored, said files being accessible separately.

17. A method according to claim 12, wherein. 1≦

k≦

n, each record of the layer k data container further has a second field for containing a number representing the position of an integer of a layer k+1 input list within a subset of the layer k+1 pattern,

and wherein, for 1≦

k≦

n, said data contained in the first field of a record of the layer k data container associated with a layer k rank and designating the position of any integer of a layer k input list within a subset of the layer k pattern comprise a pointer to at least one record of the layer k−

1 data container in which the second field contains a number representing the position of an integer of said layer k input list within said subset of the layer k pattern, whereby said record of the layer k−

1 data container is associated with the layer k−

1 rank determined by the combination of said layer k rank wit the position represented by said number.

18. A method according to claim 17, wherein said data contained in the first field of a record of the layer 1 data container and designating the position of any integer of a layer 1 input list within a subset comprise a bitmap segment in which each bit is associated with a respective integer of said subset to indicate whether said integer belongs to said layer 1 input list.

19. A method according to claim 17, wherein each layer k data container for 1≦

k≦

n comprises at least two files where the first and second fields of the records of said data container are respectively stored, said files being accessible separately.

20. A method according to claim 12, wherein, for 1≦

k≦

n, each record of the layer k data container further has a next address field, whereby record chains are defined in the layer k data container by means of the next address fields, and wherein at least some of the layer 1 input lists are respectively associated with record chains in the layer n data container whereby the coding data for layer n relating to one of said laser 1 input lists are stored in or retrievable from the record chain associated therewith in the layer n data container.

21. A method according to claim 20, wherein, for 1≦

k≦

n, said layer 1 input lists are respectively associated with record chains in the layer k data container, whereby the coding data relating to one of said layer 1 input lists for layer k are stored in or retrievable from the record chain associated therewith in the layer k data container.

22. A method according to claim 20, wherein, for 1<

k≦

n, each record of the layer k data container further has a head address field for pointing to an address of a first record of a respective chain in the layer k≦

1 data container.

23. A method according to claim 20, wherein each layer k data container for 1≦

k≦

n comprises at least two files where the first fields and the next address fields of the records of said data container are respectively stored, said files being accessible separately.

24. A method according to claim 20, further comprising the step of grouping the records of the data container for each coding layer, so that the records of each chain have contiguous addresses.

25. A method of encoding integer lists in a computer system, comprising n successive coding layers, n being a number at least equal to 1,

wherein for each coding layer, a respective integer range is divided into subsets according to a respective predetermined pattern,

and wherein each coding layer comprises the following steps for processing an input list of integers within the respective integer range:

producing coding data including, for each subset containing at least one integer of the input list, data representing the position of each integer of the input list within said subset and, at least if said layer is the last coding layer, data representing the position of said subset in the pattern;

if said layer is not the last coding layer, forming a further integer list representing the position, in the pattern of said layer, of each subset containing at least one integer of the input list, and providing said further integer list as an input list of the next layer; and

storing the coding data produced for said layer in a computer readable medium operatively coupled to a processor of the computer system the computer readable medium comprising first and second files having a common addressing mechanism, whereby for each subset containing at least one integer of the input list of said layer, the data representing the position of said subset in the pattern are stored in the first file at a first address and the data representing the position of each integer of the input list within said subset are stored in the second file at a second address corresponding to said first address according to the common addressing mechanism.

26. A method according to claim 25, wherein the coding data produced from one integer list input in the first layer are stored as at least one record chain and wherein the computer system comprises a coding data container for storing the coding data, the coding data container defined as a portion of a storage unit allocated to a plurality of integer lists.

27. A method according to claim 26, further comprising the step of grouping the records of the data container so that the records of each chain have contiguous addresses.

28. A method of encoding integer lists in a computer system, comprising n successive coding layers, n being a number at least equal to 2,

wherein for each coding layer, a respective integer range is divided into subsets according to a respective predetermined pattern,

wherein each coding layer comprises the following steps for processing an input list of integers within the respective integer range:

producing coding data including, for each subset containing at least one integer of the input list, data representing the position of each integer of the input list within said subset and, at least if said layer is the last coding layer, data representing the position of said subset in the pattern;

storing the coding data in a computer readable medium operatively coupled to a processor of the computer system; and

if said layer is not the last coding layer, executing a routine on the processor of the computer system for forming a further integer list representing the position, in the pattern of said layer, of each subset containing at least one integer of the input list, and providing said further integer list as an input list of the next layer,

wherein for each integer k such that 1≦

k≦

n, at least one layer k data container having a plurality of records is provided as a portion of a storage unit in a computer memory, each record of a layer k data container being associated with a layer k integer rank representing the position of a subset in the layer k pattern, and wherein each record of a layer k data container associated with a layer k rank representing the position of a subset in the layer k pattern has a first field for containing data designating the position within said subset of any integer of a layer k input list relating to a layer 1 input list, whereby a combination of said layer k rank with any position designated by the data contained in said first field determines a layer k−

1 rank with which a respective record of the layer k−

1 data container is associated if k>

1, and an integer of said layer 1 input list if k=1.

29. A method according to claim 28, wherein each record of the layer n data container associated with a layer n rank further has a second field for containing said layer n rank.

30. A method according to claim 28, wherein, for 1≦

k≦

n, said data contained in the first field of a record of the layer k data container and designating the position of any integer of a layer k input list within a subset comprise a bitmap segment in which each bit is associated with a respective integer of said subset to indicate whether said integer belongs to said layer k input list.

31. A method according to claim 30, wherein, for 1≦

k≦

n, each record of the layer k data container associated with a layer k rank further has a second field for containing said layer k rank.

32. A method according to claim 31, wherein each data container comprises at least two files where the first and second fields of the records of said data container are respectively stored, said files being accessible separately.

33. A method according to claim 28, wherein, for 1≦

k>

n, each record of the layer k data container further has a second field for containing a number representing the position of an integer of a layer k+1 input list within a subset of the layer k+1 pattern,

and wherein, for 1>

k≦

n, said data contained in the first field of a record of the layer k data container associated with a layer k rank and designating the position of any integer of a layer k input list within a subset of the layer k pattern comprise a pointer to at least one record of the layer k−

1 data container in which the second field contains a number representing the position of an integer of said layer k input list within said subset of the layer k pattern, whereby said record of the layer k−

1 data container is associated with the layer k−

1 rank determined by the combination of said layer k rank with the position represented by said number.

34. A method according to claim 33, wherein said data contained in the first field of a record of the layer 1 data container and designating the position of any integer of a layer 1 input list within a subset comprise a bitmap segment in which each bit is associated with a respective integer of said subset to indicate whether said integer belongs to said layer 1 input list.

35. A method according to claim 33, wherein each layer k data container for 1≦

k≦

n comprises at least two files where the first and second fields of file records of said data container are respectively stored, said files being accessible separately.

36. A method according to claim 28, wherein, for 1≦

k≦

n, each record of the layer k data container further has a next address field, whereby record chains are defined in the layer k data container by means of the next address fields, and wherein at least some of the layer 1 input lists are respectively associated with record chains in the layer n data container, whereby the coding data for layer n relating to one of said layer 1 input lists are stored in or retrievable from the record chain associated therewith in the layer n data container.

37. A method according to claim 36, wherein, for 1≦

k≦

n, said layer 1 input lists are respectively associated with record chains in the layer k data container, whereby the coding data relating to one of said layer 1 input lists for layer k are stored in or retrievable from the record chain associated therewith in the layer k data container.

38. A method according to claim 36, wherein, for 1≦

k≦

n, each record of the layer k data container further has a head address field for pointing to an address of a first record of a respective chain in the layer k−

1 data container.

39. A method according to claim 36, wherein each layer k data container for 1≦

k≦

n comprises at least two files where the first fields and the next address fields of the records of said data container are respectively stored, said files being accessible separately.

40. A method according to claim 36, further comprising the step of grouping the records of the data container for each coding layer, so that the records of each chain have contiguous addresses.

41. A computer program product for encoding integer lists in a computer system, comprising instructions for encoding the integer lists in accordance with n successive coding layers, n being a number at least equal to two,

wherein for each coding layer, a respective integer range is divided into subsets according to a predetermined pattern, wherein, in the pattern of each layer, the subsets are consecutive intervals consisting of the same number of integers, said number of integers being a whole power of 2 for each layer,

and wherein, for each coding layer in which an input list of integers within the respective integer range to be processed, the computer program product comprises:

instructions for producing coding data including, for each subset containing at at least one integer of said input list, data representing the position of each integer of the input list within said subset and, at least if said layer is the last coding layer, data representing the position of said subset in the pattern;

instructions for storing the coding data in a computer readable medium operatively couplable to a processor of a computer system; and

if said layer is not the last coding layer, instructions for forming a further integer list representing the position, in the pattern of said layer, of each subset containing at least one integer of the input list, and for providing said further integer list as an input list of the next layer.

42. A computer program product according to claim 41, further comprising instructions for storing the coding data produced for each layer in first and second files having a common addressing mechanism, whereby for each subset containing at least one integer of the input list of said layer, the data representing the position of said subset in the pattern are stored in the first file at a first address and the data representing the position of each integer of the input list within said subset are stored in the second file at a second address corresponding to said first address according to the common addressing mechanism.

43. A computer program product according to claim 41, further comprising instructions for storing the coding data produced from one integer list input in the first layer in at least one file allocated to said one integer list.

44. A computer program product according to claim 41, further comprising instructions for storing the coding data produced from one integer list input in the first layer as at least one record chain in a data container defined as a portion of a storage unit allocated to a plurality of integer lists.

45. A computer program product according to claim 44, further comprising instructions for grouping the records of the data container so that the records of each chain have contiguous addresses.

46. A computer program product for encoding integer lists in a computer system, comprising instructions for encoding the integer lists in accordance with n successive coding layers, n being a number at least equal to 1,

wherein for each coding layer, a respective integer range is divided into subsets according to a respective predetermined pattern,

and wherein, for each coding layer in which an input list of integers within the respective integer range is to be processed, the computer program product comprises:

instructions for producing coding data including, for each subset containing at least one integer of said input list, data representing the position of each integer of the input list within said subset and, at least if said layer is the last coding layer, data representing the position of said subset in the pattern;

instructions for storing the coding data in a computer readable medium operatively couplable to a processor of a computer system;

if said layer is not the last coding layer, instructions for forming a further integer list representing the position, in the pattern of said layer, of each subset containing at least one integer of the input list, and for providing said further integer list as an input list of the next layer; and

instructions for storing the coding data produced for said layer in first and second files having a common addressing mechanism, whereby for each subset containing at least one integer of the input list of said layer, the data representing the position of said subset in the pattern are stored in the first file at a first address and the data representing the position of each integer of the input list within said subset are stored in the second file at a second address corresponding to said first address according to the common addressing mechanism.

47. A computer program product according to claim 46, further comprising instructions for storing the coding data produced from one integer list input in the first layer as at least one record chain in a data container defined as a portion of a storage unit allocated to a plurality of integer lists.

48. A computer program product according to claim 47, further comprising instructions for grouping the records of the data container so that the records of each chain have contiguous addresses.

49. A computer program product for encoding integer lists in a computer system, comprising instructions for encoding the integer lists in accordance with n successive coding layers, n being a number at least equal to 2,

wherein for each coding layer, a respective integer range is divided into subsets according to a respective predetermined pattern,

and wherein, for each coding layer in which an input list of integers within the respective integer range is to be processed, the computer program product comprises:

instructions for producing coding data including, for each subset containing at least one integer of said input list, data representing the position of each integer of the input list within said subset and, at least if said layer is the last coding layer, data representing the position of said subset in the pattern;

instructions for storing the coding data in a computer readable medium operatively couplable to a processor of a computer system; and

if said layer is not the last coding layer, instructions for forming a further integer list representing the position, in the pattern of said layer, of each subset containing at least one integer of the input list, and for providing said further integer list as an input list of the next layer,

wherein for each integer k such that 1≦

k≦

n, at least one layer k data container having a plurality of records is provided as a portion of a storage unit in a computer memory, each record of a layer k data container being associated with a layer k integer rank representing the position of a subset in the layer k pattern, and wherein each record of a layer k data container associated with a layer k rank representing the position of a subset in the layer k pattern has a first field for containing data designating the position within said subset of any integer of a layer k input list relating to a layer 1 input list, whereby a combination of said layer k rank with any position designated by the data contained in said first field determines a layer k−

1 rank with which a respective record of the layer k−

1 data container is associated if k>

1, and an integer of said layer 1 input list if k=1.

50. A computer program product according to claim 49, wherein each record of the layer n data container associated with a layer n rank further has a second field for containing said layer n rank.

51. A computer program product according to claim 49, wherein, for 1≦

k≦

n, said data contained in the first field of a record of the layer k data container and designating the position of any integer of a layer k input list within a subset comprise a bitmap segment in which each bit is associated with a respective integer of said subset to indicate whether said integer belongs to said layer k input list.

52. A computer program product according to claim 51, wherein, for 1≦

k≦

n, each record of the layer k data container associated with a layer k rank farther has a second field for containing said layer k rank.

53. A computer program product according to claim 52, wherein each data container comprises at least two files where the first and second fields of the records of said data container are respectively stored, said files being accessible separately.

54. A computer program product according to claim 49, wherein, for 1≦

k>

n, each record of the layer k data container further has a second field for containing a number representing the position of an integer of a layer k+1 input list within a subset of the layer k+1 pattern,

and wherein, for 1>

k≦

n, said data contained in the first field of a record of the layer k data container associated with a layer k rank and designating the position of any integer of a layer k input list within a subset of the layer k pattern comprise a pointer to at least one record of the layer k−

1 data container in which the second field contains a number representing the position of an integer of said layer k input list within said subset of the layer k pattern, whereby said record of the layer k−

1 data container is associated with the layer k−

1 rank determined by the combination of said layer k rank with the position represented by said number.

55. A compute program product according to claim 54, wherein said data contained in the first field of a record of the layer 1 data container and designating the position of any integer of a layer 1 input list within a subset comprise a bitmap segment in which each bit is associated with a respective integer of said subset to indicate whether said integer belongs to said layer 1 input list.

56. A computer program product according to claim 54, wherein each layer k data container for 1≦

k≦

n comprises at least two files where the first and second fields of the records of said data container are respectively stored, said files being accessible separately.

57. A computer program product according to claim 49, wherein, for 1≦

k≦

n, each record of the layer k data container further has a next address field, whereby record chains are defined in the layer k data container by means of the next address fields, and wherein at least some of the layer 1 input lists are respectively associated with record chains in the layer n data container, whereby the coding data for layer n relating to one of said layer 1 input lists are stored in or retrievable from the record chain associated therewith in the layer n data container.

58. A computer program product according to claim 57, wherein, for 1≦

k≦

n, said layer 1 input lists are respectively associated with record chains in the layer k data container, whereby the coding data relating to one of said layer 1 input lists for layer k are stored in or retrievable from the record chain associated therewith in the layer k data container.

59. A computer program product according to claim 57, wherein, for 1≦

k≦

n, each record of the layer k data container further has a head address field for pointing to an address of a first record of a respective chain in the layer k−

1 data container.

60. A computer program product according to claim 57, wherein each layer k data container for 1≦

k≦

n comprises at least two files where the first fields and the next address fields of the records of said data container are respectively stored, said files being accessible separately.

61. A computer program product according to claim 57, further comprising instructions for grouping the records of the data container for each coding layer, so that the records of each chain have contiguous addresses.