Competitive recommendation systems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Competitive recommendation systems

Full text

Pdf (244 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thiry-fourth annual ACM symposium on Theory of computing table of contents

Montreal, Quebec, Canada

SESSION: Session 2A table of contents

Pages: 82 - 90

Year of Publication: 2002

ISBN:1-58113-495-9

Authors

Petros Drineas	Yale University
Iordanis Kerenidis	University of California, Berkeley
Prabhakar Raghavan	Verity, Inc., Sunnyvale, CA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 10, Downloads (12 Months): 62, Citation Count: 19

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/509907.509922 What is a DOI?

ABSTRACT

A recommendation system tracks past purchases of a group of users to make product recommendations to individual members of the group. In this paper we present a notion of competitive recommendation systems, building on recent theoretical work on this subject. We reduce the problem of achieving competitiveness to a problem in matrix reconstruction. We then present a matrix reconstruction scheme that is competitive: it requires a small overhead in the number of users and products to be sampled, delivering in the process a net utility that closely approximates the best possible with full knowledge of all user-product preferences.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Dimitris Achlioptas , Frank McSherry, Fast computation of low rank matrix approximations, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.611-618, July 2001, Hersonissos, Greece [doi>10.1145/380752.380858]
	2	Robert B. Allen, User models: theory, method, and practice, International Journal of Man-Machine Studies, v.32 n.5, p.511-543, May 1990 [doi>10.1016/S0020-7373(05)80032-X]
	3	Yossi Azar , Amos Fiat , Anna Karlin , Frank McSherry , Jared Saia, Spectral analysis of data, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.619-626, July 2001, Hersonissos, Greece [doi>10.1145/380752.380859]
	4	M.J. Berry and G. Linoff. Data Mining Techniques. John-Wiley, 1997.
	5	Michael W. Berry , Susan T. Dumais , Gavin W. O'Brien, Using linear algebra for intelligent information retrieval, SIAM Review, v.37 n.4, p.573-595, Dec. 1995 [doi>10.1137/1037127]
	6	J. Bettman. An Information Processing Theory of Consumer Choice. Addison-Wesley Publishing Company, 1979.
	7	Robert C. Blattberg , Rashi Glazer , John D. Little, The Marketing Information Revolution, Harvard Business School Press, Boston, MA, 1994
	8	B. Bollobas. Random Graphs. Academic Press, NY, 1985.
	9	R. Boppana. Eigenvalues and graph bisection: An average-case analysis, Proc. IEEE Symp. on Foundations of Computer Science, 1987.
	10	Moses Charikar , Ravi Kumar , Prabhakar Raghavan , Sridhar Rajagopalan , Andrew Tomkins, On targeting Markov segments, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.99-108, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301280]
	11	S. Deerwester, S. T. Dumais, T.K. Landauer, G.W. Furnas, and R.A.~Harshman. Indexing by latent semantic analysis. Journal of the Society for Information Science, 41(6):391--407, 1990.
	12	P. Drineas , Alan Frieze , Ravi Kannan , Santosh Vempala , V. Vinay, Clustering in large graphs and matrices, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.291-299, January 17-19, 1999, Baltimore, Maryland, United States
	13	P. Drineas , R. Kannan, Fast Monte-Carlo Algorithms for Approximate Matrix Multiplication, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.452, October 14-17, 2001
	14	P. Drineas and R. Kannan, Pass Efficient Algorithms for Large Matrices, manuscript, 2001.
	15	Alan Frieze , Ravi Kannan , Santosh Vempala, Fast Monte-Carlo Algorithms for finding low-rank approximations, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.370, November 08-11, 1998
	16	Z. Furedi and J. Komlos, The eigenvalues of random symmetric matrices, Combinatorica 1 (1981), pp. 233-241.
	17	R. Glazer. Marketing in an information-intensive environment: Strategic implications of knowledge as an asset, Journal of Marketing, 55:1--19, 1991.
	18	David Goldberg , David Nichols , Brian M. Oki , Douglas Terry, Using collaborative filtering to weave an information tapestry, Communications of the ACM, v.35 n.12, p.61-70, Dec. 1992 [doi>10.1145/138859.138867]
	19	G. Golub, C.F. Van Loan, Matrix Computations, Johns Hopkins University Press, 1989.
	20	W. Hoeffding, Probability inequalities for sums of bounded random variables, American Statistical Association Journal, March 1962, pp. 13--30.
	21	Will Hill , Larry Stead , Mark Rosenstein , George Furnas, Recommending and evaluating choices in a virtual community of use, Proceedings of the SIGCHI conference on Human factors in computing systems, p.194-201, May 07-11, 1995, Denver, Colorado, United States [doi>10.1145/223904.223929]
	22	D.L. Hoffman and T.P. Novak. Marketing in hypermedia computer-mediated environments: Conceptual foundations. Journal of Marketing, 60:50--68, 1996.
	23	J. Howard. Consumer Behavior in Marketing Strategy, Prentice Hall, Englewood Cliffs, NJ, 1989.
	24	Jon Kleinberg , Christos Papadimitriou , Prabhakar Raghavan, Segmentation problems, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.473-482, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276860]
	25	Jon Kleinberg , Christos H. Papadimitriou , Prabhakar Raghavan, On the value of private information, Proceedings of the 8th conference on Theoretical aspects of rationality and knowledge, July 08-10, 2001, Siena, Italy
	26	Ravi Kumar , Prabhakar Raghavan , Sridhar Rajagopalan , Andrew Tomkins, Recommendation Systems: A Probabilistic Analysis, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.664, November 08-11, 1998
	27	B.N. Miller, J.T. Riedl, J.A. Konstan. Experiences with GroupLens: Making usenet useful again. Proceedings of the USENIX Conference, 1997.
	28	Christos H. Papadimitriou , Hisao Tamaki , Prabhakar Raghavan , Santosh Vempala, Latent semantic indexing: a probabilistic analysis, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.159-168, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275505]
	29	P. Resnick, N. Iacovou, M. Suchak, P. Bergstrom, J. Riedl. GroupLens: An Open Architecture for Collaborative Filtering of Netnews, Center for Coordination Science, MIT Sloan School of Management Report WP #3666--94, 1994.
	30	U. Shardanand. Social Information Filtering for Music Recommendation, Masters Thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, 1994.
	31	Upendra Shardanand , Pattie Maes, Social information filtering: algorithms for automating “word of mouth”, Proceedings of the SIGCHI conference on Human factors in computing systems, p.210-217, May 07-11, 1995, Denver, Colorado, United States [doi>10.1145/223904.223931]
	32	ACM SIGGROUP resource page on collaborative filtering. http://www.acm.org/siggroup/collab.html.
	33	L. G. Valiant, A theory of the learnable, Communications of the ACM, v.27 n.11, p.1134-1142, Nov. 1984 [doi>10.1145/1968.1972]
	34	H.R. Varian. Resources on collaborative filtering. http://www.sims.berkeley.edu/resources/collab/.
	35	Paul Resnick , Hal R. Varian, Recommender systems, Communications of the ACM, v.40 n.3, p.56-58, March 1997 [doi>10.1145/245108.245121]

CITED BY 20

	Ravindran Kannan , Santosh Vempala, Spectral Algorithms, Foundations and Trends® in Theoretical Computer Science, v.4 n.3–4, p.157-288, March 2009
	Baruch Awerbuch , Boaz Patt-Shamir , David Peleg , Mark Tuttle, Collaboration of untrusting peers with changing interests, Proceedings of the 5th ACM conference on Electronic commerce, May 17-20, 2004, New York, NY, USA
	Jon Kleinberg , Mark Sandler, Using mixture models for collaborative filtering, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	Ziv Bar-Yossef, Sampling lower bounds via information theory, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA
	Jon Kleinberg , Mark Sandler, Convergent algorithms for collaborative filtering, Proceedings of the 4th ACM conference on Electronic commerce, p.1-10, June 09-12, 2003, San Diego, CA, USA
	Michael O'Mahony , Neil Hurley , Nicholas Kushmerick , Guénolé Silvestre, Collaborative recommendation: A robustness analysis, ACM Transactions on Internet Technology (TOIT), v.4 n.4, p.344-377, November 2004
	Petros Drineas , Ravi Kannan, Pass efficient algorithms for approximating large matrices, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	Baruch Awerbuch , Boaz Patt-Shamir , David Peleg , Mark Tuttle, Improved recommendation systems, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	Baruch Awerbuch , Yossi Azar , Zvi Lotker , Boaz Patt-Shamir , Mark R. Tuttle, Collaborate with strangers to find own preferences, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA
	Michael W. Mahoney , Mauro Maggioni , Petros Drineas, Tensor-CUR decompositions for tensor-based data, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA
	Noga Alon , Baruch Awerbuch , Yossi Azar , Boaz Patt-Shamir, Tell me who I am: an interactive recommendation system, Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, July 30-August 02, 2006, Cambridge, Massachusetts, USA
	Baruch Awerbuch , Aviv Nisgav , Boaz Patt-Shamir, Asynchronous recommendation systems, Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing, August 12-15, 2007, Portland, Oregon, USA
	Daniel Lemire, Scale and Translation Invariant Collaborative Filtering Systems, Information Retrieval, v.8 n.1, p.129-150, January 2005
	Anirban Dasgupta , John Hopcroft , Ravi Kannan , Pradipta Mitra, Spectral clustering with limited independence, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.1036-1045, January 07-09, 2007, New Orleans, Louisiana
	Jon Kleinberg , Mark Sandler, Using mixture models for collaborative filtering, Journal of Computer and System Sciences, v.74 n.1, p.49-69, February, 2008
	Baruch Awerbuch , Robert Kleinberg, Competitive collaborative learning, Journal of Computer and System Sciences, v.74 n.8, p.1271-1288, December, 2008
	Feng Pan , Xiang Zhang , Wei Wang, CRD: fast co-clustering on large datasets utilizing sampling-based matrix decomposition, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada
	Hilmi Yildirim , Mukkai S. Krishnamoorthy, A random walk method for alleviating the sparsity problem in collaborative filtering, Proceedings of the 2008 ACM conference on Recommender systems, October 23-25, 2008, Lausanne, Switzerland
	Christos Boutsidis , Michael W. Mahoney , Petros Drineas, An improved approximation algorithm for the column subset selection problem, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.968-977, January 04-06, 2009, New York, New York
	Aviv Nisgav , Boaz Patt-Shamir, Finding similar users in social networks: extended abstract, Proceedings of the twenty-first annual symposium on Parallelism in algorithms and architectures, August 11-13, 2009, Calgary, AB, Canada