Take the 2-minute tour ×
Database Administrators Stack Exchange is a question and answer site for database professionals who wish to improve their database skills and learn from others in the community. It's 100% free, no registration required.

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.

share|improve this question
2  
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). –  Jack Douglas May 10 '11 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 –  Yochai Timmer May 10 '11 at 11:26
    
How many rows in the table? Have you considered associative table containing precomputed value from all combinations? –  Endy Tjahjono May 10 '11 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. –  Yochai Timmer May 10 '11 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%? –  Jack Douglas May 10 '11 at 12:50

2 Answers 2

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

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

share|improve this answer
    
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. –  Yochai Timmer May 10 '11 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. –  RolandoMySQLDBA May 10 '11 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) –  Yochai Timmer May 10 '11 at 16:36
    
But good suggestion anyway :) –  Yochai Timmer May 10 '11 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. –  RolandoMySQLDBA May 10 '11 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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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