فهارس فعالة لاستعلامات النطاق المتنوعة من النوع الأعلى

ليكن P مجموعة من n نقاط ذات أوزان (غير سالبة) في Rd. نحن نعتبر مشكلة حساب مجموعة فرعية من (حد أقصى) k نقاط متنوعة وعالية القيمة من P التي تقع داخل نطاق استعلام، وهي مشكلة ذات صلة بالعديد من المجالات مثل محركات البحث، وأنظمة التوصية، والمتاجر الإلكترونية. يتم قياس التنوع والقيمة لمجموعة من النقاط كوظائف (مثل المتوسط أو الحد الأدنى) للمسافات والأوزان المزدوجة، على التوالي. ندرس مشكلات تحسين ثنائية المعايير ومقيدة. في الأولى، نرغب في إرجاع مجموعة من k نقاط تعظم مجموعًا وزنيًا لمقاييس القيمة والتنوع الخاصة بها، وفي الأخيرة، نرغب في إرجاع مجموعة من (حد أقصى) k نقاط تعظم قيمتها وتفي بفرض قيود على التنوع. نحصل على ثلاثة أنواع رئيسية من النتائج في هذه الورقة: خوارزميات تقريبية بوقت قريب من الخطي (0.5-ε) لمشكلة تحسين ثنائية المعايير في الوضع غير المتصل. فهارس بحجم قريب من الخطي لمشكلة تحسين ثنائية المعايير التي تعيد حلاً تقريبيًا (0.5-ε) في وقت O(k polylog(n)) لمستطيل الاستعلام. يمكن بناء الفهارس في وقت O(n polylog(n)). فهارس بحجم قريب من الخطي للإجابة على استعلامات تحسين النطاق المقيدة. لمستطيل الاستعلام، يمكن حساب حل تقريبي 0.5O(d) في وقت O(k polylog(n)). إذا سمحنا لبعض النقاط المعادة أن تقع على الأكثر ε خارج مستطيل الاستعلام، فإن حلاً تقريبيًا (1-ε) يمكن حسابه في وقت O(k polylog(n)). يتم بناء الفهارس في وقت O(n polylog(n)) وnO(1/εd) على التوالي.