Multiscale Histograms: Summarizing Topological Relations in Large Spatial Datasets

Summary: Multiscale histograms of topological relations (contains, contained, overlap, disjoint) using Euler histograms for exact, constant-time aligned-window summaries. A 19/12-approx NP-hard storage-minimization, a k-histogram scheme for high accuracy, and constant-time approximate queries; experiments show large accuracy gains with scalable storage. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 9217
Venue: VLDB
Year: 2003
Pagerank: 5.2143223e-05
Overall Rank: 9,825 | 32.60%
DOI: 10.1016/B978-012722442-8/50077-X

Incoming Non-self Citations Over Time

Authors

1. Xuemin Lin (University of New South Wales)
2. Qing Liu (University of New South Wales)
3. Yidong Yuan (University of New South Wales)
4. Xiaofang Zhou (University of Queensland)

BibTeX Citation

@article{lin_vldb03,
        title = {{Multiscale Histograms: Summarizing Topological Relations in Large Spatial Datasets}},
        author = {Lin, Xuemin and Liu, Qing and Yuan, Yidong and Zhou, Xiaofang},
        journal = {PVLDB},
        series = {{VLDB} '03},
        doi = {10.1016/B978-012722442-8/50077-X},
        url = {https://doi.org/10.1016/B978-012722442-8/50077-X},
        year = {2003}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,170	QuickSel: Quick Selectivity Learning with Mixture Models	2020	SIGMOD	0.00011827259

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
76	Practical Selectivity Estimation through Adaptive Sampling	1990	SIGMOD	0.00037054261
168	Wavelet-Based Histograms for Selectivity Estimation	1998	SIGMOD	0.00027541029
842	How to Summarize the Universe: Dynamic Maintenance of Quantiles	2002	VLDB	0.00013671191
1,002	Designing And Mining Multi-Terabyte Astronomy Archives: The Sloan Digital Sky Survey	2000	SIGMOD	0.00012706131
1,100	Range Queries in OLAP Data Cubes	1997	SIGMOD	0.00012169143
1,274	Querying and Mining Data Streams: You Only Get One Look	2002	SIGMOD	0.00011377527
2,127	Selectivity Estimation in Spatial Databases	1999	SIGMOD	9.127762e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,089	Window Query-Optimal Clustering of Spatial Objects	1995	PODS
2	3,741	Spatial Online Sampling and Aggregation	2016	VLDB
3	4,755	Rectangle-Efficient Aggregation in Spatial Data Streams	2012	PODS
4	4,889	Fast Algorithms For Hierarchical Range Histogram Construction	2002	PODS
5	9,209	Optimality and Scalability in Lattice Histogram Construction	2009	VLDB
6	5,421	Fast and Near–Optimal Algorithms for Approximating Distributions by Histograms	2015	PODS
7	11,632	Data-Independent Space Partitionings for Summaries	2021	PODS
8	723	Dynamic Multidimensional Histograms	2002	SIGMOD
9	9,642	Hierarchically Organized Skew-Tolerant Histograms for Geographic Data Objects	2010	SIGMOD
10	850	Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes	2000	SIGMOD