A File Structure Supporting Traversal Recursion

Summary: Introduces a simple file structure for traversal recursion on large acyclic graphs, sorting nodes topologically and storing them in a B-tree. Traversal is a single scan; supports efficient insert, delete, and modify of nodes and edges. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 2507
Venue: SIGMOD
Year: 1989
Pagerank: 5.8296302e-05
Overall Rank: 6,594 | 54.77%
DOI: 10.1145/67544.66949

Incoming Non-self Citations Over Time

Authors

1. P.-A. Larson (University of Waterloo)
2. V. Deshpande (University of Waterloo)

BibTeX Citation

@inproceedings{larson_sigmod89,
        title = {{A File Structure Supporting Traversal Recursion}},
        author = {Larson, P.-A. and Deshpande, V.},
        series = {{SIGMOD} '89},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/67544.66949},
        url = {https://dl.acm.org/doi/10.1145/67544.66949},
        year = {1989}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,341	Distributed Transitive Closure Computations: The Disconnection Set Approach	1990	VLDB	6.2602701e-05
12,867	A Data Warehousing Architecture for Enabling Service Provisioning Process	2001	VLDB	5.093636e-05
13,065	Implementation and performance evaluation of a parallel transitive closure algorithm on PRISMA/DB	1993	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
63	An Amateur's Introduction to Recursive Query Processing Strategies	1986	SIGMOD	0.00038782376
217	Traversal Recursion: A Practical Approach to Supporting Recursive Applications	1986	SIGMOD	0.00024458594

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,811	Schema-Based Query Optimisation for Graph Databases	2025	SIGMOD
2	8,943	Compact O-Complete Trees	1988	VLDB
3	1,330	Efficient Transitive Closure Algorithms	1988	VLDB
4	11,745	Parallel Traversal of Graphs Stored in RDBMSs	2020	CIDR
5	6,451	Efficient Search of Multidimensional B-Trees	1995	VLDB
6	4,107	Processing Queries on Tree-Structured Data Efficiently	2006	PODS
7	8,035	On Tree-Based Techniques for Query Evaluation	1992	PODS
8	9,173	Optimizing Recursive Queries in SQL	2005	SIGMOD
9	4,425	EFFICIENT EVALUATION FOR A SUBSET OF RECURSIVE QUERIES (Extended Abstract)	1987	PODS
10	217	Traversal Recursion: A Practical Approach to Supporting Recursive Applications	1986	SIGMOD