How do I store data with a query that's a approximated ?
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.