Compliance / Requirements Algorithm

Question

Compliance / Requirements Algorithm

I am implementing an item trading system on a site with high traffic. I have a large number of users, each of which maintains a HAVE list and a WANT list for a number of specific items. I am looking for an algorithm that will allow me to effectively offer trading partners based on your HAVE and WANTs corresponding to them. Ideally, I want to find partners with the highest mutual trading potential (that is, I have a ton of things that you want, you have a ton of things that I want). I don't need to find a global pair with the highest potential (which sounds tough), just find the pairs with the highest potential for a given user (or even some pairs with the highest potential, not global max).

Example:

 User 1 HAS A, C WANTS B, D

 User 2 HAS D WANTS A

 User 3 HAS A, B, D WANTS C

 User 1 goes to the site and clicks a button that says 
   "Find Trading Partners" and the top-ranked result is
    User 3, followed by User 2.

An additional source of complexity is that the elements have different meanings, and I want a match on the highest trade transaction, and not on most matches between the two traders. Therefore, in the above example, if all elements are worth 1, but A and D are worth 10, user 1 is now mapped to user 2 above User 3.

The naive way to do this is to calculate the maximum trading value between the user looking for partners and all other users in the database. I am thinking with some lookup tables on the right things, which I could do better. I tried searching, as this seems like a classic problem, but I don't know the name for it.

Can you recommend a good approach to solving this problem? I have seen sites like the Magic Online Trading League that seem to solve it in real time.

Answer 1

You can do this in O(n*k^2) (n is the number of people, k is the average number of elements that they have / want), keeping hash tables (or in the database, indexes) of all people who have and You want to get data, and then give points to all people who have those products that the current user needs, and you want the goods to have the current user. Display 10 or 20 points.

---

[Change] An example of how this will be implemented in SQL:

 -- Get score for @userid wants SELECT UserHas.UserID, SUM(Items.Weight) AS Score FROM UserWants INNER JOIN UserHas ON UserWants.ItemID = UserHas.ItemID INNER JOIN Items ON Items.ItemID = UserWants.ItemID WHERE UserWants.UserID = @userid GROUP BY UserWants.UserID, UserHas.UserID 

This gives you a list of other users and their rating based on what items they have, what the current user wants. Do the same for those elements that the current user wants others, and then somehow combine them (add ratings or whatever you want) and take the top 10.

Answer 2

This problem looks quite similar to the stable room problem *. I don’t see anything wrong with the SQL implementation, which received the highest vote, but, as some others have suggested, it seems like a dating / matching problem, a line-like stable marriage problem , but here all the participants are in the same pool. The second entry on Wikipedia also has a link to a practical javascript solution that may be useful

Answer 3

You can save a list for each item (as an addition to the list for each user). Then the search for items occurs. Now you can allow your own brute force search for the most valuable pair by first checking the most valuable items. If you need a more complex (possibly faster) search, you can enter many elements that are often combined into metafiles, and search for them first.

Answer 4

I mark the item with the letter and the user by number.

• m - the number of elements in all lists of presence / necessity (is or you want, not necessary and necessary)
• x is the number of users.

For each user you have a list of his desires and haves. The left line is the wish list, the right is the list (both will be sorted so we can use binary search).

 1 - ABBCDE FFFGH 2 - CFGGH BE 3 - AEEGH BBDF 

For each pair of users, you generate two values ​​and save them somewhere, you only generate it once and than you implement it. Sorting the first table and generating the second, O(m*x*log(m/x)) + O(log(m)) and will require additional memory O(x^2) . These values ​​are: how much the first user will have and how many more (if you want, you can change these values ​​by multiplying them by the value of a specific element).

 1-2 : 1 - 3 (user 1 gets 1) - (user 2 gets 3) 1-3 : 3 - 2 2-3 : 1 - 1 

You can also calculate and store the best trader for each user. After creating this useful data, you can quickly query.

• Adding / removing an item - O(m*log(m/x)) (you are viewing a list of users / want and perform a binary search on the list / list of each other user and implement the data)
• The search for the best connection is O(1) or O(x) (it depends on whether the result stored in the cache is correct or needs to be updated). You loop the user pairs and do whatever you want with the data to return the best connection to the user)

In m/x I estimate the number of items in a single user list / list.

In this algorithm, I assume that all data is not stored in the database (I don’t know if binary search in Databases is possible) and that inserting / deleting an item in the O(1) list.

PS. Sorry for the bad English, and I hope I figured it out correctly and that it works, because I need it too.

Answer 5

Ok, how about this:

Mostly there are giant "pools"

Each "pool" contains "sections". Each "pool" is intended for people who own a certain subject. Each section is intended for people who own this element and want another.

What I mean:

Pool A (for those who request A)

- section B (for those who request A who have B)

- Section C (for those who request A who have C, even if they also have B)

Pool B

- Section A

- Section B

Pool C

- Section A

- Section C

Each section is populated by people. "Transactions" will consist of one "requested" item and a "Package", you are ready to provide all or all of the items to receive the product you requested.

Each "Transaction" is calculated per pool .... if you want to receive this item, you go to the pools of items that you are ready to give, and it will find the section that belongs to the item that you are requesting.

Similarly, your trade is placed in pools. Thus, you can immediately find all applicable people, because you know exactly which pools, and EXACTLY which sections you need to look for, without the sorting necessary after they are logged in.

And then age will take precedence, older deals will be chosen, not new ones.

Answer 6

Suppose you can hash your items, or at least sort them. Suppose your goal is to find the best result for a given user on request, as in your original example. (Optimizing trading partners to maximize the total value of trading is another matter.)

It will be fast. O (log n) for each insert operation. The worst case is O (n) for the offer of trading partners, but you related this by processing time.

• You already maintain a list of items for each user.
• Give each user a score equal to the sum of the values ​​of the elements that they have.
• Maintain a list of HAVES users and user WANTS by element (@Dialecticus) sorted by user account. (You can sort on demand or save lists sorted dynamically every time a user changes their HAVE list.)
• When user1 requests invited trading partners
  • Iterate over your item elements in order by value.
  • Iterating over user-HAVES user2 for each item , in order in the user's account.
  • Calculate the trade value for user1 trades-with user2 .
  • Remember the best deal.
  • Save the hash of users processed so far to avoid re-calculating the value for the user several times.
  • Finish when you finish processing time (your guarantee in real time).

Sorting by position value and user rating is an approximation that does it quickly. I'm not sure how suboptimal this would be. There are, of course, easy examples where it will not be able to find a better deal if you do not run it before completion. In practice, it seems that this can be quite good. In the limit, you can make it optimal by letting it work until it runs out of lists in steps 4.1 and 4.2. There are additional memory costs associated with inverted lists, but you did not say that you are limited by memory. In general, if you want speed, it is not uncommon for a compromise space to get it.

Answer 7

Of course, you can always divide the system into three categories; Wants, Hava, and Open Sentences. So let's say that User1 has Item A, User2 has Item B and C and trades them for item A, but User1 still wants Item D, and User2 wants Item E. Thus, User1 (assuming that he is the owner trade) sends a request, or want for item D and item E, so the offer stands and goes in the list of "Open Offers". If it is not accepted or not edited within two or several days, it is automatically canceled. Thus, User3 searches for the elements F and the element G and searches the list for the elements F and G that are shared between User1 and User2. He understands that the open sentence of User1 and User2 includes requests for the elements D and E that he has. Therefore, he decides to "join" the operation, and she accepts their terms, trading and exchanging them with each other.

Let's say that User1 now wants Item H. He just searches the “Have” list for the item, and among the results, he discovers that User4 will trade Item H for Item I, which has user 1. They trade, all is well.

Answer 8

Just do it only BC. This solves all the problems.