[UIMA-2434] Feature structure removal from sorted index is very slow

• Type: Improvement
• Status: Resolved
• Priority: Major
• Resolution: Fixed
• Affects Version/s: 2.3.1SDK
• Fix Version/s: 2.4.1SDK
• Component/s: Core Java Framework
• Assignee: Marshall Schor
• Reporter: Mikhail Sogrin
• Created: 13/Jul/12 16:28
• Updated: 07/Nov/13 16:54
• Resolved: 17/Jun/13 15:48

Description

Removal of feature structures from sorted indexes (e.g. default index) is very slow. FSIntArrayIndex.remove() method performs two operations: linear search in the array until the given FS is found, followed by the shift of elements to the end of this array by one position to the left.

If many annotations (millions and more) are being deleted at once, this operation gets very very slow - much slower than adding these annotations in the first place. It seems to require O(N^2) time to remove N annotations.

One item is the linear search, which can be replaced by the binary search method, which is already implemented in the same class.

Second, array copy can be done with Java built-in method instead of a custom loop.

Ideally, a method for bulk removal of a collection of annotations would have been the most efficient, for example a method to remove all annotations of a given type.

Issue Links

• relates to: UIMA-3413 improve remove-from-index performance