Compressed Indexes for Approximate Library Management

This paper investigates the approximate library management problem, which is to construct an index for a dynamic text collection L such that for any query pattern P and any integer k, we can report all k-error matches of P in L efficiently. Existing work either focussed on the static version of the problem or assumed k = 0. We observe that by combining several recent techniques, we can achieve the first compressed indexes that support efficient pattern queries and updating simultaneously.