<p>You should explain how F works ... however I try to give you some tips.</p>

<h3>Suggestion 1</h3>

<p>The standard <strong>information retrieval</strong> approach may help you:</p>

<p>split each "<em>item</em>" in small size <em>words</em> (for example 4 digits), and build an <strong>inverted index</strong>, i.e. a table that maps each word to the items that contains it:</p>

<pre><code>word1 -&gt; item1, item2, item5, ...
word2 -&gt; item2, item3, item6, ...
...
</code></pre>

<p>Then if you must find items similar (closer) to item <strong>X</strong>:</p>

<ul>
<li>split <strong>X</strong> in words w1 w2 w3 ... w4</li>
<li>easily (and quickly) retrieve items that contains those words</li>
<li>order the retrieved items according to your F (weighting each item using the number of  common words also contained in <strong>X</strong>)</li>
</ul>

<p>You can also expand the inverted index to include the <strong>word positions</strong> if required by your function (w1#1 -> item1, item4; w1#2 -> item3, item6; ...).</p>

<p><strong>Obviously, this approach works only if your F can be rearranged and calculated only using the word co-occurences.</strong></p>

<p>The inverted index can be very large if the choosen word size is small. </p>

<h3>Suggestion 2</h3>

<p>Perhaps you can try to "fit" your data in a <strong>compressed prefix tree</strong>.</p>

<p>In the paper <a href="http://www.informatik.hu-berlin.de/forschung/gebiete/wbi/research/publications/2010/ssdbm_final.pdf" rel="nofollow">Prefix Tree Indexing for Similarity Search and
Similarity Joins on Genomic Data</a> the authors combine several techniques and implement similarity searches (and joins) on a prefix tree. </p>

<p><em>We present PETER, a prefix tree based indexing algorithm supporting
approximate search and approximate joins. Our tool supports Hamming
and edit distance as similarity measure and is available as C++ library,
as Unix command line tool, and as cartridge for a commercial database.
It combines an efficient implementation of compressed prefix trees with
advanced pre-filltering techniques that exclude many candidate strings
early.</em></p>

<p><em>...Our experiments reveal that PETER is faster by orders of magnitudes compared to the command-line tools. Compared to RDBMS, it computes similarity joins in minutes for which UDFs did not finish within a day and outperforms the built-in join methods even
in the exact case.</em></p>

CC BY-SA 3.0
2011-05-12T13:51:10.233Z
2011-05-12T14:02:18.917Z
2011-05-12T14:02:18.917Z
Marzio De Biasi
<p>I'm trying to find a way to store my data with fast access (better than O(n)).</p>

<p>My database consists of data (4096 byte strings) that represents some information about some items.<br>
The problem is, that the query is never exact. I get one Item, and then need to find the closest match using a function <code>F(a,b)</code>.</p>

<p>just an example:</p>

<pre><code>1234
3456
6466
F(a,b) = return % of similar digits  

GetClosest(1233,F) = 1234
</code></pre>

<p>The problem is that F(a,b) is a complicated algorithm, (not a proper metric).  </p>

<p>What I have now is just go over the whole database to search for the best match.<br>
Is there a kind of tree or other cluster database type that can give me faster finding complexity ?</p>

<p><strong>More information:</strong></p>

<p>F gives back a similarity value in %percentage. where 100% is a perfect match. </p>

CC BY-SA 3.0
2011-05-10T15:08:27.010Z
As phrased, your question is localized enough to be out of scope. But I suspect you're asking a more general question about approximate near neighbor searching under edit or Jaccard-type similarity measures, which **would** be in scope. If so, could you clarify ?
Suresh Venkat
CC BY-SA 3.0
2011-05-10T15:16:39.257Z
without further information on the function GetClosest you cannot hope to do better than $\Theta(n)$ on a classical computer, since it is always possible to set up the function GetClosest in such a way as to simulate unstructured search.
Artem Kaznatcheev
CC BY-SA 3.0
2011-05-10T17:55:32.930Z
Could you define "similarity value".  From what it looks like, order does matter (so 1234 and 4321 are only 25% similar) but what about contiguity?  e.g. 1234 and 3554 could be 25% similar (contiguity matters) or 50% similar (it doesn't).  Also, is the number of digits bounded?  That could possibly lead to something useful.
bbejot
CC BY-SA 3.0
2011-05-12T12:29:00.027Z
Looks off-topic to me by this site's standards, but anyway: - does the function have any other relevant properties? - if it's really a fixed function, is precomputing it not fast enough? I ask pretty much same question [here](http://stackoverflow.com/questions/1889065/fast-similarity-detection).
reinierpost
CC BY-SA 3.0
2011-05-12T16:14:06.230Z
meta discussion on scope here: http://meta.cstheory.stackexchange.com/questions/1141/out-of-scope-question-with-ongoing-discussion
Suresh Venkat
CC BY-SA 3.0
2011-05-12T17:24:05.770Z
It appears to me that this is the Nearest Neighbor Problem with distance being measured as Hamming distance.  See the wikipedia page on the problem: http://en.wikipedia.org/wiki/Nearest_neighbor_search
bbejot
CC BY-SA 3.0
2011-05-12T18:36:48.853Z
It's been two days, and I don't yet see any clarification that would justify keeping the question alive. I'll close it now - please go to the meta post for more discussion.
Suresh Venkat
<ds.data-structures>
How do I store data with a query that's a approximated ?
Yochai Timmer
# How do I store data with a query that's a approximated ?

(Asked by: username_0 on 2011-05-10)

I'm trying to find a way to store my data with fast access (better than O(n)).
My database consists of data (4096 byte strings) that represents some information about some items.
The problem is, that the query is never exact. I get one Item, and then need to find the closest match using a function F(a,b).
just an example:
1234
3456
6466
F(a,b) = return % of similar digits  

GetClosest(1233,F) = 1234

The problem is that F(a,b) is a complicated algorithm, (not a proper metric).  
What I have now is just go over the whole database to search for the best match.
Is there a kind of tree or other cluster database type that can give me faster finding complexity ?
More information:
F gives back a similarity value in %percentage. where 100% is a perfect match.

**Tags:** ds.data-structures
> **Comments:**
> **username_1**: As phrased, your question is localized enough to be out of scope. But I suspect you're asking a more general question about approximate near neighbor searching under edit or Jaccard-type similarity measures, which **would** be in scope. If so, could you clarify ?  
> **username_2**: without further information on the function GetClosest you cannot hope to do better than $\Theta(n)$ on a classical computer, since it is always possible to set up the function GetClosest in such a way as to simulate unstructured search.  
> **username_3**: Could you define "similarity value".  From what it looks like, order does matter (so 1234 and 4321 are only 25% similar) but what about contiguity?  e.g. 1234 and 3554 could be 25% similar (contiguity matters) or 50% similar (it doesn't).  Also, is the number of digits bounded?  That could possibly lead to something useful.  
> **username_4**: Looks off-topic to me by this site's standards, but anyway: - does the function have any other relevant properties? - if it's really a fixed function, is precomputing it not fast enough? I ask pretty much same question [here](http://stackoverflow.com/questions/1889065/fast-similarity-detection).  
> **username_1**: meta discussion on scope here: http://meta.cstheory.stackexchange.com/questions/1141/out-of-scope-question-with-ongoing-discussion  
> **username_3**: It appears to me that this is the Nearest Neighbor Problem with distance being measured as Hamming distance.  See the wikipedia page on the problem: http://en.wikipedia.org/wiki/Nearest_neighbor_search  
> **username_1**: It's been two days, and I don't yet see any clarification that would justify keeping the question alive. I'll close it now - please go to the meta post for more discussion.  

---

## 1 answers

### Answer by username_5 on 2011-05-12. Score: 3

You should explain how F works ... however I try to give you some tips.
Suggestion 1
The standard information retrieval approach may help you:
split each "item" in small size words (for example 4 digits), and build an inverted index, i.e. a table that maps each word to the items that contains it:
word1 -> item1, item2, item5, ...
word2 -> item2, item3, item6, ...
...

Then if you must find items similar (closer) to item X:

split X in words w1 w2 w3 ... w4
easily (and quickly) retrieve items that contains those words
order the retrieved items according to your F (weighting each item using the number of  common words also contained in X)

You can also expand the inverted index to include the word positions if required by your function (w1#1 -> item1, item4; w1#2 -> item3, item6; ...).
Obviously, this approach works only if your F can be rearranged and calculated only using the word co-occurences.
The inverted index can be very large if the choosen word size is small. 
Suggestion 2
Perhaps you can try to "fit" your data in a compressed prefix tree.
In the paper Prefix Tree Indexing for Similarity Search and
Similarity Joins on Genomic Data the authors combine several techniques and implement similarity searches (and joins) on a prefix tree. 
We present PETER, a prefix tree based indexing algorithm supporting
approximate search and approximate joins. Our tool supports Hamming
and edit distance as similarity measure and is available as C++ library,
as Unix command line tool, and as cartridge for a commercial database.
It combines an efficient implementation of compressed prefix trees with
advanced pre-filltering techniques that exclude many candidate strings
early.
...Our experiments reveal that PETER is faster by orders of magnitudes compared to the command-line tools. Compared to RDBMS, it computes similarity joins in minutes for which UDFs did not finish within a day and outperforms the built-in join methods even
in the exact case.


---

