{"action":"created","issue":{"url":"https://api.github.com/repos/Tribler/tribler/issues/2250","repository_url":"https://api.github.com/repos/Tribler/tribler","labels_url":"https://api.github.com/repos/Tribler/tribler/issues/2250/labels{/name}","comments_url":"https://api.github.com/repos/Tribler/tribler/issues/2250/comments","events_url":"https://api.github.com/repos/Tribler/tribler/issues/2250/events","html_url":"https://github.com/Tribler/tribler/issues/2250","id":158107839,"number":2250,"title":"The relevance ranking algorithm when searching in Tribler needs to be redesigned","user":{"login":"devos50","id":1707075,"avatar_url":"https://avatars.githubusercontent.com/u/1707075?v=3","gravatar_id":"","url":"https://api.github.com/users/devos50","html_url":"https://github.com/devos50","followers_url":"https://api.github.com/users/devos50/followers","following_url":"https://api.github.com/users/devos50/following{/other_user}","gists_url":"https://api.github.com/users/devos50/gists{/gist_id}","starred_url":"https://api.github.com/users/devos50/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/devos50/subscriptions","organizations_url":"https://api.github.com/users/devos50/orgs","repos_url":"https://api.github.com/users/devos50/repos","events_url":"https://api.github.com/users/devos50/events{/privacy}","received_events_url":"https://api.github.com/users/devos50/received_events","type":"User","site_admin":false},"labels":[{"url":"https://api.github.com/repos/Tribler/tribler/labels/enhancement","name":"enhancement","color":"84b6eb"},{"url":"https://api.github.com/repos/Tribler/tribler/labels/needs%20discussion","name":"needs discussion","color":"006b75"},{"url":"https://api.github.com/repos/Tribler/tribler/labels/possible%20student%20task","name":"possible student task","color":"fef2c0"}],"state":"open","locked":false,"assignee":{"login":"devos50","id":1707075,"avatar_url":"https://avatars.githubusercontent.com/u/1707075?v=3","gravatar_id":"","url":"https://api.github.com/users/devos50","html_url":"https://github.com/devos50","followers_url":"https://api.github.com/users/devos50/followers","following_url":"https://api.github.com/users/devos50/following{/other_user}","gists_url":"https://api.github.com/users/devos50/gists{/gist_id}","starred_url":"https://api.github.com/users/devos50/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/devos50/subscriptions","organizations_url":"https://api.github.com/users/devos50/orgs","repos_url":"https://api.github.com/users/devos50/repos","events_url":"https://api.github.com/users/devos50/events{/privacy}","received_events_url":"https://api.github.com/users/devos50/received_events","type":"User","site_admin":false},"assignees":[{"login":"devos50","id":1707075,"avatar_url":"https://avatars.githubusercontent.com/u/1707075?v=3","gravatar_id":"","url":"https://api.github.com/users/devos50","html_url":"https://github.com/devos50","followers_url":"https://api.github.com/users/devos50/followers","following_url":"https://api.github.com/users/devos50/following{/other_user}","gists_url":"https://api.github.com/users/devos50/gists{/gist_id}","starred_url":"https://api.github.com/users/devos50/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/devos50/subscriptions","organizations_url":"https://api.github.com/users/devos50/orgs","repos_url":"https://api.github.com/users/devos50/repos","events_url":"https://api.github.com/users/devos50/events{/privacy}","received_events_url":"https://api.github.com/users/devos50/received_events","type":"User","site_admin":false}],"milestone":{"url":"https://api.github.com/repos/Tribler/tribler/milestones/23","html_url":"https://github.com/Tribler/tribler/milestones/New%20GUI","labels_url":"https://api.github.com/repos/Tribler/tribler/milestones/23/labels","id":1642375,"number":23,"title":"New GUI","description":"","creator":{"login":"whirm","id":529494,"avatar_url":"https://avatars.githubusercontent.com/u/529494?v=3","gravatar_id":"","url":"https://api.github.com/users/whirm","html_url":"https://github.com/whirm","followers_url":"https://api.github.com/users/whirm/followers","following_url":"https://api.github.com/users/whirm/following{/other_user}","gists_url":"https://api.github.com/users/whirm/gists{/gist_id}","starred_url":"https://api.github.com/users/whirm/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/whirm/subscriptions","organizations_url":"https://api.github.com/users/whirm/orgs","repos_url":"https://api.github.com/users/whirm/repos","events_url":"https://api.github.com/users/whirm/events{/privacy}","received_events_url":"https://api.github.com/users/whirm/received_events","type":"User","site_admin":false},"open_issues":35,"closed_issues":15,"state":"open","created_at":"2016-03-14T10:43:20Z","updated_at":"2016-08-24T09:56:17Z","due_on":null,"closed_at":null},"comments":5,"created_at":"2016-06-02T10:24:47Z","updated_at":"2016-09-10T08:42:07Z","closed_at":null,"body":"When searching in Tribler, search results (which can consist of torrents and channels) are ranked according to several criteria. Channels and torrents are sorted separately from each other. The associated channels of the torrents are also determined and in case a torrent is present in more than one channel, the channel with the highest number of votes is taken.\r\n\r\nChannels are sorted based on the number of torrents in the channel. The algorithm to sort torrents is more complex. First, an array of five scores are constructed. These values are determined as follows:\r\n1. The number of matching keywords in the name of the torrent\r\n2. The number of matching keywords in the name of the files the torrent contains\r\n3. The position of the lowest matching keyword in the torrent name. For instance, when searching for ‘Game of Thrones’ and ‘of’ is a matching keyword, this position will be 2.\r\n4. The number of matching keywords in the extensions of the file names of the torrent.\r\n5. A score that is based on several (normalised) attributes of the torrent. This score is determined after the set of local search results are constructed. The following formula is used: _score = 0.8 * normalized_num_seeder - 0.1 * normalized_num_negative_votes + 0.1 * normalized_num_subscriptions_. Note that the number of negatives votes and number of subscriptions do not exist anymore and will always be 0. \r\n\r\nAfter the torrents and channels are sorted, the results are put in a list. Every five torrent results, a channel result is inserted. This is to make sure that channels are also showing up in the search results (and more important, are visible to the user).\r\n\r\nAlso, I think it’s better to not be dependent on other search results to make streaming torrents from the database possible (like we do now when normalising). In other words, the final relevance score in the new algorithm should only be dependent on the data that this torrent object has.\r\n\r\nI will start thinking about a new (more simple) algorithm that we could use for this and add the proposal in this issue.\r\n\r\n**Possible improvements:**\r\n- Improve the relevance algorithm by taking the number of matches inside the torrent name/torrent file names in consideration. For instance, when searching for 'pioneer one', a torrent named 'pioneer one collection' probably has a higher relevance than a torrent named 'pioneer one - episode 3, season 4'. This will prevent situations like the following, when I expect 'test_tribler.txt' to show up higher than 'test.tribler.upc.iso'.\r\n![9167a65ab13479c028a35e1a9625f2c6](https://cloud.githubusercontent.com/assets/1707075/15743437/c190e7b8-28c5-11e6-89d5-4f81cce49faf.png)\r\n- I think the lowest matching term criteria should be removed or get lower priority since I doubt that it's always true that terms that are matching earlier in torrent A than in torrent B makes torrent A more relevant. For instance, torrent A = \"game of thrones\" and torrent B = \"thrones in someplace\". If a user searches for 'thrones', torrent B will be marked as more relevant which feels weird.\r\n- Users are making mistakes when typing. For instance, if I type \"triler\", I might mean \"Tribler\" or \"triller\" so I would like to see results that are matching these queries. This can be achieved by calculating the [levenshtein distance](https://en.wikipedia.org/wiki/Levenshtein_distance) with know keywords. One issue here is performance. Fortunately, sqlite contains support for levenshtein collation.\r\n![4c590b44f5fabf0762f4fc29c01f7fa8](https://cloud.githubusercontent.com/assets/1707075/15744471/688b2e1a-28cc-11e6-8464-76da46097431.png)\r\n- The sorting of the channels is currently only dependent on the number of torrents in the channel. If I'm not mistaken, it is not even sorted on the matching in the name! See the following example for instance, where I expect the channel with 'pirate' in the name, to show up higher:\r\n![f29b7edfd88b07d83b8d69d10746db87](https://cloud.githubusercontent.com/assets/1707075/15779688/0a5b68b4-299e-11e6-9e0c-d14bf7673f1b.png)\r\n- When building the FTS3 index in the sqlite database, duplicate words are removed. This means that when searching for 'years', a torrent named 'best years' will be ranked equal to a torrent named 'years and years'. However, 'years and years' should have a higher relevance since the word 'years' occurs twice. Another example is when searching for 'iso'. A torrent file that contains 100 iso files is ranked equivalent to a torrent file that only has one iso file.\r\n- By removing the number of seeders criteria when sorting, less popular torrent have a better chance of coming up higher in the lists, increasing the chance the user will download these and seed the torrent afterwards.\r\n- Our current algorithm only returns results that matches all given keywords. So when searching for 'pirate audio', only torrents returned that have both terms in it, are returned. It might be better to show the user also torrents matching 'pirate' and matching 'audio' (while still giving more relevance to torrents that matches 'pirate audio').\r\n\r\n**Proposal for a new algorithm:**\r\n\r\nThe new algorithm should take the matching with keywords better into account and be less dependent on other (confusing) variables such as number of seeders and number of torrents in the channel.\r\n\r\n- The first step should be to adjust our FTS3 index to not filter out duplicate keywords in the torrent name, file names and file extensions. This will have consequences on the amount of storage required and requires rebuilding the FTS3 index in the upgrader.\r\n- Slightly change the FTS matching query to account for partial term results.\r\n- Use the [BM25F](https://en.wikipedia.org/wiki/Okapi_BM25) algorithm to determine the relevance of the query in the torrent name, file names and file extensions. Note that we have to calculate the BM25 score three times. After that, we can take a weighted average of these scores. The score of the torrent name matching should have the highest priority. The relevance scores are sent to the GUI over the REST API.\r\n- Channel name matching is done in the same way, however, the only difference is that we are not using FTS for the channels. We also calculate the BM25 score of the channel name matching. These relevance scores are sent to the GUI over the REST API.\r\n- If after several seconds there are no incoming results, fetch the keyword(s) with the closest Levenshtein distance from the database and display them to the user with a message similar to the following: \"No results found so far. Did you mean to search for ...\"?\r\n\r\nThe above algorithm takes all of the improvements into account I outlined above."},"comment":{"url":"https://api.github.com/repos/Tribler/tribler/issues/comments/246100120","html_url":"https://github.com/Tribler/tribler/issues/2250#issuecomment-246100120","issue_url":"https://api.github.com/repos/Tribler/tribler/issues/2250","id":246100120,"user":{"login":"synctext","id":325224,"avatar_url":"https://avatars.githubusercontent.com/u/325224?v=3","gravatar_id":"","url":"https://api.github.com/users/synctext","html_url":"https://github.com/synctext","followers_url":"https://api.github.com/users/synctext/followers","following_url":"https://api.github.com/users/synctext/following{/other_user}","gists_url":"https://api.github.com/users/synctext/gists{/gist_id}","starred_url":"https://api.github.com/users/synctext/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/synctext/subscriptions","organizations_url":"https://api.github.com/users/synctext/orgs","repos_url":"https://api.github.com/users/synctext/repos","events_url":"https://api.github.com/users/synctext/events{/privacy}","received_events_url":"https://api.github.com/users/synctext/received_events","type":"User","site_admin":false},"created_at":"2016-09-10T08:42:07Z","updated_at":"2016-09-10T08:42:07Z","body":"@themusicgod1 Yes, we need accurate metadata, proper pageranking/itemranking, and good ID3 stuff.\r\n\r\nbtw. Worked on this myself 16 years ago, sadly never got solved (http://cd.ro.nu/hypermail/1046.html). Maybe an extra 16 years:-)"}}
{"actor":{"display_login":"synctext"}}