Introduction
Collaborative Filtering (CF) remains a cornerstone of modern recommendation engines, leveraging user-item interactions to predict preferences. However, as user bases expand into the millions, the computational cost of maintaining similarity lists—essential for identifying "neighbors"—becomes a significant bottleneck. Traditional approaches typically scale at $O(n^2)$, making real-time updates for new users increasingly difficult.
Problem Statement: The "Twin User" Scenario
While much research focuses on the "cold-start" problem where new users have no data, this paper addresses a specific but frequent occurrence: the "twin user." A twin user is a new entrant whose rating profile is identical to an existing user in the system. This phenomenon occurs naturally in specialized communities or can be induced by "shilling attacks," where malicious actors inject identical bot profiles to manipulate recommendation outcomes. Standard CF algorithms treat these identical profiles as unique entities, redundantly recalculating similarity scores and wasting significant computational resources.
The TwinSearch Algorithm
The proposed TwinSearch algorithm optimizes this process by shifting from exhaustive computation to an efficient "search and copy" strategy. The methodology is grounded in the observation that user similarity scores in CF systems generally follow a Gaussian (normal) distribution.
The algorithm operates in five key stages:
- Random Sampling: Selecting a small constant number ($c$) of random users.
- Similarity Calculation: Computing the similarity between the new user and these $c$ users.
- Candidate Filtering: Identifying potential twins by searching the similarity lists of the $c$ users. If two users are identical, their similarity to any third party must be identical.
- Intersection: Narrowing the candidate pool by intersecting the sets derived from the $c$ users.
- Verification: Performing a final direct rating comparison to confirm a match and cloning the twin's existing similarity list.
By exploiting the properties of the similarity distribution, the authors demonstrate that the search space for potential twins can be reduced to approximately $1/125$ of the total user base.
Experimental Evaluation
The algorithm was tested on two real-world datasets: MovieLens (100,000 ratings) and Douban (16.8 million ratings). The results highlight a dramatic improvement in scalability.
As shown in the experimental results, the "Traditional" approach exhibits a steep linear increase in processing time as the number of users grows. In contrast, the TwinSearch algorithm's running time remains nearly flat, effectively decoupling the cost of adding "twin" users from the overall size of the system. Theoretically, this reduces the computational complexity from $O(n^2)$ to roughly $O(\frac{1}{125}n^2)$.
Conclusion and Future Directions
TwinSearch provides a robust solution for handling identical user profiles in CF systems, offering a speedup factor of over 100 in typical scenarios. Beyond performance, it serves as a defense mechanism against shilling attacks by making the processing of injected identical profiles computationally trivial. Future work may explore "fuzzy" matching for near-identical users and the impact of dynamic rating updates on established twin relationships.
Summary updated