History-independence
Theodoros Tzouramanis · 2012
The deterministic tree-based database indexing structures unintentionally retain "additional" information about previous operations records of the index itself and about the database users' past activities. Privacy is jeopardized when a user gains illegitimate access to an indexing structure and accesses this "additional" confidential information from the internal representation of the index. This paper is the first to explore the design of history-independent access methods for spatial and multidimensional databases and proposes the History-Independent R-tree (HIR-tree), an R-tree variant which does not reveal information about the sequence of insertions, deletions and updates that have been applied to it and only reveals the outcome of these historical operations. It differs from the traditional spatial access methods in that the HIR-tree has the additional property of hiding its modification history. This property is achieved through the use of randomization by the update algorithms.