Aggregate nearest neighbor queries in uncertain graphs View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2013-02-14

AUTHORS

Zhang Liu, Chaokun Wang, Jianmin Wang

ABSTRACT

Most recently, uncertain graph data begin attracting significant interests of database research community, because uncertainty is the intrinsic property of the real-world and data are more suitable to be modeled as graphs in numbers of applications, e.g. social network analysis, PPI networks in biology, and road network monitoring. Meanwhile, as one of the basic query operators, aggregate nearest neighbor (ANN) query retrieves a data entity whose aggregate distance, e.g. sum, max, to the given query data entities is smaller than those of other data entities in a database. ANN query on both certain graph data and high dimensional data has been well studied by previous work. However, existing ANN query processing approaches cannot handle the situation of uncertain graphs, because topological structures of an uncertain graph may vary in different possible worlds. Motivated by this, we propose the aggregate nearest neighbor query in uncertain graphs (UG-ANN) in this paper. First of all, we give the formal definition of UG-ANN query and the basic UG-ANN query algorithm. After that, to improve the efficiency of UG-ANN query processing, we develop two kinds of pruning approaches, i.e. structural pruning and instance pruning. The structural pruning takes advantages the monotonicity of the aggregate distance to derive the upper and lower bounds of the aggregate distance for reducing the graph size. Whereas, the instance pruning decreases the number of possible worlds to be checked in the searching tree. Comprehensive experimental results on real-world data sets demonstrate that the proposed method significantly improves the efficiency of the UG-ANN query processing. More... »

PAGES

161-188

References to SciGraph publications

  • 2007-01-01. Probabilistic Nearest-Neighbor Query on Uncertain Objects in ADVANCES IN DATABASES: CONCEPTS, SYSTEMS AND APPLICATIONS
  • 1999-06-25. Capturing the Uncertainty of Moving-Object Representations in ADVANCES IN SPATIAL DATABASES
  • 1959-12. A note on two problems in connexion with graphs in NUMERISCHE MATHEMATIK
  • 2008. Graph Theory in NONE
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s11280-012-0200-6

    DOI

    http://dx.doi.org/10.1007/s11280-012-0200-6

    DIMENSIONS

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


    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": "Department of Computer Science and Technology, Tsinghua University, 100084, Beijing, People\u2019s Republic of China", 
              "id": "http://www.grid.ac/institutes/grid.12527.33", 
              "name": [
                "Department of Computer Science and Technology, Tsinghua University, 100084, Beijing, People\u2019s Republic of China"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Liu", 
            "givenName": "Zhang", 
            "id": "sg:person.016566115360.45", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016566115360.45"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "School of Software, Tsinghua University, 100084, Beijing, People\u2019s Republic of China", 
              "id": "http://www.grid.ac/institutes/grid.12527.33", 
              "name": [
                "School of Software, Tsinghua University, 100084, Beijing, People\u2019s Republic of China"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Wang", 
            "givenName": "Chaokun", 
            "id": "sg:person.011533665437.99", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011533665437.99"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "School of Software, Tsinghua University, 100084, Beijing, People\u2019s Republic of China", 
              "id": "http://www.grid.ac/institutes/grid.12527.33", 
              "name": [
                "School of Software, Tsinghua University, 100084, Beijing, People\u2019s Republic of China"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Wang", 
            "givenName": "Jianmin", 
            "id": "sg:person.012303351315.43", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012303351315.43"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/3-540-48482-5_9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051670739", 
              "https://doi.org/10.1007/3-540-48482-5_9"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-84628-970-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1109706182", 
              "https://doi.org/10.1007/978-1-84628-970-5"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01386390", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1041716633", 
              "https://doi.org/10.1007/bf01386390"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-71703-4_30", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1019892467", 
              "https://doi.org/10.1007/978-3-540-71703-4_30"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2013-02-14", 
        "datePublishedReg": "2013-02-14", 
        "description": "Most recently, uncertain graph data begin attracting significant interests of database research community, because uncertainty is the intrinsic property of the real-world and data are more suitable to be modeled as graphs in numbers of applications, e.g. social network analysis, PPI networks in biology, and road network monitoring. Meanwhile, as one of the basic query operators, aggregate nearest neighbor (ANN) query retrieves a data entity whose aggregate distance, e.g.\u00a0sum, max, to the given query data entities is smaller than those of other data entities in a database. ANN query on both certain graph data and high dimensional data has been well studied by previous work. However, existing ANN query processing approaches cannot handle the situation of uncertain graphs, because topological structures of an uncertain graph may vary in different possible worlds. Motivated by this, we propose the aggregate nearest neighbor query in uncertain graphs (UG-ANN) in this paper. First of all, we give the formal definition of UG-ANN query and the basic UG-ANN query algorithm. After that, to improve the efficiency of UG-ANN query processing, we develop two kinds of pruning approaches, i.e.\u00a0structural pruning and instance pruning. The structural pruning takes advantages the monotonicity of the aggregate distance to derive the upper and lower bounds of the aggregate distance for reducing the graph size. Whereas, the instance pruning decreases the number of possible worlds to be checked in the searching tree. Comprehensive experimental results on real-world data sets demonstrate that the proposed method significantly improves the efficiency of the UG-ANN query processing.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/s11280-012-0200-6", 
        "inLanguage": "en", 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1136663", 
            "issn": [
              "1386-145X", 
              "1573-1413"
            ], 
            "name": "World Wide Web", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "1", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "17"
          }
        ], 
        "keywords": [
          "aggregate nearest neighbor queries", 
          "nearest neighbor queries", 
          "uncertain graphs", 
          "data entities", 
          "neighbor queries", 
          "aggregate distance", 
          "query processing", 
          "graph data", 
          "instance pruning", 
          "structural pruning", 
          "real-world data sets", 
          "query processing approach", 
          "uncertain graph data", 
          "database research community", 
          "high dimensional data", 
          "Comprehensive experimental results", 
          "road network monitoring", 
          "query operators", 
          "ANN query", 
          "social network analysis", 
          "query algorithm", 
          "network monitoring", 
          "graph size", 
          "dimensional data", 
          "queries", 
          "number of applications", 
          "searching tree", 
          "formal definition", 
          "research community", 
          "processing approach", 
          "graph", 
          "possible worlds", 
          "data sets", 
          "pruning", 
          "topological structure", 
          "experimental results", 
          "network analysis", 
          "previous work", 
          "lower bounds", 
          "processing", 
          "algorithm", 
          "different possible worlds", 
          "entities", 
          "PPI network", 
          "network", 
          "significant interest", 
          "database", 
          "efficiency", 
          "set", 
          "data", 
          "operators", 
          "applications", 
          "bounds", 
          "distance", 
          "world", 
          "advantages", 
          "trees", 
          "number", 
          "kind", 
          "monitoring", 
          "work", 
          "definition", 
          "situation", 
          "uncertainty", 
          "method", 
          "monotonicity", 
          "interest", 
          "community", 
          "sum", 
          "results", 
          "intrinsic properties", 
          "max", 
          "size", 
          "analysis", 
          "structure", 
          "biology", 
          "properties", 
          "approach", 
          "paper", 
          "basic query operators", 
          "query data entities", 
          "certain graph data", 
          "ANN query processing approaches", 
          "UG-ANN query", 
          "basic UG-ANN query algorithm", 
          "UG-ANN query algorithm", 
          "UG-ANN query processing"
        ], 
        "name": "Aggregate nearest neighbor queries in uncertain graphs", 
        "pagination": "161-188", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1053659943"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s11280-012-0200-6"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s11280-012-0200-6", 
          "https://app.dimensions.ai/details/publication/pub.1053659943"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2022-01-01T18:30", 
        "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_601.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/s11280-012-0200-6"
      }
    ]
     

    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/s11280-012-0200-6'

    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/s11280-012-0200-6'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s11280-012-0200-6'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s11280-012-0200-6'


     

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

    177 TRIPLES      22 PREDICATES      116 URIs      104 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s11280-012-0200-6 schema:about anzsrc-for:08
    2 anzsrc-for:0806
    3 schema:author Nc9f1f25cdd774511af7461cd7bf12ef5
    4 schema:citation sg:pub.10.1007/3-540-48482-5_9
    5 sg:pub.10.1007/978-1-84628-970-5
    6 sg:pub.10.1007/978-3-540-71703-4_30
    7 sg:pub.10.1007/bf01386390
    8 schema:datePublished 2013-02-14
    9 schema:datePublishedReg 2013-02-14
    10 schema:description Most recently, uncertain graph data begin attracting significant interests of database research community, because uncertainty is the intrinsic property of the real-world and data are more suitable to be modeled as graphs in numbers of applications, e.g. social network analysis, PPI networks in biology, and road network monitoring. Meanwhile, as one of the basic query operators, aggregate nearest neighbor (ANN) query retrieves a data entity whose aggregate distance, e.g. sum, max, to the given query data entities is smaller than those of other data entities in a database. ANN query on both certain graph data and high dimensional data has been well studied by previous work. However, existing ANN query processing approaches cannot handle the situation of uncertain graphs, because topological structures of an uncertain graph may vary in different possible worlds. Motivated by this, we propose the aggregate nearest neighbor query in uncertain graphs (UG-ANN) in this paper. First of all, we give the formal definition of UG-ANN query and the basic UG-ANN query algorithm. After that, to improve the efficiency of UG-ANN query processing, we develop two kinds of pruning approaches, i.e. structural pruning and instance pruning. The structural pruning takes advantages the monotonicity of the aggregate distance to derive the upper and lower bounds of the aggregate distance for reducing the graph size. Whereas, the instance pruning decreases the number of possible worlds to be checked in the searching tree. Comprehensive experimental results on real-world data sets demonstrate that the proposed method significantly improves the efficiency of the UG-ANN query processing.
    11 schema:genre article
    12 schema:inLanguage en
    13 schema:isAccessibleForFree false
    14 schema:isPartOf Nce4fad960cde4b99b5c6e234a6baca5c
    15 Nf278ce56387a4ef3a5957b929f76e158
    16 sg:journal.1136663
    17 schema:keywords ANN query
    18 ANN query processing approaches
    19 Comprehensive experimental results
    20 PPI network
    21 UG-ANN query
    22 UG-ANN query algorithm
    23 UG-ANN query processing
    24 advantages
    25 aggregate distance
    26 aggregate nearest neighbor queries
    27 algorithm
    28 analysis
    29 applications
    30 approach
    31 basic UG-ANN query algorithm
    32 basic query operators
    33 biology
    34 bounds
    35 certain graph data
    36 community
    37 data
    38 data entities
    39 data sets
    40 database
    41 database research community
    42 definition
    43 different possible worlds
    44 dimensional data
    45 distance
    46 efficiency
    47 entities
    48 experimental results
    49 formal definition
    50 graph
    51 graph data
    52 graph size
    53 high dimensional data
    54 instance pruning
    55 interest
    56 intrinsic properties
    57 kind
    58 lower bounds
    59 max
    60 method
    61 monitoring
    62 monotonicity
    63 nearest neighbor queries
    64 neighbor queries
    65 network
    66 network analysis
    67 network monitoring
    68 number
    69 number of applications
    70 operators
    71 paper
    72 possible worlds
    73 previous work
    74 processing
    75 processing approach
    76 properties
    77 pruning
    78 queries
    79 query algorithm
    80 query data entities
    81 query operators
    82 query processing
    83 query processing approach
    84 real-world data sets
    85 research community
    86 results
    87 road network monitoring
    88 searching tree
    89 set
    90 significant interest
    91 situation
    92 size
    93 social network analysis
    94 structural pruning
    95 structure
    96 sum
    97 topological structure
    98 trees
    99 uncertain graph data
    100 uncertain graphs
    101 uncertainty
    102 work
    103 world
    104 schema:name Aggregate nearest neighbor queries in uncertain graphs
    105 schema:pagination 161-188
    106 schema:productId N473cfe9042d94012a0afde733d4a7c97
    107 Nec4519fb006d46bb9c1a921fcf47c975
    108 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053659943
    109 https://doi.org/10.1007/s11280-012-0200-6
    110 schema:sdDatePublished 2022-01-01T18:30
    111 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    112 schema:sdPublisher N5bd3c25de67f4a8f8f5dc2847a80a18f
    113 schema:url https://doi.org/10.1007/s11280-012-0200-6
    114 sgo:license sg:explorer/license/
    115 sgo:sdDataset articles
    116 rdf:type schema:ScholarlyArticle
    117 N473cfe9042d94012a0afde733d4a7c97 schema:name dimensions_id
    118 schema:value pub.1053659943
    119 rdf:type schema:PropertyValue
    120 N5bd3c25de67f4a8f8f5dc2847a80a18f schema:name Springer Nature - SN SciGraph project
    121 rdf:type schema:Organization
    122 N724627b501f74193b2f13eb82d46058a rdf:first sg:person.011533665437.99
    123 rdf:rest Naa53726db7ff4347a66a0d4db58dee76
    124 Naa53726db7ff4347a66a0d4db58dee76 rdf:first sg:person.012303351315.43
    125 rdf:rest rdf:nil
    126 Nc9f1f25cdd774511af7461cd7bf12ef5 rdf:first sg:person.016566115360.45
    127 rdf:rest N724627b501f74193b2f13eb82d46058a
    128 Nce4fad960cde4b99b5c6e234a6baca5c schema:volumeNumber 17
    129 rdf:type schema:PublicationVolume
    130 Nec4519fb006d46bb9c1a921fcf47c975 schema:name doi
    131 schema:value 10.1007/s11280-012-0200-6
    132 rdf:type schema:PropertyValue
    133 Nf278ce56387a4ef3a5957b929f76e158 schema:issueNumber 1
    134 rdf:type schema:PublicationIssue
    135 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    136 schema:name Information and Computing Sciences
    137 rdf:type schema:DefinedTerm
    138 anzsrc-for:0806 schema:inDefinedTermSet anzsrc-for:
    139 schema:name Information Systems
    140 rdf:type schema:DefinedTerm
    141 sg:journal.1136663 schema:issn 1386-145X
    142 1573-1413
    143 schema:name World Wide Web
    144 schema:publisher Springer Nature
    145 rdf:type schema:Periodical
    146 sg:person.011533665437.99 schema:affiliation grid-institutes:grid.12527.33
    147 schema:familyName Wang
    148 schema:givenName Chaokun
    149 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011533665437.99
    150 rdf:type schema:Person
    151 sg:person.012303351315.43 schema:affiliation grid-institutes:grid.12527.33
    152 schema:familyName Wang
    153 schema:givenName Jianmin
    154 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012303351315.43
    155 rdf:type schema:Person
    156 sg:person.016566115360.45 schema:affiliation grid-institutes:grid.12527.33
    157 schema:familyName Liu
    158 schema:givenName Zhang
    159 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016566115360.45
    160 rdf:type schema:Person
    161 sg:pub.10.1007/3-540-48482-5_9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051670739
    162 https://doi.org/10.1007/3-540-48482-5_9
    163 rdf:type schema:CreativeWork
    164 sg:pub.10.1007/978-1-84628-970-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1109706182
    165 https://doi.org/10.1007/978-1-84628-970-5
    166 rdf:type schema:CreativeWork
    167 sg:pub.10.1007/978-3-540-71703-4_30 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019892467
    168 https://doi.org/10.1007/978-3-540-71703-4_30
    169 rdf:type schema:CreativeWork
    170 sg:pub.10.1007/bf01386390 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041716633
    171 https://doi.org/10.1007/bf01386390
    172 rdf:type schema:CreativeWork
    173 grid-institutes:grid.12527.33 schema:alternateName Department of Computer Science and Technology, Tsinghua University, 100084, Beijing, People’s Republic of China
    174 School of Software, Tsinghua University, 100084, Beijing, People’s Republic of China
    175 schema:name Department of Computer Science and Technology, Tsinghua University, 100084, Beijing, People’s Republic of China
    176 School of Software, Tsinghua University, 100084, Beijing, People’s Republic of China
    177 rdf:type schema:Organization
     




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


    ...