title: Large scale K-means clustering using GPUs

authors: Li, Mi

subjects: k-means

abstract: The k-means algorithm is widely used for clustering, compressing, and summarizing vector data. We present a fast and memory-efficient GPU-based algorithm for exact k-means, Asynchronous Selective Batched K-means (ASB K-means). Unlike most GPU-based k-means algorithms that require loading the whole dataset onto the GPU for clustering, the amount of GPU memory required to run our algorithm can be chosen to be much smaller than the size of the whole dataset. Thus, our algorithm can cluster datasets whose size exceeds the available GPU memory. The algorithm works in a batched fashion and applies the triangle inequality in each k-means iteration to omit a data point if its membership assignment, i.e., the cluster it belongs to, remains unchanged, thus significantly reducing the number of data points that need to be transferred between the CPU’s RAM and the GPU’s global memory and enabling the algorithm to very efficiently process large datasets. Our algorithm can be substantially faster than a GPU-based implementation of standard k-means even in situations when application of the standard algorithm is feasible because the whole dataset fits into GPU memory. Experiments show that ASB K-means can run up to 15x times faster than a standard GPU-based implementation of k-means, and it also outperforms the GPU-based k-means implementation in NVIDIA’s open-source RAPIDS machine learning library on all the datasets used in our experiments.

text: Large scale K-means clustering using GPUs The k-means algorithm is widely used for clustering, compressing, and summarizing vector data. We present a fast and memory-efficient GPU-based algorithm for exact k-means, Asynchronous Selective Batched K-means (ASB K-means). Unlike most GPU-based k-means algorithms that require loading the whole dataset onto the GPU for clustering, the amount of GPU memory required to run our algorithm can be chosen to be much smaller than the size of the whole dataset. Thus, our algorithm can cluster datasets whose size exceeds the available GPU memory. The algorithm works in a batched fashion and applies the triangle inequality in each k-means iteration to omit a data point if its membership assignment, i.e., the cluster it belongs to, remains unchanged, thus significantly reducing the number of data points that need to be transferred between the CPU’s RAM and the GPU’s global memory and enabling the algorithm to very efficiently process large datasets. Our algorithm can be substantially faster than a GPU-based implementation of standard k-means even in situations when application of the standard algorithm is feasible because the whole dataset fits into GPU memory. Experiments show that ASB K-means can run up to 15x times faster than a standard GPU-based implementation of k-means, and it also outperforms the GPU-based k-means implementation in NVIDIA’s open-source RAPIDS machine learning library on all the datasets used in our experiments.

year: 2022

title: An open-source toolkit for mining Wikipedia

authors: Milne, David N.

subjects: Annotation

abstract: The online encyclopedia Wikipedia is a vast, constantly evolving tapestry of interlinked articles. For developers and researchers it represents a giant multilingual database of concepts and semantic relations, a potential resource for natural language processing and many other research areas. This paper introduces the Wikipedia Miner toolkit, an open-source software system that allows researchers and developers to integrate Wikipedia's rich semantics into their own applications. The toolkit creates databases that contain summarized versions of Wikipedia's content and structure, and includes a Java API to provide access to them. Wikipedia's articles, categories and redirects are represented as classes, and can be efficiently searched, browsed, and iterated over. Advanced features include parallelized processing of Wikipedia dumps, machine-learned semantic relatedness measures and annotation features, and XML-based web services. Wikipedia Miner is intended to be a platform for sharing data mining techniques. Annotation; Disambiguation; Ontology extraction; Semantic relatedness; Toolkit; Wikipedia

text: An open-source toolkit for mining Wikipedia The online encyclopedia Wikipedia is a vast, constantly evolving tapestry of interlinked articles. For developers and researchers it represents a giant multilingual database of concepts and semantic relations, a potential resource for natural language processing and many other research areas. This paper introduces the Wikipedia Miner toolkit, an open-source software system that allows researchers and developers to integrate Wikipedia's rich semantics into their own applications. The toolkit creates databases that contain summarized versions of Wikipedia's content and structure, and includes a Java API to provide access to them. Wikipedia's articles, categories and redirects are represented as classes, and can be efficiently searched, browsed, and iterated over. Advanced features include parallelized processing of Wikipedia dumps, machine-learned semantic relatedness measures and annotation features, and XML-based web services. Wikipedia Miner is intended to be a platform for sharing data mining techniques. Annotation; Disambiguation; Ontology extraction; Semantic relatedness; Toolkit; Wikipedia

year: 2013

title: The Control, environmental sustainability and information management of Maori land in New Zealand

authors: Morad, Munir

subjects: Maori land

abstract: An increase in Maori land claims and the subsequent settlement of a number of land confiscation grievances have prompted calls for change to the land management, cadastral and legal regimes in New Zealand. There is little expert agreement as to Me shape any such reforms should take, but environmental planners and Maori leaders have conceded the need for an overhaul of current land information management practices. Such reforms must aspire to being legally workable, culturally appropriate and environmentally sustainable.
Most land in New Zealand is subject to recent legislation (post-1984) which acknowledges concern for Maori cultural values and ancestral rights and environmental sustainability. The existence of this legislation and growing Maori involvement in formulating public policy for the management of land and environmental resources mean that Maori concepts of land management and sustainability are receiving increasing attention and are likely to influence the shape of future cadastral reforms for Maori lands.

text: The Control, environmental sustainability and information management of Maori land in New Zealand An increase in Maori land claims and the subsequent settlement of a number of land confiscation grievances have prompted calls for change to the land management, cadastral and legal regimes in New Zealand. There is little expert agreement as to Me shape any such reforms should take, but environmental planners and Maori leaders have conceded the need for an overhaul of current land information management practices. Such reforms must aspire to being legally workable, culturally appropriate and environmentally sustainable.
Most land in New Zealand is subject to recent legislation (post-1984) which acknowledges concern for Maori cultural values and ancestral rights and environmental sustainability. The existence of this legislation and growing Maori involvement in formulating public policy for the management of land and environmental resources mean that Maori concepts of land management and sustainability are receiving increasing attention and are likely to influence the shape of future cadastral reforms for Maori lands.

year: 1997