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

Last change on this file since 5443 was 5443, checked in by Kon Lovett, 13 years ago

Chg for misc-extn 3.0

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.101" "Dropped :optional")
35                        (version "1.1" "Support for \"optimal K\"")
36                        (version "1.0" "Exports")
37                        (version "0.2" "Add hash primitives configuration file")
38                        (version "0.1" "Initial release"))
39                (requires
40                        iset hashes md5 sha1 sha2 tiger-hash ripemd message-digest lookup-table mathh misc-extn)
41                (usage)
42                (download "bloom-filter.egg")
43
44                (documentation
45
46                        (subsection "Bloom Filter Object"
47
48                                (procedure "(make-bloom-filter M MESSAGE-DIGEST-PRIMITIVE-LIST [K])"
49                                        (p "Returns a bloom-filter object with " (tt "M") " bits of
50                                        discrimination and a set of hash functions built from the
51                                        supplied " (tt "MESSAGE-DIGEST-PRIMITIVE-LIST") ". The
52                                        elements of the list of primitives may be an actual primitive
53                                        object or a symbol naming the desired message-digest.")
54
55                                        (p "The number of hash functions, k, is not necessarily the
56                                        same as the number of message-digests. A hash function is
57                                        defined as returning an unsigned 32 bit integer. Most
58                                        message-digests return more 32 bits of hash. The actual length
59                                        of the hash is divided into 32 bit blocks to get the
60                                        individual hash functions.")
61
62                                        (p "The argument " (tt "K") " will restrict the actual number
63                                        of hash functions to the \"first\" k, no matter how many more
64                                        the supplied message-digests create. First in the order of "
65                                        (tt "MESSAGE-DIGEST-PRIMITIVE-LIST") ".")
66
67                                        (p "Selecting the optimal set of message-digests is beyond the
68                                        scope of " (tt "make-bloom-filter") "."))
69
70                                (procedure "(bloom-filter-n BLOOM-FILTER)"
71                                        (p "The current population - the number of objects added to the filter."))
72
73                                (procedure "(bloom-filter-m BLOOM-FILTER)"
74                                        (p "The number of bits of discrimination."))
75
76                                (procedure "(bloom-filter-k BLOOM-FILTER)"
77                                        (p "The number of hash functions. (See above.)"))
78
79                                (procedure "(bloom-filter-p-false-positive BLOOM-FILTER [N])"
80                                        (p "The probability of false positives for the given population
81                                        size. The current population is assumed."))
82
83                                (procedure "(bloom-filter-set! BLOOM-FILTER OBJECT)"
84                                        (p "Add the specified " (tt "OBJECT") " to the indicated " (tt
85                                        "BLOOM-FILTER") "."))
86
87                                (procedure "(bloom-filter-exists? BLOOM-FILTER OBJECT)"
88                                        (p "Is the specified " (tt "OBJECT") " in the indicated " (tt
89                                        "BLOOM-FILTER") "."))
90                        )
91
92                        (subsection "Auxillary Procedures"
93
94                                (procedure "(bloom-filter:optimum-k N M)"
95                                        (p "Optimal count of hash functions for the given population
96                                        size " (tt "N") " and " (tt "M") " bits of discrimination."))
97
98                                (procedure "(bloom-filter:optimum-m K N)"
99                                        (p "Optimal count of bits of discrimination for the given
100                                        population size " (tt "N") " and " (tt "K") " number of hash
101                                        functions."))
102
103                                (procedure "(bloom-filter:p-false-positive K N M)"
104                                        (p "What is the probability of false positives for the
105                                        population size " (tt "N") " assuming " (tt "K") " hash
106                                        functions and " (tt "M") " bits of discrimination."))
107
108                                (procedure "(bloom-filter:desired-m P N [K])"
109                                        (p "Calculates a near-optimal number of bits of discrimination
110                                        to meet the desired probability of false positives " (tt "P") ",
111                                        with the given population size " (tt "N") " and number of hash
112                                        functions " (tt "K") ". When the k parameter is missing the "
113                                        (tt "bloom-filter:optimum-k") " procedure is used to calculate a
114                                        value.")
115
116                                        (p "A multi-valued return of the calculated M, K, and P values.
117                                        The calculated probability may be lower than the desired."))
118
119                                (procedure "(bloom-filter:actual-k MESSAGE-DIGEST-PRIMITIVE-LIST)"
120                                        (p "Calculates the actual number of hash functions for the " (tt
121                                        "MESSAGE-DIGEST-PRIMITIVE-LIST") ". The elements of the list of
122                                        primitives may be an actual primitive object or a symbol naming
123                                        the desired message-digest."))
124
125                                (procedure "(bloom-filter:p-random-one-bit K N M)"
126                                        (p "Guess."))
127                        )
128
129                        (subsection "Hash Primitives Configuration File"
130
131                                (p "A file, \"hash-primitives-info\", is located in the Chicken
132                                Repository. The file contains the information needed by
133                                bloom-filter to load hash primitives at runtime. The file is
134                                self-documenting.")
135                        )
136                )
137
138                (section "References"
139
140                        (ul
141                                (li (url "http://www.cs.wisc.edu/~cao/papers/summary-cache/node8.html#SECTION00053000000000000000"
142                                "Nice exposition of Bloom Filter False Positive Probability."))
143
144                                (li (url "http://www.cc.gatech.edu/fac/Pete.Manolios/bloom-filters/calculator.html"
145                                "A web interface for a better version of " (tt"bloom-filter:desired-m") "."))
146                        )
147                )
148
149                (section "License" (pre ,license))
150        )
151))
152
153(eggdoc->html doc)
Note: See TracBrowser for help on using the repository browser.