iPoc: A Polar Coordinate Based Indexing Method for Nearest Neighbor Search in High Dimensional Space View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2010

AUTHORS

Zhang Liu , Chaokun Wang , Peng Zou , Wei Zheng , Jianmin Wang

ABSTRACT

K-nearest neighbor (KNN) search in high dimensional space is essential for database applications, especially multimedia database applications, because images and audio clips are always modeled as high dimensional vectors. However, performance of existing indexing methods degrades dramatically as the dimensionality increases. In this paper, we propose a novel polar coordinate based indexing method, called iPoc, for efficient KNN search in high dimensional space. First, data space is initially partitioned into hypersphere regions, and then each hypersphere is further refined into hypersectors via hyperspherical surface clustering. After that, a series of local polar coordinate systems can be derived from hypersectors, taking advantage of the geometric characters of hypersectors. During search processing, iPoc can effectively prune query-unrelated data points by estimating the lower and upper bounds in both radial coordinate and angle coordinate. Furthermore, we design a key mapping scheme to merge keys measured by independent local polar coordinates into the global polar coordinates. Finally, the global polar coordinates are indexed by a traditional 2-dimensional spatial index, e.g., R-tree. Extensive experiments on real audio datasets and synthetic datasets confirm the effectiveness and efficiency of our proposal and prove that iPoc is more efficient than the existing high dimensional KNN search methods. More... »

PAGES

345-356

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-14246-8_34

DOI

http://dx.doi.org/10.1007/978-3-642-14246-8_34

DIMENSIONS

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


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": "Department of Computer Science and Technology, Tsinghua University", 
          "id": "http://www.grid.ac/institutes/grid.12527.33", 
          "name": [
            "Department of Computer Science and Technology, Tsinghua University"
          ], 
          "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": "Key Laboratory for Information System Security, Ministry of Education", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "School of Software, Tsinghua University, 100084, Beijing, China", 
            "Tsinghua National Laboratory for Information Science and Technology", 
            "Key Laboratory for Information System Security, Ministry of Education"
          ], 
          "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, China", 
          "id": "http://www.grid.ac/institutes/grid.12527.33", 
          "name": [
            "School of Software, Tsinghua University, 100084, Beijing, China"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Zou", 
        "givenName": "Peng", 
        "id": "sg:person.016573572021.95", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016573572021.95"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "School of Software, Tsinghua University, 100084, Beijing, China", 
          "id": "http://www.grid.ac/institutes/grid.12527.33", 
          "name": [
            "School of Software, Tsinghua University, 100084, Beijing, China"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Zheng", 
        "givenName": "Wei", 
        "id": "sg:person.011250253613.22", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011250253613.22"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Key Laboratory for Information System Security, Ministry of Education", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "School of Software, Tsinghua University, 100084, Beijing, China", 
            "Tsinghua National Laboratory for Information Science and Technology", 
            "Key Laboratory for Information System Security, Ministry of Education"
          ], 
          "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"
      }
    ], 
    "datePublished": "2010", 
    "datePublishedReg": "2010-01-01", 
    "description": "K-nearest neighbor\u00a0(KNN) search in high dimensional space is essential for database applications, especially multimedia database applications, because images and audio clips are always modeled as high dimensional vectors. However, performance of existing indexing methods degrades dramatically as the dimensionality increases. In this paper, we propose a novel polar coordinate based indexing method, called iPoc, for efficient KNN search in high dimensional space. First, data space is initially partitioned into hypersphere regions, and then each hypersphere is further refined into hypersectors via hyperspherical surface clustering. After that, a series of local polar coordinate systems can be derived from hypersectors, taking advantage of the geometric characters of hypersectors. During search processing, iPoc can effectively prune query-unrelated data points by estimating the lower and upper bounds in both radial coordinate and angle coordinate. Furthermore, we design a key mapping scheme to merge keys measured by independent local polar coordinates into the global polar coordinates. Finally, the global polar coordinates are indexed by a traditional 2-dimensional spatial index, e.g., R-tree. Extensive experiments on real audio datasets and synthetic datasets confirm the effectiveness and efficiency of our proposal and prove that iPoc is more efficient than the existing high dimensional KNN search methods.", 
    "editor": [
      {
        "familyName": "Chen", 
        "givenName": "Lei", 
        "type": "Person"
      }, 
      {
        "familyName": "Tang", 
        "givenName": "Changjie", 
        "type": "Person"
      }, 
      {
        "familyName": "Yang", 
        "givenName": "Jun", 
        "type": "Person"
      }, 
      {
        "familyName": "Gao", 
        "givenName": "Yunjun", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-14246-8_34", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-642-14245-1", 
        "978-3-642-14246-8"
      ], 
      "name": "Web-Age Information Management", 
      "type": "Book"
    }, 
    "keywords": [
      "high dimensional space", 
      "indexing method", 
      "database applications", 
      "dimensional space", 
      "multimedia database applications", 
      "efficient kNN search", 
      "Nearest Neighbor Search", 
      "high dimensional vectors", 
      "kNN search", 
      "neighbor search", 
      "audio dataset", 
      "Extensive experiments", 
      "search processing", 
      "synthetic datasets", 
      "audio clips", 
      "data space", 
      "local polar coordinates", 
      "spatial index", 
      "search method", 
      "mapping scheme", 
      "dimensionality increases", 
      "dimensional vector", 
      "nearest neighbors", 
      "novel polar", 
      "polar coordinates", 
      "datasets", 
      "data points", 
      "upper bounds", 
      "search", 
      "space", 
      "applications", 
      "clustering", 
      "geometric character", 
      "images", 
      "neighbors", 
      "scheme", 
      "coordinates", 
      "method", 
      "processing", 
      "key", 
      "surface clustering", 
      "clips", 
      "proposal", 
      "performance", 
      "effectiveness", 
      "bounds", 
      "system", 
      "advantages", 
      "trees", 
      "vector", 
      "efficiency", 
      "experiments", 
      "point", 
      "IPoC", 
      "Polar", 
      "character", 
      "series", 
      "region", 
      "index", 
      "increase", 
      "paper", 
      "hypersphere regions", 
      "hypersectors", 
      "hyperspherical surface clustering", 
      "query-unrelated data points", 
      "key mapping scheme", 
      "independent local polar coordinates", 
      "global polar coordinates", 
      "real audio datasets", 
      "high dimensional KNN search methods", 
      "dimensional KNN search methods", 
      "KNN search methods"
    ], 
    "name": "iPoc: A Polar Coordinate Based Indexing Method for Nearest Neighbor Search in High Dimensional Space", 
    "pagination": "345-356", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1032605603"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-14246-8_34"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-14246-8_34", 
      "https://app.dimensions.ai/details/publication/pub.1032605603"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-01-01T19:18", 
    "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/chapter/chapter_317.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-14246-8_34"
  }
]
 

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-14246-8_34'

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-14246-8_34'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-14246-8_34'

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-14246-8_34'


 

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

186 TRIPLES      23 PREDICATES      99 URIs      91 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-14246-8_34 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 anzsrc-for:0806
4 schema:author N84b2a946542648fd98375b27b33c1a15
5 schema:datePublished 2010
6 schema:datePublishedReg 2010-01-01
7 schema:description K-nearest neighbor (KNN) search in high dimensional space is essential for database applications, especially multimedia database applications, because images and audio clips are always modeled as high dimensional vectors. However, performance of existing indexing methods degrades dramatically as the dimensionality increases. In this paper, we propose a novel polar coordinate based indexing method, called iPoc, for efficient KNN search in high dimensional space. First, data space is initially partitioned into hypersphere regions, and then each hypersphere is further refined into hypersectors via hyperspherical surface clustering. After that, a series of local polar coordinate systems can be derived from hypersectors, taking advantage of the geometric characters of hypersectors. During search processing, iPoc can effectively prune query-unrelated data points by estimating the lower and upper bounds in both radial coordinate and angle coordinate. Furthermore, we design a key mapping scheme to merge keys measured by independent local polar coordinates into the global polar coordinates. Finally, the global polar coordinates are indexed by a traditional 2-dimensional spatial index, e.g., R-tree. Extensive experiments on real audio datasets and synthetic datasets confirm the effectiveness and efficiency of our proposal and prove that iPoc is more efficient than the existing high dimensional KNN search methods.
8 schema:editor N944a04601fc145f8b48377c02454cb41
9 schema:genre chapter
10 schema:inLanguage en
11 schema:isAccessibleForFree false
12 schema:isPartOf N939403ca37af4ae9bd81ebd4dbb34696
13 schema:keywords Extensive experiments
14 IPoC
15 KNN search methods
16 Nearest Neighbor Search
17 Polar
18 advantages
19 applications
20 audio clips
21 audio dataset
22 bounds
23 character
24 clips
25 clustering
26 coordinates
27 data points
28 data space
29 database applications
30 datasets
31 dimensional KNN search methods
32 dimensional space
33 dimensional vector
34 dimensionality increases
35 effectiveness
36 efficiency
37 efficient kNN search
38 experiments
39 geometric character
40 global polar coordinates
41 high dimensional KNN search methods
42 high dimensional space
43 high dimensional vectors
44 hypersectors
45 hypersphere regions
46 hyperspherical surface clustering
47 images
48 increase
49 independent local polar coordinates
50 index
51 indexing method
52 kNN search
53 key
54 key mapping scheme
55 local polar coordinates
56 mapping scheme
57 method
58 multimedia database applications
59 nearest neighbors
60 neighbor search
61 neighbors
62 novel polar
63 paper
64 performance
65 point
66 polar coordinates
67 processing
68 proposal
69 query-unrelated data points
70 real audio datasets
71 region
72 scheme
73 search
74 search method
75 search processing
76 series
77 space
78 spatial index
79 surface clustering
80 synthetic datasets
81 system
82 trees
83 upper bounds
84 vector
85 schema:name iPoc: A Polar Coordinate Based Indexing Method for Nearest Neighbor Search in High Dimensional Space
86 schema:pagination 345-356
87 schema:productId N9a5bdc51166c4335a7ba0a19aec2645d
88 Nfffaf20b5dce4d5892fdf64193af864b
89 schema:publisher N5bc887f3ce6e4956bf2fc5eef8ab6390
90 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032605603
91 https://doi.org/10.1007/978-3-642-14246-8_34
92 schema:sdDatePublished 2022-01-01T19:18
93 schema:sdLicense https://scigraph.springernature.com/explorer/license/
94 schema:sdPublisher N9994a264cb52476fad609fbd7161d343
95 schema:url https://doi.org/10.1007/978-3-642-14246-8_34
96 sgo:license sg:explorer/license/
97 sgo:sdDataset chapters
98 rdf:type schema:Chapter
99 N3c654f386ee54cd999c9e9d831386cc8 rdf:first sg:person.016573572021.95
100 rdf:rest Nd922924ee7794b8081e9bc22c4a6b37d
101 N460cfcd146df476d997504d47b5017c8 rdf:first Nbacfabe253c9454f9b28263247f8c8f1
102 rdf:rest Nde06c796febc47338bce3a18781fc1c6
103 N4bd643aa79f047f7ae8d86be4b837eb4 rdf:first sg:person.011533665437.99
104 rdf:rest N3c654f386ee54cd999c9e9d831386cc8
105 N5bc887f3ce6e4956bf2fc5eef8ab6390 schema:name Springer Nature
106 rdf:type schema:Organisation
107 N5bd46cbb63074949bd117ed95dfe4de3 schema:familyName Chen
108 schema:givenName Lei
109 rdf:type schema:Person
110 N84b2a946542648fd98375b27b33c1a15 rdf:first sg:person.016566115360.45
111 rdf:rest N4bd643aa79f047f7ae8d86be4b837eb4
112 N939403ca37af4ae9bd81ebd4dbb34696 schema:isbn 978-3-642-14245-1
113 978-3-642-14246-8
114 schema:name Web-Age Information Management
115 rdf:type schema:Book
116 N944a04601fc145f8b48377c02454cb41 rdf:first N5bd46cbb63074949bd117ed95dfe4de3
117 rdf:rest N460cfcd146df476d997504d47b5017c8
118 N9994a264cb52476fad609fbd7161d343 schema:name Springer Nature - SN SciGraph project
119 rdf:type schema:Organization
120 N9a5bdc51166c4335a7ba0a19aec2645d schema:name dimensions_id
121 schema:value pub.1032605603
122 rdf:type schema:PropertyValue
123 Nb4a9ce44c53946a7b0dc6580635401bd schema:familyName Gao
124 schema:givenName Yunjun
125 rdf:type schema:Person
126 Nbacfabe253c9454f9b28263247f8c8f1 schema:familyName Tang
127 schema:givenName Changjie
128 rdf:type schema:Person
129 Nbca67cefbbf94922b4ac87a3a265a68a rdf:first sg:person.012303351315.43
130 rdf:rest rdf:nil
131 Nc3815e95b0c54fcba6c9e14b3af0b8e7 rdf:first Nb4a9ce44c53946a7b0dc6580635401bd
132 rdf:rest rdf:nil
133 Nd922924ee7794b8081e9bc22c4a6b37d rdf:first sg:person.011250253613.22
134 rdf:rest Nbca67cefbbf94922b4ac87a3a265a68a
135 Nde06c796febc47338bce3a18781fc1c6 rdf:first Nf67ab4f7e65c43829427930ace2bcd81
136 rdf:rest Nc3815e95b0c54fcba6c9e14b3af0b8e7
137 Nf67ab4f7e65c43829427930ace2bcd81 schema:familyName Yang
138 schema:givenName Jun
139 rdf:type schema:Person
140 Nfffaf20b5dce4d5892fdf64193af864b schema:name doi
141 schema:value 10.1007/978-3-642-14246-8_34
142 rdf:type schema:PropertyValue
143 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
144 schema:name Information and Computing Sciences
145 rdf:type schema:DefinedTerm
146 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
147 schema:name Artificial Intelligence and Image Processing
148 rdf:type schema:DefinedTerm
149 anzsrc-for:0806 schema:inDefinedTermSet anzsrc-for:
150 schema:name Information Systems
151 rdf:type schema:DefinedTerm
152 sg:person.011250253613.22 schema:affiliation grid-institutes:grid.12527.33
153 schema:familyName Zheng
154 schema:givenName Wei
155 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011250253613.22
156 rdf:type schema:Person
157 sg:person.011533665437.99 schema:affiliation grid-institutes:None
158 schema:familyName Wang
159 schema:givenName Chaokun
160 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011533665437.99
161 rdf:type schema:Person
162 sg:person.012303351315.43 schema:affiliation grid-institutes:None
163 schema:familyName Wang
164 schema:givenName Jianmin
165 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012303351315.43
166 rdf:type schema:Person
167 sg:person.016566115360.45 schema:affiliation grid-institutes:grid.12527.33
168 schema:familyName Liu
169 schema:givenName Zhang
170 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016566115360.45
171 rdf:type schema:Person
172 sg:person.016573572021.95 schema:affiliation grid-institutes:grid.12527.33
173 schema:familyName Zou
174 schema:givenName Peng
175 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016573572021.95
176 rdf:type schema:Person
177 grid-institutes:None schema:alternateName Key Laboratory for Information System Security, Ministry of Education
178 schema:name Key Laboratory for Information System Security, Ministry of Education
179 School of Software, Tsinghua University, 100084, Beijing, China
180 Tsinghua National Laboratory for Information Science and Technology
181 rdf:type schema:Organization
182 grid-institutes:grid.12527.33 schema:alternateName Department of Computer Science and Technology, Tsinghua University
183 School of Software, Tsinghua University, 100084, Beijing, China
184 schema:name Department of Computer Science and Technology, Tsinghua University
185 School of Software, Tsinghua University, 100084, Beijing, China
186 rdf:type schema:Organization
 




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


...