تخصیص به نزدیکترین همسایه با حد آستانه نسبی (RTNNA ) کاوه پاشائی ، رضا باصدا ، دکتر مسعود رهگذر دانشگاه تهران- دانشكده فني - گروه مهندسي برق و كامپيوتر {K.Pashaei , R.Basseda }@ece.ut.ac.ir , Rahgozar@ut.ac.ir چكيده : در اين مقاله استراتژي تخصيص داده پوياي جديد براي سيستم هاي پايگاه داده توزيع شده غيرتکراري به نام الگوريتم RTNNA[ Relatively Threshold Near Neighborhood Algorithm] مطرح گرديده است. اين الگوريتم با توجه به تغيير الگوي دسترسي به قطعه‌هاي داده عمل تخصيص مجدد قطعه‌هاي داده را انجام مي‌دهد. در اين الگوريتم قطعه‌هاي داده به نودي منتقل مي شود که در نزديکي نودهايي قرار دارد که بيشترين دسترسي را به اين قطعه داده دارند. اين الگوريتم با بوجود آوردن خوشه‌هاي داده براي سيستمهاي پايگاه داده توزيع شده که با بار زياد و درخواستهاي متعدد از سايتهاي مختلف در يک شبکه مواجه مي‌باشند مناسب مي‌باشد. نتايج شبيه‌سازي نشان مي‌دهد که الگوريتم RTNNA براي شبکه‌هايي که در آنها قطعه‌هاي داده به طور مکرر از سايتهاي مختلف درخواست مي‌شود زمان پاسخ بهتري دارد و براي انتقال قطعه‌هاي داده در شبکه نياز به زمان کمتري دارد. 1.مقدمه : پيشرفت در تکنولوژيهاي شبکه و پايگاه داده در دهه هاي اخير منجر به ايجاد سيستم هاي پايگاه داده توزيع شده گشته است .يک سيستم پايگاه داده توزيع شده مجموعه‌اي از سايتها مي باشد که از طريق شبکه به هم متصل شده‌اند که هر کدام از سايت ها پايگاه داده مخصوص به خود دارد اما مي توانند با يکديگر کار کنند بنابراين هر کاربري در هر سايتي مي تواند به همه داده هاي موجود در شبکه دسترسي داشته باشد درست مانند اينکه همه داده ها در سايت کاربر ذخيره شده است.[11] دغدغه اصلي سيستم هاي پايگاه داده توزيع شده قطعه‌قطعه کردن[ Fragmentation] و تخصيص[ Allocation] پايگاه داده اصلي مي باشد واحد قطعه داده مي تواند يک فايل باشد که در اين حالت موضوع تخصيص همان تخصيص فايل خواهد بود مشکل تخصيص داده يک مسئله از درجه NP مي باشد بنابراين نياز به هيوريستيکهاي سريع براي توليد راه حل هاي موثر مي باشد علاوه بر اينها تخصيص بهينه اشيا پايگاه داده به طور شديد بستگي به استراتژي اجراي پرس وجو [ Query] که به وسيله پايگاه داده توزيع شده پياده سازي شده دارد. مسئله تخصيص فايل به طور کامل در ادبيات مقالات بررسي شده است که ابتدا توسط Chu آغاز شده است[2] و سپس مدلهاي تکراري و غير تکراري در [3],[4] بررسي شده و در [5],[6] برخي مطالعات در زمينه تخصيص فايل پويا انجام شده است.