Abstract
In this talk we review and survey some recent work and work in progress on data mining and web search. We discuss Latent Semantic Analysis and give conditions under which it is robust. We also consider the problem of collaborative filtering and show how spectral techniques can give a rigorous and robust justification for doing so. We consider the problems of web search and show how both Google and Klienberg’s algorithm are robust under a model of web generation, and how this model can be reasonably extended. We then give an algorithm that provably gives the correct result in this extended model. The results surveyed are joint work with Azar, Karlin, McSherry and Saia [2], and Achlioptas, Karlin and McSherry [1].
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
D. Achlioptas, A. Fiat, A. R. Karlin, and F. McSherry. Web Search vis Hub Synthesis. Manuscript, 2001.
Y. Azar, A. Fiat, A. R. Karlin, F. McSherry, and J. Saia. Spectral analysis of data. In STOC 2001, 2001.
Sergey Brin and Lawrence Page. The anatomy of a large-scale hypertextual Web search engine. Computer Networks and ISDN Systems, 30(1–7):107–117, 1998.
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.
S. Kumar, P. Raghavan, S. Rajagopalan, and A. Tomkins. Recommendation Systems: A Probabilistic Analysis. In Foundations of Computer Science, pp. 664–673, 1998.
Jon M. Kleinberg. Authoritative sources in a hyperlinked environment. Journal of the ACM, 46(5):604–632, 1999.
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.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fiat, A. (2001). Some Recent Results on Data Mining and Search. In: Sgall, J., Pultr, A., Kolman, P. (eds) Mathematical Foundations of Computer Science 2001. MFCS 2001. Lecture Notes in Computer Science, vol 2136. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44683-4_4
Download citation
DOI: https://doi.org/10.1007/3-540-44683-4_4
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-42496-3
Online ISBN: 978-3-540-44683-5
eBook Packages: Springer Book Archive