NVBIO
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Public Types | Public Methods | Public Members | List of all members
nvbio::QGramFilter< device_tag, qgram_index_type, query_iterator, index_iterator > Struct Template Reference

Detailed description

template< typename qgram_index_type, typename query_iterator, typename index_iterator>
struct nvbio::QGramFilter< device_tag, qgram_index_type, query_iterator, index_iterator >

This class implements a q-gram filter which can be used to find and filter matches between an arbitrary set of indexed query q-grams, representing q-grams of a given text, and a q-gram index. The q-gram index can be either a simple string index or a string-set index.

For string q-gram indices, the filter will return an ordered set of (qgram-pos,query-pos) pairs, where qgram-pos is the index of the hit into the string used to build qgram-index, and query-pos corresponds to one of the input query q-gram indices.
For string-set q-gram indices, the filter will return an ordered set of (string-id,string-pos,query-pos) pairs (encoded as uint4), where string-id is the index of the hit into the string-set used to build qgram-index, and query-pos corresponds to one of the input query q-gram indices.
Furthermore, the filter offers the ability to merge hits by diagonal bucket: in this case, the output type will be either a simple uint32 linear coordinate describing the diagonal, or a (string-id,diagonal) for string-set indices.

Definition at line 214 of file filter.h.

#include <filter.h>

Inheritance diagram for nvbio::QGramFilter< device_tag, qgram_index_type, query_iterator, index_iterator >:
nvbio::QGramFilterDevice< qgram_index_type, query_iterator, index_iterator >

Public Types

typedef device_tag system_tag
 
typedef plain_view_subtype
< const qgram_index_type >
::type 
qgram_index_view
 
typedef
qgram_index_type::coord_type 
coord_type
 the coordinate type of the q-gram index, uint32|uint2 More...
 
typedef if_equal< coord_type,
uint32, uint2, uint4 >::type 
hit_type
 
typedef if_equal< coord_type,
uint32, uint32, uint2 >::type 
diagonal_type
 

Public Methods

uint64 rank (const qgram_index_type &qgram_index, const uint32 n_queries, const query_iterator queries, const index_iterator indices)
 
template<typename hits_iterator >
void locate (const uint64 begin, const uint64 end, hits_iterator hits)
 
template<typename hits_iterator , typename output_iterator >
void diagonals (const uint32 n_hits, const hits_iterator hits, output_iterator diags, const uint32 interval=1)
 
template<typename hits_iterator , typename output_iterator , typename count_iterator >
uint32 merge (const uint32 interval, const uint32 n_hits, const hits_iterator hits, output_iterator merged_hits, count_iterator merged_counts)
 
const uint2 * ranges () const
 
const uint64ranks () const
 

Public Members

uint32 m_n_queries
 
query_iterator m_queries
 
index_iterator m_indices
 
qgram_index_view m_qgram_index
 
uint64 m_n_occurrences
 
thrust::device_vector< uint2 > m_ranges
 
thrust::device_vector< uint64m_slots
 
thrust::device_vector
< diagonal_type
m_diags
 
thrust::device_vector< uint8d_temp_storage
 

Member Typedef Documentation

template<typename qgram_index_type , typename query_iterator , typename index_iterator >
typedef qgram_index_type::coord_type nvbio::QGramFilter< device_tag, qgram_index_type, query_iterator, index_iterator >::coord_type

the coordinate type of the q-gram index, uint32|uint2

Definition at line 220 of file filter.h.

template<typename qgram_index_type , typename query_iterator , typename index_iterator >
typedef if_equal<coord_type, uint32, uint32, uint2>::type nvbio::QGramFilter< device_tag, qgram_index_type, query_iterator, index_iterator >::diagonal_type

Definition at line 226 of file filter.h.

template<typename qgram_index_type , typename query_iterator , typename index_iterator >
typedef if_equal<coord_type, uint32, uint2, uint4>::type nvbio::QGramFilter< device_tag, qgram_index_type, query_iterator, index_iterator >::hit_type

the type of the hits will be either a uint2, if qgram_index_type is a string index, or a uint4 if it is a string-set index (the last entry of the uint4 is unused)

Definition at line 225 of file filter.h.

template<typename qgram_index_type , typename query_iterator , typename index_iterator >
typedef plain_view_subtype<const qgram_index_type>::type nvbio::QGramFilter< device_tag, qgram_index_type, query_iterator, index_iterator >::qgram_index_view

Definition at line 218 of file filter.h.

template<typename qgram_index_type , typename query_iterator , typename index_iterator >
typedef device_tag nvbio::QGramFilter< device_tag, qgram_index_type, query_iterator, index_iterator >::system_tag

Definition at line 216 of file filter.h.

Member Function Documentation

template<typename qgram_index_type , typename query_iterator , typename index_iterator >
template<typename hits_iterator , typename output_iterator >
void nvbio::QGramFilter< device_tag, qgram_index_type, query_iterator, index_iterator >::diagonals ( const uint32  n_hits,
const hits_iterator  hits,
output_iterator  diags,
const uint32  interval = 1 
)

simply convert hits to diagonal coordinates

Template Parameters
hits_iteratora hit_iterator iterator
output_iteratora diagonal_type iterator
Parameters
n_hitsthe number of input hits
hitsthe input hits
diagsthe output diagonals
intervalthe snapping interval

Definition at line 426 of file filter_inl.h.

template<typename qgram_index_type , typename query_iterator , typename index_iterator >
template<typename hits_iterator >
void nvbio::QGramFilter< device_tag, qgram_index_type, query_iterator, index_iterator >::locate ( const uint64  begin,
const uint64  end,
hits_iterator  hits 
)

enumerate all hits in a given range

hits_iterator a uint2 iterator

Definition at line 395 of file filter_inl.h.

template<typename qgram_index_type , typename query_iterator , typename index_iterator >
template<typename hits_iterator , typename output_iterator , typename count_iterator >
uint32 nvbio::QGramFilter< device_tag, qgram_index_type, query_iterator, index_iterator >::merge ( const uint32  interval,
const uint32  n_hits,
const hits_iterator  hits,
output_iterator  merged_hits,
count_iterator  merged_counts 
)

merge hits falling within the same diagonal interval; given a vector of hits, this method will return a compacted list of hits snapped to the closest sample diagonal (i.e. multiple of the given interval), together with a counts vector providing their multiplicity, i.e. the number of hits falling on the same spot

Template Parameters
hits_iteratora hit_iterator iterator
output_iteratora diagonal_type iterator
counts_iteratora uint8|uint16|uint32|uint64 iterator
Parameters
intervalthe merging interval
n_hitsthe number of input hits
hitsthe input hits
merged_hitsthe output merged hits
merged_countsthe output merged counts
Returns
the number of merged hits

Definition at line 455 of file filter_inl.h.

template<typename qgram_index_type , typename query_iterator , typename index_iterator >
const uint2* nvbio::QGramFilter< device_tag, qgram_index_type, query_iterator, index_iterator >::ranges ( ) const
inline

return the individual ranges of the ranked queries

Definition at line 297 of file filter.h.

template<typename qgram_index_type , typename query_iterator , typename index_iterator >
uint64 nvbio::QGramFilter< device_tag, qgram_index_type, query_iterator, index_iterator >::rank ( const qgram_index_type &  qgram_index,
const uint32  n_queries,
const query_iterator  queries,
const index_iterator  indices 
)

enact the q-gram filter on a q-gram index and a set of indexed query q-grams;
note: the q-gram index and the query q-gram and index iterators will be cached inside the filter for any follow-up method calls (to e.g. locate() and merge())

Parameters
qgram_indexthe q-gram index
n_queriesthe number of query q-grams
queriesthe query q-grams
indicesthe query indices

Definition at line 345 of file filter_inl.h.

template<typename qgram_index_type , typename query_iterator , typename index_iterator >
const uint64* nvbio::QGramFilter< device_tag, qgram_index_type, query_iterator, index_iterator >::ranks ( ) const
inline

return the global ranks of the output hits (i.e. the range [ranks[i], ranks[i+1]) identifies the position of the hits corresponding to the i-th query in the locate output)

Definition at line 302 of file filter.h.

Member Data Documentation

template<typename qgram_index_type , typename query_iterator , typename index_iterator >
thrust::device_vector<uint8> nvbio::QGramFilter< device_tag, qgram_index_type, query_iterator, index_iterator >::d_temp_storage

Definition at line 312 of file filter.h.

template<typename qgram_index_type , typename query_iterator , typename index_iterator >
thrust::device_vector<diagonal_type> nvbio::QGramFilter< device_tag, qgram_index_type, query_iterator, index_iterator >::m_diags

Definition at line 311 of file filter.h.

template<typename qgram_index_type , typename query_iterator , typename index_iterator >
index_iterator nvbio::QGramFilter< device_tag, qgram_index_type, query_iterator, index_iterator >::m_indices

Definition at line 306 of file filter.h.

template<typename qgram_index_type , typename query_iterator , typename index_iterator >
uint64 nvbio::QGramFilter< device_tag, qgram_index_type, query_iterator, index_iterator >::m_n_occurrences

Definition at line 308 of file filter.h.

template<typename qgram_index_type , typename query_iterator , typename index_iterator >
uint32 nvbio::QGramFilter< device_tag, qgram_index_type, query_iterator, index_iterator >::m_n_queries

Definition at line 304 of file filter.h.

template<typename qgram_index_type , typename query_iterator , typename index_iterator >
qgram_index_view nvbio::QGramFilter< device_tag, qgram_index_type, query_iterator, index_iterator >::m_qgram_index

Definition at line 307 of file filter.h.

template<typename qgram_index_type , typename query_iterator , typename index_iterator >
query_iterator nvbio::QGramFilter< device_tag, qgram_index_type, query_iterator, index_iterator >::m_queries

Definition at line 305 of file filter.h.

template<typename qgram_index_type , typename query_iterator , typename index_iterator >
thrust::device_vector<uint2> nvbio::QGramFilter< device_tag, qgram_index_type, query_iterator, index_iterator >::m_ranges

Definition at line 309 of file filter.h.

template<typename qgram_index_type , typename query_iterator , typename index_iterator >
thrust::device_vector<uint64> nvbio::QGramFilter< device_tag, qgram_index_type, query_iterator, index_iterator >::m_slots

Definition at line 310 of file filter.h.


The documentation for this struct was generated from the following files: