Matching dominance: Capture the semantics of dominance for multi-dimensional uncertain objects

Publication Type:
Conference Proceeding
ACM International Conference Proceeding Series, 2014
Issue Date:
Full metadata record
Files in This Item:
Filename Description Size
ThumbnailSSDBM14_dominance.pdf Published version304.69 kB
Adobe PDF
The dominance operator plays an important role in a wide spectrum of multi-criteria decision making applications. Generally speaking, a dominance operator is a partial order on a setO of objects, and we say the dominance operator has the monotonic property regarding a family of ranking functions F if o1dominates o2implies f(o1) ≥ f( o2) for any ranking function f ε F and objects o1, o2ε O The dominance operator on the multi-dimensional points is well defined, which has the monotonic property regarding any monotonic ranking (scoring) function. Due to the uncertain nature of data in many emerging applications, a variety of existing works have studied the semantics of ranking query on uncertain objects. However, the problem of dominance operator against multi-dimensional uncertain objects remains open. Although there are several attempts to propose dominance operator on multi-dimensional uncertain objects, none of them claims the monotonic property on these ranking approaches. Motivated by this, in this paper we propose a novel matching based dominance operator, namely matching dominance, to capture the semantics of the dominance for multidimensional uncertain objects so that the new dominance operator has the monotonic property regarding the monotonic parameterized ranking function, which can unify other popular ranking approaches for uncertain objects. Then we develop a layer indexing technique, Matching Dominance based Band (MDB), to facilitate the top k queries on multidimensional uncertain objects based on the matching dominance operator proposed in this paper. Efficient algorithms are proposed to compute the MDB index. Comprehensive experiments convincingly demonstrate the effectiveness and efficiency of our indexing techniques. © Copyright 2014 ACM 978-1-4503-2722-0/14/06⋯$15.00.
Please use this identifier to cite or link to this item: