ವೇಯ್ಟೆಡ್ ರಿಸರ್ವಾಯರ್ ಸ್ಯಾಂಪಲಿಂಗ್ (weighted reservoir sampling - A-Res) ಗೆ ಬದಲಾಯಿಸಿದ್ದಕ್ಕಾಗಿ, ನಮ್ಮ ವಿಡಿಯೋ ಹೋಂ ಪೇಜ್ ಈಗ ಪ್ರತಿ ರಿಫ್ರೆಶ್ ಮಾಡುವಾಗಲೂ 24 ಹೊಸ ಶಿಫಾರಸುಗಳನ್ನು ತೋರಿಸುತ್ತದೆ. ಈ ಬದಲಾವಣೆಯು ನಮ್ಮ ಹಿಂದಿನ ಸ್ಕೋರ್-ಸಾರ್ಟ್ ಮಾಡಿದ ಫೀಡ್‌ನಲ್ಲಿ ಎದುರಾಗುತ್ತಿದ್ದ “same-grid-forever” (ಯಾವಾಗಲೂ ಒಂದೇ ಗ್ರಿಡ್) ಸಮಸ್ಯೆಯನ್ನು ನಿವಾರಿಸಿದೆ.

ಹಳೆಯ ವಿಧಾನವು ಅನುಭವವನ್ನು ಏಕೆ ಹಾಳುಮಾಡಿತು

ಪ್ರತಿ ಎರಡು ಗಂಟೆ마다 ನಾವು ಎಂಟು ಪ್ರದೇಶಗಳಿಂದ ಇತ್ತೀಚಿನ ಟ್ರೆಂಡಿಂಗ್ ವಿಡಿಯೋಗಳನ್ನು ಪಡೆದು, ಆ ಫಲಿತಾಂಶಗಳನ್ನು SQLite ಟೇಬಲ್‌ಗೆ ಸೇರಿಸುತ್ತೇವೆ. ಇಡೀ ಸೆಟ್ ಅನ್ನು—relevance score ಆಧಾರದ ಮೇಲೆ—ಸಾರ್ಟ್ ಮಾಡಿ, ಮೊದಲ 24 ವಿಡಿಯೋಗಳನ್ನು ತೆಗೆದುಕೊಳ್ಳುವುದು ಒಂದು ಸರಳ ಪರಿಹಾರವಾಗಿತ್ತು. ಆ ವಿಧಾನವು ಅತಿ ಹೆಚ್ಚು ಸ್ಕೋರ್ ಹೊಂದಿರುವ ಐಟಂಗಳು ಕಾಣಿಸಿಕೊಳ್ಳುವುದನ್ನು ಖಚಿತಪಡಿಸುತ್ತದೆ, ಆದರೆ ಅವು ಅಲ್ಲಿಯೇ ಉಳಿಯುವುದನ್ನೂ ಖಚಿತಪಡಿಸುತ್ತದೆ. ಒಂದು ವೈರಲ್ ಕ್ಲಿಪ್ ದಿನಗಟ್ಟಲೆ ಮೊದಲ ಸ್ಥಾನವನ್ನು ಆಕ್ರಮಿಸಿಕೊಳ್ಳಬಹುದು ಮತ್ತು ಬಳಕೆದಾರರು ಪ್ರತಿ ಬಾರಿ ರಿಲೋಡ್ ಮಾಡಿದಾಗಲೂ ಒಂದೇ ರೀತಿಯ ಗ್ರಿಡ್ ಅನ್ನು ನೋಡುತ್ತಾರೆ.

ಹಳೆಯದಾದ ಅನುಭವದ ಹೊರತಾಗಿ, ಪ್ರತಿ ವಿನಂತಿಗಾಗಿ ಇಡೀ ಟೇಬಲ್ ಅನ್ನು ಸಾರ್ಟ್ ಮಾಡುವುದು SQLite ಅನ್ನು ದೊಡ್ಡ ತಾತ್ಕಾಲಿಕ ರಚನೆಯನ್ನು ಮೆಮೊರಿಗೆ ಲೋಡ್ ಮಾಡಲು ಒತ್ತಾಯಿಸುತ್ತದೆ, ಇದು ವ್ಯರ್ಥವಾಗಿದೆ.

ವೇಯ್ಟೆಡ್ ರಿಸರ್ವಾಯರ್ ಸ್ಯಾಂಪಲಿಂಗ್ ನಮಗೆ ಏನು ನೀಡುತ್ತದೆ

ವೇಯ್ಟೆಡ್ ರಿಸರ್ವಾಯರ್ ಸ್ಯಾಂಪಲಿಂಗ್ ಎರಡು ಸಮಸ್ಯೆಗಳನ್ನು ಏಕಕಾಲದಲ್ಲಿ ಪರಿಹರಿಸುತ್ತದೆ:

  1. ಬಯಾಸ್‌ನೊಂದಿಗೆ ತಾಜಾತನ (Freshness with bias) – ಪ್ರತಿ ವಿಡಿಯೋ ಆಯ್ಕೆಯಾಗುವ ಸಾಧ್ಯತೆಯು ಅದರ ವೇಯ್ಟ್‌ಗೆ (ಉದಾಹರಣೆಗೆ, relevance score) ಅನುಗುಣವಾಗಿರುತ್ತದೆ. ಎರಡರಷ್ಟು ವೇಯ್ಟ್ ಹೊಂದಿರುವ ವಿಡಿಯೋ ಕಾಣಿಸಿಕೊಳ್ಳುವ ಸಾಧ್ಯತೆ ಎರಡರಷ್ಟು ಹೆಚ್ಚಿರುತ್ತದೆ, ಆದರೆ ಯಾವುದೇ ಐಟಂಗೆ ಸ್ಥಾನವು ಖಚಿತವಾಗಿರುವುದಿಲ್ಲ.
  2. ಮೆಮೊರಿ ದಕ್ಷತೆ (Memory efficiency) – ಈ ಅಲ್ಗಾರಿದಮ್ ಕೇವಲ k ಐಟಂಗಳ ನಿಗದಿತ ಗಾತ್ರದ “reservoir” ಅನ್ನು ಇರಿಸಿಕೊಳ್ಳುತ್ತದೆ (ನಮ್ಮ ಫೀಡ್‌ಗಾಗಿ k = 24). ಇದು ಸ್ಟ್ರೀಮ್ ಅನ್ನು ಒಂದೇ ಪಾಸ್‌ನಲ್ಲಿ ಪ್ರೊಸೆಸ್ ಮಾಡುತ್ತದೆ, ಆದ್ದರಿಂದ ಎಷ್ಟು ಅಭ್ಯರ್ಥಿಗಳು ಬಂದರೂ ಮೆಮೊರಿ O(k) ಆಗಿಯೇ ಇರುತ್ತದೆ.

ಇದರ ಮೂಲ ಪರಿಕಲ್ಪನೆಯು ಸರಳವಾಗಿದೆ. ನಾವು ಬರುವ ರೋಗಳನ್ನು ಸ್ಕ್ಯಾನ್ ಮಾಡುವಾಗ, ಪ್ರತಿ ಐಟಂಗೆ ಅದರ ವೇಯ್ಟ್ ಅನ್ನು ಒಳಗೊಂಡಿರುವ ಒಂದು ರ್ಯಾಂಡಮ್ ಕೀ (random key) ಅನ್ನು ನೀಡುತ್ತೇವೆ, ನಂತರ ಅತಿ ಹೆಚ್ಚಿನ ಕೀಗಳನ್ನು ಹೊಂದಿರುವ k ಐಟಂಗಳನ್ನು ಉಳಿಸಿಕೊಳ್ಳುತ್ತೇವೆ.

ಪ್ರಾಯೋಗಿಕವಾಗಿ ಅಲ್ಗಾರಿದಮ್

ಪ್ರತಿ ವಿಡಿಯೋಗೂ ನಾವು:

  1. ಒಂದು ಸಮಾನ ರ್ಯಾಂಡಮ್ ಸಂಖ್ಯೆ u ∈ (0, 1) ಅನ್ನು ಪಡೆಯುತ್ತೇವೆ.
  2. ಕೀ k = u^(1/weight) ಅನ್ನು ಲೆಕ್ಕಹಾಕುತ್ತೇವೆ.
    (ವೇಯ್ಟ್ ಹೆಚ್ಚಾದಂತೆ, ನಿರೀಕ್ಷಿತ ಕೀ ಕೂಡ ದೊಡ್ಡದಾಗಿರುತ್ತದೆ.)
  3. ಪ್ರಸ್ತುತ ಟಾಪ್ k ಕೀಗಳನ್ನು ಸಂಗ್ರಹಿಸುವ min-heap ನಲ್ಲಿ ಐಟಂ ಅನ್ನು ಸೇರಿಸುತ್ತೇವೆ.
    ಒಂದು ವೇಳೆ heap ಗಾತ್ರವು k ಮೀರಿತುವುದೆಂದರೆ, ನಾವು ಅತ್ಯಂತ ಚಿಕ್ಕ ಕೀಯನ್ನು ಕೈಬಿಡುತ್ತೇವೆ.

ಸ್ಟ್ರೀಮ್ ಮುಗಿದಾಗ, ನಾವು ಪ್ರದರ್ಶಿಸುವ 24 ವಿಡಿಯೋಗಳು heap ನಲ್ಲಿರುತ್ತವೆ.

ಫ್ಲೋಟಿಂಗ್-ಪಾಯಿಂಟ್ ಮಿತಿಗಳನ್ನು ನಿಭಾಯಿಸುವುದು

ವಿಡಿಯೋದ ವೇಯ್ಟ್ ತುಂಬಾ ದೊಡ್ಡದಿದ್ದಾಗ, double-precision ಅರಿಥ್ಮೆಟಿಕ್‌ನಲ್ಲಿ u^(1/weight) ಎಂಬುದು 1.0 ನಿಂದ ಪ್ರತ್ಯೇಕಿಸಲು ಸಾಧ್ಯವಾಗದ ಮೌಲ್ಯಕ್ಕೆ ಕುಸಿಯುತ್ತದೆ, ಇದರಿಂದಾಗಿ ಅನೇಕ ಹೆಚ್ಚಿನ ವೇಯ್ಟ್ ಹೊಂದಿರುವ ಐಟಂಗಳು ಒಂದೇ ಕೀಯನ್ನು ಹಂಚಿಕೊಳ್ಳುತ್ತವೆ ಮತ್ತು ರ್ಯಾಂಡಮ್‌ನೆಸ್ ಅನ್ನು ಕಳೆದುಕೊಳ್ಳುತ್ತವೆ. ಇದಕ್ಕೆ ಪರಿಹಾರವೆಂದರೆ log space ನಲ್ಲಿ ಕೆಲಸ ಮಾಡುವುದು:

  • ಪವರ್ ಎಕ್ಸ್‌ಪ್ರೆಶನ್ ಬದಲಿಗೆ log_key = log(u) / weight ಅನ್ನು ಲೆಕ್ಕಹಾಕಿ.

ಲಾಗರಿಥಮ್‌ಗಳು ಎಕ್ಸ್‌ಪೊನೆನ್ಸಿಯೇಷನ್ ಅನ್ನು ಗುಣಾಕಾರವಾಗಿ ಪರಿವರ್ತಿಸುವುದರಿಂದ, ಪ್ರೆಸಿಷನ್ ಸಮಸ್ಯೆಯನ್ನು ತಪ್ಪಿಸುವಾಗ ಕೀಗಳ ಕ್ರಮವು (ordering) ಉಳಿಯುತ್ತದೆ. ಈ ಲೆಕ್ಕಾಚಾರಕ್ಕೆ ಹೆಚ್ಚಿನ ವೆಚ್ಚವಾಗುವುದಿಲ್ಲ.

ಇಂಪ್ಲಿಮೆಂಟೇಶನ್ ಚೆಕ್‌ಲಿಸ್ಟ್

  • Data structure: k ಗಾತ್ರದ ಒಂದು min-heap (priority queue) ದೊಡ್ಡ ಕೀಗಳನ್ನು ದಕ್ಷತೆಯಿಂದ ಇರಿಸಿಕೊಳ್ಳುತ್ತದೆ (ಪ್ರತಿ ಇನ್ಸರ್ಶನ್‌ಗೆ O(log k)).
  • Numeric type: u ಮತ್ತು log-ಆಧಾರಿತ ಕೀಗಳಿಗಾಗಿ 64-bit ಫ್ಲೋಟಿಂಗ್-ಪಾಯಿಂಟ್ ಸಂಖ್ಯೆಗಳನ್ನು ಬಳಸಿ; ಅವು ಸಾಮಾನ್ಯ ವೇಯ್ಟ್ ವ್ಯಾಪ್ತಿಗಳಿಗೆ ಸಾಕಷ್ಟು ಪ್ರೆಸಿಷನ್ ನೀಡುತ್ತವೆ.
  • Statistical sanity check: ಸಣ್ಣ ಸ್ಯಾಂಪಲ್ ಸೆಟ್ ಮೇಲೆ ಕ್ವಿಕ್ Monte-Carlo ಟೆಸ್ಟ್ ಮಾಡಿ. ವೇಯ್ಟ್ 10 ಹೊಂದಿರುವ ಐಟಂಗಳು ವೇಯ್ಟ್ 1 ಹೊಂದಿರುವ ಐಟಂಗಳಿಗಿಂತ ಸುಮಾರು ಹತ್ತು ಪಟ್ಟು ಹೆಚ್ಚು ಕಾಣಿಸಿಕೊಂಡರೆ, ಇಂಪ್ಲಿಮೆಂಟೇಶನ್ ಸರಿಯಾಗಿದೆ ಎಂದರ್ಥ.
  • Single-pass streaming: ಅಲ್ಗಾರಿದಮ್ ಅಭ್ಯರ್ಥಿಗಳ ಒಟ್ಟು ಸಂಖ್ಯೆಯನ್ನು ಮೊದಲೇ ತಿಳಿಯುವ ಅಗತ್ಯವಿಲ್ಲ, ಇದು ಒಂದೊಂದಾಗಿ ರೋಗಳನ್ನು ನೀಡುವ ನಮ್ಮ SQLite cursor ಗೆ ನೈಸರ್ಗಿಕವಾಗಿ ಹೊಂದಿಕೆಯಾಗುತ್ತದೆ.

ಸಾರಾಂಶ

ವೇಯ್ಟೆಡ್ ರಿಸರ್ವಾಯರ್ ಸ್ಯಾಂಪಲಿಂಗ್ ವಿಡಿಯೋ ಶಿಫಾರಸು ಸೇವೆಯು ತನ್ನ ಹೋಂ ಪೇಜ್ ಅನ್ನು ತಾಜಾವಾಗಿಡಲು, relevance scores ಅನ್ನು ಗೌರವಿಸಲು ಮತ್ತು ಮೆಮೊರಿ ಬಳಕೆಯನ್ನು ಕಡಿಮೆ ಮಾಡಲು ಸಹಾಯ ಮಾಡುತ್ತದೆ—ಇವೆಲ್ಲವೂ ಹತ್ತಾರು ಸಾವಿರ ಅಭ್ಯರ್ಥಿಗಳ ಮೇಲೆ ಕೇವಲ ಒಂದೇ ಒಂದು ಪಾಸ್ ಮೂಲಕ ಸಾಧ್ಯವಾಗುತ್ತದೆ. ಕೀ ಲೆಕ್ಕಾಚಾರವನ್ನು log space ಗೆ ವರ್ಗಾಯಿಸುವ ಮೂಲಕ ಮತ್ತು min-heap ಅನ್ನು ಬಳಸುವ ಮೂಲಕ, ಈ ವಿಧಾನವು ನಿಖರ ಮತ್ತು ಕಾರ್ಯಕ್ಷಮತೆಯಿಂದ ಕೂಡಿದೆ.