<p>It turns out there is no need to check the separation invariant.  In the long version of the cover tree paper (<a href="https://hunch.net/%7Ejl/projects/cover_tree/paper/paper.pdf">https://hunch.net/~jl/projects/cover_tree/paper/paper.pdf</a>), they write that for implementation they take a few shortcuts, including:</p>

<blockquote>
<p>We relax the separation invariant in batch construction.</p>
</blockquote>

<p>So, since the mlpack cover tree code is based heavily on the original cover tree code, the separation invariant is also relaxed in mlpack, and there is no need to test for it.  <a href="https://github.com/mlpack/mlpack/commit/3f5503bfe71dbbda4b4551c9cdfaba8b819565ad" class="commit-link"><tt>3f5503b</tt></a> removes the test and fixes the issue.</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/issues/357#issuecomment-247360905">view it on GitHub</a>, or <a href="https://github.com/notifications/unsubscribe-auth/AJ4bFDKt6S6TXbBze11MplV6-R6Cfl-fks5qqWNsgaJpZM4DM53f">mute the thread</a>.<img alt="" height="1" src="https://github.com/notifications/beacon/AJ4bFPl5uvkE1kh7vD_HvxgLRaiSykZqks5qqWNsgaJpZM4DM53f.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/357#issuecomment-247360905"></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://cloud.githubusercontent.com/assets/143418/17495839/a5054eac-5d88-11e6-95fc-7290892c7bb5.png","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":"@rcurtin in #357: It turns out there is no need to check the separation invariant.  In the long version of the cover tree paper (https://hunch.net/~jl/projects/cover_tree/paper/paper.pdf), they write that for implementation they take a few shortcuts, including:\r\n\r\n\u003e We relax the separation invariant in batch construction.\r\n\r\nSo, since the mlpack cover tree code is based heavily on the original cover tree code, the separation invariant is also relaxed in mlpack, and there is no need to test for it.  3f5503b removes the test and fixes the issue."}],"action":{"name":"View Issue","url":"https://github.com/mlpack/mlpack/issues/357#issuecomment-247360905"}}}</script>