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.00025589066
Overall Rank: 195 | 98.70%
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.00026634326
288	Graphs-at-a-time: Query Language and Access Methods for Graph Databases	2008	SIGMOD	0.00022009138
333	FG-Index: Towards Verification-Free Query Processing on Graph Databases	2007	SIGMOD	0.00020712452
356	On Graph Query Optimization in Large Networks	2010	VLDB	0.00020086045
456	Stack-based Algorithms for Pattern Matching on DAGs	2005	VLDB	0.00017946233
465	Counting Triangles in Data Streams	2006	PODS	0.00017754185
513	Scalable SPARQL Querying of Large RDF Graphs	2011	VLDB	0.00017023182
601	Substructure Similarity Search in Graph Databases	2005	SIGMOD	0.00015699993
683	Efficient Algorithms for Processing XPath Queries	2002	VLDB	0.00014781223
734	Graph Indexing: Tree + Delta >= Graph	2007	VLDB	0.00014334121
786	Distance-Join: Pattern Match Query In a Large Graph Database	2009	VLDB	0.00013979657
1,136	Comparing Stars: On Approximating Graph Edit Distance	2009	VLDB	0.00011857445
1,148	Graph Pattern Matching: From Intractable to Polynomial Time	2010	VLDB	0.00011777466
1,180	An In-depth Comparison of Subgraph Isomorphism Algorithms in Graph Databases	2013	VLDB	0.00011600363
1,378	Neighborhood Based Fast Graph Search in Large Networks	2011	SIGMOD	0.00010848501
1,813	gStore: Answering SPARQL Queries via Subgraph Matching	2011	VLDB	9.5705978e-05
2,387	Towards Graph Containment Search and Indexing	2007	VLDB	8.5236741e-05
2,705	TreeSpan: Efficiently Computing Similarity All-Matching	2012	SIGMOD	8.0936619e-05
2,782	Graph Homomorphism Revisited for Graph Matching	2010	VLDB	8.0054142e-05
3,504	iGraph: A Framework for Comparisons of Disk-Based Graph Indexing Techniques	2010	VLDB	7.2296629e-05
3,665	On Querying Historical Evolving Graph Sequences	2011	VLDB	7.0996773e-05
4,485	Fast Continuous Subgraph Matching over Streaming Graphs via Backtracking Reduction	2023	SIGMOD	6.5644966e-05
6,245	Efficient Exact Subgraph Matching via GNN-based Path Dominance Embedding	2024	VLDB	5.8210521e-05
7,689	Efficient Indexing and Querying over Syntactically Annotated Trees	2012	VLDB	5.4565877e-05
7,991	Periscope/GQ: A Graph Querying Toolkit	2008	VLDB	5.3949937e-05
8,012	From a Stream of Relational Queries to Distributed Stream Processing	2010	VLDB	5.3911783e-05
10,283	Top-k Relevant Semantic Place Retrieval on Spatial RDF Data	2016	SIGMOD	5.0334833e-05
10,811	Characterizing Parallel Subgraph Matching Performance: A Systematic Study of Interactions, Scalability, and Enumeration	2026	VLDB	4.9605343e-05
11,491	Mix & Match: Subgraph Matching for Absolute Coverage	2025	VLDB	4.9605343e-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,688	Indexing for Keyword Search with Structured Constraints	2023	PODS
2	6,597	Efficient Search of Multidimensional B-Trees	1995	VLDB
3	7,381	Efficient Search in Very Large Databases	1988	VLDB
4	777	Effective Keyword Search in Relational Databases	2006	SIGMOD
5	1,566	Keyword Proximity Search in Complex Data Graphs	2008	SIGMOD
6	9,824	Memory-Efficient Search Trees for Database Management Systems	2021	SIGMOD
7	1,450	Finding and Approximating Top-k Answers in Keyword Proximity Search	2006	PODS
8	8,684	Top-K Nearest Keyword Search on Large Graphs	2013	VLDB
9	2,177	An Approximate Search Engine for Structural Databases	2000	SIGMOD
10	3,512	Keyword Search on External Memory Data Graphs	2008	VLDB