Name
Title | ||
|---|---|---|
Efficient representations of row-sorted 1-variant matrices for parallel string applications |
Abstract | ||
|---|---|---|
We investigate the efficient storage of row-sorted 1-variant (m + 1) × (n + 1) matrices, m n, that have the following properties: the rows are sorted in strictly increasing order and the set of elements of each row differs only by one single element from the set of elements of the next row. It has been shown that row-sorted 1-variant matrices are important in several parallel string comparison applications. Due to the large amount of redundancy in the row elements, we investigate efficient data structures to store such matrices. In this paper we propose a representation that stores a row-sorted 1-variant matrix in O(m log m) space and access time of O(log m) and can be constructed in O(m log m) time. We thus seek a representation that constitutes a nice balance between access time, representation construction time, and space requirement. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1007/978-3-540-72905-1_6 | ICA3PP |
Keywords | Field | DocType |
row element,1-variant matrix,m log m,row-sorted 1-variant,representation construction time,access time,next row,efficient data structure,m n,log m,parallel string application,efficient representation,data structure,longest common subsequence | Row,Data structure,Discrete mathematics,Longest common subsequence problem,Longest increasing subsequence,Matrix (mathematics),Parallel algorithm,Computer science,Parallel computing,Row equivalence,Algorithm,Redundancy (engineering) | Conference |
Volume | ISSN | Citations |
4494 | 0302-9743 | 1 |
PageRank | References | Authors |
0.41 | 6 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Carlos Eduardo Rodrigues Alves | 1 | 28 | 3.75 |
| Edson Norberto Cáceres | 2 | 29 | 7.30 |
| Siang Wun Song | 3 | 18 | 4.21 |