- Ubuntu
- C++ 11
- GCC 4.8
- Boost
- cmake
$ cmake .
$ make
./fora action_name --algo <algorithm> [options]
- action:
- query: static SSPPR query
- topk: static top-k query
- build: build index, for FORA only
- dynamic-ss
- dynamic-topk
- dynamic-onehop
- dynamic-hybird
- algo: which algorithm you prefer to run
- baton: Baton
- fora: FORA
- partup: Genda with partial update
- lazyup: Genda with lazy update
- resacc: ResAcc
- options
- --prefix <prefix>
- --epsilon <epsilon>
- --dataset <dataset>
- --query_size <queries count>
- --k <top k>
- --with_idx
- --beta
- --baton
The example data format is in ./data/webstanford/
folder. The data for DBLP, Pokec, Orkut, LiveJournal, Twitter are not included here for size limitation reason. You can find them online.
Generate query files for the graph data. Each line contains a node id.
$ ./fora generate-ss-query --prefix <data-folder> --dataset <graph-name> --query_size <query count>
$ ./fora gen-update --prefix <data-folder> --dataset <graph-name> --query_size <query count>
- Example:
$ ./fora generate-ss-query --prefix ./data/ --dataset webstanford --query_size 1000
Construct index files for the graph data using a single core.
Note: the code of indexing for hubppr is not included here, please turn to the code of hubppr: https://sourceforge.net/projects/hubppr/
- Example
For FORA index:
$ ./fora build --prefix ./data/ --dataset webstanford --epsilon 0.5
For BATON index:
$ ./fora build --prefix ./data/ --dataset webstanford --epsilon 0.5 --baton
Process queries.
$ ./fora <query-type> --algo <algo-name> --prefix <data-folder> --dataset <graph-name> --result_dir <output-folder> --epsilon <relative error> --query_size <query count> --update_size<update count> [--with-idx --exact]
- Example:
For static queries
// FORA without index KDD version
$ ./fora query --algo fora --prefix ./data/ --dataset webstanford --epsilon 0.5 --query_size 20
// FORA without index TODS version (balance strategy and optimization technique included)
$ ./fora query --algo fora --prefix ./data/ --dataset webstanford --epsilon 0.5 --query_size 20 --balanced --opt
// FORA with index KDD version
$ ./fora query --algo fora --prefix ./data/ --dataset webstanford --epsilon 0.5 --query_size 20 --with_idx
// FORA with index TODS version
$ ./fora query --algo fora --prefix ./data/ --dataset webstanford --epsilon 0.5 --query_size 20 --with_idx --opt
// Genda
$ ./fora query --algo genda --prefix ./data/ --dataset webstanford --epsilon 0.5 --query_size 20 --with_idx
For dynamic SSPPR:
$ ./fora dynamic-ss --algo lazyup --epsilon 0.5 --prefix ./data/ --dataset webstanford --query_size 200 --update_size 200 --beta 1 --with_idx
For dynamic top-k PPR:
$ ./fora dynamic-topk --algo lazyup --epsilon 0.5 --prefix ./data/ --dataset webstanford --query_size 200 --update_size 200 --beta 1 --with_idx
For dynamic onehop PPR:
$ ./fora dynamic-onehop --algo lazyup --epsilon 0.5 --prefix ./data/ --dataset webstanford --query_size 200 --update_size 200 --beta 1 --with_idx