Patent ID: 11868331
Assignee: nan
Field: Computer technology (Electrical engineering)
Classification: CPC G | IPC G

Claim 0:
1. A method for aligning first and second data tables,
wherein:
the first data table comprises a first array, the first array comprising a plurality of first-table rows, each first-table row of the plurality of first-table rows (i) storing a first-table key, of a plurality of first-table keys, that uniquely identifies said each first-table row in the first array and (ii) having a first-table row position that uniquely locates said each first-table row in the first array, the first-table key being different from the first-table row position;
the second data table comprises a second array, the second array comprising a plurality of second-table rows, each second-table row of the plurality of second-table rows (i) storing a second-table key, of a plurality of second-table keys, that uniquely identifies said each second-table row in the second array and (ii) having a second-table row position that uniquely locates said each second-table row in the second array, the second-table key being different from the second-table row position;
the first array has a first subset of matched first-table rows and the second array has a second subset of matched second-table rows, the first-table key of each matched first-table row of the first subset equaling the second-table key of a corresponding matched second-table row of the second subset;
the first array has a third subset of unmatched first-table rows, the first-table key of each unmatched first-table row of the third subset not equaling any of the plurality of second-table keys; and
the second array has a fourth subset of unmatched second-table rows, the second-table key of each unmatched second-table row of the fourth subset not equaling any of the plurality of first-table keys;

the method comprising:
generating a key search tree having a plurality of nodes, each of the plurality of nodes storing (i) one of the plurality of second-table keys and (ii) the second-table row position of the one of the plurality of second-table rows having said one of the plurality of second-table keys;
constructing, using the key search tree, a row-index array comprising a plurality of row-index elements that are indexed in one-to-one correspondence with the plurality of first-table rows of the first array, the row-index array including a plurality of matched elements of the plurality of row-index elements, each matched element of the plurality of matched elements storing the second-table row position of the matched second-table row whose corresponding matched first-table row is located at the first-table row position that matches an element position of said each matched element in the row-index array;
compacting, using the row-index array, the first data table into a compacted first data table by discarding the unmatched first-table rows from the first data table;
reordering, using the row-index array, the second data table into a reordered second data table by:
discarding the unmatched second-table rows from the second data table; and
rearranging the matched second-table rows such that an order of the second-table keys of the matched second-table rows is similar to matches an order of the first-table keys of the matched first-table rows; and

joining the compacted first data table and the reordered second data table.