File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Efficient skyline evaluation over partially ordered domains

TitleEfficient skyline evaluation over partially ordered domains
Authors
KeywordsColumn-store
False positive
Multidimensional data
Ordered domains
Partial order
Issue Date2010
PublisherVery Large Data Base (VLDB) Endowment Inc.. The Journal's web site is located at http://vldb.org/pvldb/index.html
Citation
The 36th International Conference on Very Large Data Bases, Singapore, 13-17 September 2010. In Proceedings of the VLDB Endowment, 2010, v. 3 n. 1, p. 1255-1266 How to Cite?
AbstractAlthough there has been a considerable body of work on skyline evaluation in multidimensional data with totally ordered attribute domains, there are only a few methods that consider attributes with partially ordered domains. Existing work maps each partially ordered domain to a total order and then adapts algorithms for totallyordered domains to solve the problem. Nevertheless these methods either use stronger notions of dominance, which generate false positives, or require expensive dominance checks. In this paper, we propose two new methods, which do not have these drawbacks. The first method uses an appropriate mapping of a partial order to a total order, inspired by the lattice theorem and an off-the-shelf skyline algorithm. The second technique uses an appropriate storage and indexing approach, inspired by column stores, which enables efficient verification of whether a pair of objects are incompatible. We demonstrate that both our methods are up to an order of magnitude more efficient than previous work and scale well with different problem parameters, such as complexity of partial orders. © 2010 VLDB Endowment.
Persistent Identifierhttp://hdl.handle.net/10722/129581
ISSN
References

 

DC FieldValueLanguage
dc.contributor.authorZhang, Sen_US
dc.contributor.authorMamoulis, Nen_US
dc.contributor.authorKao, Ben_US
dc.contributor.authorCheung, DWLen_US
dc.date.accessioned2010-12-23T08:39:28Z-
dc.date.available2010-12-23T08:39:28Z-
dc.date.issued2010en_US
dc.identifier.citationThe 36th International Conference on Very Large Data Bases, Singapore, 13-17 September 2010. In Proceedings of the VLDB Endowment, 2010, v. 3 n. 1, p. 1255-1266en_US
dc.identifier.issn2150-8097-
dc.identifier.urihttp://hdl.handle.net/10722/129581-
dc.description.abstractAlthough there has been a considerable body of work on skyline evaluation in multidimensional data with totally ordered attribute domains, there are only a few methods that consider attributes with partially ordered domains. Existing work maps each partially ordered domain to a total order and then adapts algorithms for totallyordered domains to solve the problem. Nevertheless these methods either use stronger notions of dominance, which generate false positives, or require expensive dominance checks. In this paper, we propose two new methods, which do not have these drawbacks. The first method uses an appropriate mapping of a partial order to a total order, inspired by the lattice theorem and an off-the-shelf skyline algorithm. The second technique uses an appropriate storage and indexing approach, inspired by column stores, which enables efficient verification of whether a pair of objects are incompatible. We demonstrate that both our methods are up to an order of magnitude more efficient than previous work and scale well with different problem parameters, such as complexity of partial orders. © 2010 VLDB Endowment.-
dc.languageengen_US
dc.publisherVery Large Data Base (VLDB) Endowment Inc.. The Journal's web site is located at http://vldb.org/pvldb/index.html-
dc.relation.ispartofProceedings of the VLDB Endowment-
dc.subjectColumn-store-
dc.subjectFalse positive-
dc.subjectMultidimensional data-
dc.subjectOrdered domains-
dc.subjectPartial order-
dc.titleEfficient skyline evaluation over partially ordered domainsen_US
dc.typeConference_Paperen_US
dc.identifier.emailZhang, S: smzhang@hku.hken_US
dc.identifier.emailMamoulis, N: nikos@cs.hku.hken_US
dc.identifier.emailKao, B: kao@cs.hku.hken_US
dc.identifier.emailCheung, DWL: dcheung@cs.hku.hken_US
dc.description.naturelink_to_OA_fulltext-
dc.identifier.scopuseid_2-s2.0-84859228183-
dc.identifier.hkuros176429en_US
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-84859228183&selection=ref&src=s&origin=recordpage-
dc.identifier.volume3-
dc.identifier.issue1-
dc.identifier.spage1255-
dc.identifier.epage1266-
dc.publisher.placeUnited States-
dc.description.otherThe 36th International Conference on Very Large Data Bases, Singapore, 13-17 September 2010. In Proceedings of the VLDB Endowment, 2010, v. 3 n. 1, p. 1255-1266-
dc.identifier.scopusauthoridZhang, S=55163532300-
dc.identifier.scopusauthoridMamoulis, N=55163690400-
dc.identifier.scopusauthoridCheung, DW=34567902600-
dc.identifier.scopusauthoridKao, B=35221592600-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats