On the Optimality of Clustering Properties of Space Filling Curves

Summary: Characterizes the clustering number (average count of contiguous curve segments per query region) for a broad class of space‑filling curves and proves the first non‑trivial lower bounds on clustering. Resolves Jagadish's 1997 open problem on SFC optimality. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1578
Venue: PODS
Year: 2012
Pagerank: 6.088071e-05
Overall Rank: 5,787 | 60.30%
DOI: 10.1145/2213556.2213587

Incoming Non-self Citations Over Time

Authors

1. Pan Xu (Iowa State University)
2. Srikanta Tirthapura (Iowa State University)

BibTeX Citation

@inproceedings{xu_pods12,
        address = {New York, NY, USA},
        series = {{PODS} '12},
        title = {{On the Optimality of Clustering Properties of Space Filling Curves}},
        url = {https://dl.acm.org/doi/10.1145/2213556.2213587},
        doi = {10.1145/2213556.2213587},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Xu, Pan and Tirthapura, Srikanta},
        year = {2012}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,335	QUILTS: Multidimensional Partitioning Framework Based on Query-Aware and Skew-Tolerant Space-Filling Curves	2017	SIGMOD	5.9090498e-05
7,151	Theoretically Optimal and Empirically Efficient R-trees with Strong Parallelizability	2018	VLDB	5.6873519e-05
8,003	Towards Designing and Learning Piecewise Space-Filling Curves	2023	VLDB	5.5084586e-05
11,342	Efficient Cost Modeling of Space-filling Curves	2024	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
253	A Class of Data Structures for Associative Searching	1984	PODS	0.00023200431
2,742	Multiattribute Hashing Using Gray Codes.	1986	SIGMOD	8.1827223e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	11,141	Optimal (Multiway) Spatial Joins	2024	PODS
2	11,632	Data-Independent Space Partitionings for Summaries	2021	PODS
3	6,753	Optimal Indexing Using Near-Minimal Space [Extended Abstract]	2003	PODS
4	4,755	Rectangle-Efficient Aggregation in Spatial Data Streams	2012	PODS
5	10,182	The Space-Time Complexity of Sum-Product Queries	2026	PODS
6	6,335	QUILTS: Multidimensional Partitioning Framework Based on Query-Aware and Skew-Tolerant Space-Filling Curves	2017	SIGMOD
7	12,835	From Discrepancy to Declustering: Near-optimal multidimensional declustering strategies for range queries [Extended Abstract]	2002	PODS
8	354	Linear Clustering of Objects with Multiple Attributes	1990	SIGMOD
9	11,342	Efficient Cost Modeling of Space-filling Curves	2024	VLDB
10	6,089	Window Query-Optimal Clustering of Spatial Objects	1995	PODS