On Estimating the Maximum Domination Value and the Skyline Cardinality of Multi-Dimensional Data Sets

Eleftherios Tiakas, Apostolos N. Papadopoulos and Yannis Manolopoulos
Additional contact information
Eleftherios Tiakas: Department of Informatics, Aristotle University, Thessaloniki, Greece
Apostolos N. Papadopoulos: Department of Informatics, Aristotle University, Thessaloniki, Greece
Yannis Manolopoulos: Department of Informatics, Aristotle University, Thessaloniki, Greece

International Journal of Knowledge-Based Organizations (IJKBO), 2013, vol. 3, issue 4, 61-83

Abstract: The last years there is an increasing interest for query processing techniques that take into consideration the dominance relationship between items to select the most promising ones, based on user preferences. Skyline and top-k dominating queries are examples of such techniques. A skyline query computes the items that are not dominated, whereas a top-k dominating query returns the k items with the highest domination score. To enable query optimization, it is important to estimate the expected number of skyline items as well as the maximum domination value of an item. In this article, the authors provide an estimation for the maximum domination value under the dinstinct values and attribute independence assumptions. The authors provide three different methodologies for estimating and calculating the maximum domination value and the authors test their performance and accuracy. Among the proposed estimation methods, their method Estimation with Roots outperforms all others and returns the most accurate results. They also introduce the eliminating dimension, i.e., the dimension beyond which all domination values become zero, and the authors provide an efficient estimation of that dimension. Moreover, the authors provide an accurate estimation of the skyline cardinality of a data set.

Date: 2013
References: Add references at CitEc
Citations:

Downloads: (external link)
http://services.igi-global.com/resolvedoi/resolve. ... 018/ijkbo.2013100104 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:igg:jkbo00:v:3:y:2013:i:4:p:61-83

Access Statistics for this article

International Journal of Knowledge-Based Organizations (IJKBO) is currently edited by John Wang

More articles in International Journal of Knowledge-Based Organizations (IJKBO) from IGI Global
Bibliographic data for series maintained by Journal Editor ().