Algorithmics and applications of tree and graph searching
The DOI matches its Crossref record; 53 of the 53 references it cites were found in a registry or an index.
Abstract
Modern search engines answer keyword-based queries extremely efficiently. The impressive speed is due to clever inverted index structures, caching, a domain-independent knowledge of strings, and thousands of machines. Several research efforts have attempted to generalize keyword search to keytree and keygraph searching, because trees and graphs have many applications in next-generation database systems. This paper surveys both algorithms and applications, giving some emphasis to our own work.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
(1979) · Cited by 43,841
Baeza-Yates, R. A., & Ribeiro-Neto, B. A. (1999) · Cited by 11,505
Principles of Artificial Intelligence
Nilsson, N. J. (1982) · doi:10.1007/978-3-662-09438-9 · Cited by 3,457
Information Retrieval: Data Structures and Algorithms
Frakes, W. B., & Baeza-Yates, R. A. (1992) · Cited by 2,757
An Algorithm for Subgraph Isomorphism
Ullmann, J. R. (1976) · Journal of the ACM · doi:10.1145/321921.321925 · Cited by 2,277
DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases
Goldman, R., & Widom, J. (1997) · Cited by 1,136
A graduated assignment algorithm for graph matching
Gold, S., & Rangarajan, A. (1996) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.491619 · Cited by 1,090
Data on the Web from relations to semistructured data and XML
Abiteboul, S., Buneman, P., & Suciu, D. M. (2000) · Cited by 1,062
The Lorel query language for semistructured data
Abiteboul, S., Quass, D., McHugh, J., Widom, J., & Wiener, J. L. (1997) · International Journal on Digital Libraries · doi:10.1007/s007990050005 · Cited by 1,058
A distance measure between attributed relational graphs for pattern recognition
Sanfeliu, A., & Fu, K.-S. (1983) · IEEE Transactions on Systems, Man, and Cybernetics · doi:10.1109/tsmc.1983.6313167 · Cited by 999
Cited by
Survey of graph database models
Angles, R., & Gutierrez, C. (2008) · ACM Computing Surveys · doi:10.1145/1322432.1322433 · Cited by 1,706
A Survey of Schema-Based Matching Approaches
Shvaiko, P., & Euzenat, J. (2005) · Lecture Notes in Computer Science · doi:10.1007/11603412_5 · Cited by 1,147
Graph indexing: a frequent structure-based approach
Yan, X., Yu, P. S., & Han, J. (2004) · Proceedings of the 2004 ACM SIGMOD international conference on Management of data · doi:10.1145/1007568.1007607 · Cited by 637
Managing and Mining Graph Data
(2010) · Advances in Database Systems · doi:10.1007/978-1-4419-6045-0 · Cited by 594
Provenance and scientific workflows: challenges and opportunities
Davidson, S. B., & Freire, J. (2008) · Proceedings of the 2008 ACM SIGMOD international conference on Management of data · doi:10.1145/1376616.1376772 · Cited by 468
Scalable SPARQL querying of large RDF graphs
Huang, J., Abadi, D. J., & Ren, K. (2011) · Proceedings of the VLDB Endowment · doi:10.14778/3402707.3402747 · Cited by 461
Graphs-at-a-time: query language and access methods for graph databases
He, H., & Singh, A. K. (2008) · Proceedings of the 2008 ACM SIGMOD international conference on Management of data · doi:10.1145/1376616.1376660 · Cited by 450
Comparing stars: on approximating graph edit distance
Zeng, Z., Tung, A. K. H., Wang, J., Feng, J., & Zhou, L. (2009) · Proceedings of the VLDB Endowment · doi:10.14778/1687627.1687631 · Cited by 399
Self-citationComputational approaches for detecting protein complexes from protein interaction networks: a survey
Li, X., Wu, M., Kwoh, C.-K., & Ng, S.-K. (2010) · BMC Genomics · doi:10.1186/1471-2164-11-s1-s3 · Cited by 349
A survey of frequent subgraph mining algorithms
Jiang, C., Coenen, F., & Zito, M. (2013) · The Knowledge Engineering Review · doi:10.1017/s0269888912000331 · Cited by 346
Substructure similarity search in graph databases
Yan, X., Yu, P. S., & Han, J. (2005) · Proceedings of the 2005 ACM SIGMOD international conference on Management of data · doi:10.1145/1066157.1066244 · Cited by 314
Large-scale malware indexing using function-call graphs
Hu, X., Chiueh, T.-C., & Shin, K. G. (2009) · Proceedings of the 16th ACM conference on Computer and communications security · doi:10.1145/1653662.1653736 · Cited by 312
Closure-Tree: An Index Structure for Graph Queries
He, H., & Singh, A. K. (2006) · 22nd International Conference on Data Engineering (ICDE'06) · doi:10.1109/icde.2006.37 · Cited by 293
Graph pattern matching: from intractable to polynomial time
Fan, W., Li, J., Ma, S., Tang, N., Wu, Y., & Wu, Y. (2010) · Proceedings of the VLDB Endowment · doi:10.14778/1920841.1920878 · Cited by 285
Fg-index: towards verification-free query processing on graph databases
Cheng, J., Ke, Y., Ng, W., & Lu, A. (2007) · Proceedings of the 2007 ACM SIGMOD international conference on Management of data · doi:10.1145/1247480.1247574 · Cited by 265
A Comparison of Current Graph Database Models
Angles, R. (2012) · 2012 IEEE 28th International Conference on Data Engineering Workshops · doi:10.1109/icdew.2012.31 · Cited by 260
SAGA: a subgraph matching tool for biological graphs
Tian, Y., McEachin, R. C., Santos, C., States, D. J., & Patel, J. M. (2007) · Bioinformatics · doi:10.1093/bioinformatics/btl571 · Cited by 253
Metadata
- Authors
- Shasha, D., Wang, J. T. L., & Giugno, R.
- Venue
- Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems
- Publisher
- ACM
- Published
- 2002-06-03
- Pages
- 39-52
- OpenAlex
- W2050137450
- Cited by
- 387
- References
- 53
- FWCI
- 12.23
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.