लुसेन का एल्गोरिदम

Question

मैंने डॉग कटिंग द्वारा पेपर पढ़ा; "Space optimizations for total ranking"।

चूंकि इसे बहुत समय पहले लिखा गया था, मुझे आश्चर्य है कि एल्गोरिदम ल्यूसीन क्या उपयोग करता है (पोस्टिंग सूची ट्रैवर्सल और स्कोर गणना, रैंकिंग के संबंध में)।

विशेष रूप से, वर्णित कुल रैंकिंग एल्गोरिदम में प्रत्येक क्वेरी शब्द के लिए संपूर्ण पोस्टिंग सूची को घुमाने में शामिल होना शामिल है, इसलिए "पीले कुत्ते" जैसे बहुत सामान्य प्रश्नों के मामले में, 2 शब्दों में से कोई भी बहुत लंबी पोस्टिंग हो सकती है वेब खोज के मामले में सूची। क्या वे सभी वास्तव में वर्तमान लुसीन/सोलर में घुस गए हैं? या नियोजित सूची को कम करने के लिए कोई हेरिस्टिक है?

मामले में जब केवल शीर्ष के परिणाम लौटाए जाते हैं, तो मैं समझ सकता हूं कि कई मशीनों में पोस्टिंग सूची वितरित करना और फिर प्रत्येक से शीर्ष-के संयोजन करना काम करेगा, लेकिन अगर हमें "100 वें" परिणाम पृष्ठ ", यानी परिणाम 9 0 9 -1000 से रैंक किए गए, फिर प्रत्येक विभाजन को अभी भी शीर्ष 1000 का पता लगाना होगा, इसलिए विभाजन बहुत मदद नहीं करेगा।

कुल मिलाकर, लुसीन द्वारा उपयोग किए जाने वाले आंतरिक एल्गोरिदम पर कोई अद्यतित विस्तृत दस्तावेज है?

Answer 1

मुझे ऐसे दस्तावेज से अवगत नहीं है, लेकिन चूंकि लुसीन ओपन-सोर्स है, इसलिए मैं आपको स्रोत कोड पढ़ने के लिए प्रोत्साहित करता हूं। विशेष रूप से, वर्तमान ट्रंक संस्करण में flexible indexing शामिल है, जिसका अर्थ है कि भंडारण और पोस्टिंग सूची ट्रैवर्सल को शेष कोड से डीकॉप्ल किया गया है, जिससे कस्टम कोडेक्स लिखना संभव हो जाता है।

आप मान्यताओं पोस्टिंग सूची ट्रेवर्सल के बारे में सही हैं, डिफ़ॉल्ट रूप से (यह अपने Scorer कार्यान्वयन पर निर्भर करता है) Lucene प्रत्येक प्रश्न में वर्तमान अवधि के लिए पूरी पोस्टिंग सूची को पार करता है और आकार कश्मीर का एक ढेर शीर्ष गणना करने के लिए में मिलान दस्तावेजों डालता है -के दस्तावेज़ (TopDocsCollector देखें)। तो 9 0 9 से 1000 तक के परिणाम लौटने से ल्यूसीन आकार 1000 के ढेर को तत्काल बना देता है। और यदि आप दस्तावेज़ द्वारा अपनी अनुक्रमणिका को विभाजित करते हैं (एक और दृष्टिकोण शब्द के अनुसार विभाजित किया जा सकता है), प्रत्येक शार्ड को सर्वर पर शीर्ष 1000 परिणाम भेजने की आवश्यकता होगी जो कि है परिणामों को विलय करने के लिए ज़िम्मेदार (उदाहरण के लिए सोलर QueryComponent देखें, जो एन से पी> एन से एक क्वेरी का अनुवाद 0 से पी sreq.params.set(CommonParams.START, "0"); से कई शार्ड अनुरोधों में करता है)। यही कारण है कि चरम पेजिंग के मामले में स्टैंडअलोन मोड की तुलना में सौर वितरित मोड में धीमा हो सकता है।

मैं Google कुशलतापूर्वक परिणाम स्कोर करने के लिए प्रबंधन करता है पता नहीं है, लेकिन ट्विटर एक paper on their retrieval engine Earlybird प्रकाशित जहां वे बताएं कि किस तरह वे आदेश पोस्टिंग सूची के कुशल विपरीत कालानुक्रमिक क्रम ट्रेवर्सल है, जो उन्हें सबसे वापस लौट सकते हैं करने के लिए Lucene समझौता हालिया ट्वीट्स प्रत्येक शब्द के लिए पूरी पोस्टिंग सूची को घुमाने के बिना किसी क्वेरी से मेल खाते हैं।

अद्यतन: मैं गूगलर Jeff Dean, जो बताते हैं कि कैसे गूगल अपनी बड़े पैमाने पर सूचना पुनर्प्राप्ति सिस्टम बनाया से इस presentation पाया। विशेष रूप से, यह शेरिंग रणनीतियों और पोस्टिंग एन्कोडिंग पोस्ट करने के बारे में बात करता है।