Algorithmics and Applications of Tree and Graph Searching

Summary: Survey of algorithmics for keyword search generalized from strings to trees and graphs (keytree/keygraph), focusing on index structures, query semantics, and algorithmic tradeoffs. Emphasizes DB applications and the authors' efficient indexing, pruning, and scalable evaluation techniques. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1249
Venue: PODS
Year: 2002
Pagerank: 0.00026138589
Overall Rank: 187 | 98.72%
DOI: 10.1145/543613.543620

Incoming Non-self Citations Over Time

Authors

1. Dennis Shasha (New York University)
2. Jason T. L. Wang (New Jersey Institute of Technology)
3. Rosalba Giugno (University of Catania)

BibTeX Citation

@inproceedings{shasha_pods02,
        address = {New York, NY, USA},
        series = {{PODS} '02},
        title = {{Algorithmics and Applications of Tree and Graph Searching}},
        url = {https://dl.acm.org/doi/10.1145/543613.543620},
        doi = {10.1145/543613.543620},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Shasha, Dennis and Wang, Jason T. L. and Giugno, Rosalba},
        year = {2002}
}

Incoming Citations (Sorted by Pagerank)

Showing 29 of 29 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
177	Graph Indexing: A Frequent Structure-based Approach	2004	SIGMOD	0.00027100548
294	Graphs-at-a-time: Query Language and Access Methods for Graph Databases	2008	SIGMOD	0.00022253507
326	FG-Index: Towards Verification-Free Query Processing on Graph Databases	2007	SIGMOD	0.00021152829
352	On Graph Query Optimization in Large Networks	2010	VLDB	0.00020375193
444	Stack-based Algorithms for Pattern Matching on DAGs	2005	VLDB	0.00018350865
458	Counting Triangles in Data Streams	2006	PODS	0.0001810876
500	Scalable SPARQL Querying of Large RDF Graphs	2011	VLDB	0.00017413839
591	Substructure Similarity Search in Graph Databases	2005	SIGMOD	0.0001603683
666	Efficient Algorithms for Processing XPath Queries	2002	VLDB	0.00015166582
727	Graph Indexing: Tree + Delta >= Graph	2007	VLDB	0.00014565738
776	Distance-Join: Pattern Match Query In a Large Graph Database	2009	VLDB	0.00014110016
1,115	Comparing Stars: On Approximating Graph Edit Distance	2009	VLDB	0.00012117375
1,128	Graph Pattern Matching: From Intractable to Polynomial Time	2010	VLDB	0.0001206219
1,181	An In-depth Comparison of Subgraph Isomorphism Algorithms in Graph Databases	2013	VLDB	0.0001179597
1,394	Neighborhood Based Fast Graph Search in Large Networks	2011	SIGMOD	0.0001093153
1,774	gStore: Answering SPARQL Queries via Subgraph Matching	2011	VLDB	9.7870727e-05
2,328	Towards Graph Containment Search and Indexing	2007	VLDB	8.745748e-05
2,650	TreeSpan: Efficiently Computing Similarity All-Matching	2012	SIGMOD	8.2920414e-05
2,718	Graph Homomorphism Revisited for Graph Matching	2010	VLDB	8.209788e-05
3,431	iGraph: A Framework for Comparisons of Disk-Based Graph Indexing Techniques	2010	VLDB	7.4189541e-05
3,594	On Querying Historical Evolving Graph Sequences	2011	VLDB	7.2736453e-05
4,995	Fast Continuous Subgraph Matching over Streaming Graphs via Backtracking Reduction	2023	SIGMOD	6.4089186e-05
6,149	Efficient Exact Subgraph Matching via GNN-based Path Dominance Embedding	2024	VLDB	5.9581422e-05
7,524	Efficient Indexing and Querying over Syntactically Annotated Trees	2012	VLDB	5.6029996e-05
7,823	Periscope/GQ: A Graph Querying Toolkit	2008	VLDB	5.5370475e-05
7,840	From a Stream of Relational Queries to Distributed Stream Processing	2010	VLDB	5.5339505e-05
10,052	Top-k Relevant Semantic Place Retrieval on Spatial RDF Data	2016	SIGMOD	5.1685424e-05
10,558	Characterizing Parallel Subgraph Matching Performance: A Systematic Study of Interactions, Scalability, and Enumeration	2026	VLDB	5.093636e-05
11,075	Mix & Match: Subgraph Matching for Absolute Coverage	2025	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 0 of 0 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,472	Indexing for Keyword Search with Structured Constraints	2023	PODS
2	6,451	Efficient Search of Multidimensional B-Trees	1995	VLDB
3	7,342	Efficient Search in Very Large Databases	1988	VLDB
4	748	Effective Keyword Search in Relational Databases	2006	SIGMOD
5	1,542	Keyword Proximity Search in Complex Data Graphs	2008	SIGMOD
6	9,635	Memory-Efficient Search Trees for Database Management Systems	2021	SIGMOD
7	1,429	Finding and Approximating Top-k Answers in Keyword Proximity Search	2006	PODS
8	8,493	Top-K Nearest Keyword Search on Large Graphs	2013	VLDB
9	2,143	An Approximate Search Engine for Structural Databases	2000	SIGMOD
10	3,450	Keyword Search on External Memory Data Graphs	2008	VLDB