Using B+-trees for processing of line segments in large spatial databases

被引:6
作者
Lin, Hung-Yi [1 ]
机构
[1] Taichung Inst Technol, Dept Logist Engn & Management, Taichung 404, Taiwan
关键词
spatial database; line segment-based database; B(+)-trees; GIS; line segments;
D O I
10.1007/s10844-007-0039-y
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
Points, lines, and regions are the three basic entities for constituting vector-based objects in spatial databases. Many indexing methods (G-tree, K-D-B tree, Quad-tree, PMR-tree, Grid-file, R-tree, and so on) have been widely discussed for handling point or region data. These traditional methods can efficiently organize point or region objects in a space into a hashing or hierarchical directory. They provide efficient access methods to meet the requirement of accurate retrievals. However, two problems are encountered when their techniques are applied to deal with line segments. The first is that representing line segments by means of point or region objects cannot exactly and properly preserve the spatial information about the proximities of line segments. The second problem is derived from the large dead space and overlapping areas in external and internal nodes of the hierarchical directory caused by the use of rectangles to enclose line objects. In this paper, we propose an indexing structure for line segments based on B(+)-tree to remedy these two problems. Through the experimental results, we demonstrate that our approach has significant improvement over the storage efficiency. In addition, the retrieval efficiency has also been significantly prompted as compared to the method using R-tree index scheme. These improvements derive mainly from the proposed data processing techniques and the new indexing method.
引用
收藏
页码:35 / 52
页数:18
相关论文
共 15 条
  • [1] MULTIDIMENSIONAL BINARY SEARCH TREES USED FOR ASSOCIATIVE SEARCHING
    BENTLEY, JL
    [J]. COMMUNICATIONS OF THE ACM, 1975, 18 (09) : 509 - 517
  • [2] BLANKEN H, 1990, PROCEEDINGS : 6TH INTERNATIONAL CONFERENCE ON DATA ENGINEERING, P380
  • [3] Multidimensional access methods
    Gaede, V
    Gunther, O
    [J]. ACM COMPUTING SURVEYS, 1998, 30 (02) : 170 - 231
  • [4] Guttman A., 1984, P ACM SIGMOD INT C M, P47, DOI DOI 10.1145/602259.602266
  • [5] HOEL EG, 1991, LECT NOTES COMPUT SC, V525, P237
  • [6] HOEL EG, 1992, QUALITATIVE COMPARIS, P205
  • [7] JAGADISH HV, 1990, P 16 INT C VER LARG, P614
  • [8] G-TREE - A NEW DATA STRUCTURE FOR ORGANIZING MULTIDIMENSIONAL DATA
    KUMAR, A
    [J]. IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING, 1994, 6 (02) : 341 - 347
  • [9] LINDENBAUM M, 2000, 34551 U MAR COMP SCI
  • [10] THE GRID FILE - AN ADAPTABLE, SYMMETRIC MULTIKEY FILE STRUCTURE
    NIEVERGELT, J
    HINTERBERGER, H
    SEVCIK, KC
    [J]. ACM TRANSACTIONS ON DATABASE SYSTEMS, 1984, 9 (01): : 38 - 71