affirmative-sampling 1.0.0

Reference implementation of the Affirmative Sampling algorithm by Jérémie Lumbroso and Conrado Martínez (2022).

Affirmative Sampling: Reference Implementation

This repository contains a reference implementation, in Python, of the Affirmative Sampling algorithm by Jérémie Lumbroso and Conrado Martínez (2022), as well as the original paper, accepted at the Analysis of Algorithms 2022 edition in Philadelphia.

Table of contents:

• Abstract
• Installation
• Historical Context
• Example
• Intuition of How the Random Sample Grows
• License

ToC generated with markdown-toc

Abstract

Affirmative Sampling is a practical and efficient novel algorithm to obtain random samples of distinct elements from a data stream.

Its most salient feature is that the size $S$ of the sample will, on expectation, grow with the (unknown) number $n$ of distinct elements in the data stream.

As any distinct element has the same probability to be sampled, and the sample size is greater when the "diversity" (the number of distinct elements) is greater, the samples that Affirmative Sampling delivers are more representative than those produced by any scheme where the sample size is fixed a priori—hence its name. This repository contains a reference implementation, in Python, to illustrate how the algorithm works and showcase some basic experimentation.

Installation

This package is available on PyPI and can be installed through the typical means:

$ pip install affirmative_sampling

The hash functions that are used in this package come from the randomhash Python package.

Historical Context

Sampling is a very important tool, because it makes it possible to infer information about a large data set using the characteristics of a much smaller data set. Historically, it came in the following flavors:

• (Straight) Sampling: Each element of the initial data set of size $N$ is taken with the same (fixed) probability $p$. Such sample's size is a random variable, distributed like a binomial and centered in a mean of $Np$.

• Reservoir Sampling: This (family of) algorithm(s), introduced by Jeffrey Vitter (1985), ensures the size of the resulting sample is fixed, by using replacements—indeed an element that is in the sample at some point in these algorithms, might later be evicted and replaced, to ensure the sample is both of fixed size, yet contains elements with uniform probability.

• Adaptive/Distinct Sampling: This algorithm, introduced by Mark Wegman (1980), analyzed by Philippe Flajolet (1990) and rebranded by Philip Gibbons (2001), draws elements not from a data set of size $N$, but by the underlying set of distinct items of that data set, of cardinality $n$. Both previous families of algorithm are susceptible to large, frequent elements, that drawn out other more rare elements. Distinct sampling algorithms are family of sampling algorithms that use hash functions to be insensitive to repetitions. While the size of the sample is not fixed, it oscillates closely around a fixed (constant) size.

• Affirmative Sampling: This novel algorithm conserves the properties of the Distinct Sampling family of algorithms (because it also uses a hash function to be insensitive to repeated elements), but allows the target size of the sample to be a function of $n$, the number of distinct elements in the source data set—to be precise, the size of the sample is supposed to be $~k \cdot \log \frac n k + k$, logarithmic in the number of distinct elements. This is important, because the accuracy of estimates inferred from a random sample depend on how representative the sample is of the diversity of the source data set, and Affirmative Sampling calibrates the size of the sample to deliver accurate estimates.

Example

You can look and run an example. Assuming you have pipenv:

$ pipenv run python example.py

or otherwise assuming your current Python environment has the package affirmative_sampling installed:

$ python example.py

The output will be something along the following lines (exact value will change as the seed depends on the computer's clock):

=====================================================
'Affirmative Sampling' by J. Lumbroso and C. Martínez
=====================================================

   Examples use Moby Dick (from the Gutenberg Project)
   N=215436, n=19962, k=100, k*ln(n/k)=629.641555925844

EXAMPLE 1: Number of tokens without 'e'
====================================
- Exact count: 6839
- Estimated count: 7398.94
  - Error: 8.19%

- Size of sample: 648
   - Expected size of sample: 629.64
   - Tokens in sample without 'e': 242
   - Proportion of tokens in sample without 'e': 37.35%


EXAMPLE 2: Number of mice (freq. less or equal to 5)
====================================================
- Exact count: 16450
- Estimated count: 16999.21
  - Error: 3.34%

- Size of sample: 648
   - Expected size of sample: 629.64
   - Tokens in sample without 'e': 556
   - Proportion of tokens in sample without 'e': 85.8%

SAMPLE
======
 1780 but
  427 would
  315 do
  165 water
  103 sight
   86 give
   68 name
   61 together
   54 entire
   43 straight
   37 famous
   33 idea
   31 mariners
   29 person
   29 stands
   27 wooden
   26 circumstance
   26 cutting
   26 otherwise
   25 souls
   22 aboard
   22 owing
   20 ah
   19 concluded
   19 deeper
   19 leaves
   19 ordinary
   18 anchor
   18 presently
   17 foolish
   17 previously
   17 weight
   16 fate
   15 fit
   15 flag
   15 grass
   15 shake
   14 intent
   14 rock
   13 bunger
   13 cool
   13 eager
   13 glancing
   13 slightly
   13 token
   13 trademark
   13 visit
   12 america
   12 smells
   12 solemn
   12 street
   12 touched
   11 ashes
   11 carefully
   11 carpenters
   11 dish
   11 downwards
   11 sounding
   11 stream
   10 event
   10 inferior
   10 lift
   10 perch
    9 cask
    9 change
    9 driving
    9 everlasting
    8 crushed
    8 currents
    8 damp
    8 leviathanic
    8 mayhew
    8 monkey
    8 ought
    8 published
    8 shooting
    8 strove
    7 cracked
    7 destined
    7 knocking
    7 lookout
    6 arch
    6 bury
    6 cheek
    6 comfort
    6 decent
    6 longitude
    6 probable
    6 purple
    6 subjects
    6 symptoms
    6 value
    5 depend
    5 dip
    5 disordered
    5 faded
    5 fasten
    5 france
    5 guard
    5 humming
    5 invited
    5 navy
    5 paradise
    5 pen
    5 riveted
    5 rude
    5 specimen
    5 sufficient
    5 wait
    4 anchored
    4 arsacidean
    4 assert
    4 beast
    4 beaver
    4 blubberroom
    4 boatknife
    4 cease
    4 damages
    4 distinguish
    4 fidelity
    4 follows
    4 gills
    4 hearses
    4 moves
    4 music
    4 ninety
    4 offers
    4 paintings
    4 razor
    4 respectfully
    4 scorching
    4 sets
    4 spaniards
    4 standers
    4 stroll
    4 supposition
    4 tufted
    4 unrecorded
    3 asiatic
    3 behooves
    3 brilliancy
    3 capacity
    3 capricious
    3 cares
    3 characteristics
    3 charley
    3 churned
    3 closet
    3 cuts
    3 describe
    3 disposition
    3 dodge
    3 entity
    3 epidemic
    3 eternities
    3 extinct
    3 fancies
    3 figured
    3 fleetness
    3 flooded
    3 flurry
    3 grizzled
    3 halls
    3 hip
    3 inconsiderable
    3 inmates
    3 inseparable
    3 mending
    3 mule
    3 pouring
    3 pregnant
    3 providence
    3 quoted
    3 rags
    3 romish
    3 route
    3 shun
    3 smoky
    3 socks
    3 spots
    3 stained
    3 stolen
    3 substantiated
    3 suspect
    3 tarpaulins
    3 tashtegos
    3 thrusts
    3 ticklish
    3 tows
    3 tragedy
    3 treat
    3 typhoons
    3 unabated
    3 user
    3 weighty
    3 westward
    3 whittling
    3 wraps
    2 accessible
    2 admitting
    2 admonished
    2 aglow
    2 agonized
    2 alluding
    2 attain
    2 avenues
    2 awed
    2 backwoodsman
    2 barely
    2 belshazzars
    2 bout
    2 brag
    2 bravest
    2 bumps
    2 burkes
    2 ceases
    2 chancelike
    2 chasefirst
    2 complement
    2 confidently
    2 constitution
    2 cows
    2 cringing
    2 decanting
    2 digest
    2 dilapidated
    2 distinctive
    2 dusting
    2 egotistical
    2 enlivened
    2 ensue
    2 entrances
    2 error
    2 essentially
    2 exertion
    2 expiring
    2 faraway
    2 fearlessly
    2 fishe
    2 fishspears
    2 girdling
    2 glide
    2 grammar
    2 halloo
    2 hilariously
    2 housekeeping
    2 hover
    2 hudson
    2 imputation
    2 injured
    2 junks
    2 keyhole
    2 manofwar
    2 masterless
    2 meridian
    2 misanthropic
    2 navel
    2 newspaper
    2 obligations
    2 opulent
    2 oughts
    2 outlast
    2 outwardbound
    2 overseeing
    2 paramount
    2 penetrating
    2 performed
    2 permitting
    2 pumping
    2 quaint
    2 quilt
    2 rabelais
    2 reappeared
    2 regulating
    2 ripple
    2 ruinous
    2 sadder
    2 sagittarius
    2 saltsea
    2 scandinavian
    2 scratches
    2 serves
    2 shunned
    2 snows
    2 squeezed
    2 stiffest
    2 sympathies
    2 tarpaulin
    2 temperature
    2 texas
    2 toilings
    2 tweezers
    2 underneath
    2 unthinkingly
    2 unwarrantably
    2 ushered
    2 vagabond
    2 whalehunters
    2 woodlands
    1 abstemious
    1 accomplishment
    1 acquiesce
    1 admirer
    1 adoring
    1 affghanistan
    1 afterhes
    1 ahabshudder
    1 airfreighted
    1 alpine
    1 amosti
    1 ancestress
    1 andromedaindeed
    1 animosity
    1 annually
    1 antecedent
    1 aroostook
    1 arter
    1 asa
    1 atom
    1 attarofrose
    1 backof
    1 ballena
    1 bamboozingly
    1 bamboozle
    1 battled
    1 bays
    1 bedclothes
    1 beehive
    1 bellbuttons
    1 bestreaked
    1 billiardball
    1 billiardballs
    1 boatsmark
    1 boatswain
    1 brandingiron
    1 breedeth
    1 brutal
    1 brutes
    1 bungle
    1 burlybrowed
    1 cajoling
    1 cambrics
    1 centipede
    1 channel
    1 characteristically
    1 chickens
    1 circumambient
    1 clapt
    1 claw
    1 claws
    1 cloudscud
    1 colorless
    1 commentator
    1 confidentially
    1 congeniality
    1 connexions
    1 consolatory
    1 constrain
    1 contiguity
    1 controllable
    1 costermongers
    1 couldin
    1 counteracted
    1 counterbalanced
    1 counters
    1 courtesymay
    1 coverlid
    1 creware
    1 crookedness
    1 crownjewels
    1 czarship
    1 dallied
    1 deaden
    1 decisionone
    1 defiles
    1 delightwho
    1 demonism
    1 departing
    1 detects
    1 digester
    1 dines
    1 disbands
    1 discipline
    1 dissolve
    1 domineered
    1 donned
    1 donthe
    1 doubleshuffle
    1 doubling
    1 doughnuts
    1 dubiouslooking
    1 dugongs
    1 dumbest
    1 dwarfed
    1 earththat
    1 eavetroughs
    1 ego
    1 ellery
    1 elucidating
    1 emoluments
    1 englishknowing
    1 engraven
    1 enthusiasmbut
    1 errorabounding
    1 eventuated
    1 exaggerate
    1 exegetists
    1 exploring
    1 expressly
    1 exultation
    1 factories
    1 feasting
    1 featuring
    1 ferdinando
    1 fiercefanged
    1 fissures
    1 fitsthats
    1 flavorish
    1 froissart
    1 funereally
    1 furs
    1 garterknights
    1 ghastliness
    1 glimmering
    1 gloss
    1 glows
    1 godomnipresent
    1 grease
    1 greenly
    1 grog
    1 groupings
    1 guido
    1 halfbelieved
    1 hangdog
    1 hayseed
    1 headladen
    1 heraldic
    1 hitching
    1 hoarfrost
    1 honing
    1 hopefulness
    1 horned
    1 hussars
    1 ifand
    1 ignore
    1 ignoring
    1 ills
    1 illumination
    1 imitated
    1 import
    1 incidents
    1 indianfile
    1 inflated
    1 instigation
    1 intangible
    1 intercedings
    1 interflow
    1 inventing
    1 inventors
    1 irresolution
    1 ithow
    1 ixion
    1 jobcoming
    1 jollynot
    1 jugglers
    1 lackaday
    1 lacks
    1 ladthe
    1 lakeevinced
    1 laureate
    1 legmaker
    1 lend
    1 leopardsthe
    1 leviathanism
    1 lifeas
    1 lighten
    1 lighthouse
    1 lordvishnoo
    1 lovings
    1 maintruckha
    1 maltreated
    1 manufacturer
    1 marquee
    1 meatmarket
    1 miasmas
    1 midnighthow
    1 migrating
    1 milkiness
    1 misfortune
    1 mixing
    1 mock
    1 moons
    1 mossy
    1 mutinying
    1 mystically
    1 namelessly
    1 nantuckois
    1 napoleons
    1 naythe
    1 negligence
    1 neighborsthe
    1 netted
    1 nondescripts
    1 offwe
    1 oftenest
    1 ohwhew
    1 oilpainting
    1 onsets
    1 overbalance
    1 overdoing
    1 palpableness
    1 panicstricken
    1 parenthesize
    1 particoloured
    1 pascal
    1 pauselessly
    1 pave
    1 peddlin
    1 pedestal
    1 perturbation
    1 pester
    1 philopater
    1 plaintively
    1 platos
    1 poker
    1 prescribed
    1 princess
    1 proas
    1 propulsion
    1 prtorians
    1 queerqueer
    1 quitthe
    1 quivered
    1 rads
    1 rarities
    1 readable
    1 reasona
    1 rechristened
    1 regardless
    1 reglar
    1 repent
    1 reverenced
    1 reveriestallied
    1 rightdown
    1 rioting
    1 rob
    1 rosesome
    1 rustling
    1 saidtherefore
    1 sawlightning
    1 sayshands
    1 scoot
    1 scornfully
    1 scuffling
    1 seafowl
    1 seamless
    1 seasalt
    1 seconds
    1 sedentary
    1 seducing
    1 selfcollectedness
    1 sheathed
    1 shindy
    1 shipwhich
    1 shirrbut
    1 shortwarpthe
    1 shoutedsail
    1 sideladder
    1 silverso
    1 singlesheaved
    1 sirin
    1 slanderous
    1 soars
    1 sodom
    1 songster
    1 sphynxs
    1 spill
    1 spoiling
    1 spurzheim
    1 starbuckbut
    1 staterooms
    1 stingy
    1 stoopingly
    1 sunburnt
    1 superseded
    1 surcoat
    1 surpassingly
    1 surveying
    1 syren
    1 tenement
    1 terribleness
    1 theni
    1 therethe
    1 thingbe
    1 thingnamely
    1 thingsoak
    1 thinkbut
    1 thisgreen
    1 thisthe
    1 thunderclotted
    1 ticdollyrow
    1 tick
    1 ticking
    1 tie
    1 timberhead
    1 tipping
    1 topple
    1 tracingsout
    1 traditional
    1 trans
    1 treachery
    1 treasuries
    1 trivial
    1 trumpblister
    1 tunnels
    1 unblinkingly
    1 unchallenged
    1 undecided
    1 undefiled
    1 underground
    1 unequal
    1 unfavourable
    1 unfractioned
    1 unmisgiving
    1 unsay
    1 unthought
    1 usei
    1 vanquished
    1 victory
    1 virgo
    1 volunteered
    1 wading
    1 wales
    1 wan
    1 wary
    1 waythats
    1 weathersheet
    1 weaverpauseone
    1 wept
    1 wethough
    1 whalethis
    1 whalewise
    1 winces
    1 workmen
    1 worm
    1 wornout
    1 worseat
    1 zip

Intuition of How the Random Sample Grows

The novel property of the algorithm is that it grows in a controlled way, that is related to the logarithm of the number of distinct elements. The sample is divided into two parts: A fixed-size part (sample_core) that will always be of size $k$; and a variable-size part (sample_xtra) that will grow slowly throughout the process of the algorithm. Depending on its hashed value, a new element $z$ might either be DISCARDED, REPLACE an existing element of the sample, or EXPAND the variable-size sample, see diagram below:

REPRESENTATION OF THE SAMPLE DURING THE ALGORITHM         |   OUTCOMES FOR NEW ELEMENT z
                                                          |         y = hash(z)
      High hash values                                    |
             ^                                            |
             |                                            |
             |                                            |
+-------------------------+ <-- max hash of S so far      |
|                         |     (no need to track this)   | <-- y >= k-th hash
| sample_core             |                               |
| size = k (always/fixed) |                               |  EXPAND:
|                         |                               |    ADD z to sample_core
+-------------------------+ <-- k-th hash of S            |    MOVE z_kth_hash from
|                         |     = min hash in sample_core |      sample_core to sample_xtra
|                         |                               |    total size ++
| sample_xtra             |                               |
| size = S - k (variable) |                               | <-- kth_hash > y > min_hash
|                         |                               |
|                         |                               |  REPLACE z_min_hash with z:
|                         |                               |    ADD z to sample_xtra
+-------------------------+ <-- min hash of S             |    REMOVE z_min_hash from sample_xtra
             |                  = min hash in sample_xtra |
             |                                            | <-- y <= min_hash
             |                                            |
             v                                            |  DISCARD z
       Low hash values                                    |
                                                          |

As the paper illustrates, it is also possible to design variants of the Affirmative Sampling algorithm, with a growth rate that is different than logarithmic.

License

This project is licensed under the MIT license, which means that you can do whatever you want with this code, as long as you preserve, in some form, the associated copyright and license notice.