Paper: https://eprint.iacr.org/2024/1600

We implement a sublinear query cost private vector ANN search algorithm based on PianoPIR and Graph-based ANN.

• Dependency
• Usage
• Contributing
• License

1. Install Go 1.22.
2. Install the dependency of NGT. Instruction can be found here (https://github.com/yahoojapan/NGT)
3. Install the dependency of hnswgo: HNSWGO(https://github.com/evan176/hnswgo)
4. Run go mod tidy to download the go module dependencies.
5. Download the SIFT dataset (http://corpus-texmex.irisa.fr/). Run sh SIFT-download.sh. It takes a while -- the dataset is around 100GB. Warning: it could take hours to download and extrat the files. It's recommended to run it in the background. Make sure the disk space is enough (>230GB).

1. To run the private search algorithm: sh run-private-search.sh. See the report in private-search-report.txt. The parameters can be changed by modifying the script file.

Optional:

1. To run the NGT non-private ANN for quality comparison: sh run-ngt-search.sh. See the report in ngt-report.txt.
2. To run the cluster-based algorithm for quality comparison: sh run-cluster-search.sh. See the report in cluster-report.txt. (Requiring the FAISS package. To download it: pip install faiss-cpu)
3. To test the latency of an optimized inner product baseline (as what we used in the paper):

• a. cd graphann
• b. go test -v -run InnerProduct (you can go into graphann_test.go and see the parameters)

This project is licensed under the MIT License - see the LICENSE file for details.

mingxunz@andrew.cmu.edu