{"action":"created","comment":{"url":"https://api.github.com/repos/mlpack/mlpack/pulls/comments/75734406","id":75734406,"diff_hunk":"@@ -506,13 +507,55 @@ class BinarySpaceTree\n    * @param oldFromNew Vector which will be filled with the old positions for\n    *    each new point.\n    */\n+  template<typename SplitInfo>\n   size_t PerformSplit(MatType& data,\n                       const size_t begin,\n                       const size_t count,\n-                      const typename Split::SplitInfo& splitInfo,\n+                      const SplitInfo& splitInfo,\n                       std::vector<size_t>& oldFromNew);\n \n   /**\n+   * An overload for the universal B tree. For the first time the function\n+   * rearranges the whole dataset. Next time the function only returns the split\n+   * column.\n+   *\n+   * @param bound The bound used for this node.\n+   * @param data The dataset used by the binary space tree.\n+   * @param begin Index of the starting point in the dataset that belongs to\n+   *    this node.\n+   * @param count Number of points in this node.\n+   * @param splitInfo The information about the split.\n+   * @param oldFromNew Vector which will be filled with the old positions for\n+   *    each new point.\n+   */\n+  size_t PerformSplit(MatType& data,\n+    const size_t begin,\n+    const size_t count,\n+    const typename UBTreeSplit<BoundType<MetricType>,\n+                               MatType>::SplitInfo& splitInfo);\n+\n+  /**\n+   * An overload for the universal B tree. For the first time the function\n+   * rearranges the whole dataset. Next time the function only returns the split\n+   * column.\n+   *\n+   * @param bound The bound used for this node.\n+   * @param data The dataset used by the binary space tree.\n+   * @param begin Index of the starting point in the dataset that belongs to\n+   *    this node.\n+   * @param count Number of points in this node.\n+   * @param splitInfo The information about the split.\n+   * @param oldFromNew Vector which will be filled with the old positions for\n+   *    each new point.\n+   */\n+  size_t PerformSplit(MatType& data,\n+    const size_t begin,\n+    const size_t count,\n+    const typename UBTreeSplit<BoundType<MetricType>,\n+                               MatType>::SplitInfo& splitInfo,\n+    std::vector<size_t>& oldFromNew);","path":"src/mlpack/core/tree/binary_space_tree/binary_space_tree.hpp","position":64,"original_position":64,"commit_id":"2c5eb5780226c30b8fb088ee928487f0970dc802","original_commit_id":"2c5eb5780226c30b8fb088ee928487f0970dc802","user":{"login":"rcurtin","id":1845039,"avatar_url":"https://avatars.githubusercontent.com/u/1845039?v=3","gravatar_id":"","url":"https://api.github.com/users/rcurtin","html_url":"https://github.com/rcurtin","followers_url":"https://api.github.com/users/rcurtin/followers","following_url":"https://api.github.com/users/rcurtin/following{/other_user}","gists_url":"https://api.github.com/users/rcurtin/gists{/gist_id}","starred_url":"https://api.github.com/users/rcurtin/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/rcurtin/subscriptions","organizations_url":"https://api.github.com/users/rcurtin/orgs","repos_url":"https://api.github.com/users/rcurtin/repos","events_url":"https://api.github.com/users/rcurtin/events{/privacy}","received_events_url":"https://api.github.com/users/rcurtin/received_events","type":"User","site_admin":false},"body":"The spacing seems odd on this line.","created_at":"2016-08-22T18:42:21Z","updated_at":"2016-08-22T18:42:21Z","html_url":"https://github.com/mlpack/mlpack/pull/746#discussion_r75734406","pull_request_url":"https://api.github.com/repos/mlpack/mlpack/pulls/746","_links":{"self":{"href":"https://api.github.com/repos/mlpack/mlpack/pulls/comments/75734406"},"html":{"href":"https://github.com/mlpack/mlpack/pull/746#discussion_r75734406"},"pull_request":{"href":"https://api.github.com/repos/mlpack/mlpack/pulls/746"}}},"pull_request":{"url":"https://api.github.com/repos/mlpack/mlpack/pulls/746","id":79582461,"html_url":"https://github.com/mlpack/mlpack/pull/746","diff_url":"https://github.com/mlpack/mlpack/pull/746.diff","patch_url":"https://github.com/mlpack/mlpack/pull/746.patch","issue_url":"https://api.github.com/repos/mlpack/mlpack/issues/746","number":746,"state":"open","locked":false,"title":"Universal B tree implementation","user":{"login":"lozhnikov","id":10090844,"avatar_url":"https://avatars.githubusercontent.com/u/10090844?v=3","gravatar_id":"","url":"https://api.github.com/users/lozhnikov","html_url":"https://github.com/lozhnikov","followers_url":"https://api.github.com/users/lozhnikov/followers","following_url":"https://api.github.com/users/lozhnikov/following{/other_user}","gists_url":"https://api.github.com/users/lozhnikov/gists{/gist_id}","starred_url":"https://api.github.com/users/lozhnikov/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/lozhnikov/subscriptions","organizations_url":"https://api.github.com/users/lozhnikov/orgs","repos_url":"https://api.github.com/users/lozhnikov/repos","events_url":"https://api.github.com/users/lozhnikov/events{/privacy}","received_events_url":"https://api.github.com/users/lozhnikov/received_events","type":"User","site_admin":false},"body":"I implemented the UB tree. Despite the tree passes all tests from `ub_tree_test.cpp` including the test that verifies `MinDistance()` and `MaxDistance()`, `KNNTest/KNNModelTest` sometimes fails, I am trying to fix that.\r\n\r\nThe bound of the UB tree consists of a number of hyperrectangles in such a way that children of the UB tree do not overlap each other. However, I realized that the calculation of the distance between two nodes requires a lot of operations. So, I had to add some limitations on the number of hyperrectangles.\r\n\r\nThe tree sorts the dataset before the split process since the tree introduces an ordering in multidimensional space and all points are inserted into the tree according to that ordering. Probably it is better to choose a number of distinct samples and to split according the median. ","created_at":"2016-08-01T14:59:07Z","updated_at":"2016-08-22T18:42:21Z","closed_at":null,"merged_at":null,"merge_commit_sha":"524f7526c227544adbb09f024d38f2168b7af02a","assignee":null,"assignees":[],"milestone":null,"commits_url":"https://api.github.com/repos/mlpack/mlpack/pulls/746/commits","review_comments_url":"https://api.github.com/repos/mlpack/mlpack/pulls/746/comments","review_comment_url":"https://api.github.com/repos/mlpack/mlpack/pulls/comments{/number}","comments_url":"https://api.github.com/repos/mlpack/mlpack/issues/746/comments","statuses_url":"https://api.github.com/repos/mlpack/mlpack/statuses/2c5eb5780226c30b8fb088ee928487f0970dc802","head":{"label":"lozhnikov:ubtree","ref":"ubtree","sha":"2c5eb5780226c30b8fb088ee928487f0970dc802","user":{"login":"lozhnikov","id":10090844,"avatar_url":"https://avatars.githubusercontent.com/u/10090844?v=3","gravatar_id":"","url":"https://api.github.com/users/lozhnikov","html_url":"https://github.com/lozhnikov","followers_url":"https://api.github.com/users/lozhnikov/followers","following_url":"https://api.github.com/users/lozhnikov/following{/other_user}","gists_url":"https://api.github.com/users/lozhnikov/gists{/gist_id}","starred_url":"https://api.github.com/users/lozhnikov/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/lozhnikov/subscriptions","organizations_url":"https://api.github.com/users/lozhnikov/orgs","repos_url":"https://api.github.com/users/lozhnikov/repos","events_url":"https://api.github.com/users/lozhnikov/events{/privacy}","received_events_url":"https://api.github.com/users/lozhnikov/received_events","type":"User","site_admin":false},"repo":{"id":53449734,"name":"mlpack","full_name":"lozhnikov/mlpack","owner":{"login":"lozhnikov","id":10090844,"avatar_url":"https://avatars.githubusercontent.com/u/10090844?v=3","gravatar_id":"","url":"https://api.github.com/users/lozhnikov","html_url":"https://github.com/lozhnikov","followers_url":"https://api.github.com/users/lozhnikov/followers","following_url":"https://api.github.com/users/lozhnikov/following{/other_user}","gists_url":"https://api.github.com/users/lozhnikov/gists{/gist_id}","starred_url":"https://api.github.com/users/lozhnikov/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/lozhnikov/subscriptions","organizations_url":"https://api.github.com/users/lozhnikov/orgs","repos_url":"https://api.github.com/users/lozhnikov/repos","events_url":"https://api.github.com/users/lozhnikov/events{/privacy}","received_events_url":"https://api.github.com/users/lozhnikov/received_events","type":"User","site_admin":false},"private":false,"html_url":"https://github.com/lozhnikov/mlpack","description":"mlpack: a scalable C++ machine learning library","fork":true,"url":"https://api.github.com/repos/lozhnikov/mlpack","forks_url":"https://api.github.com/repos/lozhnikov/mlpack/forks","keys_url":"https://api.github.com/repos/lozhnikov/mlpack/keys{/key_id}","collaborators_url":"https://api.github.com/repos/lozhnikov/mlpack/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/lozhnikov/mlpack/teams","hooks_url":"https://api.github.com/repos/lozhnikov/mlpack/hooks","issue_events_url":"https://api.github.com/repos/lozhnikov/mlpack/issues/events{/number}","events_url":"https://api.github.com/repos/lozhnikov/mlpack/events","assignees_url":"https://api.github.com/repos/lozhnikov/mlpack/assignees{/user}","branches_url":"https://api.github.com/repos/lozhnikov/mlpack/branches{/branch}","tags_url":"https://api.github.com/repos/lozhnikov/mlpack/tags","blobs_url":"https://api.github.com/repos/lozhnikov/mlpack/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/lozhnikov/mlpack/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/lozhnikov/mlpack/git/refs{/sha}","trees_url":"https://api.github.com/repos/lozhnikov/mlpack/git/trees{/sha}","statuses_url":"https://api.github.com/repos/lozhnikov/mlpack/statuses/{sha}","languages_url":"https://api.github.com/repos/lozhnikov/mlpack/languages","stargazers_url":"https://api.github.com/repos/lozhnikov/mlpack/stargazers","contributors_url":"https://api.github.com/repos/lozhnikov/mlpack/contributors","subscribers_url":"https://api.github.com/repos/lozhnikov/mlpack/subscribers","subscription_url":"https://api.github.com/repos/lozhnikov/mlpack/subscription","commits_url":"https://api.github.com/repos/lozhnikov/mlpack/commits{/sha}","git_commits_url":"https://api.github.com/repos/lozhnikov/mlpack/git/commits{/sha}","comments_url":"https://api.github.com/repos/lozhnikov/mlpack/comments{/number}","issue_comment_url":"https://api.github.com/repos/lozhnikov/mlpack/issues/comments{/number}","contents_url":"https://api.github.com/repos/lozhnikov/mlpack/contents/{+path}","compare_url":"https://api.github.com/repos/lozhnikov/mlpack/compare/{base}...{head}","merges_url":"https://api.github.com/repos/lozhnikov/mlpack/merges","archive_url":"https://api.github.com/repos/lozhnikov/mlpack/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/lozhnikov/mlpack/downloads","issues_url":"https://api.github.com/repos/lozhnikov/mlpack/issues{/number}","pulls_url":"https://api.github.com/repos/lozhnikov/mlpack/pulls{/number}","milestones_url":"https://api.github.com/repos/lozhnikov/mlpack/milestones{/number}","notifications_url":"https://api.github.com/repos/lozhnikov/mlpack/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/lozhnikov/mlpack/labels{/name}","releases_url":"https://api.github.com/repos/lozhnikov/mlpack/releases{/id}","deployments_url":"https://api.github.com/repos/lozhnikov/mlpack/deployments","created_at":"2016-03-08T22:26:22Z","updated_at":"2016-03-08T22:26:25Z","pushed_at":"2016-08-21T08:16:08Z","git_url":"git://github.com/lozhnikov/mlpack.git","ssh_url":"git@github.com:lozhnikov/mlpack.git","clone_url":"https://github.com/lozhnikov/mlpack.git","svn_url":"https://github.com/lozhnikov/mlpack","homepage":null,"size":147448,"stargazers_count":0,"watchers_count":0,"language":"C++","has_issues":false,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":0,"mirror_url":null,"open_issues_count":0,"forks":0,"open_issues":0,"watchers":0,"default_branch":"master"}},"base":{"label":"mlpack:master","ref":"master","sha":"0a19d07bd39e6223991976474bc79671ba8aa0f0","user":{"login":"mlpack","id":10216045,"avatar_url":"https://avatars.githubusercontent.com/u/10216045?v=3","gravatar_id":"","url":"https://api.github.com/users/mlpack","html_url":"https://github.com/mlpack","followers_url":"https://api.github.com/users/mlpack/followers","following_url":"https://api.github.com/users/mlpack/following{/other_user}","gists_url":"https://api.github.com/users/mlpack/gists{/gist_id}","starred_url":"https://api.github.com/users/mlpack/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/mlpack/subscriptions","organizations_url":"https://api.github.com/users/mlpack/orgs","repos_url":"https://api.github.com/users/mlpack/repos","events_url":"https://api.github.com/users/mlpack/events{/privacy}","received_events_url":"https://api.github.com/users/mlpack/received_events","type":"Organization","site_admin":false},"repo":{"id":28149409,"name":"mlpack","full_name":"mlpack/mlpack","owner":{"login":"mlpack","id":10216045,"avatar_url":"https://avatars.githubusercontent.com/u/10216045?v=3","gravatar_id":"","url":"https://api.github.com/users/mlpack","html_url":"https://github.com/mlpack","followers_url":"https://api.github.com/users/mlpack/followers","following_url":"https://api.github.com/users/mlpack/following{/other_user}","gists_url":"https://api.github.com/users/mlpack/gists{/gist_id}","starred_url":"https://api.github.com/users/mlpack/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/mlpack/subscriptions","organizations_url":"https://api.github.com/users/mlpack/orgs","repos_url":"https://api.github.com/users/mlpack/repos","events_url":"https://api.github.com/users/mlpack/events{/privacy}","received_events_url":"https://api.github.com/users/mlpack/received_events","type":"Organization","site_admin":false},"private":false,"html_url":"https://github.com/mlpack/mlpack","description":"mlpack: a scalable C++ machine learning library","fork":false,"url":"https://api.github.com/repos/mlpack/mlpack","forks_url":"https://api.github.com/repos/mlpack/mlpack/forks","keys_url":"https://api.github.com/repos/mlpack/mlpack/keys{/key_id}","collaborators_url":"https://api.github.com/repos/mlpack/mlpack/collaborators{/collaborator}","teams_url":"https://api.github.com/repos/mlpack/mlpack/teams","hooks_url":"https://api.github.com/repos/mlpack/mlpack/hooks","issue_events_url":"https://api.github.com/repos/mlpack/mlpack/issues/events{/number}","events_url":"https://api.github.com/repos/mlpack/mlpack/events","assignees_url":"https://api.github.com/repos/mlpack/mlpack/assignees{/user}","branches_url":"https://api.github.com/repos/mlpack/mlpack/branches{/branch}","tags_url":"https://api.github.com/repos/mlpack/mlpack/tags","blobs_url":"https://api.github.com/repos/mlpack/mlpack/git/blobs{/sha}","git_tags_url":"https://api.github.com/repos/mlpack/mlpack/git/tags{/sha}","git_refs_url":"https://api.github.com/repos/mlpack/mlpack/git/refs{/sha}","trees_url":"https://api.github.com/repos/mlpack/mlpack/git/trees{/sha}","statuses_url":"https://api.github.com/repos/mlpack/mlpack/statuses/{sha}","languages_url":"https://api.github.com/repos/mlpack/mlpack/languages","stargazers_url":"https://api.github.com/repos/mlpack/mlpack/stargazers","contributors_url":"https://api.github.com/repos/mlpack/mlpack/contributors","subscribers_url":"https://api.github.com/repos/mlpack/mlpack/subscribers","subscription_url":"https://api.github.com/repos/mlpack/mlpack/subscription","commits_url":"https://api.github.com/repos/mlpack/mlpack/commits{/sha}","git_commits_url":"https://api.github.com/repos/mlpack/mlpack/git/commits{/sha}","comments_url":"https://api.github.com/repos/mlpack/mlpack/comments{/number}","issue_comment_url":"https://api.github.com/repos/mlpack/mlpack/issues/comments{/number}","contents_url":"https://api.github.com/repos/mlpack/mlpack/contents/{+path}","compare_url":"https://api.github.com/repos/mlpack/mlpack/compare/{base}...{head}","merges_url":"https://api.github.com/repos/mlpack/mlpack/merges","archive_url":"https://api.github.com/repos/mlpack/mlpack/{archive_format}{/ref}","downloads_url":"https://api.github.com/repos/mlpack/mlpack/downloads","issues_url":"https://api.github.com/repos/mlpack/mlpack/issues{/number}","pulls_url":"https://api.github.com/repos/mlpack/mlpack/pulls{/number}","milestones_url":"https://api.github.com/repos/mlpack/mlpack/milestones{/number}","notifications_url":"https://api.github.com/repos/mlpack/mlpack/notifications{?since,all,participating}","labels_url":"https://api.github.com/repos/mlpack/mlpack/labels{/name}","releases_url":"https://api.github.com/repos/mlpack/mlpack/releases{/id}","deployments_url":"https://api.github.com/repos/mlpack/mlpack/deployments","created_at":"2014-12-17T18:16:59Z","updated_at":"2016-08-20T12:08:54Z","pushed_at":"2016-08-22T18:40:54Z","git_url":"git://github.com/mlpack/mlpack.git","ssh_url":"git@github.com:mlpack/mlpack.git","clone_url":"https://github.com/mlpack/mlpack.git","svn_url":"https://github.com/mlpack/mlpack","homepage":null,"size":168703,"stargazers_count":1103,"watchers_count":1103,"language":"C++","has_issues":true,"has_downloads":true,"has_wiki":true,"has_pages":false,"forks_count":383,"mirror_url":null,"open_issues_count":73,"forks":383,"open_issues":73,"watchers":1103,"default_branch":"master"}},"_links":{"self":{"href":"https://api.github.com/repos/mlpack/mlpack/pulls/746"},"html":{"href":"https://github.com/mlpack/mlpack/pull/746"},"issue":{"href":"https://api.github.com/repos/mlpack/mlpack/issues/746"},"comments":{"href":"https://api.github.com/repos/mlpack/mlpack/issues/746/comments"},"review_comments":{"href":"https://api.github.com/repos/mlpack/mlpack/pulls/746/comments"},"review_comment":{"href":"https://api.github.com/repos/mlpack/mlpack/pulls/comments{/number}"},"commits":{"href":"https://api.github.com/repos/mlpack/mlpack/pulls/746/commits"},"statuses":{"href":"https://api.github.com/repos/mlpack/mlpack/statuses/2c5eb5780226c30b8fb088ee928487f0970dc802"}}}}
{"actor":{"display_login":"rcurtin"}}