Changeset 1549


Ignore:
Timestamp:
Oct 22, 2011, 2:04:00 PM (6 years ago)
Author:
cameron
Message:

Update parlensort doc

File:
1 edited

Legend:

Unmodified
Added
Removed
  • docs/Working/parlensort.tex

    r1302 r1549  
    99\maketitle
    1010
    11 \section{The Idea}
     11\section{Length-Group Bitstreams}
    1212
    1313Given streams $S$ and $E$ that mark the starts and ends of Names.
     
    1818ends of Names of length 1, $E_1$, and the stream
    1919of ends of Names of greater than length 1, $E_{>1}$, as follows.
     20Here  $n(S)$ is the bitstream ``next'' operation, shifting the
     21stream forward one position.
    2022
    2123\begin{eqnarray*}
     
    5759\end{eqnarray*}
    5860
     61
     62\section{Parallel Hashing}
     63
     64Given length groups identified as in the previous section,
     65it is possible to perform parallel hash value calculation for
     66names in each group as follows.
     67
     68The first step is to create hash streams.
     69Let $B_0, B_1, \ldots, B_7$ be the {\em basis} bitstreams
     70determined by character stream transposition.   That is,
     71the $k$th basis bitstream $B_k$ consists of the $k$th bit
     72of each character in the source data stream.
     73Then we may compute hash streams by some bitwise logical combination
     74of basis bit streams.
     75For example, the following two hash streams may be useful.
     76
     77\begin{eqnarray*}
     78h_a & = & B_2 \oplus B_4 \oplus B_6 \\
     79h_b & = & B_3 \oplus B_5 \oplus B_7 \\
     80\end{eqnarray*}
     81
     82
     83
     84
     85
    5986\section{Follow-up}
    6087
     
    84111lengths?   This avoids allocation of length-based position arrays, the memory
    85112operations of insertion of positions into those arrays, bounds-checking on those
    86 arrays and maintaining an auxiliary array of lengths of the each array.
     113arrays and maintaining an auxiliary array of lengths of each array.
    87114
    88115A further benefit may be from the programming side: the length sorting can
Note: See TracChangeset for help on using the changeset viewer.