Improving Real Time Search Performance using Inverted Index Entries Invalidation Strategies

• Published in: Journal of computer science and technology (La Plata) 2016-04, Vol.16 (1), p.6-13
• Main Authors: Ríssola, Esteban A, Gabriel Hernán Tolosa
• Format: Article
• Language: eng ; spa
• Subjects: Algorithms; Data structures; efficiency; index entry invalidator; Indexing; Real time; real time search; Retrieval; Search engines; User generated content; Windows (intervals)
• ISSN: 1666-6046; 1666-6038

The impressive rise of user-generated content on the web in the hands of sites like Twitter imposes new challenges to search systems. The concept of real-time search emerges, increasing the role that efficient indexing and retrieval algorithms play in this scenario. Thousands of new updates need to be processed in the very moment they are generated and users expect content to be “searchable” within seconds. This lead to the develop of efficient data structures and algorithms that may face this challenge efficiently. In this work, we introduce the concept of index entry invalidator, a strategy responsible for keeping track of the evolution of the underlying vocabulary and selectively invalidate and evict those inverted index entries that do not considerably degrade retrieval effectiveness. Consequently, the index becomes smaller and may increase overall efficiency. We introduce and evaluate two approaches based on Time-to-Live and Sliding Windows criteria. We also study the dynamics of the vocabulary using a real dataset while the evaluation is carry out using a search engine specifically designed for real-time indexing and search.