Searching for partial match - 1 item to be searched in $n$ preprocessed items My problem is generalization of the simple problem:

Search for item $x$ in a set $S$.

This is trivial to do it fast if the elements are comparable. Sort the $S$, and do the binary search.  

My problem is that I'm interested in partial match. That is, my items are ordered sets of $n = 15$ numbers, and I consider them equal if they have $m = 10$ numbers (at same position) same. For smaller numbers (like 5 out of 6), I can use $n = 6$ sorted sets that have all $m = 5$ number subsets of preprocessed items and then just do 6 binary searches. But for large numbers $n$ and $m$ where $n - m &gt; 2$ number of sets (the binomial coefficient) explodes.

Is there efficient way to search for a partial match?

The only thing that I could think of is to index each number of the set. For example, when preprocessing size 3 sets:

{1,2,3},//set0
{2,3,4}//set1


Create entries  

1-&gt;(set0,pos0)(position is important), 2-&gt;(set0,pos1),(set1,pos0) ... (4-&gt;set1,pos2)


and then when I get a new number, I just go for the each number in it and check the sets in which it appears. If there is a set that has many hits (say 10 or more), they are declared the same.

Of course I could use an array trick (i.e. array[1234] contains the pointer to the list of sets that contain 1234). This works for small ranges. For large ranges, I could hash the number and do modulo.

Of course this could go very very wrong for some distributions of preprocessed data. 

So is there a better way?
If I understand the problem correctly, this looks like an instance of the Nearest Neighbor Search, under the Hamming distance.

In other words, the "distance" between ordered sets is just the number of mismatched positions. The goal is to preprocess a collection (dataset) of ordered sets, each of size n, so that given a "query" ordered set, the data structure reports an ordered set within Hamming distance n-m. In your case, n is the dimension, and n-m is the distance. (This variant is actually called near neighbor search (the nearest neighbor is one where one reports the closest dataset item).

If that's the problem, then the wiki page may be a good start for pointers on existing work.