<p>Hi <a href="https://github.com/sumedhghaisas" class="user-mention">@sumedhghaisas</a>! I have implemented generalized Spill Trees, to consider general splitting hyperplanes, not necessarily axis-orthogonal.</p>

<p>I added a new template parameter for Spill Trees: <code>HyperplaneType</code>, and I implemented two candidate classes: <code>AxisOrthogonalHyperplane</code> and <code>Hyperplane</code>.</p>

<ul>
<li>
<code>AxisOrthogonalHyperplane</code> consider an axis-parallel projection vector. So, we can project any vector in O(1) time, considering the appropiate dimension.</li>
<li>
<code>Hyperplane</code> consider a general projection vector. So we can project any vector in O(d) time, through a dot product.</li>
</ul>

<p>Inside the SpillTrees, I consider BallBound for non-axis-orthogonal hyperplanes, and HrectBound for axis-orthogonal hyperplanes.<br>
Also, I replaced the methods: SplitValue() and SplitDimension() by HalfSpaceContains() and HalfSpaceIntersects(), which are more general.</p>

<p>Considering this abstraction, I managed to significantly simplify the Split methods: MeanSplit and Midpoint Split. Now, they share most of the code.</p>

<p>I think we could use this abstraction for BinarySpaceTrees too.</p>

<p>By default, SpillSearch considers <code>AxisOrthogonalHyperplanes</code> because they seem to be faster in many cases, but this is not always true. I think we should benchmark both methods and see which is faster and which is more accurate, I mean, which has the best relation between running time and relative approximation error.</p>

<p>I will add a new command line flag "--get_real_error" to compare the approximate neighbor search against the naive method and print the real relative error, so we can benchmark with different values of tau and different spill tree flavours.</p>

<p>Thanks,</p>

<p>Marcos</p>

<p style="font-size:small;-webkit-text-size-adjust:none;color:#666;">&mdash;<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/pull/747#issuecomment-237610583">view it on GitHub</a>, or <a href="https://github.com/notifications/unsubscribe-auth/AJ4bFMji_zQVBxx-lzIFPeE97DGPiFDzks5qchYBgaJpZM4JZzLU">mute the thread</a>.<img alt="" height="1" src="https://github.com/notifications/beacon/AJ4bFAo8pmth8MUfs0OtXJSmNnTbLbTqks5qchYBgaJpZM4JZzLU.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/pull/747#issuecomment-237610583"></link>
  <meta itemprop="name" content="View Pull Request"></meta>
</div>
<meta itemprop="description" content="View this Pull Request 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":"@MarcosPividori in #747: Hi @sumedhghaisas! I have implemented generalized Spill Trees, to consider general splitting hyperplanes, not necessarily axis-orthogonal.\r\n\r\nI added a new template parameter for Spill Trees: `HyperplaneType`, and I implemented two candidate classes: `AxisOrthogonalHyperplane` and `Hyperplane`.\r\n+ `AxisOrthogonalHyperplane` consider an axis-parallel projection vector. So, we can project any vector in O(1) time, considering the appropiate dimension.\r\n+ `Hyperplane` consider a general projection vector. So we can project any vector in O(d) time, through a dot product.\r\n\r\nInside the SpillTrees, I consider BallBound for non-axis-orthogonal hyperplanes, and HrectBound for axis-orthogonal hyperplanes.\r\nAlso, I replaced the methods: SplitValue() and SplitDimension() by HalfSpaceContains() and HalfSpaceIntersects(), which are more general.\r\n\r\nConsidering this abstraction, I managed to significantly simplify the Split methods: MeanSplit and Midpoint Split. Now, they share most of the code.\r\n\r\nI think we could use this abstraction for BinarySpaceTrees too.\r\n\r\nBy default, SpillSearch considers `AxisOrthogonalHyperplanes` because they seem to be faster in many cases, but this is not always true. I think we should benchmark both methods and see which is faster and which is more accurate, I mean, which has the best relation between running time and relative approximation error.\r\n\r\nI will add a new command line flag \"--get_real_error\" to compare the approximate neighbor search against the naive method and print the real relative error, so we can benchmark with different values of tau and different spill tree flavours.\r\n\r\nThanks,\r\n\r\nMarcos\r\n"}],"action":{"name":"View Pull Request","url":"https://github.com/mlpack/mlpack/pull/747#issuecomment-237610583"}}}</script>