MKL-tree: an index structure for high-dimensional vector spaces View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2006-11-09

AUTHORS

Annalisa Franco, Alessandra Lumini, Dario Maio

ABSTRACT

In this work, a novel hierarchical data structure for high dimensional data indexing is proposed. MKL-tree is based on dimensionality reduction operated by means of the MKL transform, a multi-space generalization of the KL transform. A local dimensionality reduction is performed at each node of the tree, allowing more selective features to be extracted and thus increasing the discriminating power of the index. The mathematical foundation for nodes and leaves representation and for the techniques aimed to manage the structure is detailed. Moreover, the algorithms for bulk loading MKL-tree (i.e., for creating the tree given a large number of objects simultaneously), for updating and splitting nodes after the insertion of new objects and for performing similarity searches are described. Results are reported for the comparison of MKL-tree with other well-known access methods in terms of I/O and CPU costs and precision of the result in the execution of similarity queries. More... »

PAGES

533-550

References to SciGraph publications

  • 1986. Principal Component Analysis in NONE
  • 1999. Efficient Bulk Loading of Large High-Dimensional Indexes in DATAWAREHOUSING AND KNOWLEDGE DISCOVERY
  • 1994-10. The TV-tree: An index structure for high-dimensional data in THE VLDB JOURNAL
  • 1997-06. BIRCH: A New Data Clustering Algorithm and Its Applications in DATA MINING AND KNOWLEDGE DISCOVERY
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00530-006-0070-9

    DOI

    http://dx.doi.org/10.1007/s00530-006-0070-9

    DIMENSIONS

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


    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"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Corso di Laurea in Scienze dell\u2019Informazione, Universit\u00e0 di Bologna, via Sacchi 3, 47023, Cesena, Italy", 
              "id": "http://www.grid.ac/institutes/grid.6292.f", 
              "name": [
                "Corso di Laurea in Scienze dell\u2019Informazione, Universit\u00e0 di Bologna, via Sacchi 3, 47023, Cesena, Italy"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Franco", 
            "givenName": "Annalisa", 
            "id": "sg:person.011002501427.92", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011002501427.92"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Corso di Laurea in Scienze dell\u2019Informazione, Universit\u00e0 di Bologna, via Sacchi 3, 47023, Cesena, Italy", 
              "id": "http://www.grid.ac/institutes/grid.6292.f", 
              "name": [
                "Corso di Laurea in Scienze dell\u2019Informazione, Universit\u00e0 di Bologna, via Sacchi 3, 47023, Cesena, 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 - CSITE-CNR - Universit\u00e0 di Bologna, viale Risorgimento 2, 40136, Bologna, Italy", 
              "id": "http://www.grid.ac/institutes/grid.6292.f", 
              "name": [
                "DEIS - CSITE-CNR - 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"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1023/a:1009783824328", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1000292060", 
              "https://doi.org/10.1023/a:1009783824328"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4757-1904-8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1031639131", 
              "https://doi.org/10.1007/978-1-4757-1904-8"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01231606", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1015907927", 
              "https://doi.org/10.1007/bf01231606"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-48298-9_27", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051887266", 
              "https://doi.org/10.1007/3-540-48298-9_27"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2006-11-09", 
        "datePublishedReg": "2006-11-09", 
        "description": "In this work, a novel hierarchical data structure for high dimensional data indexing is proposed. MKL-tree is based on dimensionality reduction operated by means of the MKL transform, a multi-space generalization of the KL transform. A local dimensionality reduction is performed at each node of the tree, allowing more selective features to be extracted and thus increasing the discriminating power of the index. The mathematical foundation for nodes and leaves representation and for the techniques aimed to manage the structure is detailed. Moreover, the algorithms for bulk loading MKL-tree (i.e., for creating the tree given a large number of objects simultaneously), for updating and splitting nodes after the insertion of new objects and for performing similarity searches are described. Results are reported for the comparison of MKL-tree with other well-known access methods in terms of I/O and CPU costs and precision of the result in the execution of similarity queries.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/s00530-006-0070-9", 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1358858", 
            "issn": [
              "0942-4962", 
              "1432-1882"
            ], 
            "name": "Multimedia Systems", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "6", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "12"
          }
        ], 
        "keywords": [
          "novel hierarchical data structure", 
          "local dimensionality reduction", 
          "mathematical foundation", 
          "high-dimensional vector space", 
          "dimensionality reduction", 
          "vector space", 
          "hierarchical data structure", 
          "CPU cost", 
          "KL transform", 
          "high-dimensional data indexing", 
          "data structure", 
          "new objects", 
          "generalization", 
          "splitting nodes", 
          "nodes", 
          "algorithm", 
          "space", 
          "structure", 
          "representation", 
          "access methods", 
          "transform", 
          "selective features", 
          "similarity search", 
          "updating", 
          "objects", 
          "terms", 
          "index structure", 
          "results", 
          "power", 
          "technique", 
          "means", 
          "data indexing", 
          "work", 
          "foundation", 
          "search", 
          "comparison", 
          "cost", 
          "precision", 
          "features", 
          "trees", 
          "execution", 
          "reduction", 
          "similarity queries", 
          "index", 
          "indexing", 
          "queries", 
          "loading", 
          "bulk loading", 
          "insertion", 
          "method"
        ], 
        "name": "MKL-tree: an index structure for high-dimensional vector spaces", 
        "pagination": "533-550", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1010033619"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00530-006-0070-9"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00530-006-0070-9", 
          "https://app.dimensions.ai/details/publication/pub.1010033619"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2022-12-01T06:25", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20221201/entities/gbq_results/article/article_419.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/s00530-006-0070-9"
      }
    ]
     

    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/s00530-006-0070-9'

    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/s00530-006-0070-9'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00530-006-0070-9'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00530-006-0070-9'


     

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

    139 TRIPLES      21 PREDICATES      78 URIs      66 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00530-006-0070-9 schema:about anzsrc-for:08
    2 anzsrc-for:0801
    3 schema:author N30e887365e524f2585fade4fa31970e8
    4 schema:citation sg:pub.10.1007/3-540-48298-9_27
    5 sg:pub.10.1007/978-1-4757-1904-8
    6 sg:pub.10.1007/bf01231606
    7 sg:pub.10.1023/a:1009783824328
    8 schema:datePublished 2006-11-09
    9 schema:datePublishedReg 2006-11-09
    10 schema:description In this work, a novel hierarchical data structure for high dimensional data indexing is proposed. MKL-tree is based on dimensionality reduction operated by means of the MKL transform, a multi-space generalization of the KL transform. A local dimensionality reduction is performed at each node of the tree, allowing more selective features to be extracted and thus increasing the discriminating power of the index. The mathematical foundation for nodes and leaves representation and for the techniques aimed to manage the structure is detailed. Moreover, the algorithms for bulk loading MKL-tree (i.e., for creating the tree given a large number of objects simultaneously), for updating and splitting nodes after the insertion of new objects and for performing similarity searches are described. Results are reported for the comparison of MKL-tree with other well-known access methods in terms of I/O and CPU costs and precision of the result in the execution of similarity queries.
    11 schema:genre article
    12 schema:isAccessibleForFree false
    13 schema:isPartOf Ncfbc8a04da2b4a668358aa331a4c66d5
    14 Nd9c449652d894fc7ab21a2d7f90666d9
    15 sg:journal.1358858
    16 schema:keywords CPU cost
    17 KL transform
    18 access methods
    19 algorithm
    20 bulk loading
    21 comparison
    22 cost
    23 data indexing
    24 data structure
    25 dimensionality reduction
    26 execution
    27 features
    28 foundation
    29 generalization
    30 hierarchical data structure
    31 high-dimensional data indexing
    32 high-dimensional vector space
    33 index
    34 index structure
    35 indexing
    36 insertion
    37 loading
    38 local dimensionality reduction
    39 mathematical foundation
    40 means
    41 method
    42 new objects
    43 nodes
    44 novel hierarchical data structure
    45 objects
    46 power
    47 precision
    48 queries
    49 reduction
    50 representation
    51 results
    52 search
    53 selective features
    54 similarity queries
    55 similarity search
    56 space
    57 splitting nodes
    58 structure
    59 technique
    60 terms
    61 transform
    62 trees
    63 updating
    64 vector space
    65 work
    66 schema:name MKL-tree: an index structure for high-dimensional vector spaces
    67 schema:pagination 533-550
    68 schema:productId N6608581d85cf4f37b2a0be4d9eeadb78
    69 N94136fd229074a58903ba0775b3299a3
    70 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010033619
    71 https://doi.org/10.1007/s00530-006-0070-9
    72 schema:sdDatePublished 2022-12-01T06:25
    73 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    74 schema:sdPublisher Nc478aeff9b0b4e70bb08432d9a08220e
    75 schema:url https://doi.org/10.1007/s00530-006-0070-9
    76 sgo:license sg:explorer/license/
    77 sgo:sdDataset articles
    78 rdf:type schema:ScholarlyArticle
    79 N30e887365e524f2585fade4fa31970e8 rdf:first sg:person.011002501427.92
    80 rdf:rest N8467c5aea6584b1cac13a57070db012b
    81 N6608581d85cf4f37b2a0be4d9eeadb78 schema:name doi
    82 schema:value 10.1007/s00530-006-0070-9
    83 rdf:type schema:PropertyValue
    84 N795d28b352664366b518f5f900fdf7a1 rdf:first sg:person.013075040365.65
    85 rdf:rest rdf:nil
    86 N8467c5aea6584b1cac13a57070db012b rdf:first sg:person.01230440001.42
    87 rdf:rest N795d28b352664366b518f5f900fdf7a1
    88 N94136fd229074a58903ba0775b3299a3 schema:name dimensions_id
    89 schema:value pub.1010033619
    90 rdf:type schema:PropertyValue
    91 Nc478aeff9b0b4e70bb08432d9a08220e schema:name Springer Nature - SN SciGraph project
    92 rdf:type schema:Organization
    93 Ncfbc8a04da2b4a668358aa331a4c66d5 schema:issueNumber 6
    94 rdf:type schema:PublicationIssue
    95 Nd9c449652d894fc7ab21a2d7f90666d9 schema:volumeNumber 12
    96 rdf:type schema:PublicationVolume
    97 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    98 schema:name Information and Computing Sciences
    99 rdf:type schema:DefinedTerm
    100 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
    101 schema:name Artificial Intelligence and Image Processing
    102 rdf:type schema:DefinedTerm
    103 sg:journal.1358858 schema:issn 0942-4962
    104 1432-1882
    105 schema:name Multimedia Systems
    106 schema:publisher Springer Nature
    107 rdf:type schema:Periodical
    108 sg:person.011002501427.92 schema:affiliation grid-institutes:grid.6292.f
    109 schema:familyName Franco
    110 schema:givenName Annalisa
    111 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011002501427.92
    112 rdf:type schema:Person
    113 sg:person.01230440001.42 schema:affiliation grid-institutes:grid.6292.f
    114 schema:familyName Lumini
    115 schema:givenName Alessandra
    116 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01230440001.42
    117 rdf:type schema:Person
    118 sg:person.013075040365.65 schema:affiliation grid-institutes:grid.6292.f
    119 schema:familyName Maio
    120 schema:givenName Dario
    121 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013075040365.65
    122 rdf:type schema:Person
    123 sg:pub.10.1007/3-540-48298-9_27 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051887266
    124 https://doi.org/10.1007/3-540-48298-9_27
    125 rdf:type schema:CreativeWork
    126 sg:pub.10.1007/978-1-4757-1904-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031639131
    127 https://doi.org/10.1007/978-1-4757-1904-8
    128 rdf:type schema:CreativeWork
    129 sg:pub.10.1007/bf01231606 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015907927
    130 https://doi.org/10.1007/bf01231606
    131 rdf:type schema:CreativeWork
    132 sg:pub.10.1023/a:1009783824328 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000292060
    133 https://doi.org/10.1023/a:1009783824328
    134 rdf:type schema:CreativeWork
    135 grid-institutes:grid.6292.f schema:alternateName Corso di Laurea in Scienze dell’Informazione, Università di Bologna, via Sacchi 3, 47023, Cesena, Italy
    136 DEIS - CSITE-CNR - Università di Bologna, viale Risorgimento 2, 40136, Bologna, Italy
    137 schema:name Corso di Laurea in Scienze dell’Informazione, Università di Bologna, via Sacchi 3, 47023, Cesena, Italy
    138 DEIS - CSITE-CNR - Università di Bologna, viale Risorgimento 2, 40136, Bologna, Italy
    139 rdf:type schema:Organization
     




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


    ...