Publication Information

{'id': 'https://openalex.org/W2157823105', 'doi': 'https://doi.org/10.1109/ipps.1995.395932', 'title': 'B-trees with relaxed balance', 'display_name': 'B-trees with relaxed balance', 'publication_year': 2002, 'publication_date': '2002-11-19', 'ids': {'openalex': 'https://openalex.org/W2157823105', 'doi': 'https://doi.org/10.1109/ipps.1995.395932', 'mag': '2157823105'}, 'language': 'en', 'primary_location': {'is_oa': False, 'landing_page_url': 'https://doi.org/10.1109/ipps.1995.395932', 'pdf_url': None, 'source': None, 'license': None, 'license_id': None, 'version': None, 'is_accepted': False, 'is_published': False}, 'type': 'article', 'type_crossref': 'proceedings-article', 'indexed_in': ['crossref'], 'open_access': {'is_oa': False, 'oa_status': 'closed', 'oa_url': None, 'any_repository_has_fulltext': False}, 'authorships': [{'author_position': 'first', 'author': {'id': 'https://openalex.org/A5000210653', 'display_name': 'Kim S. Larsen', 'orcid': 'https://orcid.org/0000-0003-0560-3794'}, 'institutions': [], 'countries': ['DK'], 'is_corresponding': False, 'raw_author_name': 'K.S. Larsen', 'raw_affiliation_strings': ['Department of Mat hematics and Computer Science, Odense University, Odense, Denmark'], 'affiliations': [{'raw_affiliation_string': 'Department of Mat hematics and Computer Science, Odense University, Odense, Denmark', 'institution_ids': []}]}, {'author_position': 'last', 'author': {'id': 'https://openalex.org/A5021765002', 'display_name': 'Rolf Fagerberg', 'orcid': 'https://orcid.org/0000-0003-1004-3314'}, 'institutions': [], 'countries': ['DK'], 'is_corresponding': False, 'raw_author_name': 'R. Fagerberg', 'raw_affiliation_strings': ['Department of Mat hematics and Computer Science, Odense University, Odense, Denmark'], 'affiliations': [{'raw_affiliation_string': 'Department of Mat hematics and Computer Science, Odense University, Odense, Denmark', 'institution_ids': []}]}], 'institution_assertions': [], 'countries_distinct_count': 1, 'institutions_distinct_count': 0, 'corresponding_author_ids': [], 'corresponding_institution_ids': [], 'apc_list': None, 'apc_paid': None, 'fwci': 0.373, 'has_fulltext': True, 'fulltext_origin': 'ngrams', 'cited_by_count': 16, 'citation_normalized_percentile': {'value': 0.665945, 'is_in_top_1_percent': False, 'is_in_top_10_percent': False}, 'cited_by_percentile_year': {'min': 83, 'max': 84}, 'biblio': {'volume': None, 'issue': None, 'first_page': '196', 'last_page': '202'}, 'is_retracted': False, 'is_paratext': False, 'primary_topic': {'id': 'https://openalex.org/T10772', 'display_name': 'Distributed systems and fault tolerance', 'score': 0.9999, 'subfield': {'id': 'https://openalex.org/subfields/1705', 'display_name': 'Computer Networks and Communications'}, 'field': {'id': 'https://openalex.org/fields/17', 'display_name': 'Computer Science'}, 'domain': {'id': 'https://openalex.org/domains/3', 'display_name': 'Physical Sciences'}}, 'topics': [{'id': 'https://openalex.org/T10772', 'display_name': 'Distributed systems and fault tolerance', 'score': 0.9999, 'subfield': {'id': 'https://openalex.org/subfields/1705', 'display_name': 'Computer Networks and Communications'}, 'field': {'id': 'https://openalex.org/fields/17', 'display_name': 'Computer Science'}, 'domain': {'id': 'https://openalex.org/domains/3', 'display_name': 'Physical Sciences'}}, {'id': 'https://openalex.org/T10829', 'display_name': 'Interconnection Networks and Systems', 'score': 0.9959, 'subfield': {'id': 'https://openalex.org/subfields/1705', 'display_name': 'Computer Networks and Communications'}, 'field': {'id': 'https://openalex.org/fields/17', 'display_name': 'Computer Science'}, 'domain': {'id': 'https://openalex.org/domains/3', 'display_name': 'Physical Sciences'}}, {'id': 'https://openalex.org/T10054', 'display_name': 'Parallel Computing and Optimization Techniques', 'score': 0.9947, 'subfield': {'id': 'https://openalex.org/subfields/1708', 'display_name': 'Hardware and Architecture'}, '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/constant', 'display_name': 'Constant (computer programming)', 'score': 0.6591376}, {'id': 'https://openalex.org/keywords/amortized-analysis', 'display_name': 'Amortized analysis', 'score': 0.62722075}, {'id': 'https://openalex.org/keywords/tree', 'display_name': 'Tree (set theory)', 'score': 0.6137067}, {'id': 'https://openalex.org/keywords/degree', 'display_name': 'Degree (music)', 'score': 0.5845241}, {'id': 'https://openalex.org/keywords/b-tree', 'display_name': 'B-tree', 'score': 0.5076543}, {'id': 'https://openalex.org/keywords/lock', 'display_name': 'Lock (firearm)', 'score': 0.50282615}, {'id': 'https://openalex.org/keywords/root', 'display_name': 'Root (linguistics)', 'score': 0.49663}], 'concepts': [{'id': 'https://openalex.org/C2777027219', 'wikidata': 'https://www.wikidata.org/wiki/Q1284190', 'display_name': 'Constant (computer programming)', 'level': 2, 'score': 0.6591376}, {'id': 'https://openalex.org/C142417499', 'wikidata': 'https://www.wikidata.org/wiki/Q331716', 'display_name': 'Amortized analysis', 'level': 3, 'score': 0.62722075}, {'id': 'https://openalex.org/C113174947', 'wikidata': 'https://www.wikidata.org/wiki/Q2859736', 'display_name': 'Tree (set theory)', 'level': 2, 'score': 0.6137067}, {'id': 'https://openalex.org/C2775997480', 'wikidata': 'https://www.wikidata.org/wiki/Q586277', 'display_name': 'Degree (music)', 'level': 2, 'score': 0.5845241}, {'id': 'https://openalex.org/C41008148', 'wikidata': 'https://www.wikidata.org/wiki/Q21198', 'display_name': 'Computer science', 'level': 0, 'score': 0.5658871}, {'id': 'https://openalex.org/C151319957', 'wikidata': 'https://www.wikidata.org/wiki/Q752739', 'display_name': 'Asynchronous communication', 'level': 2, 'score': 0.5522258}, {'id': 'https://openalex.org/C39927690', 'wikidata': 'https://www.wikidata.org/wiki/Q11197', 'display_name': 'Logarithm', 'level': 2, 'score': 0.54973245}, {'id': 'https://openalex.org/C114614502', 'wikidata': 'https://www.wikidata.org/wiki/Q76592', 'display_name': 'Combinatorics', 'level': 1, 'score': 0.53299654}, {'id': 'https://openalex.org/C78669399', 'wikidata': 'https://www.wikidata.org/wiki/Q677051', 'display_name': 'B-tree', 'level': 3, 'score': 0.5076543}, {'id': 'https://openalex.org/C174839445', 'wikidata': 'https://www.wikidata.org/wiki/Q1134386', 'display_name': 'Lock (firearm)', 'level': 2, 'score': 0.50282615}, {'id': 'https://openalex.org/C171078966', 'wikidata': 'https://www.wikidata.org/wiki/Q111029', 'display_name': 'Root (linguistics)', 'level': 2, 'score': 0.49663}, {'id': 'https://openalex.org/C63553672', 'wikidata': 'https://www.wikidata.org/wiki/Q581168', 'display_name': 'Binary logarithm', 'level': 2, 'score': 0.46493432}, {'id': 'https://openalex.org/C33923547', 'wikidata': 'https://www.wikidata.org/wiki/Q395', 'display_name': 'Mathematics', 'level': 0, 'score': 0.4296986}, {'id': 'https://openalex.org/C13355873', 'wikidata': 'https://www.wikidata.org/wiki/Q2920850', 'display_name': 'Connection (principal bundle)', 'level': 2, 'score': 0.42747164}, {'id': 'https://openalex.org/C168031717', 'wikidata': 'https://www.wikidata.org/wiki/Q1530280', 'display_name': 'Balance (ability)', 'level': 2, 'score': 0.42709756}, {'id': 'https://openalex.org/C118615104', 'wikidata': 'https://www.wikidata.org/wiki/Q121416', 'display_name': 'Discrete mathematics', 'level': 1, 'score': 0.39115357}, {'id': 'https://openalex.org/C162319229', 'wikidata': 'https://www.wikidata.org/wiki/Q175263', 'display_name': 'Data structure', 'level': 2, 'score': 0.34325123}, {'id': 'https://openalex.org/C197855036', 'wikidata': 'https://www.wikidata.org/wiki/Q380172', 'display_name': 'Binary tree', 'level': 2, 'score': 0.10269579}, {'id': 'https://openalex.org/C111919701', 'wikidata': 'https://www.wikidata.org/wiki/Q9135', 'display_name': 'Operating system', 'level': 1, 'score': 0.07446018}, {'id': 'https://openalex.org/C78519656', 'wikidata': 'https://www.wikidata.org/wiki/Q101333', 'display_name': 'Mechanical engineering', 'level': 1, 'score': 0.0}, {'id': 'https://openalex.org/C31258907', 'wikidata': 'https://www.wikidata.org/wiki/Q1301371', 'display_name': 'Computer network', 'level': 1, 'score': 0.0}, {'id': 'https://openalex.org/C134306372', 'wikidata': 'https://www.wikidata.org/wiki/Q7754', 'display_name': 'Mathematical analysis', 'level': 1, 'score': 0.0}, {'id': 'https://openalex.org/C41895202', 'wikidata': 'https://www.wikidata.org/wiki/Q8162', 'display_name': 'Linguistics', 'level': 1, 'score': 0.0}, {'id': 'https://openalex.org/C138885662', 'wikidata': 'https://www.wikidata.org/wiki/Q5891', 'display_name': 'Philosophy', 'level': 0, 'score': 0.0}, {'id': 'https://openalex.org/C121332964', 'wikidata': 'https://www.wikidata.org/wiki/Q413', 'display_name': 'Physics', 'level': 0, 'score': 0.0}, {'id': 'https://openalex.org/C2524010', 'wikidata': 'https://www.wikidata.org/wiki/Q8087', 'display_name': 'Geometry', 'level': 1, 'score': 0.0}, {'id': 'https://openalex.org/C71924100', 'wikidata': 'https://www.wikidata.org/wiki/Q11190', 'display_name': 'Medicine', 'level': 0, 'score': 0.0}, {'id': 'https://openalex.org/C24890656', 'wikidata': 'https://www.wikidata.org/wiki/Q82811', 'display_name': 'Acoustics', 'level': 1, 'score': 0.0}, {'id': 'https://openalex.org/C127413603', 'wikidata': 'https://www.wikidata.org/wiki/Q11023', 'display_name': 'Engineering', 'level': 0, 'score': 0.0}, {'id': 'https://openalex.org/C99508421', 'wikidata': 'https://www.wikidata.org/wiki/Q2678675', 'display_name': 'Physical medicine and rehabilitation', 'level': 1, 'score': 0.0}, {'id': 'https://openalex.org/C199360897', 'wikidata': 'https://www.wikidata.org/wiki/Q9143', 'display_name': 'Programming language', 'level': 1, 'score': 0.0}], 'mesh': [], 'locations_count': 1, 'locations': [{'is_oa': False, 'landing_page_url': 'https://doi.org/10.1109/ipps.1995.395932', 'pdf_url': None, 'source': None, 'license': None, 'license_id': None, 'version': None, 'is_accepted': False, 'is_published': False}], 'best_oa_location': None, 'sustainable_development_goals': [], 'grants': [], 'datasets': [], 'versions': [], 'referenced_works_count': 16, 'referenced_works': ['https://openalex.org/W172574161', 'https://openalex.org/W1973610879', 'https://openalex.org/W1974269564', 'https://openalex.org/W1984825199', 'https://openalex.org/W1986975171', 'https://openalex.org/W2021615496', 'https://openalex.org/W2028764399', 'https://openalex.org/W2033584818', 'https://openalex.org/W2039071499', 'https://openalex.org/W2057391254', 'https://openalex.org/W2077180154', 'https://openalex.org/W2108179552', 'https://openalex.org/W2145052180', 'https://openalex.org/W2901608006', 'https://openalex.org/W4249958171', 'https://openalex.org/W6502334'], 'related_works': ['https://openalex.org/W8290509', 'https://openalex.org/W4297665144', 'https://openalex.org/W4205704978', 'https://openalex.org/W3092127654', 'https://openalex.org/W2737298126', 'https://openalex.org/W2184537587', 'https://openalex.org/W2076407808', 'https://openalex.org/W2065411828', 'https://openalex.org/W2006811735', 'https://openalex.org/W1482484961'], 'abstract_inverted_index': {'B-trees': [0, 39], 'with': [1, 35, 40], 'relaxed': [2, 41], 'balance': [3], 'have': [4, 199], 'been': [5, 21], 'defined': [6], 'to': [7, 50, 122, 161], 'facilitate': [8], 'first': [9], 'updating': [10, 25], 'on': [11, 112], 'shared-memory': [12], 'asynchronous': [13], 'parallel': [14], 'architectures.': [15], 'To': [16], 'obtain': [17], 'this,': [18], 'rebalancing': [19, 55, 95, 108, 133, 163], 'has': [20], 'uncoupled': [22], 'from': [23, 142], 'the': [24, 60, 63, 68, 82, 90, 105, 130, 143, 146, 152, 156, 166, 178, 192, 204], 'such': [26], 'that': [27, 45, 81, 94, 129, 181], 'extensive': [28], 'locking': [29], 'can': [30, 96], 'be': [31, 97, 172], 'avoided': [32], 'in': [33, 78, 99, 104, 155, 188], 'connection': [34], 'updates.': [36], 'We': [37, 126], 'analyze': [38], 'balance,': [42], 'and': [43, 65, 213], 'prove': [44, 93, 128], 'each': [46], 'update': [47, 118], 'gives': [48], 'rise': [49, 121], 'at': [51, 87, 135], 'most': [52], '[log/sub': [53], 'a/(N/2)]+1': [54], 'operations,': [56], 'where': [57], 'a': [58, 158, 162, 168], 'is': [59, 67, 109, 149], 'degree': [61], 'of': [62, 84, 132, 180, 184, 203], 'B-tree,': [64], 'N': [66], 'bound': [69], 'an': [70], 'its': [71], 'maximal': [72], 'size': [73, 83], 'since': [74, 151], 'it': [75], 'was': [76], 'last': [77], 'balance.': [79], 'Assuming': [80], 'nodes': [85], 'are': [86, 187], 'least': [88], 'twice': [89], 'degree,': [91], 'we': [92, 198], 'performed': [98], 'amortized': [100], 'constant': [101, 110], 'time.': [102], 'So,': [103], 'long': [106], 'run,': [107], 'time': [111, 124], 'average,': [113], 'even': [114], 'if': [115], 'any': [116, 136], 'particular': [117, 137], 'could': [119], 'give': [120], 'logarithmic': [123], 'rebalancing.': [125], 'also': [127], 'amount': [131], 'done': [134], 'level': [138], 'decreases': [139], 'exponentially': [140], 'going': [141], 'leaves': [144], 'towards': [145], 'root.': [147], 'This': [148], 'important': [150], 'higher': [153], 'up': [154], 'tree': [157], 'lock': [159], 'due': [160], 'operation': [164], 'occurs,': [165], 'larger': [167], 'subtree': [169], 'which': [170], 'cannot': [171], 'accessed': [173], 'by': [174], 'other': [175], 'processes': [176], 'for': [177, 191, 201], 'duration': [179], 'lock.': [182], 'All': [183], 'these': [185], 'results': [186, 200], 'fact': [189], 'obtained': [190], 'more': [193], 'general': [194], '(a,': [195], 'b)-trees,': [196], 'so': [197], 'both': [202], 'common': [205], 'B-tree': [206], 'versions': [207], 'as': [208, 210], 'well': [209], '2-3': [211], 'trees': [212], '2-3-4': [214], 'trees.<': [215], '<ETX': [216], 'xmlns:mml="http://www.w3.org/1998/Math/MathML"': [217], 'xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>': [218]}, 'cited_by_api_url': 'https://api.openalex.org/works?filter=cites:W2157823105', 'counts_by_year': [{'year': 2021, 'cited_by_count': 1}, {'year': 2017, 'cited_by_count': 2}], 'updated_date': '2024-12-09T03:21:31.471128', 'created_date': '2016-06-24'}