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

F gives back a similarity value in %percentage. where 100% is a perfect match.

• Can you explain a bit more about `F()` - specifically if it is a function of just the data in one row or more than one. Is `F()` different to `GetClosest()`?. Not sure if we are in function based indexes territory here. It might also help to reformulate the question in database terms spelling out fields and so on (even if you have to simplify from your real schema). May 10, 2011 at 10:37
• F(a,b) is a function that returns a %Percentage of similarity, like how much a is similar to b. I'l update the question to try and be clearer May 10, 2011 at 11:26
• How many rows in the table? Have you considered associative table containing precomputed value from all combinations? May 10, 2011 at 12:01
• Can't do precomputed values. The query is always from an item that is not inside the database, and i need to find the closest match from within the database. May 10, 2011 at 12:19
• so `GetClosest(1233)=1234` where `GetClosest` is something like: `select data from table order by F(1233, data) desc limit 1`. If you want better than O(n) we are going to need some more information. Can you combine `F(a,b)` and `F(a,c)` to say something about `F(b,c)`? For example can you say if `F(a,b)`=90% and `F(a,c)`=90% then `F(b,c)`>=80%? May 10, 2011 at 12:50

You may want to try the retrieval (re trie val) tree, as known as the TRIE. Some refer to this as a Radix Tree.

The idea is to create tree node structures that contain branches for every character your data field can possibly contain.

Let's use a simple case, a numeric field. Obviously, the character range is 0-9. Each tree node would contain ten(10) branches. Let's take the worst case for a 4 byte unsigned integer, 2^32 - 1, which is 4294967295. What is its length? Just compute the length by take the integer of the log base 10 of 4294967295 and adding 1.

``````mysql> select floor(log10(power(2,32)) + 1);
+-------------------------------+
| floor(log10(power(2,32)) + 1) |
+-------------------------------+
|                            10 |
+-------------------------------+
1 row in set (0.00 sec)
``````

So, you would have a TRIE with a maximum height of 10. Starting at the root of the TRIE, if you have the number 4294967295, you traverse branches 4,2,9,4,9,6,7,2,9, and 5. At each branch, you would perform an array-styled binary search.

If the branch located at that TRIE node is an exact match, you can assign a percentage to that level, and recursively walk down that branch to check for the next digit and return percentages from deeper TRIE nodes to add to the percentage you have at the currently searched TRIE node.

If the branch located at that TRIE node is NOT an exact match, you stop your recursive search there and return either 0 or some other percentage you may want to designate.

Given the sum of return values from all searched TRIE nodes, you may want to sum up the percentages and divide that answer by the length of the string. In other words,

Pct per Node = (1 / (Number of TRIE nodes that need to be searched)) or Zero(0).

Sum(Pct) = (Number of TRIE nodes exactly matched) / (Number of TRIE nodes that need to be searched [length of the string being searched]).

Given the length of the numberic field you store, you have O(log n) due to field length. For each TRIE node, you have O(log n) for searching for the proper branch. Overall, your search should have O(log (log n)) search time.

This performance stands out ever more if the field is alphanumeric. Assuming using only ASCII, each TRIE node would have 256 branches. The height of the TRIE would depend on the length of the character field. Representing this TRIE for variable-length strings would produce TRIE nodes that would be very sparse, but quickly searchable nonetheless.

Regardless what database you use, carefuly plan the data types you will be using to represent the TRIE node. You may also want to partition the table so that strings of length n terminate in partition n. Thus, you will have O(log n) search time at each partition.

http://en.wikipedia.org/wiki/Trie

http://www.eecs.harvard.edu/~ellard/Q-97/HTML/root/node24.html

http://www.webreference.com/js/tips/000318.html

• Tries are good when doing string comparisons or finding substrings, where you need to find a string match. How can I convert a Trie to use the F(a,b) function that is calculated on the entire strings as a whole? .. I don't see how i can use that to traverse the branches. May 10, 2011 at 16:17
• Instead of individual digits or characters, you have each branch represent an enum data type where each value of the enum represents a creature. Naturally, this would add complexity to TRIE nodes. You would have to properly represent every F(a,b) for all relations, making sure that F(a,b) = F(a,c) * F(c,b) if such paths exist. May 10, 2011 at 16:26
• F is not a metric. it's not transitive. only thing i can say is that F(a,b) = F(b,a) May 10, 2011 at 16:36
• But good suggestion anyway :) May 10, 2011 at 16:37
• You could represent each branch as a group of multiple character ASCII strings. The TRIE node ends up 256^2 (65536) branches for 2 characters, and 256^3 (16777216) branches for 3 characters. If you really want whole strings per branch, then each TRIE node should contain HASH buckets (using MD5) for O(1) search at the TRIE node. The TRIE would end up being very, very short, which is a good thing. Thank you for taking my answer into consideration. May 10, 2011 at 16:38

I assume you want to use a traditional RDBMS to store and query this data. I also assume the load profile on this data is read heavy.

My suggestion is to pre-calculate the values of `F()` as new records are inserted into your main table and store the results separately. This will incur a large storage cost as well as a large insert penalty, but your reads will run in `O(log n)`.

A pseudo-schema would look like:

``````items
-------
item_id       (auto-generated clustered PK)
value         (unique)

similarities
------------
item_id_a     (composite clustered PK) (FK referencing item.item_id)
item_id_b     (composite clustered PK) (FK referencing item.item_id)
similarity
``````

So, for every new `value` you insert into `items` you would insert the following into `similarities`:

``````INSERT INTO similarities (
item_id_a
, item_id_b
, similarity
)
SELECT
new_value
, i.value
, F(new_value, i.value)
FROM items AS i;
``````

Note that with this approach you will either need to store both `F(a, b)` and `F(b, a)` or somehow make sure you always store and query `F(a, b)` in a consistent manner so the parameters are in a predictable order. This is because `(a, b, similarity)` and `(b, a, similarity)` are distinct values as far as the `similarities` table is concerned.