[BK-2020-03.git] / doc / unitproc / bkshuf / article.tm

<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-14T13:48+00>|<doc-misc|CC BY-SA 4.0>>

  <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 <hlink|<verbatim|080ea4c>|https://gitlab.com/baltakatei/baltakatei-exdev/-/blob/080ea4c0ff0d4e6b5ce86f664fa6645c1cb02bf0/unitproc/bkshuf>
      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|1|../../../../../wr/20230213..bkshuf_draft/src/doc.tm>>
    <associate|auto-10|<tuple|3.3.3|4|../../../../../wr/20230213..bkshuf_draft/src/doc.tm>>
    <associate|auto-11|<tuple|3.3.4|5|../../../../../wr/20230213..bkshuf_draft/src/doc.tm>>
    <associate|auto-12|<tuple|4|5|../../../../../wr/20230213..bkshuf_draft/src/doc.tm>>
    <associate|auto-13|<tuple|1|5|../../../../../wr/20230213..bkshuf_draft/src/doc.tm>>
    <associate|auto-14|<tuple|1|?|../../../../../wr/20230213..bkshuf_draft/src/doc.tm>>
    <associate|auto-2|<tuple|2|1|../../../../../wr/20230213..bkshuf_draft/src/doc.tm>>
    <associate|auto-3|<tuple|3|1|../../../../../wr/20230213..bkshuf_draft/src/doc.tm>>
    <associate|auto-4|<tuple|3.1|1|../../../../../wr/20230213..bkshuf_draft/src/doc.tm>>
    <associate|auto-5|<tuple|3.2|2|../../../../../wr/20230213..bkshuf_draft/src/doc.tm>>
    <associate|auto-6|<tuple|3.3|2|../../../../../wr/20230213..bkshuf_draft/src/doc.tm>>
    <associate|auto-7|<tuple|3.3.1|2|../../../../../wr/20230213..bkshuf_draft/src/doc.tm>>
    <associate|auto-8|<tuple|1|3|../../../../../wr/20230213..bkshuf_draft/src/doc.tm>>
    <associate|auto-9|<tuple|3.3.2|4|../../../../../wr/20230213..bkshuf_draft/src/doc.tm>>
    <associate|eq gsize-const-ksq|<tuple|5|3|../../../../../wr/20230213..bkshuf_draft/src/doc.tm>>
    <associate|eq gsize-ex-1|<tuple|7|4|../../../../../wr/20230213..bkshuf_draft/src/doc.tm>>
    <associate|eq gsize-ex-1-lin500|<tuple|8|4|../../../../../wr/20230213..bkshuf_draft/src/doc.tm>>
    <associate|eq gsize-lin|<tuple|6|4|../../../../../wr/20230213..bkshuf_draft/src/doc.tm>>
    <associate|eq gsize-model|<tuple|3|3|../../../../../wr/20230213..bkshuf_draft/src/doc.tm>>
    <associate|eq gsize-param-rel|<tuple|4|3|../../../../../wr/20230213..bkshuf_draft/src/doc.tm>>
    <associate|eq rel-x-lin|<tuple|1|3|../../../../../wr/20230213..bkshuf_draft/src/doc.tm>>
    <associate|eq rel-x0-lin0|<tuple|2|3|../../../../../wr/20230213..bkshuf_draft/src/doc.tm>>
    <associate|fig ex-plot-s|<tuple|1|3|../../../../../wr/20230213..bkshuf_draft/src/doc.tm>>
    <associate|footnote-1|<tuple|1|5|../../../../../wr/20230213..bkshuf_draft/src/doc.tm>>
    <associate|footnote-2|<tuple|2|5|../../../../../wr/20230213..bkshuf_draft/src/doc.tm>>
    <associate|footnr-1|<tuple|1|5|../../../../../wr/20230213..bkshuf_draft/src/doc.tm>>
    <associate|footnr-2|<tuple|2|5|../../../../../wr/20230213..bkshuf_draft/src/doc.tm>>
    <associate|jump-to-random|<tuple|4|2|../../../../../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>|>
        A table listing versions of <with|mode|<quote|prog>|prog-language|<quote|shell>|font-family|<quote|rm>|bkshuf>.
      </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>