NONG Ge

Ph.D (Computer Science)

Associate Prof.

Computer Science Department,

Sun Yat-sen University,

Guangzhou 510275, P.R.C.              

While (programming) skills++;

Welcome to drop me a web-visit, and hope you may find here something interesting :)

I got my Ph.D in 1999 from the computer science department of the Hong Kong University of Science and Technology. Then, I worked in STMicroelectronics as a senior researcher and joined the computer science department of the Sun Yat-Sen University in 2004.

Constructing Suffix Arrays

Recently, we have designed two novel algorithms for linear suffix array construction, i.e. the induced sorting (IS) and the d-critical sorting (DS) algorithms, which are presented in this draft (under review) "Two Efficient Algorithms for Linear Suffix Array Construction", including the sample code. If you have any comments about this work, welcome to send us a message, thanks! (May 2008)

The proposed IS algorithm has been applied in the following projects that we are currently aware of:

  • Yuta Mori has carried out an independent study on the time and space performance of our algorithms vs. the others. He also optimized the coding of our IS algorithm given in the appendix of the above draft, and rewrote the algorithm in C++. According to his report, the IS algorithm (with optimized coding, called SAIS) is the best among all in the study, including the Difference-Cover algorithm, the Deep-Shallow sorting algorithm, the Ko-Aluru algorithm and the Larsson-Sadakane algorithm. Here find the details with the code packages (if you fail to visit that site, may try this alternative link). The SAIS is used in this project (owned by Yuta too): libdivsufsort - a lightweight suffix sorting library. We appreciate Mori as an independent party to re-implement the IS algorithm disclosed in the above draft. (July 2008)
  • bwa - Burrows-Wheeler Alignment Tool, where "IS is the default algorithm due to its simplicity" for constructing BWT index. (August 2008)
  • In-place Update of Suffix Array while Recoding Words, where the IS algorithm was adopted by the Symbiose Project Team at INRIA/Irisa. (September 2008)
  • Describing and testing two new linear suffix array construction algorithms, an independent study conducted by Aur¨¦lien Bellet on the proposed IS and DS algorithms, where the algorithms are presented intuitively for fast catching up the key ideas. (April 2009)
    		•
    Recent Works

    [1] G. Nong, S. Zhang and W. H. Chan, Linear Time Suffix Array Construction Using D-Critical Substrings, Proceedings of 20th Combinatorial Pattern Matching (CPM), Jun. 2009, Lille, France. (draft in [pdf])

    [2]   G. Nong, S. Zhang and W. H. Chan, Linear Suffix Array Construction by Almost Pure Induced-Sorting, Proceedings of 19th IEEE Data Compression Conference (IEEE DCC), Mar. 2009. (draft in [pdf])

    [3] G. Nong, S. Zhang and W. H. Chan, Computing Inverse ST in Linear Complexity, Proceedings of 19th Combinatorial Pattern Matching (CPM), Jun. 2008, Pisa, Italy. (draft in [pdf] with some typos corrected)

    [4]   S. Zhang and G. Nong, Fast and Space Efficient Linear Suffix Array Construction, Proceedings of IEEE Data Compression Conference (IEEE DCC), Mar. 2008.

    [5]    G. Nong and S. Zhang, Efficient Algorithms for the Inverse Sort Transform, IEEE Transactions on Computers, Vol. 56, No. 11, Nov. 2007. [pdf]

    [6]    G. Nong, N. Situ and M. Hamdi, Delay Analysis of Combined Input-Crosspoint Queueing Switches, Proceedings of 16th IEEE International Conference on Computer Communications and Networks (IEEE ICCCN), Aug. 2007. [pdf]

    [7]    G. Nong and S. Zhang, Optimal Lightweight Construction of Suffix Arrays for Constant Alphabets, Proceedings of 10th Workshop on Algorithms and Data Structures (WADS), Aug. 2007, LNCS 4619. [pdf]

    [8]    G. Nong and S. Zhang, An Efficient Algorithm for the Inverse ST Problem, Proceedings of IEEE Data Compression Conference (IEEE DCC), Mar. 2007.

    [9]    G. Nong and S. Zhang, Unifying the Burrows-Wheeler and the Schindler Transforms, Proceedings of IEEE Data Compression Conference (IEEE DCC), Mar. 2006.

    [10]    G. Nong, S. Zhang and X. L. Lin, An Efficient MAC Protocol for Optical WDM Networks with Simulation Evaluation, Proceedings of 31st IEEE Conference on Local Computer Networks (IEEE LCN), 2006.

    [11]    G. Nong, S. Zhang and W. H. Chan, The Inverse Sort Transform Is Linear Computable, submitted to ACM Transactions on Algorithms.

    Well, still interested in what I have done? my past publications may give some idea.

    -- Last updated in April 2009 --