Çѱ¹°ø°£Á¤º¸ ÇÐȸÁö
Current Result Document :
ÇѱÛÁ¦¸ñ(Korean Title) |
SQR-Tree£ºÈ¿À²ÀûÀÎ °ø°£ ÁúÀÇ Ã³¸®¸¦ À§ÇÑ ÇÏÀ̺긮µå À妽º ±¸Á¶ |
¿µ¹®Á¦¸ñ(English Title) |
SQR-Tree : A Hybrid Index Structure for Efficient Spatial Query Processing |
ÀúÀÚ(Author) |
°È«±¸
½ÅÀμö
±èÁ¤ÁØ
ÇѱâÁØ
Hong-Koo Kang
In-Su Shin
Joung-Joon Kim
Ki-Joon Han
|
¿ø¹®¼ö·Ïó(Citation) |
VOL 19 NO. 02 PP. 0047 ~ 0056 (2011. 04) |
Çѱ۳»¿ë (Korean Abstract) |
´ëÇ¥ÀûÀÎ Æ®¸® ±â¹Ý °ø°£ À妽º ±¸Á¶´Â Å©°Ô R-Tree¿Í °°Àº µ¥ÀÌŸ ºÐÇÒ ±â¹Ý À妽º ±¸Á¶¿Í KD-Tree¿Í °°Àº °ø°£ ºÐÇÒ ±â¹Ý À妽º ±¸Á¶·Î ±¸ºÐµÇ¸ç, ÃÖ±Ù¿¡´Â À̵éÀÇ ÀåÁ¡À» °áÇÕÇÑ ÇÏÀ̺긮µå À妽º ±¸Á¶¿¡ ´ëÇÑ ¿¬±¸°¡ È°¹ßÈ÷ ÁøÇàµÇ°í ÀÖ´Ù. ±×·¯³ª, ±âÁ¸ ¿¬±¸¿¡¼´Â °ø°£ °´Ã¼°¡ »ðÀԵǴ ³ëµåÀÇ ºÐÇÒ °æ°è È®ÀåÀÌ ´Ù¸¥ ÀÌ¿ô ³ëµå¿¡ ¿¬¼âÀûÀ¸·Î ÀüÆÄµÇ¾î ³ëµå°£ °ãħÀÌ Áõ°¡ÇÏ°í ÁúÀÇ Ã³¸® ºñ¿ëÀÌ ³ô¾ÆÁö´Â ¹®Á¦°¡ ÀÖ´Ù. º» ³í¹®¿¡¼´Â ÀÌ·¯ÇÑ ¹®Á¦¸¦ ÇØ°áÇϱâ À§ÇÏ¿© È¿À²ÀûÀÎ ÁúÀÇ Ã³¸®¸¦ À§ÇÑ ÇÏÀ̺긮µå À妽º ±¸Á¶ÀÎ SQR-Tree¸¦ Á¦½ÃÇÑ´Ù. SQR-Tree´Â Å©±â¸¦ °®´Â °ø°£ °´Ã¼ 󸮿¡ ÀûÇÕÇϵµ·Ï Quad-Tree¸¦ È®ÀåÇÑ SQ-Tree(Spatial Quad-Tree)¿Í SQ-TreeÀÇ ¸®ÇÁ ³ëµå¸¶´Ù ¿¬°èµÇ¾î ½ÇÁ¦·Î °ø°£ °´Ã¼¸¦ ÀúÀåÇÏ´Â R-Tree°¡ °áÇÕµÈ À妽º ±¸Á¶ÀÌ´Ù. SQR-Tree´Â ³ëµå¸¶´Ù ÇÏÀ§ ³ëµå¸¦ Æ÷ÇÔÇÏ´Â MBRÀ» °¡Áö°í Àֱ⠶§¹®¿¡ ³ëµåÀÇ ºÐÇÒ °æ°è È®ÀåÀÌ µ¶¸³ÀûÀ¸·Î ÀÌ·ç¾îÁöµµ·Ï ÇÏ¿© ³ëµå°£ °ãħÀ» ÁÙ¿´´Ù. ±×¸®°í SQR-Tree¿¡¼ °ø°£ °´Ã¼´Â ºÐÇÒµÈ µ¥ÀÌŸ °ø°£¸¶´Ù Á¸ÀçÇÏ´Â ¿©·¯ R-Tree¿¡ ºÐ»ê ÀúÀåµÇ¸ç SQ-Tree°¡ ºÐÇÒµÈ µ¥ÀÌŸ °ø°£À» ½Äº°ÇÏ´Â ±â´ÉÀ» ¼öÇàÇÑ´Ù. µû¶ó¼ °ø°£ ÁúÀÇ Ã³¸®½Ã ÁúÀÇ ¿µ¿ª¿¡ ÇØ´çÇÏ´Â R-Tree¸¸ Á¢±ÙÇÏ¸é µÇ±â ¶§¹®¿¡ ÁúÀÇ Ã³¸® ºñ¿ëÀ» ÁÙÀÏ ¼ö ÀÖ´Ù. ¸¶Áö¸·À¸·Î ½ÇÇèÀ» ÅëÇØ SQR-TreeÀÇ ¿ì¼ö¼ºÀ» ÀÔÁõÇÏ¿´´Ù.
|
¿µ¹®³»¿ë (English Abstract) |
Typical tree-based spatial index structures are divided into a data-partitioning index structure such as R-Tree and a space-partitioning index structure such as KD-Tree. In recent years, researches on hybrid index structures combining advantages of these index structures have been performed extensively. However, because the split boundary extension of the node to which a new spatial object is inserted may extend split boundaries of other neighbor nodes in existing researches, overlaps between nodes are increased and the query processing cost is raised. In this paper, we propose a hybrid index structure, called SQR-Tree that can support efficient processing of spatial queries to solve these problems. SQR-Tree is a combination of SQ-Tree(Spatial Quad-Tree) which is an extended Quad-Tree to process non-size spatial objects and R-Tree which actually stores spatial objects associated with each leaf node of SQ-Tree. Because each SQR-Tree node has an MBR containing sub-nodes, the split boundary of a node will be extended independently and overlaps between nodes can be reduced. In addition, a spatial object is inserted into R-Tree in each split data space and SQ-Tree is used to identify each split data space. Since only R-Trees of SQR-Tree in the query area are accessed to process a spatial query, query processing cost can be reduced. Finally, we proved superiority of SQR-Tree through experiments.
|
Å°¿öµå(Keyword) |
´ë¿ë·® °ø°£ µ¥ÀÌŸ
ÇÏÀ̺긮µå À妽º ±¸Á¶
SQ-Tree
R-Tree
Large Spatial Data
Hybrid Index Structure
|
ÆÄÀÏ÷ºÎ |
PDF ´Ù¿î·Îµå
|