Thumbnail Image
Publication

Geometric Burrows-Wheeler Transform: Linking Range Searching and Text Indexing (extended abstract)

Chien, Yu-Feng
; 
Hon, Wing-Kai
; 
Shah, Rahul
; 
Vitter, Jeffrey Scott
Citations
Altmetric:
Abstract
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 can answer 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 [16]? We also introduce a reverse transform, called Points2Text, which converts a set of points into text. This transform allows us to derive the ¯rst 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.
Description
(c) 2008 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other users, including reprinting/ republishing this material for advertising or promotional purposes, creating new collective works for resale or redistribution to servers or lists, or reuse of any copyrighted components of this work in other works.
Date
2008
Journal Title
Journal ISSN
Volume Title
Publisher
IEEE
Collections
Provost Office Published Articles
Distinguished Professors Scholarly Works
Electrical Engineering and Computer Science Scholarly Works
Show all metadata
Files
Thumbnail Image
CHS08.geometricbw.pdf
Adobe PDF, 198.15 KB
Research Projects
Organizational Units
Journal Issue
Keywords
Citation
Y.-F. Chien, W.-K. Hon, R. Shah, and J. S. Vitter. “Geometric Burrows-Wheeler Transform: Linking Range Searching and Text Indexing,” in preparation. An extended abstract appears in Proceedings of the 2008 IEEE Data Compression Conference (DCC ’08), Snowbird, UT, March 2008. http://dx.doi.org/10.1109/DCC.2008.67
URI
https://hdl.handle.net/1808/7231
DOI
10.1109/DCC.2008.67
Embedded videos