2025-11-17T04:01:13.190278

Retroactive Monotonic Priority Queues via Range Searching

Castro, de Freitas

The best-known fully retroactive priority queue costs $O(\log^2 m \log \log m)$ time per operation, where $m$ is the number of operations performed on the data structure. In contrast, standard (non-retroactive) and partially retroactive priority queues can cost $O(\log m)$ time per operation. So far, it is unknown whether this $O(\log m)$ bound can be achieved for fully retroactive priority queues. In this work, we study a restricted variant of priority queues known as monotonic priority queues. First, we show that finding the minimum in a retroactive monotonic priority queue is a special case of the range-searching problem. Then, we design a fully retroactive monotonic priority queue with a cost of $O(\log m + T(m))$ time per operation, where $T(m)$ is the maximum between the query and the update time of a specific range-searching data structure with $m$ elements. Finally, we design a fully retroactive monotonic priority queue that costs $O(\log m \log \log m)$ time per operation.

academic

পূর্বাভাসী একঘেয়ে অগ্রাধিকার সারি পরিসীমা অনুসন্ধানের মাধ্যমে

মৌলিক তথ্য

পত্রিকা আইডি: 2508.09892
শিরোনাম: পূর্বাভাসী একঘেয়ে অগ্রাধিকার সারি পরিসীমা অনুসন্ধানের মাধ্যমে
লেখক: লুকাস কাস্ট্রো, রোসিয়ানে ডি ফ্রেইটাস (ইনস্টিটিউট অফ কম্পিউটিং - ইউএফএএম, ব্রাজিল)
শ্রেণীবিভাগ: cs.DS (ডেটা স্ট্রাকচার এবং অ্যালগরিদম), cs.CG (কম্পিউটেশনাল জিওমেট্রি)
প্রকাশনার সময়: arXiv প্রি-প্রিন্ট, ২০২৫ সালের ১৪ অক্টোবর আপডেট
পত্রিকা লিঙ্ক: https://arxiv.org/abs/2508.09892

সারসংক্ষেপ

সম্পূর্ণ পূর্বাভাসী অগ্রাধিকার সারির জন্য পরিচিত সর্বোত্তম প্রতিটি অপারেশনে $O(\log^2 m \log \log m)$ সময় প্রয়োজন, যেখানে $m$ হল ডেটা স্ট্রাকচারে সম্পাদিত মোট অপারেশনের সংখ্যা। বিপরীতে, মান (অ-পূর্বাভাসী) এবং আংশিক পূর্বাভাসী অগ্রাধিকার সারি প্রতিটি অপারেশনে মাত্র $O(\log m)$ সময় প্রয়োজন। এটি স্পষ্ট নয় যে সম্পূর্ণ পূর্বাভাসী অগ্রাধিকার সারি $O(\log m)$ সীমানা অর্জন করতে পারে কিনা। এই পত্রিকা একঘেয়ে অগ্রাধিকার সারির এই সীমিত বৈকল্পিক অধ্যয়ন করে, প্রথমে প্রমাণ করে যে পূর্বাভাসী একঘেয়ে অগ্রাধিকার সারিতে ন্যূনতম খুঁজে পাওয়া পরিসীমা অনুসন্ধান সমস্যার একটি বিশেষ ক্ষেত্র, তারপর প্রতিটি অপারেশনে $O(\log m + T(m))$ সময়ের সম্পূর্ণ পূর্বাভাসী একঘেয়ে অগ্রাধিকার সারি ডিজাইন করে, এবং অবশেষে প্রতিটি অপারেশনে $O(\log m \log \log m)$ সময়ের সম্পূর্ণ পূর্বাভাসী একঘেয়ে অগ্রাধিকার সারি বাস্তবায়ন করে।

গবেষণা পটভূমি এবং প্রেরণা

সমস্যা সংজ্ঞা

ঐতিহ্যবাহী ডেটা স্ট্রাকচার শুধুমাত্র "বর্তমান" অবস্থায় কাজ করতে পারে এবং অতীতের অবস্থা অনুসন্ধান বা সংশোধন করতে পারে না। পূর্বাভাসী ডেটা স্ট্রাকচার ডেমেইন এবং অন্যদের দ্বারা প্রবর্তিত হয়েছিল, যা অতীতের অবস্থা সংশোধন করতে এবং সংশোধনের ফলাফল বর্তমান অবস্থায় প্রচার করতে পারে। কার্যকারিতার উপর ভিত্তি করে, এগুলি বিভক্ত:

আংশিক পূর্বাভাসী: অতীত সংশোধন করতে পারে, কিন্তু শুধুমাত্র বর্তমান অবস্থা অনুসন্ধান করতে পারে
সম্পূর্ণ পূর্বাভাসী: অতীত সংশোধন এবং যেকোনো সময়ে অবস্থা অনুসন্ধান উভয়ই করতে পারে

গবেষণা প্রেরণা

দক্ষতার ব্যবধান: সম্পূর্ণ পূর্বাভাসী অগ্রাধিকার সারি এবং মান/আংশিক পূর্বাভাসী সংস্করণের মধ্যে উল্লেখযোগ্য সময় জটিলতার পার্থক্য রয়েছে
তাত্ত্বিক চ্যালেঞ্জ: এটি স্পষ্ট নয় যে সম্পূর্ণ পূর্বাভাসী অগ্রাধিকার সারি $O(\log m)$ তাত্ত্বিক নিম্ন সীমানা অর্জন করতে পারে কিনা
ব্যবহারিক প্রয়োগ: একঘেয়ে অগ্রাধিকার সারি ডিজকস্ট্রা অ্যালগরিদম এবং অন্যান্য পরিস্থিতিতে গুরুত্বপূর্ণ প্রয়োগ মূল্য রয়েছে

বিদ্যমান পদ্ধতির সীমাবদ্ধতা

সর্বোত্তম সম্পূর্ণ পূর্বাভাসী অগ্রাধিকার সারির সময় জটিলতা $O(\log^2 m \log \log m)$
মান অগ্রাধিকার সারির $O(\log m)$ জটিলতার সাথে উল্লেখযোগ্য পার্থক্য রয়েছে
সীমিত বৈকল্পিক (যেমন একঘেয়ে অগ্রাধিকার সারি) সম্পর্কে বিশেষায়িত গবেষণার অভাব

মূল অবদান

তাত্ত্বিক আবিষ্কার: প্রমাণ করে যে পূর্বাভাসী একঘেয়ে অগ্রাধিকার সারিতে ন্যূনতম খুঁজে পাওয়া পরিসীমা অনুসন্ধান সমস্যার সমতুল্য
সাধারণ কাঠামো: $O(\log m + T(m))$ সময় জটিলতার সম্পূর্ণ পূর্বাভাসী একঘেয়ে অগ্রাধিকার সারি ডিজাইন করে, যেখানে $T(m)$ হল পরিসীমা অনুসন্ধান ডেটা স্ট্রাকচারের অনুসন্ধান/আপডেট সময়
নির্দিষ্ট বাস্তবায়ন: ২ডি পরিসীমা গাছের উপর ভিত্তি করে $O(\log m \log \log m)$ সময় জটিলতার সম্পূর্ণ পূর্বাভাসী একঘেয়ে অগ্রাধিকার সারি বাস্তবায়ন করে
জ্যামিতিক দৃষ্টিভঙ্গি: পূর্বাভাসী অগ্রাধিকার সারি বোঝার জন্য একটি নতুন জ্যামিতিক দৃষ্টিভঙ্গি প্রদান করে

পদ্ধতির বিস্তারিত বিবরণ

কাজের সংজ্ঞা

নিম্নলিখিত অপারেশন সমর্থন করে এমন সম্পূর্ণ পূর্বাভাসী একঘেয়ে অগ্রাধিকার সারি ডিজাইন করুন:

Insert(insert(x), t): সময় $t$ -তে উপাদান $x$ সন্নিবেশ করান
Delete(insert(x), t): সময় $t$ -এর সন্নিবেশ অপারেশন মুছুন
Insert(extract-min, t): সময় $t$ -তে ন্যূনতম বের করার অপারেশন সন্নিবেশ করান
Delete(extract-min, t): সময় $t$ -এর বের করার অপারেশন মুছুন
GetMin(t): সময় $t$ -এর ন্যূনতম উপাদান ফেরত দিন

একঘেয়েতার সীমাবদ্ধতা: বের করা উপাদানগুলি অ-হ্রাসমান ক্রম গঠন করতে হবে।

মূল তাত্ত্বিক ভিত্তি

অস্তিত্বের শর্ত (লেম্মা 14)

একঘেয়ে অগ্রাধিকার সারিতে, উপাদান $x$ সময় $t$ -তে বিদ্যমান থাকে যদি এবং শুধুমাত্র যদি:

insertionTime(x) ≤ t
x > lastExtracted(t)

এটি প্রতিটি উপাদানের বের করার সময় বজায় রাখার প্রয়োজনীয়তা এড়ায় এবং পূর্বাভাসী অপারেশনের জটিলতা সরল করে।

শেষ বের করা উপাদানের দক্ষ অনুসন্ধান (লেম্মা 16-17)

মূল অন্তর্দৃষ্টি: একঘেয়ে অগ্রাধিকার সারিতে, $k$ -তম ক্ষুদ্রতম উপাদান val[k] শুধুমাত্র $k$ -তম বের করার অপারেশন em[k] দ্বারা বের করা যেতে পারে।

অ্যালগরিদম:

বের করার সময়ের গাছে সময় $t$ -এর পূর্বসূরি অপারেশন খুঁজুন
সেই অপারেশনের ক্রম সংখ্যা $k$ নির্ধারণ করুন
$k$ -তম ক্ষুদ্রতম উপাদান ফেরত দিন

সময় জটিলতা: $O(\log m)$

জ্যামিতিক প্রতিনিধিত্ব (লেম্মা 18)

একঘেয়ে অগ্রাধিকার সারি ২ডি সমতলে বিন্দু হিসাবে প্রতিনিধিত্ব করুন:

প্রতিটি উপাদান $e$ বিন্দু (insertionTime(e), e) হিসাবে প্রতিনিধিত্ব করা হয়
GetMin(t) অনুসন্ধান আয়তক্ষেত্র $R(t) = (-\infty, t] \times (\text{lastExtracted}(t), \infty)$ -এ $y$ স্থানাঙ্কের সর্বনিম্ন বিন্দু খুঁজে পাওয়ার সমস্যায় রূপান্তরিত হয়

এই প্রতিনিধিত্ব অগ্রাধিকার সারি অনুসন্ধান সমস্যা সম্পূর্ণভাবে জ্যামিতিক পরিসীমা অনুসন্ধান সমস্যায় রূপান্তরিত করে।

ডেটা স্ট্রাকচার ডিজাইন

তিনটি সহায়ক ডেটা স্ট্রাকচার:

$T_{el}$ : সমস্ত সন্নিবেশিত উপাদানের অর্ডার পরিসংখ্যান গাছ
$T_{em}$ : সমস্ত বের করার সময়ের অর্ডার পরিসংখ্যান গাছ
$T_{ins}$ : সমস্ত (সন্নিবেশ সময়, উপাদান মূল্য) জোড়ার ন্যূনতম-y পরিসীমা অনুসন্ধান ডেটা স্ট্রাকচার

অপারেশন বাস্তবায়ন:

GetMin(t): প্রথমে lastExtracted(t) খুঁজুন, তারপর $T_{ins}$ -এ আয়তক্ষেত্র পরিসীমা অনুসন্ধান করুন
Insert/Delete(insert(x), t): $T_{el}$ এবং $T_{ins}$ আপডেট করুন
Insert/Delete(extract-min, t): $T_{em}$ আপডেট করুন

পরীক্ষামূলক সেটআপ

তাত্ত্বিক বিশ্লেষণ কাঠামো

এই পত্রিকা প্রধানত তাত্ত্বিক বিশ্লেষণ পরিচালনা করে এবং নিম্নলিখিত উপায়ে পদ্ধতির সঠিকতা যাচাই করে:

গাণিতিক প্রমাণ: সমস্ত মূল লেম্মা এবং উপপাদ্য কঠোরভাবে প্রমাণ করুন
জটিলতা বিশ্লেষণ: প্রতিটি অপারেশনের সময় এবং স্থান জটিলতা বিস্তারিতভাবে বিশ্লেষণ করুন
সঠিকতা যাচাইকরণ: জ্যামিতিক অন্তর্দৃষ্টি এবং অ্যালগরিদম যুক্তির মাধ্যমে পদ্ধতির সঠিকতা যাচাই করুন

পরিসীমা অনুসন্ধান ডেটা স্ট্রাকচার নির্বাচন

মেহলহর্ন এবং নেহরের ২ডি পরিসীমা গাছ নির্বাচন করুন অন্তর্নিহিত ডেটা স্ট্রাকচার হিসাবে:

আপডেট সময়: $O(\log n \log \log n)$ (পরিশোধিত, সর্বোচ্চ ক্ষেত্রে রূপান্তরযোগ্য)
অনুসন্ধান সময়: $O(\log n \log \log n)$
স্থান জটিলতা: $O(n \log n)$

পরীক্ষামূলক ফলাফল

প্রধান তাত্ত্বিক ফলাফল

উপপাদ্য 20 (সাধারণ কাঠামো): নিম্নলিখিত জটিলতার সম্পূর্ণ পূর্বাভাসী একঘেয়ে অগ্রাধিকার সারি বিদ্যমান:

বের করার অপারেশন: $O(\log m)$
সন্নিবেশ অপারেশন: $O(\log m + U(m))$
অনুসন্ধান অপারেশন: $O(\log m + Q(m))$
স্থান জটিলতা: $O(m + S(m))$

যেখানে $U(m)$ , $Q(m)$ , $S(m)$ যথাক্রমে পরিসীমা অনুসন্ধান ডেটা স্ট্রাকচারের আপডেট, অনুসন্ধান এবং স্থান জটিলতা।

উপপাদ্য 21 (নির্দিষ্ট বাস্তবায়ন): ২ডি পরিসীমা গাছের উপর ভিত্তি করে বাস্তবায়ন নিম্নলিখিত জটিলতা রয়েছে:

বের করার অপারেশন: $O(\log m)$
সন্নিবেশ অপারেশন: $O(\log m \log \log m)$
অনুসন্ধান অপারেশন: $O(\log m \log \log m)$
স্থান জটিলতা: $O(m \log m)$

জটিলতা তুলনা

ডেটা স্ট্রাকচার ধরন	সময় জটিলতা
মান অগ্রাধিকার সারি	$O(\log m)$
আংশিক পূর্বাভাসী অগ্রাধিকার সারি	$O(\log m)$
সম্পূর্ণ পূর্বাভাসী অগ্রাধিকার সারি (পরিচিত সর্বোত্তম)	$O(\log^2 m \log \log m)$
এই পত্রিকা: সম্পূর্ণ পূর্বাভাসী একঘেয়ে অগ্রাধিকার সারি	$O(\log m \log \log m)$

এই পত্রিকা সম্পূর্ণ পূর্বাভাসী অগ্রাধিকার সারির জটিলতার উল্লেখযোগ্য উন্নতি অর্জন করেছে (একঘেয়ে সীমাবদ্ধতার অধীনে)।

উপসংহার এবং আলোচনা

প্রধান উপসংহার

তাত্ত্বিক অবদান: প্রথমবারের মতো পূর্বাভাসী অগ্রাধিকার সারি সমস্যা এবং পরিসীমা অনুসন্ধানের মধ্যে সংযোগ স্থাপন করেছে
অ্যালগরিদম উন্নতি: একঘেয়ে সীমাবদ্ধতার অধীনে সম্পূর্ণ পূর্বাভাসী অগ্রাধিকার সারির দক্ষতা উল্লেখযোগ্যভাবে উন্নত করেছে
সাধারণ কাঠামো: বিভিন্ন পরিসীমা অনুসন্ধান ডেটা স্ট্রাকচারের উপর ভিত্তি করে সাধারণ ডিজাইন কাঠামো প্রদান করেছে

সীমাবদ্ধতা

সীমাবদ্ধতার সীমা: শুধুমাত্র একঘেয়ে অগ্রাধিকার সারির জন্য প্রযোজ্য, সাধারণ ক্ষেত্রে সরাসরি প্রসারিত করা যায় না
তাত্ত্বিক ফলাফল: প্রধানত তাত্ত্বিক বিশ্লেষণ, বাস্তব বাস্তবায়ন এবং পরীক্ষামূলক যাচাইকরণের অভাব
জটিলতার ব্যবধান: মান অগ্রাধিকার সারির সাথে এখনও $\log \log m$ ফ্যাক্টরের পার্থক্য রয়েছে

ভবিষ্যত দিকনির্দেশনা

লেখক স্পষ্টভাবে তিনটি গবেষণা দিকনির্দেশনা প্রস্তাব করেছেন:

অন্যান্য সীমিত অগ্রাধিকার সারি বৈকল্পিকের সম্পূর্ণ পূর্বাভাসী সংস্করণ অধ্যয়ন করুন
সাধারণ সম্পূর্ণ পূর্বাভাসী অগ্রাধিকার সারির উপরের সীমানা অধ্যয়ন করুন
পূর্বাভাসী অগ্রাধিকার সারির নিম্ন সীমানা অধ্যয়ন করুন

গভীর মূল্যায়ন

সুবিধা

শক্তিশালী উদ্ভাবনী: প্রথমবারের মতো পূর্বাভাসী ডেটা স্ট্রাকচার এবং গণনামূলক জ্যামিতির মধ্যে সংযোগ স্থাপন করেছে, দৃষ্টিভঙ্গি নতুন
তাত্ত্বিক কঠোরতা: সমস্ত মূল ফলাফলে কঠোর গাণিতিক প্রমাণ রয়েছে, যুক্তি স্পষ্ট
ব্যবহারিক মূল্য: একঘেয়ে অগ্রাধিকার সারি বাস্তব অ্যালগরিদমে গুরুত্বপূর্ণ প্রয়োগ রয়েছে
স্পষ্ট লেখা: ব্যাংক সিস্টেম সাদৃশ্য ইত্যাদি ব্যবহার করে ধারণা ব্যাখ্যা স্পষ্ট এবং বোধগম্য
জ্যামিতিক অন্তর্দৃষ্টি: রশ্মি প্রক্ষেপণ সাদৃশ্য চমৎকার জ্যামিতিক অন্তর্দৃষ্টি প্রদান করে

অপূর্ণতা

প্রয়োগের পরিসীমা: শুধুমাত্র একঘেয়ে অগ্রাধিকার সারির মধ্যে সীমাবদ্ধ, সাধারণতা সীমিত
পরীক্ষামূলক অভাব: বাস্তব বাস্তবায়ন এবং কর্মক্ষমতা পরীক্ষার অভাব
নিম্ন সীমানা বিশ্লেষণ: সংশ্লিষ্ট নিম্ন সীমানা বিশ্লেষণ প্রদান করেনি
ধ্রুবক ফ্যাক্টর: তাত্ত্বিক বিশ্লেষণ ধ্রুবক ফ্যাক্টরের প্রভাব বিবেচনা করেনি

প্রভাব

তাত্ত্বিক অবদান: পূর্বাভাসী ডেটা স্ট্রাকচার গবেষণার জন্য নতুন জ্যামিতিক দৃষ্টিভঙ্গি প্রদান করেছে
পদ্ধতিগত মূল্য: সমস্যার বিশেষ কাঠামো কীভাবে অপ্টিমাইজেশনের জন্য ব্যবহার করতে হয় তা প্রদর্শন করেছে
অনুপ্রেরণামূলক অর্থ: অন্যান্য সীমিত ডেটা স্ট্রাকচারের পূর্বাভাসী সংস্করণ গবেষণা অনুপ্রাণিত করতে পারে

প্রযোজ্য পরিস্থিতি

ডিজকস্ট্রা অ্যালগরিদম: গতিশীল গ্রাফে সর্বনিম্ন পথ সমস্যা
ইভেন্ট সময়সূচী: ঐতিহাসিক ইভেন্ট সংশোধন প্রয়োজন এমন সময়সূচী সিস্টেম
ডেটা সংশোধন: ডেটা সংশোধন ট্র্যাক করা প্রয়োজন এমন প্রয়োগ পরিস্থিতি

রেফারেন্স

পত্রিকা ১৩টি সম্পর্কিত রেফারেন্স উদ্ধৃত করেছে, প্রধানত অন্তর্ভুক্ত:

ডেমেইন এবং অন্যরা (২০০৭) - পূর্বাভাসী ডেটা স্ট্রাকচারের যুগান্তকারী কাজ
ডেমেইন এবং অন্যরা (২০১৫) - বর্তমান সর্বোত্তম সম্পূর্ণ পূর্বাভাসী অগ্রাধিকার সারি
মেহলহর্ন এবং নেহর (১৯৯০) - ২ডি পরিসীমা গাছের ক্লাসিক কাজ
আগারওয়াল (২০১৮) - পরিসীমা অনুসন্ধান সমস্যার সমীক্ষা

সামগ্রিক মূল্যায়ন: এটি একটি উচ্চ মানের তাত্ত্বিক কম্পিউটার বিজ্ঞান পত্রিকা যা চতুর জ্যামিতিক চিন্তাভাবনার মাধ্যমে পূর্বাভাসী ডেটা স্ট্রাকচারে একটি গুরুত্বপূর্ণ সমস্যা সমাধান করেছে। যদিও ফলাফল শুধুমাত্র একঘেয়ে পরিস্থিতিতে প্রযোজ্য, পদ্ধতি উদ্ভাবনী এবং তাত্ত্বিক কঠোর, এই ক্ষেত্রের আরও গবেষণার জন্য মূল্যবান চিন্তাভাবনা এবং সরঞ্জাম প্রদান করে।