Spectral analysis of data

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Spectral analysis of data

Full text

Pdf (260 KB)

Source

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

Hersonissos, Greece

Pages: 619 - 626

Year of Publication: 2001

ISBN:1-58113-349-9

Authors

Yossi Azar	Dept. of Computer Science, Tel Aviv University, Tel-Aviv 69978, Israel
Amos Fiat	Dept. of Computer Science, Tel Aviv University, Tel-Aviv 69978, Israel
Anna Karlin	Dept. of Computer Science, University of Washington at Seattle
Frank McSherry	Dept. of Computer Science, University of Washington at Seattle
Jared Saia	Dept. of Computer Science, University of Washington at Seattle

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 19, Downloads (12 Months): 101, Citation Count: 51

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/380752.380859 What is a DOI?

ABSTRACT

Experimental evidence suggests that spectral techniques are valuable for a wide range of applications. A partial list of such applications include (i) semantic analysis of documents used to cluster documents into areas of interest, (ii) collaborative filtering --- the reconstruction of missing data items, and (iii) determining the relative importance of documents based on citation/link structure. Intuitive arguments can explain some of the phenomena that has been observed but little theoretical study has been done. In this paper we present a model for framing data mining tasks and a unified approach to solving the resulting data mining problems using spectral analysis. These results give strong justification to the use of spectral techniques for latent semantic indexing, collaborative filtering, and web site ranking.

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	Rakesh Agrawal , Tomasz Imieliński , Arun Swami, Mining association rules between sets of items in large databases, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.207-216, May 25-28, 1993, Washington, D.C., United States
	2	Chumki Basu , Haym Hirsh , William Cohen, Recommendation as classification: using social and content-based information in recommendation, Proceedings of the fifteenth national/tenth conference on Artificial intelligence/Innovative applications of artificial intelligence, p.714-720, July 1998, Madison, Wisconsin, United States
	3	Michael W. Berry , Zlatko Drmac , Elizabeth R. Jessup, Matrices, Vector Spaces, and Information Retrieval, SIAM Review, v.41 n.2, p.335-362, June 1999 [doi>10.1137/S0036144598347035]
	4	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]
	5	R.B. Boppana. Eigenvalues and Graph Bisection: An Average-Case Analysis. In Proc. of 28th Annual FOCS, pp. 280-285, 1987.
	6	Z. Furedi and J. Komlos. The eigenvalues of random symmetric matrices. Combinatorica 1:3, pp. 233-241, 1981.
	7	Gene H. Golub , Charles F. Van Loan, Matrix computations (3rd ed.), Johns Hopkins University Press, Baltimore, MD, 1996
	8	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]
	9	Jester shadow.ieor.berkeley.edu/humor
	10	R. Kannan , S. Vempala , A. Veta, On clusterings-good, bad and spectral, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.367, November 12-14, 2000
	11	Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.668-677, January 25-27, 1998, San Francisco, California, United States
	12	Flip Korn , Alexandros Labrinidis , Yannis Kotidis , Christos Faloutsos, Ratio Rules: A New Paradigm for Fast, Quantifiable Data Mining, Proceedings of the 24rd International Conference on Very Large Data Bases, p.582-593, August 24-27, 1998
	13	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
	14	C. Papadimitriou, P. Raghavan, H. Tamaki, and S. Vempala. Latent Semantic Indexing: A Probabilistic Analysis. In Proceedings of ACM Symposium on Principles of Database Systems, 1997.
	15	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]
	16	Sleeper www.pmetrics.com/sleeper
	17	G.W. Stewart. Matrix Algorithms, Volume 1: Basic Decompositions. Society for Industrial and Applied Mathematics, 1998.

CITED BY 51

	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
	Petros Drineas , Iordanis Kerenidis , Prabhakar Raghavan, Competitive recommendation systems, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	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
	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
	Rie Kubota Ando , Lillian Lee, Iterative residual rescaling, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.154-162, September 2001, New Orleans, Louisiana, United States
	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
	Mark Sandler, On the use of linear programming for unsupervised text classification, Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA
	P. Drineas , A. Frieze , R. Kannan , S. Vempala , V. Vinay, Clustering Large Graphs via the Singular Value Decomposition, Machine Learning, v.56 n.1-3, p.9-33
	Ravi Kannan , Santosh Vempala , Adrian Vetta, On clusterings: Good, bad and spectral, Journal of the ACM (JACM), v.51 n.3, p.497-515, May 2004
	Rodrigo B. Almeida , Virgilio A. F. Almeida, A community-aware search engine, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA
	David Kempe , Frank McSherry, A decentralized algorithm for spectral analysis, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	Santosh Vempala , Grant Wang, A spectral algorithm for learning mixture models, Journal of Computer and System Sciences, v.68 n.4, p.841-860, June 2004
	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
	Christian Borgs , Jennifer Chayes , Mohammad Mahdian , Amin Saberi, Exploring the community structure of newsgroups, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA
	Panayiotis Tsaparas, Using non-linear dynamical systems for web searching and ranking, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France
	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
	Gianluigi Greco , Sergio Greco , Ester Zumpano, Collaborative filtering supporting web site navigation, AI Communications, v.17 n.3, p.155-166, July 2004
	Ioannis N. Kouris , Christos H. Makris , Athanasios K. Tsakalidis, Using information retrieval techniques for supporting data mining, Data & Knowledge Engineering, v.52 n.3, p.353-383, March 2005
	Hui Han , Hongyuan Zha , C. Lee Giles, Name disambiguation in author citations using a K-way spectral clustering method, Proceedings of the 5th ACM/IEEE-CS joint conference on Digital libraries, June 07-11, 2005, Denver, CO, USA
	Holger Bast , Debapriyo Majumdar, Why spectral retrieval works, Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, August 15-19, 2005, Salvador, Brazil
	Jacob G. Martin, Subproblem optimization by gene correlation with singular value decomposition, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA
	Allan Borodin , Gareth O. Roberts , Jeffrey S. Rosenthal , Panayiotis Tsaparas, Link analysis ranking: algorithms, theory, and experiments, ACM Transactions on Internet Technology (TOIT), v.5 n.1, p.231-297, February 2005
	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
	Chris H. Q. Ding, A probabilistic model for Latent Semantic Indexing: Research Articles, Journal of the American Society for Information Science and Technology, v.56 n.6, p.597-608, April 2005
	Ali Shokoufandeh , Spiros Mancoridis , Trip Denton , Matthew Maycock, Spectral and meta-heuristic algorithms for software clustering, Journal of Systems and Software, v.77 n.3, p.213-223, September 2005
	Jasson D. M. Rennie , Nathan Srebro, Fast maximum margin matrix factorization for collaborative prediction, Proceedings of the 22nd international conference on Machine learning, p.713-719, August 07-11, 2005, Bonn, Germany
	Alejandro López-Ortiz, Algorithmic foundations of the internet, ACM SIGACT News, v.36 n.2, June 2005
	Edith Cohen , Amos Fiat , Haim Kaplan, A case for associative peer to peer overlays, ACM SIGCOMM Computer Communication Review, v.33 n.1, p.95-100, January 2003
	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
	Gianluigi Greco , Sergio Greco , Ester Zumpano, Collaborative Filtering Supporting Web Site Navigation, AI Communications, v.17 n.3, p.155-166, August 2004
	Sheng Zhang , Yi Ouyang , James Ford , Fillia Makedon, Analysis of a low-dimensional linear model under recommendation attacks, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA
	Dimitris Achlioptas , Frank Mcsherry, Fast computation of low-rank matrix approximations, Journal of the ACM (JACM), v.54 n.2, p.9-es, April 2007
	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
	Robert Jenssen , Deniz Erdogmus , Kenneth E. Hild, II , Jose C. Principe , Torbjørn Eltoft, Information cut for clustering using a gradient descent approach, Pattern Recognition, v.40 n.3, p.796-806, March, 2007
	David Kempe , Frank McSherry, A decentralized algorithm for spectral analysis, Journal of Computer and System Sciences, v.74 n.1, p.70-83, February, 2008
	M. G. Vozalis , K. G. Margaritis, Using SVD and demographic data for the enhancement of generalized Collaborative Filtering, Information Sciences: an International Journal, v.177 n.15, p.3017-3037, August, 2007
	Petros Drineas , Michael W. Mahoney, On the Nyström Method for Approximating a Gram Matrix for Improved Kernel-Based Learning, The Journal of Machine Learning Research, 6, p.2153-2175, 12/1/2005
	Mark Rudelson , Roman Vershynin, Sampling from large matrices: An approach through geometric functional analysis, Journal of the ACM (JACM), v.54 n.4, p.21-es, July 2007
	R. Lempel , S. Moran, Rank-Stability and Rank-Similarity of Link-Based Web Ranking Algorithms in Authority-Connected Graphs, Information Retrieval, v.8 n.2, p.245-264, April 2005
	Juan C. Valle-Lisboa , Eduardo Mizraji, The uncovering of hidden structures by Latent Semantic Analysis, Information Sciences: an International Journal, v.177 n.19, p.4122-4147, October, 2007
	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
	Bhaskar Mehta , Thomas Hofmann , Wolfgang Nejdl, Robust collaborative filtering, Proceedings of the 2007 ACM conference on Recommender systems, October 19-20, 2007, Minneapolis, MN, USA
	Baruch Awerbuch , Robert Kleinberg, Competitive collaborative learning, Journal of Computer and System Sciences, v.74 n.8, p.1271-1288, December, 2008
	Wenyuan Li , Wee-Keong Ng , Ying Liu , Kok-Leong Ong, Enhancing the Effectiveness of Clustering with Spectra Analysis, IEEE Transactions on Knowledge and Data Engineering, v.19 n.7, p.887-902, July 2007
	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
	Fan Zhang , Edwin R. Hancock, Graph spectral image smoothing using the heat kernel, Pattern Recognition, v.41 n.11, p.3328-3342, November, 2008
	Manolis G. Vozalis , Konstantinos G. Margaritis, Identifying the effects of SVD and demographic data use on generalized collaborative filtering, International Journal of Computer Mathematics, v.85 n.12, p.1741-1763, December 2008
	Umut Ozertem , Deniz Erdogmus , Robert Jenssen, Mean shift spectral clustering, Pattern Recognition, v.41 n.6, p.1924-1938, June, 2008
	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
	Rong Pan , Martin Scholz, Mind the gaps: weighting the unknown in large-scale one-class collaborative filtering, Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, June 28-July 01, 2009, Paris, France