On-Line Dynamic Index Hybrid Update Scheme Based on Self-Learning of Allocated Space

To improve time and space efficiencies of index maintenance, an on-line dynamic index hybrid update (ODIHU) technique is proposed based on self-learning of allocated space. Based on Zipf theorem, ODIHU appropriately estimates the number of short and long lists with theoretical analysis, and manages short and long lists with uniform storage model of distinguishing long and short lists based on link. ODIHU manages long list space with history-based adaptive learning allocation (HALA), and manages short list space with linear allocation (LA), exponential allocation (EA), and uniform allocation (UA). To decrease index and retrieval cost, ODIHU divides index data set into limited sections and controls index merge with schemes. Then ODIHU merges short lists with immediate merge, and merges long lists with improved Y-limited contiguous multiple merge scheme, which balances the trade-off of the time and space efficiencies effectively. Based on the proposed RABIF, ODIHU not only considers both index level and inverted list level updating, but also effectively improves time and space efficiencies of index updating.