Frequent update and efficient retrieval: an oxymoron on moving object indexes?

Abstract

Traditionally, indexes have been designed to facilitate fast retrieval of static objects. Moreover, updates are assumed to be infrequent and hence slow update speed can be tolerated. However, this assumption does not hold for new applications fueled by the advancement of GPS, wireless technologies and small but powerful digital devices. In these applications, objects are mobile and to track these objects their locations have to be updated frequently. Existing indexes no longer can keep up with the high update rates while providing speedy retrieval at the same time. There is a need for novel indexes to be designed for moving objects. In this paper, we examine various design issues that need to be addressed to support efficient retrieval of moving objects with frequent updates. 1