NDLI: The compressed permuterm index

Please wait, while we are loading the content...

ACM Transactions on Algorithms (TALG) : Volume 13

ACM Transactions on Algorithms (TALG) : Volume 12

ACM Transactions on Algorithms (TALG) : Volume 11

ACM Transactions on Algorithms (TALG) : Volume 10

ACM Transactions on Algorithms (TALG) : Volume 9

ACM Transactions on Algorithms (TALG) : Volume 8

ACM Transactions on Algorithms (TALG) : Volume 7

Issue 4, September 2011

Issue 3, July 2011

Issue 2, March 2011

Issue 1, November 2010

Computing large matchings fast

Approximation algorithms for the sex-equal stable marriage problem

A faster algorithm for computing the girth of planar and bounded genus graphs

Length-bounded cuts and flows

Additive spanners and (α, β)-spanners

On the bicriteria k-server problem

On the online unit clustering problem

Clustering lines in high-dimensional space: Classification of incomplete data

Geodesic Fréchet distance inside a simple polygon

The compressed permuterm index

I/O-efficient batched union-find and its applications to terrain analysis

How to probe for an extreme value

Taxes for linear atomic congestion games

ACM Transactions on Algorithms (TALG) : Volume 6

ACM Transactions on Algorithms (TALG) : Volume 5

ACM Transactions on Algorithms (TALG) : Volume 4

ACM Transactions on Algorithms (TALG) : Volume 3

ACM Transactions on Algorithms (TALG) : Volume 2

ACM Transactions on Algorithms (TALG) : Volume 1

The compressed permuterm index

Content Provider	ACM Digital Library
Author	Ferragina, Paolo Venturini, Rossano
Copyright Year	2010
Abstract	The Permuterm index [Garfield 1976] is a time-efficient and elegant solution to the string dictionary problem in which pattern queries may possibly include one wild-card symbol (called Tolerant Retrieval problem). Unfortunately the Permuterm index is space inefficient because it quadruples the dictionary size. In this article we propose the $\textit{Compressed}$ Permuterm Index which solves the Tolerant Retrieval problem in time proportional to the length of the searched pattern, and space close to the $\textit{k}th$ order empirical entropy of the indexed dictionary. We also design a $\textit{dynamic}$ version of this index that allows to efficiently manage insertion in, and deletion from, the dictionary of individual strings. The result is based on a simple variant of the Burrows-Wheeler Transform, defined on a dictionary of strings of variable length, that allows to efficiently solve the Tolerant Retrieval problem via known (dynamic) compressed indexes [Navarro and Mäkinen 2007]. We will complement our theoretical study with a significant set of experiments that show that the Compressed Permuterm Index supports fast queries within a space occupancy that is close to the one achievable by compressing the string dictionary via gzip or bzip. This improves known approaches based on Front-Coding [Witten et al. 1999] by more than 50% in absolute space occupancy, still guaranteeing comparable query time.
Starting Page	1
Ending Page	21
Page Count	21
File Format	PDF
ISSN	15496325
e-ISSN	15496333
DOI	10.1145/1868237.1868248
Volume Number	7
Issue Number	1
Journal	ACM Transactions on Algorithms (TALG)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2010-12-08
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Burrows-Wheeler transform Compressed index Indexing data structure Permuterm String dictionary
Content Type	Text
Resource Type	Article
Subject	Mathematics

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Compressed permuterm index

Compressed permuterm index

Compressed permuterm index (2007)

Compressed permuterm index

Compressed Cache-Oblivious String B-Tree

Geometric burrows-wheeler transform: Linking range searching and text indexing

Indexing compressed text

Compressed representations of sequences and full-text indexes

A Space-Efficient Construction of the Burrows-Wheeler Transform for Genomic Data

The compressed permuterm index

Similar Documents

Compressed permuterm index

Compressed permuterm index

Compressed permuterm index (2007)

Compressed permuterm index

Compressed Cache-Oblivious String B-Tree

Geometric burrows-wheeler transform: Linking range searching and text indexing

Indexing compressed text

Compressed representations of sequences and full-text indexes

A Space-Efficient Construction of the Burrows-Wheeler Transform for Genomic Data

The compressed permuterm index