title: Is there a search algorithm for huge two-dimensional arrays?
body: <p>This is not a real-life question, it is just theory-crafting.</p>
  
  <p>I have a big array which consists of elements like <code>[1,140,245,123443]</code>, all
  integer or floats with low selectivity, and the number of unique values is ten
  times less than the size of the array. B*tree indexing is not good in this case.</p>
  
  <p>I also tried to implement bitmap indexing, but in Ruby, binary operations are not so fast.</p>
  
  <p>Are there any good algorithms for searching two-dimensional arrays of fixed size vectors?</p>
  
  <p>And, the main question is, how do I convert the vector in value, where the conversion function has to be monotonic, so I can apply range queries such as:</p>
  
  <pre><code>(v[0]&lt;10, v[2]&gt;100, v[3]=32, 0.67*10^-8&lt;v[4]&lt;1.2154241410*10^-6)
  </code></pre>
  
  <p>the only idea i have is to create separate sorted indexes for each component of vector...binary search then and merge...but it is a bad idea because in the worst case scenario it will require O(N*N) operations...</p>