search

FALCONN-LIB / FALCONN

FAst Lookups of Cosine and Other Nearest Neighbors (based on fast locality-sensitive hashing)
http://falconn-lib.org/
MIT License
1.14k stars 195 forks source link

can't find the right one using falconn v 1.3.1 #90

Open SueeH opened 7 years ago

SueeH commented 7 years ago

I built a hash table with about 20,000 data, feature dimension is 256, but when using find_k_nearest_neighbors ,it can't find the right one; and when using [get_unique_candidates] , it may return 2000~4000 candidates, including the right one ; still i search all the data one by one ,

the final result is same as get_unique_candidates. For example When using find_k_nearest_neighbors (in our case k =9) can not find the shortest distance FuMingming, and may return 9 candidates with distance 0.66~0.7; so the right one is missed; while using get_unique_candidates or get_duplicate_candidates it can find the right one ;

example

![Uploading example.jpg…]()

ludwigschmidt commented 7 years ago

Internally, find_k_nearest_neighbors relies on the methods for finding candidates. So in principle what you described shouldn't happen.

Just to clarify: what distance function are you using when you find the nearest neighbor yourself among the candidates returned by get_unique_candidates?

SueeH commented 7 years ago

I use Euclidean distance，for two normalized vector v1 v2，||v1-v2|| is calculated . Is any possible falconn v1.3.1 only find the local optimal value, rather than the global optimal value？

ludwigschmidt commented 7 years ago

FALCONN can certainly miss the nearest neighbor. But if the nearest neighbor appears in the candidate set, FALCONN should find it.

What distance function are you using when you set up the FALCONN data structure?

SueeH commented 7 years ago

I used parameter as follows: params_hp.dimension = veclen; params_hp.lsh_family = LSHFamily::CrossPolytope; params_hp.distance_function = DistanceFunction::EuclideanSquared; params_hp.storage_hash_table = StorageHashTable::BitPackedFlatHashTable; params_hp.k =2; params_hp.l = 10; params_hp.feature_hashing_dimension = 8; params_hp.last_cp_dimension = 8; params_hp.num_rotations = 3; params_hp.num_setup_threads = 0; params_hp.seed = seed ^ 833840234; and set_num_probes(2464);