{"id":{"repo_id":"baylor","oai_identifier":"oai:baylor-ir.tdl.org:2104/9570"},"canonical_url":"https://search.dev.ndltd.org/etd/baylor/oai:baylor-ir.tdl.org:2104/9570","repository":{"repo_id":"baylor","name":"Baylor University","base_url":"https://baylor-ir.tdl.org/server/oai/request"},"display":{"title":"Geometric methods of accelerating triangle-inequality-based k-means.","abstract":"One of the most frequent ways how to cluster data is k-means. The standard way of solving the problem is iterative Lloyd's algorithm. This algorithm performs many redundant calculations. Elkan's and Hamerly's algorithms, the heap algorithm and many others eliminate this redundancy by maintaining a set of upper and lower bounds. The goal of this thesis is to further improve the runtime of those algorithms. Namely we improve the way how those bounds are maintained between iterations. By tighter updates of lower bounds we can further decrease the number of distance calculations. The other improvements stated in the thesis include elimination of centroids from the innermost loop of the algorithms when the bounds do not help. The common property of those two proposals is that they require only calculations that are done once per iteration. We also solve a problem that is left as open in the heap algorithm.","abstract_html":"One of the most frequent ways how to cluster data is k-means. The standard way of solving the problem is iterative Lloyd's algorithm. This algorithm performs many redundant calculations. Elkan's and Hamerly's algorithms, the heap algorithm and many others eliminate this redundancy by maintaining a set of upper and lower bounds. The goal of this thesis is to further improve the runtime of those algorithms. Namely we improve the way how those bounds are maintained between iterations. By tighter updates of lower bounds we can further decrease the number of distance calculations. The other improvements stated in the thesis include elimination of centroids from the innermost loop of the algorithms when the bounds do not help. The common property of those two proposals is that they require only calculations that are done once per iteration. We also solve a problem that is left as open in the heap algorithm.","abstract_has_math":false,"creators":["Ryšavý, Petr, 1991-"],"institution":"Baylor University.","degree_name":"M.S.","degree_level":"Masters","degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":["Hamerly, Gregory James, 1977-"],"committee_chairs":[],"committee_members":[],"year":2015,"date_issued":"2015-12","date_published":"2015-12","updated_at":"2026-07-24T01:08:19Z","subjects":["Clustering.","K-means.","Triangle inequality."],"languages":["en"],"rights":["Baylor University works are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. Contact libraryquestions@baylor.edu for inquiries about permission."],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/2104/9570","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Hamerly, Gregory James, 1977-"]},{"key":"dc:creator","label":"Author","values":["Ryšavý, Petr, 1991-"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2016-01-14T17:41:15Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2016-01-14T17:41:15Z"]},{"key":"dc:date.issued","label":"Date","values":["2015-12"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Masters"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["Baylor University."]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Clustering.","K-means.","Triangle inequality."]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Baylor University works are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. Contact libraryquestions@baylor.edu for inquiries about permission."]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/2104/9570"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["One of the most frequent ways how to cluster data is k-means. The standard way of solving the problem is iterative Lloyd's algorithm. This algorithm performs many redundant calculations. Elkan's and Hamerly's algorithms, the heap algorithm and many others eliminate this redundancy by maintaining a set of upper and lower bounds. The goal of this thesis is to further improve the runtime of those algorithms. Namely we improve the way how those bounds are maintained between iterations. By tighter updates of lower bounds we can further decrease the number of distance calculations. The other improvements stated in the thesis include elimination of centroids from the innermost loop of the algorithms when the bounds do not help. The common property of those two proposals is that they require only calculations that are done once per iteration. We also solve a problem that is left as open in the heap algorithm."]},{"key":"dc:format.mimetype","label":"Dc Format Mimetype","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Geometric methods of accelerating triangle-inequality-based k-means."]}]}],"canonical_facts":{"dc:contributor.advisor":["Hamerly, Gregory James, 1977-"],"dc:creator":["Ryšavý, Petr, 1991-"],"dc:date.accessioned":["2016-01-14T17:41:15Z"],"dc:date.available":["2016-01-14T17:41:15Z"],"dc:date.issued":["2015-12"],"dc:description.abstract":["One of the most frequent ways how to cluster data is k-means. The standard way of solving the problem is iterative Lloyd's algorithm. This algorithm performs many redundant calculations. Elkan's and Hamerly's algorithms, the heap algorithm and many others eliminate this redundancy by maintaining a set of upper and lower bounds. The goal of this thesis is to further improve the runtime of those algorithms. Namely we improve the way how those bounds are maintained between iterations. By tighter updates of lower bounds we can further decrease the number of distance calculations. The other improvements stated in the thesis include elimination of centroids from the innermost loop of the algorithms when the bounds do not help. The common property of those two proposals is that they require only calculations that are done once per iteration. We also solve a problem that is left as open in the heap algorithm."],"dc:format.mimetype":["application/pdf"],"dc:identifier.uri":["https://hdl.handle.net/2104/9570"],"dc:language.iso":["en"],"dc:rights":["Baylor University works are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. Contact libraryquestions@baylor.edu for inquiries about permission."],"dc:subject":["Clustering.","K-means.","Triangle inequality."],"dc:title":["Geometric methods of accelerating triangle-inequality-based k-means."],"dc:type":["Thesis"],"thesis:degree_level":["Masters"],"thesis:degree_name":["M.S."],"thesis:institution_name":["Baylor University."]},"updated_at":"2026-07-24T01:08:19Z"}