Q-Gram Index Module

Detailed Description

This module contains a series of classes and functions to build a compact Q-Gram Index over a string T, with memory consumption and query time proportional to O(|T|) and O(log(unique(T))) respectively, where unique(T) is the number of unique q-grams in T. This is achieved by keeping a plain sorted list of the unique q-grams in T, together with an index of their occurrences in the original string T. This data-structure offers up to 5x higher construction speed and a potentially unbounded improvement in memory consumption compared to the Q-Group Index, though the query time is asymptotically higher.

Classes
struct	nvbio::QGramIndexViewCore< QGramVectorType, IndexVectorType, CoordVectorType >
struct	nvbio::QGramIndexCore< SystemTag, QGramType, IndexType, CoordType >
struct	nvbio::QGramIndexHost
struct	nvbio::QGramIndexDevice
struct	nvbio::QGramSetIndexHost
struct	nvbio::QGramSetIndexDevice
struct	nvbio::plain_view_subtype< QGramIndexHost >
struct	nvbio::plain_view_subtype< QGramIndexDevice >
struct	nvbio::plain_view_subtype< const QGramIndexHost >
struct	nvbio::plain_view_subtype< const QGramIndexDevice >
struct	nvbio::plain_view_subtype< QGramSetIndexHost >
struct	nvbio::plain_view_subtype< QGramSetIndexDevice >
struct	nvbio::plain_view_subtype< const QGramSetIndexHost >
struct	nvbio::plain_view_subtype< const QGramSetIndexDevice >
struct	nvbio::qgram_locate_functor< qgram_index_type >

Typedefs
typedef QGramIndexViewCore < uint64 *, uint32 *, uint32 * >	nvbio::QGramIndexView
typedef QGramIndexViewCore < uint64 *, uint32 *, uint2 * >	nvbio::QGramSetIndexView
typedef QGramIndexViewCore < const uint64 *, const uint32 *, const uint32 * >	nvbio::ConstQGramIndexView
typedef QGramIndexViewCore < const uint64 *, const uint32 *, const uint2 * >	nvbio::ConstQGramSetIndexView

Functions
template<typename SystemTag , typename QT , typename IT , typename CT >
QGramIndexViewCore< QT, IT, CT >	nvbio::plain_view (const QGramIndexViewCore< QT, IT, CT > qgram)
template<typename SystemTag , typename QT , typename IT , typename CT >
QGramIndexViewCore< QT *, IT *, CT * >	nvbio::plain_view (QGramIndexCore< SystemTag, QT, IT, CT > &qgram)
template<typename SystemTag , typename QT , typename IT , typename CT >
QGramIndexViewCore< const QT *, const IT *, const CT * >	nvbio::plain_view (const QGramIndexCore< SystemTag, QT, IT, CT > &qgram)

Typedef Documentation

typedef QGramIndexViewCore<const uint64*,const uint32*,const uint32*> nvbio::ConstQGramIndexView

Definition at line 564 of file qgram.h.

typedef QGramIndexViewCore<const uint64*,const uint32*,const uint2*> nvbio::ConstQGramSetIndexView

Definition at line 565 of file qgram.h.

typedef QGramIndexViewCore<uint64*,uint32*,uint32*> nvbio::QGramIndexView

Definition at line 562 of file qgram.h.

typedef QGramIndexViewCore<uint64*,uint32*,uint2*> nvbio::QGramSetIndexView

Definition at line 563 of file qgram.h.

Function Documentation

template<typename SystemTag , typename QT , typename IT , typename CT >

QGramIndexViewCore<QT,IT,CT> nvbio::plain_view

(

const QGramIndexViewCore< QT, IT, CT >

qgram)

return the plain view of a QGramIndexView, i.e. the object itself

Definition at line 736 of file qgram.h.

template<typename SystemTag , typename QT , typename IT , typename CT >

QGramIndexViewCore<QT*,IT*,CT*> nvbio::plain_view

(

QGramIndexCore< SystemTag, QT, IT, CT > &

qgram)

return the plain view of a QGramIndex

Definition at line 741 of file qgram.h.

template<typename SystemTag , typename QT , typename IT , typename CT >

QGramIndexViewCore<const QT*,const IT*,const CT*> nvbio::plain_view

(

const QGramIndexCore< SystemTag, QT, IT, CT > &

qgram)

return the plain view of a QGramIndex

Definition at line 759 of file qgram.h.