source: project/bloom-filter/bloom-filter-eggdoc.scm @ 1412

Last change on this file since 1412 was 1412, checked in by Kon Lovett, 14 years ago

To account for the split up hashes.

File size: 5.8 KB
Line 
1;;;; bloom-filter-eggdoc.scm
2
3(use eggdoc)
4
5(define license #<<EOF
6Copyright (c) 2006, Kon Lovett.  All rights reserved.
7
8Permission is hereby granted, free of charge, to any person obtaining a
9copy of this software and associated documentation files (the Software),
10to deal in the Software without restriction, including without limitation
11the rights to use, copy, modify, merge, publish, distribute, sublicense,
12and/or sell copies of the Software, and to permit persons to whom the
13Software is furnished to do so, subject to the following conditions:
14
15The above copyright notice and this permission notice shall be included
16in all copies or substantial portions of the Software.
17
18THE SOFTWARE IS PROVIDED ASIS, WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
19IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
20FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
21THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
22OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
23ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
24OTHER DEALINGS IN THE SOFTWARE.
25EOF
26)
27
28(define doc `(
29        (eggdoc:begin
30                (name "bloom-filter")
31                (description (p "Provides a simple Bloom Filter"))
32                (author (url "mailto:klovett@pacbell.net" "Kon Lovett"))
33                (history
34                        (version "1.1" "Support for \"optimal K\"")
35                        (version "1.0" "Exports")
36                        (version "0.2" "Add hash primitives configuration file")
37                        (version "0.1" "Initial release"))
38                (requires
39                        iset hashes md5 sha1 sha2 tiger-hash ripemd message-digest lookup-table mathh misc-extn)
40                (usage)
41                (download "bloom-filter.egg")
42
43                (documentation
44
45                        (subsection "Bloom Filter Object"
46
47                                (procedure "(make-bloom-filter M MESSAGE-DIGEST-PRIMITIVE-LIST [K])"
48                                        (p "Returns a bloom-filter object with " (tt "M") " bits of
49                                        discrimination and a set of hash functions built from the
50                                        supplied " (tt "MESSAGE-DIGEST-PRIMITIVE-LIST") ". The
51                                        elements of the list of primitives may be an actual primitive
52                                        object or a symbol naming the desired message-digest.")
53
54                                        (p "The number of hash functions, k, is not necessarily the
55                                        same as the number of message-digests. A hash function is
56                                        defined as returning an unsigned 32 bit integer. Most
57                                        message-digests return more 32 bits of hash. The actual length
58                                        of the hash is divided into 32 bit blocks to get the
59                                        individual hash functions.")
60
61                                        (p "The argument " (tt "K") " will restrict the actual number
62                                        of hash functions to the \"first\" k, no matter how many more
63                                        the supplied message-digests create. First in the order of "
64                                        (tt "MESSAGE-DIGEST-PRIMITIVE-LIST") ".")
65
66                                        (p "Selecting the optimal set of message-digests is beyond the
67                                        scope of " (tt "make-bloom-filter") "."))
68
69                                (procedure "(bloom-filter-n BLOOM-FILTER)"
70                                        (p "The current population - the number of objects added to the filter."))
71
72                                (procedure "(bloom-filter-m BLOOM-FILTER)"
73                                        (p "The number of bits of discrimination."))
74
75                                (procedure "(bloom-filter-k BLOOM-FILTER)"
76                                        (p "The number of hash functions. (See above.)"))
77
78                                (procedure "(bloom-filter-p-false-positive BLOOM-FILTER [N])"
79                                        (p "The probability of false positives for the given population
80                                        size. The current population is assumed."))
81
82                                (procedure "(bloom-filter-set! BLOOM-FILTER OBJECT)"
83                                        (p "Add the specified " (tt "OBJECT") " to the indicated " (tt
84                                        "BLOOM-FILTER") "."))
85
86                                (procedure "(bloom-filter-exists? BLOOM-FILTER OBJECT)"
87                                        (p "Is the specified " (tt "OBJECT") " in the indicated " (tt
88                                        "BLOOM-FILTER") "."))
89                        )
90
91                        (subsection "Auxillary Procedures"
92
93                                (procedure "(bloom-filter:optimum-k N M)"
94                                        (p "Optimal count of hash functions for the given population
95                                        size " (tt "N") " and " (tt "M") " bits of discrimination."))
96
97                                (procedure "(bloom-filter:optimum-m K N)"
98                                        (p "Optimal count of bits of discrimination for the given
99                                        population size " (tt "N") " and " (tt "K") " number of hash
100                                        functions."))
101
102                                (procedure "(bloom-filter:p-false-positive K N M)"
103                                        (p "What is the probability of false positives for the
104                                        population size " (tt "N") " assuming " (tt "K") " hash
105                                        functions and " (tt "M") " bits of discrimination."))
106
107                                (procedure "(bloom-filter:desired-m P N [K])"
108                                        (p "Calculates a near-optimal number of bits of discrimination
109                                        to meet the desired probability of false positives " (tt "P") ",
110                                        with the given population size " (tt "N") " and number of hash
111                                        functions " (tt "K") ". When the k parameter is missing the "
112                                        (tt "bloom-filter:optimum-k") " procedure is used to calculate a
113                                        value.")
114
115                                        (p "A multi-valued return of the calculated M, K, and P values.
116                                        The calculated probability may be lower than the desired."))
117
118                                (procedure "(bloom-filter:actual-k MESSAGE-DIGEST-PRIMITIVE-LIST)"
119                                        (p "Calculates the actual number of hash functions for the " (tt
120                                        "MESSAGE-DIGEST-PRIMITIVE-LIST") ". The elements of the list of
121                                        primitives may be an actual primitive object or a symbol naming
122                                        the desired message-digest."))
123
124                                (procedure "(bloom-filter:p-random-one-bit K N M)"
125                                        (p "Guess."))
126                        )
127
128                        (subsection "Hash Primitives Configuration File"
129
130                                (p "A file, \"hash-primitives-info\", is located in the Chicken
131                                Repository. The file contains the information needed by
132                                bloom-filter to load hash primitives at runtime. The file is
133                                self-documenting.")
134                        )
135                )
136
137                (section "References"
138
139                        (ul
140                                (li (url "http://www.cs.wisc.edu/~cao/papers/summary-cache/node8.html#SECTION00053000000000000000"
141                                "Nice exposition of Bloom Filter False Positive Probability."))
142
143                                (li (url "http://www.cc.gatech.edu/fac/Pete.Manolios/bloom-filters/calculator.html"
144                                "A web interface for a better version of " (tt"bloom-filter:desired-m") "."))
145                        )
146                )
147
148                (section "License" (pre ,license))
149        )
150))
151
152(eggdoc->html doc)
Note: See TracBrowser for help on using the repository browser.