Comparison of Clustering Algorithms in a Single User Environment through OO7 Benchmark View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1995

AUTHORS

Kadir Koc , Asuman Dogac , Cem Evrendilek

ABSTRACT

In this paper, we present a new clustering algorithm called the High Fan Out algorithm and then give the performance comparison of the High Fan Out (HFO) algorithm, Kemighan-Lin based algorithms, and the Probability Ranking Partitioning algorithm for a persistent C++(C**) implementation in a single user environment where the global request stream follows a pattern most of the time. The global request stream is obtained through OO7 Benchmark. It is shown than HFO algorithm performs the best when object sizes are uniform and the cache sizes are relatively large. We conclude with a table that indicates the best clustering algorithm to be used depending on the characteristics of the database application at hand and the restrictions imposed by the computer system. It is also indicated that, the performance of a clustering algorithm can not be based solely on the communication cost, or on the amount of internal fragmentation. On the contrary both of the measures should be taken into account to predict the number of cache misses. More... »

PAGES

77-89

References to SciGraph publications

  • 1996. A Preprocessor Approach to Persistent C++ in ADVANCES IN DATABASES AND INFORMATION SYSTEMS
  • Book

    TITLE

    East/West Database Workshop

    ISBN

    978-3-540-19946-5
    978-1-4471-3577-7

    Author Affiliations

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/978-1-4471-3577-7_6

    DOI

    http://dx.doi.org/10.1007/978-1-4471-3577-7_6

    DIMENSIONS

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


    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": "Middle East Technical University", 
              "id": "https://www.grid.ac/institutes/grid.6935.9", 
              "name": [
                "Software Research and Development Center Scientific and Technical Research Council of T\u00fcrkiye Dept. of Computer Engineering, Middle East Technical University, 06531\u00a0Ankara, T\u00fcrkiye"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Koc", 
            "givenName": "Kadir", 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Middle East Technical University", 
              "id": "https://www.grid.ac/institutes/grid.6935.9", 
              "name": [
                "Software Research and Development Center Scientific and Technical Research Council of T\u00fcrkiye Dept. of Computer Engineering, Middle East Technical University, 06531\u00a0Ankara, T\u00fcrkiye"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Dogac", 
            "givenName": "Asuman", 
            "id": "sg:person.01074167140.73", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01074167140.73"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Middle East Technical University", 
              "id": "https://www.grid.ac/institutes/grid.6935.9", 
              "name": [
                "Software Research and Development Center Scientific and Technical Research Council of T\u00fcrkiye Dept. of Computer Engineering, Middle East Technical University, 06531\u00a0Ankara, T\u00fcrkiye"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Evrendilek", 
            "givenName": "Cem", 
            "id": "sg:person.013633220171.70", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013633220171.70"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/978-1-4471-1486-4_16", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1010296669", 
              "https://doi.org/10.1007/978-1-4471-1486-4_16"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/190.194", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1010414189"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "1995", 
        "datePublishedReg": "1995-01-01", 
        "description": "In this paper, we present a new clustering algorithm called the High Fan Out algorithm and then give the performance comparison of the High Fan Out (HFO) algorithm, Kemighan-Lin based algorithms, and the Probability Ranking Partitioning algorithm for a persistent C++(C**) implementation in a single user environment where the global request stream follows a pattern most of the time. The global request stream is obtained through OO7 Benchmark. It is shown than HFO algorithm performs the best when object sizes are uniform and the cache sizes are relatively large. We conclude with a table that indicates the best clustering algorithm to be used depending on the characteristics of the database application at hand and the restrictions imposed by the computer system. It is also indicated that, the performance of a clustering algorithm can not be based solely on the communication cost, or on the amount of internal fragmentation. On the contrary both of the measures should be taken into account to predict the number of cache misses.", 
        "editor": [
          {
            "familyName": "Eder", 
            "givenName": "Johann", 
            "type": "Person"
          }, 
          {
            "familyName": "Kalinichenko", 
            "givenName": "Leonid A.", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/978-1-4471-3577-7_6", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": {
          "isbn": [
            "978-3-540-19946-5", 
            "978-1-4471-3577-7"
          ], 
          "name": "East/West Database Workshop", 
          "type": "Book"
        }, 
        "name": "Comparison of Clustering Algorithms in a Single User Environment through OO7 Benchmark", 
        "pagination": "77-89", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/978-1-4471-3577-7_6"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "0b130a07538171c72f87002e8a56365f2e9feffba45ed7c1a500ecdb39fd054f"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1002325866"
            ]
          }
        ], 
        "publisher": {
          "location": "London", 
          "name": "Springer London", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/978-1-4471-3577-7_6", 
          "https://app.dimensions.ai/details/publication/pub.1002325866"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-15T16:14", 
        "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_8675_00000244.jsonl", 
        "type": "Chapter", 
        "url": "http://link.springer.com/10.1007/978-1-4471-3577-7_6"
      }
    ]
     

    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-1-4471-3577-7_6'

    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-1-4471-3577-7_6'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-1-4471-3577-7_6'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-1-4471-3577-7_6'


     

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

    90 TRIPLES      23 PREDICATES      29 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/978-1-4471-3577-7_6 schema:about anzsrc-for:08
    2 anzsrc-for:0806
    3 schema:author Na9cacad6a69748c8be25fef56ca2f817
    4 schema:citation sg:pub.10.1007/978-1-4471-1486-4_16
    5 https://doi.org/10.1145/190.194
    6 schema:datePublished 1995
    7 schema:datePublishedReg 1995-01-01
    8 schema:description In this paper, we present a new clustering algorithm called the High Fan Out algorithm and then give the performance comparison of the High Fan Out (HFO) algorithm, Kemighan-Lin based algorithms, and the Probability Ranking Partitioning algorithm for a persistent C++(C**) implementation in a single user environment where the global request stream follows a pattern most of the time. The global request stream is obtained through OO7 Benchmark. It is shown than HFO algorithm performs the best when object sizes are uniform and the cache sizes are relatively large. We conclude with a table that indicates the best clustering algorithm to be used depending on the characteristics of the database application at hand and the restrictions imposed by the computer system. It is also indicated that, the performance of a clustering algorithm can not be based solely on the communication cost, or on the amount of internal fragmentation. On the contrary both of the measures should be taken into account to predict the number of cache misses.
    9 schema:editor Ndf64f7aed0e248bfb9c0140ac42f36ea
    10 schema:genre chapter
    11 schema:inLanguage en
    12 schema:isAccessibleForFree false
    13 schema:isPartOf N800d0c7802b24072b442f6a489df82db
    14 schema:name Comparison of Clustering Algorithms in a Single User Environment through OO7 Benchmark
    15 schema:pagination 77-89
    16 schema:productId Na024109dfc0740f7b4618047c59254ce
    17 Ne33d4385e48d467eb185dd8d61bb2697
    18 Nefe4491c50f7463e8e066481729c01a7
    19 schema:publisher Ne6a58a4c53ea41a6a616353c80e62b72
    20 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002325866
    21 https://doi.org/10.1007/978-1-4471-3577-7_6
    22 schema:sdDatePublished 2019-04-15T16:14
    23 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    24 schema:sdPublisher N0c0579769e04433f88a9743c64a86078
    25 schema:url http://link.springer.com/10.1007/978-1-4471-3577-7_6
    26 sgo:license sg:explorer/license/
    27 sgo:sdDataset chapters
    28 rdf:type schema:Chapter
    29 N029a5cb02b1e42e28c4bbfadb595c64d rdf:first sg:person.013633220171.70
    30 rdf:rest rdf:nil
    31 N0c0579769e04433f88a9743c64a86078 schema:name Springer Nature - SN SciGraph project
    32 rdf:type schema:Organization
    33 N21732bca08db456e949222412d75394c rdf:first sg:person.01074167140.73
    34 rdf:rest N029a5cb02b1e42e28c4bbfadb595c64d
    35 N47569f4946fe405ead46c997c46b36d6 schema:affiliation https://www.grid.ac/institutes/grid.6935.9
    36 schema:familyName Koc
    37 schema:givenName Kadir
    38 rdf:type schema:Person
    39 N67cbebfbf83549399aa84cc294a96a08 rdf:first Neacf8af632eb464aa0f59c124bf4e14d
    40 rdf:rest rdf:nil
    41 N800d0c7802b24072b442f6a489df82db schema:isbn 978-1-4471-3577-7
    42 978-3-540-19946-5
    43 schema:name East/West Database Workshop
    44 rdf:type schema:Book
    45 Na024109dfc0740f7b4618047c59254ce schema:name readcube_id
    46 schema:value 0b130a07538171c72f87002e8a56365f2e9feffba45ed7c1a500ecdb39fd054f
    47 rdf:type schema:PropertyValue
    48 Na9cacad6a69748c8be25fef56ca2f817 rdf:first N47569f4946fe405ead46c997c46b36d6
    49 rdf:rest N21732bca08db456e949222412d75394c
    50 Nbb47880a0689440db3b7a676eea044ca schema:familyName Eder
    51 schema:givenName Johann
    52 rdf:type schema:Person
    53 Ndf64f7aed0e248bfb9c0140ac42f36ea rdf:first Nbb47880a0689440db3b7a676eea044ca
    54 rdf:rest N67cbebfbf83549399aa84cc294a96a08
    55 Ne33d4385e48d467eb185dd8d61bb2697 schema:name dimensions_id
    56 schema:value pub.1002325866
    57 rdf:type schema:PropertyValue
    58 Ne6a58a4c53ea41a6a616353c80e62b72 schema:location London
    59 schema:name Springer London
    60 rdf:type schema:Organisation
    61 Neacf8af632eb464aa0f59c124bf4e14d schema:familyName Kalinichenko
    62 schema:givenName Leonid A.
    63 rdf:type schema:Person
    64 Nefe4491c50f7463e8e066481729c01a7 schema:name doi
    65 schema:value 10.1007/978-1-4471-3577-7_6
    66 rdf:type schema:PropertyValue
    67 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    68 schema:name Information and Computing Sciences
    69 rdf:type schema:DefinedTerm
    70 anzsrc-for:0806 schema:inDefinedTermSet anzsrc-for:
    71 schema:name Information Systems
    72 rdf:type schema:DefinedTerm
    73 sg:person.01074167140.73 schema:affiliation https://www.grid.ac/institutes/grid.6935.9
    74 schema:familyName Dogac
    75 schema:givenName Asuman
    76 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01074167140.73
    77 rdf:type schema:Person
    78 sg:person.013633220171.70 schema:affiliation https://www.grid.ac/institutes/grid.6935.9
    79 schema:familyName Evrendilek
    80 schema:givenName Cem
    81 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013633220171.70
    82 rdf:type schema:Person
    83 sg:pub.10.1007/978-1-4471-1486-4_16 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010296669
    84 https://doi.org/10.1007/978-1-4471-1486-4_16
    85 rdf:type schema:CreativeWork
    86 https://doi.org/10.1145/190.194 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010414189
    87 rdf:type schema:CreativeWork
    88 https://www.grid.ac/institutes/grid.6935.9 schema:alternateName Middle East Technical University
    89 schema:name Software Research and Development Center Scientific and Technical Research Council of Türkiye Dept. of Computer Engineering, Middle East Technical University, 06531 Ankara, Türkiye
    90 rdf:type schema:Organization
     




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


    ...