Back to results
US 8,666,991 B2Granted
Combinators to build a search engine
AssigneeBlekko, Inc.
InventorsKeith Peters, Bryn Robert Dole, Michael Markson, Robert Michael Saliba, Rich Skrenta, Robert N. Truel, Gregory B. Lindahl
Life of this patent
Estimating the term…
Abstract
A method of counting items in a database system. The database system having nodes comprising processors and memory where the memory stores programs to be executed by the processors. Identifying and counting M unique number of items. Determining and storing a logcount for M unique items.
Claims18
A method of counting items in a database system comprising:
- at the database system having one or more nodes comprising,
- one or more processors and memory, the memory of the one or more nodes storing one or more programs to be executed by the one or more processors;
- identifying an M number of items;
- counting unique items of the M number of items;
- determining a logcount for the unique items of the M number of items;
- and
- storing the logcount for the unique items,
- wherein determining a logcount comprises,
- partitioning each of the unique items of the M number of items into a set of N number of parts, wherein each N part includes a subset of the unique items of the M number of items and wherein each subset of unique items is expressed as a bit value;
- finding a lowest unset bit in each of the N number of parts for each subset of the M number of items;
- setting the lowest bit in N intermediate values for each subset of unique items in the set of N parts;
- averaging the lowest unset bit values of the N intermediate values for each set of N parts;
- and
- applying the averaged value as a log value expressed in powers-of-two.
11 more elements
A method of counting items in a database system comprising:
- at the database system having one or more nodes comprising one or more processors and memory, the memory of the one or more nodes storing one or more programs to be executed by the one or more processors;
- identifying an M number of items;
- counting unique items of the M number of items;
- determining a logcount for the unique items of the M number of items;
- and
- storing the logcount for the unique items,
- wherein determining a logcount includes:
- partitioning each of the unique items of the M number of items into a set of N number of parts,
- wherein each N part includes a subset of the unique items of the M number of items, and
- wherein each subset of unique items is expressed as a bit value;
- finding a lowest unset bit in each of the N number of parts for each subset of the M number of items;
- choosing which bit to set in the N intermediate values using an arbitrary exponential decay factor;
- averaging the lowest unset bit values of the N intermediate values for each set of N parts;
- and
- applying the average value as a log value expressed with an arbitrary base related to the arbitrary exponential decay factor.
12 more elements
Dependencies are inferred from the claim text.