RecTree: An efficient collaborative filtering method

Sonny Han Seng Chee, Jiawei Han, Ke Wang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Many people rely on the recommendations of trusted friends to find restaurants or movies, which match their tastes. But, what if your friends have not sampled the item of interest? Collaborative filtering (CF) seeks to increase the effectiveness of this process by automating the derivation of a recommendation, often from a clique of advisors that we have no prior personal relationship with. CF is a promising tool for dealing with the information overload that we face in the networked world. Prior works in CF have dealt with improving the accuracy of the predictions. However, it is still challenging to scale these methods to large databases. In this study, we develop an efficient collaborative filtering method, called RecTree (which stands for RECommendation Tree) that addresses the scalability problem with a divide-and-conquer approach. The method first performs an efficient k-means-like clustering to group data and creates neighborhood of similar users, and then performs subsequent clustering based on smaller, partitioned databases. Since the progressive partitioning reduces the search space dramatically, the search for an advisory clique will be faster than scanning the entire database of users. In addition, the partitions contain users that are more similar to each other than those in other partitions. This characteristic allows RecTree to avoid the dilution of opinions from good advisors by a multitude of poor advisors and thus yielding a higher overall accuracy. Based on our experiments and performance study, RecTree outperforms the well-known collaborative filter, CorrCF, in both execution time and accuracy. In particular, RecTree’s execution time scales by O(nlog2(n)) with the dataset size while CorrCF scales quadratically.

Original languageEnglish (US)
Title of host publicationData Warehousing and Knowledge Discovery - 3rd International Conference, DaWaK 2001, Proceedings
EditorsWerner Winiwarter, Yahiko Kambayashi, Masatoshi Arikawa
PublisherSpringer
Pages141-151
Number of pages11
ISBN (Print)3540425535, 9783540425533
DOIs
StatePublished - Jan 1 2001
Externally publishedYes
Event3rd International Conference on Data Warehousing and Knowledge Discovery, DaWaK 2001 - Munich, Germany
Duration: Sep 5 2001Sep 7 2001

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2114
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other3rd International Conference on Data Warehousing and Knowledge Discovery, DaWaK 2001
Country/TerritoryGermany
CityMunich
Period9/5/019/7/01

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'RecTree: An efficient collaborative filtering method'. Together they form a unique fingerprint.

Cite this