Partially Specified Nearest Neighbor Search View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2012

AUTHORS

Tomas Hruz , Marcel Schöngens

ABSTRACT

We study the Partial Nearest Neighbor Problem that consists in preprocessing n points \(\mathcal{D}\) from d-dimensional metric space such that the following query can be answered efficiently: Given a query vector Q ∈ ℝ d and an axes-aligned query subspace represented by S ∈ {0,1} d , report a point \(P \in \mathcal{D}\) with d S (Q,P) ≤ d S (Q,P′) for all \(P' \in \mathcal{D}\), where d S (Q,P) is the distance between Q and P in the subspace S. This problem is related to similarity search between feature vectors w.r.t. a subset of features. Thus, the problem is of great practical importance in bioinformatics, image recognition, etc., however, due to exponentially many subspaces, each changing distances significantly, the problem has a considerable complexity. We present the first exact algorithms for ℓ2- and ℓ ∞ -metrics with linear space and sub-linear worst-case query time. We also give a simple approximation algorithm, and show experimentally that our approach performs well on real world data. More... »

PAGES

372-383

References to SciGraph publications

Book

TITLE

Computing and Combinatorics

ISBN

978-3-642-32240-2
978-3-642-32241-9

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-32241-9_32

DOI

http://dx.doi.org/10.1007/978-3-642-32241-9_32

DIMENSIONS

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


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": "https://doi.org/10.1145/276698.276876", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1004824658"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-13818-8_38", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1007510157", 
          "https://doi.org/10.1007/978-3-642-13818-8_38"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-13818-8_38", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1007510157", 
          "https://doi.org/10.1007/978-3-642-13818-8_38"
        ], 
        "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": "https://doi.org/10.1016/0020-0190(82)90106-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1011902333"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf00263763", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1013672587", 
          "https://doi.org/10.1007/bf00263763"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf00263763", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1013672587", 
          "https://doi.org/10.1007/bf00263763"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1186/1471-2164-12-156", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1015894116", 
          "https://doi.org/10.1186/1471-2164-12-156"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/pl00009394", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1022776301", 
          "https://doi.org/10.1007/pl00009394"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/pl00009394", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1022776301", 
          "https://doi.org/10.1007/pl00009394"
        ], 
        "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.1093/mp/ssn048", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1040658897"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/383034.383035", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1043239832"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0925-7721(92)90006-e", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1052937945"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0925-7721(92)90006-e", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1052937945"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/s0097539796260321", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062880085"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/1.9781611973068.33", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1088801077"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/ssdbm.2006.23", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1094113036"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2012", 
    "datePublishedReg": "2012-01-01", 
    "description": "We study the Partial Nearest Neighbor Problem that consists in preprocessing n points \\(\\mathcal{D}\\) from d-dimensional metric space such that the following query can be answered efficiently: Given a query vector Q\u2009\u2208\u2009\u211d d and an axes-aligned query subspace represented by S\u2009\u2208\u2009{0,1} d , report a point \\(P \\in \\mathcal{D}\\) with d S (Q,P)\u2009\u2264\u2009d S (Q,P\u2032) for all \\(P' \\in \\mathcal{D}\\), where d S (Q,P) is the distance between Q and P in the subspace S. This problem is related to similarity search between feature vectors w.r.t.\u00a0a subset of features. Thus, the problem is of great practical importance in bioinformatics, image recognition, etc., however, due to exponentially many subspaces, each changing distances significantly, the problem has a considerable complexity. We present the first exact algorithms for \u21132- and \u2113\u2009\u221e\u2009-metrics with linear space and sub-linear worst-case query time. We also give a simple approximation algorithm, and show experimentally that our approach performs well on real world data.", 
    "editor": [
      {
        "familyName": "Gudmundsson", 
        "givenName": "Joachim", 
        "type": "Person"
      }, 
      {
        "familyName": "Mestre", 
        "givenName": "Juli\u00e1n", 
        "type": "Person"
      }, 
      {
        "familyName": "Viglas", 
        "givenName": "Taso", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-32241-9_32", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-32240-2", 
        "978-3-642-32241-9"
      ], 
      "name": "Computing and Combinatorics", 
      "type": "Book"
    }, 
    "name": "Partially Specified Nearest Neighbor Search", 
    "pagination": "372-383", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-32241-9_32"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "27aa92f9b0aae89a5f054f9f0e8d3431b168fd968845739a45220c9cbb6a754e"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1008326161"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-32241-9_32", 
      "https://app.dimensions.ai/details/publication/pub.1008326161"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-15T23:50", 
    "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_8697_00000248.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/978-3-642-32241-9_32"
  }
]
 

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-32241-9_32'

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-32241-9_32'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-32241-9_32'

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-32241-9_32'


 

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

129 TRIPLES      23 PREDICATES      41 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-32241-9_32 schema:about anzsrc-for:08
2 anzsrc-for:0806
3 schema:author N639336cdae214c48a86d57097c600360
4 schema:citation sg:pub.10.1007/978-3-642-13818-8_38
5 sg:pub.10.1007/bf00263763
6 sg:pub.10.1007/bf02574015
7 sg:pub.10.1007/pl00009394
8 sg:pub.10.1186/1471-2164-12-156
9 https://doi.org/10.1016/0020-0190(82)90106-5
10 https://doi.org/10.1016/0925-7721(92)90006-e
11 https://doi.org/10.1093/mp/ssn048
12 https://doi.org/10.1109/ssdbm.2006.23
13 https://doi.org/10.1137/1.9781611973068.33
14 https://doi.org/10.1137/s0097539796260321
15 https://doi.org/10.1145/10515.10522
16 https://doi.org/10.1145/276698.276876
17 https://doi.org/10.1145/383034.383035
18 schema:datePublished 2012
19 schema:datePublishedReg 2012-01-01
20 schema:description We study the Partial Nearest Neighbor Problem that consists in preprocessing n points \(\mathcal{D}\) from d-dimensional metric space such that the following query can be answered efficiently: Given a query vector Q ∈ ℝ d and an axes-aligned query subspace represented by S ∈ {0,1} d , report a point \(P \in \mathcal{D}\) with d S (Q,P) ≤ d S (Q,P′) for all \(P' \in \mathcal{D}\), where d S (Q,P) is the distance between Q and P in the subspace S. This problem is related to similarity search between feature vectors w.r.t. a subset of features. Thus, the problem is of great practical importance in bioinformatics, image recognition, etc., however, due to exponentially many subspaces, each changing distances significantly, the problem has a considerable complexity. We present the first exact algorithms for ℓ2- and ℓ ∞ -metrics with linear space and sub-linear worst-case query time. We also give a simple approximation algorithm, and show experimentally that our approach performs well on real world data.
21 schema:editor N3738d5c8743a43ad808fada0206dc89c
22 schema:genre chapter
23 schema:inLanguage en
24 schema:isAccessibleForFree true
25 schema:isPartOf Nc2a99b330e8045dc9df5ffacfe3ae762
26 schema:name Partially Specified Nearest Neighbor Search
27 schema:pagination 372-383
28 schema:productId N5ea7da3eb6424b899f366bfd9b2718ff
29 N69a94f189ae44f968d2d16a5b584bdfa
30 Nb613e6c1d64b42a2802824452dc682c8
31 schema:publisher Nda1e7720900944b7874a6a4abbb970d2
32 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008326161
33 https://doi.org/10.1007/978-3-642-32241-9_32
34 schema:sdDatePublished 2019-04-15T23:50
35 schema:sdLicense https://scigraph.springernature.com/explorer/license/
36 schema:sdPublisher Nda04a37ccc0a42fcab1939b0152e395e
37 schema:url http://link.springer.com/10.1007/978-3-642-32241-9_32
38 sgo:license sg:explorer/license/
39 sgo:sdDataset chapters
40 rdf:type schema:Chapter
41 N3738d5c8743a43ad808fada0206dc89c rdf:first Ncb33e9410b4b419198a2e0256064ef14
42 rdf:rest Nc936caf35d9f4264ad60558c92674ce5
43 N47b1fa21fa2d4c58aba9416afe1e673c rdf:first sg:person.01204623653.80
44 rdf:rest rdf:nil
45 N5ea7da3eb6424b899f366bfd9b2718ff schema:name readcube_id
46 schema:value 27aa92f9b0aae89a5f054f9f0e8d3431b168fd968845739a45220c9cbb6a754e
47 rdf:type schema:PropertyValue
48 N639336cdae214c48a86d57097c600360 rdf:first sg:person.01271152363.00
49 rdf:rest N47b1fa21fa2d4c58aba9416afe1e673c
50 N65e3c02345a24deba5382a476017c952 rdf:first N8cecc6db67f74f1493706dcc0a3883cc
51 rdf:rest rdf:nil
52 N69a94f189ae44f968d2d16a5b584bdfa schema:name doi
53 schema:value 10.1007/978-3-642-32241-9_32
54 rdf:type schema:PropertyValue
55 N8cecc6db67f74f1493706dcc0a3883cc schema:familyName Viglas
56 schema:givenName Taso
57 rdf:type schema:Person
58 Nb613e6c1d64b42a2802824452dc682c8 schema:name dimensions_id
59 schema:value pub.1008326161
60 rdf:type schema:PropertyValue
61 Nc2a99b330e8045dc9df5ffacfe3ae762 schema:isbn 978-3-642-32240-2
62 978-3-642-32241-9
63 schema:name Computing and Combinatorics
64 rdf:type schema:Book
65 Nc936caf35d9f4264ad60558c92674ce5 rdf:first Ndbc53fb650dc4d6da7ad00994e123644
66 rdf:rest N65e3c02345a24deba5382a476017c952
67 Ncb33e9410b4b419198a2e0256064ef14 schema:familyName Gudmundsson
68 schema:givenName Joachim
69 rdf:type schema:Person
70 Nda04a37ccc0a42fcab1939b0152e395e schema:name Springer Nature - SN SciGraph project
71 rdf:type schema:Organization
72 Nda1e7720900944b7874a6a4abbb970d2 schema:location Berlin, Heidelberg
73 schema:name Springer Berlin Heidelberg
74 rdf:type schema:Organisation
75 Ndbc53fb650dc4d6da7ad00994e123644 schema:familyName Mestre
76 schema:givenName Julián
77 rdf:type schema:Person
78 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
79 schema:name Information and Computing Sciences
80 rdf:type schema:DefinedTerm
81 anzsrc-for:0806 schema:inDefinedTermSet anzsrc-for:
82 schema:name Information Systems
83 rdf:type schema:DefinedTerm
84 sg:person.01204623653.80 schema:affiliation https://www.grid.ac/institutes/grid.5801.c
85 schema:familyName Schöngens
86 schema:givenName Marcel
87 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01204623653.80
88 rdf:type schema:Person
89 sg:person.01271152363.00 schema:affiliation https://www.grid.ac/institutes/grid.5801.c
90 schema:familyName Hruz
91 schema:givenName Tomas
92 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01271152363.00
93 rdf:type schema:Person
94 sg:pub.10.1007/978-3-642-13818-8_38 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007510157
95 https://doi.org/10.1007/978-3-642-13818-8_38
96 rdf:type schema:CreativeWork
97 sg:pub.10.1007/bf00263763 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013672587
98 https://doi.org/10.1007/bf00263763
99 rdf:type schema:CreativeWork
100 sg:pub.10.1007/bf02574015 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010441172
101 https://doi.org/10.1007/bf02574015
102 rdf:type schema:CreativeWork
103 sg:pub.10.1007/pl00009394 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022776301
104 https://doi.org/10.1007/pl00009394
105 rdf:type schema:CreativeWork
106 sg:pub.10.1186/1471-2164-12-156 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015894116
107 https://doi.org/10.1186/1471-2164-12-156
108 rdf:type schema:CreativeWork
109 https://doi.org/10.1016/0020-0190(82)90106-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011902333
110 rdf:type schema:CreativeWork
111 https://doi.org/10.1016/0925-7721(92)90006-e schema:sameAs https://app.dimensions.ai/details/publication/pub.1052937945
112 rdf:type schema:CreativeWork
113 https://doi.org/10.1093/mp/ssn048 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040658897
114 rdf:type schema:CreativeWork
115 https://doi.org/10.1109/ssdbm.2006.23 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094113036
116 rdf:type schema:CreativeWork
117 https://doi.org/10.1137/1.9781611973068.33 schema:sameAs https://app.dimensions.ai/details/publication/pub.1088801077
118 rdf:type schema:CreativeWork
119 https://doi.org/10.1137/s0097539796260321 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062880085
120 rdf:type schema:CreativeWork
121 https://doi.org/10.1145/10515.10522 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038514923
122 rdf:type schema:CreativeWork
123 https://doi.org/10.1145/276698.276876 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004824658
124 rdf:type schema:CreativeWork
125 https://doi.org/10.1145/383034.383035 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043239832
126 rdf:type schema:CreativeWork
127 https://www.grid.ac/institutes/grid.5801.c schema:alternateName Swiss Federal Institute of Technology in Zurich
128 schema:name Institute of Theoretical Computer Science, ETH Zurich, Switzerland
129 rdf:type schema:Organization
 




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


...