{"action":"created","issue":{"url":"https://api.github.com/repos/lvdmaaten/bhtsne/issues/41","repository_url":"https://api.github.com/repos/lvdmaaten/bhtsne","labels_url":"https://api.github.com/repos/lvdmaaten/bhtsne/issues/41/labels{/name}","comments_url":"https://api.github.com/repos/lvdmaaten/bhtsne/issues/41/comments","events_url":"https://api.github.com/repos/lvdmaaten/bhtsne/issues/41/events","html_url":"https://github.com/lvdmaaten/bhtsne/pull/41","id":178340916,"number":41,"title":"Eliminated sqrt from VpTree distance calculation","user":{"login":"make","id":70431,"avatar_url":"https://avatars.githubusercontent.com/u/70431?v=3","gravatar_id":"","url":"https://api.github.com/users/make","html_url":"https://github.com/make","followers_url":"https://api.github.com/users/make/followers","following_url":"https://api.github.com/users/make/following{/other_user}","gists_url":"https://api.github.com/users/make/gists{/gist_id}","starred_url":"https://api.github.com/users/make/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/make/subscriptions","organizations_url":"https://api.github.com/users/make/orgs","repos_url":"https://api.github.com/users/make/repos","events_url":"https://api.github.com/users/make/events{/privacy}","received_events_url":"https://api.github.com/users/make/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":2,"created_at":"2016-09-21T13:04:51Z","updated_at":"2016-09-22T07:03:27Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/lvdmaaten/bhtsne/pulls/41","html_url":"https://github.com/lvdmaaten/bhtsne/pull/41","diff_url":"https://github.com/lvdmaaten/bhtsne/pull/41.diff","patch_url":"https://github.com/lvdmaaten/bhtsne/pull/41.patch"},"body":"Optimized ball tree building phase to perform in 20% - 30% of original cpu time by eliminating sqrt from distance calculation."},"comment":{"url":"https://api.github.com/repos/lvdmaaten/bhtsne/issues/comments/248827988","html_url":"https://github.com/lvdmaaten/bhtsne/pull/41#issuecomment-248827988","issue_url":"https://api.github.com/repos/lvdmaaten/bhtsne/issues/41","id":248827988,"user":{"login":"make","id":70431,"avatar_url":"https://avatars.githubusercontent.com/u/70431?v=3","gravatar_id":"","url":"https://api.github.com/users/make","html_url":"https://github.com/make","followers_url":"https://api.github.com/users/make/followers","following_url":"https://api.github.com/users/make/following{/other_user}","gists_url":"https://api.github.com/users/make/gists{/gist_id}","starred_url":"https://api.github.com/users/make/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/make/subscriptions","organizations_url":"https://api.github.com/users/make/orgs","repos_url":"https://api.github.com/users/make/repos","events_url":"https://api.github.com/users/make/events{/privacy}","received_events_url":"https://api.github.com/users/make/received_events","type":"User","site_admin":false},"created_at":"2016-09-22T07:03:27Z","updated_at":"2016-09-22T07:03:27Z","body":"Yes, you are right.\r\n\r\nI found now that eliminating the sqrt doesn't boost performance at all.\r\nFound also that triangle inequality test becomes into triangle acuity test when using squared distances.\r\nSo the boost came from changing the triangle inequality test into triangle acuity test that reduces the count of search paths dramatically.\r\nThe marvelous thing is that acuity test seems to work somewhat nicely (at least in my case) when finding nearest neighbors. It seems that the node is more likely to contain k-nearest neighbor when dist, _tau and threshold form an acute triangle.\r\n\r\nDo you have an idea of the effect of leaving obtuse triangles searched?\r\n\r\n![iter_05650](https://cloud.githubusercontent.com/assets/70431/18739255/f93173d0-80aa-11e6-9e23-046db81bc804.png)\r\n\r\nIn the images above the left one is original image and the right is calculated using vptree with squared euclidean distance. I am using data set of 821620 samples with 200 dimensions and external initializing for Y."}}
{"actor":{"display_login":"make"}}