Absolute bounds on set intersection and union sizes from distribution information
Rowe, Neil C.
MetadataShow full item record
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.
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.
RightsThis 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.
Showing items related by title, author, creator and subject.
Rowe, Neil C. (Monterey, California. Naval Postgraduate School, 1985-09); NPS-52-85-014Estimation of set intersection and union sizes is important for access method selection for a database. Absolute bounds on sizes are often much easier to compute than size estimates, requiring no distributional or independence ...
Murphy, Douglas M. (Monterey, California. Naval Postgraduate School, 1995-09);The current Department of Defense shipping procedures do not encourage Installation Transportation Officers (ITOs) to use small parcel carriers (SPCs) for domestic ground transportation. There is still a significant amount ...
Stress distribution in two circular cylinders intersecting at right angles under the influence of internal pressure Harmon, Leonard Edward (Pasadena, California; California Institute of Technology, 1949);This investigation is an experimental study of the stress distribution in two circular cylinders intersecting at right angles and acted on by internal pressure. Two specimens of the thick-wall category were tested to ...