Filter Trees for Managing Spatial Data Over a Range of Size Granularities

Summary: Introduces Filter Trees, a hierarchical spatial file organization that stratifies entities by size and orders each level along a Hilbert curve. Bulk-I/O-aware range-query and spatial-join algorithms substantially outperform competing methods, especially for full joins. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 8519
Venue: VLDB
Year: 1996
Pagerank: 6.3194496e-05
Overall Rank: 5,202 | 64.32%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Kenneth C. Sevcik (University of Toronto)
2. Nikos Koudas (University of Toronto)

BibTeX Citation

@article{sevcik_vldb96,
        title = {{Filter Trees for Managing Spatial Data Over a Range of Size Granularities}},
        author = {Sevcik, Kenneth C. and Koudas, Nikos},
        journal = {PVLDB},
        series = {{VLDB} '96},
        year = {1996}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,648	On Effective Multi-Dimensional Indexing for Strings	2000	SIGMOD	8.2957097e-05
3,066	Size Separation Spatial Join	1997	SIGMOD	7.7941163e-05
5,932	Spatial Join Selectivity Using Power Laws	2000	SIGMOD	6.0369275e-05
6,491	Two-dimensional Substring Indexing	2001	PODS	5.8641664e-05
7,070	Indexing Methods for Moving Object Databases: Games and Other Applications	2013	SIGMOD	5.7116663e-05

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
2	R-Trees: A Dynamic Index Structure For Spatial Searching	1984	SIGMOD	0.0020210012
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.001157935
42	The R+-Tree: A Dynamic Multi-Dimensional Index for Objects	1987	VLDB	0.00046170812
88	Efficient and Effective Clustering Methods for Spatial Data Mining	1994	VLDB	0.00035240327
145	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.00029548428
329	Hilbert R-tree: An Improved R-tree Using Fractals	1994	VLDB	0.00021068647
354	Linear Clustering of Objects with Multiple Attributes	1990	SIGMOD	0.00020355578

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,066	Size Separation Spatial Join	1997	SIGMOD
2	994	Spatial Hash-Joins	1996	SIGMOD
3	4,815	Integration of Spatial Join Algorithms for Processing Multiple Inputs	1999	SIGMOD
4	1,525	Incremental Distance Join Algorithms for Spatial Databases	1998	SIGMOD
5	6,426	Adaptive Multi-Stage Distance Join Processing	2000	SIGMOD
6	7,744	Processing and Optimization of Multiway Spatial Joins Using R-trees	1999	PODS
7	9,887	Adaptive Indexing of Objects with Spatial Extent	2023	VLDB
8	2,548	Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations	1997	VLDB
9	145	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD
10	2,310	Spatial Joins Using Seeded Trees	1994	SIGMOD