Á¤º¸Ã³¸®ÇÐȸ ³í¹®Áö ¼ÒÇÁÆ®¿þ¾î ¹× µ¥ÀÌÅÍ °øÇÐ
Current Result Document :
ÇѱÛÁ¦¸ñ(Korean Title) |
´ë¿ë·® ±×·¡ÇÁ¿¡¼ k-Â÷¼ö À妽º Å×À̺íÀ» ÀÌ¿ëÇÑ RDBMS ±â¹ÝÀÇ È¿À²ÀûÀÎ ÃÖ´Ü °æ·Î Ž»ö ±â¹ý |
¿µ¹®Á¦¸ñ(English Title) |
RDBMS Based Efficient Method for Shortest Path Searching Over Large Graphs Using K-degree Index Table |
ÀúÀÚ(Author) |
È«ÁöÇý
Çѿ뱸
ÀÌ¿µ±¸
Jihye Hong
Yongkoo Han
Young-Koo Lee
|
¿ø¹®¼ö·Ïó(Citation) |
VOL 03 NO. 05 PP. 0179 ~ 0186 (2014. 05) |
Çѱ۳»¿ë (Korean Abstract) |
¼Ò¼È ³×Æ®¿öÅ©, À¥ ÆäÀÌÁö ¸µÅ©, ±³Åë ³×Æ®¿öÅ© µî°ú °°Àº ÃÖ±ÙÀÇ ³×Æ®¿öÅ©µéÀº ³ëµå¿Í ¿¡ÁöÀÇ ¼ö°¡ ¹æ´ëÇÑ ºò µ¥ÀÌÅÍÀÌ´Ù. ¼Ò¼È ³×Æ®¿öÅ© ¼ºñ½º³ª ³×ºñ°ÔÀÌ¼Ç ¼ºñ½º¿Í °°ÀÌ ÀÌ¿Í °°Àº ³×Æ®¿öÅ©¸¦ ÀÌ¿ëÇÏ´Â ¾ÖÇø®ÄÉÀ̼ÇÀÌ ¸¹¾ÆÁö°í ÀÖ´Ù. ´ë¿ë·® ³×Æ®¿öÅ©´Â Àüü¸¦ ¸Þ¸ð¸®¿¡ ÀûÀçÇÒ ¼ö ¾ø¾î, ±âÁ¸ÀÇ ³×Æ®¿öÅ© ºÐ¼® ±â¼úÀ» È°¿ëÇÒ ¼ö ¾ø´Ù. ÃÖ±Ù ´ë¿ë·® ±×·¡ÇÁÀÇ È¿À²Àû Ž»öÀ» Á¦°øÇÏ´Â RDB ±â¹Ý ¿¬»êÀÚµéÀÌ ÇÁ·¹ÀÓ¿öÅ©(Frontier-expand-merge framework, FEM)·Î Á¦¾ÈµÇ¾ú´Ù. FEMÀº È¿À²ÀûÀÎ ÃÖ´Ü °æ·Î Ž»öÀ» À§ÇØ ºÎºÐ ÃÖ´Ü °æ·Î¸¦ ÀúÀåÇÏ´Â RDB ±â¹ÝÀÇ À妽º Å×À̺íÀ» ±¸ÃàÇÏ¿´´Ù. ±×·¯³ª FEMÀÇ À妽º Å×À̺íÀº ÃÖ´Ü °æ·Î¿¡ Æ÷ÇÔµÉ È®·üº¸´Ù À妽ºÀÇ °Å¸®¿¡ ÀÇÇØ °áÁ¤µÇ±â ¶§¹®¿¡ À妽º Å×À̺í ÂüÁ¶À²ÀÌ ¶³¾îÁø´Ù. º» ³í¹®¿¡¼´Â È¿À²ÀûÀÎ ÃÖ´Ü °æ·Î Ž»öÀ» Áö¿øÇÏ´Â À妽º ÂüÁ¶À²ÀÌ ³ôÀº Â÷¼ö°¡ Å« ³ëµåµéÀ» ÀÌ¿ëÇÑ À妽º Å×ÀÌºí ±¸Ãà ±â¹ýÀ» Á¦¾ÈÇÑ´Ù. ½ÇÇèÀ» ÅëÇÏ¿© Á¦¾ÈÇÏ´Â À妽º Å×ÀÌºí ±¸Ãà ±â¹ýÀÌ ½Ç¼¼°è µ¥ÀÌÅÍ ¼Â¿¡¼ È¿À²ÀûÀÎ ÃÖ´Ü °æ·Î Ž»öÀ» Áö¿øÇÔÀ» º¸ÀδÙ.
|
¿µ¹®³»¿ë (English Abstract) |
Current networks such as social network, web page link, traffic network are big data which have the large numbers of nodes and edges. Many applications such as social network services and navigation systems use these networks. Since big networks are not fit into the memory, existing in-memory based analysis techniques cannot provide high performance. Frontier-Expansion-Merge (FEM) framework for graph search operations using three corresponding operators in the relational database (RDB) context. FEM exploits an index table that stores pre-computed partial paths for efficient shortest path discovery. However, the index table of FEM has low hit ratio because the indices are determined by distances of indices rather than the possibility of containing a shortest path. In this paper, we propose an method that construct index table using high degree nodes having high hit ratio for efficient shortest path discovery. We experimentally verify that our index technique can support shortest path discovery efficiently in real-world datasets.
|
Å°¿öµå(Keyword) |
Shortest Path Search
RDBMS
Indexing
ÃÖ´Ü °æ·Î Ž»ö
RDBMS
À妽Ì
|
ÆÄÀÏ÷ºÎ |
PDF ´Ù¿î·Îµå
|