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: h1191e35028f08707
Venue: SIGMOD
Year: 1991
Pagerank: 9.7534412e-05
Overall Rank: 1,735 | 88.38%
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
122	Schism: a Workload-Driven Approach to Database Replication and Partitioning	2010	VLDB	0.00030701814
2,042	On the Performance of Object Clustering Techniques	1992	SIGMOD	9.1275895e-05
2,964	Dual-Buffering Strategies in Object Bases	1994	VLDB	7.7923396e-05
4,406	Partition Selection Policies in Object Database Garbage Collection	1994	SIGMOD	6.6024515e-05
5,118	A Decomposition-Based Simulated Annealing Technique for Data Clustering	1994	PODS	6.2548449e-05
6,020	Clustering Techniques for Minimizing External Path Length	1996	VLDB	5.8934229e-05
7,337	Self-Adaptive, On-Line Reclustering of Complex Object Data	1994	SIGMOD	5.53385e-05
8,137	On-line Reorganization in Object Databases	2000	SIGMOD	5.3739121e-05
8,958	Vertical Data Migration in Large Near-Line Document Archives Based on Markov-Chain Predictions	1997	VLDB	5.2361195e-05
13,423	The Term Retrieval Abstract Machine	1992	SIGMOD	4.9605343e-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,286	The Performance and Utility of the Cactis Implementation Algorithms	1990	VLDB	8.6833735e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,019	Effective Clustering Of Complex Objects In Object-Oriented Databases	1991	SIGMOD
2	14,166	Programmable Clustering	2006	PODS
3	3,644	Efficient and Effective Algorithms for Clustering Uncertain Graphs	2019	VLDB
4	6,231	Window Query-Optimal Clustering of Spatial Objects	1995	PODS
5	7,762	Clustering Objects on a Spatial Network	2004	SIGMOD
6	12,802	An Access Cost-Aware Approach for Object Retrieval over Multiple Sources	2010	VLDB
7	9,480	A Conceptual Model for Dynamic Clustering in Object Databases	1992	VLDB
8	6,489	Clustering Uncertain Graphs	2018	VLDB
9	7,337	Self-Adaptive, On-Line Reclustering of Complex Object Data	1994	SIGMOD
10	2,042	On the Performance of Object Clustering Techniques	1992	SIGMOD