New method accelerates data retrieval in huge databases.

นักวิจัยจาก MIT ได้พัฒนาวิธีการ machine learning ที่สร้างฟังก์ชันแฮช (hash functions) ที่มีการชนกันน้อยกว่าวิธีดั้งเดิม การแฮชใช้สำหรับการจัดทำดัชนีฐานข้อมูล การบีบอัดข้อมูล และการเข้ารหัส รวมถึงแอปพลิเคชันอื่นๆ แต่การชนกันอาจทำให้การค้นหาช้าลงและส่งผลกระทบต่อประสิทธิภาพ นักวิจัยใช้โมเดลการเรียนรู้ที่ลดการชนกันในบางสถานการณ์ โดยเพิ่มเวลาในการคำนวณสำหรับฟังก์ชันแฮชเพื่อลดการชนกันอย่างมาก นักวิจัยพบว่าโมเดลที่เรียนรู้นั้นสร้างได้เร็วกว่าและง่ายกว่าฟังก์ชันแฮชที่สมบูรณ์แบบ แต่สังเกตว่าวิธีการนี้อาจทำให้เกิดการชนกันมากขึ้นหากช่องว่างระหว่างจุดข้อมูลแตกต่างกันมากเกินไป

Researchers from MIT have developed a machine learning approach that builds hash functions with fewer collisions than traditional methods. Hashing is used for database indexing, data compression and cryptography, among other applications, but collisions can slow searches and impact performance. The researchers used learned models that reduce collisions in certain situations, with the computation time for the hash function increased to reduce collisions significantly. The researchers found that learned models were faster and easier to build than perfect hash functions, but noted that the approach may cause more collisions if the gaps between data points vary too widely.

MIT พัฒนาวิธีการใหม่ช่วยเร่งการดึงข้อมูลในฐานข้อมูลขนาดใหญ่

นักวิจัยใช้แมชชีนเลิร์นนิงเพื่อสร้างฟังก์ชันแฮชที่รวดเร็วและมีประสิทธิภาพมากขึ้น ซึ่งเป็นองค์ประกอบสำคัญของฐานข้อมูล

การแฮชเป็นการดำเนินการหลักในฐานข้อมูลออนไลน์ส่วนใหญ่ เช่น แคตตาล็อกห้องสมุดหรือเว็บไซต์อีคอมเมิร์ซ ฟังก์ชันแฮชสร้างรหัสที่กำหนดตำแหน่งที่จะจัดเก็บข้อมูลโดยตรง ดังนั้น เมื่อใช้รหัสเหล่านี้ การค้นหาและดึงข้อมูลจะง่ายขึ้น

อย่างไรก็ตาม เนื่องจากฟังก์ชันแฮชแบบดั้งเดิมสร้างรหัสแบบสุ่ม บางครั้งข้อมูลสองส่วนสามารถถูกแฮชด้วยค่าเดียวกันได้ ซึ่งทำให้เกิดการชนกัน — เมื่อค้นหารายการหนึ่งๆ จะชี้ผู้ใช้ไปยังข้อมูลหลายชิ้นที่มีค่าแฮชเดียวกัน การค้นหาที่ถูกต้องใช้เวลานานกว่ามาก ส่งผลให้การค้นหาช้าลงและประสิทธิภาพลดลง

ฟังก์ชันแฮชบางประเภทเรียกว่าฟังก์ชันแฮชที่สมบูรณ์แบบ ได้รับการออกแบบเพื่อวางข้อมูลในลักษณะที่ป้องกันการชนกัน แต่ใช้เวลานานในการสร้างชุดข้อมูลแต่ละชุดและใช้เวลาในการคำนวณมากกว่าฟังก์ชันแฮชแบบเดิม

เนื่องจากมีการใช้การแฮชในแอปพลิเคชันจำนวนมาก ตั้งแต่การจัดทำดัชนีฐานข้อมูล การบีบอัดข้อมูล ไปจนถึงการเข้ารหัส ฟังก์ชันการแฮชที่รวดเร็วและมีประสิทธิภาพจึงมีความสำคัญอย่างยิ่ง ดังนั้น นักวิจัยจาก MIT และที่อื่น ๆ จึงออกเดินทางเพื่อดูว่าพวกเขาสามารถใช้การเรียนรู้ของเครื่องเพื่อสร้างฟังก์ชันแฮชที่ดีขึ้นได้หรือไม่

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

“สิ่งที่เราพบในงานนี้คือ ในบางสถานการณ์ เราสามารถหาจุดแลกเปลี่ยนที่ดีกว่าระหว่างการคำนวณฟังก์ชันแฮชและการชนกันที่เราจะต้องเจอ ในสถานการณ์เหล่านี้ เวลาในการคำนวณสำหรับฟังก์ชันแฮชสามารถเพิ่มขึ้นได้เล็กน้อย แต่ในขณะเดียวกันการชนกันของมันสามารถลดลงได้อย่างมาก” Ibrahim Sabek, postdoc จาก MIT Data Systems Group of the Computer Science and Artificial Intelligence กล่าว ห้องปฏิบัติการ (CSAIL).

งานวิจัยของพวกเขาซึ่งจะนำเสนอในการประชุมนานาชาติเรื่องฐานข้อมูลขนาดใหญ่มากในปี 2023 แสดงให้เห็นว่าสามารถออกแบบฟังก์ชันแฮชเพื่อเพิ่มความเร็วในการค้นหาในฐานข้อมูลขนาดใหญ่ได้อย่างไร ตัวอย่างเช่น เทคนิคของพวกเขาสามารถเร่งระบบคอมพิวเตอร์ที่นักวิทยาศาสตร์ใช้ในการจัดเก็บและวิเคราะห์ดีเอ็นเอ ลำดับกรดอะมิโน หรือข้อมูลทางชีววิทยาอื่นๆ

Sabek เป็นผู้เขียนร่วมของบทความนี้กับนักศึกษาระดับบัณฑิตศึกษาภาควิชาวิศวกรรมไฟฟ้าและวิทยาการคอมพิวเตอร์ (EECS) Kapil Vaidya พวกเขาเข้าร่วมโดยผู้เขียนร่วม Dominick Horn นักศึกษาระดับบัณฑิตศึกษาที่มหาวิทยาลัยเทคนิคแห่งมิวนิก; Andreas Kipf, postdoc ของ MIT; Michael Mitzenmacher ศาสตราจารย์ด้านวิทยาการคอมพิวเตอร์ที่ Harvard John A. Paulson School of Engineering and Applied Sciences; และผู้เขียนอาวุโส Tim Kraska รองศาสตราจารย์ของ EECS ที่ MIT และผู้อำนวยการร่วมของ Data, Systems และ AI Lab

Hashing it out

เมื่อป้อนข้อมูลหรือคีย์ ฟังก์ชันแฮชแบบดั้งเดิมจะสร้างตัวเลขสุ่มหรือรหัสที่สอดคล้องกับสล็อตที่จะจัดเก็บคีย์นั้น หากต้องการใช้ตัวอย่างง่ายๆ หากมี 10 คีย์ที่ต้องใส่ลงใน 10 ช่อง ฟังก์ชันจะสร้างจำนวนเต็มระหว่าง 1 ถึง 10 สำหรับแต่ละอินพุต มีความเป็นไปได้สูงที่คีย์สองคีย์จะลงเอยในช่องเดียวกัน ทำให้เกิดการชนกัน

ฟังก์ชันแฮชที่สมบูรณ์แบบเป็นทางเลือกที่ปราศจากการชนกัน นักวิจัยให้ความรู้เพิ่มเติมแก่ฟังก์ชัน เช่น จำนวนช่องข้อมูลที่จะใส่เข้าไป จากนั้นจึงทำการคำนวณเพิ่มเติมเพื่อหาตำแหน่งที่จะวางแต่ละคีย์เพื่อหลีกเลี่ยงการชนกัน อย่างไรก็ตาม การคำนวณที่เพิ่มเข้ามาเหล่านี้ทำให้สร้างฟังก์ชันได้ยากขึ้นและมีประสิทธิภาพน้อยลง

“เราสงสัยว่าถ้าเรารู้มากขึ้นเกี่ยวกับข้อมูลที่มาจากการแจกแจงเฉพาะ เราจะสามารถใช้โมเดลที่เรียนรู้เพื่อสร้างฟังก์ชันแฮชที่สามารถลดการชนกันได้จริงหรือ” ไวยา กล่าว

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

นักวิจัยใช้ตัวอย่างเล็กๆ จากชุดข้อมูลและใช้การเรียนรู้ของเครื่องเพื่อประมาณรูปร่างของการกระจายข้อมูลหรือวิธีการกระจายข้อมูล จากนั้นโมเดลที่เรียนรู้จะใช้การประมาณเพื่อทำนายตำแหน่งของคีย์ในชุดข้อมูล

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

“เราอาจมีอินพุตข้อมูลจำนวนมาก และช่องว่างระหว่างอินพุตที่ต่อเนื่องกันนั้นแตกต่างกันมาก ดังนั้นการเรียนรู้โมเดลเพื่อจับการกระจายข้อมูลของอินพุตเหล่านี้จึงค่อนข้างยาก” ซาเบกอธิบาย

Fewer collisions, faster results

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

“เมื่อถึงเกณฑ์หนึ่งของรุ่นย่อย คุณจะได้รับข้อมูลเพียงพอที่จะสร้างค่าประมาณที่คุณต้องการสำหรับฟังก์ชันแฮช แต่หลังจากนั้นจะไม่นำไปสู่การปรับปรุงลดการชนกันอีกต่อไป” Sabek กล่าว

จากการวิเคราะห์นี้ นักวิจัยต้องการใช้โมเดลที่เรียนรู้เพื่อออกแบบฟังก์ชันแฮชสำหรับข้อมูลประเภทอื่นๆ พวกเขายังวางแผนที่จะสำรวจการแฮชที่เรียนรู้สำหรับฐานข้อมูลที่สามารถแทรกหรือลบข้อมูลได้ เมื่อข้อมูลได้รับการอัปเดตด้วยวิธีนี้ โมเดลจำเป็นต้องเปลี่ยนตามนั้น แต่การเปลี่ยนโมเดลโดยที่ยังคงความแม่นยำไว้นั้นเป็นปัญหาที่ยาก

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

“ฟังก์ชันการแฮชและการสร้างดัชนีเป็นแกนหลักของฟังก์ชันฐานข้อมูลจำนวนมาก เนื่องจากความหลากหลายของผู้ใช้และกรณีการใช้งาน จึงไม่มีขนาดใดที่เหมาะกับแฮชทั้งหมด และโมเดลที่เรียนรู้จะช่วยปรับฐานข้อมูลให้เหมาะกับผู้ใช้เฉพาะราย เอกสารฉบับนี้เป็นการวิเคราะห์ที่สมดุลอย่างยิ่งเกี่ยวกับความเป็นไปได้ของเทคนิคใหม่เหล่านี้ และทำหน้าที่ได้ดีในการพูดคุยเกี่ยวกับข้อดีและข้อเสียอย่างเข้มงวด และช่วยให้เราสร้างความเข้าใจว่าเมื่อใดที่วิธีการดังกล่าวคาดว่าจะได้ผลดี” กล่าวโดย Murali Narayanaswamy นักวิทยาศาสตร์ด้านแมชชีนเลิร์นนิงหลักของ Amazon ซึ่งไม่ได้เกี่ยวข้องกับงานนี้ “การสำรวจการปรับปรุงประเภทนี้เป็นพื้นที่ที่น่าตื่นเต้นของการวิจัยทั้งในด้านวิชาการและอุตสาหกรรม และประเภทของความเข้มงวดที่แสดงในงานนี้เป็นสิ่งสำคัญสำหรับวิธีการเหล่านี้ที่จะมีผลกระทบอย่างมาก”

งานนี้ได้รับการสนับสนุนบางส่วนโดย Google, Intel, Microsoft, มูลนิธิวิทยาศาสตร์แห่งชาติของสหรัฐฯ, ห้องปฏิบัติการวิจัยกองทัพอากาศสหรัฐฯ และเครื่องเร่งความเร็วปัญญาประดิษฐ์ของกองทัพอากาศสหรัฐฯ

view original*