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.00019980483
Overall Rank: 363 | 97.57%
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.00051292389
103	Selectivity Estimation Without the Attribute Value Independence Assumption	1997	VLDB	0.00033884854
207	Generalized Search Trees for Database Systems (Extended Abstract)	1995	VLDB	0.00024976482
336	Hilbert R-tree: An Improved R-tree Using Fractals	1994	VLDB	0.00020652147
410	Semantic Data Caching and Replacement	1996	VLDB	0.00018796567
488	FastMap: A Fast Algorithm for Indexing, Data-Mining and Visualization of Traditional and Multimedia Datasets	1995	SIGMOD	0.00017451091
527	Multi-Step Processing of Spatial Joins	1994	SIGMOD	0.00016874202
744	Client-Server Paradise	1994	VLDB	0.00014305129
839	Fast Nearest Neighbor Search in Medical Image Databases	1996	VLDB	0.0001354488
1,529	On the Analysis of Indexing Schemes	1997	PODS	0.00010346523
2,390	Parallel R-trees	1992	SIGMOD	8.5335833e-05
5,334	Filter Trees for Managing Spatial Data Over a Range of Size Granularities	1996	VLDB	6.1749174e-05
6,007	Clustering Techniques for Minimizing External Path Length	1996	VLDB	5.912767e-05
7,472	Parallel Algorithms for High-dimensional Proximity Joins	1997	VLDB	5.5163696e-05
7,761	Snakes and Sandwiches: Optimal Clustering Strategies for a Data Warehouse	1999	SIGMOD	5.4565021e-05
7,796	K-Anonymization as Spatial Indexing: Toward Scalable and Incremental Anonymization	2007	VLDB	5.4500222e-05
8,186	Towards Designing and Learning Piecewise Space-Filling Curves	2023	VLDB	5.3800965e-05
9,213	Fast and Adaptive Indexing of Multi-Dimensional Observational Data	2016	VLDB	5.2056173e-05
9,533	R-Tree Based Indexing of Now-Relative Bitemporal Data	1998	VLDB	5.1643871e-05
11,122	Optimizing Block Skipping for High-Dimensional Data with Learned Adaptive Curve	2025	SIGMOD	4.9769913e-05
11,607	Partition, Don’t Sort! Compression Boosters for Cloud Data Ingestion Pipelines	2024	VLDB	4.9769913e-05
13,053	Efficiently Processing Queries on Interval-and-Value Tuples in Relational Databases	2005	VLDB	4.9769913e-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.0019923528
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0011402175
101	Spatial Query Processing in an Object-Oriented Database System	1986	SIGMOD	0.00033923053
265	A Class of Data Structures for Associative Searching	1984	PODS	0.00022748432
1,035	Redundancy in Spatial Databases	1989	SIGMOD	0.00012388306
1,228	Fractals for Secondary Key Retrieval	1989	PODS	0.00011427053
2,794	Multiattribute Hashing Using Gray Codes.	1986	SIGMOD	8.0003415e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,112	A Dynamic Clustering Technique For Physical Database Design	1980	SIGMOD
2	9,948	Compressed Spatial Hierarchical Bitmap (cSHB) Indexes for Efficiently Processing Spatial Range Query Workloads	2015	VLDB
3	9,213	Fast and Adaptive Indexing of Multi-Dimensional Observational Data	2016	VLDB
4	5,708	A Mapping Function for the Directory of a Multidimensional Extendible Hashing	1984	VLDB
5	3,886	Fast Parallel Similarity Search in Multimedia Databases	1997	SIGMOD
6	5,907	On the Optimality of Clustering Properties of Space Filling Curves	2012	PODS
7	5,334	Filter Trees for Managing Spatial Data Over a Range of Size Granularities	1996	VLDB
8	7,566	Cache-oblivious High-performance Similarity Join	2019	SIGMOD
9	1,228	Fractals for Secondary Key Retrieval	1989	PODS
10	855	Storage Mappings For Multidimensional Linear Dynamic Hashing	1983	PODS