A comparison of labeling schemes for ancestor queries
Lists
Only you see this
Abstract
Motivated by a recent application in XML search engines we study the problem of labeling the nodes of a tree (XML file) such that given the labels of two nodes one can determine whether one node is an ancestor of the other. We describe several new prefix-based labeling schemes, where an ancestor query roughly amounts to testing whether one label is a prefix of the other. We compare our new schemes to a simple interval-based scheme currently used by search engines, as well as, to schemes with the best theoretical guarantee on the maximum label length. We performed our experimental evaluation on real XML data and on some families of random trees.
BibTeX
@inproceedings{kaplan2002comparison,
author = {Haim Kaplan and Tova Milo and Ronen Shabo},
title = {{A comparison of labeling schemes for ancestor queries}},
booktitle = {SODA},
year = {2002},
url = {https://openreview.net/forum?id=mNMkoJxWyoE},
}Loading related content...