Linear Clustering of Objects with Multiple Attributes

Summary: Hilbert space-filling curve-based linearization of multi-attribute space; analysis and simulation show it beats prior interleaving, Gray, and Peano mappings on average. Uses include one-dimensional indexing for multi-dimensional objects (Orenstein), and storage layouts to minimize disk I/O; cross-domain relevance. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h80f128624bef46b4
Venue: SIGMOD
Year: 1990
Pagerank: 0.00019976696
Overall Rank: 364 | 97.56%
DOI: 10.1145/93597.98742

Incoming Non-self Citations Over Time

Authors

1. H V Jagadish (AT&T)

BibTeX Citation

@inproceedings{jagadish_sigmod90,
        title = {{Linear Clustering of Objects with Multiple Attributes}},
        author = {Jagadish, H V},
        series = {{SIGMOD} '90},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/93597.98742},
        url = {https://dl.acm.org/doi/10.1145/93597.98742},
        year = {1990}
}

Incoming Citations (Sorted by Pagerank)

Showing 22 of 22 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
28	Nearest Neighbor Queries	1995	SIGMOD	0.00051312804
103	Selectivity Estimation Without the Attribute Value Independence Assumption	1997	VLDB	0.00033894985
206	Generalized Search Trees for Database Systems (Extended Abstract)	1995	VLDB	0.00024986675
335	Hilbert R-tree: An Improved R-tree Using Fractals	1994	VLDB	0.00020660268
416	Semantic Data Caching and Replacement	1996	VLDB	0.00018658244
488	FastMap: A Fast Algorithm for Indexing, Data-Mining and Visualization of Traditional and Multimedia Datasets	1995	SIGMOD	0.00017457851
527	Multi-Step Processing of Spatial Joins	1994	SIGMOD	0.00016880616
743	Client-Server Paradise	1994	VLDB	0.00014311524
837	Fast Nearest Neighbor Search in Medical Image Databases	1996	VLDB	0.00013551047
1,527	On the Analysis of Indexing Schemes	1997	PODS	0.00010350889
2,388	Parallel R-trees	1992	SIGMOD	8.5375939e-05
5,328	Filter Trees for Managing Spatial Data Over a Range of Size Granularities	1996	VLDB	6.1778312e-05
6,007	Clustering Techniques for Minimizing External Path Length	1996	VLDB	5.9155532e-05
7,468	Parallel Algorithms for High-dimensional Proximity Joins	1997	VLDB	5.5189807e-05
7,755	Snakes and Sandwiches: Optimal Clustering Strategies for a Data Warehouse	1999	SIGMOD	5.4590631e-05
7,788	K-Anonymization as Spatial Indexing: Toward Scalable and Incremental Anonymization	2007	VLDB	5.4526034e-05
8,179	Towards Designing and Learning Piecewise Space-Filling Curves	2023	VLDB	5.3826446e-05
9,204	Fast and Adaptive Indexing of Multi-Dimensional Observational Data	2016	VLDB	5.2080128e-05
9,522	R-Tree Based Indexing of Now-Relative Bitemporal Data	1998	VLDB	5.1668323e-05
11,113	Optimizing Block Skipping for High-Dimensional Data with Learned Adaptive Curve	2025	SIGMOD	4.9793485e-05
11,601	Partition, Don’t Sort! Compression Boosters for Cloud Data Ingestion Pipelines	2024	VLDB	4.9793485e-05
13,047	Efficiently Processing Queries on Interval-and-Value Tuples in Relational Databases	2005	VLDB	4.9793485e-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
101	Spatial Query Processing in an Object-Oriented Database System	1986	SIGMOD	0.00033937215
264	A Class of Data Structures for Associative Searching	1984	PODS	0.00022757762
1,035	Redundancy in Spatial Databases	1989	SIGMOD	0.00012393393
1,226	Fractals for Secondary Key Retrieval	1989	PODS	0.00011431306
2,794	Multiattribute Hashing Using Gray Codes.	1986	SIGMOD	8.0033879e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	101	Spatial Query Processing in an Object-Oriented Database System	1986	SIGMOD
2	9,941	Compressed Spatial Hierarchical Bitmap (cSHB) Indexes for Efficiently Processing Spatial Range Query Workloads	2015	VLDB
3	9,204	Fast and Adaptive Indexing of Multi-Dimensional Observational Data	2016	VLDB
4	5,707	A Mapping Function for the Directory of a Multidimensional Extendible Hashing	1984	VLDB
5	3,887	Fast Parallel Similarity Search in Multimedia Databases	1997	SIGMOD
6	5,904	On the Optimality of Clustering Properties of Space Filling Curves	2012	PODS
7	5,328	Filter Trees for Managing Spatial Data Over a Range of Size Granularities	1996	VLDB
8	7,560	Cache-oblivious High-performance Similarity Join	2019	SIGMOD
9	1,226	Fractals for Secondary Key Retrieval	1989	PODS
10	855	Storage Mappings For Multidimensional Linear Dynamic Hashing	1983	PODS