Absolute bounds on set intersection and union sizes from distribution information
Loading...
Authors
Rowe, Neil C.
Subjects
intersection
union
databases
query processing
statistical computing
statistical databases
inequalities
sets
Boolean algebra
estimation
frequency distributions
union
databases
query processing
statistical computing
statistical databases
inequalities
sets
Boolean algebra
estimation
frequency distributions
Advisors
Date of Issue
1988-07
Date
July 1988
Publisher
Monterey, California. Naval Postgraduate School
Language
Abstract
Estimation of set intersection and union sizes is important for access method selection for a database and other data retrieval
problems. Absolute bounds on sizes are often easier to compute than estimates, requiring no distributional or independence
assumptions, and can answer many of the same needs. We present a catalog of quick closed-form bounds on set intersection
and union sizes; they can be expressed as rules, and managed by a rule-based system architecture. These methods use a
variety of statistics precomputed on the data, and exploit homomorphisms (onto mappings) of the data items onto
distributions that can be more easily analyzed. The methods can be used anytime, but tend to work best when there are strong
or complex correlations in the data. This circumstance is poorly handled by the standard independence-assumption and
distributional-assumption estimates, and hence our methods fill a need.
Type
Conference Paper
Description
The equations were redrawn in 2008.
IEEE Transactions on Software Engineering, SE-14, no. 7 (July 1988), 1033-1048. The equations were redrawn in 2008.
IEEE Transactions on Software Engineering, SE-14, no. 7 (July 1988), 1033-1048. The equations were redrawn in 2008.
Series/Report No
Department
Computer Science (CS)
Organization
Identifiers
NPS Report Number
Sponsors
The work reported herein was partially supported by the Foundation Research Program of the Naval Postgraduate School with funds provided by the Chief of Naval Research
Supported by the Foundation Research Program of the Naval Postgraduate School with funds provided by the Chief of Naval Research
Supported by the Foundation Research Program of the Naval Postgraduate School with funds provided by the Chief of Naval Research
Funder
The work reported herein was partially supported by the Foundation Research Program of the Naval Postgraduate School with funds provided by the Chief of Naval Research
Format
Citation
IEEE Transactions on Software Engineering, SE-14, no. 7 (July 1988), 1033-1048.
Distribution Statement
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.