CSE 262 Class Readings (Spring 2006)

Many of the readings are on-line, but some may be handed out in class. Be sure to read the assigned papers before lecture, and be prepared to discuss them in class.

Note: your grade will be based in part on 1-page write-ups you must submit before lecture. For 12 of the 20 lectures, you must submit a 1 page write-up for each paper assigned that lecture. Submit these writeups via the web board, using the numbered lecture conference set aside for the purpose. You may provide a URL as your submission. Some writeups will be posted publicly, and will be made available after class.

In an effort to comply with prevailing copyright restrictions, most links to ACM and IEEE papers refer to the ACM or IEEE digital library, respectively. Both digital libraries are subscription services. However, UCSD has a campus-wide subscription in each case and you should be able to obtain the papers from any campus machine. If you are a member of ACM and/or IEEE, then you should also be able to access the on-line papers as using your member web account(s).

If you have a UCSD network account, then you may use the UCSD Web proxy which will enable you to access restricted content from non-UCSD Internet service providers.

Please email me if you have difficulty accessing any of the papers.

Current lecture readings

Tuesday, 4/4/2006: Introduction

  • Lessons Learned from Managing a Petabyte, by Jacek Becla and Daniel L. Wang. Second Biennial Conference on Innovative Data Systems Research (CIDR 2005), pp. 70-83, Jan. 2005.

  • Where the Rubber Meets the Sky: Bridging the Gap between Databases and Science, by Jim Gray and Alexander S. Szalay, IEEE Data Engineering Bulletin, 27(4):3-11, Dec. 2004.

    • Thursday, 4/6/2006: High Performance I/O

  • GPFS: A Shared-Disk File System for Large Computing Clusters by Frank Schmuck and Roger Haskin, Proc. First Conf. File and Storage Technologies (FAST), pp. 231-244. USENIX, 2002.
  • A Cost-Effective, High-Bandwidth Storage Architecture, by G. A. Gibson et al., Proc. 8th Conf on Architectural Support for Programming Languages and Operating Systems (ASPLOS), pp. 92-103, 1998.
    (Glance at Network Attached Storage Architecture, by Garth A. Gibson and Rodney Van Meter, CACM 43(11), Nov. 2000.)
  • Frangipani: A Scalable Distributed File System, by Chandramohan A. Thekkath, Timothy Mann, and Edward K. Lee, Proc. 16th ACM Symp. on Operating Systems Principles, September 1997, Saint Malo, France, pp. 224-237.
  • Other parallel file systems:
  • PVFS2
  • Lustre

    • Tuesday, 4/11/2006: Sorting

  • GPUTeraSort: High Performance Graphics Coprocessor Sorting for Large Database Management by Naga K. Govindaraju, Jim Gray, Ritesh Kumar, and Dinesh Manocha, Proc. ACM SIGMOD Conference, Chicago, IL, June, 2006.
  • Parallel Sorting on a Shared-Nothing Architecture using Probabilistic Splitting, by David J. DeWitt, Jeffrey F. Naughton, and Donovan A. Schneider. Proc. 1st Int'l Conf. on Parallel and Disttributed Information Sys., pp 280-291, 1993.
  • High-performance sorting on networks of workstations, Andrea C. Arpaci-Dusseau et al. SIGMOD '97: Proc. 1997 ACM SIGMOD Int'l. Conf. on Management of Data, pp. 243--254, 1997.
  • Browse the Sort Benchmark Page

    • Thursday, 4/13/2006: Search trees

  • Selections from R-Trees: Theory and Applications by Y. Manolopoulos et al. Springer 2006: pp. 3-22, 175-189.
  • The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles. Proc. 1990 ACM SIGMOD International Conf. on Management of Data, pp. 322-331, 1990. New link
  • Indexing for Dynamic Abstract Regions by Joxan Jaffar, Roland H.C. Yap, Kenny Q. Zhu.
  • For reference:
  • R-Trees: A Dynamic Index Structure for Spatial Searching by A. Guttman, Proc. 1984 ACM SIGMOD International Conf. on Management of Data, pp. 47-57. Gutman's original R-tree paper.
  • The rtree portal. A shrine to the R-tree and its variants.
  • Multidimensional access methods, ACM Computing Surveys, 30(2):170-231, June 1998. A lengthly survey with many variants.

    • Tuesday, 4/18/2006

  • A case for redundant arrays of inexpensive disks (RAID) by David A. Patterson, Garth Gibson, Randy H. Katz, Proc 1988 ACM SIGMOD Int'l Conf on Management of Data, pp. 109-116 (1988).

  • The Google File System, by Sanjay Ghemawat, Howard Gobioff, and Shun-Tak Leung. 19th ACM Symp on Operating Systems Principles, 2003.

    • Thursday, 4/20/2006 (SBB)

  • Spatial Databases A Tour, by Shashi Shekhar and Sanjay Chawla. Prentice Hall Pub. (2003): pp. 1-21.
  • The SDSS SkyServer - Public Access to the Sloan Digital Sky Server Data, by A. S. Szalay et al. Proc. ACM SIGMOD '02, pp. 570-581.

    • Tuedsay, 4/25/2006 (SBB)

  • Spatial Databases A Tour, pp 22-44.
  • Database System Concepts, 5th Edition, by Silberschatz, Korth, and Sudarshan, McGraw Hill (2006): pp. 37-45.

    • Thursday, 4/27/2006 (SBB)

  • Silberschatz, pp 44-64, 73-74.
  • Shekhar, pp 52-59, 79-82

    • Tuesday, 5/2/2006 (SBB)

  • Shekhar, pp 59-79
  • "There Goes the Neighborhood: Relational Algebra for Spatial Data Search," J. Gray et al. Microsoft Research Technical Report MSR-TR-2004-32 (2004). (Re-read Where the Rubber Meets the Sky: Bridging the Gap between Databases and Science, by Jim Gray and Alexander S. Szalay, to refresh your memory)

    • Thursday, 5/4/2006

  • Polaris: A System for Query, Analysis, and Visualization of Multidimensional Relational Databases, Chris Stolte, Diane Tang and Pat Hanrahan, IEEE Trans. on Visualization and Computer Graphics, 8(1), January-March 2002 .
  • Algebraic Manipulation of Scientific Datasets, Bill Howe and David Maier, 30th Intl. Conf. on Very Large Data Bases (VLDB 2004).

    • Tuesday, 5/9/2006 (Daniel Tracy)

  • Partition based spatial-merge join, Proc. 1996 ACM SIGMOD international Conference on Management of Data, pp. 259-270.
  • Multi-Step Processing of Spatial Joins, by Thomas Brinkhoff et al. SIGMOD 1994, pp 197-208.

    • Thursday, 5/11/2006

        Double session, 3:30 to 6:30 PM. Room: EBU3B 3109
  • Task Scheduling Strategies for Workflow-based Applications in Grids, by J Blythe, S Jain, E Deelman, Y Gil, K Vahi, A Mandal,K Kennedy, Proc. of CCGrid '05, Cardiff, UK, May 2005.
  • A Hypergraph Partitioning Based Approach for Scheduling of Tasks with Batch-shared I/O, by G. Khanna, N. Vydyanathan, T. Kurc, U. Catalyurek, P. Wyckoff, J. Saltz and P. Sadayappan. Proc. of CCGrid '05, Cardiff, UK, May 2005.
  • Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Totals by J. Gray et al., Data Mining and Knowledge Discovery, 1(1):29-53 (March 1997)     Pre-print     From Springer site (somewhat longer)

    • Tuesdsay, 5/16/2006

  • Volume tracking, D. Silver and X. Wang, Proc. 7th Conf. on Visualization, San Francisco, 1996.
  • Lecture notes on the FFT (a superset of what will be covered in class)
  • The Discrete Fourier Transform, from Online version of The Scientist and Engineer's Guide to Digital Signal Processing, by Steve W. Smith. (For reference only. This is rather detailed)

    • Thursday, 5/18/2006: Wavelets (Chris Schroeder)

  • Engineer's Ultimate Guide to Wavelet Analysis, by Robi Polikar. All the sections are concatenated. For the original source, see Robi Polikar's web site
  • More Wavelet resources
  • Chris Schroeder's Lecture materials on Wavelets

    • Tuesdsay, 5/30/2006

  • WaveCluster: A MultiResolution Clustering Approach for Very Large Spatial Databases, by G. Sheikholeslami, S. Chatterjee, and A. Zhang. Proc 24th VLDB, pp. 428-439 (1998).
  • Real Time Feature Extraction for Analysis of Turbulent Flows, I. Marusic et al., in Data Mining for Scientific and Engineering Applications, R.L. Grossman et al. eds., Kluwer Academic Publishing (2001), Chapter 13, pp. 223-238. (Background reading for next lecture)
  • To explore further ....
  • A Survey on Wavelet Applications in Data Mining by T. Li, Q. Li, S. Zhu, and M. Ogihara. SIGKDD, 4(2):49-68 (December 2002). There are plenty of references in this survey.
  • Some interesting tutorials on large databases and data mining. Daniel Keim's web page

    • Thursday, 6/1/2006
  • "Data Mining for Turbulent Flows," by E.-H. Han, G. Karypis, and V. Kumar, in Data Mining for Scientific and Engineering Applications, R.L. Grossman et al. eds., Kluwer Academic Publishing (2001), Chapter 14, pp. 239-256 (Be sure to read last lecture's Marusic paper first).
  • A short introduction to boosting, by Y. Freund and R. Schapire, J. Japan. Soc. for Artif. Intel., 14(5):771-780 (1999).
  • To explore further
  • A Tutorial on Support Vector Machines for Pattern Recognition Christopher J. C. Burges. Data Mining and Knowledge Discovery, 2(2):121-167 (1998).
  • The alternating decision tree learning algorithm, Yoav Freund and Llew Mason. Proc. 16th International Conf. on Machine Learning, pp. 124-133 (1999).
  • Building Classification Models: ID3 and C4.5 (Tutorial on ID3)

    • Tuesday, 6/6/2006: Project Presentations (I)

  • We meet in EBU3B 3109, 3pm to 6pm.
  • Schedule

    • Thursday, 6/8/2006: Project Presentations (II)

  • Usual class time and place.
  • Schedule

    • Maintained by . Last modified: Wed May 24 22:02:04 PDT 2006