4 ms·

Estimating the amount of unique elements in a set and counting the amount of unique elements in a set are very different things. Cool method, bad headline.

• dools 2y ago
  It's an approximation, not an estimation.
  • ranguna 2y ago
    Still very different things, no?
    • coldtea 2y ago
      It's the same thing at different degrees of accuracy. The goal is the same.
      • amelius 2y ago
        Still, counting things and counting unique things are two different procedures.
  • blackkettle 2y ago
    Actually, my understanding is that it is an estimation because in the given context we don't know or cannot compute the true answer due to some kind of constraint (here memory or the size of |X|). An approximation is when we use a simplified or rounded version of an exact number that we actually know.
    • dools 2y ago
      Wikipedia is on your side: "In mathematics, approximation describes the process of finding estimates in the form of upper or lower bounds for a quantity that cannot readily be evaluated precisely" This process doesn't use upper and lower bounds. However, it still seems more like approximation than estimation to me because of this: “Of course,” Variyam said, “if the [memory] is so big that it fits all the words, then we can get 100% accuracy. It seems that in estimation the answer should be unknowable without additional information, whereas in this case it's just a matter of resolution or granularity because of the memory size. Anyhoo ... EDIT: also the paper says "estimate" and the article says both "approximate" and "estimate" at different times so it seems everyone except me thinks it's either an estimation or that estimation and approximation are interchangeable.
  • davidmurdoch 2y ago
    The authors of the article disagree with you.
    • dools 2y ago
      The authors of the paper disagree with me, the authors of the article don't (they use both approximate and estimate, but the paper does say estimate).
  • chrisweekly 2y ago
    For someone who's pretty well-versed in English, but not a math-oriented computer scientist, this seems like a distinction without a difference. Please remedy my ignorance.
    • lupire 2y ago
      My GP was wrong, but the words are different. Eatimation is a procedure the generates an estimate, which is a kind of approximation, while approximation is a result value. They are different "types", as a computer scientist would say. An approximation is any value that is justifiably considered to be nearly exact. ("prox" means "near". See also "proximate" and "proxy".) Estimation is one way to generate an approximation. An estimate is a subtype of an approximation. There are non-estimation ways to generate an approximation. For example, take an exact value and round it to the nearest multiple of 100. That generates an approximation, but does not use estimation.
      • jameshart 2y ago
        I’m not sure the linguistic differences here are as cut and dried as you would like them to be. Estimate and approximate are both verbs, so you can derive nouns from them both for the process of doing the thing, and for the thing that results from such a process. Estimation is the process of estimating. It produces an estimate. Approximation is the process of approximating. It produces an approximation. You can also derive adjectives from the verbs as well. An estimate is an estimated value. An approximation is an approximate value. But you’re right that the ‘approximate’ terms make claims about the result - that it is in some way near to the correct value - while the ‘estimate’ derived terms all make a claim about the process that produced the result (ie that it was based on data that is known to be incomplete, uncertain, or approximate)
• jameshart 2y ago
  They’re not very different things; the terms are used interchangeably in most contexts because in the real world all counting methods have some nonzero error rate. We talk about ‘counting votes’ in elections, for example, yet when things are close we perform ‘recounts’ which we fully expect can produce slightly different numbers than the original count. That means that vote counting is actually vote estimating, and recounting is just estimating with a tighter error bound. I kind of think the mythology of the ‘countless stones’ (https://en.wikipedia.org/wiki/Countless_stones https://en.wikipedia.org/wiki/Countless_stones) is a sort of folk-reminder that you can never be too certain that you counted something right. Even something as big and solid and static as a standing stone. The situations where counting is not estimating are limited to the mathematical, where you can assure yourself of exhaustively never missing any item or ever mistaking one thing’s identity for another’s.
  • lupire 2y ago
    Come on. There is a fundamental difference between trying to get an exactly answer and not trying to get an exactly correct answer.
    • jameshart 2y ago
      It’s not a fundamental difference, it’s a fundamental constraint. There are circumstances - and in real life those circumstances are very common - where you must accept that getting an exactly correct answer is not realistic. Yet nonetheless you want to ‘count’ things anyway. We still call procedures for counting things under those circumstances ‘counting’. The constraints on this problem (insufficient memory to remember all the unique items you encounter) are one such situation where even computerized counting isn’t going to be exact.
      • Levitz 2y ago
        I agree with you, but we are talking theory here. The algorithm doesn't count, it estimates. You can make an algorithm that counts, you can make an algorithm that estimates, this is the second.
• Koshkin 2y ago
  True - for (relatively) small numbers. For large (huge) numbers estimation is usually considered to be equivalent to counting, and the result is sometimes represented using the "scientific" notation (i.e. "floating-point") rather than as an integer. For example, the mole is an integer whose value is only known approximately (and no one cares about the exact value anyway).
  • OutOfHere 2y ago
    This doesn't justify estimation to be equivalent to counting even if some mathematicians consider them to be the same. Floating points are for estimation. Integers are for counting. The two are not the same, not even for large numbers.
    • Koshkin 2y ago
      "Equivalent" and "the same" are sometimes equivalent. (Or the same.) It depends on what the meaning of the word 'is' is. https://libquotes.com/bill-clinton/quote/lby0h7o https://libquotes.com/bill-clinton/quote/lby0h7o
  • YoshiRulz 2y ago
    As of May 2019, the mole has an exact value, and Carbon-12's molar mass is the empirically-determined value.