A Stochastic Approach for Clustering in Object Bases

Summary: Optimal object clustering under probabilistic access patterns is rigorously formulated for object bases. In a second model, clustering is NP-complete and reduces to graph partitioning; a Kernighan-style heuristic is proposed with experiments against baselines. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 2571
Venue: SIGMOD
Year: 1991
Pagerank: 9.9585965e-05
Overall Rank: 1,709 | 88.28%
DOI: 10.1145/115790.115792

Incoming Non-self Citations Over Time

Authors

1. Manolis M. Tsangaris (University of Wisconsin)
2. Jeffrey F. Naughton (University of Wisconsin)

BibTeX Citation

@inproceedings{tsangaris_sigmod91,
        title = {{A Stochastic Approach for Clustering in Object Bases}},
        author = {Tsangaris, Manolis M. and Naughton, Jeffrey F.},
        series = {{SIGMOD} '91},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/115790.115792},
        url = {https://dl.acm.org/doi/10.1145/115790.115792},
        year = {1991}
}

Incoming Citations (Sorted by Pagerank)

Showing 10 of 10 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
126	Schism: a Workload-Driven Approach to Database Replication and Partitioning	2010	VLDB	0.00030779127
1,992	On the Performance of Object Clustering Techniques	1992	SIGMOD	9.3427219e-05
2,902	Dual-Buffering Strategies in Object Bases	1994	VLDB	7.9769977e-05
4,299	Partition Selection Policies in Object Database Garbage Collection	1994	SIGMOD	6.7749142e-05
5,007	A Decomposition-Based Simulated Annealing Technique for Data Clustering	1994	PODS	6.4032846e-05
5,888	Clustering Techniques for Minimizing External Path Length	1996	VLDB	6.0498293e-05
7,174	Self-Adaptive, On-Line Reclustering of Complex Object Data	1994	SIGMOD	5.682335e-05
7,944	On-line Reorganization in Object Databases	2000	SIGMOD	5.5181056e-05
8,768	Vertical Data Migration in Large Near-Line Document Archives Based on Markov-Chain Predictions	1997	VLDB	5.3766157e-05
13,086	The Term Retrieval Abstract Machine	1992	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 1 of 1 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,229	The Performance and Utility of the Cactis Implementation Algorithms	1990	VLDB	8.9030801e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,884	Effective Clustering Of Complex Objects In Object-Oriented Databases	1991	SIGMOD
2	3,559	Efficient and Effective Algorithms for Clustering Uncertain Graphs	2019	VLDB
3	13,810	Programmable Clustering	2006	PODS
4	6,089	Window Query-Optimal Clustering of Spatial Objects	1995	PODS
5	7,602	Clustering Objects on a Spatial Network	2004	SIGMOD
6	12,462	An Access Cost-Aware Approach for Object Retrieval over Multiple Sources	2010	VLDB
7	9,267	A Conceptual Model for Dynamic Clustering in Object Databases	1992	VLDB
8	6,345	Clustering Uncertain Graphs	2018	VLDB
9	7,174	Self-Adaptive, On-Line Reclustering of Complex Object Data	1994	SIGMOD
10	1,992	On the Performance of Object Clustering Techniques	1992	SIGMOD