The Ring: Worst-case Optimal Joins in Graph Databases using (Almost) No Extra Space Article Swipe
Diego Arroyuelo
,
Adrián Gómez‐Brandón
,
Aidan Hogan
,
Gonzalo Navarro
,
Juan L. Reutter
,
Javiel Rojas-Ledesma
,
Adrián Soto
·
YOU?
·
· 2024
· Open Access
·
· DOI: https://doi.org/10.1145/3644824
YOU?
·
· 2024
· Open Access
·
· DOI: https://doi.org/10.1145/3644824
We present an indexing scheme for triple-based graphs that supports join queries in worst-case optimal (wco) time within compact space. This scheme, called a ring , regards each triple as a cyclic string of length 3. Each rotation of the triples is lexicographically sorted and the values of the last attribute are stored as a column, so we obtain the order of the next column by stably re-sorting the triples by its attribute. We show that, by representing the columns with a compact data structure called a wavelet tree, this ordering enables forward and backward navigation between columns without needing pointers. These wavelet trees further support wco join algorithms and cardinality estimations for query planning. While traditional data structures such as B-Trees, tries, and so on, require 6 index orders to support all possible wco joins over triples, we can use one ring to index them all. This ring replaces the graph and uses only sublinear extra space, thus supporting wco joins in almost no space beyond storing the graph itself. Experiments querying a large graph (Wikidata) in memory show that the ring offers nearly the best overall query times while using only a small fraction of the space required by several state-of-the-art approaches. We then turn our attention to some theoretical results for indexing tables of arity d higher than 3 in such a way that supports wco joins. While a single ring of length d no longer suffices to cover all d ! orders, we need much fewer rings to index them all: O (2 d ) rings with a small constant. For example, we need 5 rings instead of 120 orders for d =5. We show that our rings become a particular case of what we dub order graphs , whose nodes are attribute orders and where stably sorting by some attribute leads us from an order to another, thereby inducing an edge labeled by the attribute. The index is then the set of columns associated with the edges, and a set of rings is just one possible graph shape. We show that other shapes, like for example a single ring instead of several ones of length d , can lead us to even smaller indexes, and that other more general shapes are also possible. For example, we handle d =5 attributes within space equivalent to 4 rings.
Related Topics
Concepts
Metadata
- Type
- article
- Language
- en
- Landing Page
- https://doi.org/10.1145/3644824
- OA Status
- green
- Cited By
- 6
- References
- 58
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W4391653333
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W4391653333Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.1145/3644824Digital Object Identifier
- Title
-
The Ring: Worst-case Optimal Joins in Graph Databases using (Almost) No Extra SpaceWork title
- Type
-
articleOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2024Year of publication
- Publication date
-
2024-02-08Full publication date if available
- Authors
-
Diego Arroyuelo, Adrián Gómez‐Brandón, Aidan Hogan, Gonzalo Navarro, Juan L. Reutter, Javiel Rojas-Ledesma, Adrián SotoList of authors in order
- Landing page
-
https://doi.org/10.1145/3644824Publisher landing page
- Open access
-
YesWhether a free full text is available
- OA status
-
greenOpen access status per OpenAlex
- OA URL
-
https://hdl.handle.net/2183/37862Direct OA link when available
- Concepts
-
Computer science, Joins, Lexicographical order, Search engine indexing, Graph, Cardinality (data modeling), Database, Graph database, Algorithm, Theoretical computer science, Combinatorics, Mathematics, Information retrieval, Programming languageTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
6Total citation count in OpenAlex
- Citations by year (recent)
-
2025: 3, 2024: 3Per-year citation counts (last 5 years)
- References (count)
-
58Number of works referenced by this work
- Related works (count)
-
10Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W4391653333 |
|---|---|
| doi | https://doi.org/10.1145/3644824 |
| ids.doi | https://doi.org/10.1145/3644824 |
| ids.openalex | https://openalex.org/W4391653333 |
| fwci | 3.83267129 |
| type | article |
| title | The Ring: Worst-case Optimal Joins in Graph Databases using (Almost) No Extra Space |
| biblio.issue | 2 |
| biblio.volume | 49 |
| biblio.last_page | 45 |
| biblio.first_page | 1 |
| topics[0].id | https://openalex.org/T11269 |
| topics[0].field.id | https://openalex.org/fields/17 |
| topics[0].field.display_name | Computer Science |
| topics[0].score | 0.9998999834060669 |
| topics[0].domain.id | https://openalex.org/domains/3 |
| topics[0].domain.display_name | Physical Sciences |
| topics[0].subfield.id | https://openalex.org/subfields/1702 |
| topics[0].subfield.display_name | Artificial Intelligence |
| topics[0].display_name | Algorithms and Data Compression |
| topics[1].id | https://openalex.org/T11106 |
| topics[1].field.id | https://openalex.org/fields/17 |
| topics[1].field.display_name | Computer Science |
| topics[1].score | 0.9993000030517578 |
| topics[1].domain.id | https://openalex.org/domains/3 |
| topics[1].domain.display_name | Physical Sciences |
| topics[1].subfield.id | https://openalex.org/subfields/1711 |
| topics[1].subfield.display_name | Signal Processing |
| topics[1].display_name | Data Management and Algorithms |
| topics[2].id | https://openalex.org/T10317 |
| topics[2].field.id | https://openalex.org/fields/17 |
| topics[2].field.display_name | Computer Science |
| topics[2].score | 0.9980000257492065 |
| topics[2].domain.id | https://openalex.org/domains/3 |
| topics[2].domain.display_name | Physical Sciences |
| topics[2].subfield.id | https://openalex.org/subfields/1705 |
| topics[2].subfield.display_name | Computer Networks and Communications |
| topics[2].display_name | Advanced Database Systems and Queries |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C41008148 |
| concepts[0].level | 0 |
| concepts[0].score | 0.7633273601531982 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[0].display_name | Computer science |
| concepts[1].id | https://openalex.org/C2778692605 |
| concepts[1].level | 2 |
| concepts[1].score | 0.763214111328125 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q4041866 |
| concepts[1].display_name | Joins |
| concepts[2].id | https://openalex.org/C159254197 |
| concepts[2].level | 2 |
| concepts[2].score | 0.6954164505004883 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q1144915 |
| concepts[2].display_name | Lexicographical order |
| concepts[3].id | https://openalex.org/C75165309 |
| concepts[3].level | 2 |
| concepts[3].score | 0.690894603729248 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q2258979 |
| concepts[3].display_name | Search engine indexing |
| concepts[4].id | https://openalex.org/C132525143 |
| concepts[4].level | 2 |
| concepts[4].score | 0.4753551185131073 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q141488 |
| concepts[4].display_name | Graph |
| concepts[5].id | https://openalex.org/C87117476 |
| concepts[5].level | 2 |
| concepts[5].score | 0.4536074101924896 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q362383 |
| concepts[5].display_name | Cardinality (data modeling) |
| concepts[6].id | https://openalex.org/C77088390 |
| concepts[6].level | 1 |
| concepts[6].score | 0.4356966018676758 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q8513 |
| concepts[6].display_name | Database |
| concepts[7].id | https://openalex.org/C176225458 |
| concepts[7].level | 3 |
| concepts[7].score | 0.41198575496673584 |
| concepts[7].wikidata | https://www.wikidata.org/wiki/Q595971 |
| concepts[7].display_name | Graph database |
| concepts[8].id | https://openalex.org/C11413529 |
| concepts[8].level | 1 |
| concepts[8].score | 0.35331207513809204 |
| concepts[8].wikidata | https://www.wikidata.org/wiki/Q8366 |
| concepts[8].display_name | Algorithm |
| concepts[9].id | https://openalex.org/C80444323 |
| concepts[9].level | 1 |
| concepts[9].score | 0.340864360332489 |
| concepts[9].wikidata | https://www.wikidata.org/wiki/Q2878974 |
| concepts[9].display_name | Theoretical computer science |
| concepts[10].id | https://openalex.org/C114614502 |
| concepts[10].level | 1 |
| concepts[10].score | 0.20057007670402527 |
| concepts[10].wikidata | https://www.wikidata.org/wiki/Q76592 |
| concepts[10].display_name | Combinatorics |
| concepts[11].id | https://openalex.org/C33923547 |
| concepts[11].level | 0 |
| concepts[11].score | 0.18319356441497803 |
| concepts[11].wikidata | https://www.wikidata.org/wiki/Q395 |
| concepts[11].display_name | Mathematics |
| concepts[12].id | https://openalex.org/C23123220 |
| concepts[12].level | 1 |
| concepts[12].score | 0.1389666199684143 |
| concepts[12].wikidata | https://www.wikidata.org/wiki/Q816826 |
| concepts[12].display_name | Information retrieval |
| concepts[13].id | https://openalex.org/C199360897 |
| concepts[13].level | 1 |
| concepts[13].score | 0.0 |
| concepts[13].wikidata | https://www.wikidata.org/wiki/Q9143 |
| concepts[13].display_name | Programming language |
| keywords[0].id | https://openalex.org/keywords/computer-science |
| keywords[0].score | 0.7633273601531982 |
| keywords[0].display_name | Computer science |
| keywords[1].id | https://openalex.org/keywords/joins |
| keywords[1].score | 0.763214111328125 |
| keywords[1].display_name | Joins |
| keywords[2].id | https://openalex.org/keywords/lexicographical-order |
| keywords[2].score | 0.6954164505004883 |
| keywords[2].display_name | Lexicographical order |
| keywords[3].id | https://openalex.org/keywords/search-engine-indexing |
| keywords[3].score | 0.690894603729248 |
| keywords[3].display_name | Search engine indexing |
| keywords[4].id | https://openalex.org/keywords/graph |
| keywords[4].score | 0.4753551185131073 |
| keywords[4].display_name | Graph |
| keywords[5].id | https://openalex.org/keywords/cardinality |
| keywords[5].score | 0.4536074101924896 |
| keywords[5].display_name | Cardinality (data modeling) |
| keywords[6].id | https://openalex.org/keywords/database |
| keywords[6].score | 0.4356966018676758 |
| keywords[6].display_name | Database |
| keywords[7].id | https://openalex.org/keywords/graph-database |
| keywords[7].score | 0.41198575496673584 |
| keywords[7].display_name | Graph database |
| keywords[8].id | https://openalex.org/keywords/algorithm |
| keywords[8].score | 0.35331207513809204 |
| keywords[8].display_name | Algorithm |
| keywords[9].id | https://openalex.org/keywords/theoretical-computer-science |
| keywords[9].score | 0.340864360332489 |
| keywords[9].display_name | Theoretical computer science |
| keywords[10].id | https://openalex.org/keywords/combinatorics |
| keywords[10].score | 0.20057007670402527 |
| keywords[10].display_name | Combinatorics |
| keywords[11].id | https://openalex.org/keywords/mathematics |
| keywords[11].score | 0.18319356441497803 |
| keywords[11].display_name | Mathematics |
| keywords[12].id | https://openalex.org/keywords/information-retrieval |
| keywords[12].score | 0.1389666199684143 |
| keywords[12].display_name | Information retrieval |
| language | en |
| locations[0].id | doi:10.1145/3644824 |
| locations[0].is_oa | False |
| locations[0].source.id | https://openalex.org/S90119964 |
| locations[0].source.issn | 0362-5915, 1557-4644 |
| locations[0].source.type | journal |
| locations[0].source.is_oa | False |
| locations[0].source.issn_l | 0362-5915 |
| locations[0].source.is_core | True |
| locations[0].source.is_in_doaj | False |
| locations[0].source.display_name | ACM Transactions on Database Systems |
| locations[0].source.host_organization | https://openalex.org/P4310319798 |
| locations[0].source.host_organization_name | Association for Computing Machinery |
| locations[0].source.host_organization_lineage | https://openalex.org/P4310319798 |
| locations[0].license | |
| locations[0].pdf_url | |
| locations[0].version | publishedVersion |
| locations[0].raw_type | journal-article |
| locations[0].license_id | |
| locations[0].is_accepted | True |
| locations[0].is_published | True |
| locations[0].raw_source_name | ACM Transactions on Database Systems |
| locations[0].landing_page_url | https://doi.org/10.1145/3644824 |
| locations[1].id | pmh:oai:ruc.udc.es:2183/37862 |
| locations[1].is_oa | True |
| locations[1].source.id | https://openalex.org/S4306402204 |
| locations[1].source.issn | |
| locations[1].source.type | repository |
| locations[1].source.is_oa | False |
| locations[1].source.issn_l | |
| locations[1].source.is_core | False |
| locations[1].source.is_in_doaj | False |
| locations[1].source.display_name | RUC (Universidade Da Coruña) |
| locations[1].source.host_organization | |
| locations[1].source.host_organization_name | |
| locations[1].source.host_organization_lineage | |
| locations[1].license | other-oa |
| locations[1].pdf_url | |
| locations[1].version | acceptedVersion |
| locations[1].raw_type | info:eu-repo/semantics/article |
| locations[1].license_id | https://openalex.org/licenses/other-oa |
| locations[1].is_accepted | True |
| locations[1].is_published | False |
| locations[1].raw_source_name | |
| locations[1].landing_page_url | http://hdl.handle.net/2183/37862 |
| indexed_in | crossref |
| authorships[0].author.id | https://openalex.org/A5050699073 |
| authorships[0].author.orcid | https://orcid.org/0000-0002-2509-8097 |
| authorships[0].author.display_name | Diego Arroyuelo |
| authorships[0].countries | CL |
| authorships[0].affiliations[0].institution_ids | https://openalex.org/I162148367 |
| authorships[0].affiliations[0].raw_affiliation_string | DCC, Escuela de Ingeniería, Pontificia Universidad Católica & IMFD, Santiago, Chile |
| authorships[0].institutions[0].id | https://openalex.org/I162148367 |
| authorships[0].institutions[0].ror | https://ror.org/04teye511 |
| authorships[0].institutions[0].type | education |
| authorships[0].institutions[0].lineage | https://openalex.org/I162148367 |
| authorships[0].institutions[0].country_code | CL |
| authorships[0].institutions[0].display_name | Pontificia Universidad Católica de Chile |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Diego Arroyuelo |
| authorships[0].is_corresponding | False |
| authorships[0].raw_affiliation_strings | DCC, Escuela de Ingeniería, Pontificia Universidad Católica & IMFD, Santiago, Chile |
| authorships[1].author.id | https://openalex.org/A5045121904 |
| authorships[1].author.orcid | https://orcid.org/0000-0002-1216-2176 |
| authorships[1].author.display_name | Adrián Gómez‐Brandón |
| authorships[1].countries | ES |
| authorships[1].affiliations[0].institution_ids | https://openalex.org/I11019714 |
| authorships[1].affiliations[0].raw_affiliation_string | Universidade da Coruña & CITIC & IMFD, A Coruña, Spain |
| authorships[1].institutions[0].id | https://openalex.org/I11019714 |
| authorships[1].institutions[0].ror | https://ror.org/01qckj285 |
| authorships[1].institutions[0].type | education |
| authorships[1].institutions[0].lineage | https://openalex.org/I11019714 |
| authorships[1].institutions[0].country_code | ES |
| authorships[1].institutions[0].display_name | Universidade da Coruña |
| authorships[1].author_position | middle |
| authorships[1].raw_author_name | Adrián Gómez-Brandón |
| authorships[1].is_corresponding | False |
| authorships[1].raw_affiliation_strings | Universidade da Coruña & CITIC & IMFD, A Coruña, Spain |
| authorships[2].author.id | https://openalex.org/A5070504151 |
| authorships[2].author.orcid | https://orcid.org/0000-0001-9482-1982 |
| authorships[2].author.display_name | Aidan Hogan |
| authorships[2].countries | CL |
| authorships[2].affiliations[0].institution_ids | https://openalex.org/I69737025 |
| authorships[2].affiliations[0].raw_affiliation_string | DCC, University of Chile & IMFD, Santiago, Chile |
| authorships[2].institutions[0].id | https://openalex.org/I69737025 |
| authorships[2].institutions[0].ror | https://ror.org/047gc3g35 |
| authorships[2].institutions[0].type | education |
| authorships[2].institutions[0].lineage | https://openalex.org/I69737025 |
| authorships[2].institutions[0].country_code | CL |
| authorships[2].institutions[0].display_name | University of Chile |
| authorships[2].author_position | middle |
| authorships[2].raw_author_name | Aidan Hogan |
| authorships[2].is_corresponding | False |
| authorships[2].raw_affiliation_strings | DCC, University of Chile & IMFD, Santiago, Chile |
| authorships[3].author.id | https://openalex.org/A5080743153 |
| authorships[3].author.orcid | https://orcid.org/0000-0002-2286-741X |
| authorships[3].author.display_name | Gonzalo Navarro |
| authorships[3].countries | CL |
| authorships[3].affiliations[0].institution_ids | https://openalex.org/I69737025 |
| authorships[3].affiliations[0].raw_affiliation_string | DCC, University of Chile & IMFD, Santiago, Chile |
| authorships[3].institutions[0].id | https://openalex.org/I69737025 |
| authorships[3].institutions[0].ror | https://ror.org/047gc3g35 |
| authorships[3].institutions[0].type | education |
| authorships[3].institutions[0].lineage | https://openalex.org/I69737025 |
| authorships[3].institutions[0].country_code | CL |
| authorships[3].institutions[0].display_name | University of Chile |
| authorships[3].author_position | middle |
| authorships[3].raw_author_name | Gonzalo Navarro |
| authorships[3].is_corresponding | False |
| authorships[3].raw_affiliation_strings | DCC, University of Chile & IMFD, Santiago, Chile |
| authorships[4].author.id | https://openalex.org/A5000893188 |
| authorships[4].author.orcid | https://orcid.org/0000-0002-2186-0312 |
| authorships[4].author.display_name | Juan L. Reutter |
| authorships[4].countries | CL |
| authorships[4].affiliations[0].institution_ids | https://openalex.org/I162148367 |
| authorships[4].affiliations[0].raw_affiliation_string | DCC, Escuela de Ingeniería, Pontificia Universidad Católica & Instituto de Ingeniería Matemática y Computacional, Pontificia Universidad Católica & IMFD, Santiago, Chile |
| authorships[4].institutions[0].id | https://openalex.org/I162148367 |
| authorships[4].institutions[0].ror | https://ror.org/04teye511 |
| authorships[4].institutions[0].type | education |
| authorships[4].institutions[0].lineage | https://openalex.org/I162148367 |
| authorships[4].institutions[0].country_code | CL |
| authorships[4].institutions[0].display_name | Pontificia Universidad Católica de Chile |
| authorships[4].author_position | middle |
| authorships[4].raw_author_name | Juan Reutter |
| authorships[4].is_corresponding | False |
| authorships[4].raw_affiliation_strings | DCC, Escuela de Ingeniería, Pontificia Universidad Católica & Instituto de Ingeniería Matemática y Computacional, Pontificia Universidad Católica & IMFD, Santiago, Chile |
| authorships[5].author.id | https://openalex.org/A5081233098 |
| authorships[5].author.orcid | https://orcid.org/0000-0003-3208-1880 |
| authorships[5].author.display_name | Javiel Rojas-Ledesma |
| authorships[5].countries | CL |
| authorships[5].affiliations[0].institution_ids | https://openalex.org/I69737025 |
| authorships[5].affiliations[0].raw_affiliation_string | DCC, Universidad de Chile & IMFD, Penalolen, Chile |
| authorships[5].institutions[0].id | https://openalex.org/I69737025 |
| authorships[5].institutions[0].ror | https://ror.org/047gc3g35 |
| authorships[5].institutions[0].type | education |
| authorships[5].institutions[0].lineage | https://openalex.org/I69737025 |
| authorships[5].institutions[0].country_code | CL |
| authorships[5].institutions[0].display_name | University of Chile |
| authorships[5].author_position | middle |
| authorships[5].raw_author_name | Javiel Rojas-Ledesma |
| authorships[5].is_corresponding | False |
| authorships[5].raw_affiliation_strings | DCC, Universidad de Chile & IMFD, Penalolen, Chile |
| authorships[6].author.id | https://openalex.org/A5062640934 |
| authorships[6].author.orcid | https://orcid.org/0000-0001-7682-1639 |
| authorships[6].author.display_name | Adrián Soto |
| authorships[6].countries | CL |
| authorships[6].affiliations[0].institution_ids | https://openalex.org/I21067949 |
| authorships[6].affiliations[0].raw_affiliation_string | FIC, Universidad Adolfo Ibáñ ez & IMFD, Santiago, Chile |
| authorships[6].institutions[0].id | https://openalex.org/I21067949 |
| authorships[6].institutions[0].ror | https://ror.org/0326knt82 |
| authorships[6].institutions[0].type | education |
| authorships[6].institutions[0].lineage | https://openalex.org/I21067949 |
| authorships[6].institutions[0].country_code | CL |
| authorships[6].institutions[0].display_name | Adolfo Ibáñez University |
| authorships[6].author_position | last |
| authorships[6].raw_author_name | Adrián Soto |
| authorships[6].is_corresponding | False |
| authorships[6].raw_affiliation_strings | FIC, Universidad Adolfo Ibáñ ez & IMFD, Santiago, Chile |
| has_content.pdf | False |
| has_content.grobid_xml | False |
| is_paratext | False |
| open_access.is_oa | True |
| open_access.oa_url | http://hdl.handle.net/2183/37862 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2025-10-10T00:00:00 |
| display_name | The Ring: Worst-case Optimal Joins in Graph Databases using (Almost) No Extra Space |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-11-06T03:46:38.306776 |
| primary_topic.id | https://openalex.org/T11269 |
| primary_topic.field.id | https://openalex.org/fields/17 |
| primary_topic.field.display_name | Computer Science |
| primary_topic.score | 0.9998999834060669 |
| primary_topic.domain.id | https://openalex.org/domains/3 |
| primary_topic.domain.display_name | Physical Sciences |
| primary_topic.subfield.id | https://openalex.org/subfields/1702 |
| primary_topic.subfield.display_name | Artificial Intelligence |
| primary_topic.display_name | Algorithms and Data Compression |
| related_works | https://openalex.org/W2088925915, https://openalex.org/W2382891957, https://openalex.org/W2393491644, https://openalex.org/W2067184662, https://openalex.org/W1993634787, https://openalex.org/W3125614403, https://openalex.org/W2476923378, https://openalex.org/W3047837489, https://openalex.org/W3100240142, https://openalex.org/W2803221307 |
| cited_by_count | 6 |
| counts_by_year[0].year | 2025 |
| counts_by_year[0].cited_by_count | 3 |
| counts_by_year[1].year | 2024 |
| counts_by_year[1].cited_by_count | 3 |
| locations_count | 2 |
| best_oa_location.id | pmh:oai:ruc.udc.es:2183/37862 |
| best_oa_location.is_oa | True |
| best_oa_location.source.id | https://openalex.org/S4306402204 |
| best_oa_location.source.issn | |
| best_oa_location.source.type | repository |
| best_oa_location.source.is_oa | False |
| best_oa_location.source.issn_l | |
| best_oa_location.source.is_core | False |
| best_oa_location.source.is_in_doaj | False |
| best_oa_location.source.display_name | RUC (Universidade Da Coruña) |
| best_oa_location.source.host_organization | |
| best_oa_location.source.host_organization_name | |
| best_oa_location.source.host_organization_lineage | |
| best_oa_location.license | other-oa |
| best_oa_location.pdf_url | |
| best_oa_location.version | acceptedVersion |
| best_oa_location.raw_type | info:eu-repo/semantics/article |
| best_oa_location.license_id | https://openalex.org/licenses/other-oa |
| best_oa_location.is_accepted | True |
| best_oa_location.is_published | False |
| best_oa_location.raw_source_name | |
| best_oa_location.landing_page_url | http://hdl.handle.net/2183/37862 |
| primary_location.id | doi:10.1145/3644824 |
| primary_location.is_oa | False |
| primary_location.source.id | https://openalex.org/S90119964 |
| primary_location.source.issn | 0362-5915, 1557-4644 |
| primary_location.source.type | journal |
| primary_location.source.is_oa | False |
| primary_location.source.issn_l | 0362-5915 |
| primary_location.source.is_core | True |
| primary_location.source.is_in_doaj | False |
| primary_location.source.display_name | ACM Transactions on Database Systems |
| primary_location.source.host_organization | https://openalex.org/P4310319798 |
| primary_location.source.host_organization_name | Association for Computing Machinery |
| primary_location.source.host_organization_lineage | https://openalex.org/P4310319798 |
| primary_location.license | |
| primary_location.pdf_url | |
| primary_location.version | publishedVersion |
| primary_location.raw_type | journal-article |
| primary_location.license_id | |
| primary_location.is_accepted | True |
| primary_location.is_published | True |
| primary_location.raw_source_name | ACM Transactions on Database Systems |
| primary_location.landing_page_url | https://doi.org/10.1145/3644824 |
| publication_date | 2024-02-08 |
| publication_year | 2024 |
| referenced_works | https://openalex.org/W4244579861, https://openalex.org/W2013520691, https://openalex.org/W2668736619, https://openalex.org/W4386509124, https://openalex.org/W3173455703, https://openalex.org/W2161584750, https://openalex.org/W2169998163, https://openalex.org/W2116258248, https://openalex.org/W2051511420, https://openalex.org/W2913970915, https://openalex.org/W4252462081, https://openalex.org/W3089271291, https://openalex.org/W2613282787, https://openalex.org/W2038647778, https://openalex.org/W2184653508, https://openalex.org/W6713578294, https://openalex.org/W1495014783, https://openalex.org/W2013667086, https://openalex.org/W2159647614, https://openalex.org/W2107082304, https://openalex.org/W2799059383, https://openalex.org/W3094660140, https://openalex.org/W2049204576, https://openalex.org/W2151453116, https://openalex.org/W1962019683, https://openalex.org/W2041961594, https://openalex.org/W2050882124, https://openalex.org/W2161291780, https://openalex.org/W2980615028, https://openalex.org/W2552956925, https://openalex.org/W2585424461, https://openalex.org/W2890592029, https://openalex.org/W1798412263, https://openalex.org/W2970204999, https://openalex.org/W4237754109, https://openalex.org/W2183729464, https://openalex.org/W2086536051, https://openalex.org/W4247794781, https://openalex.org/W2000656232, https://openalex.org/W2794645646, https://openalex.org/W2790840297, https://openalex.org/W2015362435, https://openalex.org/W2536131596, https://openalex.org/W2089455813, https://openalex.org/W2949054050, https://openalex.org/W1974033543, https://openalex.org/W1791587242, https://openalex.org/W3023361615, https://openalex.org/W1986055680, https://openalex.org/W2080133951, https://openalex.org/W2135577024, https://openalex.org/W2915063781, https://openalex.org/W4249717268, https://openalex.org/W2911252216, https://openalex.org/W2405066551, https://openalex.org/W4232666159, https://openalex.org/W3103927822, https://openalex.org/W2161488606 |
| referenced_works_count | 58 |
| abstract_inverted_index.! | 244 |
| abstract_inverted_index.) | 258 |
| abstract_inverted_index., | 25, 292, 361 |
| abstract_inverted_index.3 | 221 |
| abstract_inverted_index.4 | 389 |
| abstract_inverted_index.5 | 268 |
| abstract_inverted_index.6 | 127 |
| abstract_inverted_index.O | 255 |
| abstract_inverted_index.a | 23, 30, 54, 81, 86, 173, 193, 224, 231, 261, 283, 333, 351 |
| abstract_inverted_index.d | 218, 236, 243, 257, 275, 360, 382 |
| abstract_inverted_index.(2 | 256 |
| abstract_inverted_index.3. | 35 |
| abstract_inverted_index.=5 | 383 |
| abstract_inverted_index.We | 0, 73, 204, 277, 343 |
| abstract_inverted_index.an | 2, 308, 314 |
| abstract_inverted_index.as | 29, 53, 120 |
| abstract_inverted_index.by | 65, 70, 76, 200, 302, 317 |
| abstract_inverted_index.in | 12, 162, 177, 222 |
| abstract_inverted_index.is | 41, 322, 337 |
| abstract_inverted_index.no | 164, 237 |
| abstract_inverted_index.of | 33, 38, 47, 61, 196, 216, 234, 271, 286, 326, 335, 355, 358 |
| abstract_inverted_index.so | 56, 124 |
| abstract_inverted_index.to | 130, 143, 209, 240, 251, 310, 365, 388 |
| abstract_inverted_index.us | 306, 364 |
| abstract_inverted_index.we | 57, 138, 246, 266, 288, 380 |
| abstract_inverted_index.120 | 272 |
| abstract_inverted_index.=5. | 276 |
| abstract_inverted_index.For | 264, 378 |
| abstract_inverted_index.The | 320 |
| abstract_inverted_index.all | 132, 242 |
| abstract_inverted_index.and | 44, 93, 109, 123, 152, 298, 332, 369 |
| abstract_inverted_index.are | 51, 295, 375 |
| abstract_inverted_index.can | 139, 362 |
| abstract_inverted_index.dub | 289 |
| abstract_inverted_index.for | 5, 112, 213, 274, 349 |
| abstract_inverted_index.its | 71 |
| abstract_inverted_index.on, | 125 |
| abstract_inverted_index.one | 141, 339 |
| abstract_inverted_index.our | 207, 280 |
| abstract_inverted_index.set | 325, 334 |
| abstract_inverted_index.the | 39, 45, 48, 59, 62, 68, 78, 150, 168, 181, 185, 197, 318, 324, 330 |
| abstract_inverted_index.use | 140 |
| abstract_inverted_index.way | 225 |
| abstract_inverted_index.wco | 106, 134, 160, 228 |
| abstract_inverted_index.Each | 36 |
| abstract_inverted_index.This | 20, 147 |
| abstract_inverted_index.all. | 146 |
| abstract_inverted_index.all: | 254 |
| abstract_inverted_index.also | 376 |
| abstract_inverted_index.best | 186 |
| abstract_inverted_index.case | 285 |
| abstract_inverted_index.data | 83, 117 |
| abstract_inverted_index.each | 27 |
| abstract_inverted_index.edge | 315 |
| abstract_inverted_index.even | 366 |
| abstract_inverted_index.from | 307 |
| abstract_inverted_index.join | 10, 107 |
| abstract_inverted_index.just | 338 |
| abstract_inverted_index.last | 49 |
| abstract_inverted_index.lead | 363 |
| abstract_inverted_index.like | 348 |
| abstract_inverted_index.more | 372 |
| abstract_inverted_index.much | 248 |
| abstract_inverted_index.need | 247, 267 |
| abstract_inverted_index.next | 63 |
| abstract_inverted_index.ones | 357 |
| abstract_inverted_index.only | 154, 192 |
| abstract_inverted_index.over | 136 |
| abstract_inverted_index.ring | 24, 142, 148, 182, 233, 353 |
| abstract_inverted_index.show | 74, 179, 278, 344 |
| abstract_inverted_index.some | 210, 303 |
| abstract_inverted_index.such | 119, 223 |
| abstract_inverted_index.than | 220 |
| abstract_inverted_index.that | 8, 180, 226, 279, 345, 370 |
| abstract_inverted_index.them | 145, 253 |
| abstract_inverted_index.then | 205, 323 |
| abstract_inverted_index.this | 89 |
| abstract_inverted_index.thus | 158 |
| abstract_inverted_index.time | 16 |
| abstract_inverted_index.turn | 206 |
| abstract_inverted_index.uses | 153 |
| abstract_inverted_index.what | 287 |
| abstract_inverted_index.with | 80, 260, 329 |
| abstract_inverted_index.(wco) | 15 |
| abstract_inverted_index.These | 101 |
| abstract_inverted_index.While | 115, 230 |
| abstract_inverted_index.arity | 217 |
| abstract_inverted_index.cover | 241 |
| abstract_inverted_index.extra | 156 |
| abstract_inverted_index.fewer | 249 |
| abstract_inverted_index.graph | 151, 169, 175, 341 |
| abstract_inverted_index.index | 128, 144, 252, 321 |
| abstract_inverted_index.joins | 135, 161 |
| abstract_inverted_index.large | 174 |
| abstract_inverted_index.leads | 305 |
| abstract_inverted_index.nodes | 294 |
| abstract_inverted_index.order | 60, 290, 309 |
| abstract_inverted_index.other | 346, 371 |
| abstract_inverted_index.query | 113, 188 |
| abstract_inverted_index.rings | 250, 259, 269, 281, 336 |
| abstract_inverted_index.small | 194, 262 |
| abstract_inverted_index.space | 165, 198, 386 |
| abstract_inverted_index.that, | 75 |
| abstract_inverted_index.times | 189 |
| abstract_inverted_index.tree, | 88 |
| abstract_inverted_index.trees | 103 |
| abstract_inverted_index.using | 191 |
| abstract_inverted_index.where | 299 |
| abstract_inverted_index.while | 190 |
| abstract_inverted_index.whose | 293 |
| abstract_inverted_index.almost | 163 |
| abstract_inverted_index.become | 282 |
| abstract_inverted_index.beyond | 166 |
| abstract_inverted_index.called | 22, 85 |
| abstract_inverted_index.column | 64 |
| abstract_inverted_index.cyclic | 31 |
| abstract_inverted_index.edges, | 331 |
| abstract_inverted_index.graphs | 7, 291 |
| abstract_inverted_index.handle | 381 |
| abstract_inverted_index.higher | 219 |
| abstract_inverted_index.joins. | 229 |
| abstract_inverted_index.length | 34, 235, 359 |
| abstract_inverted_index.longer | 238 |
| abstract_inverted_index.memory | 178 |
| abstract_inverted_index.nearly | 184 |
| abstract_inverted_index.obtain | 58 |
| abstract_inverted_index.offers | 183 |
| abstract_inverted_index.orders | 129, 273, 297 |
| abstract_inverted_index.rings. | 390 |
| abstract_inverted_index.scheme | 4 |
| abstract_inverted_index.shape. | 342 |
| abstract_inverted_index.shapes | 374 |
| abstract_inverted_index.single | 232, 352 |
| abstract_inverted_index.sorted | 43 |
| abstract_inverted_index.space, | 157 |
| abstract_inverted_index.space. | 19 |
| abstract_inverted_index.stably | 66, 300 |
| abstract_inverted_index.stored | 52 |
| abstract_inverted_index.string | 32 |
| abstract_inverted_index.tables | 215 |
| abstract_inverted_index.tries, | 122 |
| abstract_inverted_index.triple | 28 |
| abstract_inverted_index.values | 46 |
| abstract_inverted_index.within | 17, 385 |
| abstract_inverted_index.between | 96 |
| abstract_inverted_index.column, | 55 |
| abstract_inverted_index.columns | 79, 97, 327 |
| abstract_inverted_index.compact | 18, 82 |
| abstract_inverted_index.enables | 91 |
| abstract_inverted_index.example | 350 |
| abstract_inverted_index.forward | 92 |
| abstract_inverted_index.further | 104 |
| abstract_inverted_index.general | 373 |
| abstract_inverted_index.instead | 270, 354 |
| abstract_inverted_index.itself. | 170 |
| abstract_inverted_index.labeled | 316 |
| abstract_inverted_index.needing | 99 |
| abstract_inverted_index.optimal | 14 |
| abstract_inverted_index.orders, | 245 |
| abstract_inverted_index.overall | 187 |
| abstract_inverted_index.present | 1 |
| abstract_inverted_index.queries | 11 |
| abstract_inverted_index.regards | 26 |
| abstract_inverted_index.require | 126 |
| abstract_inverted_index.results | 212 |
| abstract_inverted_index.scheme, | 21 |
| abstract_inverted_index.several | 201, 356 |
| abstract_inverted_index.shapes, | 347 |
| abstract_inverted_index.smaller | 367 |
| abstract_inverted_index.sorting | 301 |
| abstract_inverted_index.storing | 167 |
| abstract_inverted_index.support | 105, 131 |
| abstract_inverted_index.thereby | 312 |
| abstract_inverted_index.triples | 40, 69 |
| abstract_inverted_index.wavelet | 87, 102 |
| abstract_inverted_index.without | 98 |
| abstract_inverted_index.B-Trees, | 121 |
| abstract_inverted_index.another, | 311 |
| abstract_inverted_index.backward | 94 |
| abstract_inverted_index.example, | 265, 379 |
| abstract_inverted_index.fraction | 195 |
| abstract_inverted_index.indexes, | 368 |
| abstract_inverted_index.indexing | 3, 214 |
| abstract_inverted_index.inducing | 313 |
| abstract_inverted_index.ordering | 90 |
| abstract_inverted_index.possible | 133, 340 |
| abstract_inverted_index.querying | 172 |
| abstract_inverted_index.replaces | 149 |
| abstract_inverted_index.required | 199 |
| abstract_inverted_index.rotation | 37 |
| abstract_inverted_index.suffices | 239 |
| abstract_inverted_index.supports | 9, 227 |
| abstract_inverted_index.triples, | 137 |
| abstract_inverted_index.attention | 208 |
| abstract_inverted_index.attribute | 50, 296, 304 |
| abstract_inverted_index.constant. | 263 |
| abstract_inverted_index.planning. | 114 |
| abstract_inverted_index.pointers. | 100 |
| abstract_inverted_index.possible. | 377 |
| abstract_inverted_index.structure | 84 |
| abstract_inverted_index.sublinear | 155 |
| abstract_inverted_index.(Wikidata) | 176 |
| abstract_inverted_index.algorithms | 108 |
| abstract_inverted_index.associated | 328 |
| abstract_inverted_index.attribute. | 72, 319 |
| abstract_inverted_index.attributes | 384 |
| abstract_inverted_index.equivalent | 387 |
| abstract_inverted_index.navigation | 95 |
| abstract_inverted_index.particular | 284 |
| abstract_inverted_index.re-sorting | 67 |
| abstract_inverted_index.structures | 118 |
| abstract_inverted_index.supporting | 159 |
| abstract_inverted_index.worst-case | 13 |
| abstract_inverted_index.Experiments | 171 |
| abstract_inverted_index.approaches. | 203 |
| abstract_inverted_index.cardinality | 110 |
| abstract_inverted_index.estimations | 111 |
| abstract_inverted_index.theoretical | 211 |
| abstract_inverted_index.traditional | 116 |
| abstract_inverted_index.representing | 77 |
| abstract_inverted_index.triple-based | 6 |
| abstract_inverted_index.state-of-the-art | 202 |
| abstract_inverted_index.lexicographically | 42 |
| cited_by_percentile_year.max | 97 |
| cited_by_percentile_year.min | 96 |
| countries_distinct_count | 2 |
| institutions_distinct_count | 7 |
| sustainable_development_goals[0].id | https://metadata.un.org/sdg/11 |
| sustainable_development_goals[0].score | 0.5899999737739563 |
| sustainable_development_goals[0].display_name | Sustainable cities and communities |
| citation_normalized_percentile.value | 0.90953777 |
| citation_normalized_percentile.is_in_top_1_percent | False |
| citation_normalized_percentile.is_in_top_10_percent | True |