• DocumentCode
    1057869
  • Title

    Absolute bounds on set intersection and union sizes from distribution information

  • Author

    Rowe, Neil C.

  • Author_Institution
    Dept. of Comput. Sci., US Naval Postgraduate Sch., Monterey, CA, USA
  • Volume
    14
  • Issue
    7
  • fYear
    1988
  • fDate
    7/1/1988 12:00:00 AM
  • Firstpage
    1033
  • Lastpage
    1048
  • Abstract
    A catalog of quick closed-form bounds on set intersection and union sizes is presented; 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
  • Keywords
    Boolean algebra; database theory; file organisation; set theory; statistical analysis; Boolean algebra; closed-form bounds; database access; distribution information; file organisation; rule-based system architecture; set intersection; set theory; statistical analysis; union sizes; Algebra; Algorithm design and analysis; Computer architecture; Distributed computing; Frequency estimation; Information retrieval; Knowledge based systems; Statistical analysis; Statistical distributions; Transaction databases;
  • fLanguage
    English
  • Journal_Title
    Software Engineering, IEEE Transactions on
  • Publisher
    ieee
  • ISSN
    0098-5589
  • Type

    jour

  • DOI
    10.1109/32.42743
  • Filename
    42743