เหตุใด textreuse packge ใน R จึงทำให้ถัง LSH มีขนาดใหญ่กว่า minhashes เดิม

Aug 15 2020

เท่าที่ฉันเข้าใจหนึ่งในหน้าที่หลักของวิธี LSH คือการลดข้อมูลแม้จะอยู่นอกเหนือแฮชที่อยู่เบื้องหลัง ฉันใช้textreuseแพ็คเกจใน R และฉันประหลาดใจกับขนาดของข้อมูลที่สร้างขึ้น textreuseเป็นแพ็คเกจROpenSci ที่ผ่านการตรวจสอบโดยเพื่อนดังนั้นฉันคิดว่ามันทำงานได้อย่างถูกต้อง แต่คำถามของฉันยังคงมีอยู่

สมมติว่าฉันใช้ 256 การเรียงสับเปลี่ยนและ 64 แบนด์สำหรับฟังก์ชัน minhash และ LSH ของฉันตามลำดับ - ค่าจริงที่มักใช้ในการตรวจจับด้วยความคล้ายคลึงกันที่แน่นอน (~ 98%) ต่ำถึง 50%

หากฉันแฮชไฟล์ข้อความแบบสุ่มโดยใช้TextReuseTextDocument(256 perms) และกำหนดให้trtdฉันจะมี:

object.size(trtd$minhashes)
> 1072 bytes

ตอนนี้มาสร้างที่เก็บข้อมูล LSH สำหรับวัตถุนี้ (64 แบนด์) และกำหนดให้lฉันจะมี:

object.size(l$buckets)
> 6704 bytes

ดังนั้นแฮชที่เก็บไว้ในที่เก็บข้อมูล LSH จึงมีขนาดใหญ่กว่ามินแฮชดั้งเดิมหกเท่า ฉันเข้าใจว่าสิ่งนี้เกิดขึ้นเนื่องจากtextreuse ใช้การย่อย md5เพื่อสร้างแฮชที่เก็บข้อมูล

แต่สิ่งนี้ไม่สิ้นเปลือง / มากเกินไปและฉันไม่สามารถปรับปรุงได้หรือไม่? เป็นเรื่องปกติหรือไม่ที่เทคนิคการลดข้อมูลของเราจะทำให้ท้องอืดได้ถึงขนาดนี้? และการจับคู่เอกสารตามแฮชดั้งเดิมนั้นมีประสิทธิภาพมากขึ้นหรือไม่ (คล้ายกับ perms = 256 และ bands = 256) จากนั้นใช้เกณฑ์เพื่อกำจัดผลบวกปลอมหรือไม่?

โปรดทราบว่าฉันได้ตรวจสอบข้อความทั่วไปเช่นMining of Massive Datasetsแล้ว แต่คำถามนี้ยังคงเกี่ยวกับการนำไปใช้งานนี้โดยเฉพาะ นอกจากนี้โปรดทราบว่าคำถามไม่ได้เกิดจากความอยากรู้อยากเห็นเท่านั้น แต่ยังไม่จำเป็นอีกด้วย เมื่อคุณมีแฮชหลายล้านหรือหลายพันล้านแฮชความแตกต่างเหล่านี้จะมีความสำคัญ

คำตอบ

1 LincolnMullen Aug 17 2020 at 03:24

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

คำถามคือคุณต้องการอะไร? หากคุณต้องการค้นหาเฉพาะการจับคู่ที่ใกล้เคียงกัน (เช่นด้วยคะแนน Jaccard ใกล้เคียงกับ 1.0) คุณไม่จำเป็นต้องค้นหาที่ละเอียดอ่อนโดยเฉพาะ อย่างไรก็ตามหากคุณต้องการตรวจจับการแข่งขันที่มีศักยภาพที่เชื่อถือได้ซึ่งแชร์เฉพาะส่วนที่ทับซ้อนกันบางส่วนเท่านั้น (เช่นด้วยคะแนน Jaccard ที่ใกล้เคียงกับ 0) คุณต้องมีแฮช / วงดนตรีเพิ่มเติม

เนื่องจากคุณได้อ่าน MMD แล้วคุณสามารถค้นหาสมการได้ที่นั่น แต่มีฟังก์ชั่นสองอย่างในแพ็คเกจซึ่งมีการบันทึกไว้ที่นี่ซึ่งสามารถช่วยคุณคำนวณจำนวนแฮช / แบนด์ที่คุณต้องการได้ lsh_threshold()จะคำนวณคะแนน Jaccard ตามเกณฑ์ที่จะตรวจพบ ในขณะที่lsh_probability()จะบอกคุณว่ามีความเป็นไปได้เพียงใดที่จะตรวจพบเอกสารคู่ที่มีคะแนน Jaccard ที่ระบุ เล่นกับสองฟังก์ชั่นเหล่านี้จนกว่าคุณจะได้จำนวนแฮช / แบนด์ที่เหมาะสมที่สุดสำหรับปัญหาการค้นหาของคุณ