Clustering Under Perturbation Stability in Near-Linear Time Article Swipe
Pankaj K. Agarwal
,
Hsien-Chih Chang
,
Kamesh Munagala
,
Erin Taylor
,
Emo Welzl
·
YOU?
·
· 2020
· Open Access
·
· DOI: https://doi.org/10.4230/lipics.fsttcs.2020.8
YOU?
·
· 2020
· Open Access
·
· DOI: https://doi.org/10.4230/lipics.fsttcs.2020.8
We consider the problem of center-based clustering in low-dimensional Euclidean spaces under the perturbation stability assumption. An instance is α-stable if the underlying optimal clustering continues to remain optimal even when all pairwise distances are arbitrarily perturbed by a factor of at most α. Our main contribution is in presenting efficient exact algorithms for α-stable clustering instances whose running times depend near-linearly on the size of the data set when α ≥ 2 + √3. For k-center and k-means problems, our algorithms also achieve polynomial dependence on the number of clusters, k, when α ≥ 2 + √3 + ε for any constant ε > 0 in any fixed dimension. For k-median, our algorithms have polynomial dependence on k for α > 5 in any fixed dimension; and for α ≥ 2 + √3 in two dimensions. Our algorithms are simple, and only require applying techniques such as local search or dynamic programming to a suitably modified metric space, combined with careful choice of data structures.
Related Topics
Concepts
Metadata
- Type
- preprint
- Language
- en
- Landing Page
- https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2020.8
- OA Status
- green
- Cited By
- 1
- References
- 55
- Related Works
- 20
- OpenAlex ID
- https://openalex.org/W3090987474
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W3090987474Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.4230/lipics.fsttcs.2020.8Digital Object Identifier
- Title
-
Clustering Under Perturbation Stability in Near-Linear TimeWork title
- Type
-
preprintOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2020Year of publication
- Publication date
-
2020-01-01Full publication date if available
- Authors
-
Pankaj K. Agarwal, Hsien-Chih Chang, Kamesh Munagala, Erin Taylor, Emo WelzlList of authors in order
- Landing page
-
https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2020.8Publisher 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.FSTTCS.2020.8Direct OA link when available
- Concepts
-
Cluster analysis, Combinatorics, Mathematics, Time complexity, Euclidean space, Metric space, Dimension (graph theory), Perturbation (astronomy), Pairwise comparison, Euclidean geometry, Discrete mathematics, Physics, Geometry, Statistics, Quantum mechanicsTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
1Total citation count in OpenAlex
- Citations by year (recent)
-
2024: 1Per-year citation counts (last 5 years)
- References (count)
-
55Number of works referenced by this work
- Related works (count)
-
20Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W3090987474 |
|---|---|
| doi | https://doi.org/10.4230/lipics.fsttcs.2020.8 |
| ids.doi | https://doi.org/10.3929/ethz-b-000465026 |
| ids.mag | 3090987474 |
| ids.openalex | https://openalex.org/W3090987474 |
| fwci | 0.0 |
| type | preprint |
| title | Clustering Under Perturbation Stability in Near-Linear Time |
| biblio.issue | |
| biblio.volume | |
| biblio.last_page | |
| biblio.first_page | |
| topics[0].id | https://openalex.org/T10996 |
| topics[0].field.id | https://openalex.org/fields/17 |
| topics[0].field.display_name | Computer Science |
| topics[0].score | 0.9998000264167786 |
| topics[0].domain.id | https://openalex.org/domains/3 |
| topics[0].domain.display_name | Physical Sciences |
| topics[0].subfield.id | https://openalex.org/subfields/1704 |
| topics[0].subfield.display_name | Computer Graphics and Computer-Aided Design |
| topics[0].display_name | Computational Geometry and Mesh Generation |
| 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.9970999956130981 |
| 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/T11502 |
| topics[2].field.id | https://openalex.org/fields/14 |
| topics[2].field.display_name | Business, Management and Accounting |
| topics[2].score | 0.9961000084877014 |
| topics[2].domain.id | https://openalex.org/domains/2 |
| topics[2].domain.display_name | Social Sciences |
| topics[2].subfield.id | https://openalex.org/subfields/1407 |
| topics[2].subfield.display_name | Organizational Behavior and Human Resource Management |
| topics[2].display_name | Facility Location and Emergency Management |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C73555534 |
| concepts[0].level | 2 |
| concepts[0].score | 0.708193838596344 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q622825 |
| concepts[0].display_name | Cluster analysis |
| concepts[1].id | https://openalex.org/C114614502 |
| concepts[1].level | 1 |
| concepts[1].score | 0.6256420612335205 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q76592 |
| concepts[1].display_name | Combinatorics |
| concepts[2].id | https://openalex.org/C33923547 |
| concepts[2].level | 0 |
| concepts[2].score | 0.6209467053413391 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q395 |
| concepts[2].display_name | Mathematics |
| concepts[3].id | https://openalex.org/C311688 |
| concepts[3].level | 2 |
| concepts[3].score | 0.5645636320114136 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q2393193 |
| concepts[3].display_name | Time complexity |
| concepts[4].id | https://openalex.org/C186450821 |
| concepts[4].level | 2 |
| concepts[4].score | 0.5485756993293762 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q17295 |
| concepts[4].display_name | Euclidean space |
| concepts[5].id | https://openalex.org/C198043062 |
| concepts[5].level | 2 |
| concepts[5].score | 0.5379617214202881 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q180953 |
| concepts[5].display_name | Metric space |
| concepts[6].id | https://openalex.org/C33676613 |
| concepts[6].level | 2 |
| concepts[6].score | 0.5140934586524963 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q13415176 |
| concepts[6].display_name | Dimension (graph theory) |
| concepts[7].id | https://openalex.org/C177918212 |
| concepts[7].level | 2 |
| concepts[7].score | 0.4895840585231781 |
| concepts[7].wikidata | https://www.wikidata.org/wiki/Q803623 |
| concepts[7].display_name | Perturbation (astronomy) |
| concepts[8].id | https://openalex.org/C184898388 |
| concepts[8].level | 2 |
| concepts[8].score | 0.4866503179073334 |
| concepts[8].wikidata | https://www.wikidata.org/wiki/Q1435712 |
| concepts[8].display_name | Pairwise comparison |
| concepts[9].id | https://openalex.org/C129782007 |
| concepts[9].level | 2 |
| concepts[9].score | 0.4358506500720978 |
| concepts[9].wikidata | https://www.wikidata.org/wiki/Q162886 |
| concepts[9].display_name | Euclidean geometry |
| concepts[10].id | https://openalex.org/C118615104 |
| concepts[10].level | 1 |
| concepts[10].score | 0.4009944498538971 |
| concepts[10].wikidata | https://www.wikidata.org/wiki/Q121416 |
| concepts[10].display_name | Discrete mathematics |
| concepts[11].id | https://openalex.org/C121332964 |
| concepts[11].level | 0 |
| concepts[11].score | 0.1313876509666443 |
| concepts[11].wikidata | https://www.wikidata.org/wiki/Q413 |
| concepts[11].display_name | Physics |
| concepts[12].id | https://openalex.org/C2524010 |
| concepts[12].level | 1 |
| concepts[12].score | 0.07870206236839294 |
| concepts[12].wikidata | https://www.wikidata.org/wiki/Q8087 |
| concepts[12].display_name | Geometry |
| concepts[13].id | https://openalex.org/C105795698 |
| concepts[13].level | 1 |
| concepts[13].score | 0.06967395544052124 |
| concepts[13].wikidata | https://www.wikidata.org/wiki/Q12483 |
| concepts[13].display_name | Statistics |
| concepts[14].id | https://openalex.org/C62520636 |
| concepts[14].level | 1 |
| concepts[14].score | 0.0 |
| concepts[14].wikidata | https://www.wikidata.org/wiki/Q944 |
| concepts[14].display_name | Quantum mechanics |
| keywords[0].id | https://openalex.org/keywords/cluster-analysis |
| keywords[0].score | 0.708193838596344 |
| keywords[0].display_name | Cluster analysis |
| keywords[1].id | https://openalex.org/keywords/combinatorics |
| keywords[1].score | 0.6256420612335205 |
| keywords[1].display_name | Combinatorics |
| keywords[2].id | https://openalex.org/keywords/mathematics |
| keywords[2].score | 0.6209467053413391 |
| keywords[2].display_name | Mathematics |
| keywords[3].id | https://openalex.org/keywords/time-complexity |
| keywords[3].score | 0.5645636320114136 |
| keywords[3].display_name | Time complexity |
| keywords[4].id | https://openalex.org/keywords/euclidean-space |
| keywords[4].score | 0.5485756993293762 |
| keywords[4].display_name | Euclidean space |
| keywords[5].id | https://openalex.org/keywords/metric-space |
| keywords[5].score | 0.5379617214202881 |
| keywords[5].display_name | Metric space |
| keywords[6].id | https://openalex.org/keywords/dimension |
| keywords[6].score | 0.5140934586524963 |
| keywords[6].display_name | Dimension (graph theory) |
| keywords[7].id | https://openalex.org/keywords/perturbation |
| keywords[7].score | 0.4895840585231781 |
| keywords[7].display_name | Perturbation (astronomy) |
| keywords[8].id | https://openalex.org/keywords/pairwise-comparison |
| keywords[8].score | 0.4866503179073334 |
| keywords[8].display_name | Pairwise comparison |
| keywords[9].id | https://openalex.org/keywords/euclidean-geometry |
| keywords[9].score | 0.4358506500720978 |
| keywords[9].display_name | Euclidean geometry |
| keywords[10].id | https://openalex.org/keywords/discrete-mathematics |
| keywords[10].score | 0.4009944498538971 |
| keywords[10].display_name | Discrete mathematics |
| keywords[11].id | https://openalex.org/keywords/physics |
| keywords[11].score | 0.1313876509666443 |
| keywords[11].display_name | Physics |
| keywords[12].id | https://openalex.org/keywords/geometry |
| keywords[12].score | 0.07870206236839294 |
| keywords[12].display_name | Geometry |
| keywords[13].id | https://openalex.org/keywords/statistics |
| keywords[13].score | 0.06967395544052124 |
| keywords[13].display_name | Statistics |
| language | en |
| locations[0].id | pmh:oai:drops-oai.dagstuhl.de:13249 |
| 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.FSTTCS.2020.8 |
| locations[1].id | pmh:oai:research-collection.ethz.ch:20.500.11850/465026 |
| locations[1].is_oa | True |
| locations[1].source | |
| locations[1].license | cc-by |
| locations[1].pdf_url | |
| locations[1].version | publishedVersion |
| locations[1].raw_type | info:eu-repo/semantics/publishedVersion |
| locations[1].license_id | https://openalex.org/licenses/cc-by |
| locations[1].is_accepted | True |
| locations[1].is_published | True |
| locations[1].raw_source_name | 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020) |
| locations[1].landing_page_url | http://hdl.handle.net/20.500.11850/465026 |
| locations[2].id | pmh:oai:arXiv.org:2009.14358 |
| locations[2].is_oa | True |
| locations[2].source.id | https://openalex.org/S4306400194 |
| locations[2].source.issn | |
| locations[2].source.type | repository |
| locations[2].source.is_oa | True |
| locations[2].source.issn_l | |
| locations[2].source.is_core | False |
| locations[2].source.is_in_doaj | False |
| locations[2].source.display_name | arXiv (Cornell University) |
| locations[2].source.host_organization | https://openalex.org/I205783295 |
| locations[2].source.host_organization_name | Cornell University |
| locations[2].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[2].license | |
| locations[2].pdf_url | https://arxiv.org/pdf/2009.14358 |
| locations[2].version | submittedVersion |
| locations[2].raw_type | text |
| locations[2].license_id | |
| locations[2].is_accepted | False |
| locations[2].is_published | False |
| locations[2].raw_source_name | |
| locations[2].landing_page_url | http://arxiv.org/abs/2009.14358 |
| locations[3].id | mag:3090987474 |
| locations[3].is_oa | True |
| locations[3].source.id | https://openalex.org/S4306400194 |
| locations[3].source.issn | |
| locations[3].source.type | repository |
| locations[3].source.is_oa | True |
| locations[3].source.issn_l | |
| locations[3].source.is_core | False |
| locations[3].source.is_in_doaj | False |
| locations[3].source.display_name | arXiv (Cornell University) |
| locations[3].source.host_organization | https://openalex.org/I205783295 |
| locations[3].source.host_organization_name | Cornell University |
| locations[3].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[3].license | |
| locations[3].pdf_url | |
| locations[3].version | submittedVersion |
| locations[3].raw_type | |
| locations[3].license_id | |
| locations[3].is_accepted | False |
| locations[3].is_published | False |
| locations[3].raw_source_name | arXiv (Cornell University) |
| locations[3].landing_page_url | http://export.arxiv.org/pdf/2009.14358 |
| locations[4].id | doi:10.48550/arxiv.2009.14358 |
| locations[4].is_oa | True |
| locations[4].source.id | https://openalex.org/S4306400194 |
| locations[4].source.issn | |
| locations[4].source.type | repository |
| locations[4].source.is_oa | True |
| locations[4].source.issn_l | |
| locations[4].source.is_core | False |
| locations[4].source.is_in_doaj | False |
| locations[4].source.display_name | arXiv (Cornell University) |
| locations[4].source.host_organization | https://openalex.org/I205783295 |
| locations[4].source.host_organization_name | Cornell University |
| locations[4].source.host_organization_lineage | https://openalex.org/I205783295 |
| locations[4].license | |
| locations[4].pdf_url | |
| locations[4].version | |
| locations[4].raw_type | article |
| locations[4].license_id | |
| locations[4].is_accepted | False |
| locations[4].is_published | |
| locations[4].raw_source_name | |
| locations[4].landing_page_url | https://doi.org/10.48550/arxiv.2009.14358 |
| locations[5].id | doi:10.3929/ethz-b-000465026 |
| locations[5].is_oa | True |
| locations[5].source.id | https://openalex.org/S7407051236 |
| locations[5].source.type | repository |
| locations[5].source.is_oa | False |
| locations[5].source.issn_l | |
| locations[5].source.is_core | False |
| locations[5].source.is_in_doaj | False |
| locations[5].source.display_name | ETH Zürich Research Collection |
| locations[5].source.host_organization | |
| locations[5].source.host_organization_name | |
| locations[5].license | cc-by |
| locations[5].pdf_url | |
| locations[5].version | |
| locations[5].raw_type | article-journal |
| locations[5].license_id | https://openalex.org/licenses/cc-by |
| locations[5].is_accepted | False |
| locations[5].is_published | |
| locations[5].raw_source_name | |
| locations[5].landing_page_url | https://doi.org/10.3929/ethz-b-000465026 |
| locations[6].id | doi:10.4230/lipics.fsttcs.2020.8 |
| locations[6].is_oa | True |
| locations[6].source.id | https://openalex.org/S7407052059 |
| locations[6].source.type | repository |
| locations[6].source.is_oa | False |
| locations[6].source.issn_l | |
| locations[6].source.is_core | False |
| locations[6].source.is_in_doaj | False |
| locations[6].source.display_name | Dagstuhl Research Online Publication Server |
| locations[6].source.host_organization | |
| locations[6].source.host_organization_name | |
| locations[6].license | cc-by |
| locations[6].pdf_url | |
| locations[6].version | |
| locations[6].raw_type | |
| locations[6].license_id | https://openalex.org/licenses/cc-by |
| locations[6].is_accepted | False |
| locations[6].is_published | |
| locations[6].raw_source_name | |
| locations[6].landing_page_url | https://doi.org/10.4230/lipics.fsttcs.2020.8 |
| locations[7].id | mag:3113827893 |
| locations[7].is_oa | False |
| locations[7].source.id | https://openalex.org/S4306418453 |
| locations[7].source.issn | |
| locations[7].source.type | conference |
| locations[7].source.is_oa | False |
| locations[7].source.issn_l | |
| locations[7].source.is_core | False |
| locations[7].source.is_in_doaj | False |
| locations[7].source.display_name | Foundations of Software Technology and Theoretical Computer Science |
| locations[7].source.host_organization | |
| locations[7].source.host_organization_name | |
| locations[7].license | |
| locations[7].pdf_url | |
| locations[7].version | |
| locations[7].raw_type | |
| locations[7].license_id | |
| locations[7].is_accepted | False |
| locations[7].is_published | |
| locations[7].raw_source_name | Foundations of Software Technology and Theoretical Computer Science |
| locations[7].landing_page_url | http://dblp.uni-trier.de/db/journals/corr/corr2009.html#abs-2009-14358 |
| indexed_in | arxiv, datacite |
| authorships[0].author.id | https://openalex.org/A5058649592 |
| authorships[0].author.orcid | https://orcid.org/0000-0002-9439-181X |
| authorships[0].author.display_name | Pankaj K. Agarwal |
| authorships[0].countries | US |
| authorships[0].affiliations[0].institution_ids | https://openalex.org/I170897317 |
| authorships[0].affiliations[0].raw_affiliation_string | Duke University, Durham, United States |
| authorships[0].institutions[0].id | https://openalex.org/I170897317 |
| authorships[0].institutions[0].ror | https://ror.org/00py81415 |
| authorships[0].institutions[0].type | education |
| authorships[0].institutions[0].lineage | https://openalex.org/I170897317 |
| authorships[0].institutions[0].country_code | US |
| authorships[0].institutions[0].display_name | Duke University |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Pankaj K. Agarwal |
| authorships[0].is_corresponding | False |
| authorships[0].raw_affiliation_strings | Duke University, Durham, United States |
| authorships[1].author.id | https://openalex.org/A5003923315 |
| authorships[1].author.orcid | https://orcid.org/0000-0001-6714-7988 |
| authorships[1].author.display_name | Hsien-Chih Chang |
| authorships[1].countries | US |
| authorships[1].affiliations[0].institution_ids | https://openalex.org/I170897317 |
| authorships[1].affiliations[0].raw_affiliation_string | Duke University, Durham, United States |
| authorships[1].institutions[0].id | https://openalex.org/I170897317 |
| authorships[1].institutions[0].ror | https://ror.org/00py81415 |
| authorships[1].institutions[0].type | education |
| authorships[1].institutions[0].lineage | https://openalex.org/I170897317 |
| authorships[1].institutions[0].country_code | US |
| authorships[1].institutions[0].display_name | Duke University |
| authorships[1].author_position | middle |
| authorships[1].raw_author_name | Hsien-Chih Chang |
| authorships[1].is_corresponding | False |
| authorships[1].raw_affiliation_strings | Duke University, Durham, United States |
| authorships[2].author.id | https://openalex.org/A5047351951 |
| authorships[2].author.orcid | https://orcid.org/0000-0003-2636-9650 |
| authorships[2].author.display_name | Kamesh Munagala |
| authorships[2].countries | US |
| authorships[2].affiliations[0].institution_ids | https://openalex.org/I205783295 |
| authorships[2].affiliations[0].raw_affiliation_string | Cornell University, Ithaca, United States |
| authorships[2].institutions[0].id | https://openalex.org/I205783295 |
| authorships[2].institutions[0].ror | https://ror.org/05bnh6r87 |
| authorships[2].institutions[0].type | education |
| authorships[2].institutions[0].lineage | https://openalex.org/I205783295 |
| authorships[2].institutions[0].country_code | US |
| authorships[2].institutions[0].display_name | Cornell University |
| authorships[2].author_position | middle |
| authorships[2].raw_author_name | Kamesh Munagala |
| authorships[2].is_corresponding | False |
| authorships[2].raw_affiliation_strings | Cornell University, Ithaca, United States |
| authorships[3].author.id | https://openalex.org/A5103187061 |
| authorships[3].author.orcid | https://orcid.org/0009-0009-3797-4419 |
| authorships[3].author.display_name | Erin Taylor |
| authorships[3].countries | US |
| authorships[3].affiliations[0].institution_ids | https://openalex.org/I170897317 |
| authorships[3].affiliations[0].raw_affiliation_string | Duke University, Durham, United States |
| authorships[3].institutions[0].id | https://openalex.org/I170897317 |
| authorships[3].institutions[0].ror | https://ror.org/00py81415 |
| authorships[3].institutions[0].type | education |
| authorships[3].institutions[0].lineage | https://openalex.org/I170897317 |
| authorships[3].institutions[0].country_code | US |
| authorships[3].institutions[0].display_name | Duke University |
| authorships[3].author_position | middle |
| authorships[3].raw_author_name | Erin Taylor |
| authorships[3].is_corresponding | False |
| authorships[3].raw_affiliation_strings | Duke University, Durham, United States |
| authorships[4].author.id | https://openalex.org/A5107336010 |
| authorships[4].author.orcid | |
| authorships[4].author.display_name | Emo Welzl |
| authorships[4].countries | CH |
| authorships[4].affiliations[0].institution_ids | https://openalex.org/I35440088 |
| authorships[4].affiliations[0].raw_affiliation_string | ETH Zurich, Zurich, Switzerland |
| authorships[4].institutions[0].id | https://openalex.org/I35440088 |
| authorships[4].institutions[0].ror | https://ror.org/05a28rw58 |
| authorships[4].institutions[0].type | education |
| authorships[4].institutions[0].lineage | https://openalex.org/I2799323385, https://openalex.org/I35440088 |
| authorships[4].institutions[0].country_code | CH |
| authorships[4].institutions[0].display_name | ETH Zurich |
| authorships[4].author_position | last |
| authorships[4].raw_author_name | Emo Welzl |
| authorships[4].is_corresponding | False |
| authorships[4].raw_affiliation_strings | ETH Zurich, Zurich, Switzerland |
| 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.FSTTCS.2020.8 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2025-10-10T00:00:00 |
| display_name | Clustering Under Perturbation Stability in Near-Linear Time |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-11-06T06:51:31.235846 |
| primary_topic.id | https://openalex.org/T10996 |
| primary_topic.field.id | https://openalex.org/fields/17 |
| primary_topic.field.display_name | Computer Science |
| primary_topic.score | 0.9998000264167786 |
| primary_topic.domain.id | https://openalex.org/domains/3 |
| primary_topic.domain.display_name | Physical Sciences |
| primary_topic.subfield.id | https://openalex.org/subfields/1704 |
| primary_topic.subfield.display_name | Computer Graphics and Computer-Aided Design |
| primary_topic.display_name | Computational Geometry and Mesh Generation |
| related_works | https://openalex.org/W3113827893, https://openalex.org/W2890639290, https://openalex.org/W1554183221, https://openalex.org/W2952769483, https://openalex.org/W1588576489, https://openalex.org/W2963896776, https://openalex.org/W2963037070, https://openalex.org/W1562488694, https://openalex.org/W2769916633, https://openalex.org/W2989721195, https://openalex.org/W2950342785, https://openalex.org/W2762594064, https://openalex.org/W2091170478, https://openalex.org/W2893274952, https://openalex.org/W2952399199, https://openalex.org/W2779706529, https://openalex.org/W2005612196, https://openalex.org/W3201369752, https://openalex.org/W2184269872, https://openalex.org/W1624155241 |
| cited_by_count | 1 |
| counts_by_year[0].year | 2024 |
| counts_by_year[0].cited_by_count | 1 |
| locations_count | 8 |
| best_oa_location.id | pmh:oai:drops-oai.dagstuhl.de:13249 |
| 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.FSTTCS.2020.8 |
| primary_location.id | pmh:oai:drops-oai.dagstuhl.de:13249 |
| 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.FSTTCS.2020.8 |
| publication_date | 2020-01-01 |
| publication_year | 2020 |
| referenced_works | https://openalex.org/W166438205, https://openalex.org/W2739434859, https://openalex.org/W2003207175, https://openalex.org/W2028747718, https://openalex.org/W2895978147, https://openalex.org/W2160039585, https://openalex.org/W1558625102, https://openalex.org/W2086959852, https://openalex.org/W1973264045, https://openalex.org/W2511984840, https://openalex.org/W2289504059, https://openalex.org/W2133311553, https://openalex.org/W2963273335, https://openalex.org/W2171125141, https://openalex.org/W2119265025, https://openalex.org/W2962845353, https://openalex.org/W2006514056, https://openalex.org/W2029698681, https://openalex.org/W2016400774, https://openalex.org/W2963896776, https://openalex.org/W2225750372, https://openalex.org/W2028430839, https://openalex.org/W2603442307, https://openalex.org/W2966797629, https://openalex.org/W2971624618, https://openalex.org/W2139230981, https://openalex.org/W2133962824, https://openalex.org/W2187617524, https://openalex.org/W2962736938, https://openalex.org/W2018804864, https://openalex.org/W2011999472, https://openalex.org/W1977541023, https://openalex.org/W1535669030, https://openalex.org/W2059971059, https://openalex.org/W2174175400, https://openalex.org/W2963923450, https://openalex.org/W806373222, https://openalex.org/W2536358984, https://openalex.org/W2059651397, https://openalex.org/W2626597900, https://openalex.org/W2613497313, https://openalex.org/W2073583237, https://openalex.org/W2162148987, https://openalex.org/W1521225740, https://openalex.org/W2943587448, https://openalex.org/W2942858066, https://openalex.org/W2964283450, https://openalex.org/W2787757736, https://openalex.org/W1503339058, https://openalex.org/W2884886133, https://openalex.org/W2150256023, https://openalex.org/W2045964207, https://openalex.org/W2247953682, https://openalex.org/W2962858215, https://openalex.org/W2171394996 |
| referenced_works_count | 55 |
| abstract_inverted_index.+ | 73, 96, 98, 132 |
| abstract_inverted_index.0 | 105 |
| abstract_inverted_index.2 | 72, 95, 131 |
| abstract_inverted_index.5 | 122 |
| abstract_inverted_index.> | 104, 121 |
| abstract_inverted_index.a | 38, 154 |
| abstract_inverted_index.k | 118 |
| abstract_inverted_index.An | 16 |
| abstract_inverted_index.We | 0 |
| abstract_inverted_index.as | 147 |
| abstract_inverted_index.at | 41 |
| abstract_inverted_index.by | 37 |
| abstract_inverted_index.if | 20 |
| abstract_inverted_index.in | 7, 48, 106, 123, 134 |
| abstract_inverted_index.is | 18, 47 |
| abstract_inverted_index.k, | 91 |
| abstract_inverted_index.of | 4, 40, 65, 89, 163 |
| abstract_inverted_index.on | 62, 86, 117 |
| abstract_inverted_index.or | 150 |
| abstract_inverted_index.to | 26, 153 |
| abstract_inverted_index.α | 70, 93, 120, 129 |
| abstract_inverted_index.ε | 99, 103 |
| abstract_inverted_index.For | 75, 110 |
| abstract_inverted_index.Our | 44, 137 |
| abstract_inverted_index.all | 31 |
| abstract_inverted_index.and | 77, 127, 141 |
| abstract_inverted_index.any | 101, 107, 124 |
| abstract_inverted_index.are | 34, 139 |
| abstract_inverted_index.for | 53, 100, 119, 128 |
| abstract_inverted_index.our | 80, 112 |
| abstract_inverted_index.set | 68 |
| abstract_inverted_index.the | 2, 12, 21, 63, 66, 87 |
| abstract_inverted_index.two | 135 |
| abstract_inverted_index.α. | 43 |
| abstract_inverted_index.≥ | 71, 94, 130 |
| abstract_inverted_index.also | 82 |
| abstract_inverted_index.data | 67, 164 |
| abstract_inverted_index.even | 29 |
| abstract_inverted_index.have | 114 |
| abstract_inverted_index.main | 45 |
| abstract_inverted_index.most | 42 |
| abstract_inverted_index.only | 142 |
| abstract_inverted_index.size | 64 |
| abstract_inverted_index.such | 146 |
| abstract_inverted_index.when | 30, 69, 92 |
| abstract_inverted_index.with | 160 |
| abstract_inverted_index.√3 | 97, 133 |
| abstract_inverted_index.exact | 51 |
| abstract_inverted_index.fixed | 108, 125 |
| abstract_inverted_index.local | 148 |
| abstract_inverted_index.times | 59 |
| abstract_inverted_index.under | 11 |
| abstract_inverted_index.whose | 57 |
| abstract_inverted_index.√3. | 74 |
| abstract_inverted_index.choice | 162 |
| abstract_inverted_index.depend | 60 |
| abstract_inverted_index.factor | 39 |
| abstract_inverted_index.metric | 157 |
| abstract_inverted_index.number | 88 |
| abstract_inverted_index.remain | 27 |
| abstract_inverted_index.search | 149 |
| abstract_inverted_index.space, | 158 |
| abstract_inverted_index.spaces | 10 |
| abstract_inverted_index.achieve | 83 |
| abstract_inverted_index.careful | 161 |
| abstract_inverted_index.dynamic | 151 |
| abstract_inverted_index.k-means | 78 |
| abstract_inverted_index.optimal | 23, 28 |
| abstract_inverted_index.problem | 3 |
| abstract_inverted_index.require | 143 |
| abstract_inverted_index.running | 58 |
| abstract_inverted_index.simple, | 140 |
| abstract_inverted_index.applying | 144 |
| abstract_inverted_index.combined | 159 |
| abstract_inverted_index.consider | 1 |
| abstract_inverted_index.constant | 102 |
| abstract_inverted_index.instance | 17 |
| abstract_inverted_index.k-center | 76 |
| abstract_inverted_index.modified | 156 |
| abstract_inverted_index.pairwise | 32 |
| abstract_inverted_index.suitably | 155 |
| abstract_inverted_index.Euclidean | 9 |
| abstract_inverted_index.clusters, | 90 |
| abstract_inverted_index.continues | 25 |
| abstract_inverted_index.distances | 33 |
| abstract_inverted_index.efficient | 50 |
| abstract_inverted_index.instances | 56 |
| abstract_inverted_index.k-median, | 111 |
| abstract_inverted_index.perturbed | 36 |
| abstract_inverted_index.problems, | 79 |
| abstract_inverted_index.stability | 14 |
| abstract_inverted_index.α-stable | 19, 54 |
| abstract_inverted_index.algorithms | 52, 81, 113, 138 |
| abstract_inverted_index.clustering | 6, 24, 55 |
| abstract_inverted_index.dependence | 85, 116 |
| abstract_inverted_index.dimension. | 109 |
| abstract_inverted_index.dimension; | 126 |
| abstract_inverted_index.polynomial | 84, 115 |
| abstract_inverted_index.presenting | 49 |
| abstract_inverted_index.techniques | 145 |
| abstract_inverted_index.underlying | 22 |
| abstract_inverted_index.arbitrarily | 35 |
| abstract_inverted_index.assumption. | 15 |
| abstract_inverted_index.dimensions. | 136 |
| abstract_inverted_index.programming | 152 |
| abstract_inverted_index.structures. | 165 |
| abstract_inverted_index.center-based | 5 |
| abstract_inverted_index.contribution | 46 |
| abstract_inverted_index.perturbation | 13 |
| abstract_inverted_index.near-linearly | 61 |
| abstract_inverted_index.low-dimensional | 8 |
| cited_by_percentile_year.max | 94 |
| cited_by_percentile_year.min | 90 |
| countries_distinct_count | 2 |
| institutions_distinct_count | 5 |
| citation_normalized_percentile.value | 0.19042969 |
| citation_normalized_percentile.is_in_top_1_percent | False |
| citation_normalized_percentile.is_in_top_10_percent | False |