Complexity analysis of distributed database algorithm

W. S., Alfred LOO, Chris BLOOR, David GREY

    Research output: Book Chapters | Papers in Conference ProceedingsConference paper (refereed)Researchpeer-review

    6 Citations (Scopus)

    Abstract

    This paper presents the complexity analysis and empirical results of a distributed selection algorithm. The algorithm uses the statistical properties of the data file. The objective of the algorithm is to minimize the number of communication messages required for the whole selection process. The algorithm is designed to select the y th smallest key from a very large file which is physically distributed over many sites (stations). The size of the file is so large that it is not feasible or efficient to transfer all data to a single node as no node has sufficient memory space for internal sorting. The selection work will be shared by all sites involved and the load balancing is also ensured by the algorithm. The complexity of the algorithm is O(log log N/P) for a network with P stations and a file with N records.
    Original languageEnglish
    Title of host publicationInternational Series on Advances in High Performance Computing
    PublisherComputational Mechanics Publ, Ashurst, United Kingdom
    Pages135-143
    Number of pages9
    Publication statusPublished - 1 Jan 1997

    Fingerprint

    Sorting
    Resource allocation
    Data storage equipment
    Communication

    Cite this

    LOO, W. S. . A., BLOOR, C., & GREY, D. (1997). Complexity analysis of distributed database algorithm. In International Series on Advances in High Performance Computing (pp. 135-143). Computational Mechanics Publ, Ashurst, United Kingdom.
    LOO, W. S., Alfred ; BLOOR, Chris ; GREY, David. / Complexity analysis of distributed database algorithm. International Series on Advances in High Performance Computing. Computational Mechanics Publ, Ashurst, United Kingdom, 1997. pp. 135-143
    @inproceedings{35c04905f7e643278b3076ae1f8a5b09,
    title = "Complexity analysis of distributed database algorithm",
    abstract = "This paper presents the complexity analysis and empirical results of a distributed selection algorithm. The algorithm uses the statistical properties of the data file. The objective of the algorithm is to minimize the number of communication messages required for the whole selection process. The algorithm is designed to select the y th smallest key from a very large file which is physically distributed over many sites (stations). The size of the file is so large that it is not feasible or efficient to transfer all data to a single node as no node has sufficient memory space for internal sorting. The selection work will be shared by all sites involved and the load balancing is also ensured by the algorithm. The complexity of the algorithm is O(log log N/P) for a network with P stations and a file with N records.",
    author = "LOO, {W. S., Alfred} and Chris BLOOR and David GREY",
    year = "1997",
    month = "1",
    day = "1",
    language = "English",
    pages = "135--143",
    booktitle = "International Series on Advances in High Performance Computing",
    publisher = "Computational Mechanics Publ, Ashurst, United Kingdom",

    }

    LOO, WSA, BLOOR, C & GREY, D 1997, Complexity analysis of distributed database algorithm. in International Series on Advances in High Performance Computing. Computational Mechanics Publ, Ashurst, United Kingdom, pp. 135-143.

    Complexity analysis of distributed database algorithm. / LOO, W. S., Alfred; BLOOR, Chris; GREY, David.

    International Series on Advances in High Performance Computing. Computational Mechanics Publ, Ashurst, United Kingdom, 1997. p. 135-143.

    Research output: Book Chapters | Papers in Conference ProceedingsConference paper (refereed)Researchpeer-review

    TY - GEN

    T1 - Complexity analysis of distributed database algorithm

    AU - LOO, W. S., Alfred

    AU - BLOOR, Chris

    AU - GREY, David

    PY - 1997/1/1

    Y1 - 1997/1/1

    N2 - This paper presents the complexity analysis and empirical results of a distributed selection algorithm. The algorithm uses the statistical properties of the data file. The objective of the algorithm is to minimize the number of communication messages required for the whole selection process. The algorithm is designed to select the y th smallest key from a very large file which is physically distributed over many sites (stations). The size of the file is so large that it is not feasible or efficient to transfer all data to a single node as no node has sufficient memory space for internal sorting. The selection work will be shared by all sites involved and the load balancing is also ensured by the algorithm. The complexity of the algorithm is O(log log N/P) for a network with P stations and a file with N records.

    AB - This paper presents the complexity analysis and empirical results of a distributed selection algorithm. The algorithm uses the statistical properties of the data file. The objective of the algorithm is to minimize the number of communication messages required for the whole selection process. The algorithm is designed to select the y th smallest key from a very large file which is physically distributed over many sites (stations). The size of the file is so large that it is not feasible or efficient to transfer all data to a single node as no node has sufficient memory space for internal sorting. The selection work will be shared by all sites involved and the load balancing is also ensured by the algorithm. The complexity of the algorithm is O(log log N/P) for a network with P stations and a file with N records.

    UR - https://www.witpress.com/elibrary/wit-transactions-on-information-and-communication-technologies/18/7868

    UR - http://commons.ln.edu.hk/sw_master/6955

    M3 - Conference paper (refereed)

    SP - 135

    EP - 143

    BT - International Series on Advances in High Performance Computing

    PB - Computational Mechanics Publ, Ashurst, United Kingdom

    ER -

    LOO WSA, BLOOR C, GREY D. Complexity analysis of distributed database algorithm. In International Series on Advances in High Performance Computing. Computational Mechanics Publ, Ashurst, United Kingdom. 1997. p. 135-143