Λεπτομέρειες

ΕίδοςΔημοσίευση
ΚωδικόςTR-2012-6
ΤίτλοςΑποδοτική αναζήτηση λέξεων κλειδιών σε μεγάλες βάσεις δεδομένων δενδρικής δομής.
ΣυγγραφέαςΑγγελική Δημητρίου, Δημήτρης Θεοδωράτος
Έτος2012
Λέξεις κλειδιάkeyword search, XML, tree-structured data, LCA, search algorithm, ranking
ΠερίληψηKeyword search is the most popular paradigm for querying XML data on the web. In this context, three challenging problems are (a) to avoid missing useful results in the answer set, (b) to rank the results with respect to some relevance criterion and (c) to design algorithms that can efficiently compute the results on large datasets. In this paper, we present a novel multi-stack based algorithm that returns as an answer to a keyword query all the results ranked on their size. Our algorithm exploits a lattice of stacks each corresponding to a partition of the keyword set of the query. This feature empowers a linear time performance on the size of the input data for a given number of query keywords. As a result, our algorithm can run efficiently on large input data for several keywords. We also present a variation of our algorithm which accounts for in- frequent keywords in the query and show that it can significantly improve the execution time. An extensive experimental evaluation of our approach confirms the theoretical analysis, and shows that it scales smoothly when the size of the input data and the number of input keywords increases.
ΚατηγορίαSemanttic Web, XML
ΔημοσίευσηACM KEYS 2012, Proceedings of the Third International Workshop on Keyword Search on Structured Data, Pages 63-74
Αρχείο Επισκόπηση


Επιστροφή στην αρχική σελίδα