METHOD FOR CARDINALITY COUNTING METHOD, CARDINALITY COUNTER AND CARDINALITY COUNTING SYSTEM

摘要

PROBLEM TO BE SOLVED: To estimate an input cardinality with previously specified estimation accuracy by considering an input cardinality necessary for guaranteeing the estimation accuracy of two counting methods and the accuracy of both the counting method in the case of performing cardinality counting by using two counting methods.;SOLUTION: A cardinality counting method for specifying a certain attribute of a record as key k and stochastically estimating/recording the cardinality of an attribute F which can be optionally specified on the record in each key k comprises a statistical management part for managing a bit map for recoding the cardinality in each key k and a cardinality estimation part for estimatively calculating the cardinality by using the information of the bit map; wherein, a counting method (e.g. a linear counting method) suited to the counting of small cardinalities and a counting method (e.g. a Loglog counting method) suited to the counting large cardinalities are used together, and while considering estimation errors in the two counting methods and the range of input cardinalities suited to the two counting methods, a cardinality is estimated/recorded on the basis of the previously specified estimation accuracy by using estimated values of both the counting methods.;COPYRIGHT: (C)2008,JPO&INPIT