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.1778312e-05
Overall Rank: 5,328 | 64.18%
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,706	On Effective Multi-Dimensional Indexing for Strings	2000	SIGMOD	8.1111109e-05
3,120	Size Separation Spatial Join	1997	SIGMOD	7.6300049e-05
6,052	Spatial Join Selectivity Using Power Laws	2000	SIGMOD	5.9028248e-05
6,616	Two-dimensional Substring Indexing	2001	PODS	5.7330951e-05
7,215	Indexing Methods for Moving Object Databases: Games and Other Applications	2013	SIGMOD	5.5837763e-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.001992968
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0011405675
44	The R+-Tree: A Dynamic Multi-Dimensional Index for Objects	1987	VLDB	0.00045337853
94	Efficient and Effective Clustering Methods for Spatial Data Mining	1994	VLDB	0.00034579889
146	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.00029061754
335	Hilbert R-tree: An Improved R-tree Using Fractals	1994	VLDB	0.00020660268
364	Linear Clustering of Objects with Multiple Attributes	1990	SIGMOD	0.00019976696

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,120	Size Separation Spatial Join	1997	SIGMOD
2	994	Spatial Hash-Joins	1996	SIGMOD
3	4,927	Integration of Spatial Join Algorithms for Processing Multiple Inputs	1999	SIGMOD
4	1,552	Incremental Distance Join Algorithms for Spatial Databases	1998	SIGMOD
5	6,540	Adaptive Multi-Stage Distance Join Processing	2000	SIGMOD
6	7,904	Processing and Optimization of Multiway Spatial Joins Using R-trees	1999	PODS
7	10,048	Adaptive Indexing of Objects with Spatial Extent	2023	VLDB
8	2,588	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,358	Spatial Joins Using Seeded Trees	1994	SIGMOD