Adaptive greedy method for ordering intersecting of a group of lists into a left-deep AND-tree

A computer-implemented method of ordering an intersecting of a group of lists into a left-deep AND-tree, said method comprising:

• performing, by a computer, a first selecting process comprising selecting a top list, corresponding to a top leaf of said left-deep AND-tree, from said group of lists to leave remaining lists of said group of lists;
• estimating, by said computer, intersections of said remaining lists with said top list by estimating an amount of intersection between said remaining lists and said top list;
• performing, by said computer, a second selecting process comprising selecting a worst-case list from said remaining lists that has a smallest amount of intersection, based on said estimating;
• intersecting, by said computer, said top list and said worst-case list;
• removing, by said computer, said worst-case list from said remaining lists to produce updated remaining lists;
• repeating, by said computer, said estimating, said performing of said second selecting process, said intersecting, and said removing using said updated remaining lists iteratively until all lists within said group of lists have been processed to produce a list of intersections;
• and
• outputting, by said computer, said list of intersections,
• wherein said performing of said second selecting process comprises ordering said remaining lists in a binary AND-tree.

A computer-implemented method of ordering an intersecting of a group of lists into a left-deep AND-tree, said method comprising:

• performing, by a computer, a first selecting process comprising selecting a top list, corresponding to a top leaf of said left-deep AND-tree, from said group of lists to leave remaining lists of said group of lists, wherein said top list comprises a smallest list of said lists;
• estimating, by said computer, intersections of said remaining lists with said top list by estimating an amount of intersection between said remaining lists and said top list;
• performing, by said computer, a second selecting process comprising selecting a worst-case list from said remaining lists that has a smallest amount of intersection based on said estimating;
• intersecting, by said computer, said top list and said worst-case list;
• removing, by said computer, said worst-case list from said remaining lists to produce updated remaining lists;
• repeating, by said computer, said estimating, said performing of said second selecting process, said intersecting, and said removing using said updated remaining lists iteratively until all lists within said group of lists have been processed to produce a list of intersections;
• and
• outputting, by said computer, said list of intersections.

A computer-implemented method of ordering an intersecting of a group of lists into a left-deep AND-tree, said method comprising:

• performing, by a computer, a first selecting process comprising selecting a top list, corresponding to a top leaf of said left-deep AND-tree, from said group of lists to leave remaining lists of said group of lists, wherein said top list comprises a smallest list of said lists;
• estimating, by said computer, intersections of said remaining lists with said top list by estimating an amount of intersection between said remaining lists and said top list;
• performing, by said computer, a second selecting process comprising selecting a worst-case list from said remaining lists that has a smallest amount of intersection based on said estimating;
• intersecting, by said computer, said top list and said worst-case list;
• removing, by said computer, said worst-case list from said remaining lists to produce updated remaining lists;
• repeating, by said computer, said estimating, said performing of said second selecting process, said intersecting, and said removing using said updated remaining lists iteratively until all lists within said group of lists have been processed to produce a list of intersections;
• and
• outputting, by said computer, said list of intersections,
• wherein said performing of said second selecting process comprises ordering said remaining lists in a binary AND-tree.

A computer-implemented method of ordering an intersecting of a group of lists into a left-deep AND-tree, said method comprising:

• performing, by a computer, a first selecting process comprising selecting a top list, corresponding to a top leaf of said left-deep AND-tree, from said group of lists to leave remaining lists of said group of lists, wherein said top list comprises a smallest list of said lists;
• estimating, by said computer, intersections of said remaining lists with said top list by estimating an amount of intersection between said remaining lists and said top list;
• performing, by said computer, a second selecting process comprising selecting a worst-case list from said remaining lists that has a smallest amount of intersection based on said estimating, wherein said performing of said second selecting process comprises ordering said remaining lists in a binary AND-tree;
• intersecting, by said computer, said top list and said worst-case list;
• removing, by said computer, said worst-case list from said remaining lists to produce updated remaining lists;
• repeating, by said computer, said estimating, said performing of said second selecting process, said intersecting, and said removing using said updated remaining lists iteratively until all lists within said group of lists have been processed to produce a list of intersections;
• and
• outputting, by said computer, said list of intersections.

A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform a method of ordering an intersecting of a group of lists into a left-deep AND-tree, said method comprising:

• performing a first selecting process comprising selecting a top list, corresponding to a top leaf of said left-deep AND-tree, from said group of lists to leave remaining lists of said group of lists, wherein said top list comprises a smallest list of said lists;
• estimating intersections of said remaining lists with said top list by estimating an amount of intersection between said remaining lists and said top list;
• performing a second selecting process comprising selecting a worst-case list from said remaining lists that has a smallest amount of intersection based on said estimating, wherein said performing of said second selecting process comprises ordering said remaining lists in a binary AND-tree;
• intersecting said top list and said worst-case list;
• removing said worst-case list from said remaining lists to produce updated remaining lists;
• repeating said estimating, said performing of said second selecting process, said intersecting, and said removing using said updated remaining lists iteratively until all lists within said group of lists have been processed to produce a list of intersections;
• and
• outputting said list of intersections.