| 1 |
Ranked document selection
|
|
|
|
In: http://www.dcc.uchile.cl/~gnavarro/ps/swat14.pdf (2014)
|
|
BASE
|
|
Show details
|
|
|
| 2 |
I/O-efficient compressed text indexes: From theory to practice
|
|
|
|
In: http://faculty.cse.tamu.edu/jsv/Papers/CHSV10IOtextindexes.pdf (2010)
|
|
Abstract:
Pattern matching on text data has been a fundamental field of Computer Science for nearly 40 years. Databases supporting full-text indexing functionality on text data are now widely used by biologists. In the theoretical literature, the most popular internal-memory index structures are the suffix trees and the suffix arrays, and the most popular external-memory index structure is the string B-tree. However, the practical applicability of these indexes has been limited mainly because of their space consumption and I/O issues. These structures use a lot more space (almost 20 to 50 times more) than the original text data and are often disk-resident. Ferragina and Manzini (2005) and Grossi and Vitter (2005) gave the first compressed text indexes with efficient query times in the internal-memory model. Recently, Chien et al (2008) presented a compact text index in the external memory based on the concept of Geometric Burrows-Wheeler Transform. They also presented lower bounds which suggested that it may be hard to obtain a good index structure in the external memory. In this paper, we investigate this issue from a practical point of view. On the positive side we show an external-memory text indexing structure (based on R-trees and KD-trees) that saves space by about an order of magnitude as compared to the standard String B-tree. While saving space, these structures also maintain a comparable I/O efficiency to that of String B-tree. We also show various space vs I/O efficiency trade-offs for our structures. I.
|
|
URL: http://faculty.cse.tamu.edu/jsv/Papers/CHSV10IOtextindexes.pdf
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.205.9051
|
|
BASE
|
|
Hide details
|
|
|
| 3 |
On Entropy-Compressed Text Indexing in External Memory
|
|
|
|
In: http://faculty.cse.tamu.edu/jsv/Papers/HST09externaltextindexing.pdf (2009)
|
|
BASE
|
|
Show details
|
|
|
| 4 |
Space-Efficient Framework for Top-k String Retrieval Problems
|
|
|
|
In: http://www.cs.nthu.edu.tw/~wkhon/papers/HSV09.pdf
|
|
BASE
|
|
Show details
|
|
|
| 5 |
Space-Efficient Framework for Top-k String Retrieval Problems
|
|
|
|
In: http://faculty.cse.tamu.edu/jsv/Papers/HSV09topk.pdf
|
|
BASE
|
|
Show details
|
|
|
| 6 |
Top-k Term-Proximity in Succinct Space
|
|
|
|
In: http://www.dcc.uchile.cl/~gnavarro/ps/isaac14.pdf
|
|
BASE
|
|
Show details
|
|
|
|
|
