Scalable Algorithm for Distributed In-Memory Text Indexing

Text based search remains an important technique to retrieve data. Existing and emerging domains including the massive and rapidly changing Web, sensor networks, stream computing and others involve searching huge quantity of data coming at large rates of 10GB/s - 100GB/s. High input data rates in these applications impose real time constraints on indexing. This makes it necessary to have high indexing rates for large volumes of data. Future parallel architectures with storage class memories will pave the way for high speed in-memory text indexing, where index can be completely stored in a high capacity storage class memory.
We present sequential and distributed in-memory text indexing algorithms. These algorithms leverage our novel index data structures that make text document indexing and merging process more efficient. We compare our design with the indexing algorithm in CLucene and show that the asymptotic time complexity of our sequential indexing algorithm (O(R.γ/k)) is better than CLucene (O(R.γ/k * (log(R/k) + θ))), where R is the number of documents, γ and θ are document-term distribution parameters and k is the merge-factor parameter in index construction. We also present the asymptotic time complexity for our distributed indexing algorithm and show that it is better in scalability compared to distributed version of CLucene.
The experimental results of our sequential & distributed indexing algorithm using actual website data on an MPP architecture (BG/L) are also presented along with comparison to sequential & distributed indexing using CLucene. We demonstrate around 2x improvement in indexing performance for the sequential algorithm and around 3x – 7x improvement in indexing performance for the distributed algorithm.