3
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Tyson Williams Oct 19 '11 at 2:59
  • $\begingroup$ Tnx, it didnt introduce any errors. $\endgroup$ – NoSenseEtAl Oct 19 '11 at 12:21
2
+100
$\begingroup$

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)

| cite | improve this answer | |
$\endgroup$
6
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.