Computer Data Center 2
Thông tin công nghệ

Đột phá lý thuyết tại MIT có thể tăng khả năng lưu trữ dữ liệu

Computer Data Center

Công việc mới về bảng băm thăm dò tuyến tính từ MIT CSAIL có thể dẫn đến việc lưu trữ và truy xuất dữ liệu hiệu quả hơn trong máy tính.

Bộ ba nhà nghiên cứu bao gồm William Kuszmaul – một nghiên cứu sinh về khoa học máy tính tại MIT – đã thực hiện một khám phá có thể dẫn đến việc lưu trữ và truy xuất dữ liệu hiệu quả hơn trong máy tính.

Phát hiện của nhóm liên quan đến cái gọi là “bảng băm thăm dò tuyến tính”, được giới thiệu vào năm 1954 và là một trong những cấu trúc dữ liệu lâu đời nhất, đơn giản nhất và nhanh nhất hiện nay. Cấu trúc dữ liệu cung cấp các cách tổ chức và lưu trữ dữ liệu trong máy tính, với bảng băm là một trong những cách tiếp cận được sử dụng phổ biến nhất. Trong bảng băm thăm dò tuyến tính, các vị trí mà thông tin có thể được lưu trữ nằm dọc theo một mảng tuyến tính.

Ví dụ, giả sử rằng một cơ sở dữ liệu được thiết kế để lưu trữ số An sinh xã hội của 10.000 người, Kuszmaul gợi ý. “Chúng tôi lấy số An sinh xã hội của bạn, x, và sau đó chúng tôi sẽ tính toán hàm băm của x, h (x), cung cấp cho bạn một số ngẫu nhiên từ một đến 10.000.” Bước tiếp theo là lấy số ngẫu nhiên đó, h (x), đi đến vị trí đó trong mảng và đặt x, số An sinh xã hội, vào vị trí đó.

Nếu đã có thứ gì đó chiếm giữ vị trí đó, Kuszmaul nói, “bạn chỉ cần tiến tới vị trí trống tiếp theo và đặt nó ở đó. Đây là nguồn gốc của thuật ngữ ‘thăm dò tuyến tính’, khi bạn tiếp tục tiến lên một cách tuyến tính cho đến khi bạn tìm thấy một điểm mở. ” Để sau này lấy số An sinh xã hội, x, bạn chỉ cần đi đến vị trí được chỉ định, h (x), và nếu không có ở đó, bạn tiến lên phía trước cho đến khi bạn tìm thấy x hoặc đến vị trí tự do và kết luận rằng x là không có trong cơ sở dữ liệu của bạn.

Có một giao thức hơi khác để xóa một mục, chẳng hạn như số An sinh xã hội. Nếu bạn chỉ để lại một vị trí trống trong bảng băm sau khi xóa thông tin, điều đó có thể gây ra nhầm lẫn khi bạn cố gắng tìm thứ khác sau đó, vì vị trí trống có thể gợi ý sai rằng mục bạn đang tìm không được tìm thấy ở đó kho dữ liệu. Để tránh vấn đề đó, Kuszmaul giải thích, “bạn có thể đến nơi mà phần tử đã bị loại bỏ và đặt một điểm đánh dấu nhỏ ở đó gọi là ‘bia mộ’, cho biết từng có một phần tử ở đây, nhưng giờ nó đã biến mất.”

Thủ tục chung này đã được tuân thủ trong hơn nửa thế kỷ. Nhưng trong khoảng thời gian đó, hầu như tất cả mọi người sử dụng bảng băm thăm dò tuyến tính đều cho rằng nếu bạn cho phép chúng quá đầy, các điểm bị chiếm đóng kéo dài sẽ chạy lại với nhau để tạo thành “cụm”. Kết quả là, thời gian cần thiết để tìm thấy một vị trí trống sẽ tăng lên đáng kể – trên thực tế, theo bậc hai – mất nhiều thời gian đến mức không thực tế. Do đó, mọi người đã được đào tạo để vận hành bảng băm ở công suất thấp – một phương pháp có thể chính xác hóa một khoản phí kinh tế bằng cách ảnh hưởng đến lượng phần cứng mà một công ty phải mua và bảo trì.

Nhưng nguyên tắc được tôn vinh từ lâu này, vốn được sử dụng từ lâu để chống lại các yếu tố tải cao, đã hoàn toàn bị ảnh hưởng bởi công trình nghiên cứu của Kuszmaul và các đồng nghiệp của ông, Michael Bender của Đại học Stony Brook và Bradley Kuszmaul của Google. Họ phát hiện ra rằng đối với các ứng dụng mà số lần chèn và số lần xóa vẫn bằng nhau – và lượng dữ liệu được thêm vào gần tương đương với số lần bị xóa – bảng băm thăm dò tuyến tính có thể hoạt động ở dung lượng lưu trữ cao mà không bị giảm tốc độ.

Ngoài ra, nhóm nghiên cứu đã nghĩ ra một chiến lược mới, được gọi là “băm nghĩa địa”, liên quan đến việc tăng số lượng bia mộ được đặt trong một mảng một cách giả tạo cho đến khi chúng chiếm khoảng một nửa số vị trí trống. Những tấm bia mộ này sau đó dành chỗ trống có thể được sử dụng cho những lần chèn trong tương lai.

Kuszmaul nói, cách tiếp cận này, trái ngược với những gì mọi người thường được hướng dẫn làm, “có thể dẫn đến hiệu suất tối ưu trong các bảng băm thăm dò tuyến tính”. Hoặc, như anh và các đồng tác giả của mình khẳng định trong bài báo của mình, “việc sử dụng bia mộ được thiết kế tốt có thể thay đổi hoàn toàn… cảnh quan về cách hoạt động của hoạt động thăm dò tuyến tính”.

Kuszmaul đã viết những phát hiện này cùng với Bender và Kuszmaul trong một bài báo được đăng vào đầu năm nay và sẽ được trình bày vào tháng 2 tại Hội nghị chuyên đề về Khoa học Máy tính (FOCS) ở Boulder, Colorado.

Cố vấn luận án Tiến sĩ của Kuszmaul, giáo sư khoa học máy tính Charles E. Leiserson của MIT (người không tham gia nghiên cứu này), đồng ý với đánh giá đó. “Những kết quả mới và đáng ngạc nhiên này đã lật ngược một trong những quan niệm thông thường lâu đời nhất về hành vi của bảng băm,” Leiserson nói. “Các bài học sẽ vang dội trong nhiều năm giữa các nhà lý thuyết và các nhà thực hành.”

Về việc chuyển các kết quả của họ vào thực tế, Kuszmaul lưu ý, “có rất nhiều cân nhắc khi xây dựng bảng băm. Mặc dù chúng tôi đã nâng cao câu chuyện đáng kể từ quan điểm lý thuyết, nhưng chúng tôi chỉ mới bắt đầu khám phá khía cạnh thử nghiệm của mọi thứ. “

Tài liệu tham khảo: “Kiểm tra lại tuyến tính: Bia mộ Đánh dấu cái chết của Phân cụm sơ cấp” của Michael A. Bender, Bradley C. Kuszmaul và William Kuszmaul, ngày 2 tháng 7 năm 2021, Khoa học máy tính> Cấu trúc dữ liệu và thuật toán .
arXiv: 2107.01250

Theo Scitechdaily

What's your reaction?

Excited
0
Happy
0
In Love
0
Not Sure
0

You may also like

Leave a reply

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *

Website này sử dụng Akismet để hạn chế spam. Tìm hiểu bình luận của bạn được duyệt như thế nào.