Flajolet et alによるHyperLogLog アルゴリズムは、ごく少量のメモリを使用してセットのカーディナリティを推定する巧妙な方法を説明しています。ただし、計算では元のセットのN個の要素すべてが考慮されます。元のNの小さなランダムサンプル（たとえば、10％）にしかアクセスできなかった場合はどうなりますか？HyperLogLogまたは同様のアルゴリズムをこの状況にどのように適応させることができるかについての研究はありますか？
これは本質的に、明確な価値の推定として説明されている問題であり、豊富な研究が存在することを認識しています（概要については、たとえばこの論文を参照してください）。ただし、私が知っている明確な値の推定に関する調査では、HyperLogLogで使用されているアプローチとは非常に異なる多くのアドホック推定量を使用しています。したがって、誰かがHyperLogLogを明確な値の見積もりの問題に適応させることをすでに考えているのではないかと思います。
ただし、私が知っている明確な値の推定に関する調査では、HyperLogLogで使用されているアプローチとは非常に異なる多くのアドホック推定量を使用しています。
はい、彼らは非常に異なる問題を解決しているからです。
1.000.000の偽造ドル紙幣を没収したばかりで、個別のシリアル番号の数を知りたいとします。
それらの100.000をサンプリングすると（旧式の蒸気駆動計数機には1kのメモリしかないため、HyperLogLogを使用して）、5000の異なるシリアル番号をカウントします。各シリアル番号は約20回発生します。そうすれば、隠し場所全体に5000を少し超える異なるシリアル番号しか含まれないことを確信できます。
ここで、1つのシリアル番号が95.001回発生し、4999のシリアル番号が1回だけ発生するとします。どうやら、いくつかの善意の紙幣があなたの隠し場所に侵入したようです。これで、隠し場所に約5％の正直な紙幣が含まれていることを確信できます。そのため、隠し場所全体に約50.000の異なるシリアル番号が含まれています。
サンプルの頻度の分布は、スタッシュ全体の分布について何かを推測するために使用されることに注意してください。これは、実際には、引用する2番目の論文の「アドホック」（あなたの言葉）の方法の1つとして言及されています（「サンプリングベースの個別の値の数の推定（..）」）。
パラメトリック推定量の背後にある考え方は、確率分布を さまざまな属性値の観測された相対度数に適合させることです。
また、HyperLogLogおよび同様のメソッドの結果は、それらの値に対するサンプルの分布に完全に影響されないことに注意してください。しかし、あなたの最終的な見積もりは明らかにそれに大きく依存しています！
私のアドバイス：選択した方法（HyperLogLogなど）を使用してサンプル内の個別の値の数をカウントしてから、「サンプリングベースの推定」の方法の1つを使用して、マルチセット全体の値の数を推定するか、あなたの事前の知識は、見積もりを計算するためにマルチセットの分布に隣接しています（おそらく、偽造者の印刷機を見たことがあり、それが1つのシリアル番号しか印刷できないことを知っています）
引用検索は素晴らしいものです。私は提起された 2 つの問題にあまり詳しくないので、この論文はあなたが意図したとおりではないかもしれません。少なくとも彼らは確かに HyperLogLog とその問題との関係について話しているので、おそらくあなたの好奇心を満たしてくれるでしょう。