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.00025647819
Overall Rank: 193 | 98.71%
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.00026688651
289	Graphs-at-a-time: Query Language and Access Methods for Graph Databases	2008	SIGMOD	0.00021960834
332	FG-Index: Towards Verification-Free Query Processing on Graph Databases	2007	SIGMOD	0.00020756016
355	On Graph Query Optimization in Large Networks	2010	VLDB	0.00020116134
453	Stack-based Algorithms for Pattern Matching on DAGs	2005	VLDB	0.00017963727
463	Counting Triangles in Data Streams	2006	PODS	0.00017799662
512	Scalable SPARQL Querying of Large RDF Graphs	2011	VLDB	0.00017053842
601	Substructure Similarity Search in Graph Databases	2005	SIGMOD	0.00015725619
680	Efficient Algorithms for Processing XPath Queries	2002	VLDB	0.0001483008
737	Graph Indexing: Tree + Delta >= Graph	2007	VLDB	0.00014357361
784	Distance-Join: Pattern Match Query In a Large Graph Database	2009	VLDB	0.00014015324
1,133	Comparing Stars: On Approximating Graph Edit Distance	2009	VLDB	0.00011892544
1,150	Graph Pattern Matching: From Intractable to Polynomial Time	2010	VLDB	0.00011804185
1,181	An In-depth Comparison of Subgraph Isomorphism Algorithms in Graph Databases	2013	VLDB	0.00011621825
1,374	Neighborhood Based Fast Graph Search in Large Networks	2011	SIGMOD	0.00010875727
1,804	gStore: Answering SPARQL Queries via Subgraph Matching	2011	VLDB	9.5980088e-05
2,377	Towards Graph Containment Search and Indexing	2007	VLDB	8.5503022e-05
2,701	TreeSpan: Efficiently Computing Similarity All-Matching	2012	SIGMOD	8.114832e-05
2,774	Graph Homomorphism Revisited for Graph Matching	2010	VLDB	8.0313907e-05
3,499	iGraph: A Framework for Comparisons of Disk-Based Graph Indexing Techniques	2010	VLDB	7.2515431e-05
3,662	On Querying Historical Evolving Graph Sequences	2011	VLDB	7.1164957e-05
4,589	Fast Continuous Subgraph Matching over Streaming Graphs via Backtracking Reduction	2023	SIGMOD	6.5130839e-05
6,235	Efficient Exact Subgraph Matching via GNN-based Path Dominance Embedding	2024	VLDB	5.8403639e-05
7,676	Efficient Indexing and Querying over Syntactically Annotated Trees	2012	VLDB	5.4746904e-05
7,973	Periscope/GQ: A Graph Querying Toolkit	2008	VLDB	5.4128097e-05
7,995	From a Stream of Relational Queries to Distributed Stream Processing	2010	VLDB	5.4090565e-05
10,253	Top-k Relevant Semantic Place Retrieval on Spatial RDF Data	2016	SIGMOD	5.0501823e-05
10,750	Characterizing Parallel Subgraph Matching Performance: A Systematic Study of Interactions, Scalability, and Enumeration	2026	VLDB	4.9769913e-05
11,438	Mix & Match: Subgraph Matching for Absolute Coverage	2025	VLDB	4.9769913e-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,660	Indexing for Keyword Search with Structured Constraints	2023	PODS
2	6,587	Efficient Search of Multidimensional B-Trees	1995	VLDB
3	7,359	Efficient Search in Very Large Databases	1988	VLDB
4	770	Effective Keyword Search in Relational Databases	2006	SIGMOD
5	1,565	Keyword Proximity Search in Complex Data Graphs	2008	SIGMOD
6	9,792	Memory-Efficient Search Trees for Database Management Systems	2021	SIGMOD
7	1,446	Finding and Approximating Top-k Answers in Keyword Proximity Search	2006	PODS
8	8,668	Top-K Nearest Keyword Search on Large Graphs	2013	VLDB
9	2,169	An Approximate Search Engine for Structural Databases	2000	SIGMOD
10	3,509	Keyword Search on External Memory Data Graphs	2008	VLDB