From: Steven Baltakatei Sandoval <baltakatei@gmail.com> Date: Tue, 14 Feb 2023 13:27:57 +0000 (+0000) Subject: feat(doc/up/bkshuf/):Add TeXmacs documentation X-Git-Tag: 0.8.1~10 X-Git-Url: https://zdv2.bktei.com/gitweb/BK-2020-03.git/commitdiff_plain/080ea4c0ff0d4e6b5ce86f664fa6645c1cb02bf0?ds=inline;hp=-c feat(doc/up/bkshuf/):Add TeXmacs documentation - Note: Compiled PDF uploaded to: https://reboil.com/res/2023/txt/20230214T1327+00..bkshuf_article.pdf --- 080ea4c0ff0d4e6b5ce86f664fa6645c1cb02bf0 diff --git a/doc/unitproc/bkshuf/article.tm b/doc/unitproc/bkshuf/article.tm new file mode 100644 index 0000000..0030c11 --- /dev/null +++ b/doc/unitproc/bkshuf/article.tm @@ -0,0 +1,374 @@ +<TeXmacs|2.1.1> + +<style|generic> + +<\body> + <doc-data|<doc-title|bkshuf: A Shuf-Like Utility with Pre-Image Resistance + and Relative Order Preservation for Random Sampling of Long + Lists>|<doc-author|<author-data|<author-name|Steven Baltakatei + Sandoval>>>|<doc-date|2023-02-14>> + + <section|Summary> + + <shell|bkshuf> is a <shell|shuf>-like utility designed to output randomly + sized groups of lines with a group size distribution centered around some + characteristic value. + + <section|Objective> + + The author desires to create a <shell|shuf>-like utility named + <shell|bkshuf> to mix line lists in order to produce output line lists with + the following somewhat conflicting properties: + + <\description> + <item*|Pre-image resistance (PIR)>An output line's position should not + contain information about its input line position. + + <item*|Relative order preservation (ROP)>Two neighboring lines in the + input stream should have a high probability of remaining neighbors in the + output stream. + </description> + + The objective is to improve the value of a short random scan of a small + fraction of a potentially large input list; output that demonstrates ROP as + well as some degree of PIR may achieve this objective. In contrast, the + <shell|shuf> utility provides PIR but no ROP: a line's neighbor in the + output of <shell|shuf> is equally likely to be any other random line from + the input.\ + + In other words, output produced by <shell|bkshuf> should group together + sequential segments of the input lines in order to partially preserve + relationships that may exist between sequential files. For example, this + could be done by jumping to a random position in the input lines, consuming + (i.e. reading, outputting, and marking a line not to be read again) some + amount of sequential lines, then repeating the process until every line is + consumed. The amount of sequential lines to read between jumps affects how + well the above desired properties are satisfied. + + The objective of <shell|bkshuf> is not to completely prevent the + possibility of reassembling the input given the output. Additionally, a + valuable property desired of <shell|bkshuf> is output which demonstrates + sufficiently high PIR compared to ROP such that only a short (compared to + the logarithm of the input list size) sequential scan of the output list + from a random starting position is required before a jump to a new group is + is encountered; this would permit the overal contents of very large input + line lists to be sampled. + + <section|Design> + + <subsection|Definitions> + + <\eqnarray*> + <tformat|<table|<row|<cell|l>|<cell|:>|<cell|<text|number of + lines>>>|<row|<cell|l<rsub|<text|in>>>|<cell|:>|<cell|<text|input line + count>>>|<row|<cell|l<rsub|<text|out>>>|<cell|:>|<cell|<text|output line + count>>>|<row|<cell|c>|<cell|:>|<cell|<text|target group + count>>>|<row|<cell|s>|<cell|:>|<cell|<text|target group + size>>>|<row|<cell|p<rsub|<text|seq>><rsub|<text|>>>|<cell|:>|<cell|<text|probability + to include next sequential line>>>|<row|<cell|s<around*|(|l<rsub|<text|in>,0>|)>>|<cell|:>|<cell|<text|<math|target + group size parameter>>>>|<row|<cell|l<rsub|<text|in>,0>>|<cell|:>|<cell|<text|input + line count parameter>>>>> + </eqnarray*> + + <subsection|Process> + + <\enumerate-numeric> + <item>Acquire and count input lines (via <shell|/dev/stdin> or positional + arguments). + + <item>Calculate line count <math|l<rsub|<text|in>>> . + + <item>Calculate target group size <math|s>. + + <item>Select random unconsumed input line and consume it to + output.<label|jump-to-random> + + <item>Consume the next sequential line with probability + <math|p<rsub|<text|seq>>>. Otherwise if some input lines remain + unconsumed, go to step <reference|jump-to-random>. Otherwise, exit. + </enumerate-numeric> + + <subsection|Parameter analysis> + + <subsubsection|Target group size calculation> + + The simultaneous presence of ROP and PIR properties in the output depends + upon the amount of sequential lines that are read before <shell|bkshuf> + jumps to a new random position in the input list. This amount is the + <em|target group size>, <math|s>; it is the \Ptarget\Q since <math|s> + represents the average of a distribution of group sizes that may be + selected, not a single group size. In this analysis, the total number of + lines in the input list is <math|l<rsub|<text|in>>>. For small input line + counts, (e.g. <math|l<rsub|<text|in>>\<cong\>10>) the target group size + should be nearly one (e.g. <math|s\<cong\>1>) since group sizes any larger + than this would have almost no PIR (e.g. a group size of <math|s=8> for + <math|l<rsub|<text|in>>=10> would be 80% identical to the input). For + modest line input counts (e.g. <math|l<rsub|<text|in>>\<cong\>100>), the + target group size may be allowed to be larger, such as a tenth of the input + line count (e.g. <math|s\<cong\>10>); this would provide some PIR + (approximately <math|10!> permutations between the approximately + <math|<frac|l<rsub|<text|in>>|s>\<cong\><frac|100|10>\<cong\>10> groups) + while each line in groups around size <math|10> would have a low + probability of not being next to its neighbor (<math|8> of the 10 lines + would retain the same two neighbors while the two ends would retain one + each). For very large input line counts (e.g. + <math|l<rsub|<text|in>>\<cong\>1<separating-space|0.2em>000<separating-space|0.2em>000>), + however, breaking up and randomizing the input into ten groups of + <math|100<separating-space|0.2em>000> offers very little PIR; the benefit + of the very high ROP is also lost since sequential scanning of tens of + thousands of lines is required before a random jump to a new group may be + encountered; therefore, the target group size should be a much smaller + fraction of <math|l<rsub|<text|in>>>, (e.g. <math|s\<cong\>20>) while still + increasing. The relationship between a desireable target group size + <math|s> and the input line count <math|l<rsub|<text|in>>> is non-linear. + The author believes a reasonable approach is to scale the group size to the + logarithm of input line count. + + <hgroup|Figure <reference|fig ex-plot-s>> shows an example plot of + <math|s<around*|(|l<rsub|<text|in>>|)>> that is tuned to achieve a target + group size of <math|s<around*|(|l<rsub|<text|in>>=10<rsup|6>|)>=25> for an + input list length of <math|l<rsub|<text|in>>=10<rsup|6>> lines.\ + + <\big-figure|<with|gr-mode|<tuple|edit|point>|gr-frame|<tuple|scale|1.18922cm|<tuple|0.299593gw|0.120812gh>>|gr-geometry|<tuple|geometry|1par|0.6par>|gr-grid|<tuple|cartesian|<point|0|0>|1>|gr-grid-old|<tuple|cartesian|<point|0|0>|1>|gr-edit-grid-aspect|<tuple|<tuple|axes|none>|<tuple|1|none>|<tuple|10|none>>|gr-edit-grid|<tuple|cartesian|<point|0|0>|1>|gr-edit-grid-old|<tuple|cartesian|<point|0|0>|1>|gr-grid-aspect-props|<tuple|<tuple|axes|#808080>|<tuple|1|#c0c0c0>|<tuple|10|pastel + blue>>|gr-grid-aspect|<tuple|<tuple|axes|#808080>|<tuple|1|#c0c0c0>|<tuple|10|pastel + blue>>|magnify|1.18920711463847|gr-auto-crop|false|<graphics||<math-at|5|<point|-0.221848749616356|1.0>>|<math-at|10|<point|-0.397940008672038|2.0>>|<math-at|15|<point|-0.397940008672038|3.0>>|<math-at|20|<point|-0.397940008672038|4.0>>|<math-at|25|<point|-0.397940008672038|5.0>>|<math-at|30|<point|-0.397940008672038|6.0>>|<math-at|s|<point|0.0719460474170896|6.34360008343183>>|<point|0|0.2>|<point|6|5>|<math-at|10<rsup|1>|<point|1.0|-0.4>>|<math-at|10<rsup|2>|<point|2.0|-0.4>>|<math-at|10<rsup|3>|<point|3.0|-0.4>>|<math-at|10<rsup|4>|<point|4.0|-0.4>>|<math-at|10<rsup|5>|<point|5.0|-0.4>>|<math-at|10<rsup|6>|<point|6.0|-0.4>>|<math-at|1|<point|1.0|-0.8>>|<math-at|2|<point|2.0|-0.8>>|<math-at|3|<point|3.0|-0.8>>|<math-at|4|<point|4.0|-0.8>>|<math-at|5|<point|5.0|-0.8>>|<math-at|6|<point|6.0|-0.8>>|<math-at|x|<point|7.0|-0.8>>|<math-at|l<rsub|<text|in>>|<point|7.0|-0.4>>|<point|5.0|3.5>|<point|4.0|2.3>|<point|3.0|1.4>|<point|2.0|0.7>|<point|1.0|0.3>>>> + <label|fig ex-plot-s>A plot of a possible function that relates target + group size <math|s> and input lines <math|l<rsub|<text|in>>> that provide + some ROP and PIR. The function is tuned to achieve + <math|s<around*|(|l<rsub|<text|in>>=10<rsup|6>|)>=25>.\ + </big-figure> + + The following is a set of equations that are used to derive a definition + for <math|s<around*|(|l<rsub|<text|in>>|)>> that satisfies the plot in + <hgroup|Figure <reference|fig ex-plot-s>>.\ + + <\eqnarray*> + <tformat|<table|<row|<cell|x>|<cell|=>|<cell|<text|log> + <around*|(|l<rsub|<text|in>>|)>=<frac|ln + <around*|(|l<rsub|<text|in>>|)>|<text|ln> + <around*|(|10|)>><eq-number><label|eq + rel-x-lin>>>|<row|<cell|10<rsup|x>>|<cell|=>|<cell|l<rsub|<text|in>>>>|<row|<cell|x<rsub|0>>|<cell|=>|<cell|<text|log> + <around*|(|l<rsub|<text|in>,0>|)>=<frac|ln + <around*|(|l<rsub|<text|in>,0>|)>|<text|ln> + <around*|(|10|)>><eq-number><label|eq + rel-x0-lin0>>>|<row|<cell|10<rsup|x<rsub|0>>>|<cell|=>|<cell|l<rsub|<text|in>,0>>>|<row|<cell|>|<cell|>|<cell|>>|<row|<cell|s<around*|(|x|)>>|<cell|=>|<cell|<around*|(|k**x|)><rsup|2>+1<eq-number><label|eq + gsize-model>>>|<row|<cell|s<around*|(|x=6|)>=25>|<cell|=>|<cell|k<rsup|2>\<cdot\><around*|(|6|)><rsup|2>+1>>|<row|<cell|25>|<cell|=>|<cell|k<rsup|2>\<cdot\><around*|(|36|)>+1>>|<row|<cell|s<around*|(|x<rsub|0>|)>>|<cell|=>|<cell|<around*|(|k*x<rsub|0>|)><rsup|2>+1<eq-number><label|eq + gsize-param-rel>>>|<row|<cell|<frac|s<around*|(|x<rsub|0>|)>-1|x<rsub|0><rsup|2>>>|<cell|=>|<cell|k<rsup|2>>>|<row|<cell|k>|<cell|=>|<cell|<sqrt|<frac|s<around*|(|x<rsub|0>|)>-1|x<rsub|0><rsup|2>>>>>|<row|<cell|k>|<cell|=>|<cell|<frac|<sqrt|s<around*|(|x<rsub|0>|)>-1>|x<rsub|0>>>>|<row|<cell|k<rsup|2>>|<cell|=>|<cell|<frac|s<around*|(|x<rsub|0>|)>-1|x<rsub|0><rsup|2>><eq-number><label|eq + gsize-const-ksq>>>|<row|<cell|s<around*|(|l<rsub|<text|in>>|)>>|<cell|=>|<cell|<around*|(|<frac|s<around*|(|x<rsub|0>|)>-1|x<rsub|0><rsup|2>>|)>\<cdot\><around*|(|<frac|<text|ln><around*|(|l<rsub|<text|in>>|)>|<text|ln> + <around*|(|10|)>>|)><rsup|2>+1>>|<row|<cell|>|<cell|=>|<cell|<around*|(|<frac|<text|ln> + <around*|(|10|)>|ln <around*|(|l<rsub|<text|in>,0>|)>>|)><rsup|2>\<cdot\><around*|(|s<around*|(|x<rsub|0>|)>-1|)>\<cdot\><around*|(|<frac|<text|ln><around*|(|l<rsub|<text|in>>|)>|<text|ln> + <around*|(|10|)>>|)><rsup|2>+1>>|<row|<cell|s<around*|(|l<rsub|<text|in>>|)>>|<cell|=>|<cell|<around*|(|s<around*|(|l<rsub|<text|in>,0>|)>-1|)>\<cdot\><around*|(|<frac|<text|ln><around*|(|l<rsub|<text|in>>|)>|ln + <around*|(|l<rsub|<text|in>,0>|)>>|)><rsup|2>+1>>|<row|<cell|s<around*|(|l<rsub|<text|in>>|)>>|<cell|=>|<cell|<around*|(|<frac|s<around*|(|l<rsub|<text|in>,0>|)>-1|<around*|[|ln + <around*|(|l<rsub|<text|in>,0>|)>|]><rsup|2>>|)>\<cdot\><around*|[|<text|ln><around*|(|l<rsub|<text|in>>|)>|]><rsup|2>+1<eq-number><label|eq + gsize-lin>>>>> + </eqnarray*> + + Equation <reference|eq gsize-model> defines a quadratic equation for the + linear range <math|s> and the logarithmic domain <math|x>. <math|x> is + defined in terms of <math|l<rsub|<text|in>>> via a domain transformation + defined by <hgroup|Equation <reference|eq rel-x-lin>>. The result is + <hgroup|Equation <reference|eq gsize-lin>> which defines + <math|s<around*|(|l<rsub|<text|in>>|)>> as a function of + <math|l<rsub|<text|in>>> and parameters + <math|s<around*|(|l<rsub|<text|in>,0>|)>> and <math|l<rsub|<text|in>,0>>. + The parameters define how quickly or slowly the quadratic equation grows. + In other words, if a user wishes for a <math|1<separating-space|0.2em>000<separating-space|0.2em>000> + line input to be split into groups each containing, on average, <math|25> + lines, then they should plug in <math|l<rsub|<text|in>,0>=1<separating-space|0.2em>000<separating-space|0.2em>000> + and <math|s<around*|(|l<rsub|<text|in>,0>|)>=25> into <hgroup|Equation + <reference|eq gsize-lin>> as is done in <hgroup|Equation <reference|eq + gsize-ex-1>>. This equation can then be used to calculate target group + sizes <math|s> as a function of other input line counts + <math|l<rsub|<text|in>>> besides <math|l<rsub|<text|in>>=1<separating-space|0.2em>000<separating-space|0.2em>000>. + For example, plugging <math|l<rsub|<text|in>>=500> into <hgroup|Equation + <reference|eq gsize-ex-1>> yields <hgroup|Equation <reference|eq + gsize-ex-1-lin500>> which specifies a target group size of + <math|5.85629\<cong\>6>. + + <\eqnarray*> + <tformat|<table|<row|<cell|s<around*|(|l<rsub|<text|in>>|)>>|<cell|=>|<cell|<around*|(|<frac|s<around*|(|l<rsub|<text|in>,0>|)>-1|<around*|[|ln + <around*|(|l<rsub|<text|in>,0>|)>|]><rsup|2>>|)>\<cdot\><around*|[|<text|ln><around*|(|l<rsub|<text|in>>|)>|]><rsup|2>+1>>|<row|<cell|s<around*|(|l<rsub|<text|in>>|)>>|<cell|=>|<cell|<around*|(|<frac|25-1|<around*|[|<text|ln + ><around*|(|1<separating-space|0.2em>000<separating-space|0.2em>000|)>|]><rsup|2>>|)>\<cdot\><around*|[|<text|ln><around*|(|l<rsub|<text|in>>|)>|]><rsup|2>+1<eq-number><label|eq + gsize-ex-1>>>|<row|<cell|>|<cell|>|<cell|>>|<row|<cell|s<around*|(|l<rsub|<text|in>>=500|)>>|<cell|=>|<cell|<around*|(|<frac|25-1|<around*|[|<text|ln + ><around*|(|1<separating-space|0.2em>000<separating-space|0.2em>000|)>|]><rsup|2>>|)>\<cdot\><around*|[|<text|ln><around*|(|500|)>|]><rsup|2>+1<eq-number><label|eq + gsize-ex-1-lin500>>>|<row|<cell|s<around*|(|l<rsub|<text|in>>=500|)>>|<cell|=>|<cell|5.85629>>>> + </eqnarray*> + + \; + + <subsubsection|Jump from expected value> + + A method <shell|bkshuf> may employ to decide when read the next sequential + unconsumed input line is to simply do so with probability + <math|p<rsub|<text|seq>>> such that the expected value of the average group + size trends towards <math|s>. + + <\eqnarray*> + <tformat|<table|<row|<cell|p<rsub|<text|seq>>>|<cell|=>|<cell|<around*|(|1-p<rsub|<text|jump>>|)>>>|<row|<cell|p<rsub|<text|jump>>>|<cell|=>|<cell|1-p<rsub|<text|seq>>>>|<row|<cell|s>|<cell|=>|<cell|<frac|1|p<rsub|<text|jump>>>=<frac|1|1-p<rsub|<text|seq>>><eq-number>>>|<row|<cell|s>|<cell|=>|<cell|<frac|1|1-p<rsub|<text|seq>>>>>|<row|<cell|1-p<rsub|<text|seq>>>|<cell|=>|<cell|<frac|1|s>>>|<row|<cell|p<rsub|<text|seq>>-1>|<cell|=>|<cell|<frac|-1|s>>>|<row|<cell|p<rsub|<text|seq>>>|<cell|=>|<cell|1-<frac|1|s<around*|(|l<rsub|<text|in>>|)>><eq-number><inactive|<label|eq + pseq-from-s-lin>>>>|<row|<cell|p<rsub|<text|jump>>>|<cell|=>|<cell|<frac|1|s<around*|(|l<rsub|<text|in>>|)>><eq-number><inactive|<label|eq + pjump-from-s-lin>>>>|<row|<cell|>|<cell|>|<cell|>>|<row|<cell|p<rsub|<text|seq>><around*|(|l<rsub|<text|in>>|)>>|<cell|=>|<cell|1-<around*|[|<around*|(|<frac|s<around*|(|l<rsub|<text|in>,0>|)>-1|<around*|[|ln + <around*|(|l<rsub|<text|in>,0>|)>|]><rsup|2>>|)>\<cdot\><around*|[|<text|ln><around*|(|l<rsub|<text|in>>|)>|]><rsup|2>+1|]><rsup|-1><eq-number><inactive|<label|eq + pseq-from-s-lin-exp>>>>>> + </eqnarray*> + + <subsubsection|Jump from random variate of inverse gaussian distribution> + + Another method <shell|bkshuf> may employ to decide when to read the next + sequential unconsumed input line is to use an inverse gaussian + distribution. This may be done by generating from the distribution a float + sampled from the inverse gaussian with range 0 to infinity with mean + <math|\<mu\>> whenever a new random position in the input list is selected; + the float is rounded to the nearest integer.<\footnote> + See <name|Michael, John R.> "Generating Random Variates Using + Transformations with Multiple Roots". 1976. + <hlink|https://doi.org/10.2307/2683801|https://doi.org/10.2307/2683801> . + </footnote> Then, after consuming an input line, this integer is + decremented by one and another sequential line is consumed provided the + integer does not become less than or equal to zero. The inverse gaussian + distribution requires specifying the mean <math|\<mu\>> and the shape + parameter <math|\<lambda\>>; a higher <math|\<lambda\>> results in a + greater spread. An upper bound may also be specified since the distribution + has none except for that imposed by its programming implementation. + + The result of using an inverse gaussian distribution is an output with + potentially much more regular group sizes than using the previously + mentioned expected value method. However, the implementation of the inverse + gaussian sampling operation described by (Michael, 1976) requires several + exponent calculations and a square root calculation in addition to various + multiplication and division operations. If sufficient processing power is + available, this may not necessarily be an issue. + + <subsubsection|Output structure> + + Regardless of whether group sizes are determined by the expected value + method or using variates of an inverse gaussian distribution, mimicking the + <shell|shuf> property of all input lines being present in the output, + albeit rearranged, results in a side effect: the first output lines are + more likely to contain groups with uninterrupted sequence runs (high ROP) + while groups in the last output lines are almost certain to contain + sequence jumps within a group (less ROP). The reason for this is that + <shell|bkshuf>, when it encounters an input line that has already been + consumed, will skip to the next available input line. The decision could be + made to skip to a new random line, but, it is simpler to simply read the + next available input line. The author's original intention of sampling only + a short initial portion of the output is compatible with the behavior that + ROP is preserved mostly at the beginning of the output. + + <section|Version History> + + <\big-table|<tabular|<tformat|<table|<row|<cell|Version + No.>|<cell|Date>|<cell|Path>|<cell|Description>>|<row|<cell|<verbatim|0.0.1>>|<cell|2023-02-14>|<cell|<verbatim|unitproc/bkshuf>>|<cell|Initial + draft implemented in <name|Bash>.>>>>>> + A table listing versions of <shell|bkshuf>. + </big-table> + + <\description> + <item*|v0.0.1>Initial implementation in <shell|bash> <verbatim|5.1.16> + with <shell|bc> <verbatim|1.07.1> and <name|GNU Coreutils> + <verbatim|8.32> and tested on <name|Pop!_OS> <verbatim|22.04 LTS>. Saved + to the author's <name|BK-2020-03> repository<\footnote> + See commit <verbatim|22772fe> at <hlink|https://gitlab.com/baltakatei/baltakatei-exdev|https://gitlab.com/baltakatei/baltakatei-exdev> + . + </footnote>. + </description> +</body> + +<initial|<\collection> +</collection>> + +<\references> + <\collection> + <associate|auto-1|<tuple|1|?|../../../../../wr/20230213..bkshuf_draft/src/doc.tm>> + <associate|auto-10|<tuple|3.3.3|?|../../../../../wr/20230213..bkshuf_draft/src/doc.tm>> + <associate|auto-11|<tuple|3.3.4|?|../../../../../wr/20230213..bkshuf_draft/src/doc.tm>> + <associate|auto-12|<tuple|4|?|../../../../../wr/20230213..bkshuf_draft/src/doc.tm>> + <associate|auto-13|<tuple|1|?|../../../../../wr/20230213..bkshuf_draft/src/doc.tm>> + <associate|auto-14|<tuple|1|?|../../../../../wr/20230213..bkshuf_draft/src/doc.tm>> + <associate|auto-2|<tuple|2|?|../../../../../wr/20230213..bkshuf_draft/src/doc.tm>> + <associate|auto-3|<tuple|3|?|../../../../../wr/20230213..bkshuf_draft/src/doc.tm>> + <associate|auto-4|<tuple|3.1|?|../../../../../wr/20230213..bkshuf_draft/src/doc.tm>> + <associate|auto-5|<tuple|3.2|?|../../../../../wr/20230213..bkshuf_draft/src/doc.tm>> + <associate|auto-6|<tuple|3.3|?|../../../../../wr/20230213..bkshuf_draft/src/doc.tm>> + <associate|auto-7|<tuple|3.3.1|?|../../../../../wr/20230213..bkshuf_draft/src/doc.tm>> + <associate|auto-8|<tuple|1|?|../../../../../wr/20230213..bkshuf_draft/src/doc.tm>> + <associate|auto-9|<tuple|3.3.2|?|../../../../../wr/20230213..bkshuf_draft/src/doc.tm>> + <associate|eq gsize-const-ksq|<tuple|5|?|../../../../../wr/20230213..bkshuf_draft/src/doc.tm>> + <associate|eq gsize-ex-1|<tuple|7|?|../../../../../wr/20230213..bkshuf_draft/src/doc.tm>> + <associate|eq gsize-ex-1-lin500|<tuple|8|?|../../../../../wr/20230213..bkshuf_draft/src/doc.tm>> + <associate|eq gsize-lin|<tuple|6|?|../../../../../wr/20230213..bkshuf_draft/src/doc.tm>> + <associate|eq gsize-model|<tuple|3|?|../../../../../wr/20230213..bkshuf_draft/src/doc.tm>> + <associate|eq gsize-param-rel|<tuple|4|?|../../../../../wr/20230213..bkshuf_draft/src/doc.tm>> + <associate|eq rel-x-lin|<tuple|1|?|../../../../../wr/20230213..bkshuf_draft/src/doc.tm>> + <associate|eq rel-x0-lin0|<tuple|2|?|../../../../../wr/20230213..bkshuf_draft/src/doc.tm>> + <associate|fig ex-plot-s|<tuple|1|?|../../../../../wr/20230213..bkshuf_draft/src/doc.tm>> + <associate|footnote-1|<tuple|1|?|../../../../../wr/20230213..bkshuf_draft/src/doc.tm>> + <associate|footnote-2|<tuple|2|?|../../../../../wr/20230213..bkshuf_draft/src/doc.tm>> + <associate|footnr-1|<tuple|1|?|../../../../../wr/20230213..bkshuf_draft/src/doc.tm>> + <associate|footnr-2|<tuple|2|?|../../../../../wr/20230213..bkshuf_draft/src/doc.tm>> + <associate|jump-to-random|<tuple|4|?|../../../../../wr/20230213..bkshuf_draft/src/doc.tm>> + </collection> +</references> + +<\auxiliary> + <\collection> + <\associate|figure> + <tuple|normal|<\surround|<hidden-binding|<tuple>|1>|> + A plot of a possible function that relates target group size + <with|mode|<quote|math>|s> and input lines + <with|mode|<quote|math>|l<rsub|<with|mode|<quote|text>|in>>> that + provide some ROP and PIR. The function is tuned to achieve + <with|mode|<quote|math>|s<around*|(|l<rsub|<with|mode|<quote|text>|in>>=10<rsup|6>|)>=25>. + </surround>|<pageref|auto-8>> + </associate> + <\associate|table> + <tuple|normal|<\surround|<hidden-binding|<tuple>|1>|> + \; + </surround>|<pageref|auto-13>> + </associate> + <\associate|toc> + <vspace*|1fn><with|font-series|<quote|bold>|math-font-series|<quote|bold>|1<space|2spc>Summary> + <datoms|<macro|x|<repeat|<arg|x>|<with|font-series|medium|<with|font-size|1|<space|0.2fn>.<space|0.2fn>>>>>|<htab|5mm>> + <no-break><pageref|auto-1><vspace|0.5fn> + + <vspace*|1fn><with|font-series|<quote|bold>|math-font-series|<quote|bold>|2<space|2spc>Objective> + <datoms|<macro|x|<repeat|<arg|x>|<with|font-series|medium|<with|font-size|1|<space|0.2fn>.<space|0.2fn>>>>>|<htab|5mm>> + <no-break><pageref|auto-2><vspace|0.5fn> + + <vspace*|1fn><with|font-series|<quote|bold>|math-font-series|<quote|bold>|3<space|2spc>Design> + <datoms|<macro|x|<repeat|<arg|x>|<with|font-series|medium|<with|font-size|1|<space|0.2fn>.<space|0.2fn>>>>>|<htab|5mm>> + <no-break><pageref|auto-3><vspace|0.5fn> + + <with|par-left|<quote|1tab>|3.1<space|2spc>Definitions + <datoms|<macro|x|<repeat|<arg|x>|<with|font-series|medium|<with|font-size|1|<space|0.2fn>.<space|0.2fn>>>>>|<htab|5mm>> + <no-break><pageref|auto-4>> + + <with|par-left|<quote|1tab>|3.2<space|2spc>Process + <datoms|<macro|x|<repeat|<arg|x>|<with|font-series|medium|<with|font-size|1|<space|0.2fn>.<space|0.2fn>>>>>|<htab|5mm>> + <no-break><pageref|auto-5>> + + <with|par-left|<quote|1tab>|3.3<space|2spc>Parameter analysis + <datoms|<macro|x|<repeat|<arg|x>|<with|font-series|medium|<with|font-size|1|<space|0.2fn>.<space|0.2fn>>>>>|<htab|5mm>> + <no-break><pageref|auto-6>> + + <with|par-left|<quote|2tab>|3.3.1<space|2spc>Target group size + calculation <datoms|<macro|x|<repeat|<arg|x>|<with|font-series|medium|<with|font-size|1|<space|0.2fn>.<space|0.2fn>>>>>|<htab|5mm>> + <no-break><pageref|auto-7>> + + <with|par-left|<quote|2tab>|3.3.2<space|2spc>Jump from expected value + <datoms|<macro|x|<repeat|<arg|x>|<with|font-series|medium|<with|font-size|1|<space|0.2fn>.<space|0.2fn>>>>>|<htab|5mm>> + <no-break><pageref|auto-9>> + + <with|par-left|<quote|2tab>|3.3.3<space|2spc>Jump from random variate + of inverse gaussian distribution <datoms|<macro|x|<repeat|<arg|x>|<with|font-series|medium|<with|font-size|1|<space|0.2fn>.<space|0.2fn>>>>>|<htab|5mm>> + <no-break><pageref|auto-10>> + + <with|par-left|<quote|2tab>|3.3.4<space|2spc>Output structure + <datoms|<macro|x|<repeat|<arg|x>|<with|font-series|medium|<with|font-size|1|<space|0.2fn>.<space|0.2fn>>>>>|<htab|5mm>> + <no-break><pageref|auto-11>> + + <vspace*|1fn><with|font-series|<quote|bold>|math-font-series|<quote|bold>|4<space|2spc>Version + History> <datoms|<macro|x|<repeat|<arg|x>|<with|font-series|medium|<with|font-size|1|<space|0.2fn>.<space|0.2fn>>>>>|<htab|5mm>> + <no-break><pageref|auto-12><vspace|0.5fn> + </associate> + </collection> +</auxiliary> \ No newline at end of file