Clustering Techniques for Minimizing External Path Length

Summary: Presents optimal node-to-page clustering for tree access structures, minimizing worst-case or weighted average external path length while supporting dynamic updates. Characterizes DAG variants as NP-complete and supplies heuristics, validated on quad-tree image workloads and applicable to object clustering. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 8547
Venue: VLDB
Year: 1996
Pagerank: 6.0498293e-05
Overall Rank: 5,888 | 59.61%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. A. A. Diwan (Indian Institute of Technology Mumbai)
2. Sanjeeva Rane (Indian Institute of Technology Mumbai)
3. S. Seshadri (Indian Institute of Technology Mumbai)
4. S. Sudarshan (Indian Institute of Technology Mumbai)

BibTeX Citation

@article{diwan_vldb96,
        title = {{Clustering Techniques for Minimizing External Path Length}},
        author = {Diwan, A. A. and Rane, Sanjeeva and Seshadri, S. and Sudarshan, S.},
        journal = {PVLDB},
        series = {{VLDB} '96},
        pages = {342},
        year = {1996}
}

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
430	A Fast Index for Semistructured Data	2001	VLDB	0.00018600166
10,479	P-MOSS: Scheduling Main-Memory Indexes Over NUMA Servers Using Next Token Prediction	2026	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 13 of 13 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
42	The R+-Tree: A Dynamic Multi-Dimensional Index for Objects	1987	VLDB	0.00046170812
354	Linear Clustering of Objects with Multiple Attributes	1990	SIGMOD	0.00020355578
837	Exploiting Inheritance and Structure Semantics for Effective Clustering and Buffering in an Object-Oriented DBMS	1989	SIGMOD	0.0001370733
1,019	Redundancy in Spatial Databases	1989	SIGMOD	0.00012622386
1,709	A Stochastic Approach for Clustering in Object Bases	1991	SIGMOD	9.9585965e-05
1,992	On the Performance of Object Clustering Techniques	1992	SIGMOD	9.3427219e-05
2,135	Path Caching: A Technique for Optimal External Searching (Extended Abstract)	1994	PODS	9.1133971e-05
2,249	A Comparison of Spatial Query Processing Techniques for Native and Parameter Spaces	1990	SIGMOD	8.8700017e-05
5,884	Effective Clustering Of Complex Objects In Object-Oriented Databases	1991	SIGMOD	6.0518046e-05
7,581	Blocking for External Graph Searching (Extended Abstract)	1993	PODS	5.5923369e-05
9,267	A Conceptual Model for Dynamic Clustering in Object Databases	1992	VLDB	5.2952969e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	4,075	Distributing a Search Tree Among a Growing Number of Processors	1994	SIGMOD
2	7,864	Cost-Sensitive Reordering of Navigational Primitives	2005	SIGMOD
3	1,813	Main-Memory Index Structures with Fixed-Size Partial Keys	2001	SIGMOD
4	3,857	Efficient Processing of Distance Queries in Large Graphs: A Vertex Cover Approach	2012	SIGMOD
5	5,061	Comparing Hierarchical Data in External Memory	1999	VLDB
6	7	Implementation Techniques For Main Memory Database Systems	1984	SIGMOD
7	2,082	A Dynamic Clustering Technique For Physical Database Design	1980	SIGMOD
8	9,635	Memory-Efficient Search Trees for Database Management Systems	2021	SIGMOD
9	6,089	Window Query-Optimal Clustering of Spatial Objects	1995	PODS
10	2,135	Path Caching: A Technique for Optimal External Searching (Extended Abstract)	1994	PODS