Index structures for temporal and multimedia databases

This thesis proposes index structures for efficient evaluation of temporal queries in temporal databases and similarity based queries in multimedia databases.; To support temporal operators and to increase the efficiency of temporal queries, indexing based on temporal attributes is required. A temporal database can support two notions of time. Valid time is the time when a data entity is valid in reality, and the transaction time is the time when a data entity is recorded in the database. In this thesis, methods for indexing time intervals in transaction time and valid time databases are proposed.; Transaction time databases are append only databases. Data is never deleted from the database, and data versions that were deleted or modified are stored as historical versions. This thesis proposes indexing current and historical versions of temporal entities separately to exploit the behavior of transaction time data. Two structures, namely IB+tree and AD*-tree, are proposed for indexing the historical data versions. IB+tree (Interval B+tree) is an augmented B+tree to support interval search queries. Similarly, AD*-tree is an augmented AD-tree (Append-Delete tree) which is a one-dimensional tree structure specifically designed for FIFO domains. Some experimental and analytical results are provided for evaluation of these proposed structures.; In valid time databases, temporal data versions can be inserted, deleted, or modified at any point in time. Furthermore, their lifespans can extend into the future. For indexing a dynamic set of valid time intervals, an indexing scheme that uses IB+trees with time-splits is proposed. Time-splits partition long intervals into disjoint subintervals and distribute them among several leaf nodes to increase efficiency of search operations, especially for timeslice queries. The effect of using time-splits on query performance is evaluated empirically. The extensions to IB+trees for handling valid time intervals that span into future and valid time intervals whose end points move along the current timeline are also shown.; In the context of multimedia databases, indexing methods for answering similarity based queries are studied. An indexing method for finding approximate matches in a collection of numerical sequences is proposed, and a general index structure for similarity based queries in metric spaces is introduced.; First problem considered is efficient matching and retrieval of sequences of different lengths. For similarity matching of sequences, a modified version of the edit distance function is used. For efficient retrieval of matching sequences, an indexing scheme based on lengths and relative distances between sequences is proposed.; Conventional index structures are designed to function in Euclidean domains. They cannot be directly used for non-Euclidean data (ex: text), and they are not as efficient for high dimensional data spaces. Distance based index structures are proposed for applications where the data domain is high dimensional, or the distance function used to compute distances between data objects is non-Euclidean. This thesis introduces a distance-based index structure, called mvp-tree (multi-vantage point tree) for similarity queries on high-dimensional metric spaces. The mvp-tree uses multiple reference points (vantage points) in each node to partition the data space into spherical shell-like regions in a hierarchical manner. It also utilizes the pre-computed distances at search time. The performance of mvp-tree is evaluated empirically, and the results are provided.