ਸਾਡਾ ਵੀਡੀਓ ਹੋਮਪੇਜ ਹੁਣ ਹਰ ਰਿਫ੍ਰੈਸ਼ 'ਤੇ 24 ਨਵੀਆਂ ਸਿਫਾਰਸ਼ਾਂ (recommendations) ਦਿਖਾਉਂਦਾ ਹੈ, ਜਿਸਦਾ ਕਾਰਨ ਵੇਟਡ ਰੈਜ਼ਰਵੋਇਰ ਸੈਂਪਲਿੰਗ (weighted reservoir sampling - A-Res) ਵਿੱਚ ਬਦਲਾਅ ਹੈ। ਇਸ ਤਬਦੀਲੀ ਨੇ "ਹਮੇਸ਼ਾ ਇੱਕੋ ਜਿਹੀ ਗਰਿੱਡ" ਵਾਲੀ ਸਮੱਸਿਆ ਨੂੰ ਖਤਮ ਕਰ ਦਿੱਤਾ ਹੈ ਜੋ ਸਾਡੇ ਪਹਿਲਾਂ ਵਾਲੇ ਸਕੋਰ-ਸੌਰਟਡ ਫੀਡ (score-sorted feed) ਵਿੱਚ ਆ ਰਹੀ ਸੀ।
ਪੁਰਾਣਾ ਤਰੀਕਾ ਅਨੁਭਵ ਨੂੰ ਕਿਉਂ ਖਰਾਬ ਕਰ ਰਿਹਾ ਸੀ
ਹਰ ਦੋ ਘੰਟਿਆਂ ਬਾਅਦ ਅਸੀਂ ਅੱਠ ਖੇਤਰਾਂ ਤੋਂ ਤਾਜ਼ਾ ਟ੍ਰੈਂਡਿੰਗ ਵੀਡੀਓਜ਼ ਲੈਂਦੇ ਹਾਂ ਅਤੇ ਨਤੀਜਿਆਂ ਨੂੰ SQLite ਟੇਬਲ ਵਿੱਚ ਪਾ ਦਿੰਦੇ ਹਾਂ। ਸਧਾਰਨ ਹੱਲ ਪੂਰੇ ਸੈੱਟ ਨੂੰ—relevance score ਦੇ ਆਧਾਰ 'ਤੇ—ਸੌਰਟ ਕਰਨਾ ਅਤੇ ਚੋਟੀ ਦੇ 24 ਵੀਡੀਓਜ਼ ਲੈਣਾ ਸੀ। ਉਹ ਤਰੀਕਾ ਇਹ ਯਕੀਨੀ ਬਣਾਉਂਦਾ ਹੈ ਕਿ ਸਭ ਤੋਂ ਵੱਧ ਸਕੋਰ ਵਾਲੀਆਂ ਚੀਜ਼ਾਂ ਦਿਖਾਈ ਦੇਣ, ਪਰ ਇਹ ਇਹ ਵੀ ਯਕੀਨੀ ਬਣਾਉਂਦਾ ਹੈ ਕਿ ਉਹ ਉੱਥੇ ਹੀ ਰਹਿਣ। ਇੱਕ ਸਿੰਗਲ ਵਾਇਰਲ ਕਲਿੱਪ ਕਈ ਦਿਨਾਂ ਤੱਕ ਪਹਿਲੇ ਨੰਬਰ 'ਤੇ ਰਹਿ ਸਕਦੀ ਹੈ, ਅਤੇ ਯੂਜ਼ਰਸ ਜਦੋਂ ਵੀ ਰੀਲੋਡ ਕਰਦੇ ਹਨ, ਉਹਨਾਂ ਨੂੰ ਹਰ ਵਾਰ ਇੱਕੋ ਜਿਹੀ ਗਰਿੱਡ ਦਿਖਾਈ ਦਿੰਦੀ ਹੈ।
ਪੁਰਾਣੇ ਅਨੁਭਵ ਤੋਂ ਇਲਾਵਾ, ਹਰ ਰਿਕਵੈਸਟ ਲਈ ਪੂਰੀ ਟੇਬਲ ਨੂੰ ਸੌਰਟ ਕਰਨ ਨਾਲ SQLite ਨੂੰ ਮੈਮੋਰੀ ਵਿੱਚ ਇੱਕ ਵੱਡੀ ਟੈਂਪਰੇਰੀ ਸਟ੍ਰਕਚਰ ਲੋਡ ਕਰਨ ਲਈ ਮਜਬੂਰ ਹੋਣਾ ਪੈਂਦਾ ਹੈ, ਜੋ ਕਿ ਬੇਕਾਰ ਹੈ।
ਵੇਟਡ ਰੈਜ਼ਰਵੋਇਰ ਸੈਂਪਲਿੰਗ ਸਾਨੂੰ ਕੀ ਦਿੰਦੀ ਹੈ
ਵੇਟਡ ਰੈਜ਼ਰਵੋਇਰ ਸੈਂਪਲਿੰਗ ਦੋ ਸਮੱਸਿਆਵਾਂ ਨੂੰ ਇੱਕੋ ਸਮੇਂ ਹੱਲ ਕਰਦੀ ਹੈ:
- ਬਾਇਸ (bias) ਦੇ ਨਾਲ ਤਾਜ਼ਗੀ – ਹਰ ਵੀਡੀਓ ਦੇ ਚੁਣੇ ਜਾਣ ਦੀ ਸੰਭਾਵਨਾ ਉਸਦੇ ਵੇਟ (weight) ਦੇ ਅਨੁਪਾਤ ਵਿੱਚ ਹੁੰਦੀ ਹੈ (ਜਿਵੇਂ ਕਿ relevance score)। ਜਿਸ ਵੀਡੀਓ ਦਾ ਵੇਟ ਦੁੱਗਣਾ ਹੈ, ਉਸਦੇ ਦਿਖਾਈ ਦੇਣ ਦੀ ਸੰਭਾਵਨਾ ਦੁੱਗਣੀ ਹੈ, ਪਰ ਕਿਸੇ ਵੀ ਚੀਜ਼ ਦੀ ਜਗ੍ਹਾ ਯਕੀਨੀ ਨਹੀਂ ਹੁੰਦੀ।
- ਮੈਮੋਰੀ ਕੁਸ਼ਲਤਾ (Memory efficiency) – ਇਹ ਐਲਗੋਰਿਦਮ ਸਿਰਫ਼ k ਆਈਟਮਾਂ ਦਾ ਇੱਕ ਨਿਸ਼ਚਿਤ ਆਕਾਰ ਦਾ "ਰੈਜ਼ਰਵੋਇਰ" (reservoir) ਰੱਖਦਾ ਹੈ (ਸਾਡੀ ਫੀਡ ਲਈ k = 24)। ਇਹ ਸਟ੍ਰੀਮ ਨੂੰ ਇੱਕੋ ਵਾਰ (single pass) ਵਿੱਚ ਪ੍ਰੋਸੈਸ ਕਰਦਾ ਹੈ, ਇਸ ਲਈ ਕਿੰਨੇ ਵੀ ਉਮੀਦਵਾਰ ਆਉਣ, ਮੈਮੋਰੀ O(k) ਹੀ ਰਹਿੰਦੀ ਹੈ।
ਮੁੱਖ ਵਿਚਾਰ ਸਰਲ ਹੈ। ਜਿਵੇਂ ਹੀ ਅਸੀਂ ਆ ਰਹੀਆਂ ਰੋਅਜ਼ (rows) ਨੂੰ ਸਕੈਨ ਕਰਦੇ ਹਾਂ, ਅਸੀਂ ਹਰ ਆਈਟਮ ਨੂੰ ਇੱਕ ਰੈਂਡਮ ਕੀ (random key) ਦਿੰਦੇ ਹਾਂ ਜਿਸ ਵਿੱਚ ਉਸਦਾ ਵੇਟ ਸ਼ਾਮਲ ਹੁੰਦਾ ਹੈ, ਫਿਰ ਸਭ ਤੋਂ ਵੱਧ ਕੀ ਵਾਲੀਆਂ k ਆਈਟਮਾਂ ਨੂੰ ਰੱਖ ਲੈਂਦੇ ਹਾਂ।
ਅਭਿਆਸ ਵਿੱਚ ਐਲਗੋਰਿਦਮ
ਹਰ ਵੀਡੀਓ ਲਈ ਅਸੀਂ:
- ਇੱਕ ਯੂਨੀਫਾਰਮ ਰੈਂਡਮ ਨੰਬਰ
u ∈ (0, 1)ਲੈਂਦੇ ਹਾਂ। - ਇੱਕ ਕੀ
k = u^(1/weight)ਦੀ ਗਣਨਾ ਕਰਦੇ ਹਾਂ।
(ਵੇਟ ਜਿੰਨਾ ਜ਼ਿਆਦਾ ਹੋਵੇਗਾ, ਉਮੀਦ ਕੀਤੀ ਗਈ ਕੀ ਉੰਨੀ ਹੀ ਵੱਡੀ ਹੋਵੇਗੀ।) - ਆਈਟਮ ਨੂੰ ਇੱਕ min-heap ਵਿੱਚ ਪਾਉਂਦੇ ਹਾਂ ਜੋ ਮੌਜੂਦਾ ਚੋਟੀ ਦੀਆਂ
kਕੀਜ਼ ਨੂੰ ਸਟੋਰ ਕਰਦਾ ਹੈ।
ਜੇਕਰ ਹੀਪ (heap) ਦਾ ਆਕਾਰkਤੋਂ ਵੱਧ ਜਾਂਦਾ ਹੈ, ਤਾਂ ਅਸੀਂ ਸਭ ਤੋਂ ਛੋਟੀ ਕੀ ਨੂੰ ਰੱਦ ਕਰ ਦਿੰਦੇ ਹਾਂ।
ਜਦੋਂ ਸਟ੍ਰੀਮ ਖਤਮ ਹੁੰਦੀ ਹੈ, ਤਾਂ ਹੀਪ ਵਿੱਚ ਉਹ 24 ਵੀਡੀਓਜ਼ ਹੁੰਦੇ ਹਨ ਜੋ ਅਸੀਂ ਦਿਖਾਵਾਂਗੇ।
ਫਲੋਟਿੰਗ-ਪੁਆਇੰਟ (floating-point) ਸੀਮਾਵਾਂ ਨਾਲ ਨਜਿੱਠਣਾ
ਜਦੋਂ ਕਿਸੇ ਵੀਡੀਓ ਦਾ ਵੇਟ ਬਹੁਤ ਜ਼ਿਆਦਾ ਹੁੰਦਾ ਹੈ, ਤਾਂ u^(1/weight) ਦੀ ਕੀਮਤ ਡਬਲ-ਪ੍ਰੀਸੀਜ਼ਨ ਅਰਿਥਮੈਟਿਕ (double-precision arithmetic) ਵਿੱਚ 1.0 ਤੋਂ ਵੱਖਰੀ ਨਹੀਂ ਰਹਿੰਦੀ, ਜਿਸ ਕਾਰਨ ਕਈ ਭਾਰੀ ਆਈਟਮਾਂ ਇੱਕੋ ਜਿਹੀ ਕੀ ਸਾਂਝੀ ਕਰਦੀਆਂ ਹਨ ਅਤੇ ਰੈਂਡਮਨੈੱਸ ਖਤਮ ਹੋ ਜਾਂਦੀ ਹੈ। ਇਸ ਦਾ ਹੱਲ ਲੌਗ ਸਪੇਸ (log space) ਵਿੱਚ ਕੰਮ ਕਰਨਾ ਹੈ:
- ਪਾਵਰ ਐਕਸਪ੍ਰੈਸ਼ਨ ਦੀ ਬਜਾਏ
log_key = log(u) / weightਦੀ ਗਣਨਾ ਕਰੋ।
ਕਿਉਂਕਿ ਲੌਗਰਿਦਮ ਐਕਸਪੋਨੈਂਸ਼ੀਏਸ਼ਨ (exponentiation) ਨੂੰ ਗੁਣਾ ਵਿੱਚ ਬਦਲ ਦਿੰਦੇ ਹਨ, ਇਸ ਨਾਲ ਪ੍ਰੀਸੀਜ਼ਨ (precision) ਦੀ ਸਮੱਸਿਆ ਤੋਂ ਬਚਦੇ ਹੋਏ ਕੀਜ਼ ਦਾ ਕ੍ਰਮ ਬਣਿਆ ਰਹਿੰਦਾ ਹੈ। ਇਸ ਗਣਨਾ ਵਿੱਚ ਲਗਭਗ ਕੋਈ ਵਾਧੂ ਲਾਗਤ ਨਹੀਂ ਆਉਂਦੀ।
ਇੰਪਲੀਮੈਂਟੇਸ਼ਨ ਚੈੱਕਲਿਸਟ
- ਡਾਟਾ ਸਟ੍ਰਕਚਰ:
kਆਕਾਰ ਦਾ ਇੱਕ min-heap (priority queue) ਵੱਡੀਆਂ ਕੀਜ਼ ਨੂੰ ਕੁਸ਼ਲਤਾ ਨਾਲ ਰੱਖਦਾ ਹੈ (ਪ੍ਰਤੀ ਇੰਸਰਸ਼ਨ O(log k))। - ਨਿਊਮੈਰਿਕ ਟਾਈਪ:
uਅਤੇ ਲੌਗ-ਅਧਾਰਤ ਕੀਜ਼ ਲਈ 64-bit ਫਲੋਟਿੰਗ-ਪੁਆਇੰਟ ਨੰਬਰਾਂ ਦੀ ਵਰਤੋਂ ਕਰੋ; ਇਹ ਆਮ ਵੇਟ ਰੇਂਜਾਂ ਲਈ ਲੋੜੀਂਦੀ ਪ੍ਰੀਸੀਜ਼ਨ ਪ੍ਰਦਾਨ ਕਰਦੇ ਹਨ। - ਸਟੈਟਿਸਟੀਕਲ ਸੈਨਿਟੀ ਚੈੱਕ: ਇੱਕ ਛੋਟੇ ਸੈਂਪਲ ਸੈੱਟ 'ਤੇ ਤੇਜ਼ੀ ਨਾਲ ਮੋਂਟੇ-ਕਾਰਲੋ (Monte-Carlo) ਟੈਸਟ ਚਲਾਓ। ਜੇਕਰ ਵੇਟ 10 ਵਾਲੀਆਂ ਆਈਟਮਾਂ ਵੇਟ 1 ਵਾਲੀਆਂ ਆਈਟਮਾਂ ਨਾਲੋਂ ਲਗਭਗ ਦਸ ਗੁਣਾ ਵਧੇਰੇ ਵਾਰ ਦਿਖਾਈ ਦਿੰਦੀਆਂ ਹਨ, ਤਾਂ ਇੰਪਲੀਮੈਂਟੇਸ਼ਨ ਸਹੀ ਹੈ।
- ਸਿੰਗਲ-ਪਾਸ ਸਟ੍ਰੀਮਿੰਗ: ਐਲਗੋਰਿਦਮ ਨੂੰ ਪਹਿਲਾਂ ਤੋਂ ਉਮੀਦਵਾਰਾਂ ਦੀ ਕੁੱਲ ਸੰਖਿਆ ਜਾਣਨ ਦੀ ਲੋੜ ਨਹੀਂ ਹੈ, ਜੋ ਸਾਡੇ SQLite ਕਰਸਰ (cursor) ਦੇ ਅਨੁਕੂਲ ਹੈ ਜੋ ਇੱਕ-ਇੱਕ ਕਰਕੇ ਰੋਅਜ਼ (rows) ਪ੍ਰਦਾਨ ਕਰਦਾ ਹੈ।
ਸਿੱਖਿਆ (Takeaway)
ਵੇਟਡ ਰੈਜ਼ਰਵੋਇਰ ਸੈਂਪਲਿੰਗ ਇੱਕ ਵੀਡੀਓ ਰੈਕਮੈਂਡੇਸ਼ਨ ਸਰਵਿਸ ਨੂੰ ਆਪਣਾ ਹੋਮਪੇਜ ਤਾਜ਼ਾ ਰੱਖਣ, ਰੇਲੇਵੈਂਸ ਸਕੋਰਾਂ ਦਾ ਸਤਿਕਾਰ ਕਰਨ ਅਤੇ ਮੈਮੋਰੀ-ਹਲਕਾ ਰਹਿਣ ਵਿੱਚ ਮਦਦ ਕਰਦੀ ਹੈ—ਇਹ ਸਭ ਦਸ ਹਜ਼ਾਰਾਂ ਉਮੀਦਵਾਰਾਂ 'ਤੇ ਇੱਕੋ ਇੱਕ ਪਾਸ (single pass) ਨਾਲ ਸੰਭਵ ਹੈ। ਕੀ ਦੀ ਗਣਨਾ ਨੂੰ ਲੌਗ ਸਪੇਸ ਵਿੱਚ ਲੈ ਕੇ ਜਾ ਕੇ ਅਤੇ min-heap ਦੀ ਵਰਤੋਂ ਕਰਕੇ, ਇਹ ਤਰੀਕਾ ਸਹੀ ਅਤੇ ਪ੍ਰਦਰਸ਼ਨਸ਼ੀਲ (performant) ਬਣਿਆ ਰਹਿੰਦਾ ਹੈ।