<p>I think that a better way is to include the position in the key of the entries; in your example you'll have: </p>

<pre><code>(1,pos0)-&gt;{set0}
(2,pos0)-&gt;{set1}
(2,pos1)-&gt;{set0}
(3,pos1)-&gt;{set1}
(3,pos2)-&gt;{set0}
(4,pos2)-&gt;{set1}
</code></pre>

<p>When you must search for an item (an ordered set) $(n_1,n_2,...,n_{15})$, you can perform the union of the sets associated to the keys $(n_1,pos0), ..., (n_{15},pos14)$, keeping track of the number of hits for each set. From the union you can finally extract the set (or sets) with 10 or more hits.</p>

<p>If this is a real problem with thousands of entries, a good RDBMS (such as MySQL) will handle the data (and searches) efficiently.</p>

<p>If you need to keep everything in memory, you can use an hash table to store the key,values $(n_i,pos_j) \rightarrow \{set_1,...,set_k\}$</p>

<p>Addendum: your problem resembles the classical problem of efficiently storing and searching word co-occurrences using <em><a href="http://en.wikipedia.org/wiki/Inverted_index" rel="nofollow">inverted indexes</a></em> (<em>Information Retrieval</em> area)</p>

CC BY-SA 3.0
2011-10-19T07:43:07.317Z
2011-10-19T08:00:54.507Z
2011-10-19T08:00:54.507Z
Marzio De Biasi
<p>If I understand the problem correctly, this looks like an instance of the <a href="http://en.wikipedia.org/wiki/Nearest_neighbor_search" rel="nofollow">Nearest Neighbor Search</a>, under the <a href="http://en.wikipedia.org/wiki/Hamming_distance" rel="nofollow">Hamming distance</a>.</p>

<p>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 <em>near</em> neighbor search (the <em>nearest</em> neighbor is one where one reports the closest dataset item).</p>

<p>If that's the problem, then the <a href="http://en.wikipedia.org/wiki/Nearest_neighbor_search" rel="nofollow">wiki page</a> may be a good start for pointers on existing work.</p>

CC BY-SA 3.0
2011-10-20T21:16:21.353Z
2011-10-21T22:15:45.070Z
2011-10-21T22:15:45.070Z
Alex Andoni
<p>My problem is generalization of the simple problem:</p>

<p>Search for item $x$ in a set $S$.</p>

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

<p>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.</p>

<p>Is there efficient way to search for a partial match?</p>

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

<pre><code>{1,2,3},//set0
{2,3,4}//set1
</code></pre>

<p>Create entries  </p>

<pre><code>1-&gt;(set0,pos0)(position is important), 2-&gt;(set0,pos1),(set1,pos0) ... (4-&gt;set1,pos2)
</code></pre>

<p>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.</p>

<p>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.</p>

<p>Of course this could go very very wrong for some distributions of preprocessed data. </p>

<p>So is there a better way?</p>

CC BY-SA 3.0
2011-10-19T02:59:44.730Z
I just edited your question to improve the presentation. (The edit will be visible after someone with enough rep approves it.) Please check that I didn't introduce any errors.
Tyson Williams
CC BY-SA 3.0
2011-10-19T12:21:31.670Z
Tnx, it didnt introduce any errors.
NoSenseEtAl
<co.combinatorics>
Searching for partial match - 1 item to be searched in $n$ preprocessed items
NoSenseEtAl
# Searching for partial match - 1 item to be searched in $n$ preprocessed items

(Asked by: username_0 on 2011-09-23)

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 > 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->(set0,pos0)(position is important), 2->(set0,pos1),(set1,pos0) ... (4->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?

**Tags:** co.combinatorics
> **Comments:**
> **username_1**: I just edited your question to improve the presentation. (The edit will be visible after someone with enough rep approves it.) Please check that I didn't introduce any errors.  
> **username_0**: Tnx, it didnt introduce any errors.  

---

## 2 answers

### Answer by username_2 on 2011-10-19. Score: 2 | Accepted answer

I think that a better way is to include the position in the key of the entries; in your example you'll have: 
(1,pos0)->{set0}
(2,pos0)->{set1}
(2,pos1)->{set0}
(3,pos1)->{set1}
(3,pos2)->{set0}
(4,pos2)->{set1}

When you must search for an item (an ordered set) $(n_1,n_2,...,n_{15})$, you can perform the union of the sets associated to the keys $(n_1,pos0), ..., (n_{15},pos14)$, keeping track of the number of hits for each set. From the union you can finally extract the set (or sets) with 10 or more hits.
If this is a real problem with thousands of entries, a good RDBMS (such as MySQL) will handle the data (and searches) efficiently.
If you need to keep everything in memory, you can use an hash table to store the key,values $(n_i,pos_j) \rightarrow \{set_1,...,set_k\}$
Addendum: your problem resembles the classical problem of efficiently storing and searching word co-occurrences using inverted indexes (Information Retrieval area)


---

### Answer by username_3 on 2011-10-20. Score: 6

If I understand the problem correctly, this looks like an instance of the [Nearest Neighbor Search](http://en.wikipedia.org/wiki/Nearest_neighbor_search), under the [Hamming distance](http://en.wikipedia.org/wiki/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](http://en.wikipedia.org/wiki/Nearest_neighbor_search) may be a good start for pointers on existing work.


---

