Threshold Interval Indexing Techniques for Complicated Uncertain Data

Uncertain data is an increasingly prevalent topic in database research, given the advance of instruments that inherently generate uncertainty in their data. In particular, the problem of indexing uncertain data for range queries has received considerable attention. This book presents a novel indexing strategy focusing on one-dimensional uncertain continuous data, called threshold interval indexing. Threshold interval indexing is able to balance I/O cost and computational cost to achieve an optimal overall query performance by using a dynamic interval tree and storing x-bounds. This book also presents two variants, called the strong threshold interval index and the hyper threshold interval index, which leverage x-bounds not only for pruning but also for accepting results. Furthermore, it presents more efficient memory-loaded versions of these indexes. An extensive set of experiments demonstrates the effectiveness and efficiency of the proposed indexing strategies.