Show simple item record

dc.contributor.authorChien, Yu-Feng
dc.contributor.authorHon, Wing-Kai
dc.contributor.authorShah, Rahul
dc.contributor.authorVitter, Jeffrey Scott
dc.date.accessioned2011-03-21T21:21:51Z
dc.date.available2011-03-21T21:21:51Z
dc.date.issued2008
dc.identifier.citationY.-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
dc.identifier.urihttp://hdl.handle.net/1808/7231
dc.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.
dc.description.abstractWe 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.
dc.language.isoen_US
dc.publisherIEEE
dc.titleGeometric Burrows-Wheeler Transform: Linking Range Searching and Text Indexing (extended abstract)
dc.typeArticle
kusw.kuauthorVitter, Jeffrey Scott
kusw.oastatusfullparticipation
dc.identifier.doi10.1109/DCC.2008.67
kusw.oaversionScholarly/refereed, author accepted manuscript
kusw.oapolicyThis item meets KU Open Access policy criteria.
dc.rights.accessrightsopenAccess


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record