Efficient optimal pagination of scrolls

Name: Work Video:
Duration: 3 min 30 s
Description: Diehr and Faaland developed an algorithm that finds the minimum sum of key length pagination of a scroll of n items, and which uses O(n log n) time, solving a problem posed by McCreight. An improved algorithm is given which uses O(n) time.
Lawrence L. Larmore; D. S. Hirschberg
{'id': 'https://openalex.org/W2017644881', 'doi': 'https://doi.org/10.1145/4021.4026', 'title': 'Efficient optimal pagination of scrolls', 'display_name': 'Efficient optimal pagination of scrolls', 'publication_year': 1985, 'publication_date': '1985-08-01', 'ids': {'openalex': 'https://openalex.org/W2017644881', 'doi': 'https://doi.org/10.1145/4021.4026', 'mag': '2017644881'}, 'language': 'en', 'primary_location': {'is_oa': True, 'landing_page_url': 'https://doi.org/10.1145/4021.4026', 'pdf_url': 'https://dl.acm.org/doi/pdf/10.1145/4021.4026', 'source': {'id': 'https://openalex.org/S103482838', 'display_name': 'Communications of the ACM', 'issn_l': '0001-0782', 'issn': ['0001-0782', '1557-7317'], 'is_oa': False, 'is_in_doaj': False, 'is_core': True, 'host_organization': 'https://openalex.org/P4310319798', 'host_organization_name': 'Association for Computing Machinery', 'host_organization_lineage': ['https://openalex.org/P4310319798'], 'host_organization_lineage_names': ['Association for Computing Machinery'], 'type': 'journal'}, 'license': None, 'license_id': None, 'version': 'publishedVersion', 'is_accepted': True, 'is_published': True}, 'type': 'article', 'type_crossref': 'journal-article', 'indexed_in': ['crossref'], 'open_access': {'is_oa': True, 'oa_status': 'bronze', 'oa_url': 'https://dl.acm.org/doi/pdf/10.1145/4021.4026', 'any_repository_has_fulltext': True}, 'authorships': [{'author_position': 'first', 'author': {'id': 'https://openalex.org/A5038877069', 'display_name': 'Lawrence L. Larmore', 'orcid': None}, 'institutions': [{'id': 'https://openalex.org/I290598920', 'display_name': 'California State University, Dominguez Hills', 'ror': 'https://ror.org/04pyvbw03', 'country_code': 'US', 'type': 'education', 'lineage': ['https://openalex.org/I290598920']}], 'countries': ['US'], 'is_corresponding': False, 'raw_author_name': 'L. L. Larmore', 'raw_affiliation_strings': ['California State University, Dominguez Hills#TAB#'], 'affiliations': [{'raw_affiliation_string': 'California State University, Dominguez Hills#TAB#', 'institution_ids': ['https://openalex.org/I290598920']}]}, {'author_position': 'last', 'author': {'id': 'https://openalex.org/A5113554965', 'display_name': 'D. S. Hirschberg', 'orcid': None}, 'institutions': [{'id': 'https://openalex.org/I204250578', 'display_name': 'University of California, Irvine', 'ror': 'https://ror.org/04gyf1771', 'country_code': 'US', 'type': 'education', 'lineage': ['https://openalex.org/I204250578']}], 'countries': ['US'], 'is_corresponding': False, 'raw_author_name': 'D. S. Hirschberg', 'raw_affiliation_strings': ['[University of California, Irvine]'], 'affiliations': [{'raw_affiliation_string': '[University of California, Irvine]', 'institution_ids': ['https://openalex.org/I204250578']}]}], 'institution_assertions': [], 'countries_distinct_count': 1, 'institutions_distinct_count': 2, 'corresponding_author_ids': [], 'corresponding_institution_ids': [], 'apc_list': None, 'apc_paid': None, 'fwci': 6.677, 'has_fulltext': True, 'fulltext_origin': 'pdf', 'cited_by_count': 15, 'citation_normalized_percentile': {'value': 0.885981, 'is_in_top_1_percent': False, 'is_in_top_10_percent': False}, 'cited_by_percentile_year': {'min': 83, 'max': 84}, 'biblio': {'volume': '28', 'issue': '8', 'first_page': '854', 'last_page': '856'}, 'is_retracted': False, 'is_paratext': False, 'primary_topic': {'id': 'https://openalex.org/T12176', 'display_name': 'Optimization and Packing Problems', 'score': 0.9321, 'subfield': {'id': 'https://openalex.org/subfields/2209', 'display_name': 'Industrial and Manufacturing Engineering'}, 'field': {'id': 'https://openalex.org/fields/22', 'display_name': 'Engineering'}, 'domain': {'id': 'https://openalex.org/domains/3', 'display_name': 'Physical Sciences'}}, 'topics': [{'id': 'https://openalex.org/T12176', 'display_name': 'Optimization and Packing Problems', 'score': 0.9321, 'subfield': {'id': 'https://openalex.org/subfields/2209', 'display_name': 'Industrial and Manufacturing Engineering'}, 'field': {'id': 'https://openalex.org/fields/22', 'display_name': 'Engineering'}, 'domain': {'id': 'https://openalex.org/domains/3', 'display_name': 'Physical Sciences'}}, {'id': 'https://openalex.org/T11797', 'display_name': 'graph theory and CDMA systems', 'score': 0.9217, 'subfield': {'id': 'https://openalex.org/subfields/2208', 'display_name': 'Electrical and Electronic Engineering'}, 'field': {'id': 'https://openalex.org/fields/22', 'display_name': 'Engineering'}, 'domain': {'id': 'https://openalex.org/domains/3', 'display_name': 'Physical Sciences'}}, {'id': 'https://openalex.org/T10374', 'display_name': 'Advanced Graph Theory Research', 'score': 0.9009, 'subfield': {'id': 'https://openalex.org/subfields/1703', 'display_name': 'Computational Theory and Mathematics'}, 'field': {'id': 'https://openalex.org/fields/17', 'display_name': 'Computer Science'}, 'domain': {'id': 'https://openalex.org/domains/3', 'display_name': 'Physical Sciences'}}], 'keywords': [{'id': 'https://openalex.org/keywords/pagination', 'display_name': 'Pagination', 'score': 0.9836823}], 'concepts': [{'id': 'https://openalex.org/C2780644320', 'wikidata': 'https://www.wikidata.org/wiki/Q783209', 'display_name': 'Pagination', 'level': 2, 'score': 0.9836823}, {'id': 'https://openalex.org/C2781324535', 'wikidata': 'https://www.wikidata.org/wiki/Q720106', 'display_name': 'Scroll', 'level': 2, 'score': 0.7254883}, {'id': 'https://openalex.org/C26517878', 'wikidata': 'https://www.wikidata.org/wiki/Q228039', 'display_name': 'Key (lock)', 'level': 2, 'score': 0.51489246}, {'id': 'https://openalex.org/C41008148', 'wikidata': 'https://www.wikidata.org/wiki/Q21198', 'display_name': 'Computer science', 'level': 0, 'score': 0.46507785}, {'id': 'https://openalex.org/C33923547', 'wikidata': 'https://www.wikidata.org/wiki/Q395', 'display_name': 'Mathematics', 'level': 0, 'score': 0.42889154}, {'id': 'https://openalex.org/C11413529', 'wikidata': 'https://www.wikidata.org/wiki/Q8366', 'display_name': 'Algorithm', 'level': 1, 'score': 0.3796499}, {'id': 'https://openalex.org/C127413603', 'wikidata': 'https://www.wikidata.org/wiki/Q11023', 'display_name': 'Engineering', 'level': 0, 'score': 0.065969646}, {'id': 'https://openalex.org/C136764020', 'wikidata': 'https://www.wikidata.org/wiki/Q466', 'display_name': 'World Wide Web', 'level': 1, 'score': 0.05372733}, {'id': 'https://openalex.org/C111919701', 'wikidata': 'https://www.wikidata.org/wiki/Q9135', 'display_name': 'Operating system', 'level': 1, 'score': 0.049131334}, {'id': 'https://openalex.org/C78519656', 'wikidata': 'https://www.wikidata.org/wiki/Q101333', 'display_name': 'Mechanical engineering', 'level': 1, 'score': 0.0}], 'mesh': [], 'locations_count': 2, 'locations': [{'is_oa': True, 'landing_page_url': 'https://doi.org/10.1145/4021.4026', 'pdf_url': 'https://dl.acm.org/doi/pdf/10.1145/4021.4026', 'source': {'id': 'https://openalex.org/S103482838', 'display_name': 'Communications of the ACM', 'issn_l': '0001-0782', 'issn': ['0001-0782', '1557-7317'], 'is_oa': False, 'is_in_doaj': False, 'is_core': True, 'host_organization': 'https://openalex.org/P4310319798', 'host_organization_name': 'Association for Computing Machinery', 'host_organization_lineage': ['https://openalex.org/P4310319798'], 'host_organization_lineage_names': ['Association for Computing Machinery'], 'type': 'journal'}, 'license': None, 'license_id': None, 'version': 'publishedVersion', 'is_accepted': True, 'is_published': True}, {'is_oa': True, 'landing_page_url': 'https://escholarship.org/uc/item/1hh4x49n', 'pdf_url': 'https://escholarship.org/content/qt1hh4x49n/qt1hh4x49n.pdf?t=q67dim', 'source': {'id': 'https://openalex.org/S4306400115', 'display_name': 'eScholarship (California Digital Library)', 'issn_l': None, 'issn': None, 'is_oa': True, 'is_in_doaj': False, 'is_core': False, 'host_organization': 'https://openalex.org/I2801248553', 'host_organization_name': 'California Digital Library', 'host_organization_lineage': ['https://openalex.org/I2801248553'], 'host_organization_lineage_names': ['California Digital Library'], 'type': 'repository'}, 'license': 'other-oa', 'license_id': 'https://openalex.org/licenses/other-oa', 'version': 'submittedVersion', 'is_accepted': False, 'is_published': False}], 'best_oa_location': {'is_oa': True, 'landing_page_url': 'https://doi.org/10.1145/4021.4026', 'pdf_url': 'https://dl.acm.org/doi/pdf/10.1145/4021.4026', 'source': {'id': 'https://openalex.org/S103482838', 'display_name': 'Communications of the ACM', 'issn_l': '0001-0782', 'issn': ['0001-0782', '1557-7317'], 'is_oa': False, 'is_in_doaj': False, 'is_core': True, 'host_organization': 'https://openalex.org/P4310319798', 'host_organization_name': 'Association for Computing Machinery', 'host_organization_lineage': ['https://openalex.org/P4310319798'], 'host_organization_lineage_names': ['Association for Computing Machinery'], 'type': 'journal'}, 'license': None, 'license_id': None, 'version': 'publishedVersion', 'is_accepted': True, 'is_published': True}, 'sustainable_development_goals': [], 'grants': [], 'datasets': [], 'versions': [], 'referenced_works_count': 2, 'referenced_works': ['https://openalex.org/W2012867943', 'https://openalex.org/W2094127279'], 'related_works': ['https://openalex.org/W4242316919', 'https://openalex.org/W2808985821', 'https://openalex.org/W2389268081', 'https://openalex.org/W2384079231', 'https://openalex.org/W2359131712', 'https://openalex.org/W2351457136', 'https://openalex.org/W2130001076', 'https://openalex.org/W2078213345', 'https://openalex.org/W2022161681', 'https://openalex.org/W1979254831'], 'abstract_inverted_index': {'Diehr': [0], 'and': [1, 21], 'Faaland': [2], 'developed': [3], 'an': [4], 'algorithm': [5, 36], 'that': [6], 'finds': [7], 'the': [8], 'minimum': [9], 'sum': [10], 'of': [11, 15, 18], 'key': [12], 'length': [13], 'pagination': [14], 'a': [16, 29], 'scroll': [17], 'n': [19], 'items,': [20], 'which': [22, 39], 'uses': [23, 40], 'O(n': [24], 'log': [25], 'n)': [26], 'time,': [27], 'solving': [28], 'problem': [30], 'posed': [31], 'by': [32], 'McCreight.': [33], 'An': [34], 'improved': [35], 'is': [37], 'given': [38], 'O(n)': [41], 'time.': [42]}, 'cited_by_api_url': 'https://api.openalex.org/works?filter=cites:W2017644881', 'counts_by_year': [{'year': 2020, 'cited_by_count': 2}, {'year': 2016, 'cited_by_count': 1}], 'updated_date': '2024-12-08T19:04:32.577725', 'created_date': '2016-06-24'}
Publication Information

Basic Information

Access and Citation

AI Researcher Chatbot

Primary Location

Authors

Topics

Keywords

Related Works
