Á¤º¸°úÇÐȸ ³í¹®Áö D : µ¥ÀÌŸº£À̽º
Current Result Document : 5 / 5
ÇѱÛÁ¦¸ñ(Korean Title) |
J-tree: »ç¿ëÀÚÀÇ °Ë»öÆÐÅÏÀ» ÀÌ¿ëÇÑ ´ë¿ë·® µ¥ÀÌŸ¸¦ À§ÇÑ È¿À²ÀûÀÎ »öÀÎ |
¿µ¹®Á¦¸ñ(English Title) |
J-Tree: An Efficient Index using User Searching Patterns for Large Scale Data |
ÀúÀÚ(Author) |
Àå¼ö¹Î
¼±¤¼®
À¯Àç¼ö
Sumin Jang
Kwangseok Seo
Jaesoo Yoo
|
¿ø¹®¼ö·Ïó(Citation) |
VOL 36 NO. 01 PP. 0044 ~ 0049 (2009. 02) |
Çѱ۳»¿ë (Korean Abstract) |
ÃÖ±Ù¿¡ ÈÞ´ë¿ë ´Ü¸»±âµéÀÇ ¹ßÀüÀ¸·Î, ´ë¿ë·® µ¥ÀÌŸ¿¡ ´ëÇÑ ´Ù¾çÇÑ °Ë»ö ¼ºñ½ºµéÀÌ ÈÞ´ë¿ë ´Ü¸»±â¿¡ Á¦°øµÇ°í ÀÖ´Ù. Á¤º¸ °Ë»öÀ» À§ÇÑ ´ëºÎºÐ ÀÀ¿ëÇÁ·Î±×·¥µéÀº ´ë¿ë·® µ¥ÀÌŸ¸¦ °Ë»öÇϱâ À§ÇÏ¿© B-tree³ª R-tree¿Í °°Àº »öÀÎÀ» »ç¿ëÇÑ´Ù. ±×·¯³ª Àüü µ¥ÀÌŸÀÇ ¸Å¿ì ÀûÀº ºÎºÐÀÌ »ç¿ëÀÚ¿¡ ÀÇÇÏ¿© Á¢±ÙµÈ´Ù. ¶ÇÇÑ, °¢ µ¥ÀÌŸ¿¡ ´ëÇÑ Á¢±Ù ºóµµ¼öµéÀº ´Ù¾çÇÏ´Ù. ±×·¯³ª B-tree³ª R-tree¿Í °°Àº »öÀεéÀº ÆíÇâÀû Á¢±Ù ÆÐÅÏÀÇ Æ¯¼ºÀ» °í·ÁÇÏÁö ¾Ê´Â´Ù. ±×¸®°í ij½¬´Â ºü¸¥ Á¢±ÙÀ» À§Çؼ ¹Ýº¹ÀûÀ¸·Î Á¢±ÙµÇ´Â µ¥ÀÌŸ¸¦ ¸Þ¸ð¸®¿¡ ÀúÀåÇÑ´Ù. ±×·¯³ª ij½¬¿¡¼ »ç¿ëÇÏ´Â ¸Þ¸ð¸®ÀÇ Å©±â´Â Á¦ÇÑÀûÀÌ´Ù. º» ³í¹®¿¡¼´Â »ç¿ëÀÚÀÇ °Ë»öÆÐÅϵéÀ» °í·ÁÇÑ µð½ºÅ© ±â¹ÝÀÇ »õ·Î¿î »öÀα¸Á¶, J-tree¸¦ Á¦¾ÈÇÑ´Ù. Á¦¾ÈµÈ »öÀÎÀº ¸ðµç µ¥ÀÌŸ¿¡ ´ëÇÑ ÀÏÁ¤ÇÑ °Ë»ö¼Óµµ¸¦ º¸ÀåÇÏ´Â ±ÕÇüÆ®¸®ÀÌ´Ù. ±×¸®°í ÀÚÁÖ Á¢±ÙµÈ µ¥ÀÌŸ¿¡ ´ëÇؼ´Â ºü¸¥ °Ë»ö¼Óµµ¸¦ Á¦°øÇÑ´Ù. ¼º´ÉÆò°¡´Â ´Ù¾çÇÑ ½ÇÇèȯ°æ¿¡¼ Á¦¾ÈµÈ »öÀÎÀÇ È¿À²¼ºÀ» º¸¿©ÁØ´Ù. |
¿µ¹®³»¿ë (English Abstract) |
In recent years, with the development of portable terminals, various searching services on large data have been provided in portable terminals. In order to search large data, most applications for information retrieval use indexes such as B-trees or R-trees. However, only a small portion of the data set is accessed by users, and the access frequencies of each data are not uniform. The existing indexes such as B-trees or R-trees do not consider the properties of the skewed access patterns. And a cache stores the frequently accessed data for fast access in memory. But the size of memory used in the cache is restricted. In this paper, we propose a new index based on disk, called J-tree, which considers user's search patterns. The proposed index is a balanced tree which guarantees uniform searching time on all data. It also supports fast searching time on the frequently accessed data. Our experiments show the effectiveness of our proposed index under various settings. |
Å°¿öµå(Keyword) |
°Ë»ö »öÀÎ
Search Index
ÆíÇâ Á¢±Ù ÆÐÅÏ
Skewed Access Patterns
»ç¿ëÀÚ °Ë»ö ÆÐÅÏ
User Searching Patterns
|
ÆÄÀÏ÷ºÎ |
PDF ´Ù¿î·Îµå
|