Á¤º¸°úÇÐȸ ³í¹®Áö D : µ¥ÀÌŸº£À̽º
ÇѱÛÁ¦¸ñ(Korean Title) |
R-Æ®¸®¿¡¼ ºó¹øÇÑ º¯°æ ÁúÀÇ Ã³¸®¸¦ À§ÇÑ È¿À²ÀûÀÎ ±â¹ý |
¿µ¹®Á¦¸ñ(English Title) |
An Efficient Technique for Processing Frequent Updates in the R-tree |
ÀúÀÚ(Author) |
±Çµ¿¼·
ÀÌ»óÁØ
À̼®È£
|
¿ø¹®¼ö·Ïó(Citation) |
VOL 31 NO. 03 PP. 0261 ~ 0273 (2004. 06) |
Çѱ۳»¿ë (Korean Abstract) |
Á¤º¸ Åë½Å ±â¼úÀÇ ¹ß´ÞÀº µ¥ÀÌŸº£À̽º ºÐ¾ß¿¡µµ »õ·Î¿î ÀÀ¿ëµéÀ» ¸¸µé°í ÀÖ´Ù. ¿¹¸¦ µé¾î, ¼ö¸¹Àº °´Ã¼µéÀÇ À§Ä¡¸¦ ÃßÀûÇÏ´Â À̵¿ °´Ã¼ µ¥ÀÌŸº£À̽º³ª °¢Á¾ ¼¾¼µé·ÎºÎÅÍ µé¾î¿À´Â µ¥ÀÌŸ ½ºÆ®¸²À» ó¸®ÇÏ´Â ½ºÆ®¸² µ¥ÀÌŸº£À̽º¿¡¼ ´Ù·ç´Â µ¥ÀÌŸ´Â ÀϹÝÀûÀ¸·Î ¸Å¿ì ºü¸£°í ²÷ÀÓ¾øÀÌ º¯°æµÈ´Ù. ÇÏÁö¸¸, ÀüÅëÀûÀÎ µ¥ÀÌŸº£À̽º¿¡¼´Â µ¥ÀÌŸ¸¦ »ç¿ëÀÚÀÇ ¸í½ÃÀûÀÎ º¯°æÀÌ ÀÖ±â Àü±îÁö´Â º¯ÇÏÁö ¾Ê´Â »ó´ëÀûÀ¸·Î Á¤ÀûÀÎ °ÍÀ¸·Î °£ÁÖÇÏ°í Àֱ⠶§¹®¿¡, ÀüÅëÀûÀÎ µ¥ÀÌŸº£À̽º ½Ã½ºÅÛÀº ÀÌ·¯ÇÑ ²÷ÀÓ¾ø°í µ¿ÀûÀÎ µ¥ÀÌŸÀÇ º¯È¸¦ È¿À²ÀûÀ¸·Î ó¸®Çϴµ¥ ¹®Á¦¸¦ Áö´Ñ´Ù. ƯÈ÷ ´ÙÂ÷¿ø µ¥ÀÌŸ 󸮸¦ À§ÇÑ ´ëÇ¥Àû À妽º ±¸Á¶ÀÎ R-Æ®¸®ÀÇ °æ¿ì, µ¥ÀÌŸÀÇ »ðÀÔÀ̳ª »èÁ¦°¡ ¿¬¼ÓÀûÀÎ ³ëµåÀÇ ºÐÇÒÀ̳ª ÇÕº´À» À¯¹ßÇÏ°í ÀÖÀ¸¹Ç·Î ÀÌ·¯ÇÑ ¹®Á¦´Â ´õ ½É°¢ÇØÁø´Ù. º» ³í¹®¿¡¼´Â ÀÌ·¯ÇÑ ºó¹øÇÑ º¯°æ È¿À²ÀûÀ¸·Î ó¸®Çϱâ À§ÇÏ¿© »õ·Î¿î R-Æ®¸® °»½Å ±â¹ýÀÎ ¸®ÇÁ °»½Å ±â¹ýÀ» Á¦¾ÈÇÑ´Ù. ¸®ÇÁ °»½Å ±â¹ý¿¡¼´Â »õ·Î¿î µ¥ÀÌŸ°¡ ÀÌÀü¿¡ ¼ÓÇØÀÖ´ø ¸®ÇÁ ³ëµåÀÇ MBR ³»¿¡ ÀÖÀ¸¸é Àüü Æ®¸®¸¦ º¯°æÇÏÁö ¾Ê°í ÇØ´ç ¸®ÇÁ ³ëµå¸¸À» º¯°æ½ÃŲ´Ù. ÀÌ·¯ÇÑ ¸®ÇÁ °»½Å ó¸®¿Í ¸®ÇÁ ³ëµå¸¦ Á÷Á¢ Á¢±ÙÇÏ°Ô ÇØÁÖ´Â ¸®ÇÁ Á¢±Ù Çؽà Å×À̺íÀ» ÀÌ¿ëÇÏ¿© ¸®ÇÁ °»½Å ±â¹ýÀº µ¥ÀÌŸÀÇ º¯°æ ¿¬»ê ºñ¿ëÀ» Å©°Ô ÁÙÀδÙ. Á¦¾È±â¹ýÀº ±âÁ¸ R-Æ®¸®ÀÇ ¾Ë°í¸®Áò°ú ±¸Á¶¸¦ ±×´ë·Î ÀÌ¿ëÇÏ°í, R-Æ®¸®ÀÇ Á¤È®¼ºÀ» º¸ÀåÇϹǷΠ´Ù¾çÇÑ R-Æ®¸® º¯Á¾µé¿¡µµ Àû¿ë °¡´ÉÇÏ°í R-Æ®¸®¸¦ ÀÌ¿ëÇÏ´Â ´Ù¾çÇÑ ÀÀ¿ë ȯ°æ¿¡ ÀÌ¿ëÀÌ °¡´ÉÇÏ´Ù. º» ³í¹®¿¡¼´Â Á¦¾È ±â¹ýÀÌ ±âÁ¸ ±â¹ý¿¡ ´ëÇÏ¿© °¡Áö´Â °»½Å ¿¬»êÀÇ ºñ¿ë À̵æÀ» ¼öÇÐÀûÀ¸·Î ºÐ¼®ÇÏ¿´°í, ½ÇÇèÀ» ÅëÇÏ¿© Á¦¾È ±â¹ýÀÇ ¿ì¼ö¼ºÀ» È®ÀÎÇÏ¿´´Ù. |
¿µ¹®³»¿ë (English Abstract) |
Advances in information and communication technologies have been creating new classes of applications in the area of databases. For example, in moving object databases, which track positions of a lot of objects, or stream databases, which process data streams from a lot of sensors, data processed in such database systems are usually changed very rapidly and continuously. However, traditional database systems have a problem in processing these rapidly and continuously changing data because they suppose that a data item stored in the database remains constant until it is explicitly modified. The problem becomes more serious in the R-tree, which is a typical index structure for multidimensional data, because modifying data in the R-tree can generate cascading node splits or merges. To process frequent updates more efficiently, we propose a novel update technique for the R-tree, which we call the leaf-update technique. If a new value of a data item lies within the leaf MBR that the data item belongs, the leaf-update technique changes the leaf node only, not whole of the tree. Using this leaf-update manner and the leaf-access hash table for direct access to leaf nodes, the proposed technique can reduce update cost greatly. In addition, the leaf-update technique can be adopted in diverse variants of the R-tree and various applications that use the R-tree since it is based on the R-tree and it guarantees the correctness of the R-tree. In this paper, we prove the effectiveness of the leaf-update techniques theoretically and present experimental results that show that our technique outperforms traditional one. , |
Å°¿öµå(Keyword) |
½Ã°ø°£ µ¥ÀÌŸº£À̽º
R-Æ®¸®
À妽º ±¸Á¶
ÁúÀÇ Ã³¸®
À̵¿ °´Ã¼
¸®ÇÁ °»½Å ±â¹ý
R-tree
Index Structure
Query processing
|
ÆÄÀÏ÷ºÎ |
PDF ´Ù¿î·Îµå
|