Instance-Optimized Data Structures for Membership Queries
We are near the end of Moore’s law and hardware growth has hit a stagnation. Modern data processing systems need to continuously improve their performance to match the humongous growth of data. Data structures and algorithms such as sorting, indexes, filters, hash tables, query optimization, etc are...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Thesis |
| Published: |
Massachusetts Institute of Technology
2023
|
| Online Access: | https://hdl.handle.net/1721.1/150074 |
| _version_ | 1826200019199328256 |
|---|---|
| author | Vaidya, Kapil Eknath |
| author2 | Kraska, Tim |
| author_facet | Kraska, Tim Vaidya, Kapil Eknath |
| author_sort | Vaidya, Kapil Eknath |
| collection | MIT |
| description | We are near the end of Moore’s law and hardware growth has hit a stagnation. Modern data processing systems need to continuously improve their performance to match the humongous growth of data. Data structures and algorithms such as sorting, indexes, filters, hash tables, query optimization, etc are the fundamental building blocks of these systems and dictate their performance. Traditional data structures and algorithms provide worst-case guarantees by making no assumptions about the data or workload. Thus, the resulting data processing system gives an adequate performance in the average case but may not be optimal for a particular use case. In this thesis, we will look at how to redesign membership query data structures so they can automatically adapt to an individual use case. These instance-optimized data structures act as drop in replacements for their counterparts in systems and improve their performance without any significant overhaul of the system or labor-intensive manual tuning. |
| first_indexed | 2024-09-23T11:29:34Z |
| format | Thesis |
| id | mit-1721.1/150074 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T11:29:34Z |
| publishDate | 2023 |
| publisher | Massachusetts Institute of Technology |
| record_format | dspace |
| spelling | mit-1721.1/1500742023-04-01T03:38:53Z Instance-Optimized Data Structures for Membership Queries Vaidya, Kapil Eknath Kraska, Tim Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science We are near the end of Moore’s law and hardware growth has hit a stagnation. Modern data processing systems need to continuously improve their performance to match the humongous growth of data. Data structures and algorithms such as sorting, indexes, filters, hash tables, query optimization, etc are the fundamental building blocks of these systems and dictate their performance. Traditional data structures and algorithms provide worst-case guarantees by making no assumptions about the data or workload. Thus, the resulting data processing system gives an adequate performance in the average case but may not be optimal for a particular use case. In this thesis, we will look at how to redesign membership query data structures so they can automatically adapt to an individual use case. These instance-optimized data structures act as drop in replacements for their counterparts in systems and improve their performance without any significant overhaul of the system or labor-intensive manual tuning. Ph.D. 2023-03-31T14:30:02Z 2023-03-31T14:30:02Z 2023-02 2023-02-28T14:39:50.935Z Thesis https://hdl.handle.net/1721.1/150074 In Copyright - Educational Use Permitted Copyright MIT http://rightsstatements.org/page/InC-EDU/1.0/ application/pdf Massachusetts Institute of Technology |
| spellingShingle | Vaidya, Kapil Eknath Instance-Optimized Data Structures for Membership Queries |
| title | Instance-Optimized Data Structures for Membership Queries |
| title_full | Instance-Optimized Data Structures for Membership Queries |
| title_fullStr | Instance-Optimized Data Structures for Membership Queries |
| title_full_unstemmed | Instance-Optimized Data Structures for Membership Queries |
| title_short | Instance-Optimized Data Structures for Membership Queries |
| title_sort | instance optimized data structures for membership queries |
| url | https://hdl.handle.net/1721.1/150074 |
| work_keys_str_mv | AT vaidyakapileknath instanceoptimizeddatastructuresformembershipqueries |