MKL-Tree: A Hierarchical Data Structure for Indexing Multidimensional Data View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2002-08-20

AUTHORS

Raffaele Cappelli , Alessandra Lumini , Dario Maio

ABSTRACT

Recently, multidimensional point indexing has generated a great deal of interest in applications where objects are usually represented through feature vectors belonging to high-dimensional spaces and are searched by similarity according to a given example. Unfortunately, although traditional data structures and access methods work well for low-dimensional spaces, they perform poorly as dimensionality increases. The application of a dimensionality reduction approach, such as the Karhunen-Loève transform, is often not very effective to deal with the indexing problem, since the substantial loss of information does not allow patterns to be sufficiently discriminated in the reduced space. In this work we present a novel hierarchical data structure based on the Multispace KL transform, a generalization of the KL transform, specifically designed to cope with locally correlated data. In the MKL-tree, dimensionality reduction is performed at each node, allowing more selective features to be extracted and thus increasing the discriminant power of the index. In this work the mathematical foundations and the algorithms on which the MKL-tree is based are presented and preliminary experimental results are reported. More... »

PAGES

914-924

Book

TITLE

Database and Expert Systems Applications

ISBN

978-3-540-44126-7
978-3-540-46146-3

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-46146-9_90

DOI

http://dx.doi.org/10.1007/3-540-46146-9_90

DIMENSIONS

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


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": "DEIS Universit\u00e0 di Bologna, viale Risorgimento 2, 40136, Bologna, Italy", 
          "id": "http://www.grid.ac/institutes/grid.6292.f", 
          "name": [
            "DEIS Universit\u00e0 di Bologna, viale Risorgimento 2, 40136, Bologna, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Cappelli", 
        "givenName": "Raffaele", 
        "id": "sg:person.011324641665.26", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011324641665.26"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "DEIS Universit\u00e0 di Bologna, viale Risorgimento 2, 40136, Bologna, Italy", 
          "id": "http://www.grid.ac/institutes/grid.6292.f", 
          "name": [
            "DEIS Universit\u00e0 di Bologna, viale Risorgimento 2, 40136, Bologna, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Lumini", 
        "givenName": "Alessandra", 
        "id": "sg:person.01230440001.42", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01230440001.42"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "DEIS Universit\u00e0 di Bologna, viale Risorgimento 2, 40136, Bologna, Italy", 
          "id": "http://www.grid.ac/institutes/grid.6292.f", 
          "name": [
            "DEIS Universit\u00e0 di Bologna, viale Risorgimento 2, 40136, Bologna, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Maio", 
        "givenName": "Dario", 
        "id": "sg:person.013075040365.65", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013075040365.65"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2002-08-20", 
    "datePublishedReg": "2002-08-20", 
    "description": "Recently, multidimensional point indexing has generated a great deal of interest in applications where objects are usually represented through feature vectors belonging to high-dimensional spaces and are searched by similarity according to a given example. Unfortunately, although traditional data structures and access methods work well for low-dimensional spaces, they perform poorly as dimensionality increases. The application of a dimensionality reduction approach, such as the Karhunen-Lo\u00e8ve transform, is often not very effective to deal with the indexing problem, since the substantial loss of information does not allow patterns to be sufficiently discriminated in the reduced space. In this work we present a novel hierarchical data structure based on the Multispace KL transform, a generalization of the KL transform, specifically designed to cope with locally correlated data. In the MKL-tree, dimensionality reduction is performed at each node, allowing more selective features to be extracted and thus increasing the discriminant power of the index. In this work the mathematical foundations and the algorithms on which the MKL-tree is based are presented and preliminary experimental results are reported.", 
    "editor": [
      {
        "familyName": "Hameurlain", 
        "givenName": "Abdelkader", 
        "type": "Person"
      }, 
      {
        "familyName": "Cicchetti", 
        "givenName": "Rosine", 
        "type": "Person"
      }, 
      {
        "familyName": "Traunm\u00fcller", 
        "givenName": "Roland", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-46146-9_90", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-44126-7", 
        "978-3-540-46146-3"
      ], 
      "name": "Database and Expert Systems Applications", 
      "type": "Book"
    }, 
    "keywords": [
      "hierarchical data structure", 
      "data structure", 
      "novel hierarchical data structure", 
      "traditional data structures", 
      "KL transform", 
      "Indexing Multidimensional Data", 
      "low-dimensional space", 
      "high-dimensional space", 
      "dimensionality reduction approach", 
      "Karhunen-Lo\u00e8ve transform", 
      "indexing problem", 
      "access methods", 
      "multidimensional data", 
      "feature vectors", 
      "preliminary experimental results", 
      "dimensionality reduction", 
      "dimensionality increases", 
      "mathematical foundation", 
      "selective features", 
      "experimental results", 
      "reduction approach", 
      "discriminant power", 
      "indexing", 
      "algorithm", 
      "transform", 
      "applications", 
      "nodes", 
      "space", 
      "objects", 
      "great deal", 
      "information", 
      "work", 
      "data", 
      "features", 
      "vector", 
      "example", 
      "generalization", 
      "deal", 
      "similarity", 
      "foundation", 
      "method", 
      "interest", 
      "power", 
      "structure", 
      "results", 
      "patterns", 
      "problem", 
      "loss", 
      "approach", 
      "substantial loss", 
      "reduction", 
      "index", 
      "increase"
    ], 
    "name": "MKL-Tree: A Hierarchical Data Structure for Indexing Multidimensional Data", 
    "pagination": "914-924", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1051494603"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-46146-9_90"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-46146-9_90", 
      "https://app.dimensions.ai/details/publication/pub.1051494603"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-11-24T21:15", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221124/entities/gbq_results/chapter/chapter_310.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-46146-9_90"
  }
]
 

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/3-540-46146-9_90'

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/3-540-46146-9_90'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-46146-9_90'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-46146-9_90'


 

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

136 TRIPLES      22 PREDICATES      77 URIs      70 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-46146-9_90 schema:about anzsrc-for:08
2 anzsrc-for:0806
3 schema:author N37bed66f120d40c0bcf3210ee042756e
4 schema:datePublished 2002-08-20
5 schema:datePublishedReg 2002-08-20
6 schema:description Recently, multidimensional point indexing has generated a great deal of interest in applications where objects are usually represented through feature vectors belonging to high-dimensional spaces and are searched by similarity according to a given example. Unfortunately, although traditional data structures and access methods work well for low-dimensional spaces, they perform poorly as dimensionality increases. The application of a dimensionality reduction approach, such as the Karhunen-Loève transform, is often not very effective to deal with the indexing problem, since the substantial loss of information does not allow patterns to be sufficiently discriminated in the reduced space. In this work we present a novel hierarchical data structure based on the Multispace KL transform, a generalization of the KL transform, specifically designed to cope with locally correlated data. In the MKL-tree, dimensionality reduction is performed at each node, allowing more selective features to be extracted and thus increasing the discriminant power of the index. In this work the mathematical foundations and the algorithms on which the MKL-tree is based are presented and preliminary experimental results are reported.
7 schema:editor Naad098a0d83f466aa6ad9239e41a2cc3
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf N01984aef099d4aaab8f8ebcbae4eabb1
11 schema:keywords Indexing Multidimensional Data
12 KL transform
13 Karhunen-Loève transform
14 access methods
15 algorithm
16 applications
17 approach
18 data
19 data structure
20 deal
21 dimensionality increases
22 dimensionality reduction
23 dimensionality reduction approach
24 discriminant power
25 example
26 experimental results
27 feature vectors
28 features
29 foundation
30 generalization
31 great deal
32 hierarchical data structure
33 high-dimensional space
34 increase
35 index
36 indexing
37 indexing problem
38 information
39 interest
40 loss
41 low-dimensional space
42 mathematical foundation
43 method
44 multidimensional data
45 nodes
46 novel hierarchical data structure
47 objects
48 patterns
49 power
50 preliminary experimental results
51 problem
52 reduction
53 reduction approach
54 results
55 selective features
56 similarity
57 space
58 structure
59 substantial loss
60 traditional data structures
61 transform
62 vector
63 work
64 schema:name MKL-Tree: A Hierarchical Data Structure for Indexing Multidimensional Data
65 schema:pagination 914-924
66 schema:productId N66290e7574b04b788063850208b17aa1
67 N72ea82e034d74af0a60064461d8f379c
68 schema:publisher N6fe8d9959edc4180bdf7db245e2cf1d6
69 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051494603
70 https://doi.org/10.1007/3-540-46146-9_90
71 schema:sdDatePublished 2022-11-24T21:15
72 schema:sdLicense https://scigraph.springernature.com/explorer/license/
73 schema:sdPublisher N868d46603e784277806b7ba475eeac00
74 schema:url https://doi.org/10.1007/3-540-46146-9_90
75 sgo:license sg:explorer/license/
76 sgo:sdDataset chapters
77 rdf:type schema:Chapter
78 N01984aef099d4aaab8f8ebcbae4eabb1 schema:isbn 978-3-540-44126-7
79 978-3-540-46146-3
80 schema:name Database and Expert Systems Applications
81 rdf:type schema:Book
82 N0502e525e66145ea820df16bd361912f rdf:first Nfd0504fdcd4c4f74a67dc4640893920d
83 rdf:rest N14b22365376846ef836c801e7b10dfa4
84 N14b22365376846ef836c801e7b10dfa4 rdf:first Nca60ff7b78954ae79ff62e48ea44549e
85 rdf:rest rdf:nil
86 N37bed66f120d40c0bcf3210ee042756e rdf:first sg:person.011324641665.26
87 rdf:rest N978dc484d304447593baa1852d656a36
88 N5568de23b0cf43a68fa1c6553290c848 schema:familyName Hameurlain
89 schema:givenName Abdelkader
90 rdf:type schema:Person
91 N66290e7574b04b788063850208b17aa1 schema:name dimensions_id
92 schema:value pub.1051494603
93 rdf:type schema:PropertyValue
94 N6fe8d9959edc4180bdf7db245e2cf1d6 schema:name Springer Nature
95 rdf:type schema:Organisation
96 N72ea82e034d74af0a60064461d8f379c schema:name doi
97 schema:value 10.1007/3-540-46146-9_90
98 rdf:type schema:PropertyValue
99 N868d46603e784277806b7ba475eeac00 schema:name Springer Nature - SN SciGraph project
100 rdf:type schema:Organization
101 N978dc484d304447593baa1852d656a36 rdf:first sg:person.01230440001.42
102 rdf:rest Ne802aaea03ad4933be56d215b70ca5de
103 Naad098a0d83f466aa6ad9239e41a2cc3 rdf:first N5568de23b0cf43a68fa1c6553290c848
104 rdf:rest N0502e525e66145ea820df16bd361912f
105 Nca60ff7b78954ae79ff62e48ea44549e schema:familyName Traunmüller
106 schema:givenName Roland
107 rdf:type schema:Person
108 Ne802aaea03ad4933be56d215b70ca5de rdf:first sg:person.013075040365.65
109 rdf:rest rdf:nil
110 Nfd0504fdcd4c4f74a67dc4640893920d schema:familyName Cicchetti
111 schema:givenName Rosine
112 rdf:type schema:Person
113 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
114 schema:name Information and Computing Sciences
115 rdf:type schema:DefinedTerm
116 anzsrc-for:0806 schema:inDefinedTermSet anzsrc-for:
117 schema:name Information Systems
118 rdf:type schema:DefinedTerm
119 sg:person.011324641665.26 schema:affiliation grid-institutes:grid.6292.f
120 schema:familyName Cappelli
121 schema:givenName Raffaele
122 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011324641665.26
123 rdf:type schema:Person
124 sg:person.01230440001.42 schema:affiliation grid-institutes:grid.6292.f
125 schema:familyName Lumini
126 schema:givenName Alessandra
127 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01230440001.42
128 rdf:type schema:Person
129 sg:person.013075040365.65 schema:affiliation grid-institutes:grid.6292.f
130 schema:familyName Maio
131 schema:givenName Dario
132 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013075040365.65
133 rdf:type schema:Person
134 grid-institutes:grid.6292.f schema:alternateName DEIS Università di Bologna, viale Risorgimento 2, 40136, Bologna, Italy
135 schema:name DEIS Università di Bologna, viale Risorgimento 2, 40136, Bologna, Italy
136 rdf:type schema:Organization
 




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


...