Uploaded image for project: 'Lucene - Core'
  1. Lucene - Core
  2. LUCENE-1514

ShingleMatrixFilter eaily throws StackOverFlow as the complexity of a matrix grows

    XMLWordPrintableJSON

    Details

    • Type: Improvement
    • Status: Closed
    • Priority: Major
    • Resolution: Fixed
    • Affects Version/s: 2.4
    • Fix Version/s: 2.9
    • Component/s: modules/analysis
    • Labels:
      None
    • Lucene Fields:
      New, Patch Available

      Description

      ShingleMatrixFilter#next makes a recursive function invocation when the current permutation iterator is exhausted or if the current state of the permutation iterator already has produced an identical shingle. In a not too complex matrix this will require a gigabyte sized stack per thread.

      My solution is to avoid the recursive invocation by refactoring like this:

      public Token next(final Token reusableToken) throws IOException {
          assert reusableToken != null;
          if (matrix == null) {
            matrix = new Matrix();
            // fill matrix with maximumShingleSize columns
            while (matrix.columns.size() < maximumShingleSize && readColumn()) {
              // this loop looks ugly
            }
          }
      
          // this loop exists in order to avoid recursive calls to the next method
          // as the complexity of a large matrix
          // then would require a multi gigabyte sized stack.
          Token token;
          do {
            token = produceNextToken(reusableToken);
          } while (token == request_next_token);
          return token;
        }
      
        
        private static final Token request_next_token = new Token();
      
        /**
         * This method exists in order to avoid reursive calls to the method
         * as the complexity of a fairlt small matrix then easily would require
         * a gigabyte sized stack per thread.
         *
         * @param reusableToken
         * @return null if exhausted, instance request_next_token if one more call is required for an answer, or instance parameter resuableToken.
         * @throws IOException
         */
        private Token produceNextToken(final Token reusableToken) throws IOException {
      
      

        Attachments

        1. LUCENE-1514.txt
          4 kB
          Karl Wettin

          Activity

            People

            • Assignee:
              karl.wettin Karl Wettin
              Reporter:
              karl.wettin Karl Wettin
            • Votes:
              0 Vote for this issue
              Watchers:
              0 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved: