<p>Essentially you reshape the secondHashTable from secondHashSize x bucketSize to secondHashSize x maxBucketSize if I understand correctly.</p>

<p>I'll run some tests to see if that improves search time.</p>

<p>I think there's still a drawback in this though - if only a few hash codes are present then we'll have few buckets, all of them full. That way we discard a lot of points due to capacity and still allocate the same size since maxBucketSize = bucketSize.</p>

<p>An idea would be to make secondHashTable from arma::Mat to arma::SpMat. The problem with this is currently we denote an empty bucket position by setting it to N, not 0, because 0 corresponds to point 0 in the reference set.<br>
So if we do SpMat we will need to change that notation everywhere, which will probably cause compatibility issues when reading saved models.<br>
Another drawback of this, is we still set a maximum number of points that secondHashTable stores per bucket - but this number can be set arbitrarily high because we're more efficient, memory-wise.<br>
A third consideration is armadillo uses compressed sparse column (not row) representation, so we'll need to transpose anything that has to do with secondHashTable in order to be more efficient.<br>
I started trying to do this but wasted 2 hours and I'm not done yet. It seemed like a quick and dirty trick but it's quite complicated :(</p>

<p>An alternative would be to have a C++ array of std::vectors. Each vector holds the contents (indices) of the corresponding bucket. This might require a little more refactoring but since vectors use only the memory they require (plus whatever they need for amortization of expansion) I think we will be better off than using SpMat.</p>

<p>Let me know what you think</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/675#issuecomment-223744179">view it on GitHub</a>, or <a href="https://github.com/notifications/unsubscribe/AJ4bFDcwDoxdM5L5bFh5sJGokQhiaYo7ks5qITiMgaJpZM4IuAcT">mute the thread</a>.<img alt="" height="1" src="https://github.com/notifications/beacon/AJ4bFKMWmml-Nedk9PlDl7PwXUVbvWLlks5qITiMgaJpZM4IuAcT.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/675#issuecomment-223744179"></link>
  <meta itemprop="name" content="View Pull Request"></meta>
</div>
<meta itemprop="description" content="View this Pull Request on GitHub"></meta>
</div>