\documentclass[12pt]{article}

\usepackage{amssymb}
\usepackage{amstext}
\usepackage{psfig}

%--------------- Various Style Declarations ----------------------------

\setlength{\textheight}    {225mm}  % about 9in
\setlength{\textwidth}     {158mm}  % about 6.3in

\setlength{\oddsidemargin}   {4mm}
\setlength{\evensidemargin}  {1mm}

\setlength{\topmargin}     {-15mm}
\setlength{\topskip}         {0mm}
\setlength{\footskip}     {0.50in}

\setlength{\parskip}         {8pt}
\setlength{\parindent}       {0pt}

\renewcommand{\baselinestretch}{1.0}  
\bibliographystyle{alpha}

\begin{document}
\section*{15-850: Algorithms for Indexing and Searching}

\paragraph{Instructors:} Blelloch, Lafferty, Miller
\paragraph{Meeting time:} 3:00-5:20pm Wednesdays

\subsection*{Topics}

Here is a rough outline with some readings.   It will be
filled in during the semester.

\begin{description}
\item[Week 1:]
  Introduction to IR
\item[Week 2:]
  Introduction to Web Searching (Henzinger Slides)
\item[Week 3:]
  Latent Semantic Indexing \cite{BDB94,PRTV98}
\item[Week 4:]
  Link-based Search Analysis \cite{K98,BB98,CDRRGK98}
\item[Week 5:]
  Efficient SVD 
\item[Week 6:]
  High-dimensional Nearest Neighbors \cite{IM98,CL97,KOR98}
\item[Week 7:]
  Cluster Analysis \cite{BGMZ97}
\item[Week 8:]
  Leave Open
\item[Week 9:]
  Properties of the Web \cite{SHMM98}
\item[Week 10 :]
  Removing duplicate documents \cite{B98}
\item[Week 11:]
  Web Caching \cite{KL4P97}
\item[Week 12:]
  Erasure Codes 
\end{description}

Our list of references is augmented from the one
provided with the following tutorial:

\begin{list}{}{}
\item
A.\,Broder and M.\,Henzinger (1998). ``Information retrieval on the web:
Tools and algorithmic issues,'' Invited tutorial at Foundations of Computer Science
(FOCS). Slides available at {\tt
http://www.research.digital.com/SRC/\-personal/\-monika/\-focs-talk-m78/\-ppframe.htm}
\end{list}

\vskip-50pt

\renewcommand\refname{}
\begin{thebibliography}{99}

\bibitem{WWW6} Proceedings of the Sixth International World Wide
Web Conference, Santa Clara, California, April 1997.

\bibitem{WWW7} WWW7 Proceedings of the Seventh International World
Wide Web Conference, Brisbane, Australia, April 1998.

\bibitem{AAMVV98}
 P.K.\,Agarwal, L.\,Arge, T.M.\,Murali, K.R.\,Varadarajan, and
J.S.\,Vitter. I/O-efficient algorithms for contour-line extraction and
planar graph blocking (extended abstract). In Proceedings of the Ninth
Annual ACM-SIAM Symposium on Discrete Algorithms, pages 117-126, San
Francisco, California, Jan. 1998.

\bibitem{AMM97}
O.\,Arocena, A.O.\,Mendelzon, and G.A.\,Mihaila. Applications of a
web query language. In Proceedings of the Sixth International World
Wide Web Conference (WWW6), pages 587- 595.

\bibitem{BDB94}
       Michael W. Berry and Susan T. Dumais, and Gavin W. O'Brien.
Using Linear Algebra for Intelligent Information Retrieval.
       Published in SIAM Review 37:4 (1995), pp. 573-595.

\bibitem{BB98}
 K.\,Bharat and A.Z.\,Broder. A technique for measuring the relative
size and overlap of public web search engines. In Proceedings of the
Seventh International World Wide Web Conference (WWW7), pages 379-388.

\bibitem{BBHKV98}
 K.\,Bharat, A.Z.\,Broder, M.\,Henzinger, P.\,Kumar, and
S.\,Venkatasubramanian. The connectivity server: Fast access to linkage
information on the web. In Proceedings of the Seventh International
World Wide Web Conference (WWW7), pages 469-477.

\bibitem{BH98}
 K.\,Bharat and M.\,Henzinger. Improved algorithms for topic
distillation in hyperlinked environments. In Proceedings of the 21st
International ACM SIGIR Conference on Research and Development in
Information Retrieval (SIGIR'98), pages 111-104, 1998.

\bibitem{BDG95} S.\,Brin, J.\,Davis, and H.\,Gar\c{c}ia-Molina. Copy
detection mechanisms for digital documents. In M.J.\,Carey and
D.A.\,Schneider, editors, Proceedings of the 1995 ACM SIGMOD
International Conference on Management of Data, pages 398-409, San
Jose, California, May 1995.

\bibitem{BP98}
 S.\,Brin and L.\,Page. The anatomy of a large-scale hypertextual web
search engine. In Proceedings of the Seventh International World Wide
Web Conference (WWW7), pages 107-117.

\bibitem{B97}
 A.Z.\,Broder. On the resemblance and containment of documents. In
Proceedings of Compression and Complexity of Sequences 1997, pages
21-29. IEEE Computer Society, 1988.

\bibitem{B98} 
A.Z.\,Broder. Filtering near-duplicate documents. In Proceedings
of FUN 98, 1998. To appear.

\bibitem{BCFM97}
 A.Z.\,Broder, M.\,Charikar, A.\,Frieze, and M.\,Mitzenmacher.  Min-wise
independent permutations. In Proceedings of the 30th Annual ACM
Symposium on Theory of Computing (STOC-98), pages 327-336, New York,
May 1998. ACM Press.

\bibitem{BCM98}
 A.Z.\,Broder, M.\,Charikar, and M.\,Mitzenmacher. A deran domization
using min-wise independent permutations. In Proceedings of Random 98,
1998. To appear.


\bibitem{BGMZ97}
 A.Z.\,Broder, S.C.\,Glassman, M.S.\,Manasse, and G.\,Zweig.  Syntactic
clustering of the Web. In Proceedings of the Sixth International World
Wide Web Conference (WWW6), pages 391- 404.

\bibitem{CK97}
 J.\,Carriere and R.\,Kazman. Webquery: Searching and visualizing the
web through connectivity. In Proceedings of the Sixth International
World Wide Web Conference (WWW6), pages 701- 711.

\bibitem{CDGKRRT98}
 S.\,Chakrabarti, B.\,Dom, D.\,Gibson, S.\,Kumar, P.\,Raghavan,
S.\,Rajagopalan, and A.\,Tomkins. Experiments in topic distillation. In
ACM-SIGIR'98 Post-Conference Workshop on Hypertext Information
Retrieval for the Web, 1998.

\bibitem{CDRRGK98}
 S.\,Chakrabarti, B.\,Dom, R.P., S.\,Rajagopalan, D.\,Gibson, and
J.\,Kleinberg. Automatic resource compilation by analyzing hyperlink
structure and associated text. In Proceedings of the Seventh
International World Wide Web Conference (WWW7), pages 65-74.

\bibitem{CGP98}
 J.\,Cho, H.\,Gar\c{c}ia-Molina, and L.\,Page. Efficient crawling through
URL ordering. In Proceedings of the Seventh International World Wide
Web Conference (WWW7), pages 161-172.

\bibitem{CL97}
Edith Cohen and David D. Lewis,
Approximating matrix multiplication for pattern recognition tasks. 
In Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 682-691, 1997. 

\bibitem{CLW97}
 E.G.\,Coffman, Z.\,Liu, and R.R.\,Weber. Optimal robot scheduling for
web search engines. Technical Report 3317, INRIA, Dec. 1997.

\bibitem{DKFVV99}, P. Drineas, Ravi Kannan, Alan Frieze, Santosh
Vempala and V. Vinay Clustering in large graphs and matrices.  To
appear in Proc. of the 10th ACM-SIAM Symposium on Discrete Algorithms,
Baltimore, 1999.

\bibitem{DEW97}
 R.B.\,Doorenbos, O.\,Etzioni, and D.S.\,Weld. A scalable
comparison-shopping agent for the World-Wide Web. In W.L.\,Johnson and
B.\,Hayes-Roth, editors, Proceedings of the 1st International
Conference on Autonomous Agents, pages 39-48, New York, Feb. 1997. ACM
Press.

\bibitem{FSGMU98}
 M.\,Fang, N.\,Shivakumar, H.\,Gar\c{c}ia-Molina, R.\,Motwani, and
J.\,Ullman. Computing iceberg queries efficiently. In Proceedings of
the 1998 International Conference on Very Large Databases (VLDB'98),
Aug. 1998. To appear.

\bibitem{BF92}
 W.B.\,Frakes and R.\,Baeza-Yates. Information Retrieval: Data
Structures and Algorithms. Prentice Hall, 1992.

\bibitem{G72}
 E.\,Garfield. Citation analysis as a tool in journal evaluation.
Science, 178, 1972.

\bibitem{H96}
 N.\,Heintze. Scalable document fingerprinting. In Second USENIX
Workshop on Electronic Commerce, pages 191-200, Oakland, California,
Nov. 1996.

\bibitem{IM98}
 P.\,Indyk and R.\,Motwani. Approximate nearest neighbors: Towards
removing the curse of dimensionality. In Proceedings of the 30th
Annual ACM Symposium on Theory of Computing (STOC-98), pages 604-613,
New York, May 1998. ACM Press.

\bibitem{KL4P97}
D.\,Karger, E.\,Lehman, T.\,Leighton, M.\,Levine, D.\,Lewin,
and R.\,Panigrahy, ``Consistent hashing and random trees: Distributed
cachine protocols for relieving hot spots on the World Wide Web,'' 
In Proceedings of the 31st Annual ACM
Symposium on Theory of Computing (STOC-97).

\bibitem{K63}
 M.M.\,Kessler. Bibliographic coupling between scientific papers.
American Documentation, 14, 1963.

\bibitem{K98}
 J.\,Kleinberg. Authoritative sources in a hyperlinked environment. In
Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete
Algorithms, pages 668-677, January 1998.

\bibitem{KOR98}
E. Kushilevitz, R. Ostrovsky and Y. Rabani.
Efficient search for approximate nearest neighbor in high 
                       dimensional spaces.
In 
Proceedings of the Thirtieth Annual ACM Symposium on Theory 
                       of Computing, 1998. pages 614-23.

\bibitem{LG98b} 
S.\,Lawrence and C.L.\,Giles. Inquirus, the NECI meta search
engine. In Proceedings of the Seventh International World Wide Web
Conference (WWW7), pages 95-105.

\bibitem{LG98a} 
S.\,Lawrence and C.L.\,Giles. Searching the World Wide Web.
Science, 280(5360):98, 1998.

\bibitem{MJSUZB97}
 Y.\,Maarek, M.\,Jacovi, M.\,Shtalhaim, S.\,Ur, D.\,Zernik, and I.Z. Ben
Shaul. Webcutter: A system for dynamic and tailorable site mapping. In
Proceedings of the Sixth International World Wide Web Conference
(WWW6), pages 713-722.

\bibitem{M94}
 U.\,Manber. Finding similar files in a large file system. In Pro
ceedings of the Winter 1994 USENIX Conference, pages 1-10, Berkeley,
CA, USA, 1994.

\bibitem{M97}
 M.\,Marchiori. The quest for correct information on the web: Hyper
search engines. In Proceedings of the Sixth International World Wide
Web Conference (WWW6), pages 265-274.


\bibitem{M96}
 G.A.\,Mihaila. WebSQL - an SQL-like query language for the world wide
Web. Master's thesis, University of Toronto, 1996.

\bibitem{ML97}
 J.\,Mogul and P.\,Leach. RFC 2227: Simple hit-metering and
usage-limiting for HTTP, Oct. 1997. Status: Proposed standard. URL:
ftp://\-ftp.math.utah.edu/\-pub/rfc/\-rfc2227.txt.

\bibitem{NP98b} 
M.\,Naor and B.\,Pinkas. Oblivious transfer and polynomial
evaluation. Manuscript, 1998.

\bibitem{NP98a} 
M.\,Naor and B.\,Pinkas. Secure accounting and auditing on the
Web. In Proceedings of the Seventh International World Wide Web
Conference (WWW7), pages 541-550.

\bibitem{NGV96}
 M.H.\,Nodine, M.T.\,Goodrich, and J.S.\,Vitter. Blocking for external
graph searching. Algorithmica, 16(2):181-214, Aug. 1996.

\bibitem{PBMW98}
 L.\,Page, S.\,Brin, R.\,Motwani, and T.\,Winograd. The PageRank citation
ranking: Bringing order to the Web. Work in progress. URL:
http://\-google.stanford.edu/\-*backrub/\-pageranksub.ps.

\bibitem{PRTV98}
Christos Papadimitriou, Prabhakar Raghavan, Hisao Tamaki and Santosh Vempala.
Latent Semantic Indexing: A Probabilistic Analysis.
Proc. 17th ACM Symposium on the Principles of Database Systems, Seattle, 1998. 

\bibitem{PPR96}
 P.\,Pirolli, J.\,Pitkow, and R.\,Rao. Silk from a sow's ear: Extracting
usable structures from the web. In Proceedings of the Conference on
Human Factors in Computing Systems (CHI 96), pages 118-125, April
1996.

\bibitem{P97}
 J.\,Pitkow. In search of: reliable usage data on the WWW.\,In
Proceedings of the Sixth International World Wide Web Conference
(WWW6), pages 452-463.

\bibitem{SLE97}
 J.\,Shakes, M.\,Langheinrich, and O.\,Etzioni. Dynamic reference
sifting: A case study in the homepage domain. In Proceedings of the
Sixth International World Wide Web Conference (WWW6), pages
189-199.

\bibitem{SG95}
 N.\,Shivakumar and H.\,Gar\c{c}ia-Molina. SCAM: A copy detection mechanism
for digital documents. In DL '95 Proceedings, 1995.

\bibitem{SG98}
 N.\,Shivakumar and H.\,Gar\c{c}ia-Molina. Finding near-replicas of
documents on the web. In Proceedings of Workshop on Web Databases
(WebDB'98), March 1998.

\bibitem{SHMM98}
 C.\,Silverstein, M.\,Henzinger, J.\,Marais, and M.\,Moricz. Analysis of a
very large AltaVista query log. Technical Report 1998-014, Compaq
Systems Research Center, Palo Alto, California, 1998.

\bibitem{S73}
 H.\,Small. Co-citation in the scientific literature: A new measure of
the relationship between two documents. J.\,Amer. Soc. Info. Sci., 24,
1973.

\bibitem{SW97}
 K.\,Sparck-Jones and P.\,Willet, editors. Readings in Information
Retrieval. Morgan Kaufmann, 1997.

\bibitem{S97}
 E.\,Spertus. Parasite: Mining structural information on the web.  In
Proceedings of the Sixth International World Wide Web Conference
(WWW6), pages 587-595.

\bibitem{TS98}
 A.\,Tombros and M.\,Sanderson. Advantages of query biased summaries in
information retrieval. In Proceedings of the 21st International ACM
SIGIR Conference on Research and Development in Information Retrieval
(SIGIR'98), pages 2-10, 1998.

\end{thebibliography}

\end{document}

 
