Fuzzy Autocomplete

A Fuzzy Query Auto-Completion system based on the paper Efficient and Effective Query Auto-Completion, by Simon Gog, Giulio Ermanno Pibiri, and Rossano Venturini, published in ACM SIGIR 2020. This project expands the system described in the paper by adding the capability of supporting user typos and semantic expansion (Numeral Normalization and Acronym Resolution).

Please, cite the paper if you use the data structures from this library.

Table of contents

1. Installation and quick start
2. Compiling the code
3. Input data format
4. Running the unit tests
5. Building an index
6. Benchmarks
7. Live demo

Installation and quick start

Just run

bash ./install

from the parent directory. The script builds the code; prepare the test data in the folder test_data/trec_05_efficiency_queries for indexing; executes the unit tests.

After that, for having a minimal running example, just run

just example

and to close the demo, press Esc.

Compiling the code

To build the code, just is required.

To compile the code for a release environment, it is sufficient to do the following:

RUSTFLAGS='-C target-cpu=native' cargo build --release

Note: The project uses the pef dependency, which is a private repository of Rossano Venturini. Ask him to grant you access or you should substitute all the implementations of Elias-Fano and BitVector.

For a testing environment, use the following instead:

cargo build

Input data format

The input file should list all completions in lexicographical order. For example, see the the file test_data/trec_05_efficiency_queries/trec_05_efficiency_queries.completions.

The first column represent the ID of the completion; the other columns contain the tokens separated by white spaces. (The IDs for the file trec_05_efficiency_queries.completions are fake, i.e., they do not take into account any particular assignment.)

The script preprocess.sh in the directory test_data helps in preparing the data for indexing the baseline version which do not handle typos. Thus, from within the directory test_data, it is sufficient to do:

bash preprocess.sh <test_collection> <num_queries>

Therefore, for our example with trec_05_efficiency_queries, it would be:

bash preprocess.sh trec_05_efficiency_queries/trec_05_efficiency_queries.completions 300

The second argument in the example, i.e., 300, represents the number of completions (per completion size) that are drawn at random and could be used to query the indexes.

If you run the script, you will get:

• trec_05_efficiency_queries.completions.dict: lists all the distinct tokens in the completions sorted in lexicographical order.

• trec_05_efficiency_queries.completions.mapped: lists all completions whose tokens have been mapped to integer ids as assigned by a lexicographically-sorted string dictionary (that should be built from the tokens listed in trec_05_efficiency_queries.completions.dict). Each completion terminates with the id 0.

• trec_05_efficiency_queries.completions.mapped.stats contains some statistics about the datasets, needed to build the data structures more efficiently.

• trec05_efficiency_queries.completions.inverted is the inverted file.

• trec_05_efficiency_queries.completions.forward is the forward file. Note that each list is not sorted, thus the lists are the same as the ones contained in trec_05_efficiency_queries.completions.mapped but sorted in docID order.

To prepare the data for the augmented version (i.e. the one that supports typos) it is needed to execute:

./target/release/build_space_efficient_fuzzy_index.rs <dataset_name>.completions

This would create new .inverted and .forward files. After that, the index should be built from scratch.

Running the unit tests

To run the tests, simply do:

cargo test

Building an index

After compiling the code, run the program just build_autocomplete <dataset_name> to build an index. Where dataset_name is the name of the dataset, without the .completions, to use.

For example, with

just build_autocomplete ./test_data/trec_05_efficiency_queries/trec_05_efficiency_queries.completions

we can build an index from the test file ./test_data/trec_05_efficiency_queries/trec_05_efficiency_queries.completions, that will be serialized to the file index_trec_05_efficiency_queries.bin.

Benchmarks

To run the top-k benchmarks, we first need some query logs. They should have been created already if you have run the script preprocess.sh, otherwise you can use

python3 partition_queries_by_length.py trec_05_efficiency_queries/trec_05_efficiency_queries.completions trec_05_efficiency_queries/trec_05_efficiency_queries.completions.queries 300

to partition the input completions by number of query terms and retain 300 queries at random. Query files are placed in the output directory trec_05_efficiency_queries/trec_05_efficiency_queries.completions.queries. (By default, 7 shards will be created: the ones having [1,6] query terms and the one collecting all completions with at least 7 query terms).

We automated the collection of results with the script script/collected_results_by_varying_percentage.py. From within the base directory, run

python3 ./script/collect_results_by_varying_percentage.py index_trec_05_efficiency_queries.bin trec_05_efficiency_queries 10 300

Live demo

Run, from the base directory:

./target/release/tui_qac.rs <index_name>

to start the TUI to use the system. To close the TUI use Esc.