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: h7e58d2667cd52591
Venue: VLDB
Year: 1996
Pagerank: 6.1545256e-05
Overall Rank: 5,350 | 64.14%
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,717	On Effective Multi-Dimensional Indexing for Strings	2000	SIGMOD	8.0808382e-05
3,131	Size Separation Spatial Join	1997	SIGMOD	7.6016052e-05
6,068	Spatial Join Selectivity Using Power Laws	2000	SIGMOD	5.8805774e-05
6,631	Two-dimensional Substring Indexing	2001	PODS	5.7114931e-05
7,236	Indexing Methods for Moving Object Databases: Games and Other Applications	2013	SIGMOD	5.5629185e-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.0019892478
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0011386412
44	The R+-Tree: A Dynamic Multi-Dimensional Index for Objects	1987	VLDB	0.00045231517
94	Efficient and Effective Clustering Methods for Spatial Data Mining	1994	VLDB	0.00034470298
146	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.000289618
338	Hilbert R-tree: An Improved R-tree Using Fractals	1994	VLDB	0.0002058961
363	Linear Clustering of Objects with Multiple Attributes	1990	SIGMOD	0.00019931086

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,131	Size Separation Spatial Join	1997	SIGMOD
2	999	Spatial Hash-Joins	1996	SIGMOD
3	4,954	Integration of Spatial Join Algorithms for Processing Multiple Inputs	1999	SIGMOD
4	1,554	Incremental Distance Join Algorithms for Spatial Databases	1998	SIGMOD
5	6,552	Adaptive Multi-Stage Distance Join Processing	2000	SIGMOD
6	7,924	Processing and Optimization of Multiway Spatial Joins Using R-trees	1999	PODS
7	10,085	Adaptive Indexing of Objects with Spatial Extent	2023	VLDB
8	2,597	Spatial Joins Using R-trees: Breadth-First Traversal with Global Optimizations	1997	VLDB
9	146	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD
10	2,368	Spatial Joins Using Seeded Trees	1994	SIGMOD