Sort-based query-adaptive loading of R-trees

摘要: Bulk-loading of R-trees has been an important problem in academia and industry for more than twenty years. Current algorithms create without any information about the expected query profile. However, profiles are extremely useful design efficient indexes. In this paper, we address deficiency present query-adaptive building optimally designed a given Since optimal R-tree loading is NP-hard (even tuning structure to profile), provide efficient, easy implement heuristics. Our sort-based consist two steps: First, sorting orders identified resulting better those obtained from standard space-filling curves. Second, order, propose dynamic programming algorithm generating linear runtime. experimental results confirm that our generally significantly ones algorithms, even when profile unknown.