อัลกอริทึม วิธีค้นหา POI ที่ใกล้ที่สุดถึง 1 ล้านพิกัดอย่างมีประสิทธิภาพ

นี่คือโพสต์สัมภาษณ์ที่ฉันจำเป็นต้องดำเนินการนี้--

ดังนั้นฉันจึงได้รับรายชื่อ POI ของร้านอาหาร (ประมาณ 2,000 แห่ง) ในพิกัดแบบยุคลิด

ฉันได้รับรายการพิกัดผู้ใช้ (1 ล้านพิกัด)

ฉันได้รับมอบหมายให้ส่งคืนจำนวนผู้ใช้ที่อยู่ในรัศมีหนึ่ง (10,15) ของ POI เดียว และประการที่สอง รัศมีที่ต้องการสำหรับผู้ใช้ 75% จะต้องอยู่ภายในระยะห่างจาก POI หนึ่งแห่ง

ระยะทางเป็นสิ่งที่ฉันคำนวณได้ แต่การบังคับอย่างโหดเหี้ยมหมายถึงการตรวจสอบ 1 ล้านพิกัดสำหรับ 1,000 พิกัด ซึ่งใช้เวลานานมาก

อะไรจะมีประสิทธิภาพมากกว่าในการทำเช่นนี้แทน?


java geocoding algorithm
person user3394313    schedule 30.10.2017    source แหล่งที่มา
comment
มีหลายวิธีในการทำ แต่โดยพื้นฐานแล้ว คุณควรแบ่งพื้นที่ออกเป็นส่วนๆ ที่ควรค่าแก่การค้นหา และส่วนต่างๆ ที่ไม่คุ้มที่จะค้นหา   -  person Andy Turner    schedule 31.10.2017
comment
คุณอาจต้องการค้นหา 'โครงสร้างข้อมูลเชิงพื้นที่' โดยเฉพาะ R-tree   -  person Ivan Smirnov    schedule 31.10.2017
comment
สำหรับปัญหาแรก: การลดแผนที่อาจเป็นอีกวิธีหนึ่ง (การใช้ทรัพยากร) สำหรับปัญหาที่สอง: จัดกลุ่มคะแนนแล้วคำนวณ POI ที่ใกล้กับผู้ใช้มากที่สุด จากนั้นเพิ่มรัศมีให้ครอบคลุม 75% ของระยะทาง user_poi เหล่านั้น   -  person displayName    schedule 01.11.2017

คำตอบ (2)


arrow_upward
1
arrow_downward

ควรใช้กรอบงานที่ช่วยให้คุณสามารถจัดทำดัชนีพิกัดเชิงพื้นที่และเรียกใช้ตัวดำเนินการเชิงพื้นที่ที่มีประสิทธิภาพ Mapinfo, ฐานข้อมูลเชิงพื้นที่ (Oracle Spatial - ซึ่งอาจต้องมีใบอนุญาตเพิ่มเติมสำหรับการใช้งานจริง), ESRI, โอเพ่นซอร์ส ฯลฯ

โดยปกติแล้วการกระทำก็จะเป็น

  1. โหลด POI ในภาชนะที่มีการจัดทำดัชนีเชิงพื้นที่ (ตารางที่มีดัชนีเชิงพื้นที่)
  2. โหลดผู้ใช้ในคอนเทนเนอร์ที่มีการจัดทำดัชนีเชิงพื้นที่
  3. ขยาย POI ให้เป็นวัตถุทรงกลมที่มีรัศมีระยะทางที่ต้องการ
  4. เข้าร่วม/รวมเชิงพื้นที่สำหรับผู้ใช้ภายในแวดวง POI

การรวมเชิงพื้นที่/การรวมเชิงพื้นที่เหล่านั้นมีให้เลือกใช้ในรูปแบบต่างๆ ของตัวดำเนินการเชิงพื้นที่

หากคุณเพียงต้องการสร้างผลลัพธ์โดยเป็นส่วนหนึ่งของแบบฝึกหัด และคุณไม่สามารถใช้กรอบงานใดๆ ได้ ฉันขอแนะนำให้ใช้แนวทางง่ายๆ สองสามวิธี

จริงๆ แล้วผู้ใช้ 1 ล้านคนนั้นไม่ได้มีขนาดใหญ่มากนัก - สามารถจัดการได้ - ปัญหาคือคะแนนเหล่านี้จะต้องได้รับการประเมินเทียบกับ 2,000 POI ฉันเชื่อว่าวิธีที่ดีที่สุดคือ

  1. สร้างสี่เหลี่ยมล้อมรอบจุดที่น่าสนใจก่อนโดยใช้รัศมี 2 x เป็นด้านข้าง
  2. ซึ่งจะช่วยให้คุณสามารถประเมินได้อย่างรวดเร็วว่าจุดใดที่น่าสนใจสำหรับ POI แต่ละจุด โดยหลักการแล้วจะใช้เฉพาะมากกว่าหรือน้อยกว่าเท่านั้นเป็นตัวดำเนินการ
  3. การมีกลุ่มผู้ใช้สำหรับแต่ละ POI คุณสามารถจำกัดให้แคบลงได้โดยการคำนวณระยะทางจริง

คุณสามารถใช้ประโยชน์จากการจัดทำดัชนีและการเรียงลำดับอัจฉริยะทุกประเภทเพื่อให้การดำเนินการนี้เร็วขึ้นมาก R-Tree ที่แนะนำในความคิดเห็นดูเหมือนจะเหมาะสมอย่างยิ่งหากคุณมีเวลาในการดำเนินการ นี่จะช่วยคุณในขั้นตอนที่สองข้างต้น

วิธีที่ง่ายกว่ามาก - ขึ้นอยู่กับว่าพิกัดของคุณถูกจัดวางอย่างไร (โลกของคุณมีลักษณะอย่างไร) คือการแบ่งโลกของคุณออกเป็นสี่เหลี่ยมจัตุรัสที่ใหญ่ขึ้น และขั้นแรกจะต้องกำหนดสำหรับผู้ใช้แต่ละคนและแต่ละ POI ว่าพวกเขาอยู่ในสี่เหลี่ยมจัตุรัสใด คุณสามารถกำหนดผู้ใช้ทั้งหมดภายในจัตุรัสเดียวกันของ POI หรือจัตุรัสใกล้เคียงว่าเป็นผู้ใช้ที่สนใจได้อย่างรวดเร็ว คิดแผนดัชนี/ลำดับเลขอันชาญฉลาดที่สามารถช่วยคุณระบุเพื่อนบ้านได้เช่นกัน ให้รายชื่อผู้ใช้จัดทำดัชนีไปยังช่องสี่เหลี่ยมของตนผ่าน Hashmaps

person YoYo    schedule 30.10.2017
comment
ขออภัยสำหรับข้อจำกัดเพิ่มเติม ฉันไม่ได้รับอนุญาตให้ใช้เฟรมเวิร์กภายนอกที่สร้างไว้แล้ว - person user3394313; 31.10.2017

arrow_upward
0
arrow_downward

ใช้โครงสร้างข้อมูลหรือฐานข้อมูลการค้นหาเชิงพื้นที่และทำการสืบค้นที่เหมาะสม

เพื่อให้รัศมีล้อมรอบผู้ใช้ 75% คุณสามารถค้นหารัศมีแบบไบนารีได้เสมอโดยใช้จำนวนผู้ใช้ทั้งหมดที่ทราบและพิกัดด้านนอกสุด

person sleeplessnerd    schedule 30.10.2017