0
$\begingroup$

I have a mysql database with the following format:

id      string
1        foo1...
2        foo2...
..       ...

There are >100k entries in this db.

What I want to do is for each string, compare it to each other string and store some metric of the comparison. Doing this will essentially yield a 2D matrix of size NxN where N is the number of row in the db.

My initial thought was creating another db where each index corresponds to the string of the index in the first db and each column is the value from comparing the two strings. For example, id 1 column 2 in the second db would be the value outputted from comparing id1 and id2 in the first db.

The format of the second db:

id    col1    col2    col3    ....
1       1      0.4     0.5    .....
...    ...     ...      ...

This way of creating the second db would result in 100k rows x 100k columns, which is the issue at hand. What is the best way to handle large data sets like this? Is storing the data in a text file more efficient (say each text file corresponds to one row in the second db.)

$\endgroup$
1
  • $\begingroup$ If you have to use a data store with limitations on the number of columns, you could map an NxN structure onto one of MN X N/M. And then wrap it in a retrieval mechanism that retrieves M rows at a time. $\endgroup$ Mar 16, 2015 at 13:15

1 Answer 1

2
$\begingroup$

It is usually more practical to compute the distances on the fly rather than storing $N^2$ values. If possible, you will want to use a heuristic to select only the items could be sufficiently similar so you don't waste time computing distance to irrelevant items. PostgreSQL can create an index on character trigrams in strings that enables efficient querying for other strings that are sufficiently similar (measured by the Jaccard similarity coefficient).

Storing an $N$ column wide table is not possible because the maximum number of columns allowed in MySQL is 4096. Even if that were not the case, using an RDBMS in such a way is considered bad practice and such a table would be difficult to work with.

If for some reason you must store a dense distance matrix, a format such as HDF5 would be more efficient than an RDBMS.

$\endgroup$
3
  • $\begingroup$ Hi user2313838, thanks for your reply! I am not familiar with spatial indices. From what I read it is a way to store spatial information regarding shapes/lines/etc..Could you expand on how the usage of spatial indices can extend into the question? $\endgroup$
    – masotann
    Jan 12, 2015 at 23:17
  • $\begingroup$ An example would be a Ball tree structure. $\endgroup$ Jan 13, 2015 at 4:04
  • $\begingroup$ I revised that first part. The spatial index would be used to efficiently query for nearby items provided your metric was based on some kind of vector representation. It may or may not be relevant to your application. $\endgroup$ Jan 13, 2015 at 4:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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