Coresets for Clustering in Excluded-minor Graphs and Beyond Article Swipe
Vladimir Braverman
,
Shaofeng H.-C. Jiang
,
Robert Krauthgamer
,
Xuan Wu
·
YOU?
·
· 2021
· Open Access
·
· DOI: https://doi.org/10.1137/1.9781611976465.159
YOU?
·
· 2021
· Open Access
·
· DOI: https://doi.org/10.1137/1.9781611976465.159
Coresets are modern data-reduction tools that are widely used in data analysis to improve efficiency in terms of running time, space and communication complexity. Our main result is a fast algorithm to construct a small coreset for k-Median in (the shortest-path metric of) an excluded-minor graph. Specifically we give the first coreset of size that depends only on k, ∊ and the excluded-minor size, and our running time is quasi-linear (in the size of the input graph).The main innovation in our new algorithm is that is iterative; it first reduces the n input points to roughly O(log n) reweighted points, then to O(log log n), and so forth until the size is independent of n. Each step in this iterative size reduction is based on the importance sampling framework of Feldman and Langberg (STOC 2011), with a crucial adaptation that reduces the number of distinct points, by employing a terminal embedding (where low distortion is guaranteed only for the distance from every terminal to all other points). Our terminal embedding is technically involved and relies on shortest-path separators, a standard tool in planar and excluded-minor graphs.Furthermore, our new algorithm is applicable also in Euclidean metrics, by simply using a recent terminal embedding result of Narayanan and Nelson (STOC 2019), which extends the Johnson-Lindenstrauss Lemma. We thus obtain an efficient coreset construction in high-dimensional Euclidean spaces, thereby matching and simplifying state-of-the-art results (Sohler and Woodruff, FOCS 2018; Huang and Vishnoi, STOC 2020).In addition, we also employ terminal embedding with additive distortion to obtain small coresets in graphs with bounded highway dimension, and use applications of our coresets to obtain improved approximation schemes, e.g., an improved PTAS for planar k-Median via a new centroid set.
Related Topics
Concepts
Metadata
- Type
- book-chapter
- Language
- en
- Landing Page
- https://doi.org/10.1137/1.9781611976465.159
- https://epubs.siam.org/doi/pdf/10.1137/1.9781611976465.159
- OA Status
- bronze
- Cited By
- 18
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W3116773026
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W3116773026Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.1137/1.9781611976465.159Digital Object Identifier
- Title
-
Coresets for Clustering in Excluded-minor Graphs and BeyondWork title
- Type
-
book-chapterOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2021Year of publication
- Publication date
-
2021-01-01Full publication date if available
- Authors
-
Vladimir Braverman, Shaofeng H.-C. Jiang, Robert Krauthgamer, Xuan WuList of authors in order
- Landing page
-
https://doi.org/10.1137/1.9781611976465.159Publisher landing page
- PDF URL
-
https://epubs.siam.org/doi/pdf/10.1137/1.9781611976465.159Direct link to full text PDF
- Open access
-
YesWhether a free full text is available
- OA status
-
bronzeOpen access status per OpenAlex
- OA URL
-
https://epubs.siam.org/doi/pdf/10.1137/1.9781611976465.159Direct OA link when available
- Concepts
-
Combinatorics, Mathematics, Metric space, Embedding, Minor (academic), Discrete mathematics, Binary logarithm, Euclidean geometry, Graph, Shortest path problem, Algorithm, Computer science, Artificial intelligence, Law, Geometry, Political scienceTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
18Total citation count in OpenAlex
- Citations by year (recent)
-
2025: 2, 2024: 5, 2023: 3, 2022: 3, 2021: 4Per-year citation counts (last 5 years)
- Related works (count)
-
10Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W3116773026 |
|---|---|
| doi | https://doi.org/10.1137/1.9781611976465.159 |
| ids.doi | https://doi.org/10.1137/1.9781611976465.159 |
| ids.mag | 3116773026 |
| ids.openalex | https://openalex.org/W3116773026 |
| fwci | 13.72505168 |
| type | book-chapter |
| title | Coresets for Clustering in Excluded-minor Graphs and Beyond |
| biblio.issue | |
| biblio.volume | |
| biblio.last_page | 2696 |
| biblio.first_page | 2679 |
| topics[0].id | https://openalex.org/T13282 |
| topics[0].field.id | https://openalex.org/fields/22 |
| topics[0].field.display_name | Engineering |
| topics[0].score | 0.9732999801635742 |
| topics[0].domain.id | https://openalex.org/domains/3 |
| topics[0].domain.display_name | Physical Sciences |
| topics[0].subfield.id | https://openalex.org/subfields/2212 |
| topics[0].subfield.display_name | Ocean Engineering |
| topics[0].display_name | Automated Road and Building Extraction |
| topics[1].id | https://openalex.org/T11344 |
| topics[1].field.id | https://openalex.org/fields/22 |
| topics[1].field.display_name | Engineering |
| topics[1].score | 0.9491000175476074 |
| topics[1].domain.id | https://openalex.org/domains/3 |
| topics[1].domain.display_name | Physical Sciences |
| topics[1].subfield.id | https://openalex.org/subfields/2215 |
| topics[1].subfield.display_name | Building and Construction |
| topics[1].display_name | Traffic Prediction and Management Techniques |
| topics[2].id | https://openalex.org/T12644 |
| topics[2].field.id | https://openalex.org/fields/23 |
| topics[2].field.display_name | Environmental Science |
| topics[2].score | 0.9449999928474426 |
| topics[2].domain.id | https://openalex.org/domains/3 |
| topics[2].domain.display_name | Physical Sciences |
| topics[2].subfield.id | https://openalex.org/subfields/2303 |
| topics[2].subfield.display_name | Ecology |
| topics[2].display_name | Wildlife-Road Interactions and Conservation |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C114614502 |
| concepts[0].level | 1 |
| concepts[0].score | 0.6412345767021179 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q76592 |
| concepts[0].display_name | Combinatorics |
| concepts[1].id | https://openalex.org/C33923547 |
| concepts[1].level | 0 |
| concepts[1].score | 0.5757443308830261 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q395 |
| concepts[1].display_name | Mathematics |
| concepts[2].id | https://openalex.org/C198043062 |
| concepts[2].level | 2 |
| concepts[2].score | 0.5434648394584656 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q180953 |
| concepts[2].display_name | Metric space |
| concepts[3].id | https://openalex.org/C41608201 |
| concepts[3].level | 2 |
| concepts[3].score | 0.5349835753440857 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q980509 |
| concepts[3].display_name | Embedding |
| concepts[4].id | https://openalex.org/C2779760435 |
| concepts[4].level | 2 |
| concepts[4].score | 0.4906691312789917 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q5396169 |
| concepts[4].display_name | Minor (academic) |
| concepts[5].id | https://openalex.org/C118615104 |
| concepts[5].level | 1 |
| concepts[5].score | 0.4512190520763397 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q121416 |
| concepts[5].display_name | Discrete mathematics |
| concepts[6].id | https://openalex.org/C63553672 |
| concepts[6].level | 2 |
| concepts[6].score | 0.4483194351196289 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q581168 |
| concepts[6].display_name | Binary logarithm |
| concepts[7].id | https://openalex.org/C129782007 |
| concepts[7].level | 2 |
| concepts[7].score | 0.44067564606666565 |
| concepts[7].wikidata | https://www.wikidata.org/wiki/Q162886 |
| concepts[7].display_name | Euclidean geometry |
| concepts[8].id | https://openalex.org/C132525143 |
| concepts[8].level | 2 |
| concepts[8].score | 0.4255460202693939 |
| concepts[8].wikidata | https://www.wikidata.org/wiki/Q141488 |
| concepts[8].display_name | Graph |
| concepts[9].id | https://openalex.org/C22590252 |
| concepts[9].level | 3 |
| concepts[9].score | 0.4164281189441681 |
| concepts[9].wikidata | https://www.wikidata.org/wiki/Q1058754 |
| concepts[9].display_name | Shortest path problem |
| concepts[10].id | https://openalex.org/C11413529 |
| concepts[10].level | 1 |
| concepts[10].score | 0.3938601016998291 |
| concepts[10].wikidata | https://www.wikidata.org/wiki/Q8366 |
| concepts[10].display_name | Algorithm |
| concepts[11].id | https://openalex.org/C41008148 |
| concepts[11].level | 0 |
| concepts[11].score | 0.31386426091194153 |
| concepts[11].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[11].display_name | Computer science |
| concepts[12].id | https://openalex.org/C154945302 |
| concepts[12].level | 1 |
| concepts[12].score | 0.0 |
| concepts[12].wikidata | https://www.wikidata.org/wiki/Q11660 |
| concepts[12].display_name | Artificial intelligence |
| concepts[13].id | https://openalex.org/C199539241 |
| concepts[13].level | 1 |
| concepts[13].score | 0.0 |
| concepts[13].wikidata | https://www.wikidata.org/wiki/Q7748 |
| concepts[13].display_name | Law |
| concepts[14].id | https://openalex.org/C2524010 |
| concepts[14].level | 1 |
| concepts[14].score | 0.0 |
| concepts[14].wikidata | https://www.wikidata.org/wiki/Q8087 |
| concepts[14].display_name | Geometry |
| concepts[15].id | https://openalex.org/C17744445 |
| concepts[15].level | 0 |
| concepts[15].score | 0.0 |
| concepts[15].wikidata | https://www.wikidata.org/wiki/Q36442 |
| concepts[15].display_name | Political science |
| keywords[0].id | https://openalex.org/keywords/combinatorics |
| keywords[0].score | 0.6412345767021179 |
| keywords[0].display_name | Combinatorics |
| keywords[1].id | https://openalex.org/keywords/mathematics |
| keywords[1].score | 0.5757443308830261 |
| keywords[1].display_name | Mathematics |
| keywords[2].id | https://openalex.org/keywords/metric-space |
| keywords[2].score | 0.5434648394584656 |
| keywords[2].display_name | Metric space |
| keywords[3].id | https://openalex.org/keywords/embedding |
| keywords[3].score | 0.5349835753440857 |
| keywords[3].display_name | Embedding |
| keywords[4].id | https://openalex.org/keywords/minor |
| keywords[4].score | 0.4906691312789917 |
| keywords[4].display_name | Minor (academic) |
| keywords[5].id | https://openalex.org/keywords/discrete-mathematics |
| keywords[5].score | 0.4512190520763397 |
| keywords[5].display_name | Discrete mathematics |
| keywords[6].id | https://openalex.org/keywords/binary-logarithm |
| keywords[6].score | 0.4483194351196289 |
| keywords[6].display_name | Binary logarithm |
| keywords[7].id | https://openalex.org/keywords/euclidean-geometry |
| keywords[7].score | 0.44067564606666565 |
| keywords[7].display_name | Euclidean geometry |
| keywords[8].id | https://openalex.org/keywords/graph |
| keywords[8].score | 0.4255460202693939 |
| keywords[8].display_name | Graph |
| keywords[9].id | https://openalex.org/keywords/shortest-path-problem |
| keywords[9].score | 0.4164281189441681 |
| keywords[9].display_name | Shortest path problem |
| keywords[10].id | https://openalex.org/keywords/algorithm |
| keywords[10].score | 0.3938601016998291 |
| keywords[10].display_name | Algorithm |
| keywords[11].id | https://openalex.org/keywords/computer-science |
| keywords[11].score | 0.31386426091194153 |
| keywords[11].display_name | Computer science |
| language | en |
| locations[0].id | doi:10.1137/1.9781611976465.159 |
| locations[0].is_oa | True |
| locations[0].source.id | https://openalex.org/S4306463922 |
| locations[0].source.issn | |
| locations[0].source.type | ebook platform |
| 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 | Society for Industrial and Applied Mathematics eBooks |
| locations[0].source.host_organization | https://openalex.org/P4310320508 |
| locations[0].source.host_organization_name | Society for Industrial and Applied Mathematics |
| locations[0].source.host_organization_lineage | https://openalex.org/P4310320508 |
| locations[0].source.host_organization_lineage_names | Society for Industrial and Applied Mathematics |
| locations[0].license | |
| locations[0].pdf_url | https://epubs.siam.org/doi/pdf/10.1137/1.9781611976465.159 |
| locations[0].version | publishedVersion |
| locations[0].raw_type | book-chapter |
| locations[0].license_id | |
| locations[0].is_accepted | True |
| locations[0].is_published | True |
| locations[0].raw_source_name | Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA) |
| locations[0].landing_page_url | https://doi.org/10.1137/1.9781611976465.159 |
| indexed_in | crossref |
| authorships[0].author.id | https://openalex.org/A5053736722 |
| authorships[0].author.orcid | https://orcid.org/0000-0001-7709-8753 |
| authorships[0].author.display_name | Vladimir Braverman |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Vladimir Braverman |
| authorships[0].is_corresponding | False |
| authorships[1].author.id | https://openalex.org/A5063670809 |
| authorships[1].author.orcid | https://orcid.org/0000-0001-7972-827X |
| authorships[1].author.display_name | Shaofeng H.-C. Jiang |
| authorships[1].author_position | middle |
| authorships[1].raw_author_name | Shaofeng H.-C. Jiang |
| authorships[1].is_corresponding | False |
| authorships[2].author.id | https://openalex.org/A5037378898 |
| authorships[2].author.orcid | https://orcid.org/0009-0003-8154-3735 |
| authorships[2].author.display_name | Robert Krauthgamer |
| authorships[2].author_position | middle |
| authorships[2].raw_author_name | Robert Krauthgamer |
| authorships[2].is_corresponding | False |
| authorships[3].author.id | https://openalex.org/A5101941388 |
| authorships[3].author.orcid | https://orcid.org/0000-0001-8031-4154 |
| authorships[3].author.display_name | Xuan Wu |
| authorships[3].author_position | last |
| authorships[3].raw_author_name | Xuan Wu |
| authorships[3].is_corresponding | False |
| has_content.pdf | True |
| has_content.grobid_xml | True |
| is_paratext | False |
| open_access.is_oa | True |
| open_access.oa_url | https://epubs.siam.org/doi/pdf/10.1137/1.9781611976465.159 |
| open_access.oa_status | bronze |
| open_access.any_repository_has_fulltext | False |
| created_date | 2025-10-10T00:00:00 |
| display_name | Coresets for Clustering in Excluded-minor Graphs and Beyond |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-11-06T03:46:38.306776 |
| primary_topic.id | https://openalex.org/T13282 |
| primary_topic.field.id | https://openalex.org/fields/22 |
| primary_topic.field.display_name | Engineering |
| primary_topic.score | 0.9732999801635742 |
| primary_topic.domain.id | https://openalex.org/domains/3 |
| primary_topic.domain.display_name | Physical Sciences |
| primary_topic.subfield.id | https://openalex.org/subfields/2212 |
| primary_topic.subfield.display_name | Ocean Engineering |
| primary_topic.display_name | Automated Road and Building Extraction |
| related_works | https://openalex.org/W2368619281, https://openalex.org/W2377143628, https://openalex.org/W2355995962, https://openalex.org/W2392462513, https://openalex.org/W2362718971, https://openalex.org/W2368173763, https://openalex.org/W2977970519, https://openalex.org/W191560551, https://openalex.org/W2075931614, https://openalex.org/W2391618338 |
| cited_by_count | 18 |
| counts_by_year[0].year | 2025 |
| counts_by_year[0].cited_by_count | 2 |
| counts_by_year[1].year | 2024 |
| counts_by_year[1].cited_by_count | 5 |
| counts_by_year[2].year | 2023 |
| counts_by_year[2].cited_by_count | 3 |
| counts_by_year[3].year | 2022 |
| counts_by_year[3].cited_by_count | 3 |
| counts_by_year[4].year | 2021 |
| counts_by_year[4].cited_by_count | 4 |
| counts_by_year[5].year | 2020 |
| counts_by_year[5].cited_by_count | 1 |
| locations_count | 1 |
| best_oa_location.id | doi:10.1137/1.9781611976465.159 |
| best_oa_location.is_oa | True |
| best_oa_location.source.id | https://openalex.org/S4306463922 |
| best_oa_location.source.issn | |
| best_oa_location.source.type | ebook platform |
| 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 | Society for Industrial and Applied Mathematics eBooks |
| best_oa_location.source.host_organization | https://openalex.org/P4310320508 |
| best_oa_location.source.host_organization_name | Society for Industrial and Applied Mathematics |
| best_oa_location.source.host_organization_lineage | https://openalex.org/P4310320508 |
| best_oa_location.source.host_organization_lineage_names | Society for Industrial and Applied Mathematics |
| best_oa_location.license | |
| best_oa_location.pdf_url | https://epubs.siam.org/doi/pdf/10.1137/1.9781611976465.159 |
| best_oa_location.version | publishedVersion |
| best_oa_location.raw_type | book-chapter |
| best_oa_location.license_id | |
| best_oa_location.is_accepted | True |
| best_oa_location.is_published | True |
| best_oa_location.raw_source_name | Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA) |
| best_oa_location.landing_page_url | https://doi.org/10.1137/1.9781611976465.159 |
| primary_location.id | doi:10.1137/1.9781611976465.159 |
| primary_location.is_oa | True |
| primary_location.source.id | https://openalex.org/S4306463922 |
| primary_location.source.issn | |
| primary_location.source.type | ebook platform |
| 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 | Society for Industrial and Applied Mathematics eBooks |
| primary_location.source.host_organization | https://openalex.org/P4310320508 |
| primary_location.source.host_organization_name | Society for Industrial and Applied Mathematics |
| primary_location.source.host_organization_lineage | https://openalex.org/P4310320508 |
| primary_location.source.host_organization_lineage_names | Society for Industrial and Applied Mathematics |
| primary_location.license | |
| primary_location.pdf_url | https://epubs.siam.org/doi/pdf/10.1137/1.9781611976465.159 |
| primary_location.version | publishedVersion |
| primary_location.raw_type | book-chapter |
| primary_location.license_id | |
| primary_location.is_accepted | True |
| primary_location.is_published | True |
| primary_location.raw_source_name | Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA) |
| primary_location.landing_page_url | https://doi.org/10.1137/1.9781611976465.159 |
| publication_date | 2021-01-01 |
| publication_year | 2021 |
| referenced_works_count | 0 |
| abstract_inverted_index.a | 28, 33, 136, 148, 178, 198, 279 |
| abstract_inverted_index.n | 91 |
| abstract_inverted_index.We | 214 |
| abstract_inverted_index.an | 43, 217, 272 |
| abstract_inverted_index.by | 146, 195 |
| abstract_inverted_index.in | 9, 15, 38, 79, 117, 181, 192, 221, 254 |
| abstract_inverted_index.is | 27, 68, 83, 85, 111, 122, 154, 170, 189 |
| abstract_inverted_index.it | 87 |
| abstract_inverted_index.k, | 58 |
| abstract_inverted_index.n) | 97 |
| abstract_inverted_index.n. | 114 |
| abstract_inverted_index.of | 17, 52, 73, 113, 129, 143, 203, 263 |
| abstract_inverted_index.on | 57, 124, 175 |
| abstract_inverted_index.so | 106 |
| abstract_inverted_index.to | 12, 31, 94, 101, 163, 250, 266 |
| abstract_inverted_index.we | 47, 242 |
| abstract_inverted_index.(in | 70 |
| abstract_inverted_index.Our | 24, 167 |
| abstract_inverted_index.all | 164 |
| abstract_inverted_index.and | 21, 60, 64, 105, 131, 173, 183, 205, 227, 232, 237, 260 |
| abstract_inverted_index.are | 1, 6 |
| abstract_inverted_index.for | 36, 157, 275 |
| abstract_inverted_index.log | 103 |
| abstract_inverted_index.low | 152 |
| abstract_inverted_index.n), | 104 |
| abstract_inverted_index.new | 81, 187, 280 |
| abstract_inverted_index.of) | 42 |
| abstract_inverted_index.our | 65, 80, 186, 264 |
| abstract_inverted_index.the | 49, 61, 71, 74, 90, 109, 125, 141, 158, 211 |
| abstract_inverted_index.use | 261 |
| abstract_inverted_index.via | 278 |
| abstract_inverted_index.∊ | 59 |
| abstract_inverted_index.(the | 39 |
| abstract_inverted_index.Each | 115 |
| abstract_inverted_index.FOCS | 234 |
| abstract_inverted_index.PTAS | 274 |
| abstract_inverted_index.STOC | 239 |
| abstract_inverted_index.also | 191, 243 |
| abstract_inverted_index.data | 10 |
| abstract_inverted_index.fast | 29 |
| abstract_inverted_index.from | 160 |
| abstract_inverted_index.give | 48 |
| abstract_inverted_index.main | 25, 77 |
| abstract_inverted_index.only | 56, 156 |
| abstract_inverted_index.set. | 282 |
| abstract_inverted_index.size | 53, 72, 110, 120 |
| abstract_inverted_index.step | 116 |
| abstract_inverted_index.that | 5, 54, 84, 139 |
| abstract_inverted_index.then | 100 |
| abstract_inverted_index.this | 118 |
| abstract_inverted_index.thus | 215 |
| abstract_inverted_index.time | 67 |
| abstract_inverted_index.tool | 180 |
| abstract_inverted_index.used | 8 |
| abstract_inverted_index.with | 135, 247, 256 |
| abstract_inverted_index.(STOC | 133, 207 |
| abstract_inverted_index.2018; | 235 |
| abstract_inverted_index.Huang | 236 |
| abstract_inverted_index.O(log | 96, 102 |
| abstract_inverted_index.based | 123 |
| abstract_inverted_index.e.g., | 271 |
| abstract_inverted_index.every | 161 |
| abstract_inverted_index.first | 50, 88 |
| abstract_inverted_index.forth | 107 |
| abstract_inverted_index.input | 75, 92 |
| abstract_inverted_index.other | 165 |
| abstract_inverted_index.size, | 63 |
| abstract_inverted_index.small | 34, 252 |
| abstract_inverted_index.space | 20 |
| abstract_inverted_index.terms | 16 |
| abstract_inverted_index.time, | 19 |
| abstract_inverted_index.tools | 4 |
| abstract_inverted_index.until | 108 |
| abstract_inverted_index.using | 197 |
| abstract_inverted_index.which | 209 |
| abstract_inverted_index.(where | 151 |
| abstract_inverted_index.2011), | 134 |
| abstract_inverted_index.2019), | 208 |
| abstract_inverted_index.Lemma. | 213 |
| abstract_inverted_index.Nelson | 206 |
| abstract_inverted_index.employ | 244 |
| abstract_inverted_index.graph. | 45 |
| abstract_inverted_index.graphs | 255 |
| abstract_inverted_index.metric | 41 |
| abstract_inverted_index.modern | 2 |
| abstract_inverted_index.number | 142 |
| abstract_inverted_index.obtain | 216, 251, 267 |
| abstract_inverted_index.planar | 182, 276 |
| abstract_inverted_index.points | 93 |
| abstract_inverted_index.recent | 199 |
| abstract_inverted_index.relies | 174 |
| abstract_inverted_index.result | 26, 202 |
| abstract_inverted_index.simply | 196 |
| abstract_inverted_index.widely | 7 |
| abstract_inverted_index.(Sohler | 231 |
| abstract_inverted_index.Feldman | 130 |
| abstract_inverted_index.bounded | 257 |
| abstract_inverted_index.coreset | 35, 51, 219 |
| abstract_inverted_index.crucial | 137 |
| abstract_inverted_index.depends | 55 |
| abstract_inverted_index.extends | 210 |
| abstract_inverted_index.highway | 258 |
| abstract_inverted_index.improve | 13 |
| abstract_inverted_index.points, | 99, 145 |
| abstract_inverted_index.reduces | 89, 140 |
| abstract_inverted_index.results | 230 |
| abstract_inverted_index.roughly | 95 |
| abstract_inverted_index.running | 18, 66 |
| abstract_inverted_index.spaces, | 224 |
| abstract_inverted_index.thereby | 225 |
| abstract_inverted_index.2020).In | 240 |
| abstract_inverted_index.Coresets | 0 |
| abstract_inverted_index.Langberg | 132 |
| abstract_inverted_index.Vishnoi, | 238 |
| abstract_inverted_index.additive | 248 |
| abstract_inverted_index.analysis | 11 |
| abstract_inverted_index.centroid | 281 |
| abstract_inverted_index.coresets | 253, 265 |
| abstract_inverted_index.distance | 159 |
| abstract_inverted_index.distinct | 144 |
| abstract_inverted_index.improved | 268, 273 |
| abstract_inverted_index.involved | 172 |
| abstract_inverted_index.k-Median | 37, 277 |
| abstract_inverted_index.matching | 226 |
| abstract_inverted_index.metrics, | 194 |
| abstract_inverted_index.points). | 166 |
| abstract_inverted_index.sampling | 127 |
| abstract_inverted_index.schemes, | 270 |
| abstract_inverted_index.standard | 179 |
| abstract_inverted_index.terminal | 149, 162, 168, 200, 245 |
| abstract_inverted_index.Euclidean | 193, 223 |
| abstract_inverted_index.Narayanan | 204 |
| abstract_inverted_index.Woodruff, | 233 |
| abstract_inverted_index.addition, | 241 |
| abstract_inverted_index.algorithm | 30, 82, 188 |
| abstract_inverted_index.construct | 32 |
| abstract_inverted_index.efficient | 218 |
| abstract_inverted_index.embedding | 150, 169, 201, 246 |
| abstract_inverted_index.employing | 147 |
| abstract_inverted_index.framework | 128 |
| abstract_inverted_index.iterative | 119 |
| abstract_inverted_index.reduction | 121 |
| abstract_inverted_index.adaptation | 138 |
| abstract_inverted_index.applicable | 190 |
| abstract_inverted_index.dimension, | 259 |
| abstract_inverted_index.distortion | 153, 249 |
| abstract_inverted_index.efficiency | 14 |
| abstract_inverted_index.graph).The | 76 |
| abstract_inverted_index.guaranteed | 155 |
| abstract_inverted_index.importance | 126 |
| abstract_inverted_index.innovation | 78 |
| abstract_inverted_index.iterative; | 86 |
| abstract_inverted_index.reweighted | 98 |
| abstract_inverted_index.complexity. | 23 |
| abstract_inverted_index.independent | 112 |
| abstract_inverted_index.separators, | 177 |
| abstract_inverted_index.simplifying | 228 |
| abstract_inverted_index.technically | 171 |
| abstract_inverted_index.Specifically | 46 |
| abstract_inverted_index.applications | 262 |
| abstract_inverted_index.construction | 220 |
| abstract_inverted_index.quasi-linear | 69 |
| abstract_inverted_index.approximation | 269 |
| abstract_inverted_index.communication | 22 |
| abstract_inverted_index.shortest-path | 40, 176 |
| abstract_inverted_index.data-reduction | 3 |
| abstract_inverted_index.excluded-minor | 44, 62, 184 |
| abstract_inverted_index.high-dimensional | 222 |
| abstract_inverted_index.state-of-the-art | 229 |
| abstract_inverted_index.graphs.Furthermore, | 185 |
| abstract_inverted_index.Johnson-Lindenstrauss | 212 |
| cited_by_percentile_year.max | 98 |
| cited_by_percentile_year.min | 89 |
| countries_distinct_count | 0 |
| institutions_distinct_count | 4 |
| sustainable_development_goals[0].id | https://metadata.un.org/sdg/9 |
| sustainable_development_goals[0].score | 0.6499999761581421 |
| sustainable_development_goals[0].display_name | Industry, innovation and infrastructure |
| citation_normalized_percentile.value | 0.99307075 |
| citation_normalized_percentile.is_in_top_1_percent | True |
| citation_normalized_percentile.is_in_top_10_percent | True |