search

grapheo12 / iqps

Web-app meant for qp.metakgp.org
MIT License
20 stars 21 forks source link

Improve Search Algorithm #31

Open grapheo12 opened 3 years ago

grapheo12 commented 3 years ago

[Sub-issues are ordered by their priorities]

  1. Currently, we use SOUNDEX algorithm as a fuzzy searching mechanism to fetch question papers. While it is robust to some minor spelling mistakes, it is not effective for longer queries. Hence we need to improve the searching algorithm. A good choice seems to be BITAP. Sadly, this is not part of the MySQL standard as SOUNDEX is, which means we need to code it ourselves either in MySQL functions or in raw C/C++ and integrate it with the database we are using. Any better suggestion is equally welcome.

  2. Another area in which the search can be improved is field coverage. Currently, only search by subject title is implemented. We can have some commonly known metadata and tags about the subject through which we can search. Also, search by department name and other pre-existing fields can be enabled.

  3. A third area would be to reduce network calls while searching. Currently, a rudimentary version of Debouncing is implemented in the frontend, with a large scope of improvement.

grapheo12 commented 3 years ago

@munditva @shubhraneel @Debraj8301 @swarup3204 You are assigned to this repo. The issue is already divided up into 3 sections, which 2 of you must have a clash. Each one picks one. Let's brainstorm in this thread. Remember, since this is open-ended, your efforts will be documented and that documentation is also worth 1 commit.

grapheo12 commented 3 years ago

Please self-assign yourself so that I get to know you have started working.

shubhraneel commented 3 years ago

Can I start working on implementing BITAP, the first subissue?

grapheo12 commented 3 years ago

Go ahead

swarup3204 commented 3 years ago

Bhaiya,I am a fresher,so I am trying my best to cope but the assignment etc is overburdening...so whatever I can do will be at the dead of night only...so I hope u will allow me some time

On Wed, Dec 9, 2020, 15:58 Shubham Mishra notifications@github.com wrote:

@munditva https://github.com/munditva @shubhraneel https://github.com/shubhraneel @Debraj8301 https://github.com/Debraj8301 @swarup3204 https://github.com/swarup3204 You are assigned to this repo. The issue is already divided up into 3 sections, which 2 of you must have a clash. Each one picks one. Let's brainstorm in this thread. Remember, since this is open-ended, your efforts will be documented and that documentation is also worth 1 commit.

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/grapheo12/iqps/issues/31#issuecomment-741681137, or unsubscribe https://github.com/notifications/unsubscribe-auth/ARYKCDR47SCRQQQXJM3TE7DST5GNDANCNFSM4UN3XH2A .

munditva commented 3 years ago

@grapheo12 I am a little unclear about subissue 2. Is search by tags going to be completely exclusive of search by title? Also, for subissue 3, I found that MFQP returns the results quite fast, so what kind of improvement is needed?

grapheo12 commented 3 years ago

@munditva Search by tags is not currently used anymore. The code is just there. You'll not see the tag filter activated even. I want something that, you don't need the filters explicitly anymore. They will still be there. But "Compilers 2018" must return papers of the Compilers subject of the year 2018, without needing to set the filters.

At least this should work for the year-filter, we don't need it for other filters, at least for now.

~Are you sure you can handle this sub-issue, given your academic pressure? If not you can consult with @shubhraneel and can document his work. That will be much lightweight.~

grapheo12 commented 3 years ago

You can also look into this: #24 as a part of this issue.

munditva commented 3 years ago

@grapheo12 I dont have much academic pressure, someone else said that ig. I would like to work on the third subissue but am not sure how to proceed

grapheo12 commented 3 years ago

@munditva My bad! Sub-issue 3 is open-ended. I'd suggest you work with #24. Then come here. You can read about Debouncing from here: https://www.youtube.com/watch?v=Zo-6_qx8uxg&ab_channel=AkshaySaini

grapheo12 commented 3 years ago

@swarup3204 Hey! I understand your academic pressure! For you, the best course of action would be to help @shubhraneel in writing and documenting the feature.

@shubhraneel Please talk to him and help.

As I said before, this feature requires a lot of experimentation and fine-tuning. All of this must also be documented. We use Sphinx to document the code.

grapheo12 commented 3 years ago

@shubhraneel Write the algo in C++

See this to understand how it is done: https://www.oreilly.com/library/view/mysql-reference-manual/0596002653/ch09s02.html

shubhraneel commented 3 years ago

@grapheo12 I find the code given in Wikipedia is enough if only substitution edit is considered and for deletion and insertion I read up and found this: Fuzzy String search I will need to modify the code in Wikipedia a little according to this and it shall work.

shubhraneel commented 3 years ago

@grapheo12 I'm not getting how to use the C function in MySQL. The examples given run them in the mysql terminal. I'm not getting how do I use the CREATE FUNCTION in search/views.py. I tried searching a lot but got nothing.

grapheo12 commented 3 years ago

@grapheo12 I find the code given in Wikipedia is enough if only substitution edit is considered and for deletion and insertion I read up and found this: Fuzzy String search I will need to modify the code in Wikipedia a little according to this and it shall work.

Yes go ahead

@grapheo12 I'm not getting how to use the C function in MySQL. The examples given run them in the mysql terminal. I'm not getting how do I use the CREATE FUNCTION in search/views.py. I tried searching a lot but got nothing.

You need to create a separate Dockerfile for Mysql. Just the base image won't work I guess. Don't worry about that now. Do one thing, set up Mariadb separately in your computer (native installation, not the docker one).I'll send you a dummy database to test your queries on.

grapheo12 commented 3 years ago

I created https://github.com/grapheo12/mariadb-udf-docker to replace the db image we use. Can someone (except @shubhraneel :-) ) take up the task of integrating it into this repo? Ping here in case of doubt.

swarup3204 commented 3 years ago

@grapheo 12 ,apart from documenting,what are the other things that i can contribute to? Or can i solve some issue?

On Sat, Dec 12, 2020 at 4:41 AM Shubham Mishra notifications@github.com wrote:

I created https://github.com/grapheo12/mariadb-udf-docker to replace the db image we use. Can someone (except @shubhraneel https://github.com/shubhraneel :-) ) take up the task of integrating it into this repo? Ping here in case of doubt.

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/grapheo12/iqps/issues/31#issuecomment-743473262, or unsubscribe https://github.com/notifications/unsubscribe-auth/ARYKCDTR4UBYPZWPUNYB56LSUKRIVANCNFSM4UN3XH2A .

grapheo12 commented 3 years ago

You can work on the above integration. Create a new folder called mysql in which you copy the contents of the above repo. Just remove the .git and .gitignore files.

On Sat, 12 Dec 2020, 10:29 swarup3204, notifications@github.com wrote:

@grapheo 12 ,apart from documenting,what are the other things that i can contribute to? Or can i solve some issue?

On Sat, Dec 12, 2020 at 4:41 AM Shubham Mishra notifications@github.com wrote:

I created https://github.com/grapheo12/mariadb-udf-docker to replace the db image we use. Can someone (except @shubhraneel https://github.com/shubhraneel :-) ) take up the task of integrating it into this repo? Ping here in case of doubt.

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/grapheo12/iqps/issues/31#issuecomment-743473262, or unsubscribe < https://github.com/notifications/unsubscribe-auth/ARYKCDTR4UBYPZWPUNYB56LSUKRIVANCNFSM4UN3XH2A

.

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/grapheo12/iqps/issues/31#issuecomment-743703543, or unsubscribe https://github.com/notifications/unsubscribe-auth/AD5MVXBJZ3GSM5A7KANPBYTSUL2DXANCNFSM4UN3XH2A .

shubhraneel commented 3 years ago

I was eager to test it out, so I built the sql new image and all that. It is working. It is applying the bitap algorithms. I will update the pull request. Also, I think I should add make -C ./mariadb-udf-bitap in install.sh, and change the template to use this image. I should do that, right?

shubhraneel commented 3 years ago

@grapheo12 It's perfectly applying the bitap algorithm without much problems but I think the algorithm needs to be modified a little bit to suit this particular application.

shubhraneel commented 3 years ago

Other than preprocessing the text to ignore hyphens or stuff, I observed that searching 'Algoryhms', shows 'graph theory and algorithms" much higher than needed. I should prioritize first letter matching, I guess.

shubhraneel commented 3 years ago

@grapheo12 I have updated the Pull request, it is supposed to run properly with BITAP algorithms on searching in the search bar. There are a few minor modifications that may be needed to be made as it still uses the actual fuzzy BITAP algorithm with support for substitution, deletion, insertion. I may need to do some preprocessing of the text. I have tested the algorithm and it works better than SOUNDEX, I do not know if it is fruitful to increase the performance (accuracy, not speed) further as it feels for the scale of this application, the results are quite sufficient.

grapheo12 commented 3 years ago

@swarup3204 This isn't the place to comment it. Isn't it?