Index Build Tools · BitFunnel

Index Build Tools

Tue, Aug 30, 2016
e91e498599
NOTE: This page was updated on 9/19/16 to reflect significant changes in the index build tools.

After many months of hard work, we kind of, sort of have a document ingestion pipeline that seems to work. By this I mean we have a minimal set of configuration and ingestion tools that we can compile and then run without crashing, and these tools seem to ingest files mostly as expected. We’re still going to need to do a lot of testing, tuning and evaluation, but I thought it would be helpful to take this time to walk through the process of bringing up an index from a set of chunk files extracted from Wikipedia.

The remainder of this post is a fairly long step-by-step description of the process I used to configure and start a BitFunnel index. It’s pretty dry, but should be useful for people who want to play around with the system.

Obtaining a Sample Corpus

I decided to use a small portion of the English Wikipedia as a basis for this walkthrough. This piece contains about 17k articles. I processed it into a collection of BitFunnel chunk files which you can download from our Azure blob storarge. (see the post entitled Sample Data for instructions on downloading the pre-built chunk files).

The chunk files were built from a Wikipedia dump using the process outlined in the WorkBench README. If you would like to build your own chunks from scratch, download the dump from the Wikipedia dump page or grab an archived copy from our Azure blob storage. Either way, the file must be decompressed before it can be used.

The Wikipedia dump file is converted to chunks using a two-step process. The first step uses an open source project called wikiextractor to filter out Wikipedia markup.

The output of Wikiextractor is a set of 1Mb XML files, with names like wiki_00, wiki_01, wiki_02, etc. and organized under directories AA, AB, AC, etc.

The second step uses the Java-based Workbench project to perform word-breaking, stemming, and stop-word elimination. The output of the Workbench stage is a set of BitFunnel chunk files.

Gathering Corpus Statistics

Because BitFunnel is a probabilistic algorithm based on Bloom Filters, its configuration depends on statistical properties of the corpus, like the distributions of term frequencies and document lengths.

The BitFunnel statistics command generates these statistics from a representative corpus. Run BitFunnel statistics -help to print out a help message describing the command line arguments.

% BitFunnel statistics -help
StatisticsBuilder
Ingest documents and compute statistics about them.

Usage:
BitFunnel statistics <manifestFile>
                     <outDir>
                     [-help]
                     [-text]
                     [-gramsize <integer>]

<manifestFile>
    Path to a file containing the paths to the chunk
    files to be ingested. One chunk file per line.
    Paths are relative to working directory. (string)

<outDir>
    Path to the output directory where files will
    be written.  (string)

[-help]
    Display help for this program. (boolean, defaults to false)


[-text]
    Create mapping from Term::Hash to term text. (boolean, defaults to false)


[-gramsize <integer>]
    Set the maximum ngram size for phrases. (integer,
    defaults to 1)

The first parameter is a manifest file that lists the paths to the chunk files, one file per line. You can generate a manifest file with all of the chunks using the Linux find command. Here’s an example that uses the find command to create a manifest for all of the prebuilt chunks that were downloaded to /tmp/wikipedia/chunks.

% find /tmp/wikipedia/chunks -type f > /tmp/wikipedia/manifest.txt

The second parameter to BitFunnel statistics is the output directory. In this case I used /tmp/wikipedia/config (note that the prebuilt chunk tarball includes a wikipedia/config directory with the output of this walkthrough). Be sure to create the output directory if it doesn’t already exist:

% mkdir /tmp/wikipedia/config

When I ran BitFunnel statistics, I omitted the -gramsize parameter because I wanted statistics for a corpus of unigrams. Had I included -gramsize, I could have generated statistics for a corpus that included bigrams or trigrams or larger ngrams.

I included the -text parameter because I wanted the document frequency table to be annotated with the text of each term. Had I not included -text, the terms would be represented solely by their hash values.

Here’s the console log:

% BitFunnel statistics /tmp/wikipedia/manifest.txt  /tmp/wikipedia/config
Blocksize: 3592
Loading chunk list file '/tmp/wikipedia/manifest.txt'
Temp dir: '/tmp/wikipedia/config'
Reading 259 files
Ingesting . . .
ChunkManifestIngestor::IngestChunk: filePath = /tmp/wikipedia/chunks/.DS_Store
ChunkManifestIngestor::IngestChunk: filePath = /tmp/wikipedia/chunks/AA/wiki_00
ChunkManifestIngestor::IngestChunk: filePath = /tmp/wikipedia/chunks/AA/wiki_01
ChunkManifestIngestor::IngestChunk: filePath = /tmp/wikipedia/chunks/AA/wiki_02
...
ChunkManifestIngestor::IngestChunk: filePath = /tmp/wikipedia/chunks/AC/wiki_56
ChunkManifestIngestor::IngestChunk: filePath = /tmp/wikipedia/chunks/AC/wiki_57
Ingestion complete.
  Ingestion time = 11.5985
  Ingestion rate (bytes/s): 1.78954e+07
Shard count:1
Document count: 17618
Bytes/Document: 11781.1
Total bytes read: 207559890
Posting count: 12848420

The statistics files were written to c/tmp/wikipedia/config:

ls -l /tmp/wikipedia/config
total 100384
-rw-r--r--  1 mhop  wheel    216796 Sep 18 16:07 CumulativeTermCounts-0.csv
-rw-r--r--  1 mhop  wheel  21516222 Sep 18 16:07 DocFreqTable-0.csv
-rw-r--r--  1 mhop  wheel     18265 Sep 18 16:07 DocumentLengthHistogram.csv
-rw-r--r--  1 mhop  wheel   8202248 Sep 18 16:07 IndexedIdfTable-0.bin
-rw-r--r--  1 mhop  wheel  13463535 Sep 18 16:07 TermToText.bin

CumulativeTermCounts-0.csv tracks the number of unique terms encountered as a function of the number of documents ingested. It is not currently used but will be needed for accurate models of memory consumption.

DocumentLengthHistogram.csv is a histogram of documents organized by the number of unique terms in each document. It is not currently used, but will be needed to determine how to organize documents into shards according to posting count.

DocFreqTable-0.csv lists the unique terms in the corpus in descending frequency order. In other words, more common words appear before less common words. Here’s what the file looks like:

% more /tmp/wikipedia/config/DocFreqTable-0.csv
hash,gramSize,streamId,frequency,text
3f0ffc72a21fd2be,1,1,0.840447,from
b3697479c07d98d5,1,1,0.808378,which
4d34895e97b1888c,1,1,0.795266,also
17e90965afd3104d,1,1,0.763764,have
d14e34f5833aecee,1,1,0.755875,one
5d4e8d01c132cf18,1,1,0.745147,other
...
8f2e873ae4281b44,1,1,5.67601e-05,arslān
d859a38c4ac69616,1,1,5.67601e-05,influxu
c307a841264a8d2d,1,1,5.67601e-05,köşk
e19c09157d44124,1,1,5.67601e-05,tharil
3885b5929dd1a8dd,1,1,5.67601e-05,www.routledge.com

As you can see, the term “from” is the most common, appearing in about 84% of documents. Towards the end of the file, “arslān” is one of the rarest, appearing in 0.006% of documents, or once in the entire corpus of 17618 documents.

IndexedIdfTable-0.bin is a binary file containing the IDF value for each term. It is used for constructing Terms during document ingestion and query formulation.

Finally, TermToText.bin is binary file containing a mapping from a term’s hash value to its text representation. It is used for debugging and diagnostics.

These files will be used in the next stage where we build the TermTable.

Building a TermTable

The TermTable is one of the most important data structures in BitFunnel. It maps each term to the exact set of rows used to indicate the term’s presence in a document.

I won’t get into how the TermTable builder works at this point, but let’s look at how to run it. Type BitFunnel termtable -help:

BitFunnel termtable -help
TermTableBuilderTool
Generate a TermTable from a DocumentFrequencyTable.

Usage:
BitFunnel termtable <tempPath>
                    [-help]

<tempPath>
    Path to a tmp directory. Something like /tmp/ or c:\temp\,
    depending on platform.. (string)

[-help]
    Display help for this program. (boolean, defaults to false)

In this case the help message could be a bit better. All you need to know is that BitFunnel termtable has a single argument and this is the output directory from the BitFunnel statistics stage. The TermTable builder will read DocFreqTable-0.csv, constuct a very basic TermTable, and write it to TermTable-0.bin.

For now, the algorithm creates a TermTable for unigrams that uses a combination of rank 0 and rank 3 rows. The algorithm is naive and doesn’t handle higher order ngrams. Down the road, we will improve the algorithm and add more options.

Here’s the output from my run:

BitFunnel termtable /tmp/wikipedia/config
Loading files for TermTable build.
Starting TermTable build.
Total build time: 0.439845 seconds.
===================================
RowAssigner for rank 0
  Terms
    Total: 512640
    Adhoc: 468884
    Explicit: 42357
    Private: 1399

  Rows
    Total: 5814
    Adhoc: 590
    Explicit: 3822
    Private: 1399

  Bytes per document: 778.75


  Densities in explicit shared rows
    Mean: 0.0999029
    Min: 0.0980813
    Max: 0.0999549
    Variance: 3.00201e-08

===================================
RowAssigner for rank 1
  No terms

===================================
RowAssigner for rank 2
  No terms

===================================
RowAssigner for rank 3
  Terms
    Total: 511026
    Adhoc: 416436
    Explicit: 90958
    Private: 3632

  Rows
    Total: 36107
    Adhoc: 1827
    Explicit: 30648
    Private: 3632

  Bytes per document: 564.172


  Densities in explicit shared rows
    Mean: 0.099836
    Min: 0.0124819
    Max: 0.0999997
    Variance: 5.68987e-07

===================================
RowAssigner for rank 4
  No terms

===================================
RowAssigner for rank 5
  No terms

===================================
RowAssigner for rank 6
  No terms

===================================
RowAssigner for rank 7
  No terms

Writing TermTable files.
Done.

From the output, above, we can see that this index will consume roughly 779 bytes of rank 0 rows and 562 bytes of rank 3 rows per document ingested. This corpus has 17618 documents, so the total memory consumption for rows should be about 22.8Mb. This is a significant reduction over the 198Mb of chunk files, but we at this point, we can draw no conclusions because we have no idea whether this naive configuration has an acceptable false positive rate.

If we look in tmp/wikipedia/config we will see the TermTable is stored in a new binary file called TermTable-0.bin:

ls -l /tmp/wikipedia/config
total 100384
-rw-r--r--  1 mhop  wheel    216796 Sep 18 16:07 CumulativeTermCounts-0.csv
-rw-r--r--  1 mhop  wheel  21516222 Sep 18 16:07 DocFreqTable-0.csv
-rw-r--r--  1 mhop  wheel     18265 Sep 18 16:07 DocumentLengthHistogram.csv
-rw-r--r--  1 mhop  wheel   8202248 Sep 18 16:07 IndexedIdfTable-0.bin
-rw-r--r--  1 mhop  wheel   7970980 Sep 18 16:09 TermTable-0.bin
-rw-r--r--  1 mhop  wheel  13463535 Sep 18 16:07 TermToText.bin

We’ve now configured our system for a typical corpus with documents similar to those in the chunk files listed in the original manifest. In the next step we will ingest some files and look at the resulting row table values.

Ingesting a Small Corpus

Now we’re getting to the fun part. BitFunnel repl is a sample application that provides an interactive Read-Eval-Print loop for ingesting documents, running queries, and inspecting various data structures.

Here’s the help message:

BitFunnel repl -help
StatisticsBuilder
Ingest documents and compute statistics about them.

Usage:
BitFunnel repl <path>
               [-help]
               [-gramsize <integer>]
               [-threads <integer>]

<path>
    Path to a tmp directory. Something like /tmp/ or c:\temp\,
    depending on platform.. (string)

[-help]
    Display help for this program. (boolean, defaults to false)


[-gramsize <integer>]
    Set the maximum ngram size for phrases. (integer, defaults
    to 1)

[-threads <integer>]
    Set the thread count for ingestion and query processing.
    (integer, defaults to 1)

The first parameter is the path to the directory with the configuration files. In my case this is /tmp/wikipedia/config. The gramsize should be the same value used in the BitFunnel statistics stage.

When you start the application, it prints out a welcome message, explains how to get help, and then prompts for input. The prompt is an integer followed by a colon. Type “help” to get a list of commands. You can also get help on a specific command:

BitFunnel repl /tmp/wikipedia/config
Welcome to BitFunnel!
Starting 1 thread
(plus one extra thread for the Recycler.

directory = "/tmp/wikipedia/config"
gram size = 1

Starting index ...
Blocksize: 11005320
Index started successfully.

Type "help" to get started.

0: help
Available commands:
  cache   Ingests documents into the index and also stores them in a cache
for query verification purposes.
  delay   Prints a message after certain number of seconds
  help    Displays a list of available commands.
  load    Ingests documents into the index
  query   Process a single query or list of queries. (TODO)
  quit    waits for all current tasks to complete then exits.
  script  Runs commands from a file.(TODO)
  show    Shows information about various data structures. (TODO)
  status  Prints system status.
  verify  Verifies the results of a single query against the document cache.

Type "help <command>" for more information on a particular command.

1: help cache
cache (manifest | chunk) <path>
  Ingests a single chunk file or a list of chunk
  files specified by a manifest.
  Also caches IDocuments for query verification.

2: help show
show cache <term>
   | rows <term> [<docstart> <docend>]
   | term <term>
  Shows information about various data structures.  PARTIALLY IMPLEMENTED

Right now the cache command doesn’t support the manifest option and the show command only supports the rows and terms option.

Let’s ingest a single chunk file. We’ll use /tmp/wikipedia/chunks/AA/wiki_00 which contains the following 41 documents:

Here’s the chunk loading in the REPL console:

3: cache chunk /tmp/wikipedia/chunks/AA/wiki_00
Ingesting chunk file "/tmp/wikipedia/chunks/AA/wiki_00"
Caching IDocuments for query verification.
ChunkManifestIngestor::IngestChunk: filePath = /tmp/wikipedia/chunks/AA/wiki_00
Ingestion complete.

We can now use the show rows command to display the rows associated with a particular term. This command lists each of the RowIds associated with a term, followed by the bits for the first 64 documents. The document ids are printed vertically above each column of bits.

4: show rows also
Term("also")
                 d 00012233333333333333333555555555555566666
                 o 12329900000123333344555677788899999901122
                 c 25980535789640246904489923902603457902501
  RowId(0, 1005 ): 11111111111011111111111101011111111111011
5: show rows some
Term("some")
                 d 00012233333333333333333555555555555566666
                 o 12329900000123333344555677788899999901122
                 c 25980535789640246904489923902603457902501
  RowId(0, 1011 ): 11111011111011001101110101001101111111011
6: show rows wings
Term("wings")
                 d 00012233333333333333333555555555555566666
                 o 12329900000123333344555677788899999901122
                 c 25980535789640246904489923902603457902501
  RowId(3, 6668 ): 00000001000000000000000000000000000000000
  RowId(3, 6669 ): 00000001000000000000000000000000000000000
  RowId(3, 6670 ): 00000001000000000000000000000000000000000
  RowId(0, 4498 ): 00000001000000000000110000000100000000000
7: show rows anarchy
Term("anarchy")
                 d 00012233333333333333333555555555555566666
                 o 12329900000123333344555677788899999901122
                 c 25980535789640246904489923902603457902501
  RowId(3, 11507): 10000000110000001000010000000000000000000
  RowId(3, 11508): 10000000110000001000010000000000000000000
  RowId(3, 11509): 10000000110000001000010000000000000000000
  RowId(0, 5354 ): 11000001110000000000010001001000000000010
8: show rows kingdom
Term("kingdom")
                 d 00012233333333333333333555555555555566666
                 o 12329900000123333344555677788899999901122
                 c 25980535789640246904489923902603457902501
  RowId(0, 1609 ): 11000010010000100000000000000001000010001

At prompt 4, the command show rows also returns a single RowId(0, 1005) corresponding to the term “also”. This is a rank 0 row in position 1005. The fact that the word “also” is associated with a single row indicates that the term is fairly common in the corpus. This is consistent with the pattern of 1 bits which show that the term appears in every document except 316, 572, 579, and 615.

At prompt 5, we see that the word “some” is also common in the corpus. It appears in every document except 295, 316, 332, 334, 359, 572, 579, 580, and 615.

Both “also” and “some” appear so frequently that are assigned private rows.

The term “wings”, seen at prompt 6, is less common. It is actually rare enough to require four row intersections to drive the noise to a tolerable level. If we look at the intersection of the four rows, we see that only document 305 contains the term. This is the only column that consists solely of 1s. All of the other columns have some 0s.

At prompt 7 we see that anarchy is also rare enough to require four rows, but it seems to appear in documents 12, 307, 308, and 358. A quick search of the actual web pages shows that “anarchy” appears in document 12 which is about Anarchism and document 307 which is about Abraham Lincoln. Pages 308 and 358 do not actually contain the term, so we are seeing a case where BitFunnel would report false positives.

Now let’s look at the verify one command. Today this command runs a very slow verification query engine on the IDocuments cached earlier by the cache chunk command. In the future, verify will run the BitFunnel query engine and compare its output with the verification query engine.

9: verify one wings
Processing query " wings"
  DocId(305)
1 match(es) out of 41 documents.
10: verify one anarchy
Processing query " anarchy"
  DocId(307)
  DocId(12)

Prompt 9 shows that only document 305 contains the term “wings”. Prompt 10 reports that only documents 12 and 307 contain the term anarchy.

Note that verify one accepts any legal BitFunnel query. Here’s an example:

11: verify one -some (anarchy | kingdom)
Processing query " -some (anarchy | kingdom)"
  DocId(332)
1 match(es) out of 41 documents.

Well that’s enough for now. Hopefully this walkthrough will help you get started with BitFunnel configuration.

Michael Hopcroft
A 19 year veteran at Microsoft, Mike has worked on Office, Windows and Visual Studio. He has spent the past 6 years developing cloud scale infrastructure for the Bing search engine. He is a founding member of BitFunnel.