loading...
Geometric Burrows-Wheeler Transform: Linking Range Searching and Text Indexing
March 25-March 27
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/DCC.2008.67Data Compression Conference (dcc 2008)
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
We introduce a new variant of the popular Burrows-Wheeler transform (BWT) called Geometric Burrows-Wheeler Transform (GBWT). Unlike BWT, which merely permutes the text, GBWT converts the text into a set of points in 2-dimensional geometry. Using this transform, we cananswer to many open questions in compressed text indexing: (1) Can compressed data structures be designed in external memory with similar performance as the uncompressed counterparts? (2) Can compressed data structures be designed for position restricted pattern matching? We also introduce a reverse transform, called??Points2Text, which converts a set of pointsinto text. This transform allows us to derive the FIRST known lower bounds in compressed text indexing. We show strong equivalence between data structural problems in geometric range searching and text pattern matching. This provides a way to derive new results in compressed text indexing by translating the results from range searching.
Index Terms:
Pattern Matching, Range Searching, Lower Bounds, Burrows-Wheeler
Citation:
Yu-Feng Chien, Wing-Kai Hon, Rahul Shah, Jeffrey Scott Vitter, "Geometric Burrows-Wheeler Transform: Linking Range Searching and Text Indexing," dcc, pp.252-261, Data Compression Conference (dcc 2008), 2008
Usage of this product signifies your acceptance of the Terms of Use.