Path caching (extended abstract): a technique for optimal external searching

摘要: External 2-dimensional searching is a fundamental problem with many applications in relational, object-oriented, spatial, and temporal databases. For example, interval intersection can be reduced to 2-sided, indexing class hierarchies of objects 3-sided, searching. Path caching new technique that used transform number time/space efficient data structures for internal (such as segment trees, priority search trees) into I/O external ones. Let n the size database, B page size, t output query. Using path caching, we provide first structure optimal query time O(logBn+t/B) Furthermore, show requires small space overhead O(n÷Blog2log2B) simple enough admit dynamic updates O(logBn) amortized time. We also extend this handle query-time, at expense slightly higher storage update overheads.