有效降低分布式SKYLINE 查询网络传输代价

《有效降低分布式SKYLINE 查询网络传输代价》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第４期电子学报Ｖｏｌ．３８Ｎｏ．４２０１０年４月ＡＣＴＡＥＬＥＣＴＲＯＮＩＣＡＳＩＮＩＣＡＡｐｒ．２０１０有效降低分布式ＳＫＹＬＩＮＥ查询网络传输代价黄震华１，２，向阳１，林琛３（１．同济大学计算机科学与工程系，上海２０００９２；２．同济大学嵌入式系统与服务计算教育部重点实验室，上海２０００９２；３．复旦大学计算机与信息技术系，上海２００４３３）摘要：分布式网络中的ｓｋｙｌｉｎｅ查询是近年来信息检索学科的一个研究重点．目前大多数研究工作均没有考虑在分布式网络中，如何有效降低ｓｋｙｌｉｎｅ查询的网络传输代价．

2、为此，提出一种在分布式网络中，有效降低ｓｋｙｌｉｎｅ查询传输代价的方法ＲＴＣＳＱＤＮ（ＲｅｄｕｃｉｎｇｔｈｅＴｒａｎｓｆｅｒｒｉｎｇＣｏｓｔｏｆＳｋｙｌｉｎｅＱｕｅｒｉｅｓｏｖｅｒＤｉｓｔｒｉｂｕｔｅｄＮｅｔｗｏｒｋｓ）．ＲＴＣＳＱＤＮ算法充分利用父空间ｓｋｙｌｉｎｅ对象集与子空间ｓｋｙｌｉｎｅ对象集间的语义关系通过三个阶段来平衡网络传输量和查询时间开销．同时，文章给出一种新颖的多维对象传送策略ＰＴＧＰＶ（ＰｏｌｉｃｙｆｏｒＴｒａｎｓｆｅｒｒｉｎｇＧｒｏｕｐｉｎｇＰｏｓｉｔｉｏｎＶａｌｕｅｓ）来避免直接传送

3、ｓｋｙｌｉｎｅ对象本身，从而最小化数据传输量．详细的理论分析和大量实验评估表明，文章给出的算法具有有效性和实用性．关键词：信息检索；ｓｋｙｌｉｎｅ查询；分布式网络；传输代价中图分类号：ＴＰ３１１１３文献标识码：Ａ文章编号：０３７２２１１２（２０１０）０４０８４８０５ＥｆｆｉｃｉｅｎｔｌｙＲｅｄｕｃｉｎｇＴｒａｎｓｆｅｒｒｉｎｇＣｏｓｔｏｆＳｋｙｌｉｎｅＱｕｅｒｉｅｓｏｖｅｒＤｉｓｔｒｉｂｕｔｅｄＮｅｔｗｏｒｋｓ１，２，ＸＩＡＮＧＹａｎｇ１，ＬＩＮＣｈｅｎ３ＨＡＮＧＺｈｅｎｈｕａ（１．Ｄｅｐａｒｔｍ

4、ｅｎｔｏｆＣｏｍｐｕｔｅｒａｎｄＴｅｃｈｎｏｌｏｇｙ，ＴｏｎｇｊｉＵｎｉｖｅｒｓｉｔｙ，Ｓｈａｎｇｈａｉ２０００９２，Ｃｈｉｎａ；２．ＴｈｅＫｅｙＬａｂｏｒａｔｏｒｙｏｆＥｍｂｅｄｄｅｄＳｙｓｔｅｍａｎｄＳｅｒｖｉｃｅＣｏｍｐｕｔｉｎｇ，ＭｉｎｉｓｔｒｙｏｆＥｄｕｃａｔｉｏｎ，ＴｏｎｇｊｉＵｎｉｖｅｒｓｉｔｙ，Ｓｈａｎｇｈａｉ２０００９２，Ｃｈｉｎａ；３．ＤｅｐａｒｔｍｅｎｔｏｆＣｏｍｐｕｔｅｒａｎｄＩｎｆｏｒｍａｔｉｏｎＴｅｃｈｎｏｌｏｇｙ，ＦｕｄａｎＵｎｉｖｅｒｓｉｔｙ，Ｓｈａｎｇｈａｉ２００４３３，Ｃ

5、ｈｉｎａ）Ａｂｓｔｒａｃｔ：Ｓｋｙｌｉｎｅｑｕｅｒｙｐｒｏｃｅｓｓｉｎｇｉｎｄｉｓｔｒｉｂｕｔｅｄｅｎｖｉｒｏｎｍｅｎｔｓｈａｓｒｅｃｅｎｔｌｙｒｅｃｅｉｖｅｄａｌｏｔｏｆａｔｔｅｎｔｉｏｎｉｎｉｎｆｏｒｍａｔｉｏｎｒｅｔｒｉｅｖａｌｃｏｍｍｕｎｉｔｙ．Ｈｏｗｅｖｅｒ，ｍｏｓｔｅｘｉｓｔｉｎｇｌｉｔｅｒａｔｕｒｅｓｄｏｎｏｔｃｏｎｓｉｄｅｒｈｏｗｔｏｅｆｆｉｃｉｅｎｔｌｙｒｅｄｕｃｅｔｈｅｔｒａｎｓｆｅｒｒｉｎｇｃｏｓｔｏｆｓｋｙｌｉｎｅｑｕｅｒｅｉｓｏｎｄｉｓｔｒｉｂｕｔｅｄｎｅｔｗｏｒｋｓ．Ｉｎｔｈｉｓ

6、ｐａｐｅｒ，ｗｅｐｒｏｐｏｓｅＲＴＣＳＱＤＮ（ＲｅｄｕｃｉｎｇｔｈｅＴｒａｎｓｆｅｒｒｉｎｇＣｏｓｔｏｆＳｋｙｌｉｎｅＱｕｅｒｉｅｓｏｖｅｒＤｉｓｔｒｉｂｕｔｅｄＮｅｔｗｏｒｋｓ），ｔｈｅｅｆｆｉｃｉｅｎｔｓｏｕｎｄａｎｄｃｏｍｐｌｅｔｅａｌｇｏｒｉｔｈｍｆｏｒｂａｌａｎｃｉｎｇｔｈｅｃｏｓｔｏｆｔｒａｎｓｆｅｒｒｉｎｇｄａｔａａｎｄｓｋｙｌｉｎｅｃｏｍｐｕｔａｔｉｏｎｃｏｓｔｏｎｔｈｅｄｉｓｔｒｉｂｕｔｅｄｎｅｔｗｏｒｋｓ．Ｓｐｅｃｉａｌｌｙ，ｔｈｅＰＤＳＱＤＮａｌｇｏｒｉｔｈｍｍａｋｅｓｕｓｅｏｆｔｈ

7、ｅｓｅｍａｎｔｉｃｒｅｌａｔｉｏｎｓｈｉｐｂｅｔｗｅｅｎｐａｒｅｎｔｓｐａｃｅｓｋｙｌｉｎｅｓａｎｄｃｈｉｌｄｓｐａｃｅｓｋｙｌｉｎｅｓ，ａｎｄｔｒａｎｓｆｅｒｓｔｈｅｄａｔａｔｈｒｏｕｇｈｔｈｒｅｅｐｈａｓｅｓ．Ｍｏｒｅｏｖｅｒ，ｗｅｐｒｅｓｅｎｔａｎｏｖｅｌｐｏｌｉｃｙ，ｉ．ｅ．ＰＴＧＰＶ（ＰｏｌｉｃｙｆｏｒＴｒａｎｓｆｅｒｒｉｎｇＧｒｏｕｐｉｎｇＰｏｓｉｔｉｏｎＶａｌｕｅｓ），ｔｏｔｒａｎｓｆｅｒｍｕｌｔｉｄｉｍｅｎｓｉｏｎａｌｏｂｊｅｃｔｓ．ＴｈｅＰＴＧＰＶｐｏｌｉｃｙｏｎｌｙｔｒａｎｓｆｅｒ

8、ｓｔｈｅｐｏｓｉｔｉｏｎｖａｌｕｅｓｏｆｏｂｊｅｃｔｓｆｏｒｍｏｓｔｄｉｍｅｎｓｉｏｎａｌｓｐａｃｅｓ，ａｎｄｈｅｎｃｅｉｔｃａｎｅｆｆｉｃｉｅｎｔｌｙｍｉｎｉｍｉｚｅｔｈｅｖｏｌｕｍｅｏｆｄａｔａｔｒａｎｓｆｅｒｒｅｄ．Ｗｅａｌｓｏｐｒｅｓｅｎｔｄｅｔａｉｌｅｄｔｈｅｏｒｅｔｉｃａｌａｎａｌｙｓｅｓａｎｄｅｘｔｅｎｓｉｖｅｅｘｐｅｒｉｍｅｎｔｓｔｈａｔｄｅｍｏｎｓｔｒａｔｅｏｕｒａｌｇｏｒｉｔｈｍｓａｒｅｂ