Methods of Encoding a Combining Integer Lists in a Computer System, and Computer Software Product for Implementing Such Methods

• US 20080263072A1
• Filed: 07/10/2007
• Published: 10/23/2008
• Est. Priority Date: 11/29/2000
• Status: Abandoned Application

• Current Assignee: Virtual Key Graph
• Original Assignee: Virtual Key Graph
• Inventors: Koskas, Elie Ouzi
• Application Number:
  US11/775,697
• Publication Number:
  US 20080263072A1
• Time in Patent Office: Days
• US Class Current: 707/101
• 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-30. -30. (canceled)

31. A computerized method of combining a plurality of first integer lists into a second integer list, wherein at least one of the first integer lists is represented by stored coding data provided by a coding scheme comprising n successive coding layers, n being a number at least equal to 1, each layer having a predetermined pattern for dividing a range covering integers of an input list of said layer into subsets, said first integer list being the input list of the first layer, wherein for any layer other than the last layer, an integer list representing the position, in the pattern of said layer, of each subset containing at least one integer of the input list forms the input list for the next layer, wherein the stored coding data representing a first integer list comprise, for each layer and 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 layer, data representing the position of said subset in the pattern of said layer, the method comprising the steps of:

defining a combination of intermediary lists each corresponding to at least one of the first integer lists;

for k decreasing from n to 1, computing a layer k result list by combining a plurality of layer k intermediary lists in accordance with said combination; and

producing the second integer list as the layer 1 result list,

and wherein, for any intermediary list corresponding to at least one first integer list represented by stored coding data, the layer n intermediary list is determined from said stored coding data as consisting of the integers of any layer n input list associated with said at least one first integer list in the coding scheme and, if n>

1, each layer k intermediary list for k<

n is determined from said stored coding data and the layer k+1 result list as consisting of any integer of a layer k input list associated with said at least one first integer list in the coding scheme which belongs to a layer k subset whose position is represented in the layer k+1 result list.

32. A method according to claim 31, wherein, in the patter of each layer, the subsets are consecutive intervals consisting of the same number of integers.

33. A method according to claim 32, wherein said number of integers is a whole power of 2 for each layer.

34. A method according to claim 31, wherein, in the coding scheme, the coding data representing the position of each integer of an input list within a subset for the coding layer n define a layer n bitmap segment in which each bit is associated with a respective integer of the subset to indicate whether said integer belongs to said input list, while the data representing the position of said subset in the layer n pattern comprise a layer n integer rank associated with said layer n bitmap segment, and wherein the layer n intermediary list for an intermediary list corresponding to at least one first integer list represented by stored coding data is determined in a procedure comprising:

initializing a layer n bitmap vector with logical zeroes;

obtaining the layer n ranks and associated bitmap segments from said stored coding data; and

for each of said layer n ranks, superimposing the layer n bitmap segment associated therewith onto a segment of said layer n bitmap vector having a position determined by said layer n rank, the superimposition being performed according to a bitwise Boolean OR operation,

said layer n intermediary list corresponding to the resulting layer n bitmap vector.

35. A method according to claim 34, wherein n>

1 and in the coding scheme, the coding data representing the position of each integer of an input list within a subset for a coding layer k<

n define a layer k bitmap segment in which each bit is associated with a respective integer of the subset to indicate whether said integer belongs to said input list, while the coding data further comprise a layer k integer rank associated with said layer k bitmap segment to represent the position of said subset in the layer k pattern, and wherein, for k<

n, the layer k intermediary list for an intermediary list corresponding to at least one first integer list represented by stored coding data is determined in a procedure comprising;

initializing a layer k bitmap vector with logical zeroes;

obtaining the layer k ranks from said stored coding data; and

selecting any obtained layer k rank belonging to the layer k+1 result list and superimposing the associated layer k bitmap segment onto a segment of said layer k bitmap vector having a position determined by the selected layer k rank, the superimposition being performed according to a bitwise Boolean OR operation,

said layer k intermediary list corresponding to the resulting layer k bitmap vector.

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

k<

n, the layer k ranks and the layer k bitmap segments associated therewith are stored at corresponding addresses in distinct first and second files, and said procedure for determining the layer k intermediary list for an intermediary list corresponding to at least one first integer list represented by stored coding data comprises;

providing a rank table in a RAM memory, having records associated with the addresses in said first and second files;

filling the rank table by writing any selected layer k rank into the rank table record associated with the address of the selected layer k rank in said first file; and

for any record of the filled rank table containing a layer k rank and associated with an address in the second file, reading the associated layer k bitmap segment at said address in the second file and superimposing the read layer k bitmap segment onto a segment of said layer k bitmap vector having a position determined by said layer k rank.

37. A method according to claim 34, wherein n>

1 and for any coding layer k such that 1≦

k<

n, a layer k′

filtering list is determined for k≦

k′

≦

n, said layer k′

filtering list being the layer k′

input list obtained by providing the layer k result list as an input list in layer k of the coding scheme,

wherein, in the coding scheme, the coding data representing the position of each integer of an input list within a subset for a coding layer k<

n define a layer k bitmap segment in which each bit is associated with a respective integer of the subset to indicate whether said integer belongs to said input list, while a layer k integer rank associated with said layer k bitmap segment represents the position of said subset in the layer k pattern, and wherein, for k<

n, the layer k intermediary list for an intermediary list corresponding to at least one first integer list represented by stored coding data is determined in a procedure comprising;

/a/ initializing a layer k bitmap vector with logical zeroes;

/b/ selecting the layer n ranks obtained from said stored coding data, and setting k′

=n;

/c/ for each selected layer k′

rank;

/c1/ if the selected layer k′

rank represents the position in the layer k′

pattern of a subset which includes at least one integer of the layer k′

filtering list, obtaining the layer k′

bitmap segment with which the selected layer k′

rank is associated;

/c2/ for any integer of the layer k′

filtering list whose position within said subset is represented in said layer k′

bitmap segment, selecting a respective layer k′

−

1 rank determined from the selected layer k′

rank and said position represented in said layer k′

bitmap segment;

/c3/ if k′

>

k+1, executing step /c/ with k′

decremented by one unit; and

/c4/ if k′

−

1=k, obtaining any layer k bitmap segment with which a selected layer k′

−

1 rank is associated, and superimposing said layer k bitmap segment onto a segment of said layer k bitmap vector having a position determined by said selected layer k′

−

1 rank, the superimposition being performed according to a bitwise Boolean OR operation,

said layer k intermediary list corresponding to the resulting layer k bitmap vector.

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

k<

n, the layer k bitmap segments are stored in at least one layer k file at addresses respectively corresponding to the layer k ranks associated therewith, and said procedure for determining the layer k intermediary list for an intermediary list corresponding to at least one first integer list represented by stored coding data comprises;

providing a rank table in a RAM memory, having records associated with the addresses in said layer k file;

filling the rank table by writing any selected layer k rank into the rank table record associated with the address corresponding to the selected layer k rank; and

for any record of the filled rank table containing a layer k rank and associated with an address in said layer k file, reading the associated layer k bitmap segment at said address and superimposing the read layer k bitmap segment onto a segment of said layer k bitmap vector having a position determined by said layer k rank.

39. A method according to claim 31, wherein a coding data container comprising records having respective addresses is provided for each coding layer k≦

n, for storing together layer k coding data of a plurality of said first integer lists, and wherein each record of the coding data container for each layer includes a first field for storing a rank related to the pattern of said layer, a second field for storing an address value and a third field for storing a bitmap segment, whereby said address value either points to another record of the data container where further layer k coding data relating to the same first integer list are stored or designates an end of coding data.

40. A method according to claim 39, wherein the records stored in the data container for each coding layer k are so grouped that the records where the layer k coding data of any first integer list are stored have contiguous addresses.

41. A method according to claim 31, wherein the coding data are stored in at least one file allocated to one first integer list.

42. A method according to claim 41, wherein the coding data of each layer are stored in first and second files having a common addressing, 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 and the data representing the position of each integer of the input list within said subset are stored at a corresponding address in the second file.

43. A method according to claim 31, wherein the intermediary lists include at least one preset list, said preset list consisting of one of the first integer lists for which the layer k input lists, according to the coding scheme, are determined in advance for 1≦

k≦

n, said layer k input lists being the respective layer k intermediary lists corresponding to said preset list.

44-63. -63. (canceled)

64. A computer program product for combining a plurality of first integer lists into a second integer list, wherein at least one of the first integer lists is represented by stored coding data provided by a coding scheme comprising n successive coding layers, n being a number at least equal to 1, each layer having a predetermined pattern for dividing a range covering integers of an input list of said layer into subsets, said first integer list being the input list of the first layer, wherein for any layer other than the last layer, an integer list representing the position, in the pattern of said layer, of each subset containing at least one integer of the input list forms the input list for the next layer, wherein the stored coding data representing a first integer list comprise, for each layer and 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 layer, data representing the position of said subset in the pattern of said layer, the computer program product comprising:

instructions for defining a combination of intermediary lists each corresponding to at least one of the first integer lists;

for k decreasing from n to 1, instructions for computing a layer k result list by combining a plurality of layer k intermediary lists in accordance with said combination; and

instructions for producing the second integer list as the layer 1 result list,

whereby, for any intermediary list corresponding to at least one first integer list represented by stored coding data, the layer n intermediary list is determined from said stored coding data as consisting of the integers of any layer n input list associated with said at least one first integer list in the coding scheme and, if n>

1, each layer k intermediary list for k<

n is determined from said stored coding data and the layer k+1 result list as consisting of any integer of a layer k input list associated with said at least one first integer list in the coding scheme which belongs to a layer k subset whose position is represented in the layer k+1 result list.

65. A computer program product according to claim 64, wherein, in the pattern of each layer, the subsets are consecutive intervals consisting of the same number of integers.

66. A computer program product according to claim 65, wherein said number of integers is a whole power of 2 for each layer.

67. A computer program product according to claim 64, wherein, in the coding scheme, the coding data representing the position of each integer of an input list within a subset for the coding layer n define a layer n bitmap segment in which each bit is associated with a respective integer of the subset to indicate whether said integer belongs to said input list, while the data representing the position of said subset in the layer n pattern comprise a layer n integer rank associated with said layer n bitmap segment, the computer program product comprising instructions for determining the layer n intermediary list for an intermediary list corresponding to at least one first integer list represented by stored coding data, said instructions for determining the layer n intermediary list comprising:

instructions for initializing a layer n bitmap vector with logical zeroes;

instructions for obtaining the layer n ranks and associated bitmap segments from said stored coding data; and

for each of said layer n ranks, instructions for superimposing the layer n bitmap segment associated therewith onto a segment of said layer n bitmap vector having a position determined by said layer n rank, the superimposition being performed according to a bitwise Boolean OR operation,

said layer n intermediary list corresponding to the resulting layer n bitmap vector.

68. A computer program product according to claim 67, wherein n>

1 and in the coding scheme, the coding data representing the position of each integer of an input list within a subset for a coding layer k<

n define a layer k bitmap segment in which each bit is associated with a respective integer of the subset to indicate whether said integer belongs to said input list, while the coding data further comprise a layer k integer rank associated with said layer k bitmap segment to represent the position of said subset in the layer k pattern, the computer program product comprising, for k<

n, instructions for determining the layer k intermediary list for an intermediary list corresponding to at least one first integer list represented by stored coding data, said instructions for determining the layer k intermediary list comprising;

instructions for initializing a layer k bitmap vector with logical zeroes;

instructions for obtaining the layer k ranks from said stored coding data; and

instructions for selecting any obtained layer k rank belonging to the layer k+1 result list and for superimposing the associated layer k bitmap segment onto a segment of said layer k bitmap vector having a position determined by the selected layer k rank, the superimposition being performed according to a bitwise Boolean OR operation,

said layer k intermediary list corresponding to the resulting layer k bitmap vector.

69. A computer program product according to claim 68, wherein, for 1≦

k<

n, the layer k ranks and the layer k bitmap segments associated therewith are stored at corresponding addresses in distinct first and second files, and said instructions for determining the layer k intermediary list for an intermediary list corresponding to at least one first integer list represented by stored coding data comprises;

instructions for providing a rank table in a RAM memory having records associated with the addresses in said first and second files;

instructions for filling the rank table by writing any selected layer k rank into the rank table record associated with the address of the selected layer k rank in said first file; and

for any record of the filled rank table containing a layer k rank and associated with an address in the second file, instructions for reading the associated layer k bitmap segment at said address in the second file and for superimposing the read layer k bitmap segment onto a segment of said layer k bitmap vector having a position determined by said layer k rank.

70. A computer program product according to claim 67, further comprising, for any coding layer k such that 1<

k≦

n instructions for determining a layer k′

filtering list for k≦

k′

≦

n, said layer k′

filtering list being the layer k′

input list obtained by providing the layer k result list as an input list in layer k of the coding scheme,

wherein, in the coding scheme, the coding data representing the position of each integer of an input list within a subset for a coding layer k<

n define a layer k bitmap segment in which each bit is associated with a respective integer of the subset to indicate whether said integer belongs to said input list, while a layer k integer rank associated with said layer k bitmap segment represents the position of said subset in the layer k pattern, the computer program product comprising, for k<

n, instructions for determining the layer k intermediary list for an intermediary list corresponding to at least one first integer list represented by stored coding data, said instructions for determining the layer k intermediary list comprising;

/a/ instructions for initializing a layer k bitmap vector with logical zeroes;

/b/ instructions for selecting the layer n ranks obtained from said stored coding data, and for setting k′

=n;

/c/ for each selected layer k′

rank;

/c1/ if the selected layer k′

rank represents the position in the layer k′

pattern of a subset which includes at least one integer of the layer k′

filtering list, instructions for obtaining the layer k′

bitmap segment with which the selected layer k′

rank is associated;

/c2/ for any integer of the layer k′

filtering list whose position within said subset is represented in said layer k′

bitmap segment, instructions for selecting a respective layer k′

−

1 rank determined from the selected layer k′

rank and said position represented in said layer k′

bitmap segment;

/c3/ if k′

>

k+1, instructions for executing the instructions /c/ with k′

decremented by one unit; and

/c4/ if k′

−

1=k, instructions for obtaining any layer k bitmap segment with which a selected layer k′

−

1 rank is associated, and for superimposing said layer k bitmap segment onto a segment of said layer k bitmap vector having a position determined by said selected layer k′

−

1 rank, the superimposition being performed according to a bitwise Boolean OR operation,

said layer k intermediary list corresponding to the resulting layer k bitmap vector.

71. A computer program product according to claim 70 further comprising, for 1≦

k<

n, instructions for storing the layer k bitmap segments in at least one layer k file at addresses respectively corresponding to the layer k ranks associated therewith, and said instructions for determining the layer k intermediary list for an intermediary list corresponding to at least one first integer list represented by stored coding data comprises;

instructions for providing a rank table in a RAM memory, having records associated with the addresses in said layer k file;

instructions for filling the rank table by writing any selected layer k rank into the rank table record associated with the address corresponding to the selected layer k rank; and

for any record of the filled rank table containing a layer k rank and associated with an address in said layer k file, instructions for reading the associated layer k bitmap segment at said address and for superimposing the read layer k bitmap segment onto a segment of said layer k bitmap vector having a position determined by said layer k rank.

72. A computer program product according to claim 64, wherein the intermediary lists include at least one preset list, said preset list consisting of one of the first integer lists for which the layer k input lists, according to the coding scheme, are determined in advance for 1≦

k≦

n, said layer k input lists being the respective layer k intermediary lists corresponding to said preset list.