Doorkeeper

Talk by Prof. Srinivasa Rao Satti (Seoul National University)

Wed, 28 Nov 2018 09:30 - 10:30 JST

RIKEN AIP

Nihonbashi 1-chome Mitsui Building, 15th floor, 1-4-1 Nihonbashi, Chuo-ku, Tokyo 103-0027, Japan

Register

Registration is closed

Get invited to future events

Free admission

Description

Title: Dynamic compressed string representations supporting random access

Abstract:
In this talk I will present a scheme for storing a dynamic string S in compressed form, while permitting following operations directly on the compressed representation of S: (a) access a substring of S; (b) replace, insert or delete a symbol in S; (c) count how many occurrences of a given symbol appear in any given prefix of S (called rank operation); and (d) locate the position of the i-th occurrence of a symbol inside S (called select operation). An important application of this result is in Compressed Random Access Memory (CRAM), where one can represent the memory of a computer in compressed form while being able to support random access efficiently (without decompressing).

These results extend or improve the bounds of previous work by Ferragina and Venturini [TCS, 2007], Jansson et al. [ICALP, 2012], and Nekrich and Navarro [SODA, 2013].

About this community

RIKEN AIP Public

RIKEN AIP Public

Public events of RIKEN Center for Advanced Intelligence Project (AIP)

Join community