Abstract
As Question & Answer (Q&A) forums scale to hundreds of millions of posts, content redundancy becomes a significant barrier to search quality and user experience. This paper proposes a highly scalable, MapReduce-based framework for detecting near-duplicate threads. By employing distributed inverted indexing and a mathematically tighter upper bound for Jaccard similarity, the system efficiently identifies redundant content across massive datasets without the computational overhead of deep linguistic processing.
Introduction
Popular Q&A platforms like Quora and Baidu Zhidao face a growing challenge: users frequently ask identical or highly similar questions. Unlike general web pages, Q&A threads are structured (comprising a title, description, and best answer) and typically short (often under 400 words). Detecting duplicates at this scale requires algorithms that are both computationally efficient and capable of handling the unique structural properties of forum content.
System Architecture
The proposed system utilizes a four-stage pipeline designed for distributed execution within a MapReduce framework.
- Text-based Signature Extraction: Signatures (e.g., n-grams) are extracted independently for the "Question," "Description," and "Best Answer" sections.
- Distributed Inverted Indexing: The system builds an index to map signatures back to the threads containing them.
- Similarity Calculation: Jaccard similarity is computed between thread signatures. A novel, tighter upper bound is used to prune pairs that cannot possibly meet the similarity threshold.
- Near-Duplicate Detection: A weighted combination of component similarities determines the final classification.
Distributed Processing with MapReduce
To handle millions of threads, the authors compared term-based and document-based indexing strategies. While term-based indexing is common in search, it often requires lossy approximations to manage intermediate data volume in similarity tasks. In contrast, the document-based approach proved more robust for exact similarity computation at scale.
As shown in the MapReduce workflow, the "Doc-based" approach maps document IDs ($D_n$) to their signatures ($S_n$), which are then sorted and grouped to produce an inverted index. This structure allows for efficient pairwise comparison without the accuracy trade-offs inherent in term-based pruning.
Experimental Results
The system was evaluated using a corpus of 28.6 million Q&A pairs from Baidu Zhidao. Key findings include:
- Signature Efficacy: 3-Shingles emerged as the most effective signature method, particularly for "Description" and "Answer" sections, achieving $F_1$ scores above 95%.
- Detection Accuracy: The system achieved a high precision of 94.98%, with an overall $F_1$ score of 66.22%.
- Redundancy Scale: Analysis revealed that approximately 15.78% of threads in a 3-million post subset had at least one near-duplicate, confirming the high level of redundancy in real-world forums.
Insights and Limitations
A primary challenge identified is the "Vocabulary Mismatch" problem, where semantically identical questions use different wording. While the current signature-based approach is highly precise and scalable, it struggles with recall (50.83%) because it relies on lexical overlap. Future work involves integrating more advanced NLP techniques to capture semantic meaning while maintaining the efficiency required for massive-scale processing.
Summary updated