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)

Paper ID: 5766
Venue: SIGMOD
Year: 2019
Pagerank: 5.7596335e-05
Overall Rank: 6,832 | 53.13%
DOI: 10.1145/3299869.3319892

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,502	AS-Parser: Log Parsing Based on Adaptive Segmentation	2023	SIGMOD	6.6599757e-05
8,508	JEDI: These aren't the JSON documents you're looking for...	2022	SIGMOD	5.4123872e-05

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.0010828372
893	Accelerating XPath Location Steps	2002	SIGMOD	0.00013374715
1,519	Top-k Query Evaluation with Probabilistic Guarantees	2004	VLDB	0.00010513777
2,006	On the Integration of Structure Indexes and Inverted Lists	2004	SIGMOD	9.3190255e-05
3,047	Similarity Evaluation on Tree-structured Data	2005	SIGMOD	7.8155543e-05
3,702	Best Position Algorithms for Top-k Queries	2007	VLDB	7.1838636e-05
4,566	Approximate Matching of Hierarchical Data Using pq-Grams	2005	VLDB	6.6275286e-05
6,014	Scaling Similarity Joins over Tree-Structured Data	2015	VLDB	6.0084322e-05
6,947	Indexing for Subtree Similarity-Search using Edit Distance	2013	SIGMOD	5.7309645e-05
7,981	DeltaNI: An Efficient Labeling Scheme for Versioned Hierarchical Data	2013	SIGMOD	5.5146136e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,334	Adaptive Indexing in High-Dimensional Metric Spaces	2023	VLDB
2	7,559	An Incrementally Maintainable Index for Approximate Lookups in Hierarchical Data	2006	VLDB
3	2,519	Similarity search in the blink of an eye with compressed indices	2023	VLDB
4	8,493	Top-K Nearest Keyword Search on Large Graphs	2013	VLDB
5	6,906	Efficient Similarity Join and Search on Multi-Attribute Data	2015	SIGMOD
6	7,692	Efficient Top-k Algorithms for Approximate Substring Matching	2013	SIGMOD
7	7,524	Efficient Indexing and Querying over Syntactically Annotated Trees	2012	VLDB
8	6,014	Scaling Similarity Joins over Tree-Structured Data	2015	VLDB
9	6,947	Indexing for Subtree Similarity-Search using Edit Distance	2013	SIGMOD
10	3,047	Similarity Evaluation on Tree-structured Data	2005	SIGMOD