This repo holds the source code and scripts for our paper: Pivot Selection Algorithms in Metric Spaces: An Experimental Evaluation,To appear in The VLDB Journal (VLDBJ), 2021.
Details can be refferred to https://github.com/ZJU-DBL/PSAMS
- Datasets and Pivots
The used datasets has the following files: *.txt *_qid.txt *_query.txt
The first file contains all the data, and the first line for datasets except 'words' denotes the size, the dimention and the distance metric (taking 1 as an example, it means L-1 Norm Distance).
The second and the third file contains the ids and the values for the quries.
- Index
After asking the authors for the codes of all the three indexes, we only get the execute file.
The file 'indexes' contains the execute files for LAESA (LAESA_Float.exe, LAESA_String.exe), MVP tree (MVP_Tree_Float.exe, MVP_Tree_String.exe) and SPB (SPB_Tree_Float.exe, SPB_Tree_String.exe) tree. In the sub folder, 'input.txt' is the input file for all the exe files. The sample input is as follow:
sample.txt
sample_qid.txt
sample_query.txt
pivot/pivotsample.txt 5
cost_sample.txt
1 5 10 20 50 100
2 3 4 5 6 8 10
5
The first three lines denotes the path of datasets and queries as explained before. The 4th line contains path of the tested pivot and the corresponding pivot number. The 5th line indicates the output file. The 6th and 7th line are 6 and 7 numbers seperately, which denotes the k for k-nearest neighbour query and r for range query. The last line denotes th size of the query.
After filling 'fil.in', simply runs the exe file and the output file will be generated to the given path.
| Algorithm | Paper | Year |
|---|---|---|
| SSS | Spatial Selection of Sparse Pivots for Similarity Search in Metric Spaces | 2007 |
| FFT | A Best Possible Heuristic for the k-Center Problem | 1985 |
| BPP | A comparison of pivot selection techniques for permutation-based indexing | 2015 |
| BPS | A new version of the nearestneighbour approximating and eliminating search algorithm (AESA) with linear preprocessing time and memory requirements | 1994 |
| HF | The Omni-family of all-purpose access methods: a simple and effective way to make similarity search more efficient | 2007 |
| MV | Reference-based indexing for metric spaces with costly distance measures | 2008 |
| SC | Selecting vantage objects for similarity indexing | 2006 |
| PCA | Pivot selection: Dimension reduction for distance-based indexing | 2012 |
| IS | Pivot selection techniques for proximity searching in metric spaces | 2003 |
| DSSS | A Dynamic Pivot Selection Technique for Similarity Search | 2008 |
| HFI | Efficient metric indexing for similarity search | 2015 |
Each dataset can be obtained from the following links.
| Dataset | link | Dimension |
|---|---|---|
| LA | http://www.dbs.informatik.uni-muenchen.de/ | 2 |
| Words | http://icon.shef.ac.uk/Moby/ | 1~34 |
| Color | http://cophir.isti.cnr.it/ | 282 |
| INT | 20 |
The dataset INT and examples for each dataset are included in the folder dataset.
The specific k for k-nearest neighbour query and r for range query are as belows:
| Dataset | Range for 1%, 2%, 4%, 8%, 16%, 32%, 64% |
|---|---|
| LA | 473, 692, 989, 1409, 1875, 2314, 3096 |
| Integer | 2321,2733, 3229,3843, 4614, 5613, 7090 |
| Color | 3838, 4092, 4399, 4773, 5241, 5904, 7104 |
| Words | 2, 3, 4, 5, 6, 8, 10 |
If you use our code for research work, please cite our paper as below:
@article{,
title={Pivot Selection Algorithms in Metric Spaces: An Experimental Evaluation},
author={Yifan Zhu, Lu Chen, Yunjun Gao, Christian S. Jensen},
journal={VLDBJ}
year={2021},
}