Courtesy of QuantaMagazine

Mahasiswa Sarjana Membalikkan Konjektur Ilmu Data yang Sudah Berusia 40 Tahun

10 Feb 2025, 07.00 WIB

92 dibaca

Ikhtisar 15 Detik

Penemuan baru oleh Andrew Krapivin dapat mengubah cara kita memahami hash table.
Hasil penelitian ini membuktikan bahwa dugaan yang telah ada selama 40 tahun bisa salah.
Pentingnya memahami struktur data dapat membuka jalan untuk inovasi di bidang komputer.

Andrew Krapivin, seorang mahasiswa di Rutgers University, menemukan sebuah makalah berjudul "Tiny Pointers" yang mengubah cara pandangnya tentang struktur data dalam ilmu komputer. Setelah dua tahun, ia mengembangkan ide untuk membuat pointer yang lebih kecil dan efisien, yang membawanya pada penemuan jenis baru dari hash table. Hash table adalah struktur data yang digunakan untuk menyimpan informasi dengan cara yang cepat dan efisien. Krapivin menemukan bahwa hash table barunya dapat menemukan elemen lebih cepat daripada yang pernah diperkirakan sebelumnya, sehingga membantah sebuah dugaan yang telah ada selama 40 tahun.

Penemuan ini tidak hanya mengubah pemahaman tentang hash table, tetapi juga menunjukkan bahwa waktu yang dibutuhkan untuk melakukan pencarian dan penyisipan dalam hash table baru ini jauh lebih cepat daripada yang diharapkan. Tim Krapivin, termasuk mantan profesor dan rekan-rekannya, berhasil membuktikan bahwa hash table baru ini dapat memberikan waktu rata-rata yang konstan untuk pencarian, terlepas dari seberapa penuh tabel tersebut. Meskipun hasil ini mungkin tidak langsung diterapkan, pemahaman yang lebih baik tentang struktur data ini dapat membuka peluang baru di masa depan.

Sumber: https://www.quantamagazine.org/undergraduate-upends-a-40-year-old-data-science-conjecture-20250210/

Pertanyaan Terkait

Siapa Andrew Krapivin dan apa penemuan pentingnya?

Andrew Krapivin adalah seorang mahasiswa pascasarjana di University of Cambridge yang menemukan jenis baru dari hash table yang lebih efisien.

Apa itu 'Tiny Pointers' dan bagaimana hubungannya dengan hash table?

'Tiny Pointers' adalah entitas yang mengarahkan ke informasi dalam memori komputer dan menjadi dasar bagi penemuan hash table baru oleh Krapivin.

Apa yang dikatakan Yao tentang hash table dan mengapa itu penting?

Yao menyatakan bahwa dalam kondisi terburuk, waktu pencarian untuk hash table tidak bisa lebih baik dari x, yang menjadi dugaan selama 40 tahun.

Bagaimana penemuan Krapivin membatalkan dugaan Yao?

Penemuan Krapivin menunjukkan bahwa waktu yang dibutuhkan untuk pencarian terburuk adalah proporsional terhadap (log x)2, yang bertentangan dengan dugaan Yao.

Mengapa hasil penelitian ini dianggap penting meskipun tidak ada aplikasi langsung?

Hasil penelitian ini penting untuk pemahaman lebih baik tentang struktur data, yang dapat membuka kemungkinan inovasi di masa depan.