کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
396926 670631 2013 15 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Comparing top-k XML lists
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر هوش مصنوعی
پیش نمایش صفحه اول مقاله
Comparing top-k XML lists
چکیده انگلیسی

Systems that produce ranked lists of results are abundant. For instance, Web search engines return ranked lists of Web pages. There has been work on distance measure for list permutations, like Kendall tau and Spearman's footrule, as well as extensions to handle top-k lists, which are more common in practice. In addition to ranking whole objects (e.g., Web pages), there is an increasing number of systems that provide keyword search on XML or other semistructured data, and produce ranked lists of XML sub-trees. Unfortunately, previous distance measures are not suitable for ranked lists of sub-trees since they do not account for the possible overlap between the returned sub-trees. That is, two sub-trees differing by a single node would be considered separate objects. In this paper, we present the first distance measures for ranked lists of sub-trees, and show under what conditions these measures are metrics. Furthermore, we present algorithms to efficiently compute these distance measures. Finally, we evaluate and compare the proposed measures on real data using three popular XML keyword proximity search systems.


► First suite of distance measures for ranked lists of sub-trees.
► Distance measures consider both total mappings and partial mappings with position.
► We prove under what conditions these measures are metrics.
► We evaluate these measures using real datasets, using three XML search systems.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Systems - Volume 38, Issue 6, September 2013, Pages 820–834
نویسندگان
, , ,