વိတ်્ટેડ રિઝર્વોયર સેમ્પલિંગ (weighted reservoir sampling - A-Res) પર સ્વિચ કરવાને કારણે, હવે અમારું વિડિયો હોમપેજ દરેક રિફ્રેશ પર 24 નવા રેકમેન્ડેશન્સ (ભલામણો) બતાવે છે. આ ફેરફારથી "હંમેશા એક સરખું ગ્રીડ" (same-grid-forever) ની સમસ્યા દૂર થઈ છે, જે અમારા અગાઉના સ્કોર-સોર્ટેડ ફીડમાં જોવા મળતી હતી.

જૂની પદ્ધતિએ અનુભવને કેમ બગાડ્યો હતો

દર બે કલાકે અમે આઠ પ્રદેશોમાંથી લેટેસ્ટ ટ્રેન્ડિંગ વિડિયો મેળવીએ છીએ અને પરિણામોને SQLite ટેબલમાં સેવ કરીએ છીએ. સાદો ઉકેલ એ હતો કે આખા સેટને—રિલેવન્સ સ્કોર (સંબંધિત સ્કોર) દ્વારા—સોર્ટ કરવો અને ટોચના 24 વિડિયો લેવા. આ પદ્ધતિ ખાતરી આપે છે કે સૌથી વધુ સ્કોર ધરાવતી વસ્તુઓ દેખાય, પરંતુ તે એ પણ ખાતરી આપે છે કે તેઓ ત્યાં જ રહેશે. એક જ વાયરલ ક્લિપ દિવસો સુધી પોઝિશન 1 પર જામી શકે છે, અને વપરાશકર્તાઓ જ્યારે પણ રિલોડ કરે છે ત્યારે તેમને એકસરખું ગ્રીડ જ દેખાય છે.

આ જૂના અનુભવ ઉપરાંત, દરેક રિક્વેસ્ટ માટે આખી ટેબલને સોર્ટ કરવાથી SQLite ને મેમરીમાં એક મોટું ટેમ્પરરી સ્ટ્રક્ચર લોડ કરવું પડે છે, જે બિનજરૂરી છે.

વိတ်્ટેડ રિઝર્વોયર સેમ્પલિંગ આપણને શું આપે છે

વိတ်્ટેડ રિઝર્વોયર સેમ્પલિંગ એકસાથે બે સમસ્યાઓનો ઉકેલ લાવે છે:

  1. બાયસ સાથે તાજગી (Freshness with bias) – દરેક વિડિયો પસંદ થવાની શક્યતા તેના વજન (weight) ના પ્રમાણમાં હોય છે (દા.ત., રિલેવન્સ સ્કોર). બમણા વજન વાળો વિડિયો દેખાવાની શક્યતા બમણી હોય છે, પરંતુ કોઈ પણ વસ્તુ માટે જગ્યાની ખાતરી હોતી નથી.
  2. મેમરી કાર્યક્ષમતા (Memory efficiency) – આ અલ્ગોરિધમ માત્ર k વસ્તુઓનું નિશ્ચિત કદનું "રિઝર્વોયર" (reservoir) રાખે છે (k = 24 અમારા ફીડ માટે). તે સ્ટ્રીમને સિંગલ પાસમાં પ્રોસેસ કરે છે, તેથી કેટલાય ઉમેદવારો આવે તે ગમે તે હોય, મેમરી O(k) જ રહે છે.

મુખ્ય વિચાર સરળ છે. જેમ આપણે આવતી રોઝ (rows) ને સ્કેન કરીએ છીએ, તેમ આપણે દરેક આઈટમને એક રેન્ડમ કી (random key) આપીએ છીએ જેમાં તેનું વજન સમાવિષ્ટ હોય છે, અને પછી સૌથી વધુ કી ધરાવતી k આઈટમોને જાળવી રાખીએ છીએ.

પ્રેક્ટિકલમાં અલ્ગોરિધમ

દરેક વિડિયો માટે અમે:

  1. એક યુનિફોર્મ રેન્ડમ નંબર u ∈ (0, 1) મેળવીએ છીએ.
  2. કી k = u^(1/weight) ની ગણતરી કરીએ છીએ.
    (વજન જેટલું વધારે, અપેક્ષિત કી એટલી મોટી.)
  3. આઈટમને એક min-heap માં ઇન્સર્ટ કરીએ છીએ જે વર્તમાન ટોપ k કી સ્ટોર કરે છે.
    જો હીપ (heap) નું કદ k થી વધી જાય, તો આપણે સૌથી નાની કીને કાઢી નાખીએ છીએ.

જ્યારે સ્ટ્રીમ પૂરી થાય છે, ત્યારે હીપમાં તે 24 વિડિયો હોય છે જે આપણે ડિસ્પ્લે કરીશું.

ફ્લોટિંગ-પોઈન્ટ મર્યાદાઓ સાથે કામ કરવું

જ્યારે વિડિયોનું વજન ખૂબ વધારે હોય, ત્યારે ડબલ-પ્રિસિઝન અરિથમેટિકમાં u^(1/weight) ની કિંમત 1.0 થી અલગ કરી શકાતી નથી, જેના કારણે ઘણા ભારે આઈટમો એક જ કી શેર કરે છે અને રેન્ડમનેસ ગુમાવે છે. આનો ઉકેલ લોગ સ્પેસ (log space) માં કામ કરવાનો છે:

  • પાવર એક્સપ્રેશનને બદલે log_key = log(u) / weight ની ગણતરી કરો.

કારણ કે લોગરીધમ એક્સપોનેન્શિએશનને ગુણાકારમાં ફેરવે છે, તેથી ચોકસાઈ (precision) ગુમાવ્યા વગર કીનો ક્રમ જળવાઈ રહે છે. આ ગણતરીમાં વધારાનો ખર્ચ લગભગ શૂન્ય છે.

ઇમ્પ્લીમેન્ટેશન ચેકલિસ્ટ

  • ડેટા સ્ટ્રક્ચર: k કદનું એક min-heap (પ્રાયોરિટી ક્યુ) કાર્યક્ષમ રીતે સૌથી મોટી કી રાખે છે (O(log k) પ્રતિ ઇન્સર્શન).
  • ન્યુમેરિક ટાઇપ: u અને લોગ-આધારિત કી માટે 64-bit ફ્લોટિંગ-પોઈન્ટ નંબર્સનો ઉપયોગ કરો; તેઓ સામાન્ય વજનની રેન્જ માટે પૂરતી ચોકસાઈ પૂરી પાડે છે.
  • સ્ટેટિસ્ટિકલ સેનિટી ચેક: નાના સેમ્પલ સેટ પર ઝડપી મોન્ટે-કાર્લો (Monte-Carlo) ટેસ્ટ ચલાવો. જો વજન 10 વાળી આઈટમો વજન 1 વાળી આઈટમો કરતા અંદાજે દસ ગણી વાર દેખાય છે, તો ઇમ્પ્લીમેન્ટેશન સાચું છે.
  • સિંગલ-પાસ સ્ટ્રીમિંગ: અલ્ગોરિધમને ઉમેદવારોની કુલ સંખ્યા અગાઉથી જાણવાની જરૂર નથી, જે અમારા SQLite કર્સર સાથે કુદરતી રીતે સુસંગત છે જે એક પછી એક રો (rows) આપે છે.

સારાંશ

વိတ်્ટેડ રિઝર્વોયર સેમ્પલિંગ વિડિયો રેકમેન્ડેશન સર્વિસને તેના હોમપેજને તાજું રાખવા, રિલેવન્સ સ્કોરનું સન્માન કરવા અને મેમરી-લાઇટ રહેવા દે છે—તે પણ હજારો ઉમેદવારો પર માત્ર એક જ પાસ સાથે. કીની ગણતરીને લોગ સ્પેસમાં ખસેડીને અને min-heap નો ઉપયોગ કરીને, આ પદ્ધતિ ચોક્કસ અને કાર્યક્ષમ બંને રહે છે.