Barriers for Faster Dimensionality Reduction Article Swipe
Ora Nova Fandina
,
Mikael Møller Høgsgaard
,
Kasper Green Larsen
,
Petra Berenbrink
,
Patricia Bouyer
,
Anuj Dawar
,
Mamadou Moustapha Kanté
·
YOU?
·
· 2023
· Open Access
·
· DOI: https://doi.org/10.4230/lipics.stacs.2023.31
YOU?
·
· 2023
· Open Access
·
· DOI: https://doi.org/10.4230/lipics.stacs.2023.31
The Johnson-Lindenstrauss transform allows one to embed a dataset of n points in ℝ^d into ℝ^m, while preserving the pairwise distance between any pair of points up to a factor (1 ± ε), provided that m = Ω(ε^{-2} lg n). The transform has found an overwhelming number of algorithmic applications, allowing to speed up algorithms and reducing memory consumption at the price of a small loss in accuracy. A central line of research on such transforms, focus on developing fast embedding algorithms, with the classic example being the Fast JL transform by Ailon and Chazelle. All known such algorithms have an embedding time of Ω(d lg d), but no lower bounds rule out a clean O(d) embedding time. In this work, we establish the first non-trivial lower bounds (of magnitude Ω(m lg m)) for a large class of embedding algorithms, including in particular most known upper bounds.
Related Topics
Concepts
Dimensionality reduction
Reduction (mathematics)
Multifactor dimensionality reduction
Computer science
Curse of dimensionality
Artificial intelligence
Mathematics
Chemistry
Geometry
Biochemistry
Gene
Genotype
Single-nucleotide polymorphism
Metadata
- Type
- article
- Language
- en
- Landing Page
- https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.31
- OA Status
- green
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W4412233758
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W4412233758Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.4230/lipics.stacs.2023.31Digital Object Identifier
- Title
-
Barriers for Faster Dimensionality ReductionWork title
- Type
-
articleOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2023Year of publication
- Publication date
-
2023-01-01Full publication date if available
- Authors
-
Ora Nova Fandina, Mikael Møller Høgsgaard, Kasper Green Larsen, Petra Berenbrink, Patricia Bouyer, Anuj Dawar, Mamadou Moustapha KantéList of authors in order
- Landing page
-
https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.31Publisher landing page
- Open access
-
YesWhether a free full text is available
- OA status
-
greenOpen access status per OpenAlex
- OA URL
-
https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.31Direct OA link when available
- Concepts
-
Dimensionality reduction, Reduction (mathematics), Multifactor dimensionality reduction, Computer science, Curse of dimensionality, Artificial intelligence, Mathematics, Chemistry, Geometry, Biochemistry, Gene, Genotype, Single-nucleotide polymorphismTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
0Total citation count in OpenAlex
- Related works (count)
-
10Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W4412233758 |
|---|---|
| doi | https://doi.org/10.4230/lipics.stacs.2023.31 |
| ids.openalex | https://openalex.org/W4412233758 |
| fwci | 0.0 |
| type | article |
| title | Barriers for Faster Dimensionality Reduction |
| biblio.issue | |
| biblio.volume | |
| biblio.last_page | |
| biblio.first_page | |
| topics[0].id | https://openalex.org/T12111 |
| topics[0].field.id | https://openalex.org/fields/22 |
| topics[0].field.display_name | Engineering |
| topics[0].score | 0.1868000030517578 |
| topics[0].domain.id | https://openalex.org/domains/3 |
| topics[0].domain.display_name | Physical Sciences |
| topics[0].subfield.id | https://openalex.org/subfields/2209 |
| topics[0].subfield.display_name | Industrial and Manufacturing Engineering |
| topics[0].display_name | Industrial Vision Systems and Defect Detection |
| topics[1].id | https://openalex.org/T13114 |
| topics[1].field.id | https://openalex.org/fields/22 |
| topics[1].field.display_name | Engineering |
| topics[1].score | 0.16769999265670776 |
| topics[1].domain.id | https://openalex.org/domains/3 |
| topics[1].domain.display_name | Physical Sciences |
| topics[1].subfield.id | https://openalex.org/subfields/2214 |
| topics[1].subfield.display_name | Media Technology |
| topics[1].display_name | Image Processing Techniques and Applications |
| topics[2].id | https://openalex.org/T10320 |
| topics[2].field.id | https://openalex.org/fields/17 |
| topics[2].field.display_name | Computer Science |
| topics[2].score | 0.16670000553131104 |
| topics[2].domain.id | https://openalex.org/domains/3 |
| topics[2].domain.display_name | Physical Sciences |
| topics[2].subfield.id | https://openalex.org/subfields/1702 |
| topics[2].subfield.display_name | Artificial Intelligence |
| topics[2].display_name | Neural Networks and Applications |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C70518039 |
| concepts[0].level | 2 |
| concepts[0].score | 0.7963120937347412 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q16000077 |
| concepts[0].display_name | Dimensionality reduction |
| concepts[1].id | https://openalex.org/C111335779 |
| concepts[1].level | 2 |
| concepts[1].score | 0.6094251871109009 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q3454686 |
| concepts[1].display_name | Reduction (mathematics) |
| concepts[2].id | https://openalex.org/C25249476 |
| concepts[2].level | 5 |
| concepts[2].score | 0.5049129128456116 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q6934678 |
| concepts[2].display_name | Multifactor dimensionality reduction |
| concepts[3].id | https://openalex.org/C41008148 |
| concepts[3].level | 0 |
| concepts[3].score | 0.4705926179885864 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[3].display_name | Computer science |
| concepts[4].id | https://openalex.org/C111030470 |
| concepts[4].level | 2 |
| concepts[4].score | 0.41527047753334045 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q1430460 |
| concepts[4].display_name | Curse of dimensionality |
| concepts[5].id | https://openalex.org/C154945302 |
| concepts[5].level | 1 |
| concepts[5].score | 0.2249450385570526 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q11660 |
| concepts[5].display_name | Artificial intelligence |
| concepts[6].id | https://openalex.org/C33923547 |
| concepts[6].level | 0 |
| concepts[6].score | 0.20884406566619873 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q395 |
| concepts[6].display_name | Mathematics |
| concepts[7].id | https://openalex.org/C185592680 |
| concepts[7].level | 0 |
| concepts[7].score | 0.16626980900764465 |
| concepts[7].wikidata | https://www.wikidata.org/wiki/Q2329 |
| concepts[7].display_name | Chemistry |
| concepts[8].id | https://openalex.org/C2524010 |
| concepts[8].level | 1 |
| concepts[8].score | 0.0459904670715332 |
| concepts[8].wikidata | https://www.wikidata.org/wiki/Q8087 |
| concepts[8].display_name | Geometry |
| concepts[9].id | https://openalex.org/C55493867 |
| concepts[9].level | 1 |
| concepts[9].score | 0.0 |
| concepts[9].wikidata | https://www.wikidata.org/wiki/Q7094 |
| concepts[9].display_name | Biochemistry |
| concepts[10].id | https://openalex.org/C104317684 |
| concepts[10].level | 2 |
| concepts[10].score | 0.0 |
| concepts[10].wikidata | https://www.wikidata.org/wiki/Q7187 |
| concepts[10].display_name | Gene |
| concepts[11].id | https://openalex.org/C135763542 |
| concepts[11].level | 3 |
| concepts[11].score | 0.0 |
| concepts[11].wikidata | https://www.wikidata.org/wiki/Q106016 |
| concepts[11].display_name | Genotype |
| concepts[12].id | https://openalex.org/C153209595 |
| concepts[12].level | 4 |
| concepts[12].score | 0.0 |
| concepts[12].wikidata | https://www.wikidata.org/wiki/Q501128 |
| concepts[12].display_name | Single-nucleotide polymorphism |
| keywords[0].id | https://openalex.org/keywords/dimensionality-reduction |
| keywords[0].score | 0.7963120937347412 |
| keywords[0].display_name | Dimensionality reduction |
| keywords[1].id | https://openalex.org/keywords/reduction |
| keywords[1].score | 0.6094251871109009 |
| keywords[1].display_name | Reduction (mathematics) |
| keywords[2].id | https://openalex.org/keywords/multifactor-dimensionality-reduction |
| keywords[2].score | 0.5049129128456116 |
| keywords[2].display_name | Multifactor dimensionality reduction |
| keywords[3].id | https://openalex.org/keywords/computer-science |
| keywords[3].score | 0.4705926179885864 |
| keywords[3].display_name | Computer science |
| keywords[4].id | https://openalex.org/keywords/curse-of-dimensionality |
| keywords[4].score | 0.41527047753334045 |
| keywords[4].display_name | Curse of dimensionality |
| keywords[5].id | https://openalex.org/keywords/artificial-intelligence |
| keywords[5].score | 0.2249450385570526 |
| keywords[5].display_name | Artificial intelligence |
| keywords[6].id | https://openalex.org/keywords/mathematics |
| keywords[6].score | 0.20884406566619873 |
| keywords[6].display_name | Mathematics |
| keywords[7].id | https://openalex.org/keywords/chemistry |
| keywords[7].score | 0.16626980900764465 |
| keywords[7].display_name | Chemistry |
| keywords[8].id | https://openalex.org/keywords/geometry |
| keywords[8].score | 0.0459904670715332 |
| keywords[8].display_name | Geometry |
| language | en |
| locations[0].id | pmh:oai:drops-oai.dagstuhl.de:17683 |
| locations[0].is_oa | True |
| locations[0].source.id | https://openalex.org/S4306402524 |
| locations[0].source.issn | |
| locations[0].source.type | repository |
| locations[0].source.is_oa | False |
| locations[0].source.issn_l | |
| locations[0].source.is_core | False |
| locations[0].source.is_in_doaj | False |
| locations[0].source.display_name | Leibniz-Zentrum für Informatik (Schloss Dagstuhl) |
| locations[0].source.host_organization | https://openalex.org/I2799853480 |
| locations[0].source.host_organization_name | Schloss Dagstuhl – Leibniz Center for Informatics |
| locations[0].source.host_organization_lineage | https://openalex.org/I2799853480 |
| locations[0].license | cc-by |
| locations[0].pdf_url | |
| locations[0].version | publishedVersion |
| locations[0].raw_type | InProceedings |
| locations[0].license_id | https://openalex.org/licenses/cc-by |
| locations[0].is_accepted | True |
| locations[0].is_published | True |
| locations[0].raw_source_name | |
| locations[0].landing_page_url | https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.31 |
| locations[1].id | pmh:oai:pure.atira.dk:openaire/69b98c47-0b4d-48af-b148-3ae215a95a68 |
| locations[1].is_oa | True |
| locations[1].source.id | https://openalex.org/S4306400216 |
| 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 | Research Portal (King's College London) |
| locations[1].source.host_organization | https://openalex.org/I183935753 |
| locations[1].source.host_organization_name | King's College London |
| locations[1].source.host_organization_lineage | https://openalex.org/I183935753 |
| locations[1].license | cc-by |
| locations[1].pdf_url | |
| locations[1].version | submittedVersion |
| locations[1].raw_type | contributionToPeriodical |
| locations[1].license_id | https://openalex.org/licenses/cc-by |
| locations[1].is_accepted | False |
| locations[1].is_published | False |
| locations[1].raw_source_name | Fandina, O N, Høgsgaard, M M & Larsen, K G 2023, Barriers for Faster Dimensionality Reduction. in P Berenbrink, P Bouyer, A Dawar & M M Kante (eds), 40th International Symposium on Theoretical Aspects of Computer Science, STACS 2023., 31, Dagstuhl Publishing, Leibniz International Proceedings in Informatics, LIPIcs, vol. 254, 40th International Symposium on Theoretical Aspects of Computer Science, STACS 2023, Hamburg, Germany, 07/03/2023. https://doi.org/10.4230/LIPIcs.STACS.2023.31 |
| locations[1].landing_page_url | https://pure.au.dk/portal/en/publications/69b98c47-0b4d-48af-b148-3ae215a95a68 |
| authorships[0].author.id | https://openalex.org/A5013947961 |
| authorships[0].author.orcid | https://orcid.org/0000-0002-3545-1501 |
| authorships[0].author.display_name | Ora Nova Fandina |
| authorships[0].countries | DK |
| authorships[0].affiliations[0].institution_ids | https://openalex.org/I204337017 |
| authorships[0].affiliations[0].raw_affiliation_string | Aarhus University, Natural Sciences, Department of Computer Science, DK |
| authorships[0].institutions[0].id | https://openalex.org/I204337017 |
| authorships[0].institutions[0].ror | https://ror.org/01aj84f44 |
| authorships[0].institutions[0].type | education |
| authorships[0].institutions[0].lineage | https://openalex.org/I204337017 |
| authorships[0].institutions[0].country_code | DK |
| authorships[0].institutions[0].display_name | Aarhus University |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Ora Nova Fandina |
| authorships[0].is_corresponding | True |
| authorships[0].raw_affiliation_strings | Aarhus University, Natural Sciences, Department of Computer Science, DK |
| authorships[1].author.id | https://openalex.org/A5067430268 |
| authorships[1].author.orcid | |
| authorships[1].author.display_name | Mikael Møller Høgsgaard |
| authorships[1].countries | DK |
| authorships[1].affiliations[0].institution_ids | https://openalex.org/I204337017 |
| authorships[1].affiliations[0].raw_affiliation_string | Aarhus University, Natural Sciences, Department of Computer Science, DK |
| authorships[1].institutions[0].id | https://openalex.org/I204337017 |
| authorships[1].institutions[0].ror | https://ror.org/01aj84f44 |
| authorships[1].institutions[0].type | education |
| authorships[1].institutions[0].lineage | https://openalex.org/I204337017 |
| authorships[1].institutions[0].country_code | DK |
| authorships[1].institutions[0].display_name | Aarhus University |
| authorships[1].author_position | middle |
| authorships[1].raw_author_name | Mikael Møller Høgsgaard |
| authorships[1].is_corresponding | True |
| authorships[1].raw_affiliation_strings | Aarhus University, Natural Sciences, Department of Computer Science, DK |
| authorships[2].author.id | https://openalex.org/A5013551063 |
| authorships[2].author.orcid | https://orcid.org/0000-0001-8841-5929 |
| authorships[2].author.display_name | Kasper Green Larsen |
| authorships[2].countries | DK |
| authorships[2].affiliations[0].institution_ids | https://openalex.org/I204337017 |
| authorships[2].affiliations[0].raw_affiliation_string | Aarhus University, Natural Sciences, Department of Computer Science, DK |
| authorships[2].institutions[0].id | https://openalex.org/I204337017 |
| authorships[2].institutions[0].ror | https://ror.org/01aj84f44 |
| authorships[2].institutions[0].type | education |
| authorships[2].institutions[0].lineage | https://openalex.org/I204337017 |
| authorships[2].institutions[0].country_code | DK |
| authorships[2].institutions[0].display_name | Aarhus University |
| authorships[2].author_position | middle |
| authorships[2].raw_author_name | Kasper Green Larsen |
| authorships[2].is_corresponding | True |
| authorships[2].raw_affiliation_strings | Aarhus University, Natural Sciences, Department of Computer Science, DK |
| authorships[3].author.id | https://openalex.org/A5072910141 |
| authorships[3].author.orcid | https://orcid.org/0000-0002-6930-3259 |
| authorships[3].author.display_name | Petra Berenbrink |
| authorships[3].author_position | middle |
| authorships[3].raw_author_name | Petra Berenbrink |
| authorships[3].is_corresponding | False |
| authorships[4].author.id | https://openalex.org/A5041884792 |
| authorships[4].author.orcid | https://orcid.org/0000-0002-2823-0911 |
| authorships[4].author.display_name | Patricia Bouyer |
| authorships[4].author_position | middle |
| authorships[4].raw_author_name | Patricia Bouyer |
| authorships[4].is_corresponding | False |
| authorships[5].author.id | https://openalex.org/A5080843415 |
| authorships[5].author.orcid | https://orcid.org/0000-0003-4014-8248 |
| authorships[5].author.display_name | Anuj Dawar |
| authorships[5].author_position | middle |
| authorships[5].raw_author_name | Anuj Dawar |
| authorships[5].is_corresponding | False |
| authorships[6].author.id | https://openalex.org/A5107904564 |
| authorships[6].author.orcid | |
| authorships[6].author.display_name | Mamadou Moustapha Kanté |
| authorships[6].author_position | last |
| authorships[6].raw_author_name | Mamadou Moustapha Kante |
| authorships[6].is_corresponding | False |
| has_content.pdf | False |
| has_content.grobid_xml | False |
| is_paratext | False |
| open_access.is_oa | True |
| open_access.oa_url | https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.31 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2025-10-10T00:00:00 |
| display_name | Barriers for Faster Dimensionality Reduction |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-11-06T03:46:38.306776 |
| primary_topic.id | https://openalex.org/T12111 |
| primary_topic.field.id | https://openalex.org/fields/22 |
| primary_topic.field.display_name | Engineering |
| primary_topic.score | 0.1868000030517578 |
| primary_topic.domain.id | https://openalex.org/domains/3 |
| primary_topic.domain.display_name | Physical Sciences |
| primary_topic.subfield.id | https://openalex.org/subfields/2209 |
| primary_topic.subfield.display_name | Industrial and Manufacturing Engineering |
| primary_topic.display_name | Industrial Vision Systems and Defect Detection |
| related_works | https://openalex.org/W4386322349, https://openalex.org/W1995622179, https://openalex.org/W1484111231, https://openalex.org/W4391160746, https://openalex.org/W1552543208, https://openalex.org/W2074396517, https://openalex.org/W2166963679, https://openalex.org/W2187269125, https://openalex.org/W1641615907, https://openalex.org/W3089231081 |
| cited_by_count | 0 |
| locations_count | 2 |
| best_oa_location.id | pmh:oai:drops-oai.dagstuhl.de:17683 |
| best_oa_location.is_oa | True |
| best_oa_location.source.id | https://openalex.org/S4306402524 |
| 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 | Leibniz-Zentrum für Informatik (Schloss Dagstuhl) |
| best_oa_location.source.host_organization | https://openalex.org/I2799853480 |
| best_oa_location.source.host_organization_name | Schloss Dagstuhl – Leibniz Center for Informatics |
| best_oa_location.source.host_organization_lineage | https://openalex.org/I2799853480 |
| best_oa_location.license | cc-by |
| best_oa_location.pdf_url | |
| best_oa_location.version | publishedVersion |
| best_oa_location.raw_type | InProceedings |
| best_oa_location.license_id | https://openalex.org/licenses/cc-by |
| best_oa_location.is_accepted | True |
| best_oa_location.is_published | True |
| best_oa_location.raw_source_name | |
| best_oa_location.landing_page_url | https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.31 |
| primary_location.id | pmh:oai:drops-oai.dagstuhl.de:17683 |
| primary_location.is_oa | True |
| primary_location.source.id | https://openalex.org/S4306402524 |
| primary_location.source.issn | |
| primary_location.source.type | repository |
| primary_location.source.is_oa | False |
| primary_location.source.issn_l | |
| primary_location.source.is_core | False |
| primary_location.source.is_in_doaj | False |
| primary_location.source.display_name | Leibniz-Zentrum für Informatik (Schloss Dagstuhl) |
| primary_location.source.host_organization | https://openalex.org/I2799853480 |
| primary_location.source.host_organization_name | Schloss Dagstuhl – Leibniz Center for Informatics |
| primary_location.source.host_organization_lineage | https://openalex.org/I2799853480 |
| primary_location.license | cc-by |
| primary_location.pdf_url | |
| primary_location.version | publishedVersion |
| primary_location.raw_type | InProceedings |
| primary_location.license_id | https://openalex.org/licenses/cc-by |
| primary_location.is_accepted | True |
| primary_location.is_published | True |
| primary_location.raw_source_name | |
| primary_location.landing_page_url | https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.31 |
| publication_date | 2023-01-01 |
| publication_year | 2023 |
| referenced_works_count | 0 |
| abstract_inverted_index.= | 36 |
| abstract_inverted_index.A | 68 |
| abstract_inverted_index.a | 7, 28, 63, 113, 134 |
| abstract_inverted_index.m | 35 |
| abstract_inverted_index.n | 10 |
| abstract_inverted_index.(1 | 30 |
| abstract_inverted_index.In | 118 |
| abstract_inverted_index.JL | 89 |
| abstract_inverted_index.an | 44, 100 |
| abstract_inverted_index.at | 59 |
| abstract_inverted_index.by | 91 |
| abstract_inverted_index.in | 12, 66, 141 |
| abstract_inverted_index.lg | 38, 105, 131 |
| abstract_inverted_index.no | 108 |
| abstract_inverted_index.of | 9, 24, 47, 62, 71, 103, 137 |
| abstract_inverted_index.on | 73, 77 |
| abstract_inverted_index.to | 5, 27, 51 |
| abstract_inverted_index.up | 26, 53 |
| abstract_inverted_index.we | 121 |
| abstract_inverted_index.± | 31 |
| abstract_inverted_index.(of | 128 |
| abstract_inverted_index.All | 95 |
| abstract_inverted_index.The | 0, 40 |
| abstract_inverted_index.and | 55, 93 |
| abstract_inverted_index.any | 22 |
| abstract_inverted_index.but | 107 |
| abstract_inverted_index.d), | 106 |
| abstract_inverted_index.for | 133 |
| abstract_inverted_index.has | 42 |
| abstract_inverted_index.m)) | 132 |
| abstract_inverted_index.n). | 39 |
| abstract_inverted_index.one | 4 |
| abstract_inverted_index.out | 112 |
| abstract_inverted_index.the | 18, 60, 83, 87, 123 |
| abstract_inverted_index.Fast | 88 |
| abstract_inverted_index.O(d) | 115 |
| abstract_inverted_index.fast | 79 |
| abstract_inverted_index.have | 99 |
| abstract_inverted_index.into | 14 |
| abstract_inverted_index.line | 70 |
| abstract_inverted_index.loss | 65 |
| abstract_inverted_index.most | 143 |
| abstract_inverted_index.pair | 23 |
| abstract_inverted_index.rule | 111 |
| abstract_inverted_index.such | 74, 97 |
| abstract_inverted_index.that | 34 |
| abstract_inverted_index.this | 119 |
| abstract_inverted_index.time | 102 |
| abstract_inverted_index.with | 82 |
| abstract_inverted_index.Ω(d | 104 |
| abstract_inverted_index.Ω(m | 130 |
| abstract_inverted_index.ε), | 32 |
| abstract_inverted_index.Ailon | 92 |
| abstract_inverted_index.being | 86 |
| abstract_inverted_index.class | 136 |
| abstract_inverted_index.clean | 114 |
| abstract_inverted_index.embed | 6 |
| abstract_inverted_index.first | 124 |
| abstract_inverted_index.focus | 76 |
| abstract_inverted_index.found | 43 |
| abstract_inverted_index.known | 96, 144 |
| abstract_inverted_index.large | 135 |
| abstract_inverted_index.lower | 109, 126 |
| abstract_inverted_index.price | 61 |
| abstract_inverted_index.small | 64 |
| abstract_inverted_index.speed | 52 |
| abstract_inverted_index.time. | 117 |
| abstract_inverted_index.upper | 145 |
| abstract_inverted_index.while | 16 |
| abstract_inverted_index.work, | 120 |
| abstract_inverted_index.ℝ^d | 13 |
| abstract_inverted_index.allows | 3 |
| abstract_inverted_index.bounds | 110, 127 |
| abstract_inverted_index.factor | 29 |
| abstract_inverted_index.memory | 57 |
| abstract_inverted_index.number | 46 |
| abstract_inverted_index.points | 11, 25 |
| abstract_inverted_index.ℝ^m, | 15 |
| abstract_inverted_index.between | 21 |
| abstract_inverted_index.bounds. | 146 |
| abstract_inverted_index.central | 69 |
| abstract_inverted_index.classic | 84 |
| abstract_inverted_index.dataset | 8 |
| abstract_inverted_index.example | 85 |
| abstract_inverted_index.allowing | 50 |
| abstract_inverted_index.distance | 20 |
| abstract_inverted_index.pairwise | 19 |
| abstract_inverted_index.provided | 33 |
| abstract_inverted_index.reducing | 56 |
| abstract_inverted_index.research | 72 |
| abstract_inverted_index.Chazelle. | 94 |
| abstract_inverted_index.accuracy. | 67 |
| abstract_inverted_index.embedding | 80, 101, 116, 138 |
| abstract_inverted_index.establish | 122 |
| abstract_inverted_index.including | 140 |
| abstract_inverted_index.magnitude | 129 |
| abstract_inverted_index.transform | 2, 41, 90 |
| abstract_inverted_index.algorithms | 54, 98 |
| abstract_inverted_index.developing | 78 |
| abstract_inverted_index.particular | 142 |
| abstract_inverted_index.preserving | 17 |
| abstract_inverted_index.Ω(ε^{-2} | 37 |
| abstract_inverted_index.algorithmic | 48 |
| abstract_inverted_index.algorithms, | 81, 139 |
| abstract_inverted_index.consumption | 58 |
| abstract_inverted_index.non-trivial | 125 |
| abstract_inverted_index.transforms, | 75 |
| abstract_inverted_index.overwhelming | 45 |
| abstract_inverted_index.applications, | 49 |
| abstract_inverted_index.Johnson-Lindenstrauss | 1 |
| cited_by_percentile_year | |
| corresponding_author_ids | https://openalex.org/A5067430268, https://openalex.org/A5013551063, https://openalex.org/A5013947961 |
| countries_distinct_count | 1 |
| institutions_distinct_count | 7 |
| corresponding_institution_ids | https://openalex.org/I204337017 |
| citation_normalized_percentile.value | 0.43808441 |
| citation_normalized_percentile.is_in_top_1_percent | False |
| citation_normalized_percentile.is_in_top_10_percent | False |