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:
Feb. 23, 2010
Filed:
Sep. 30, 2004
Sumit Ganguly, Bhopal, IN;
Minos Garofalakis, Morristown, NJ (US);
Rajeev Rastogi, New Providence, NJ (US);
Krishan Sabnani, Westfield, NJ (US);
Sumit Ganguly, Bhopal, IN;
Minos Garofalakis, Morristown, NJ (US);
Rajeev Rastogi, New Providence, NJ (US);
Krishan Sabnani, Westfield, NJ (US);
Alcatel-Lucent USA Inc., Murray Hill, NJ (US);
Abstract
A distinct-count estimate is obtained in a guaranteed small footprint using a two level hash, distinct count sketch. A first hash fills the first-level hash buckets with an exponentially decreasing number of data-elements. These are then uniformly hashed to an array of second-level-hash tables, and have an associated total-element counter and bit-location counters. These counters are used to identify singletons and so provide a distinct-sample and a distinct-count. An estimate of the total distinct-count is obtained by dividing by the distinct-count by the probability of mapping a data-element to that bucket. An estimate of the total distinct-source frequencies of destination address can be found in a similar fashion. By further associating the distinct-count sketch with a list of singletons, a total singleton count and a heap containing the destination addresses ordered by their distinct-source frequencies, a tracking distinct-count sketch may be formed that has considerably improved query time.