A Scalable Index for Top-k Subtree Similarity Queries
Summary: Scalable top-k subtree similarity via inverted lists; processes subtrees first and supports incremental updates in linear space. Tuning-free, data-type agnostic; outperforms state-of-the-art indexes in time and memory, up to four orders of magnitude. (summarized by gpt-5-nano on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Daniel Kocher (University of Salzburg)
- 2. Nikolaus Augsten (University of Salzburg)
BibTeX Citation
@inproceedings{kocher_sigmod19,
title = {{A Scalable Index for Top-k Subtree Similarity Queries}},
author = {Kocher, Daniel and Augsten, Nikolaus},
series = {{SIGMOD} '19},
booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
publisher = {Association for Computing Machinery},
doi = {10.1145/3299869.3319892},
url = {https://dl.acm.org/doi/10.1145/3299869.3319892},
year = {2019}
}Incoming Citations (Sorted by Pagerank)
Showing 2 of 2 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 4,596 | AS-Parser: Log Parsing Based on Adaptive Segmentation | 2023 | SIGMOD | 6.5074617e-05 |
| 8,684 | JEDI: These aren't the JSON documents you're looking for... | 2022 | SIGMOD | 5.2885567e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 10 of 10 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 5 | Optimal Aggregation Algorithms for Middleware [Extended Abstract] | 2001 | PODS | 0.0010679903 |
| 918 | Accelerating XPath Location Steps | 2002 | SIGMOD | 0.00013078274 |
| 1,535 | Top-k Query Evaluation with Probabilistic Guarantees | 2004 | VLDB | 0.00010326646 |
| 2,048 | On the Integration of Structure Indexes and Inverted Lists | 2004 | SIGMOD | 9.1227281e-05 |
| 3,110 | Similarity Evaluation on Tree-structured Data | 2005 | SIGMOD | 7.6367063e-05 |
| 3,653 | Best Position Algorithms for Top-k Queries | 2007 | VLDB | 7.1279819e-05 |
| 4,665 | Approximate Matching of Hierarchical Data Using pq-Grams | 2005 | VLDB | 6.4779518e-05 |
| 6,140 | Scaling Similarity Joins over Tree-Structured Data | 2015 | VLDB | 5.8708494e-05 |
| 7,088 | Indexing for Subtree Similarity-Search using Edit Distance | 2013 | SIGMOD | 5.5997256e-05 |
| 8,153 | DeltaNI: An Efficient Labeling Scheme for Versioned Hierarchical Data | 2013 | SIGMOD | 5.3883285e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 9,409 | Adaptive Indexing in High-Dimensional Metric Spaces | 2023 | VLDB |
| 2 | 7,705 | An Incrementally Maintainable Index for Approximate Lookups in Hierarchical Data | 2006 | VLDB |
| 3 | 2,061 | Similarity search in the blink of an eye with compressed indices | 2023 | VLDB |
| 4 | 8,668 | Top-K Nearest Keyword Search on Large Graphs | 2013 | VLDB |
| 5 | 7,032 | Efficient Similarity Join and Search on Multi-Attribute Data | 2015 | SIGMOD |
| 6 | 7,846 | Efficient Top-k Algorithms for Approximate Substring Matching | 2013 | SIGMOD |
| 7 | 7,676 | Efficient Indexing and Querying over Syntactically Annotated Trees | 2012 | VLDB |
| 8 | 6,140 | Scaling Similarity Joins over Tree-Structured Data | 2015 | VLDB |
| 9 | 7,088 | Indexing for Subtree Similarity-Search using Edit Distance | 2013 | SIGMOD |
| 10 | 3,110 | Similarity Evaluation on Tree-structured Data | 2005 | SIGMOD |