The patent badge is an abbreviated version of the USPTO patent document. The patent badge does contain a link to the full patent document.
The patent badge is an abbreviated version of the USPTO patent document. The patent badge covers the following: Patent number, Date patent was issued, Date patent was filed, Title of the patent, Applicant, Inventor, Assignee, Attorney firm, Primary examiner, Assistant examiner, CPCs, and Abstract. The patent badge does contain a link to the full patent document (in Adobe Acrobat format, aka pdf). To download or print any patent click here.
Patent No.:
Date of Patent:
Apr. 12, 2011
Filed:
Oct. 25, 2007
Robert Krauthgamer, Albany, CA (US);
Aranyak Mehta, San Jose, CA (US);
Vijayshankar Raman, Sunnyvale, CA (US);
Atri Rudra, Buffalo, NY (US);
Robert Krauthgamer, Albany, CA (US);
Aranyak Mehta, San Jose, CA (US);
Vijayshankar Raman, Sunnyvale, CA (US);
Atri Rudra, Buffalo, NY (US);
International Business Machines Corporation, Armonk, NY (US);
Abstract
The embodiments of the invention provide a method of ordering an intersecting of a group of lists into a left-deep AND-tree. The method begins by performing a first selecting process including selecting a top list, corresponding to a top leaf of the left-deep AND-tree, from the group of lists to leave remaining lists of the group of lists. The top list can be the smallest list of the group of lists. The method can also select a pair of lists from the group of lists, such that the pair of lists has the smallest intersection size relative to other pairs of lists of the group of lists. Next, the method estimates intersections of the remaining lists with the top list by estimating an amount of intersection between the remaining lists and the top list. This involves sampling a portion of the remaining lists. The method also includes identifying larger list pairs having smaller intersections sizes when compared to smaller list pairs having larger intersections sizes.