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: 2559
Venue: SIGMOD
Year: 1990
Pagerank: 0.00020355578
Overall Rank: 354 | 97.58%
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.00052102434
101	Selectivity Estimation Without the Attribute Value Independence Assumption	1997	VLDB	0.00034376651
202	Generalized Search Trees for Database Systems (Extended Abstract)	1995	VLDB	0.00025454884
329	Hilbert R-tree: An Improved R-tree Using Fractals	1994	VLDB	0.00021068647
409	Semantic Data Caching and Replacement	1996	VLDB	0.00018985783
483	FastMap: A Fast Algorithm for Indexing, Data-Mining and Visualization of Traditional and Multimedia Datasets	1995	SIGMOD	0.00017756569
522	Multi-Step Processing of Spatial Joins	1994	SIGMOD	0.00017133516
726	Client-Server Paradise	1994	VLDB	0.0001460632
815	Fast Nearest Neighbor Search in Medical Image Databases	1996	VLDB	0.00013835761
1,512	On the Analysis of Indexing Schemes	1997	PODS	0.00010536001
2,341	Parallel R-trees	1992	SIGMOD	8.7233426e-05
5,202	Filter Trees for Managing Spatial Data Over a Range of Size Granularities	1996	VLDB	6.3194496e-05
5,888	Clustering Techniques for Minimizing External Path Length	1996	VLDB	6.0498293e-05
7,326	Parallel Algorithms for High-dimensional Proximity Joins	1997	VLDB	5.6435709e-05
7,612	Snakes and Sandwiches: Optimal Clustering Strategies for a Data Warehouse	1999	SIGMOD	5.5834218e-05
7,632	K-Anonymization as Spatial Indexing: Toward Scalable and Incremental Anonymization	2007	VLDB	5.5777517e-05
8,003	Towards Designing and Learning Piecewise Space-Filling Curves	2023	VLDB	5.5084586e-05
9,034	Fast and Adaptive Indexing of Multi-Dimensional Observational Data	2016	VLDB	5.3274671e-05
9,343	R-Tree Based Indexing of Now-Relative Bitemporal Data	1998	VLDB	5.2854091e-05
10,672	Optimizing Block Skipping for High-Dimensional Data with Learned Adaptive Curve	2025	SIGMOD	5.093636e-05
11,274	Partition, Don’t Sort! Compression Boosters for Cloud Data Ingestion Pipelines	2024	VLDB	5.093636e-05
12,757	Efficiently Processing Queries on Interval-and-Value Tuples in Relational Databases	2005	VLDB	5.093636e-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.0020210012
4	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.001157935
96	Spatial Query Processing in an Object-Oriented Database System	1986	SIGMOD	0.00034590762
253	A Class of Data Structures for Associative Searching	1984	PODS	0.00023200431
1,019	Redundancy in Spatial Databases	1989	SIGMOD	0.00012622386
1,202	Fractals for Secondary Key Retrieval	1989	PODS	0.00011672157
2,742	Multiattribute Hashing Using Gray Codes.	1986	SIGMOD	8.1827223e-05

Semantically Similar Papers

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