Restricting skyline sizes using weak Pareto dominance View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2007-05-11

AUTHORS

Wolf Tilo Balke, Ulrich Güntzer, Wolf Siberski

ABSTRACT

Skyline queries have recently received a lot of attention due to their intuitive query formulation: users can state preferences with respect to several attributes. Unlike numerical or score-based preferences, preferences over discrete value domains do not show an inherent total order, but have to rely on partial orders as stated by the user. In such orders typically many object values are incomparable, increasing the size of skyline sets significantly, and making their computation expensive. In this paper we explore how to enable interactive tasks like query refinement or relevance feedback by providing interesting subsets of the full Pareto skyline, which give users a good overview over the skyline. To be practical these subsets have to be small, efficient to compute, suitable for higher numbers of query predicates, and representative. The key to improved performance and reduced result set sizes is the relaxation of Pareto semantics to the concept of weak Pareto dominance. We argue that this relaxation yields intuitive results and show how it opens up the use of efficient and scalable query processing algorithms. We first derive the complete skyline subset given by weak Pareto dominance called ‘restricted skyline’ and then considering the individual performance of objects limit this further to a subset called ‘focused skyline’. Assessing the practical impact our experiments show that our approach indeed leads to lean result set sizes and outperforms Pareto skyline computations by up to two orders of magnitude. More... »

PAGES

165-178

References to SciGraph publications

  • 2002-03-14. Querying with Intrinsic Preferences in ADVANCES IN DATABASE TECHNOLOGY — EDBT 2002
  • 2004. Efficient Distributed Skylining for Web Information Systems in ADVANCES IN DATABASE TECHNOLOGY - EDBT 2004
  • 2005. Approaching the Efficient Frontier: Cooperative Database Retrieval Using High-Dimensional Skylines in DATABASE SYSTEMS FOR ADVANCED APPLICATIONS
  • 2004. Approximately Dominating Representatives in DATABASE THEORY - ICDT 2005
  • 2005. In-Route Skyline Querying for Location-Based Services in WEB AND WIRELESS GEOGRAPHICAL INFORMATION SYSTEMS
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00450-007-0025-1

    DOI

    http://dx.doi.org/10.1007/s00450-007-0025-1

    DIMENSIONS

    https://app.dimensions.ai/details/publication/pub.1011782325


    Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
    Incoming Citations Browse incoming citations for this publication using opencitations.net

    JSON-LD is the canonical representation for SciGraph data.

    TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

    [
      {
        "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
        "about": [
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information and Computing Sciences", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0806", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information Systems", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "L3S Research Center, Appelstr. 4, 30167, Hannover, Germany", 
              "id": "http://www.grid.ac/institutes/grid.507815.e", 
              "name": [
                "L3S Research Center, Appelstr. 4, 30167, Hannover, Germany"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Balke", 
            "givenName": "Wolf Tilo", 
            "id": "sg:person.014313642615.12", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014313642615.12"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Institut f\u00fcr Informatik, Universit\u00e4t T\u00fcbingen, 72076, T\u00fcbingen, Germany", 
              "id": "http://www.grid.ac/institutes/grid.10392.39", 
              "name": [
                "Institut f\u00fcr Informatik, Universit\u00e4t T\u00fcbingen, 72076, T\u00fcbingen, Germany"
              ], 
              "type": "Organization"
            }, 
            "familyName": "G\u00fcntzer", 
            "givenName": "Ulrich", 
            "id": "sg:person.013324511711.75", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013324511711.75"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "L3S Research Center, Appelstr. 4, 30167, Hannover, Germany", 
              "id": "http://www.grid.ac/institutes/grid.507815.e", 
              "name": [
                "L3S Research Center, Appelstr. 4, 30167, Hannover, Germany"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Siberski", 
            "givenName": "Wolf", 
            "id": "sg:person.010614672714.11", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010614672714.11"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/3-540-45876-x_5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1034128210", 
              "https://doi.org/10.1007/3-540-45876-x_5"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-24741-8_16", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1005929905", 
              "https://doi.org/10.1007/978-3-540-24741-8_16"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11408079_37", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006882900", 
              "https://doi.org/10.1007/11408079_37"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-30570-5_14", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1029456772", 
              "https://doi.org/10.1007/978-3-540-30570-5_14"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11427865_10", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1042684883", 
              "https://doi.org/10.1007/11427865_10"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2007-05-11", 
        "datePublishedReg": "2007-05-11", 
        "description": "Skyline queries have recently received a\u00a0lot of attention due to their intuitive query formulation:\n users can state preferences with respect to several attributes. Unlike numerical or score-based preferences,\n preferences over discrete value domains do not show an inherent total order, but have to rely on partial\n orders as stated by the user. In such orders typically many object values are incomparable, increasing\n the size of skyline sets significantly, and making their computation expensive. In this paper we explore\n how to enable interactive tasks like query refinement or relevance feedback by providing interesting subsets\n of the full Pareto skyline, which give users a\u00a0good overview over the skyline. To be practical these\n subsets have to be small, efficient to compute, suitable for higher numbers of query predicates, and representative.\n The key to improved performance and reduced result set sizes is the relaxation of Pareto semantics to the\n concept of weak Pareto dominance. We argue that this relaxation yields intuitive results and show how it\n opens up the use of efficient and scalable query processing algorithms. We first derive the complete skyline\n subset given by weak Pareto dominance called \u2018restricted skyline\u2019 and then considering the individual\n performance of objects limit this further to a\u00a0subset called \u2018focused skyline\u2019. Assessing\n the practical impact our experiments show that our approach indeed leads to lean result set sizes and outperforms\n Pareto skyline computations by up to two orders of magnitude.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/s00450-007-0025-1", 
        "inLanguage": "en", 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1357733", 
            "issn": [
              "2524-8510", 
              "2524-8529"
            ], 
            "name": "SICS Software-Intensive Cyber-Physical Systems", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "3-4", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "21"
          }
        ], 
        "keywords": [
          "Pareto dominance", 
          "intuitive query formulation", 
          "performance of object", 
          "weak Pareto dominance", 
          "query refinement", 
          "skyline queries", 
          "scalable query", 
          "skyline computation", 
          "query predicates", 
          "query formulation", 
          "relevance feedback", 
          "skyline sizes", 
          "skyline set", 
          "interactive tasks", 
          "skyline", 
          "users", 
          "value domain", 
          "queries", 
          "object value", 
          "interesting subset", 
          "set size", 
          "total order", 
          "intuitive results", 
          "practical impact", 
          "good overview", 
          "improved performance", 
          "computation", 
          "Lean results", 
          "semantics", 
          "outperforms", 
          "algorithm", 
          "performance", 
          "predicates", 
          "objects", 
          "task", 
          "order", 
          "key", 
          "set", 
          "subset", 
          "attributes", 
          "feedback", 
          "domain", 
          "concept", 
          "orders of magnitude", 
          "preferences", 
          "such orders", 
          "refinement", 
          "overview", 
          "results", 
          "experiments", 
          "size", 
          "number", 
          "use", 
          "assessing", 
          "attention", 
          "formulation", 
          "higher number", 
          "respect", 
          "impact", 
          "relaxation", 
          "representatives", 
          "values", 
          "magnitude", 
          "individuals", 
          "dominance", 
          "paper", 
          "approach", 
          "score-based preferences", 
          "discrete value domains", 
          "inherent total order", 
          "full Pareto skyline", 
          "Pareto skyline", 
          "reduced result set sizes", 
          "result set sizes", 
          "Pareto semantics", 
          "complete skyline", 
          "focused skyline", 
          "Pareto skyline computations"
        ], 
        "name": "Restricting skyline sizes using weak Pareto dominance", 
        "pagination": "165-178", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1011782325"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00450-007-0025-1"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00450-007-0025-1", 
          "https://app.dimensions.ai/details/publication/pub.1011782325"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2022-01-01T18:17", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20220101/entities/gbq_results/article/article_446.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/s00450-007-0025-1"
      }
    ]
     

    Download the RDF metadata as:  json-ld nt turtle xml License info

    HOW TO GET THIS DATA PROGRAMMATICALLY:

    JSON-LD is a popular format for linked data which is fully compatible with JSON.

    curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/s00450-007-0025-1'

    N-Triples is a line-based linked data format ideal for batch operations.

    curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/s00450-007-0025-1'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00450-007-0025-1'

    RDF/XML is a standard XML format for linked data.

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00450-007-0025-1'


     

    This table displays all metadata directly associated to this object as RDF triples.

    173 TRIPLES      22 PREDICATES      108 URIs      95 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00450-007-0025-1 schema:about anzsrc-for:08
    2 anzsrc-for:0806
    3 schema:author N8d3d1e736fcc49c19c0ea9f9b1ed2081
    4 schema:citation sg:pub.10.1007/11408079_37
    5 sg:pub.10.1007/11427865_10
    6 sg:pub.10.1007/3-540-45876-x_5
    7 sg:pub.10.1007/978-3-540-24741-8_16
    8 sg:pub.10.1007/978-3-540-30570-5_14
    9 schema:datePublished 2007-05-11
    10 schema:datePublishedReg 2007-05-11
    11 schema:description Skyline queries have recently received a lot of attention due to their intuitive query formulation: users can state preferences with respect to several attributes. Unlike numerical or score-based preferences, preferences over discrete value domains do not show an inherent total order, but have to rely on partial orders as stated by the user. In such orders typically many object values are incomparable, increasing the size of skyline sets significantly, and making their computation expensive. In this paper we explore how to enable interactive tasks like query refinement or relevance feedback by providing interesting subsets of the full Pareto skyline, which give users a good overview over the skyline. To be practical these subsets have to be small, efficient to compute, suitable for higher numbers of query predicates, and representative. The key to improved performance and reduced result set sizes is the relaxation of Pareto semantics to the concept of weak Pareto dominance. We argue that this relaxation yields intuitive results and show how it opens up the use of efficient and scalable query processing algorithms. We first derive the complete skyline subset given by weak Pareto dominance called ‘restricted skyline’ and then considering the individual performance of objects limit this further to a subset called ‘focused skyline’. Assessing the practical impact our experiments show that our approach indeed leads to lean result set sizes and outperforms Pareto skyline computations by up to two orders of magnitude.
    12 schema:genre article
    13 schema:inLanguage en
    14 schema:isAccessibleForFree false
    15 schema:isPartOf N153781993ab444cbaa2319766d45f888
    16 Naac2ee97c0874369b2004bc800551035
    17 sg:journal.1357733
    18 schema:keywords Lean results
    19 Pareto dominance
    20 Pareto semantics
    21 Pareto skyline
    22 Pareto skyline computations
    23 algorithm
    24 approach
    25 assessing
    26 attention
    27 attributes
    28 complete skyline
    29 computation
    30 concept
    31 discrete value domains
    32 domain
    33 dominance
    34 experiments
    35 feedback
    36 focused skyline
    37 formulation
    38 full Pareto skyline
    39 good overview
    40 higher number
    41 impact
    42 improved performance
    43 individuals
    44 inherent total order
    45 interactive tasks
    46 interesting subset
    47 intuitive query formulation
    48 intuitive results
    49 key
    50 magnitude
    51 number
    52 object value
    53 objects
    54 order
    55 orders of magnitude
    56 outperforms
    57 overview
    58 paper
    59 performance
    60 performance of object
    61 practical impact
    62 predicates
    63 preferences
    64 queries
    65 query formulation
    66 query predicates
    67 query refinement
    68 reduced result set sizes
    69 refinement
    70 relaxation
    71 relevance feedback
    72 representatives
    73 respect
    74 result set sizes
    75 results
    76 scalable query
    77 score-based preferences
    78 semantics
    79 set
    80 set size
    81 size
    82 skyline
    83 skyline computation
    84 skyline queries
    85 skyline set
    86 skyline sizes
    87 subset
    88 such orders
    89 task
    90 total order
    91 use
    92 users
    93 value domain
    94 values
    95 weak Pareto dominance
    96 schema:name Restricting skyline sizes using weak Pareto dominance
    97 schema:pagination 165-178
    98 schema:productId N8a61bd22cb6b48409356866c0a8f69cf
    99 Na1fa225de2a74abfa2ebc260201b4255
    100 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011782325
    101 https://doi.org/10.1007/s00450-007-0025-1
    102 schema:sdDatePublished 2022-01-01T18:17
    103 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    104 schema:sdPublisher N737bc4cb131043c796d6ac62fd2c7b6a
    105 schema:url https://doi.org/10.1007/s00450-007-0025-1
    106 sgo:license sg:explorer/license/
    107 sgo:sdDataset articles
    108 rdf:type schema:ScholarlyArticle
    109 N025d9b9ba2d94ed0975eb6e64c77232c rdf:first sg:person.010614672714.11
    110 rdf:rest rdf:nil
    111 N153781993ab444cbaa2319766d45f888 schema:issueNumber 3-4
    112 rdf:type schema:PublicationIssue
    113 N56f08cec080241ba8a9890b9e785de02 rdf:first sg:person.013324511711.75
    114 rdf:rest N025d9b9ba2d94ed0975eb6e64c77232c
    115 N737bc4cb131043c796d6ac62fd2c7b6a schema:name Springer Nature - SN SciGraph project
    116 rdf:type schema:Organization
    117 N8a61bd22cb6b48409356866c0a8f69cf schema:name dimensions_id
    118 schema:value pub.1011782325
    119 rdf:type schema:PropertyValue
    120 N8d3d1e736fcc49c19c0ea9f9b1ed2081 rdf:first sg:person.014313642615.12
    121 rdf:rest N56f08cec080241ba8a9890b9e785de02
    122 Na1fa225de2a74abfa2ebc260201b4255 schema:name doi
    123 schema:value 10.1007/s00450-007-0025-1
    124 rdf:type schema:PropertyValue
    125 Naac2ee97c0874369b2004bc800551035 schema:volumeNumber 21
    126 rdf:type schema:PublicationVolume
    127 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    128 schema:name Information and Computing Sciences
    129 rdf:type schema:DefinedTerm
    130 anzsrc-for:0806 schema:inDefinedTermSet anzsrc-for:
    131 schema:name Information Systems
    132 rdf:type schema:DefinedTerm
    133 sg:journal.1357733 schema:issn 2524-8510
    134 2524-8529
    135 schema:name SICS Software-Intensive Cyber-Physical Systems
    136 schema:publisher Springer Nature
    137 rdf:type schema:Periodical
    138 sg:person.010614672714.11 schema:affiliation grid-institutes:grid.507815.e
    139 schema:familyName Siberski
    140 schema:givenName Wolf
    141 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010614672714.11
    142 rdf:type schema:Person
    143 sg:person.013324511711.75 schema:affiliation grid-institutes:grid.10392.39
    144 schema:familyName Güntzer
    145 schema:givenName Ulrich
    146 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013324511711.75
    147 rdf:type schema:Person
    148 sg:person.014313642615.12 schema:affiliation grid-institutes:grid.507815.e
    149 schema:familyName Balke
    150 schema:givenName Wolf Tilo
    151 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014313642615.12
    152 rdf:type schema:Person
    153 sg:pub.10.1007/11408079_37 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006882900
    154 https://doi.org/10.1007/11408079_37
    155 rdf:type schema:CreativeWork
    156 sg:pub.10.1007/11427865_10 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042684883
    157 https://doi.org/10.1007/11427865_10
    158 rdf:type schema:CreativeWork
    159 sg:pub.10.1007/3-540-45876-x_5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034128210
    160 https://doi.org/10.1007/3-540-45876-x_5
    161 rdf:type schema:CreativeWork
    162 sg:pub.10.1007/978-3-540-24741-8_16 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005929905
    163 https://doi.org/10.1007/978-3-540-24741-8_16
    164 rdf:type schema:CreativeWork
    165 sg:pub.10.1007/978-3-540-30570-5_14 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029456772
    166 https://doi.org/10.1007/978-3-540-30570-5_14
    167 rdf:type schema:CreativeWork
    168 grid-institutes:grid.10392.39 schema:alternateName Institut für Informatik, Universität Tübingen, 72076, Tübingen, Germany
    169 schema:name Institut für Informatik, Universität Tübingen, 72076, Tübingen, Germany
    170 rdf:type schema:Organization
    171 grid-institutes:grid.507815.e schema:alternateName L3S Research Center, Appelstr. 4, 30167, Hannover, Germany
    172 schema:name L3S Research Center, Appelstr. 4, 30167, Hannover, Germany
    173 rdf:type schema:Organization
     




    Preview window. Press ESC to close (or click here)


    ...