Serial and parallel methods for I/O efficient suffix tree construction
US8914415B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Jan 29, 2010 |
| Grant date | Dec 16, 2014 |
| Priority date | — |
| Expiry date | Aug 17, 2032 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F16/00
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
System and method for suffix tree creation for large input data/text streams. The methodology leverages the structure of suffix trees to build a suffix tree by simultaneously tiling accesses to both the input string as well as the partially constructed suffix tree. The end result enables the indexing of very large input strings and at the same time maintain a bounded working set size and a fixed memory footprint. The method is employed for serial processing. Further, a scalable parallel suffix tree construction is realized that is suitable for implementation on parallel distributed memory systems that use effective collective communication and in-network caching. The methodology is also applied for suffix link recovery in both serial and parallel implementations.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.