Hey Marcos,<br>
<br>
I will look at yiur code tonight. I will also be available online so we can<br>
discuss about it. Will you be free tonight??<br>
<br>
Regards,<br>
Sumedh Ghaisas<br>
<br>
On 01-Aug-2016 10:46 PM, "MarcosPividori" <notifications@github.com> wrote:<br>
<br>
> Hi @sumedhghaisas <https://github.com/sumedhghaisas> @rcurtin<br>
> <https://github.com/rcurtin>,<br>
><br>
> I have implemented Spill trees with axis-parallel splitting hyperplanes. I<br>
> have made an effort to avoid duplicating existing code for neighbor search.<br>
><br>
> I created a new class SpillSearch that provides an interface similar to<br>
> NeighborSearch but with an extension to properly set the tau parameter.<br>
> It encapsulates an instance of NeighborSearch.<br>
><br>
> Also, I have implemented a new version of NeighborSearchRules specialized<br>
> for Spill Trees, because I needed to modify the methods:<br>
><br>
> - Score() to consider splitting hyperplanes for overlapping nodes.<br>
> - CalculateBounds() to ignore B_2 bound (we can not use B_2 bound for<br>
> Spill Trees).<br>
><br>
> Single Tree Search:<br>
><br>
> The SingleTreeTraverser is similar to the implementation for<br>
> BinarySpaceTree.<br>
> The difference is in the implementation of NeighborSearchRules for<br>
> SpillTrees.<br>
> When calculating the score of a query point and a reference node I<br>
> consider 2 cases:<br>
><br>
> - If the reference node is non-overlapping, I calculate the score the<br>
> same than before.<br>
> - If the reference node is overlapping, I analyze the reference node's<br>
> half space. If it contains the given query point, I return 0 (best score).<br>
> Else, I return DBL_MAX (prune).<br>
><br>
> Dual Tree Search:<br>
><br>
> The Query tree is built without overlapping.<br>
><br>
> When calculating the score of a query node and a reference node, I<br>
> consider 2 cases:<br>
><br>
> - If the reference node is a non-overlapping node, I calculate the<br>
> score the same as before.<br>
> - If the reference node is a overlapping node, I analyze query node's<br>
> bounding box. If it intersects the reference node's half space, I return 0<br>
> (best score). Else, I return DBL_MAX (prune).<br>
><br>
> The DualTreeTraverser is slightly different to the implementation for<br>
> BinarySpaceTree. When referenceNode is a overlapping node and we can't<br>
> decide which child node to traverse, this means that queryNode is at both<br>
> sides of the splitting hyperplane, we analyse the queryNode:<br>
><br>
> - If queryNode is a non-leaf node, I recurse down the query node.<br>
> - If queryNode is a leaf node, I do single tree search for each point<br>
> in the query node.<br>
><br>
> The DualTreeTraverser is faster than the SingleTreeTraverser. Specially<br>
> when the value of tau increases, because we will have more non-overlapping<br>
> nodes which implies more time involved in backtracking.<br>
><br>
> The extension was incorporated to existing *mlpack_knn*. With actual<br>
> implementation, we can use *"-t spill"* to consider spill trees and *"--tau<br>
> 0.1"* to set different values for the overlapping size (default value is<br>
> tau=0).<br>
><br>
> I have made a pull request with this implementation in: #747<br>
> <https://github.com/mlpack/mlpack/pull/747>.<br>
><br>
> If you agree, I plan to work next days in these topics:<br>
><br>
> - Implement another version of SpillTrees to consider<br>
> non-axis-parallel hyperplanes, using BallBound instead of HrectBound,<br>
> and holding a projection vector in each node.<br>
> - Add a command line flag *"--get_real_error"* to compare the<br>
> approximate neighbor search against the naive method and print the real<br>
> relative error, so we can test with differents values of tau and see the<br>
> difference.<br>
><br>
> Every feedback is welcome! :)<br>
><br>
> Thanks<br>
><br>
> —<br>
> You are receiving this because you were mentioned.<br>
> Reply to this email directly, view it on GitHub<br>
> <https://github.com/mlpack/mlpack/issues/728#issuecomment-236645481>, or mute<br>
> the thread<br>
> <https://github.com/notifications/unsubscribe-auth/AFC3QaeOekficTE9vjQxBLZS9OloQoxeks5qbinwgaJpZM4JQY7d><br>
> .<br>
><br>
<p style="font-size:small;-webkit-text-size-adjust:none;color:#666;">—<br />You are receiving this because you are subscribed to this thread.<br />Reply to this email directly, <a href="https://github.com/mlpack/mlpack/issues/728#issuecomment-237148866">view it on GitHub</a>, or <a href="https://github.com/notifications/unsubscribe-auth/AJ4bFFWpIr7NrzELl8FlqNoMFkygSrgjks5qcC0mgaJpZM4JQY7d">mute the thread</a>.<img alt="" height="1" src="https://github.com/notifications/beacon/AJ4bFMrqj1qwj_3ZWDOdCJUoBVSx6KrUks5qcC0mgaJpZM4JQY7d.gif" width="1" /></p>
<div itemscope itemtype="http://schema.org/EmailMessage">
<div itemprop="action" itemscope itemtype="http://schema.org/ViewAction">
<link itemprop="url" href="https://github.com/mlpack/mlpack/issues/728#issuecomment-237148866"></link>
<meta itemprop="name" content="View Issue"></meta>
</div>
<meta itemprop="description" content="View this Issue on GitHub"></meta>
</div>
<script type="application/json" data-scope="inboxmarkup">{"api_version":"1.0","publisher":{"api_key":"05dde50f1d1a384dd78767c55493e4bb","name":"GitHub"},"entity":{"external_key":"github/mlpack/mlpack","title":"mlpack/mlpack","subtitle":"GitHub repository","main_image_url":"https://assets-cdn.github.com/images/modules/aws/aws-bg.jpg","avatar_image_url":"https://cloud.githubusercontent.com/assets/143418/15842166/7c72db34-2c0b-11e6-9aed-b52498112777.png","action":{"name":"Open in GitHub","url":"https://github.com/mlpack/mlpack"}},"updates":{"snippets":[{"icon":"PERSON","message":"@sumedhghaisas in #728: Hey Marcos,\n\nI will look at yiur code tonight. I will also be available online so we can\ndiscuss about it. Will you be free tonight??\n\nRegards,\nSumedh Ghaisas\n\nOn 01-Aug-2016 10:46 PM, \"MarcosPividori\" \u003cnotifications@github.com\u003e wrote:\n\n\u003e Hi @sumedhghaisas \u003chttps://github.com/sumedhghaisas\u003e @rcurtin\n\u003e \u003chttps://github.com/rcurtin\u003e,\n\u003e\n\u003e I have implemented Spill trees with axis-parallel splitting hyperplanes. I\n\u003e have made an effort to avoid duplicating existing code for neighbor search.\n\u003e\n\u003e I created a new class SpillSearch that provides an interface similar to\n\u003e NeighborSearch but with an extension to properly set the tau parameter.\n\u003e It encapsulates an instance of NeighborSearch.\n\u003e\n\u003e Also, I have implemented a new version of NeighborSearchRules specialized\n\u003e for Spill Trees, because I needed to modify the methods:\n\u003e\n\u003e - Score() to consider splitting hyperplanes for overlapping nodes.\n\u003e - CalculateBounds() to ignore B_2 bound (we can not use B_2 bound for\n\u003e Spill Trees).\n\u003e\n\u003e Single Tree Search:\n\u003e\n\u003e The SingleTreeTraverser is similar to the implementation for\n\u003e BinarySpaceTree.\n\u003e The difference is in the implementation of NeighborSearchRules for\n\u003e SpillTrees.\n\u003e When calculating the score of a query point and a reference node I\n\u003e consider 2 cases:\n\u003e\n\u003e - If the reference node is non-overlapping, I calculate the score the\n\u003e same than before.\n\u003e - If the reference node is overlapping, I analyze the reference node's\n\u003e half space. If it contains the given query point, I return 0 (best score).\n\u003e Else, I return DBL_MAX (prune).\n\u003e\n\u003e Dual Tree Search:\n\u003e\n\u003e The Query tree is built without overlapping.\n\u003e\n\u003e When calculating the score of a query node and a reference node, I\n\u003e consider 2 cases:\n\u003e\n\u003e - If the reference node is a non-overlapping node, I calculate the\n\u003e score the same as before.\n\u003e - If the reference node is a overlapping node, I analyze query node's\n\u003e bounding box. If it intersects the reference node's half space, I return 0\n\u003e (best score). Else, I return DBL_MAX (prune).\n\u003e\n\u003e The DualTreeTraverser is slightly different to the implementation for\n\u003e BinarySpaceTree. When referenceNode is a overlapping node and we can't\n\u003e decide which child node to traverse, this means that queryNode is at both\n\u003e sides of the splitting hyperplane, we analyse the queryNode:\n\u003e\n\u003e - If queryNode is a non-leaf node, I recurse down the query node.\n\u003e - If queryNode is a leaf node, I do single tree search for each point\n\u003e in the query node.\n\u003e\n\u003e The DualTreeTraverser is faster than the SingleTreeTraverser. Specially\n\u003e when the value of tau increases, because we will have more non-overlapping\n\u003e nodes which implies more time involved in backtracking.\n\u003e\n\u003e The extension was incorporated to existing *mlpack_knn*. With actual\n\u003e implementation, we can use *\"-t spill\"* to consider spill trees and *\"--tau\n\u003e 0.1\"* to set different values for the overlapping size (default value is\n\u003e tau=0).\n\u003e\n\u003e I have made a pull request with this implementation in: #747\n\u003e \u003chttps://github.com/mlpack/mlpack/pull/747\u003e.\n\u003e\n\u003e If you agree, I plan to work next days in these topics:\n\u003e\n\u003e - Implement another version of SpillTrees to consider\n\u003e non-axis-parallel hyperplanes, using BallBound instead of HrectBound,\n\u003e and holding a projection vector in each node.\n\u003e - Add a command line flag *\"--get_real_error\"* to compare the\n\u003e approximate neighbor search against the naive method and print the real\n\u003e relative error, so we can test with differents values of tau and see the\n\u003e difference.\n\u003e\n\u003e Every feedback is welcome! :)\n\u003e\n\u003e Thanks\n\u003e\n\u003e —\n\u003e You are receiving this because you were mentioned.\n\u003e Reply to this email directly, view it on GitHub\n\u003e \u003chttps://github.com/mlpack/mlpack/issues/728#issuecomment-236645481\u003e, or mute\n\u003e the thread\n\u003e \u003chttps://github.com/notifications/unsubscribe-auth/AFC3QaeOekficTE9vjQxBLZS9OloQoxeks5qbinwgaJpZM4JQY7d\u003e\n\u003e .\n\u003e\n"}],"action":{"name":"View Issue","url":"https://github.com/mlpack/mlpack/issues/728#issuecomment-237148866"}}}</script>