📅 Original date posted:2018-05-30
📝 Original message:Hi Jim,
Yes please, could you share CSV? We are developing a Wallet that uses
Golomb-Rice filters it would help a lot for determine the best P value
depending on the estimated number of elements the client needs to watch.
2018-05-29 19:38 GMT-03:00 Jim Posen via bitcoin-dev <
bitcoin-dev at lists.linuxfoundation.org>:
> This is a really cool finding, thanks Pieter!
>
> I did some more analysis on selecting a good P value to reduce total data
> downloaded considering both filters themselves and blocks in the case of
> false positive matches, using data from mainnet. The quantity it minimizes
> is:
>
> filter_size(N, B) + block_size * false_positive_probability(C, N, B)
>
> N is the number of filter elements per block
> B is the Golomb-Rice coding parameter
> C is the number of filter elements watched by the client
>
> The main result is that:
>
> For C = 10, B = 13 is optimal
> For C = 100, B = 16 is optimal
> For C = 1,000, B = 20 is optimal
> For C = 10,000, B = 23 is optimal
>
> So any value of B in the range 16 to 20 seems reasonable, with M = 1.4971
> * 2^B for optimal compression, as Pieter derived. The selection of the
> parameter depends on the target number of elements that a client may watch.
>
> I attached some of the results, and would be happy to share the CSV and
> raw notebook if people are interested.
>
>
> On Fri, May 25, 2018 at 2:14 PM Gregory Maxwell via bitcoin-dev <
> bitcoin-dev at lists.linuxfoundation.org> wrote:
>
>> On Fri, May 25, 2018 at 6:42 PM, Gregory Maxwell <greg at xiph.org> wrote:
>> > configuration is roughly right, then M=1569861 and rice parameter 19
>> > should be used.
>>
>> That should have been M=784931 B=19 ... paste error.
>> _______________________________________________
>> bitcoin-dev mailing list
>> bitcoin-dev at lists.linuxfoundation.org
>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>>
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20180530/e1679c4d/attachment.html>;
Lucas Ontivero [ARCHIVE] /
npub16q…gqufk
2023-06-07 18:12:30
in reply to nevent1q…m9le
Author Public Key
npub16q9ngejhxtupvrmnmcrhdqag5dcgfyxvc5mhequv4w7637xvp3ss7gqufkPublished at
2023-06-07 18:12:30Event JSON
{
"id": "e1108c8b0b751bae9997f16c84eb5bb8bb1f0ed99e24996e8e1f8a20b04d5aee",
"pubkey": "d00b34665732f8160f73de077683a8a3708490ccc5377c838cabbda8f8cc0c61",
"created_at": 1686161550,
"kind": 1,
"tags": [
[
"e",
"1fb299cd51cda0be4ef64f1bb0e47ab3eddd2a29a6e21aa9760ff086cb48ddfb",
"",
"root"
],
[
"e",
"a1d3237636e7389fa524c6e41429706e2ab9cf73ff470d1583b5ddad4b1eee84",
"",
"reply"
],
[
"p",
"9e2723f47c6c16d3093735bd6acdc8b0dd1b91c78216f7001bdd2f7562b69ed1"
]
],
"content": "📅 Original date posted:2018-05-30\n📝 Original message:Hi Jim,\n\nYes please, could you share CSV? We are developing a Wallet that uses\nGolomb-Rice filters it would help a lot for determine the best P value\ndepending on the estimated number of elements the client needs to watch.\n\n2018-05-29 19:38 GMT-03:00 Jim Posen via bitcoin-dev \u003c\nbitcoin-dev at lists.linuxfoundation.org\u003e:\n\n\u003e This is a really cool finding, thanks Pieter!\n\u003e\n\u003e I did some more analysis on selecting a good P value to reduce total data\n\u003e downloaded considering both filters themselves and blocks in the case of\n\u003e false positive matches, using data from mainnet. The quantity it minimizes\n\u003e is:\n\u003e\n\u003e filter_size(N, B) + block_size * false_positive_probability(C, N, B)\n\u003e\n\u003e N is the number of filter elements per block\n\u003e B is the Golomb-Rice coding parameter\n\u003e C is the number of filter elements watched by the client\n\u003e\n\u003e The main result is that:\n\u003e\n\u003e For C = 10, B = 13 is optimal\n\u003e For C = 100, B = 16 is optimal\n\u003e For C = 1,000, B = 20 is optimal\n\u003e For C = 10,000, B = 23 is optimal\n\u003e\n\u003e So any value of B in the range 16 to 20 seems reasonable, with M = 1.4971\n\u003e * 2^B for optimal compression, as Pieter derived. The selection of the\n\u003e parameter depends on the target number of elements that a client may watch.\n\u003e\n\u003e I attached some of the results, and would be happy to share the CSV and\n\u003e raw notebook if people are interested.\n\u003e\n\u003e\n\u003e On Fri, May 25, 2018 at 2:14 PM Gregory Maxwell via bitcoin-dev \u003c\n\u003e bitcoin-dev at lists.linuxfoundation.org\u003e wrote:\n\u003e\n\u003e\u003e On Fri, May 25, 2018 at 6:42 PM, Gregory Maxwell \u003cgreg at xiph.org\u003e wrote:\n\u003e\u003e \u003e configuration is roughly right, then M=1569861 and rice parameter 19\n\u003e\u003e \u003e should be used.\n\u003e\u003e\n\u003e\u003e That should have been M=784931 B=19 ... paste error.\n\u003e\u003e _______________________________________________\n\u003e\u003e bitcoin-dev mailing list\n\u003e\u003e bitcoin-dev at lists.linuxfoundation.org\n\u003e\u003e https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev\n\u003e\u003e\n\u003e\n\u003e _______________________________________________\n\u003e bitcoin-dev mailing list\n\u003e bitcoin-dev at lists.linuxfoundation.org\n\u003e https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev\n\u003e\n\u003e\n-------------- next part --------------\nAn HTML attachment was scrubbed...\nURL: \u003chttp://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20180530/e1679c4d/attachment.html\u003e",
"sig": "c86e33d8fc8648f577ea81869c7d6936ff0f4c40172ffea5a189196abe0e3ce6784ce4c3e1a77b94a4a2235bfee9dacd303babc5a9b7798d326c6c19fc9c3cd1"
}