How do I store data with a query that's a approximated ? 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.
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 -&gt; item1, item2, item5, ...
word2 -&gt; 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.