A Simple Framework for the Generalized Nearest Neighbor Problem View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2012

AUTHORS

Tomas Hruz , Marcel Schöngens

ABSTRACT

The problem of finding a nearest neighbor from a set of points in ℝ d to a complex query object has attracted considerable attention due to various applications in computational geometry, bio-informatics, information retrieval, etc. We propose a generic method that solves the problem for various classes of query objects and distance functions in a unified way. Moreover, for linear space requirements the method simplifies the known approach based on ray-shooting in the lower envelope of an arrangement. More... »

PAGES

83-94

References to SciGraph publications

  • 1990-10. Construction of ɛ-nets in DISCRETE & COMPUTATIONAL GEOMETRY
  • 1993-08. On ray shooting in convex polytopes in DISCRETE & COMPUTATIONAL GEOMETRY
  • 2001-03-29. The Discrepancy Method in ALGORITHMS AND COMPUTATION
  • 1989-10. Quasi-optimal range searching in spaces of finite VC-dimension in DISCRETE & COMPUTATIONAL GEOMETRY
  • 1999. Geometric Discrepancy, An Illustrated Guide in NONE
  • 1992-09. Efficient partition trees in DISCRETE & COMPUTATIONAL GEOMETRY
  • 2003-06-18. Computing a Closest Point to a Query Hyperplane in Three and Higher Dimensions in COMPUTATIONAL SCIENCE AND ITS APPLICATIONS — ICCSA 2003
  • 1994-04. On range searching with semialgebraic sets in DISCRETE & COMPUTATIONAL GEOMETRY
  • Book

    TITLE

    Algorithm Theory – SWAT 2012

    ISBN

    978-3-642-31154-3
    978-3-642-31155-0

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/978-3-642-31155-0_8

    DOI

    http://dx.doi.org/10.1007/978-3-642-31155-0_8

    DIMENSIONS

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


    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/0806", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information Systems", 
            "type": "DefinedTerm"
          }, 
          {
            "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"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Swiss Federal Institute of Technology in Zurich", 
              "id": "https://www.grid.ac/institutes/grid.5801.c", 
              "name": [
                "Institute of Theoretical Computer Science, ETH Zurich, Switzerland"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Hruz", 
            "givenName": "Tomas", 
            "id": "sg:person.01271152363.00", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01271152363.00"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Swiss Federal Institute of Technology in Zurich", 
              "id": "https://www.grid.ac/institutes/grid.5801.c", 
              "name": [
                "Institute of Theoretical Computer Science, ETH Zurich, Switzerland"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Sch\u00f6ngens", 
            "givenName": "Marcel", 
            "id": "sg:person.01204623653.80", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01204623653.80"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/3-540-44842-x_80", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1009644454", 
              "https://doi.org/10.1007/3-540-44842-x_80"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-44842-x_80", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1009644454", 
              "https://doi.org/10.1007/3-540-44842-x_80"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02574015", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1010441172", 
              "https://doi.org/10.1007/bf02574015"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02574015", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1010441172", 
              "https://doi.org/10.1007/bf02574015"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02573975", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1011212294", 
              "https://doi.org/10.1007/bf02573975"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02573975", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1011212294", 
              "https://doi.org/10.1007/bf02573975"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02187743", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1013827270", 
              "https://doi.org/10.1007/bf02187743"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02187743", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1013827270", 
              "https://doi.org/10.1007/bf02187743"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0167-8655(03)00018-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014130052"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02293051", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1017452878", 
              "https://doi.org/10.1007/bf02293051"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02293051", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1017452878", 
              "https://doi.org/10.1007/bf02293051"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02187804", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1018950291", 
              "https://doi.org/10.1007/bf02187804"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02187804", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1018950291", 
              "https://doi.org/10.1007/bf02187804"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/2157.322410", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1024042911"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-03942-3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1036718598", 
              "https://doi.org/10.1007/978-3-642-03942-3"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-03942-3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1036718598", 
              "https://doi.org/10.1007/978-3-642-03942-3"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-49381-6_1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1037982226", 
              "https://doi.org/10.1007/3-540-49381-6_1"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-49381-6_1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1037982226", 
              "https://doi.org/10.1007/3-540-49381-6_1"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/10515.10522", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1038514923"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0167-8655(98)00080-4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1042179147"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/sfcs.1983.22", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1086205171"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2012", 
        "datePublishedReg": "2012-01-01", 
        "description": "The problem of finding a nearest neighbor from a set of points in \u211d d to a complex query object has attracted considerable attention due to various applications in computational geometry, bio-informatics, information retrieval, etc. We propose a generic method that solves the problem for various classes of query objects and distance functions in a unified way. Moreover, for linear space requirements the method simplifies the known approach based on ray-shooting in the lower envelope of an arrangement.", 
        "editor": [
          {
            "familyName": "Fomin", 
            "givenName": "Fedor V.", 
            "type": "Person"
          }, 
          {
            "familyName": "Kaski", 
            "givenName": "Petteri", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/978-3-642-31155-0_8", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": {
          "isbn": [
            "978-3-642-31154-3", 
            "978-3-642-31155-0"
          ], 
          "name": "Algorithm Theory \u2013 SWAT 2012", 
          "type": "Book"
        }, 
        "name": "A Simple Framework for the Generalized Nearest Neighbor Problem", 
        "pagination": "83-94", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/978-3-642-31155-0_8"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "d16dcb827762db620898c2361a57d7f9d7f99ab2f1fc1770aab3ef677e81423a"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1043966764"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/978-3-642-31155-0_8", 
          "https://app.dimensions.ai/details/publication/pub.1043966764"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-15T22:00", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8693_00000270.jsonl", 
        "type": "Chapter", 
        "url": "http://link.springer.com/10.1007/978-3-642-31155-0_8"
      }
    ]
     

    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/978-3-642-31155-0_8'

    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/978-3-642-31155-0_8'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-31155-0_8'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-31155-0_8'


     

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

    124 TRIPLES      23 PREDICATES      40 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/978-3-642-31155-0_8 schema:about anzsrc-for:08
    2 anzsrc-for:0806
    3 schema:author N7abf6d6ff6fb4af0a976561e8543de0a
    4 schema:citation sg:pub.10.1007/3-540-44842-x_80
    5 sg:pub.10.1007/3-540-49381-6_1
    6 sg:pub.10.1007/978-3-642-03942-3
    7 sg:pub.10.1007/bf02187743
    8 sg:pub.10.1007/bf02187804
    9 sg:pub.10.1007/bf02293051
    10 sg:pub.10.1007/bf02573975
    11 sg:pub.10.1007/bf02574015
    12 https://doi.org/10.1016/s0167-8655(03)00018-7
    13 https://doi.org/10.1016/s0167-8655(98)00080-4
    14 https://doi.org/10.1109/sfcs.1983.22
    15 https://doi.org/10.1145/10515.10522
    16 https://doi.org/10.1145/2157.322410
    17 schema:datePublished 2012
    18 schema:datePublishedReg 2012-01-01
    19 schema:description The problem of finding a nearest neighbor from a set of points in ℝ d to a complex query object has attracted considerable attention due to various applications in computational geometry, bio-informatics, information retrieval, etc. We propose a generic method that solves the problem for various classes of query objects and distance functions in a unified way. Moreover, for linear space requirements the method simplifies the known approach based on ray-shooting in the lower envelope of an arrangement.
    20 schema:editor Nccd731599d274bfc91b7009ec8cd6df8
    21 schema:genre chapter
    22 schema:inLanguage en
    23 schema:isAccessibleForFree true
    24 schema:isPartOf N3db516df6f804a3fa1d9944b4de015c6
    25 schema:name A Simple Framework for the Generalized Nearest Neighbor Problem
    26 schema:pagination 83-94
    27 schema:productId N12947edd55a14a66aa0a4973bd05c32c
    28 N4e4cae19e8b64abf8bf15b4f61b9f32a
    29 N75510636282a44baae23034c11ab65d4
    30 schema:publisher Nf0b3619e485f4a6bae9dea05008db835
    31 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043966764
    32 https://doi.org/10.1007/978-3-642-31155-0_8
    33 schema:sdDatePublished 2019-04-15T22:00
    34 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    35 schema:sdPublisher Ncd0abc5457024a1984eb35eaa786e10f
    36 schema:url http://link.springer.com/10.1007/978-3-642-31155-0_8
    37 sgo:license sg:explorer/license/
    38 sgo:sdDataset chapters
    39 rdf:type schema:Chapter
    40 N12947edd55a14a66aa0a4973bd05c32c schema:name dimensions_id
    41 schema:value pub.1043966764
    42 rdf:type schema:PropertyValue
    43 N3db516df6f804a3fa1d9944b4de015c6 schema:isbn 978-3-642-31154-3
    44 978-3-642-31155-0
    45 schema:name Algorithm Theory – SWAT 2012
    46 rdf:type schema:Book
    47 N4e4cae19e8b64abf8bf15b4f61b9f32a schema:name doi
    48 schema:value 10.1007/978-3-642-31155-0_8
    49 rdf:type schema:PropertyValue
    50 N6d207bb41ead4a85a1cf482ff6308239 rdf:first sg:person.01204623653.80
    51 rdf:rest rdf:nil
    52 N75510636282a44baae23034c11ab65d4 schema:name readcube_id
    53 schema:value d16dcb827762db620898c2361a57d7f9d7f99ab2f1fc1770aab3ef677e81423a
    54 rdf:type schema:PropertyValue
    55 N7abf6d6ff6fb4af0a976561e8543de0a rdf:first sg:person.01271152363.00
    56 rdf:rest N6d207bb41ead4a85a1cf482ff6308239
    57 N7f9edb94239d4434bb8d48f8f827a650 rdf:first N8f7a962b6bdf4573bd1cbe048d15e28d
    58 rdf:rest rdf:nil
    59 N8f7a962b6bdf4573bd1cbe048d15e28d schema:familyName Kaski
    60 schema:givenName Petteri
    61 rdf:type schema:Person
    62 Nccd731599d274bfc91b7009ec8cd6df8 rdf:first Need5251175a242998b542f5664ffe378
    63 rdf:rest N7f9edb94239d4434bb8d48f8f827a650
    64 Ncd0abc5457024a1984eb35eaa786e10f schema:name Springer Nature - SN SciGraph project
    65 rdf:type schema:Organization
    66 Need5251175a242998b542f5664ffe378 schema:familyName Fomin
    67 schema:givenName Fedor V.
    68 rdf:type schema:Person
    69 Nf0b3619e485f4a6bae9dea05008db835 schema:location Berlin, Heidelberg
    70 schema:name Springer Berlin Heidelberg
    71 rdf:type schema:Organisation
    72 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    73 schema:name Information and Computing Sciences
    74 rdf:type schema:DefinedTerm
    75 anzsrc-for:0806 schema:inDefinedTermSet anzsrc-for:
    76 schema:name Information Systems
    77 rdf:type schema:DefinedTerm
    78 sg:person.01204623653.80 schema:affiliation https://www.grid.ac/institutes/grid.5801.c
    79 schema:familyName Schöngens
    80 schema:givenName Marcel
    81 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01204623653.80
    82 rdf:type schema:Person
    83 sg:person.01271152363.00 schema:affiliation https://www.grid.ac/institutes/grid.5801.c
    84 schema:familyName Hruz
    85 schema:givenName Tomas
    86 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01271152363.00
    87 rdf:type schema:Person
    88 sg:pub.10.1007/3-540-44842-x_80 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009644454
    89 https://doi.org/10.1007/3-540-44842-x_80
    90 rdf:type schema:CreativeWork
    91 sg:pub.10.1007/3-540-49381-6_1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037982226
    92 https://doi.org/10.1007/3-540-49381-6_1
    93 rdf:type schema:CreativeWork
    94 sg:pub.10.1007/978-3-642-03942-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036718598
    95 https://doi.org/10.1007/978-3-642-03942-3
    96 rdf:type schema:CreativeWork
    97 sg:pub.10.1007/bf02187743 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013827270
    98 https://doi.org/10.1007/bf02187743
    99 rdf:type schema:CreativeWork
    100 sg:pub.10.1007/bf02187804 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018950291
    101 https://doi.org/10.1007/bf02187804
    102 rdf:type schema:CreativeWork
    103 sg:pub.10.1007/bf02293051 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017452878
    104 https://doi.org/10.1007/bf02293051
    105 rdf:type schema:CreativeWork
    106 sg:pub.10.1007/bf02573975 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011212294
    107 https://doi.org/10.1007/bf02573975
    108 rdf:type schema:CreativeWork
    109 sg:pub.10.1007/bf02574015 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010441172
    110 https://doi.org/10.1007/bf02574015
    111 rdf:type schema:CreativeWork
    112 https://doi.org/10.1016/s0167-8655(03)00018-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014130052
    113 rdf:type schema:CreativeWork
    114 https://doi.org/10.1016/s0167-8655(98)00080-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042179147
    115 rdf:type schema:CreativeWork
    116 https://doi.org/10.1109/sfcs.1983.22 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086205171
    117 rdf:type schema:CreativeWork
    118 https://doi.org/10.1145/10515.10522 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038514923
    119 rdf:type schema:CreativeWork
    120 https://doi.org/10.1145/2157.322410 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024042911
    121 rdf:type schema:CreativeWork
    122 https://www.grid.ac/institutes/grid.5801.c schema:alternateName Swiss Federal Institute of Technology in Zurich
    123 schema:name Institute of Theoretical Computer Science, ETH Zurich, Switzerland
    124 rdf:type schema:Organization
     




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


    ...