Clustering Techniques for Minimizing External Path Length

Summary: Clustering main-memory access structures to yield short, fat disk mappings minimizing EPL. Trees achieve optimal worst-case EPL clustering with dynamic updates; extended to weighted EPL, NP-completeness for DAGs and height mappings, heuristics and validation on quadtrees. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 8356
Venue: VLDB
Year: 1996
Pagerank: 5.6365164e-05
Overall Rank: 5,196 | 63.86%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 2 of 2 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
415	A Fast Index for Semistructured Data	2001	VLDB	0.00023814619
10,190	P-MOSS: Scheduling Main-Memory Indexes Over NUMA Servers Using Next Token Prediction	2026	SIGMOD	4.1945683e-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.0032169493
6	The R*-tree: An Efficient and Robust Access Method for Points and Rectangles	1990	SIGMOD	0.0016162015
24	The R+-Tree: A Dynamic Index For Multi-Dimensional Objects	1987	VLDB	0.00083378538
290	Linear Clustering of Objects with Multiple Attributes	1990	SIGMOD	0.00028919734
439	Exploiting Inheritance and Structure Semantics for Effective Clustering and Buffering in an Object-Oriented DBMS	1989	SIGMOD	0.00023190547
1,034	Redundancy in Spatial Databases	1989	SIGMOD	0.00014534274
1,658	A Stochastic Approach for Clustering in Object Bases	1991	SIGMOD	0.00010980786
1,893	On the Performance of Object Clustering Techniques	1992	SIGMOD	0.00010184132
2,013	Path Caching: A Technique for Optimal External Searching (Extended Abstract)	1994	PODS	9.7928688e-05
2,472	A Comparison of Spatial Query Processing Techniques for Native and Parameter Spaces	1990	SIGMOD	8.7237893e-05
5,807	Effective Clustering Of Complex Objects In Object-Oriented Databases	1991	SIGMOD	5.3189404e-05
7,442	Blocking for External Graph Searching (Extended Abstract)	1993	PODS	4.7300735e-05
9,000	A Conceptual Model for Dynamic Clustering in Object Databases	1992	VLDB	4.410916e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
3,804	Distributing a Search Tree Among a Growing Number of Processors	1994	SIGMOD	6.7525564e-05
7,848	Cost-Sensitive Reordering of Navigational Primitives	2005	SIGMOD	4.6362551e-05
1,809	Main-Memory Index Structures with Fixed-Size Partial Keys	2001	SIGMOD	0.00010483957
4,067	Efficient Processing of Distance Queries in Large Graphs: A Vertex Cover Approach	2012	SIGMOD	6.4795399e-05
4,941	Comparing Hierarchical Data in External Memory	1999	VLDB	5.8179899e-05
9	Implementation Techniques For Main Memory Database Systems	1984	SIGMOD	0.0014279444
1,709	A Dynamic Clustering Technique For Physical Database Design	1980	SIGMOD	0.00010811082
9,498	Memory-Efficient Search Trees for Database Management Systems	2021	SIGMOD	4.3341665e-05
6,076	Window Query-Optimal Clustering of Spatial Objects	1995	PODS	5.223696e-05
2,013	Path Caching: A Technique for Optimal External Searching (Extended Abstract)	1994	PODS	9.7928688e-05