EUVIMEDEUVIMED entdecken
Crossref

Local Stability of Rankings

Felix S. Campbell, Yuval Moskovitch

Proceedings of the ACM on Management of Data · 18.05.2026 · 4 (3) · 1-27

DOI: 10.1145/3802081 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 18.05.2026. Verfasst von Felix S. Campbell und 1 weiteren Autor:innen. Die Arbeit nennt 52 Literaturangaben. Gefördert von: Israel Science Foundation, Frankel Center for Computer Science, BGU.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Rankings play a crucial role in decision-making. However, if minor changes to items significantly alter their rankings, the quality of the decisions being made can be compromised. The stability of ranking is a measure used to assess how modifications to the ranking algorithm or data affect results. While previous work has focused on stability of the ranking under changes to the algorithm, we introduce a novel measure we refer to as local stability . Local stability indicates the effect of minor changes to the values of an item in the ranking on its rank. Our proposed definition furthermore takes into account the presence of multiple items with similar qualities in the ranking, called dense regions, permitting minor modifications to swap the positions of items within the region. We show that computing this measure in general is hard, and in turn propose a relaxation of the definition to admit approximation. We present (i) LStability, a sampling-based algorithm for approximating local stability, on which we make probably-approximately-correct-type guarantees through the use of concentration inequalities, and (ii) Detect-Dense-Region, an algorithm based on this approach to detect the dense region an item lies in, if it exists. We introduce a number of optimizations to our algorithms to improve their scalability and efficiency. We validate our proposed framework through an extensive suite of experiments, including case studies highlighting the utility of our definitions.

Förderung

  • Israel Science Foundation
  • Frankel Center for Computer Science, BGU

Zitieren

APA

Campbell, F. S., & Moskovitch, Y. (2026). Local Stability of Rankings. Proceedings of the ACM on Management of Data, 4(3), 1-27. https://doi.org/10.1145/3802081

Vancouver

Campbell FS, Moskovitch Y. Local Stability of Rankings. Proceedings of the ACM on Management of Data. 2026;4(3):1-27. doi:10.1145/3802081

BibTeX
@article{Campbell2026,
  author = {Campbell, Felix S. and Moskovitch, Yuval},
  title = {Local Stability of Rankings},
  journal = {Proceedings of the ACM on Management of Data},
  year = {2026},
  volume = {4},
  number = {3},
  pages = {1--27},
  doi = {10.1145/3802081}
}
Kostenlos starten →