العثور على مجموعات مجموعات فرعية محددة

Question

أنا طالب دراسات عليا في الفيزياء و أنا أعمل على كتابة بعض التعليمات البرمجية إلى نوع عدة مئات غيغابايت من البيانات والعودة شرائح البيانات عندما كنت تسأل عن ذلك.هنا هو خدعة, أنا لا أعرف أي طريقة جيدة الفرز والبحث البيانات من هذا النوع.

البيانات أساسا يتكون من عدد كبير من مجموعات من الأرقام.هذه المجموعات يمكن أن تحتوي على أي مكان من 1 إلى n عدد داخلها (وإن كان في 99.9% من مجموعات, n أقل من 15) و هناك ما يقرب من 1.5 ~ 2 مليار دولار من هذه المجموعات (للأسف هذا الحجم يحول دون القوة الغاشمة البحث).

أنا بحاجة إلى أن تكون قادرة على تحديد مجموعة مع ك عناصر كل مجموعة مع k+1 عناصر أو أكثر يحتوي على المحدد فرعية عاد لي.

مثال بسيط:
لنفترض أن لدى المجموعات التالية عن البيانات:
(1,2,3)
(1,2,3,4,5)
(4,5,6,7)
(1,3,8,9)
(5,8,11)

إذا كنت تعطي الطلب (1,3) لكنت مجموعات:(1,2,3), (1,2,3,4,5) ، و (1,3,8,9).
طلب (11) سيعود مجموعة:(5,8,11).
طلب (1,2,3) سيعود مجموعات:(1,2,3) و (1,2,3,4,5)
الطلب (50) سيعود لا مجموعات:

الآن نمط ينبغي أن يكون واضحا.الفرق الرئيسي بين هذا المثال و هي أن مجموعات التنحي عن الحكم بياناتي هي أكبر الأرقام المستخدمة لكل عنصر من مجموعات المدى من 0 إلى 16383 (14 بت), و هناك العديد من العديد من العديد من مجموعات.

إذا كان يهم أنا أكتب هذا البرنامج في C++ على الرغم من أنني أعلم أيضا java, c, بعض للجمعية بعض fortran, وبعض بيرل.

هل لدى أحدكم أي فكرة عن كيفية فعل هذا ؟

تحرير:
للإجابة على بعض الأسئلة و إضافة بضع نقاط:

1.) البيانات لا تتغير.وقد اتخذ كل ما في واحد طويل تعيين من يدير (كل كسر في 2 أزعج الملفات).

2.) أما بالنسبة لمساحة التخزين.البيانات الخام يستغرق ما يقرب من 250 غيغابايت.أقدر أنه بعد تجهيز تجريد قبالة الكثير من دخيلة الفوقية التي لا تعنيني في بإمكاني أن أسفل إلى أي مكان من 36 إلى 48 جيجابايت اعتمادا على مقدار البيانات الوصفية قررت أن تبقي (بدون مؤشرات).بالإضافة إلى ذلك إذا كان في بلدي الأولية معالجة البيانات واجهت ما يكفي من مجموعات التي هي نفسها قد تكون قادرة على comress البيانات بعد أخرى عن طريق إضافة عدادات تكرار الأحداث بدلا من مجرد تكرار الأحداث مرارا وتكرارا.

3.) كل رقم داخل معالجتها في الحقيقة يحتوي على اثنين على الأقل من عدد 14 بت البيانات نفسها (الكشف عن الطاقة) و 7 بت البيانات الوصفية (كشف رقم).لذا سوف تحتاج على الأقل ثلاث بايت لكل عدد.

4.) بلدي "على الرغم من 99.9 ٪ من مجموعات, n أقل من 15" تعليق مضللة.في أولي وهلة من خلال بعض قطع من البيانات أجد أن لدي مجموعات التي تحتوي على العديد من 22 أرقام ولكن المتوسط هو 5 أرقام لكل مجموعة و متوسط 6 أرقام لكل مجموعة.

5.) بينما أنا أحب فكرة بناء مؤشر من المؤشرات في الملفات أنا قليلا حذرة لأن الطلبات التي تنطوي على أكثر من رقم واحد أنا غادرت مع شبه بطيئة المهمة (على الأقل أعتقد أنها بطيئة) من العثور على مجموعة من المؤشرات المشتركة بين القوائم ، أي إيجاد المشترك الأكبر فرعية لعدد معين من مجموعات.

6.) من حيث الموارد المتاحة لي يمكن حشده حوالي 300 العربات الفضائية بعد البيانات الخام على النظام (ما تبقى من نصيبي على هذا النظام).النظام هو معالج ثنائي مع الخادم 2 quad core amd opterons و 16 غيغابايت من ذاكرة الوصول العشوائي.

7.) نعم 0 يمكن أن يحدث ، هو قطعة أثرية من نظام الحصول على البيانات عندما لا ولكن يمكن أن تحدث.

Answer 1

لقد اكتشفت مؤخرا الأساليب التي تستخدم منحنيات ملء الفضاء إلى خريطة البيانات متعددة الأبعاد وصولا إلى بعد واحد.يمكن للمرء ثم مؤشر البيانات على أساس 1D مؤشر.مجموعة استفسارات يمكن حملها بسهولة من خلال إيجاد قطاعات منحنى التي تتقاطع المربع الذي يمثل المنحنى ومن ثم استرجاع تلك القطاعات.

وأعتقد أن هذه الطريقة هي أفضل بكثير مما مجنون الفهارس كما اقترح لأن بعد النظر في ذلك ، فإن مؤشر ستكون كبيرة مثل البيانات تمنيت أن المتجر لا يكاد شيء جيد.إلى حد ما شرح أكثر تفصيلا من هذا يمكن العثور عليها في:

http://www.ddj.com/184410998
و
http://www.dcs.bbk.ac.uk/~jkl/publications.html

Answer 2

مشكلتك هي نفس التي تواجه محركات البحث."لدي ملايين الوثائق.أنا في حاجة إلى تلك التي تحتوي على هذه المجموعة من الكلمات." لديك فقط (مريح جدا), الصحيحه بدلا من الكلمات ، يشرفوا الوثائق.الحل هو مؤشر مقلوب. مقدمة في استرجاع المعلومات قبل مانينغ وآخرون (على هذا الرابط) المتاحة مجانا على الانترنت, جدا للقراءة و الخوض في الكثير من التفاصيل حول كيفية القيام بذلك.

عليك أن تدفع الثمن في مساحة القرص ، ولكن يمكن أن تكون بشكل متوازي ، يجب أن تكون سريعة بما يكفي لتلبية المتطلبات الزمنية ، مرة واحدة في المؤشر هي التي شيدت.

Answer 3

على افتراض توزيع عشوائي من 0-16383 مع ثابت 15 عنصرا في مجموعة ، ملياري مجموعات ، كل عنصر سوف تظهر في حوالي 1.8 M مجموعات.هل تعتبر (و هل لديك القدرة على) بناء 16384x~1.8 M (30B إدخالات 4 بايت لكل منهما) بحث الطاولة ؟ وبالنظر إلى هذا الجدول ، يمكن الاستعلام الذي مجموعات تحتوي على (1) و (17) و (5555) ومن ثم العثور على التقاطعات من هؤلاء الثلاثة ~1.8 M-عناصر القوائم.

Answer 4

تخميني هو على النحو التالي.

نفترض أن كل مجموعة لها اسم أو هوية أو عنوان (4 بايت عدد سوف تفعل إذا كان هناك فقط 2 مليار منهم).

الآن المشي من خلال جميع مجموعات مرة و إنشاء الإخراج التالي الملفات:

• وهو الملف الذي يحتوي على معرفات جميع مجموعات التي تحتوي على '1'
• وهو الملف الذي يحتوي على معرفات جميع مجموعات التي تحتوي على '2'
• وهو الملف الذي يحتوي على معرفات جميع مجموعات التي تحتوي على '3'
• ...الخ ...

إذا كان هناك 16 إدخالات لكل مجموعة ، ثم في المتوسط كل من هذه 2^16 ملفات تحتوي على معرفات 2^20 مجموعات ؛ مع كل ID = 4 بايت ، وهذا يتطلب 2^38 بايت (256 GB) من التخزين.

عليك أن تفعل ما سبق مرة قبل عملية الطلبات.

عندما تتلقى طلبات استخدام هذه الملفات على النحو التالي:

• نظرة على بعض الأرقام في طلب
• فتح اثنين من مؤشر المقابلة الملفات
• الحصول على قائمة من كافة مجموعات والتي توجد في كل من هذه الملفات (هناك فقط مليون معرفات في كل ملف ، لذلك يجب أن لا يكون صعبا)
• ترى أي من هذه مجموعات قليلة تلبية ما تبقى من الطلب

تخميني هو أنه إذا كنت تفعل أعلاه ، وخلق سيتم الفهارس (جدا) بطء التعامل مع الطلبات (جدا) سريعة.

Answer 5

جعل 16383 ملفات فهرس واحد لكل ممكن من قيمة البحث.لكل قيمة في مجموعة الإدخال, كتابة ملف الموقف من بداية تعيين في المقابلة مؤشر الملف.المهم أن كل من مؤشر ملفات تحتوي على نفس العدد لنفس المجموعة.الآن كل مؤشر الملف سوف تتكون من الصعود الفهارس في الملف الرئيسي.

البحث تبدأ في قراءة مؤشر الملفات المقابلة لكل قيمة البحث.إذا كنت قراءة المؤشر أقل من مؤشر تقرأ من ملف آخر, تخلص منه و قراءة آخر.عندما يمكنك الحصول على نفس المؤشر من جميع الملفات, هذه المباراة على مجموعة من الملفات الرئيسية ، قراءة مؤشر جديد من كل من مؤشر الملفات.بمجرد أن تصل إلى نهاية أي مؤشر ملفات الانتهاء من ذلك.

إذا كانت القيم التي يتم توزيعها بالتساوي على كل مؤشر الملف سوف تحتوي على 1/16383 من مجموعات الإدخال.إذا كان متوسط البحث مجموعة تتكون من 6 قيم سوف تفعل الخطية تمر على 6/16383 الأصلي الخاص بك الإدخال.انها لا تزال O(n) الحل ، ولكن ن أصغر قليلا الآن.

P. S.هو الصفر مستحيلة نتيجة قيمة أو هل لديك حقا 16384 الاحتمالات ؟

Answer 6

فقط تلعب محامي الشيطان على النهج الذي يشمل القوة الغاشمة + فهرس البحث :

1. إنشاء فهرس مع الحد الأدنى والحد الأقصى أي من عناصر مجموعات.
2. ثم تطبيق القوة الغاشمة باستثناء مجموعات حيث ماكس < ماكس(مجموعة البحث) و مين > مين (مجموعة البحث)
3. في القوة الغاشمة أيضا استبعاد مجموعات كل عنصر العدد هو أقل من ذلك من تعيين يتم البحث عنها.

95% من عمليات البحث الخاصة بك سيكون حقا الغاشمة مما اضطر جدا فرعية أصغر.مجرد فكرة.