5

The problem I want to solve is the following:

Given a set of users, each with a set of interests they can specify themselves, find all the pairs of users that share same interests with a threshold of similarity (e.g 50% similar interests). Furthermore some interest categories should hold higher weight than others (i.e be more important towards the threshold).

Currently, I can only think of relational models to solve this, but it feels wrong, and something that will take too long to compute once there are as little as 100 users. With my current knowledge of document based DBs (e.g Mongo) I believe those are not an option, as we would need to cross-reference documents all the time(?). Should I be doing more reading on graph based DBs? Any pointers are welcome.

I am looking for a solution that is balanced in terms of complexity vs performance. Not looking for something that will work with millions of users if that means I have to read tons of research papers, but an approach that will support few thousand users will be sufficient.

  • 1
    how is this going to get queried? do we need to have similarities between all users all the time, or can we lazily calculate them when needed? – uylmz Feb 28 '17 at 9:33
  • This is all high-level research currently, but I think the similarity will be calculated on request, for a subset of the users, or a specific user, and the result will be stored. – latusaki Feb 28 '17 at 9:37
  • You could assign interests into a binary string. When you do that you may be able to extract all integers with specific binary combination fast. This is more or less how bit-map indexes work - See: en.wikipedia.org/wiki/Bitmap_index – NoChance Feb 28 '17 at 14:14
  • Do you have access to a database where you could create records for a couple of thousand users and test for yourself? You can index, fine-tune and denormalize the data as necessary. – JeffO Feb 28 '17 at 16:22
  • @Jeffo I can use any database that I can setup on my laptop, but my question was mainly about finding a starting point. – latusaki Feb 28 '17 at 16:27
2

Your problem is one of multidimensional search, so you need a system that is capable of such.

You can convert your interests into a sequence of features, and use Locality Sensitive Hashing to reduce the set of data on which to perform a more exact search.

Another alternative would be to use R-Trees.

2

I found Introduction to Information Retrieval to be very readable and informative. There is technical detail and long "further reading" lists, but the text itself does not get bogged down in minutiae.

Chapter 14 on Vector space classification would apply to this situation. Treat each interest as a dimension in a multi-dimensional space. Normalise the values (in the mathematical sense, not the DB one) and weight appropriately. Then calculate an N-dimensional distance between users in this space. Those with a smaller distance are more similar.

Since this is, essentially, a bunch of calculations any DBMS should be able to perform it. It may be more cost-effective to pass the data to a application server and use its CPU cycles, however.

The number of calculations rises as the square of the user base, however. You may not be able to get it to scale as you wish.

The book also covers various nearest-neighbour clustering algorithms. There are heuristics to trim the total number of comparisons at the cost of some accuracy. This may be an acceptable trade-off in this scenario.

  • Take an n-dimensional space-filling curve (they exist). A position in an n-dimensional space can be approximated by a scalar position on the curve. While computing this position may be expensive, it's only once per record. Records with scalars positions within a certain range are very easy to search for, and they would be good candidates for more precise matching. – 9000 Mar 16 '17 at 17:56
1

Basically you have a bipartite graph consisting of people and interests (corresponding to hubs and spokes).

The SALSA algorithm will give you the list of best matching people (ranked) for one person (at query time).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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