Our original disclaimer (Apr. 2017)

1. A claim

This page concerns the following paper:

Optimal In-place Suffix Sorting, By Zhize Li, Jian Li and Hongwei Huo.

The paper was accepted by ICALP 2017, under the condition of merging with another ICALP submission by Keisuke Goto (arXiv version arXiv:1703.01009v2).

In the arXiv version, Goto made the following claim, which implies that his work is independent of ours.

In our paper, we have three major results. Goto’s paper only has one result, which is very similar to one of our major results (plus an easy corollary). Hence, the ICALP PC decided that we should merge the paper.

Actually, his result is much weaker than ours. We can allow the size of the alphabet $\Sigma$ to be $O(n)$, while he can only deal with the size is less than $n$, where $n$ is the length of the string $T$. More importantly, he requires the alphabet to be continuous, i.e., all characters in the alphabet should be appeared in the string $T$. E.g., if the alphabet is $\{1,2,3,4\}$, then the string $T=``3,1,4,3,4"$ is invalid in his algorithm since $2$ does not appear in $T$.

However, after carefully reading Goto’s paper (arXiv:1703.01009v2), we believe that his paper is not independent from ours. In particular, the main bulk of the paper was written after reading our paper. Moreover, some of the claims made in that paper about our paper are quite misleading (or incorrect). Hence, we refused the merge.

The main purpose of this page is to provide evidences to support our above claim.

2. Evidences

2.1 Time

Our draft was uploaded on arXiv:1610.08305 in Oct. 2016. The ICALP 2017 deadline is Feb. 2017. Goto uploaded his draft on arXiv:1703.01009 in Mar. 2017.

2.2 A strong evidence (One doesn’t need to read the technical content of the paper)

Goto (implicitly) used many of our observations, lemmas and tricks in his paper. We do not believe that one could independently come up with exactly the same set of new ideas and tricks as ours. Of course, Goto did make an effort in making his paper look sufficiently (but only superficially) different from ours, by changing notations and mixing our ideas with ones in previous work (such as the ICALP 2007 paper by Franceschini and Muthukrishnan).

In our paper, we first use the notation LF-entry/RF-entry. The notation didn’t exist before our work. The notation is not a difficult one, but is crucial for our new interior counter technique, which is a new key contribution of our paper, which allows us to solve the open problems.

In Goto’s paper, it has the same notation, yet denoted as LE/RE throughout his paper. However, he used LF in Figure 3 in Section 4.2 of his paper (see the following figures), which is exact the same as ours, but inconsistent with the text of his own paper. It implies that the author had read our paper when he was drawing his main figure.

The following two figures are extracted from the arXiv version of Goto’s paper.

Actually, he initially used LF after reading our paper, then he attempted to cover the evidence by using the latex command to replace all LF to LE. We found the above fact in the Latex source file of his paper (we downloaded from arXiv):

But unfortunately for him, changing the above command couldn’t replace the text in the figure. We notice the figure same as ours but inconsistent with the text of his paper. We believe this is a strong evidence.

We list the above figures of his paper and its corresponding parts in his Latex source file here.

Clearly, this indicates that the author was writing his entire paper after reading ours (and using our notations). Then, he tried to cover the fact by changing the notation to LE/RE. We believe the above strong evidence is already enough to identify his dishonest behavior.

Many technical parts of his paper are also very similar to ours (excluding what is known from the literature).

For example, Transition 7 (Sort L-suffixes from the sorted LMS-suffixes) is the main technical "contribution" of his paper (the length is about half of the length of all Transition 1-9). However, his step is sufficiently similar to our Step 1 (Induced sort all L-suffixes from the sorted LMS-suffixes) in Section 3.7. This is where we develop the interior counter trick, which is one of the main new tricks (in this trick we used LF-entry).

In sum, it is hard for us to believe that one can come up with an algorithm so similar to ours independently, with a notation name in the figure same as ours but inconsistent with other parts of the paper, just four months after we made our work available online. Note that the problem we solved was open for ten years.

New update (Jun. 2018):

In Jun. 2018, Mr. Goto has made a response to our above disclaimer.

He provided some screenshots trying to show that he started writing his paper before reading our paper, but also admitted that the completion of his paper was after reading our paper and the notation LF/RF in his algorithm was also borrowed from our paper.

We were unable to judge whether Mr. Goto really had solved the problem before reading our paper since the main bulk of his paper was written after reading our paper.

As requested by Mr. Goto, we also provide a link of the page containing his response, so that the reader can see both sides. His response can be found in https://github.com/kg86/sa-comment.