CS 591 Seminar in Databases - Fall 2000
Seminar Outline (Tentative):
-
Sept 11
-
Introduction to indexing: B-tree and Linear Hashing
-
Spatial Indexing:
A. Guttman. R-Trees: A Dynamic Index Structure For Spatial Searching.
In Proc. SIGMOD 84. [PDF]
T. Sellis, N. Roussopoulos and C. Faloutsos. The R+-Tree: A Dynamic
Index for Multi-Dimensional Objects. In Proc. VLDB 87. [PS]
N. Beckmann, H.-P. Kriegel, R. Schneider, and B. Seeger. The R*-tree:
An Efficient and Robust Access Method For Points and Rectangles. In
Proc. SIGMOD 90. [PS]
-
Sept 18
-
Spatial Indexing:
I. Kamel and C. Faloutsos. Hilbert R-tree: an Improved R-tree Using
Fractals. In Proc. VLDB 94. [PS]
J. Nievergelt, H. Hinterberger, K. Sevcik. The Grid File: An Adaptable,
Symmetric Multikey File Structure. In ACM TODS 9(1): 38-71 (1984). [PDF]
D. Lomet, and B. Salzberg. The hB-tree: A Multiattribute Indexing Method
with Good Guaranteed Performance. In ACM TODS TODS 15(4): 625-658
(1990). [PDF]
Optional supplemental paper:
G. Evangelidis, D. Lomet, and B. Salzberg. The hB^Pi-tree: A Modified
hB-tree Supporting Concurrency, Recovery and Node Consolidation. In Proc.
VLDB 95. [PS]
-
Sept 25
-
Spatial joins:
T. Brinkhoff, H.-P. Kriegel, B. Seeger. Efficient Processing of Spatial
Joins Using R-Trees. In Proc. SIGMOD 93. [PDF]
M. Lo, C. V. Ravishankar.The Design and Implementation of Seeded Trees:
An Efficient Method for Spatial Joins. In IEEE TKDE 10(1): 136-152 (1998).
[PS]
N. Mamoulis, D. Papadias. Integration of Spatial Join Algorithms for
Processing Multiple Inputs. In Proc. SIGMOD 1999. [PDF]
-
Oct 2
-
Analysis of spatial index methods:
A. Belussi, C. Faloutsos. Estimating the Selectivity of Spatial Queries
Using the `Correlation' Fractal Dimension. In Proc. VLDB 1995. [PS]
B.-U. Pagel, H.-W. Six, H. Toben, P. Widmayer. Towards an Analysis
of Range Query Performance in Spatial Data Structures. In Proc. PODS 1993.
[PS]
Y. Theodoridis, T. Sellis. A Model for the Prediction of R-tree Performance.
In Proc. PODS 1996. [PS]
-
Oct 10
-
Temporal indexing:
V. Tsotras, N. Kangerlaris. The Snapshot Index: An I/O-optimal access
method for timeslice queries. In IS 20(3): 237-260 (1995). [PS]
G. Kollios, V. Tsotras. On Temporal Hashing. UCR Technical Report.
UCR-CS-98-01. [PS]
Optional supplemental paper:
S. Ramaswamy. Efficient Indexing for Constraint and Temporal Databases.
In Proc. ICDT 1997. [PS]
-
Oct 16
-
Temporal indexing:
D. Lomet, B. Salzberg. Access Methods for Multiversion Data.
In Proc. SIGMOD Conference 1989. [PDF]
B. Becker, S. Gschwind, T. Ohler, B. Seeger, Peter Widmayer. An Asymptotically
Optimal Multiversion B-Tree. In VLDB Journal 5(4): 264-275 (1996)
[PS]
Optional supplemental papers:
D. Lomet, B. Salzberg. The Performance of a Multiversion Access Method.
In Proc. SIGMOD 1990. [PDF]
-
Oct 23
-
Spatio-temporal Indexing:
J. Tayeb, Ö. Ulusoy, O. Wolfson. A Quadtree-Based Dynamic Attribute
Indexing Method. In The Computer Journal 41(3): 185-200 (1998). [PS]
G. Kollios, D. Gunopulos, V. Tsotras. On Indexing Mobile Objects.
In Proc. PODS 1999. [PS]
-
Oct 30
-
Spatio-temporal Indexing:
S. Saltenis, C. Jensen, S. Leutenegger, M. Lopez. Indexing the Positions
of Continuously Moving Objects. In Proc. SIGMOD 2000. [PS]
G. Kollios, D. Gunopulos, V.J. Tsotras, A. Delis, M. Hadjieleftheriou.
Indexing Animated Objects Using Spatiotemporal Access Methods. UCR
Technical Report. [PS]
Optional Paper:
M. Nascimento, J.R. Silva. Towards Historical R-trees. In Proc. ACM
SAC 1998. [PS]
-
Nov 6
-
Indexing:
D. Pfoser, C. Jensen, Y. Theodoridis. Novel Approaches in Query Processing
for Moving Objects. In Proc. VLDB 2000. [PDF]
A. Gionis, P. Indyk, R. Motwani. Similarity Search in High Dimensions
via Hashing. In Proc. VLDB 1999. [PS]
Optional Paper:
O. Günther, V. Oria, P. Picouet, J.-M. Saglio, M. Scholl. Benchmarking
Spatial Joins À La Carte. In Proc. SSDBM 1998. [PS]
-
Nov 13
-
High dimensional indexing:
K.-I. Lin, H. Jagadish, C. Faloutsos. The TV-Tree: An Index Structure
for High-Dimensional Data. In Proc. VLDB Journal 3(4): 517-542 (1994).
[PS]
S. Berchtold, D. Keim, H.-P. Kriegel. The X-tree : An Index Structure
for High-Dimensional Data. In Proc. VLDB 1996. [PS]
-
Nov 20
-
High dimensional indexing:
S. Berchtold, C. Böhm, H.-P. Kriegel. The Pyramid-Tree: Breaking
the Curse of Dimensionality. In Proc. SIGMOD Conference 1998. [PS]
R. Weber, H.-J. Schek, S. Blott. A Quantitative Analysis and Performance
Study for Similarity-Search Methods in High-Dimensional Spaces. In
Proc. VLDB 1998. [PS]
K. Chakrabarti, S. Mehrotra. Local Dimensionality Reduction: A New
Approach to Indexing High Dimensional Spaces. In Proc. VLDB 2000. [PS]
-
Nov 27
-
Web/XML Indexing:
R. Goldman, J. Widom. DataGuides: Enabling Query Formulation and Optimization
in Semistructured Databases. In Proc. VLDB 1997. [PS]
K. Chakrabarti, S. Mehrotra. The Hybrid Tree: An Index Structure for
High Dimensional Feature Spaces. In Proc. ICDE 1999. [PS]
T. Milo, D. Suciu. Index Structures for Path Expressions. In Proc.
ICDT 1999. [PS]
-
Dec 4
-
Theory of Indexability:
J. Hellerstein, E. Koutsoupias, C. Papadimitriou. On the Analysis of
Indexing Schemes. In Proc. PODS 1997. [PS]
E. Koutsoupias, D. S. Taylor. Tight Bounds for 2-Dimensional Indexing
Schemes. In Proc. PODS 1998. [PS]
V. Samoladas, D. Miranker. A Lower Bound Theorem for Indexing Schemes
and Its Application to Multidimensional Range Queries. In Proc. PODS 1998.
[PS]
-
Dec 11
-
Final project in-class presentations