{"action":"created","comment":{"url":"https://api.github.com/repos/spotify/annoy/pulls/comments/208345349","pull_request_review_id":144135630,"id":208345349,"node_id":"MDI0OlB1bGxSZXF1ZXN0UmV2aWV3Q29tbWVudDIwODM0NTM0OQ==","diff_hunk":"@@ -324,7 +347,129 @@ struct Angular {\n   }\n };\n \n-struct Hamming {\n+\n+struct DotProduct : Angular {\n+  template<typename S, typename T>\n+  struct ANNOY_NODE_ATTRIBUTE Node {\n+    /*\n+     * This is an extension of the Angular node with an extra attribute for the scaled norm.\n+     */\n+    S n_descendants;\n+    union {\n+      S children[2]; // Will possibly store more than 2\n+      T norm;\n+    };\n+    T dot_factor;\n+    T v[1]; // We let this one overflow intentionally. Need to allocate at least 1 to make GCC happy\n+  };\n+\n+  static const char* name() {\n+    return \"dot\";\n+  }\n+\n+  static inline size_t default_search_k(const size_t n, const size_t num_roots) {\n+    return Angular::default_search_k(n, num_roots) * 10;\n+  }\n+\n+  template<typename S, typename T>\n+  static inline T distance(const Node<S, T>* x, const Node<S, T>* y, int f) {\n+    return -dot(x->v, y->v, f);\n+  }","path":"src/annoylib.h","position":null,"original_position":122,"commit_id":"19e0f98fcc188ababd8004a8ae88e85e4ca781e9","original_commit_id":"d3ae2b5c46367421b95d6bf5d0b07a7cb0c5568a","user":{"login":"yonromai","id":1596570,"node_id":"MDQ6VXNlcjE1OTY1NzA=","avatar_url":"https://avatars0.githubusercontent.com/u/1596570?v=4","gravatar_id":"","url":"https://api.github.com/users/yonromai","html_url":"https://github.com/yonromai","followers_url":"https://api.github.com/users/yonromai/followers","following_url":"https://api.github.com/users/yonromai/following{/other_user}","gists_url":"https://api.github.com/users/yonromai/gists{/gist_id}","starred_url":"https://api.github.com/users/yonromai/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/yonromai/subscriptions","organizations_url":"https://api.github.com/users/yonromai/orgs","repos_url":"https://api.github.com/users/yonromai/repos","events_url":"https://api.github.com/users/yonromai/events{/privacy}","received_events_url":"https://api.github.com/users/yonromai/received_events","type":"User","site_admin":false},"body":"(apologies for randomly popping up here and writing an essay)\r\n\r\n@erikbern, I don't understand the rational behind using the euclidean distance here?\r\n\r\n---\r\nTo try to clarify this from an API standpoint:\r\n\r\n* The distance function is exposed to the users as follows:\r\n```py\r\nt = AnnoyIndex(2, 'dot')\r\nt.add_item(0, [0, 1])\r\nt.add_item(1, [1, 1])\r\nd = t.get_distance(0, 1)\r\n```\r\nwhere `get_distance` is defined as follows:\r\n```cpp\r\nT get_distance(S i, S j) {\r\n    return D::normalized_distance(D::distance(_get(i), _get(j), _f));\r\n  }\r\n```\r\n\r\n*  The doc does not specify anything special about the distance: \"Returns the distance between items `i` and `j`.\"\r\n\r\n* Therefore, I believe the user would expect that `t.get_distance(v_1, v_2)` would use the distance specified in `AnnoyIndex(f, {DIST})`.\r\nSo in this case it would be `dot(vectors[v_1], vectors[v_2])`. \r\n\r\n---\r\n\r\nOne issue is that `dot(x, y)` is more a similarity than a distance. I assume `-dot(...)` is more convenient than `C - dot(...)` since the dot is not normalized.\r\n\r\nI guess in this case we could return either `-dot(original_vec_i, original_vec_j)` or `1 - cos(augmented_vec_i, augmented_vec_j)`.\r\n(where `original_vec_i` is of dimension `N` and `augmented_vec_i` is of dimension `N+1`).\r\n\r\nGiven the API example above, returning the `dot` value seems to make more sense to me than returning the `cos` value.\r\n\r\n---\r\n\r\n=> @erikbern, @psobot: WDYT?","created_at":"2018-08-07T18:50:19Z","updated_at":"2018-08-07T18:50:19Z","html_url":"https://github.com/spotify/annoy/pull/303#discussion_r208345349","pull_request_url":"https://api.github.com/repos/spotify/annoy/pulls/303","author_association":"CONTRIBUTOR","_links":{"self":{"href":"https://api.github.com/repos/spotify/annoy/pulls/comments/208345349"},"html":{"href":"https://github.com/spotify/annoy/pull/303#discussion_r208345349"},"pull_request":{"href":"https://api.github.com/repos/spotify/annoy/pulls/303"}},"in_reply_to_id":205949208},"pull_request":{"url":"https://api.github.com/repos/spotify/annoy/pulls/303","id":197773460,"node_id":"MDExOlB1bGxSZXF1ZXN0MTk3NzczNDYw","html_url":"https://github.com/spotify/annoy/pull/303","diff_url":"https://github.com/spotify/annoy/pull/303.diff","patch_url":"https://github.com/spotify/annoy/pull/303.patch","issue_url":"https://api.github.com/repos/spotify/annoy/issues/303","number":303,"state":"open","locked":false,"title":"Add dot product as a distance metric.","user":{"login":"psobot","id":213293,"node_id":"MDQ6VXNlcjIxMzI5Mw==","avatar_url":"https://avatars3.githubusercontent.com/u/213293?v=4","gravatar_id":"","url":"https://api.github.com/users/psobot","html_url":"https://github.com/psobot","followers_url":"https://api.github.com/users/psobot/followers","following_url":"https://api.github.com/users/psobot/following{/other_user}","gists_url":"https://api.github.com/users/psobot/gists{/gist_id}","starred_url":"https://api.github.com/users/psobot/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/psobot/subscriptions","organizations_url":"https://api.github.com/users/psobot/orgs","repos_url":"https://api.github.com/users/psobot/repos","events_url":"https://api.github.com/users/psobot/events{/privacy}","received_events_url":"https://api.github.com/users/psobot/received_events","type":"User","site_admin":false},"body":"This PR:\r\n - adds a `DotProduct` metric, using the negative of the dot product between two vectors as a pseudo-distance metric.\r\n - makes this metric available under the string name `\"dot\"` in the standard Annoy interface\r\n - adds tests for this new metric, similar to the existing tests for the `Euclidean` metric.\r\n\r\nYou might ask - why add `dot` when we already have `angular`, which is basically just `dot` but divided by magnitude? Well, for some recommender systems (including some matrix factorization collaborative filters), the dot product between the user and item pair is a prediction of affinity between that user and item. ([Here's a great example](https://github.com/jfkirk/tensorrec/blob/master/tensorrec/tensorrec.py#L30) from @jfkirk.)","created_at":"2018-06-27T15:36:17Z","updated_at":"2018-08-07T18:50:19Z","closed_at":null,"merged_at":null,"merge_commit_sha":"650fe9fd5ea8476b39391db96d882c5b022db9a0","assignee":null,"assignees":[],"requested_reviewers":[{"login":"yonromai","id":1596570,"node_id":"MDQ6VXNlcjE1OTY1NzA=","avatar_url":"https://avatars0.githubusercontent.com/u/1596570?v=4","gravatar_id":"","url":"https://api.github.com/users/yonromai","html_url":"https://github.com/yonromai","followers_url":"https://api.github.com/users/yonromai/followers","following_url":"https://api.github.com/users/yonromai/following{/other_user}","gists_url":"https://api.github.com/users/yonromai/gists{/gist_id}","starred_url":"https://api.github.com/users/yonromai/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/yonromai/subscriptions","organizations_url":"https://api.github.com/users/yonromai/orgs","repos_url":"https://api.github.com/users/yonromai/repos","events_url":"https://api.github.com/users/yonromai/events{/privacy}","received_events_url":"https://api.github.com/users/yonromai/received_events","type":"User","site_admin":false}],"requested_teams":[],"labels":[{"id":34195866,"node_id":"MDU6TGFiZWwzNDE5NTg2Ng==","url":"https://api.github.com/repos/spotify/annoy/labels/enhancement","name":"enhancement","color":"84b6eb","default":true}],"milestone":null,"commits_url":"https://api.github.com/repos/spotify/annoy/pulls/303/commits","review_comments_url":"https://api.github.com/repos/spotify/annoy/pulls/303/comments","review_comment_url":"https://api.github.com/repos/spotify/annoy/pulls/comments{/number}","comments_url":"https://api.github.com/repos/spotify/annoy/issues/303/comments","statuses_url":"https://api.github.com/repos/spotify/annoy/statuses/19e0f98fcc188ababd8004a8ae88e85e4ca781e9","head":{"label":"psobot:dot-product","ref":"dot-product","sha":"19e0f98fcc188ababd8004a8ae88e85e4ca781e9","user":{"login":"psobot","id":213293,"node_id":"MDQ6VXNlcjIxMzI5Mw==","avatar_url":"https://avatars3.githubusercontent.com/u/213293?v=4","gravatar_id":"","url":"https://api.github.com/users/psobot","html_url":"https://github.com/psobot","followers_url":"https://api.github.com/users/psobot/followers","following_url":"https://api.github.com/users/psobot/following{/other_user}","gists_url":"https://api.github.com/users/psobot/gists{/gist_id}","starred_url":"https://api.github.com/users/psobot/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/psobot/subscriptions","organizations_url":"https://api.github.com/users/psobot/orgs","repos_url":"https://api.github.com/users/psobot/repos","events_url":"https://api.github.com/users/psobot/events{/privacy}","received_events_url":"https://api.github.com/users/psobot/received_events","type":"User","site_admin":false},"repo":{"id":138656240,"node_id":"MDEwOlJlcG9zaXRvcnkxMzg2NTYyNDA=","name":"annoy","full_name":"psobot/annoy","owner":{"login":"psobot","id":213293,"node_id":"MDQ6VXNlcjIxMzI5Mw==","avatar_url":"https://avatars3.githubusercontent.com/u/213293?v=4","gravatar_id":"","url":"https://api.github.com/users/psobot","html_url":"https://github.com/psobot","followers_url":"https://api.github.com/users/psobot/followers","following_url":"https://api.github.com/users/psobot/following{/other_user}","gists_url":"https://api.github.com/users/psobot/gists{/gist_id}","starred_url":"https://api.github.com/users/psobot/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/psobot/subscriptions","organizations_url":"https://api.github.com/users/psobot/orgs","repos_url":"https://api.github.com/users/psobot/repos","events_url":"https://api.github.com/users/psobot/events{/privacy}","received_events_url":"https://api.github.com/users/psobot/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/psobot/annoy","description":"Approximate Nearest Neighbors in C++/Python optimized for memory usage and loading/saving to disk","fork":true,"url":"https://api.github.com/repos/psobot/annoy","forks_url":"https://api.github.com/repos/psobot/annoy/forks","keys_url":"https://api.github.com/repos/psobot/annoy/keys{/key_id}","collaborators_url":"https://api.github.com/repos/psobot/annoy/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/psobot/annoy/teams","hooks_url":"https://api.github.com/repos/psobot/annoy/hooks","issue_events_url":"https://api.github.com/repos/psobot/annoy/issues/events{/number}","events_url":"https://api.github.com/repos/psobot/annoy/events","assignees_url":"https://api.github.com/repos/psobot/annoy/assignees{/user}","branches_url":"https://api.github.com/repos/psobot/annoy/branches{/branch}","tags_url":"https://api.github.com/repos/psobot/annoy/tags","blobs_url":"https://api.github.com/repos/psobot/annoy/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/psobot/annoy/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/psobot/annoy/git/refs{/sha}","trees_url":"https://api.github.com/repos/psobot/annoy/git/trees{/sha}","statuses_url":"https://api.github.com/repos/psobot/annoy/statuses/{sha}","languages_url":"https://api.github.com/repos/psobot/annoy/languages","stargazers_url":"https://api.github.com/repos/psobot/annoy/stargazers","contributors_url":"https://api.github.com/repos/psobot/annoy/contributors","subscribers_url":"https://api.github.com/repos/psobot/annoy/subscribers","subscription_url":"https://api.github.com/repos/psobot/annoy/subscription","commits_url":"https://api.github.com/repos/psobot/annoy/commits{/sha}","git_commits_url":"https://api.github.com/repos/psobot/annoy/git/commits{/sha}","comments_url":"https://api.github.com/repos/psobot/annoy/comments{/number}","issue_comment_url":"https://api.github.com/repos/psobot/annoy/issues/comments{/number}","contents_url":"https://api.github.com/repos/psobot/annoy/contents/{+path}","compare_url":"https://api.github.com/repos/psobot/annoy/compare/{base}...{head}","merges_url":"https://api.github.com/repos/psobot/annoy/merges","archive_url":"https://api.github.com/repos/psobot/annoy/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/psobot/annoy/downloads","issues_url":"https://api.github.com/repos/psobot/annoy/issues{/number}","pulls_url":"https://api.github.com/repos/psobot/annoy/pulls{/number}","milestones_url":"https://api.github.com/repos/psobot/annoy/milestones{/number}","notifications_url":"https://api.github.com/repos/psobot/annoy/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/psobot/annoy/labels{/name}","releases_url":"https://api.github.com/repos/psobot/annoy/releases{/id}","deployments_url":"https://api.github.com/repos/psobot/annoy/deployments","created_at":"2018-06-25T22:24:35Z","updated_at":"2018-06-25T22:24:37Z","pushed_at":"2018-08-01T17:21:12Z","git_url":"git://github.com/psobot/annoy.git","ssh_url":"git@github.com:psobot/annoy.git","clone_url":"https://github.com/psobot/annoy.git","svn_url":"https://github.com/psobot/annoy","homepage":null,"size":1707,"stargazers_count":0,"watchers_count":0,"language":"C++","has_issues":false,"has_projects":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":0,"mirror_url":null,"archived":false,"open_issues_count":0,"license":{"key":"apache-2.0","name":"Apache License 2.0","spdx_id":"Apache-2.0","url":"https://api.github.com/licenses/apache-2.0","node_id":"MDc6TGljZW5zZTI="},"forks":0,"open_issues":0,"watchers":0,"default_branch":"master"}},"base":{"label":"spotify:master","ref":"master","sha":"8729dccb7b4b4a9d3283531dbe5705eb98d52296","user":{"login":"spotify","id":251374,"node_id":"MDEyOk9yZ2FuaXphdGlvbjI1MTM3NA==","avatar_url":"https://avatars2.githubusercontent.com/u/251374?v=4","gravatar_id":"","url":"https://api.github.com/users/spotify","html_url":"https://github.com/spotify","followers_url":"https://api.github.com/users/spotify/followers","following_url":"https://api.github.com/users/spotify/following{/other_user}","gists_url":"https://api.github.com/users/spotify/gists{/gist_id}","starred_url":"https://api.github.com/users/spotify/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/spotify/subscriptions","organizations_url":"https://api.github.com/users/spotify/orgs","repos_url":"https://api.github.com/users/spotify/repos","events_url":"https://api.github.com/users/spotify/events{/privacy}","received_events_url":"https://api.github.com/users/spotify/received_events","type":"Organization","site_admin":false},"repo":{"id":9155431,"node_id":"MDEwOlJlcG9zaXRvcnk5MTU1NDMx","name":"annoy","full_name":"spotify/annoy","owner":{"login":"spotify","id":251374,"node_id":"MDEyOk9yZ2FuaXphdGlvbjI1MTM3NA==","avatar_url":"https://avatars2.githubusercontent.com/u/251374?v=4","gravatar_id":"","url":"https://api.github.com/users/spotify","html_url":"https://github.com/spotify","followers_url":"https://api.github.com/users/spotify/followers","following_url":"https://api.github.com/users/spotify/following{/other_user}","gists_url":"https://api.github.com/users/spotify/gists{/gist_id}","starred_url":"https://api.github.com/users/spotify/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/spotify/subscriptions","organizations_url":"https://api.github.com/users/spotify/orgs","repos_url":"https://api.github.com/users/spotify/repos","events_url":"https://api.github.com/users/spotify/events{/privacy}","received_events_url":"https://api.github.com/users/spotify/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/spotify/annoy","description":"Approximate Nearest Neighbors in C++/Python optimized for memory usage and loading/saving to disk","fork":false,"url":"https://api.github.com/repos/spotify/annoy","forks_url":"https://api.github.com/repos/spotify/annoy/forks","keys_url":"https://api.github.com/repos/spotify/annoy/keys{/key_id}","collaborators_url":"https://api.github.com/repos/spotify/annoy/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/spotify/annoy/teams","hooks_url":"https://api.github.com/repos/spotify/annoy/hooks","issue_events_url":"https://api.github.com/repos/spotify/annoy/issues/events{/number}","events_url":"https://api.github.com/repos/spotify/annoy/events","assignees_url":"https://api.github.com/repos/spotify/annoy/assignees{/user}","branches_url":"https://api.github.com/repos/spotify/annoy/branches{/branch}","tags_url":"https://api.github.com/repos/spotify/annoy/tags","blobs_url":"https://api.github.com/repos/spotify/annoy/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/spotify/annoy/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/spotify/annoy/git/refs{/sha}","trees_url":"https://api.github.com/repos/spotify/annoy/git/trees{/sha}","statuses_url":"https://api.github.com/repos/spotify/annoy/statuses/{sha}","languages_url":"https://api.github.com/repos/spotify/annoy/languages","stargazers_url":"https://api.github.com/repos/spotify/annoy/stargazers","contributors_url":"https://api.github.com/repos/spotify/annoy/contributors","subscribers_url":"https://api.github.com/repos/spotify/annoy/subscribers","subscription_url":"https://api.github.com/repos/spotify/annoy/subscription","commits_url":"https://api.github.com/repos/spotify/annoy/commits{/sha}","git_commits_url":"https://api.github.com/repos/spotify/annoy/git/commits{/sha}","comments_url":"https://api.github.com/repos/spotify/annoy/comments{/number}","issue_comment_url":"https://api.github.com/repos/spotify/annoy/issues/comments{/number}","contents_url":"https://api.github.com/repos/spotify/annoy/contents/{+path}","compare_url":"https://api.github.com/repos/spotify/annoy/compare/{base}...{head}","merges_url":"https://api.github.com/repos/spotify/annoy/merges","archive_url":"https://api.github.com/repos/spotify/annoy/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/spotify/annoy/downloads","issues_url":"https://api.github.com/repos/spotify/annoy/issues{/number}","pulls_url":"https://api.github.com/repos/spotify/annoy/pulls{/number}","milestones_url":"https://api.github.com/repos/spotify/annoy/milestones{/number}","notifications_url":"https://api.github.com/repos/spotify/annoy/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/spotify/annoy/labels{/name}","releases_url":"https://api.github.com/repos/spotify/annoy/releases{/id}","deployments_url":"https://api.github.com/repos/spotify/annoy/deployments","created_at":"2013-04-01T20:29:40Z","updated_at":"2018-08-07T13:57:32Z","pushed_at":"2018-08-01T17:21:14Z","git_url":"git://github.com/spotify/annoy.git","ssh_url":"git@github.com:spotify/annoy.git","clone_url":"https://github.com/spotify/annoy.git","svn_url":"https://github.com/spotify/annoy","homepage":null,"size":1705,"stargazers_count":3896,"watchers_count":3896,"language":"C++","has_issues":true,"has_projects":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":481,"mirror_url":null,"archived":false,"open_issues_count":17,"license":{"key":"apache-2.0","name":"Apache License 2.0","spdx_id":"Apache-2.0","url":"https://api.github.com/licenses/apache-2.0","node_id":"MDc6TGljZW5zZTI="},"forks":481,"open_issues":17,"watchers":3896,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/spotify/annoy/pulls/303"},"html":{"href":"https://github.com/spotify/annoy/pull/303"},"issue":{"href":"https://api.github.com/repos/spotify/annoy/issues/303"},"comments":{"href":"https://api.github.com/repos/spotify/annoy/issues/303/comments"},"review_comments":{"href":"https://api.github.com/repos/spotify/annoy/pulls/303/comments"},"review_comment":{"href":"https://api.github.com/repos/spotify/annoy/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/spotify/annoy/pulls/303/commits"},"statuses":{"href":"https://api.github.com/repos/spotify/annoy/statuses/19e0f98fcc188ababd8004a8ae88e85e4ca781e9"}},"author_association":"MEMBER"}}
{"actor":{"display_login":"yonromai"}}