Scalable user clustering based on set similarity

Details Scalable user clustering based on set similarity Scalable user clustering based on set similarity

2005-08-15

2010-06-15

Rones, Charles (Department: 2164)

Data processing: database and file management or data structures

Database design

Database and data structure management

C707S804000

Reexamination Certificate

active

07739314

ABSTRACT:
Methods and apparatus, including systems and computer program products, to provide clustering of users in which users are each represented as a set of elements representing items, e.g., items selected by users using a system. In one aspect, a program operates to obtain a respective interest set for each of multiple users, each interest set representing items in which the respective user expressed interest; for each of the users, to determine k hash values of the respective interest set, wherein the i-th hash value is a minimum value under a corresponding i-th hash function; and to assign each of the multiple users to each of the respective k clusters established for the respective user, the i-th cluster being represented by the i-th hash value. The assignment of each of the users to k clusters is done without regard to the assignment of any of the other users to k clusters.

REFERENCES:
patent: 5909677 (1999-06-01), Broder et al.
patent: 6119124 (2000-09-01), Broder et al.
patent: 6134532 (2000-10-01), Lazarus et al.
patent: 6230155 (2001-05-01), Broder et al.
patent: 6349296 (2002-02-01), Broder et al.
patent: 6850252 (2005-02-01), Hoffberg
patent: 6912505 (2005-06-01), Linden et al.
patent: 7072886 (2006-07-01), Salmenkaita et al.
patent: 2003/0061233 (2003-03-01), Manasse et al.
patent: 2004/0139072 (2004-07-01), Broder et al.
Broder et al., “Min-Wise Independent Permutations,”Journal of Computer Systems and Sciences, 2000, 60(3):630-659, (special issue for STOC '98), preliminary version in Proceedings of the 30th Annual ACM Symposium on Theory of Computing (1998).
Charikar, “Similarity Estimation Techniques from Rounding Algorithms,”STOC '02, May 19-21, 2002, Montreal, Quebec, Canada, 9 pages.
Charikar et al., “Incremental Clustering and Dynamic Information Retrieval,”STOC '97,1997 , El Paso, TX, pp. 626-635.
Cohen et al., “Finding Interesting Associations without Support Pruning,”16th Int'l. Conf. on Data Engineering(ICDE) , 2000, 17 pages.
Datar et al., “Locality-Sensitive Hashing Scheme Based on p-Stable Distributions”,SCG '04, Jun. 9-11, 2004, pp. 253-262.
Dean and Ghemawat, “MapReduce: Simplified Data Processing on Large Clusters,”OSDI, 2004, 13 pages.
Gr{hacek over (c)}ar “User Profiling: Collaborative Filtering,”SIKDD 2004, Oct. 12-15, 2004, Ljubljana, Slovenia, 4 pages.
Haveliwala et al., “Scalable Techniques for Clustering the Web,”Proceedings of WebDB, 2000, 6 pages.
Hofmann, “Latent Semantic Models for Collaborative Filtering,”ACM Transactions on Information Systems, 2004, 22(1):89-115.
Lemire, “Scale and Translations Invariant Collaborative Filtering Systems,”Information Retrieval, 2005, 8(1):129-150.
Papadimitriou et al., “Latent Semantic Indexing: A Probabilistic Analysis,”PODS 98, (preliminary version)JCSS, special edition (full version), Nov. 14, 1997, 21 pages.
Schwab and Kobsa, “Adaptivity through Unobtrusive Learning,” 2002, 16(3):5-9.
Wang, “Self-organising Communities Formed by Middle Agents,”AAMAS '02, Jul. 15-19, 2002, Bologna, Italy, pp. 1333-1339.
Xiao et al., “Measuring Similarity of Interests for Clustering Web-Users,”ADC, 2001, pp. 107-114.
Xie and Phoha, “Web User Clustering from Access Log Using Belief Function,”K-CAP '01, Oct. 22-23, 2001, Victoria, British Columbia, Canada, pp. 202-208.
Yu et al., “Selecting Relevant Instances for Efficient and Accurate Collaborative Filtering,”CIKM '01, Nov. 5-10, 2001, Atlanta, Georgia, pp. 239-246.
Zeng et al., “Similarity Measure and Instance Selection for Collaborative Filtering,”WWW '03, May 20-24, 2003, Budapest, Hungary, pp. 652-658.
Cohen, “Size-Estimation Framework with Applications to Transitive Closure and Reachability,”J. Comput. System Sci., 1997, 55(3):441-453.
Indyk and Motwani, “Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality,”Proceedings of the 30th Annual ACM Symposium on Theory of Computing, 1998, 20 pages.

Affiliated with

Also associated with

Rating

Scalable user clustering based on set similarity does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Scalable user clustering based on set similarity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Scalable user clustering based on set similarity will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4205639