Subspace Nearest Neighbor Search - Problem Statement, Approaches, and Discussion View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2015-10-17

AUTHORS

Michael Hund , Michael Behrisch , Ines Färber , Michael Sedlmair , Tobias Schreck , Thomas Seidl , Daniel Keim

ABSTRACT

Computing the similarity between objects is a central task for many applications in the field of information retrieval and data mining. For finding k-nearest neighbors, typically a ranking is computed based on a predetermined set of data dimensions and a distance function, constant over all possible queries. However, many high-dimensional feature spaces contain a large number of dimensions, many of which may contain noise, irrelevant, redundant, or contradicting information. More specifically, the relevance of dimensions may depend on the query object itself, and in general, different dimension sets (subspaces) may be appropriate for a query. Approaches for feature selection or -weighting typically provide a global subspace selection, which may not be suitable for all possibly queries. In this position paper, we frame a new research problem, called subspace nearest neighbor search, aiming at multiple query-dependent subspaces for nearest neighbor search. We describe relevant problem characteristics, relate to existing approaches, and outline potential research directions. More... »

PAGES

307-313

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-319-25087-8_29

DOI

http://dx.doi.org/10.1007/978-3-319-25087-8_29

DIMENSIONS

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


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/0801", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Artificial Intelligence and Image Processing", 
        "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": "University of Konstanz, Konstanz, Germany", 
          "id": "http://www.grid.ac/institutes/grid.9811.1", 
          "name": [
            "University of Konstanz, Konstanz, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Hund", 
        "givenName": "Michael", 
        "id": "sg:person.012227723565.37", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012227723565.37"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Konstanz, Konstanz, Germany", 
          "id": "http://www.grid.ac/institutes/grid.9811.1", 
          "name": [
            "University of Konstanz, Konstanz, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Behrisch", 
        "givenName": "Michael", 
        "id": "sg:person.015652304075.82", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015652304075.82"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "RWTH Aachen University, Aachen, Germany", 
          "id": "http://www.grid.ac/institutes/grid.1957.a", 
          "name": [
            "RWTH Aachen University, Aachen, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "F\u00e4rber", 
        "givenName": "Ines", 
        "id": "sg:person.012777621745.44", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012777621745.44"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Vienna, Wien, Austria", 
          "id": "http://www.grid.ac/institutes/grid.10420.37", 
          "name": [
            "University of Vienna, Wien, Austria"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Sedlmair", 
        "givenName": "Michael", 
        "id": "sg:person.01274657031.24", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01274657031.24"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Graz University of Technology, Graz, Austria", 
          "id": "http://www.grid.ac/institutes/grid.410413.3", 
          "name": [
            "Graz University of Technology, Graz, Austria"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Schreck", 
        "givenName": "Tobias", 
        "id": "sg:person.01165671765.01", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01165671765.01"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "RWTH Aachen University, Aachen, Germany", 
          "id": "http://www.grid.ac/institutes/grid.1957.a", 
          "name": [
            "RWTH Aachen University, Aachen, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Seidl", 
        "givenName": "Thomas", 
        "id": "sg:person.010006167221.37", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010006167221.37"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Konstanz, Konstanz, Germany", 
          "id": "http://www.grid.ac/institutes/grid.9811.1", 
          "name": [
            "University of Konstanz, Konstanz, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Keim", 
        "givenName": "Daniel", 
        "id": "sg:person.0635776571.01", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0635776571.01"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2015-10-17", 
    "datePublishedReg": "2015-10-17", 
    "description": "Computing the similarity between objects is a central task for many applications in the field of information retrieval and data mining. For finding k-nearest neighbors, typically a ranking is computed based on a predetermined set of data dimensions and a distance function, constant over all possible queries. However, many high-dimensional feature spaces contain a large number of dimensions, many of which may contain noise, irrelevant, redundant, or contradicting information. More specifically, the relevance of dimensions may depend on the query object itself, and in general, different dimension sets (subspaces) may be appropriate for a query. Approaches for feature selection or -weighting typically provide a global subspace selection, which may not be suitable for all possibly queries. In this position paper, we frame a new research problem, called subspace nearest neighbor search, aiming at multiple query-dependent subspaces for nearest neighbor search. We describe relevant problem characteristics, relate to existing approaches, and outline potential research directions.", 
    "editor": [
      {
        "familyName": "Amato", 
        "givenName": "Giuseppe", 
        "type": "Person"
      }, 
      {
        "familyName": "Connor", 
        "givenName": "Richard", 
        "type": "Person"
      }, 
      {
        "familyName": "Falchi", 
        "givenName": "Fabrizio", 
        "type": "Person"
      }, 
      {
        "familyName": "Gennaro", 
        "givenName": "Claudio", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-319-25087-8_29", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-319-25086-1", 
        "978-3-319-25087-8"
      ], 
      "name": "Similarity Search and Applications", 
      "type": "Book"
    }, 
    "keywords": [
      "nearest neighbor search", 
      "neighbor search", 
      "high-dimensional feature space", 
      "new research problem", 
      "information retrieval", 
      "possible queries", 
      "data mining", 
      "potential research directions", 
      "feature selection", 
      "data dimension", 
      "queries", 
      "feature space", 
      "problem characteristics", 
      "dimension sets", 
      "subspace selection", 
      "relevance of dimensions", 
      "nearest neighbors", 
      "research problem", 
      "position paper", 
      "research directions", 
      "distance function", 
      "predetermined set", 
      "central task", 
      "large number", 
      "mining", 
      "set", 
      "retrieval", 
      "search", 
      "task", 
      "neighbors", 
      "objects", 
      "selection", 
      "information", 
      "subspace", 
      "ranking", 
      "applications", 
      "noise", 
      "space", 
      "dimensions", 
      "similarity", 
      "number", 
      "field", 
      "direction", 
      "statements", 
      "discussion", 
      "function", 
      "relevance", 
      "characteristics", 
      "approach", 
      "paper", 
      "problem"
    ], 
    "name": "Subspace Nearest Neighbor Search - Problem Statement, Approaches, and Discussion", 
    "pagination": "307-313", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1009194621"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-319-25087-8_29"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-319-25087-8_29", 
      "https://app.dimensions.ai/details/publication/pub.1009194621"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-09-02T16:15", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220902/entities/gbq_results/chapter/chapter_395.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-319-25087-8_29"
  }
]
 

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-319-25087-8_29'

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-319-25087-8_29'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-25087-8_29'

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-319-25087-8_29'


 

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

180 TRIPLES      22 PREDICATES      76 URIs      68 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-319-25087-8_29 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 anzsrc-for:0806
4 schema:author Ne8019d740b4c446fb46832e90ac266ca
5 schema:datePublished 2015-10-17
6 schema:datePublishedReg 2015-10-17
7 schema:description Computing the similarity between objects is a central task for many applications in the field of information retrieval and data mining. For finding k-nearest neighbors, typically a ranking is computed based on a predetermined set of data dimensions and a distance function, constant over all possible queries. However, many high-dimensional feature spaces contain a large number of dimensions, many of which may contain noise, irrelevant, redundant, or contradicting information. More specifically, the relevance of dimensions may depend on the query object itself, and in general, different dimension sets (subspaces) may be appropriate for a query. Approaches for feature selection or -weighting typically provide a global subspace selection, which may not be suitable for all possibly queries. In this position paper, we frame a new research problem, called subspace nearest neighbor search, aiming at multiple query-dependent subspaces for nearest neighbor search. We describe relevant problem characteristics, relate to existing approaches, and outline potential research directions.
8 schema:editor Nfb6c915e9eac498ab4852232f05d1890
9 schema:genre chapter
10 schema:isAccessibleForFree true
11 schema:isPartOf N980395cd1117481daa78d8aea3268f67
12 schema:keywords applications
13 approach
14 central task
15 characteristics
16 data dimension
17 data mining
18 dimension sets
19 dimensions
20 direction
21 discussion
22 distance function
23 feature selection
24 feature space
25 field
26 function
27 high-dimensional feature space
28 information
29 information retrieval
30 large number
31 mining
32 nearest neighbor search
33 nearest neighbors
34 neighbor search
35 neighbors
36 new research problem
37 noise
38 number
39 objects
40 paper
41 position paper
42 possible queries
43 potential research directions
44 predetermined set
45 problem
46 problem characteristics
47 queries
48 ranking
49 relevance
50 relevance of dimensions
51 research directions
52 research problem
53 retrieval
54 search
55 selection
56 set
57 similarity
58 space
59 statements
60 subspace
61 subspace selection
62 task
63 schema:name Subspace Nearest Neighbor Search - Problem Statement, Approaches, and Discussion
64 schema:pagination 307-313
65 schema:productId N5dc3854ef15447a6958bfccbb9b673d9
66 N979fa8088ab24a758d3f5c7c0a978e0a
67 schema:publisher N842aaba481644c738d616c64db4b3062
68 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009194621
69 https://doi.org/10.1007/978-3-319-25087-8_29
70 schema:sdDatePublished 2022-09-02T16:15
71 schema:sdLicense https://scigraph.springernature.com/explorer/license/
72 schema:sdPublisher Nfe5081fca1b942e2a32fc93010518c9c
73 schema:url https://doi.org/10.1007/978-3-319-25087-8_29
74 sgo:license sg:explorer/license/
75 sgo:sdDataset chapters
76 rdf:type schema:Chapter
77 N4d4d23f51a45441694d8589abbea3325 rdf:first sg:person.015652304075.82
78 rdf:rest Nca3fcce6c09e4522968622eac65c8930
79 N557d2519fd6f4e74a15677fa06187561 rdf:first N784f68fb63184e6fb3b4bb44d97ff53f
80 rdf:rest rdf:nil
81 N598183f388fc4710aeaa4edded3b6b8b rdf:first sg:person.0635776571.01
82 rdf:rest rdf:nil
83 N5dc3854ef15447a6958bfccbb9b673d9 schema:name doi
84 schema:value 10.1007/978-3-319-25087-8_29
85 rdf:type schema:PropertyValue
86 N736c86a11106460c9eb659f34f491e67 rdf:first Nbf6813c66c964df6996462ae3c0b407b
87 rdf:rest N9a060db1f02a4251bbfcdc7d57ae4969
88 N784f68fb63184e6fb3b4bb44d97ff53f schema:familyName Gennaro
89 schema:givenName Claudio
90 rdf:type schema:Person
91 N842aaba481644c738d616c64db4b3062 schema:name Springer Nature
92 rdf:type schema:Organisation
93 N94f3c97a06dd43c9aee18d9694ebf22d schema:familyName Falchi
94 schema:givenName Fabrizio
95 rdf:type schema:Person
96 N979fa8088ab24a758d3f5c7c0a978e0a schema:name dimensions_id
97 schema:value pub.1009194621
98 rdf:type schema:PropertyValue
99 N980395cd1117481daa78d8aea3268f67 schema:isbn 978-3-319-25086-1
100 978-3-319-25087-8
101 schema:name Similarity Search and Applications
102 rdf:type schema:Book
103 N9a060db1f02a4251bbfcdc7d57ae4969 rdf:first N94f3c97a06dd43c9aee18d9694ebf22d
104 rdf:rest N557d2519fd6f4e74a15677fa06187561
105 Nadbcfafb34b54b7182ad5c93e738d8dd rdf:first sg:person.01165671765.01
106 rdf:rest Nc48d5032961c4976bcad69493a6f914a
107 Nbf6813c66c964df6996462ae3c0b407b schema:familyName Connor
108 schema:givenName Richard
109 rdf:type schema:Person
110 Nc48d5032961c4976bcad69493a6f914a rdf:first sg:person.010006167221.37
111 rdf:rest N598183f388fc4710aeaa4edded3b6b8b
112 Nca3fcce6c09e4522968622eac65c8930 rdf:first sg:person.012777621745.44
113 rdf:rest Nd9afa2f1578648a5a3aba80ae16b0a0e
114 Ncd8d9b5bc6fe4e6db8c28e6433226d2a schema:familyName Amato
115 schema:givenName Giuseppe
116 rdf:type schema:Person
117 Nd9afa2f1578648a5a3aba80ae16b0a0e rdf:first sg:person.01274657031.24
118 rdf:rest Nadbcfafb34b54b7182ad5c93e738d8dd
119 Ne8019d740b4c446fb46832e90ac266ca rdf:first sg:person.012227723565.37
120 rdf:rest N4d4d23f51a45441694d8589abbea3325
121 Nfb6c915e9eac498ab4852232f05d1890 rdf:first Ncd8d9b5bc6fe4e6db8c28e6433226d2a
122 rdf:rest N736c86a11106460c9eb659f34f491e67
123 Nfe5081fca1b942e2a32fc93010518c9c schema:name Springer Nature - SN SciGraph project
124 rdf:type schema:Organization
125 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
126 schema:name Information and Computing Sciences
127 rdf:type schema:DefinedTerm
128 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
129 schema:name Artificial Intelligence and Image Processing
130 rdf:type schema:DefinedTerm
131 anzsrc-for:0806 schema:inDefinedTermSet anzsrc-for:
132 schema:name Information Systems
133 rdf:type schema:DefinedTerm
134 sg:person.010006167221.37 schema:affiliation grid-institutes:grid.1957.a
135 schema:familyName Seidl
136 schema:givenName Thomas
137 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010006167221.37
138 rdf:type schema:Person
139 sg:person.01165671765.01 schema:affiliation grid-institutes:grid.410413.3
140 schema:familyName Schreck
141 schema:givenName Tobias
142 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01165671765.01
143 rdf:type schema:Person
144 sg:person.012227723565.37 schema:affiliation grid-institutes:grid.9811.1
145 schema:familyName Hund
146 schema:givenName Michael
147 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012227723565.37
148 rdf:type schema:Person
149 sg:person.01274657031.24 schema:affiliation grid-institutes:grid.10420.37
150 schema:familyName Sedlmair
151 schema:givenName Michael
152 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01274657031.24
153 rdf:type schema:Person
154 sg:person.012777621745.44 schema:affiliation grid-institutes:grid.1957.a
155 schema:familyName Färber
156 schema:givenName Ines
157 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012777621745.44
158 rdf:type schema:Person
159 sg:person.015652304075.82 schema:affiliation grid-institutes:grid.9811.1
160 schema:familyName Behrisch
161 schema:givenName Michael
162 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015652304075.82
163 rdf:type schema:Person
164 sg:person.0635776571.01 schema:affiliation grid-institutes:grid.9811.1
165 schema:familyName Keim
166 schema:givenName Daniel
167 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0635776571.01
168 rdf:type schema:Person
169 grid-institutes:grid.10420.37 schema:alternateName University of Vienna, Wien, Austria
170 schema:name University of Vienna, Wien, Austria
171 rdf:type schema:Organization
172 grid-institutes:grid.1957.a schema:alternateName RWTH Aachen University, Aachen, Germany
173 schema:name RWTH Aachen University, Aachen, Germany
174 rdf:type schema:Organization
175 grid-institutes:grid.410413.3 schema:alternateName Graz University of Technology, Graz, Austria
176 schema:name Graz University of Technology, Graz, Austria
177 rdf:type schema:Organization
178 grid-institutes:grid.9811.1 schema:alternateName University of Konstanz, Konstanz, Germany
179 schema:name University of Konstanz, Konstanz, Germany
180 rdf:type schema:Organization
 




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


...