TL;DR
- مشاهده PDF HTML (تجربی) چکیده:.
- PANDA یک الگوریتم عمومی قدرتمند برای پاسخگویی به پرس و جوهای پیوندی (CQ) و قوانین دیتالوگ جدایی (DDR).
- با توجه به محدودیت های درجه ورودی است.
چه اتفاقی افتاد
مشاهده PDF HTML (تجربی) چکیده:. PANDA یک الگوریتم عمومی قدرتمند برای پاسخگویی به پرس و جوهای پیوندی (CQ) و قوانین دیتالوگ جدایی (DDR).
با توجه به محدودیت های درجه ورودی است. در حالت خاصی که محدودیتهای درجه،.
محدودیتهای اصلی هستند و پرسوجو Boolean است،. PANDA در $\tilde O (N^{subw})$-time اجرا میشود،.
جایی که $N$ اندازه ورودی است،. و $subw$ عرض زیر مدولار پرسوجو است،.
مفهومی که توسط دانیل مارکس (JACM 2013) معرفی شد. هنگامی که به کلاسهای خاصی از مشکلات یافتن الگوی زیرگراف اختصاص داده میشود،.
زمان اجرا $\tilde O(N^{subw})$ با زمان اجرا بهینه ممکن مطابقت دارد،. با مدول کردن برخی حدسها در پیچیدگی ریز (برینگمن و گورباچف (STOC 25)).
چارچوب PANDA بسیار عمومیتر است،. زیرا محدودیتهای درجه ورودی دلخواه را کنترل میکند،.
که آمارهای رایج و محدودیتهای یکپارچگی مورد استفاده در سیستمهای مدیریت پایگاه داده رابطهای را ثبت میکند. پرس و جو با متغیرهای رایگان، و برای هر دو CQ و DDR.
نقطه ضعف کلیدی PANDA فاکتور بزرگ $polylog(N)$ است که در نماد $\tilde O(\cdot)$ پنهان شده است. این امر باعث می شود تا PANDA کاملاً غیر عملی باشد و از آنچه که با الگوریتم های.
تخصصی قابل دستیابی است فاصله بگیرد. این مقاله با دو ایده جدید این ضعف را برطرف می کند.
اول،. ما یک نابرابری احتمالی جدید را ثابت می کنیم که اندازه خروجی DDR ها را تحت محدودیت های.
درجه دلخواه محدود می کند. دوم،.
اثبات این نابرابری مستقیماً منجر به الگوریتم جدیدی به نام PANDAExpress میشود که هم سادهتر و هم سریعتر. از PANDA است.
ویژگی جدید PANDAExpress یک طرح پارتیشن بندی جدید است که به جای ابرصفحه های موازی محور که در. PANDA استفاده می شود،.
از برش های فراصفحه دلخواه استفاده می کند. این ابرصفحه ها به صورت پویا بر اساس آمار چولگی داده ها که در طول اجرای الگوریتم به.
دقت ردیابی می شوند،. ساخته می شوند.
در نتیجه،. PANDAExpress حذف می کند عامل $polylog(N)$ از زمان اجرا PANDA،.
با زمان اجرا الگوریتمهای تخصصی پیچیده مطابقت دارد،. در حالی که کلیات و قدرت خود را حفظ میکند.
موضوعات:. پایگاه های داده (cs.DB)؛
نظریه اطلاعات (cs.IT)؛ احتمال (math.PR) استناد به عنوان:.
arXiv:. 2512.10217 [cs.DB] (یا arXiv:.
2512.10217v3 [cs.DB] برای این نسخه) https:. //doi.org/10.48550/arXiv.2512.10217 DOI صادر شده توسط arXiv از طریق DataCite تاریخچه ارسال از:.
محمود ابوخمیس [مشاهده ایمیل] [v1] پنجشنبه،. 11 دسامبر 2025،.
02:. 08:.
02 UTC (39 کیلوبایت) [v2] چهارشنبه،. 4 مارس 2026،.
18:. 26:.
53 UTC (56 KB) [v3] دوشنبه،. 6 آوریل 2026،.
18:. 25:.
04 UTC (40 KB).
چرا مهم است
اهمیت این خبر در این است که روی استفاده واقعی از AI و تصمیمگیری سازمانی اثر میگذارد.
منبع
لینک منبع اصلی در کارت و صفحه مقاله نمایش داده میشود.