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: ha1d2cf68f9e94b16
Venue: PODS
Year: 2002
Pagerank: 0.00025659453
Overall Rank: 192 | 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
176	Graph Indexing: A Frequent Structure-based Approach	2004	SIGMOD	0.00026700508
288	Graphs-at-a-time: Query Language and Access Methods for Graph Databases	2008	SIGMOD	0.00021969641
332	FG-Index: Towards Verification-Free Query Processing on Graph Databases	2007	SIGMOD	0.00020765078
355	On Graph Query Optimization in Large Networks	2010	VLDB	0.00020124083
453	Stack-based Algorithms for Pattern Matching on DAGs	2005	VLDB	0.00017972038
462	Counting Triangles in Data Streams	2006	PODS	0.00017807125
511	Scalable SPARQL Querying of Large RDF Graphs	2011	VLDB	0.00017061883
601	Substructure Similarity Search in Graph Databases	2005	SIGMOD	0.00015732701
679	Efficient Algorithms for Processing XPath Queries	2002	VLDB	0.00014837097
736	Graph Indexing: Tree + Delta >= Graph	2007	VLDB	0.00014363536
783	Distance-Join: Pattern Match Query In a Large Graph Database	2009	VLDB	0.00014021799
1,133	Comparing Stars: On Approximating Graph Edit Distance	2009	VLDB	0.00011898162
1,148	Graph Pattern Matching: From Intractable to Polynomial Time	2010	VLDB	0.00011809728
1,181	An In-depth Comparison of Subgraph Isomorphism Algorithms in Graph Databases	2013	VLDB	0.00011627329
1,374	Neighborhood Based Fast Graph Search in Large Networks	2011	SIGMOD	0.00010880336
1,804	gStore: Answering SPARQL Queries via Subgraph Matching	2011	VLDB	9.6025094e-05
2,376	Towards Graph Containment Search and Indexing	2007	VLDB	8.5543073e-05
2,702	TreeSpan: Efficiently Computing Similarity All-Matching	2012	SIGMOD	8.1177147e-05
2,773	Graph Homomorphism Revisited for Graph Matching	2010	VLDB	8.0351713e-05
3,499	iGraph: A Framework for Comparisons of Disk-Based Graph Indexing Techniques	2010	VLDB	7.2549774e-05
3,661	On Querying Historical Evolving Graph Sequences	2011	VLDB	7.1198662e-05
4,587	Fast Continuous Subgraph Matching over Streaming Graphs via Backtracking Reduction	2023	SIGMOD	6.5161686e-05
6,232	Efficient Exact Subgraph Matching via GNN-based Path Dominance Embedding	2024	VLDB	5.84313e-05
7,670	Efficient Indexing and Querying over Syntactically Annotated Trees	2012	VLDB	5.4772833e-05
7,969	Periscope/GQ: A Graph Querying Toolkit	2008	VLDB	5.4153733e-05
7,990	From a Stream of Relational Queries to Distributed Stream Processing	2010	VLDB	5.4116144e-05
10,247	Top-k Relevant Semantic Place Retrieval on Spatial RDF Data	2016	SIGMOD	5.0525742e-05
10,740	Characterizing Parallel Subgraph Matching Performance: A Systematic Study of Interactions, Scalability, and Enumeration	2026	VLDB	4.9793485e-05
11,432	Mix & Match: Subgraph Matching for Absolute Coverage	2025	VLDB	4.9793485e-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,653	Indexing for Keyword Search with Structured Constraints	2023	PODS
2	6,584	Efficient Search of Multidimensional B-Trees	1995	VLDB
3	7,355	Efficient Search in Very Large Databases	1988	VLDB
4	768	Effective Keyword Search in Relational Databases	2006	SIGMOD
5	1,565	Keyword Proximity Search in Complex Data Graphs	2008	SIGMOD
6	9,786	Memory-Efficient Search Trees for Database Management Systems	2021	SIGMOD
7	1,445	Finding and Approximating Top-k Answers in Keyword Proximity Search	2006	PODS
8	8,662	Top-K Nearest Keyword Search on Large Graphs	2013	VLDB
9	2,167	An Approximate Search Engine for Structural Databases	2000	SIGMOD
10	3,509	Keyword Search on External Memory Data Graphs	2008	VLDB