PocketLens: Toward a personal recommender system

ABSTRACT

Recommender systems using collaborative filtering are a popular technique for reducing information overload and finding products to purchase. One limitation of current recommenders is that they are not portable. They can only run on large computers connected to the Internet. A second limitation is that they require the user to trust the owner of the recommender with personal preference data. Personal recommenders hold the promise of delivering high quality recommendations on palmtop computers, even when disconnected from the Internet. Further, they can protect the user's privacy by storing personal information locally, or by sharing it in encrypted form. In this article we present the new PocketLens collaborative filtering algorithm along with five peer-to-peer architectures for finding neighbors. We evaluate the architectures and algorithms in a series of offline experiments. These experiments show that Pocketlens can run on connected servers, on usually connected workstations, or on occasionally connected portable devices, and produce recommendations that are as good as the best published algorithms to date.

REFERENCES

• 1: Mark S. Ackerman , Lorrie Faith Cranor , Joseph Reagle, Privacy in e-commerce: examining user scenarios and privacy preferences, Proceedings of the 1st ACM conference on Electronic commerce, p.1-8, November 03-05, 1999, Denver, Colorado, United States [doi>10.1145/336992.336995]
• 2: Charu C. Aggarwal , Joel L. Wolf , Kun-Lung Wu , Philip S. Yu, Horting hatches an egg: a new graph-theoretic approach to collaborative filtering, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.201-212, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312230]
• 3: David P. Anderson , Jeff Cobb , Eric Korpela , Matt Lebofsky , Dan Werthimer, SETI@home: an experiment in public-resource computing, Communications of the ACM, v.45 n.11, p.56-61, November 2002 [doi>10.1145/581571.581573]
• 4: AP. 2002. New shopping technology could breed supermarket class system. San Jose Mercury News (November 10).
• 5: Daniel Billsus , Michael J. Pazzani, Learning Collaborative Information Filters, Proceedings of the Fifteenth International Conference on Machine Learning, p.46-54, July 24-27, 1998
• 6: Anna Bouch , Allan Kuchinsky , Nina Bhatti, Quality is in the eye of the beholder: meeting users' requirements for Internet quality of service, Proceedings of the SIGCHI conference on Human factors in computing systems, p.297-304, April 01-06, 2000, The Hague, The Netherlands [doi>10.1145/332040.332447]
• 7: Breese, J. S., Heckerman, D., and Kadie, C. 1998. Empirical analysis of predictive algorithms for collaborative filtering. In Proceedings of the 14th Conference on Uncertainty in Artificial Intelligence (UAI-98). 43--52.
• 8: John Canny, Collaborative Filtering with Privacy, Proceedings of the 2002 IEEE Symposium on Security and Privacy, p.45, May 12-15, 2002
• 9: John Canny, Collaborative Filtering with Privacy, Proceedings of the 2002 IEEE Symposium on Security and Privacy, p.45, May 12-15, 2002
• 10: John Canny, Collaborative filtering with privacy via factor analysis, Proceedings of the 25th annual international ACM SIGIR conference on Research and development in information retrieval, August 11-15, 2002, Tampere, Finland [doi>10.1145/564376.564419]
• 11: Chavez, A. and Maes, P. 1996. Kasbah: An agent marketplace for buying and selling goods. In the First International Conference on the Practical Application of Intelligent Agents and Multi-Agent Technology (PAAM'96). Practical Application Company, London, UK, 75--90.
• 12: Yuan Chen , Jan Edler , Andrew Goldberg , Allan Gottlieb , Sumeet Sobti , Peter Yianilos, A prototype implementation of archival Intermemory, Proceedings of the fourth ACM conference on Digital libraries, p.28-37, August 11-14, 1999, Berkeley, California, United States [doi>10.1145/313238.313249]
• 13: Ian Clarke , Scott G. Miller , Theodore W. Hong , Oskar Sandberg , Brandon Wiley, Protecting Free Expression Online with Freenet, IEEE Internet Computing, v.6 n.1, p.40-49, January 2002 [doi>10.1109/4236.978368]
• 14: Mark Claypool , Phong Le , Makoto Wased , David Brown, Implicit interest indicators, Proceedings of the 6th international conference on Intelligent user interfaces, p.33-40, January 14-17, 2001, Santa Fe, New Mexico, United States [doi>10.1145/359784.359836]
• 15: Clymer, A. 2003. Troops risk identity theft after burglary. New York Times (January 12).
• 16: Cramer, R., Gennaro, R., and Schoenmakers, B. 1997. A secure and optimally efficient multi-authority election scheme. Lecture Notes in Computer Science 1233, 103--118.
• 17: Frank Dabek , M. Frans Kaashoek , David Karger , Robert Morris , Ion Stoica, Wide-area cooperative storage with CFS, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 18: Devore, J. L. 1995. Probability and Statistics for Engineering and the Sciences, fourth edition Duxbury Press.
• 19: Roger Dingledine , Michael J. Freedman , David Molnar, The free haven project: distributed anonymous storage service, International workshop on Designing privacy enhancing technologies: design issues in anonymity and unobservability, p.67-95, January 2001, Berkeley, California, United States
• 20: Peter Druschel , Antony Rowstron, PAST: A Large-Scale, Persistent Peer-to-Peer Storage Utility, Proceedings of the Eighth Workshop on Hot Topics in Operating Systems, p.75, May 20-22, 2001
• 21: Leonard Newton Foner , Pattie Maes, Political artifacts and personal privacy: the yenta multiagent distributed matchmaking system, 1999
• 22: Foner, L. N. 1996. A multi-agent referral system for matchmaking. Proceedings of the Second International Conference on Multi-Agent System (ICMAS-96).
• 23: Michael J. Freedman , Robert Morris, Tarzan: a peer-to-peer anonymizing network layer, Proceedings of the 9th ACM conference on Computer and communications security, November 18-22, 2002, Washington, DC, USA [doi>10.1145/586110.586137]
• 24: Friedman, E. and Resnick, P. 1999. The social cost of cheap pseudonyms. Journal of Economics and Management Strategy, 10, 2 (August), 173--199.
• 25: Gnutella. Gnutella website http://gnutella.wego.com.
• 26: Jeremy Goecks , Jude Shavlik, Learning users' interests by unobtrusively observing their normal behavior, Proceedings of the 5th international conference on Intelligent user interfaces, p.129-132, January 09-12, 2000, New Orleans, Louisiana, United States [doi>10.1145/325737.325806]
• 27: David Goldschlag , Michael Reed , Paul Syverson, Onion routing, Communications of the ACM, v.42 n.2, p.39-41, Feb. 1999 [doi>10.1145/293411.293443]
• 28: Nathaniel Good , J. Ben Schafer , Joseph A. Konstan , Al Borchers , Badrul Sarwar , Jon Herlocker , John Riedl, Combining collaborative filtering with personal agents for better recommendations, Proceedings of the sixteenth national conference on Artificial intelligence and the eleventh Innovative applications of artificial intelligence conference innovative applications of artificial intelligence, p.439-446, July 18-22, 1999, Orlando, Florida, United States
• 29: Hansell, S. 2002. Privacy policy on web shifts as profits ebb. New York Times (April 11).
• 30: Jonathan L. Herlocker , Joseph A. Konstan , Al Borchers , John Riedl, An algorithmic framework for performing collaborative filtering, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.230-237, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312682]
• 31: Jovanovic, M. A. 2001. Modelling large peer-to-peer networks and a case study of gnutella. M.S. thesis, University of Cincinnati.
• 32: David Karger , Eric Lehman , Tom Leighton , Rina Panigrahy , Matthew Levine , Daniel Lewin, Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the World Wide Web, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.654-663, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258660]
• 33: George Karypis, Evaluation of Item-Based Top-N Recommendation Algorithms, Proceedings of the tenth international conference on Information and knowledge management, October 05-10, 2001, Atlanta, Georgia, USA [doi>10.1145/502585.502627]
• 34: John Kubiatowicz , David Bindel , Yan Chen , Steven Czerwinski , Patrick Eaton , Dennis Geels , Ramakrishna Gummadi , Sean Rhea , Hakim Weatherspoon , Chris Wells , Ben Zhao, OceanStore: an architecture for global-scale persistent storage, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.190-201, November 2000, Cambridge, Massachusetts, United States
• 35: Lyman, P. and Varian, H. 2000. How much information? http://www.sims.berkeley.edu/how-much-info.
• 36: Pattie Maes, Agents that reduce work and information overload, Communications of the ACM, v.37 n.7, p.30-40, July 1994 [doi>10.1145/176789.176792]
• 37: Maes, P. and Kozierok, R. 1993. Learning interface agents. In Proceedings of AAAI-93 and IAAI-93. AAAI Press; Menlo Park, CA, USA.
• 38: Miller, B., Riedl, J., and Konstan, J. 2002. From Usenet to CoWebs: Interacting with Social Information Systems. Springer Verlag, Chapter Experiences in Applying Collaborative Filtering to a Social Information System.
• 39: Minar, N. 1998. Designing an ecology of distributed agents. M.S. thesis, MIT.
• 40: Nelson Minar , Matthew Gray , Oliver Roup , Raffi Krikorian , Pattie Maes, Hive: Distributed Agents for Networking Things, Proceedings of the First International Symposium on Agent Systems and Applications Third International Symposium on Mobile Agents, p.118, October 03-06, 1999
• 41: Bamshad Mobasher , Robert Cooley , Jaideep Srivastava, Automatic personalization based on Web usage mining, Communications of the ACM, v.43 n.8, p.142-151, Aug. 2000 [doi>10.1145/345124.345169]
• 42: Bamshad Mobasher , Honghua Dai , Tao Luo , Miki Nakagawa, Discovery and Evaluation of Aggregate Usage Profiles for Web Personalization, Data Mining and Knowledge Discovery, v.6 n.1, p.61-82, January 2002 [doi>10.1023/A:1013232803866]
• 43: Masahiro Morita , Yoichi Shinoda, Information filtering based on user behavior analysis and best match text retrieval, Proceedings of the 17th annual international ACM SIGIR conference on Research and development in information retrieval, p.272-281, July 03-06, 1994, Dublin, Ireland
• 44: Alexandros Moukas , Giorgos Zacharia, Evolving a multi-agent information filtering solution in Amalthaea, Proceedings of the first international conference on Autonomous agents, p.394-403, February 05-08, 1997, Marina del Rey, California, United States [doi>10.1145/267658.267747]
• 45: Peter G. Neumann, Computer related risks, ACM Press/Addison-Wesley Publishing Co., New York, NY, 1995
• 46: Pedersen, T. 1991. A threshold cryptosystem without a trusted party. In Advances in Cryptology - EUROCRYPT'91 Lecture Notes in Computer Science, D. W. Davies, Ed. Vol. 547. Springer-Verlag, 522--526.
• 47: Sylvia Ratnasamy , Paul Francis , Mark Handley , Richard Karp , Scott Schenker, A scalable content-addressable network, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.161-172, August 2001, San Diego, California, United States
• 48: Paul Resnick , Neophytos Iacovou , Mitesh Suchak , Peter Bergstrom , John Riedl, GroupLens: an open architecture for collaborative filtering of netnews, Proceedings of the 1994 ACM conference on Computer supported cooperative work, p.175-186, October 22-26, 1994, Chapel Hill, North Carolina, United States [doi>10.1145/192844.192905]
• 49: Matei Ripeanu , Adriana Iamnitchi , Ian Foster, Mapping the Gnutella Network, IEEE Internet Computing, v.6 n.1, p.50-57, January 2002 [doi>10.1109/4236.978369]
• 50: Antony I. T. Rowstron , Peter Druschel, Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems, Proceedings of the IFIP/ACM International Conference on Distributed Systems Platforms Heidelberg, p.329-350, November 12-16, 2001
• 51: Antony Rowstron , Peter Druschel, Storage management and caching in PAST, a large-scale, persistent peer-to-peer storage utility, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 52: Badrul M. Sarwar , Joseph A. Konstan , Al Borchers , Jon Herlocker , Brad Miller , John Riedl, Using filtering agents to improve prediction quality in the GroupLens research collaborative filtering system, Proceedings of the 1998 ACM conference on Computer supported cooperative work, p.345-354, November 14-18, 1998, Seattle, Washington, United States [doi>10.1145/289444.289509]
• 53: Sarwar, B., Konstan, J., and Riedl, J. 2001. Internet Commerce and Software Agents: Cases, Technologies, and Opportunities. Idea Group, Chapter Distributed Recommender Systems: New Opportunities for Internet Commerce, Idea Group Publishing, Hershey, PA.
• 54: Badrul Sarwar , George Karypis , Joseph Konstan , John Riedl, Analysis of recommendation algorithms for e-commerce, Proceedings of the 2nd ACM conference on Electronic commerce, p.158-167, October 17-20, 2000, Minneapolis, Minnesota, United States [doi>10.1145/352871.352887]
• 55: Sarwar, B. M., Karypis, G., Konstan, J. A., and Riedl, J. 2000b. Application of dimensionality reduction in recommender system---a case study. In ACM WebKDD 2000 Web Mining for E-Commerce Workshop.
• 56: Badrul Sarwar , George Karypis , Joseph Konstan , John Reidl, Item-based collaborative filtering recommendation algorithms, Proceedings of the 10th international conference on World Wide Web, p.285-295, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372071]
• 57: 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]
• 58: Sheth, B. and Maes, P. 1993. Evolving agents for personalized information filtering. In Proceedings of 9th IEEE Conference on Artificial Intelligence for Applications. IEEE Computer Society Press; Los Alamitos, CA, USA.
• 59: Shirkey, C. 2001. Peer-to-Peer, Harnessing the Power of Disruptive Technologies. O'Reilly and Associates, Chapter Listening to Napster.
• 60: Ion Stoica , Robert Morris , David Karger , M. Frans Kaashoek , Hari Balakrishnan, Chord: A scalable peer-to-peer lookup service for internet applications, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.149-160, August 2001, San Diego, California, United States
• 61: Loren Terveen , Will Hill , Brian Amento , David McDonald , Josh Creter, PHOAKS: a system for sharing recommendations, Communications of the ACM, v.40 n.3, p.59-62, March 1997 [doi>10.1145/245108.245122]
• 62: Ungar, L. and Foster, D. 1998. Clustering methods for collaborative filtering. In Proceedings of the Workshop on Recommendation Systems. AAAI Press, Menlo Park California.
• 63: Marc Waldman , David Mazières, Tangler: a censorship-resistant publishing system based on document entanglements, Proceedings of the 8th ACM conference on Computer and Communications Security, November 05-08, 2001, Philadelphia, PA, USA [doi>10.1145/501983.502002]
• 64: Waldman, M., Rubin, A. D., and Cranor, L. F. 2000. Publius: A robust, tamper-evident, censorship-resistant, web publishing system. In Proceedings of the 9th USENIX Security Symposium. 59--72.
• 65: Whelan, C. 2002. How consumers can strike back if their identity has been stolen. Wall Street Journal (August 21).
• 66: Wingfield, N. and Pereira, J. December, 2002. Amazon uses faux suggestions to promote new clothing store. Wall Street Journal (December 4).

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Information filtering

General Terms:
Algorithms, Measurement, Security

Keywords:
Collaborative Filtering, Peer-to-Peer Networking, Privacy, Recommender Systems