Standard versus uniform binary search and their variants in learned static indexing: The case of the searching on sorted data benchmarking software platform. (6th September 2022)
- Record Type:
- Journal Article
- Title:
- Standard versus uniform binary search and their variants in learned static indexing: The case of the searching on sorted data benchmarking software platform. (6th September 2022)
- Main Title:
- Standard versus uniform binary search and their variants in learned static indexing: The case of the searching on sorted data benchmarking software platform
- Authors:
- Amato, Domenico
Lo Bosco, Giosué
Giancarlo, Raffaele - Abstract:
- Abstract: Learned Indexes use a model to restrict the search of a sorted table to a smaller interval. Typically, a final binary search is done using the lower_bound routine of the Standard C++ library. Recent studies have shown that on current processors other search approaches (such as k‐ary search) can be more efficient in some applications. Using the SOSD learned indexing benchmarking software, we extend these results to show that k‐ary search is indeed a better choice when using learned indexes. We highlight how such a choice may be dependent on the computer architecture used, for example, Intel I7 or Apple M1, and provide guidelines for the selection of the Search routine within the learned indexing framework.
- Is Part Of:
- Software, practice & experience. Volume 53:Number 2(2023)
- Journal:
- Software, practice & experience
- Issue:
- Volume 53:Number 2(2023)
- Issue Display:
- Volume 53, Issue 2 (2023)
- Year:
- 2023
- Volume:
- 53
- Issue:
- 2
- Issue Sort Value:
- 2023-0053-0002-0000
- Page Start:
- 318
- Page End:
- 346
- Publication Date:
- 2022-09-06
- Subjects:
- algorithms with prediction -- binary search variants -- learned index structures -- search on sorted data platform
Computer software -- Periodicals
Computer programming -- Periodicals
Computer programs -- Periodicals
005.3 - Journal URLs:
- http://onlinelibrary.wiley.com/ ↗
- DOI:
- 10.1002/spe.3150 ↗
- Languages:
- English
- ISSNs:
- 0038-0644
- Deposit Type:
- Legaldeposit
- View Content:
- Available online (eLD content is only available in our Reading Rooms) ↗
- Physical Locations:
- British Library DSC - 8321.453000
British Library DSC - BLDSS-3PM
British Library STI - ELD Digital store - Ingest File:
- 25662.xml