Selection on X 1  +  X 2  + ⋯ +  X m via Cartesian product trees

Selection on the Cartesian product is a classic problem in computer science. Recently, an optimal algorithm for selection on  +  , based on soft heaps, was introduced. By combining this approach with layer-ordered heaps (LOHs), an algorithm using a balanced binary tree of  +  selections was proposed...

Full description

Saved in:
Bibliographic Details
Published in:PeerJ. Computer science 2021, Vol.7, p.e483-e483, Article e483
Main Authors: Kreitzberg, Patrick, Lucke, Kyle, Pennington, Jake, Serang, Oliver
Format: Article
Language:English
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by cdi_FETCH-LOGICAL-c1366-29b9f3d384d516aeeddaf4284beaf86031e92fa226aad6df7d79a1cdc2d47a223
cites cdi_FETCH-LOGICAL-c1366-29b9f3d384d516aeeddaf4284beaf86031e92fa226aad6df7d79a1cdc2d47a223
container_end_page e483
container_issue
container_start_page e483
container_title PeerJ. Computer science
container_volume 7
creator Kreitzberg, Patrick
Lucke, Kyle
Pennington, Jake
Serang, Oliver
description Selection on the Cartesian product is a classic problem in computer science. Recently, an optimal algorithm for selection on  +  , based on soft heaps, was introduced. By combining this approach with layer-ordered heaps (LOHs), an algorithm using a balanced binary tree of  +  selections was proposed to perform selection on  +   + ⋯ +  in ( ⋅  +  ⋅ ), where have length . Here, that ( ⋅  +  ⋅ ) algorithm is combined with a novel, optimal LOH-based algorithm for selection on  +  (without a soft heap). Performance of algorithms for selection on  +   + ⋯ +  are compared empirically, demonstrating the benefit of the algorithm proposed here.
doi_str_mv 10.7717/peerj-cs.483
format article
fullrecord <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_miscellaneous_2528179817</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>2528179817</sourcerecordid><originalsourceid>FETCH-LOGICAL-c1366-29b9f3d384d516aeeddaf4284beaf86031e92fa226aad6df7d79a1cdc2d47a223</originalsourceid><addsrcrecordid>eNpNkMFKAzEQhoMottTePEuOgm7dJLvJ5iiLWqHgQQVvIU0msGW3W5NdwWfwJfoGvkMfxScx2lYcZpif4ecf-BA6JelECCKuVgB-kZgwyQp2gIaUCZ7kUtLDf3qAxiEs0jQlOYklj9GAMVmILOdDNH2EGkxXtUsc-wUTvFlfbNZR0a36-vjcXxr8Vmlcat9BqPQSr3xre9PhzgOEE3TkdB1gvNsj9Hx781ROk9nD3X15PUsMYZwnVM6lY5YVmc0J1wDWapfRIpuDdgVPGQFJnaaUa225dcIKqYmxhtpMxDMbofNtbvz-2kPoVFMFA3Wtl9D2QdGcFkTIONF6ubUa34bgwamVrxrt3xVJ1Q8-9YtPmaAivmg_2yX38wbsn3kPi30DLg5vNg</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>2528179817</pqid></control><display><type>article</type><title>Selection on X 1  +  X 2  + ⋯ +  X m via Cartesian product trees</title><source>Publicly Available Content Database (Proquest) (PQ_SDU_P3)</source><source>PubMed Central</source><creator>Kreitzberg, Patrick ; Lucke, Kyle ; Pennington, Jake ; Serang, Oliver</creator><creatorcontrib>Kreitzberg, Patrick ; Lucke, Kyle ; Pennington, Jake ; Serang, Oliver</creatorcontrib><description>Selection on the Cartesian product is a classic problem in computer science. Recently, an optimal algorithm for selection on  +  , based on soft heaps, was introduced. By combining this approach with layer-ordered heaps (LOHs), an algorithm using a balanced binary tree of  +  selections was proposed to perform selection on  +   + ⋯ +  in ( ⋅  +  ⋅ ), where have length . Here, that ( ⋅  +  ⋅ ) algorithm is combined with a novel, optimal LOH-based algorithm for selection on  +  (without a soft heap). Performance of algorithms for selection on  +   + ⋯ +  are compared empirically, demonstrating the benefit of the algorithm proposed here.</description><identifier>ISSN: 2376-5992</identifier><identifier>EISSN: 2376-5992</identifier><identifier>DOI: 10.7717/peerj-cs.483</identifier><identifier>PMID: 33987456</identifier><language>eng</language><publisher>United States</publisher><ispartof>PeerJ. Computer science, 2021, Vol.7, p.e483-e483, Article e483</ispartof><rights>2021 Kreitzberg et al.</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c1366-29b9f3d384d516aeeddaf4284beaf86031e92fa226aad6df7d79a1cdc2d47a223</citedby><cites>FETCH-LOGICAL-c1366-29b9f3d384d516aeeddaf4284beaf86031e92fa226aad6df7d79a1cdc2d47a223</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>314,780,784,4024,27923,27924,27925,37013</link.rule.ids><backlink>$$Uhttps://www.ncbi.nlm.nih.gov/pubmed/33987456$$D View this record in MEDLINE/PubMed$$Hfree_for_read</backlink></links><search><creatorcontrib>Kreitzberg, Patrick</creatorcontrib><creatorcontrib>Lucke, Kyle</creatorcontrib><creatorcontrib>Pennington, Jake</creatorcontrib><creatorcontrib>Serang, Oliver</creatorcontrib><title>Selection on X 1  +  X 2  + ⋯ +  X m via Cartesian product trees</title><title>PeerJ. Computer science</title><addtitle>PeerJ Comput Sci</addtitle><description>Selection on the Cartesian product is a classic problem in computer science. Recently, an optimal algorithm for selection on  +  , based on soft heaps, was introduced. By combining this approach with layer-ordered heaps (LOHs), an algorithm using a balanced binary tree of  +  selections was proposed to perform selection on  +   + ⋯ +  in ( ⋅  +  ⋅ ), where have length . Here, that ( ⋅  +  ⋅ ) algorithm is combined with a novel, optimal LOH-based algorithm for selection on  +  (without a soft heap). Performance of algorithms for selection on  +   + ⋯ +  are compared empirically, demonstrating the benefit of the algorithm proposed here.</description><issn>2376-5992</issn><issn>2376-5992</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2021</creationdate><recordtype>article</recordtype><recordid>eNpNkMFKAzEQhoMottTePEuOgm7dJLvJ5iiLWqHgQQVvIU0msGW3W5NdwWfwJfoGvkMfxScx2lYcZpif4ecf-BA6JelECCKuVgB-kZgwyQp2gIaUCZ7kUtLDf3qAxiEs0jQlOYklj9GAMVmILOdDNH2EGkxXtUsc-wUTvFlfbNZR0a36-vjcXxr8Vmlcat9BqPQSr3xre9PhzgOEE3TkdB1gvNsj9Hx781ROk9nD3X15PUsMYZwnVM6lY5YVmc0J1wDWapfRIpuDdgVPGQFJnaaUa225dcIKqYmxhtpMxDMbofNtbvz-2kPoVFMFA3Wtl9D2QdGcFkTIONF6ubUa34bgwamVrxrt3xVJ1Q8-9YtPmaAivmg_2yX38wbsn3kPi30DLg5vNg</recordid><startdate>2021</startdate><enddate>2021</enddate><creator>Kreitzberg, Patrick</creator><creator>Lucke, Kyle</creator><creator>Pennington, Jake</creator><creator>Serang, Oliver</creator><scope>NPM</scope><scope>AAYXX</scope><scope>CITATION</scope><scope>7X8</scope></search><sort><creationdate>2021</creationdate><title>Selection on X 1  +  X 2  + ⋯ +  X m via Cartesian product trees</title><author>Kreitzberg, Patrick ; Lucke, Kyle ; Pennington, Jake ; Serang, Oliver</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c1366-29b9f3d384d516aeeddaf4284beaf86031e92fa226aad6df7d79a1cdc2d47a223</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2021</creationdate><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Kreitzberg, Patrick</creatorcontrib><creatorcontrib>Lucke, Kyle</creatorcontrib><creatorcontrib>Pennington, Jake</creatorcontrib><creatorcontrib>Serang, Oliver</creatorcontrib><collection>PubMed</collection><collection>CrossRef</collection><collection>MEDLINE - Academic</collection><jtitle>PeerJ. Computer science</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Kreitzberg, Patrick</au><au>Lucke, Kyle</au><au>Pennington, Jake</au><au>Serang, Oliver</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Selection on X 1  +  X 2  + ⋯ +  X m via Cartesian product trees</atitle><jtitle>PeerJ. Computer science</jtitle><addtitle>PeerJ Comput Sci</addtitle><date>2021</date><risdate>2021</risdate><volume>7</volume><spage>e483</spage><epage>e483</epage><pages>e483-e483</pages><artnum>e483</artnum><issn>2376-5992</issn><eissn>2376-5992</eissn><abstract>Selection on the Cartesian product is a classic problem in computer science. Recently, an optimal algorithm for selection on  +  , based on soft heaps, was introduced. By combining this approach with layer-ordered heaps (LOHs), an algorithm using a balanced binary tree of  +  selections was proposed to perform selection on  +   + ⋯ +  in ( ⋅  +  ⋅ ), where have length . Here, that ( ⋅  +  ⋅ ) algorithm is combined with a novel, optimal LOH-based algorithm for selection on  +  (without a soft heap). Performance of algorithms for selection on  +   + ⋯ +  are compared empirically, demonstrating the benefit of the algorithm proposed here.</abstract><cop>United States</cop><pmid>33987456</pmid><doi>10.7717/peerj-cs.483</doi></addata></record>
fulltext fulltext
identifier ISSN: 2376-5992
ispartof PeerJ. Computer science, 2021, Vol.7, p.e483-e483, Article e483
issn 2376-5992
2376-5992
language eng
recordid cdi_proquest_miscellaneous_2528179817
source Publicly Available Content Database (Proquest) (PQ_SDU_P3); PubMed Central
title Selection on X 1  +  X 2  + ⋯ +  X m via Cartesian product trees
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-04T18%3A39%3A38IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Selection%20on%20X%201%20%C2%A0+%C2%A0%20X%202%20%C2%A0+%C2%A0%E2%8B%AF%C2%A0+%C2%A0%20X%20m%20via%20Cartesian%20product%20trees&rft.jtitle=PeerJ.%20Computer%20science&rft.au=Kreitzberg,%20Patrick&rft.date=2021&rft.volume=7&rft.spage=e483&rft.epage=e483&rft.pages=e483-e483&rft.artnum=e483&rft.issn=2376-5992&rft.eissn=2376-5992&rft_id=info:doi/10.7717/peerj-cs.483&rft_dat=%3Cproquest_cross%3E2528179817%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c1366-29b9f3d384d516aeeddaf4284beaf86031e92fa226aad6df7d79a1cdc2d47a223%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=2528179817&rft_id=info:pmid/33987456&rfr_iscdi=true