title: Fast Algorithms for Nearest Neighbour Search

authors: Kibriya, Ashraf Masood

subjects: Nearest Neighbour

abstract: The nearest neighbour problem is of practical significance in a number of fields. Often we are interested in finding an object near to a given query object. The problem is old, and a large number of solutions have been proposed for it in the literature. However, it remains the case that even the most popular of the techniques proposed for its solution have not been compared against each other. Also, many techniques, including the old and popular ones, can be implemented in a number of ways, and often the different implementations of a technique have not been thoroughly compared either.


  This research presents a detailed investigation of different implementations of two popular nearest neighbour search data structures, KDTrees and Metric Trees, and compares the different implementations of each of the two structures against each other. The best implementations of these structures are then compared against each other and against two other techniques, Annulus Method and Cover Trees. Annulus Method is an old technique that was rediscovered during the research for this thesis. Cover Trees are one of the most novel and promising data structures for nearest neighbour search that have been proposed in the literature.

text: Fast Algorithms for Nearest Neighbour Search The nearest neighbour problem is of practical significance in a number of fields. Often we are interested in finding an object near to a given query object. The problem is old, and a large number of solutions have been proposed for it in the literature. However, it remains the case that even the most popular of the techniques proposed for its solution have not been compared against each other. Also, many techniques, including the old and popular ones, can be implemented in a number of ways, and often the different implementations of a technique have not been thoroughly compared either.


  This research presents a detailed investigation of different implementations of two popular nearest neighbour search data structures, KDTrees and Metric Trees, and compares the different implementations of each of the two structures against each other. The best implementations of these structures are then compared against each other and against two other techniques, Annulus Method and Cover Trees. Annulus Method is an old technique that was rediscovered during the research for this thesis. Cover Trees are one of the most novel and promising data structures for nearest neighbour search that have been proposed in the literature.

year: 2007

title: Correlation-based feature selection of discrete and numeric class machine learning

authors: Hall, Mark A.

subjects: computer science

abstract: Algorithms for feature selection fall into two broad categories: wrappers that use the learning algorithm itself to evaluate the usefulness of features and filters that evaluate features according to heuristics based on general characteristics of the data. For application to large databases, filters have proven to be more practical than wrappers because they are much faster. However, most existing filter algorithms only work with discrete classification problems. This paper describes a fast, correlation-based filter algorithm that can be applied to continuous and discrete problems. The algorithm often out-performs the well-known ReliefF attribute estimator when used as a preprocessing step for naive Bayes, instance-based learning, decision trees, locally weighted regression, and model trees. It performs more feature selection than ReliefF does-reducing the data dimensionality by fifty percent in most cases. Also, decision and model trees built from the preprocessed data are often significantly smaller.

text: Correlation-based feature selection of discrete and numeric class machine learning Algorithms for feature selection fall into two broad categories: wrappers that use the learning algorithm itself to evaluate the usefulness of features and filters that evaluate features according to heuristics based on general characteristics of the data. For application to large databases, filters have proven to be more practical than wrappers because they are much faster. However, most existing filter algorithms only work with discrete classification problems. This paper describes a fast, correlation-based filter algorithm that can be applied to continuous and discrete problems. The algorithm often out-performs the well-known ReliefF attribute estimator when used as a preprocessing step for naive Bayes, instance-based learning, decision trees, locally weighted regression, and model trees. It performs more feature selection than ReliefF does-reducing the data dimensionality by fifty percent in most cases. Also, decision and model trees built from the preprocessed data are often significantly smaller.

year: 2000-05

title: The alienation of the Opuatia block: A GIS case study report written for Counting our Tūpuna

authors: Whitehead, Jesse

abstract: This report provides an analysis and visualisation of the fragmentation and alienation of the Opuatia block (Opuatia hereafter), as well as changes in its ownership and geographic structure since 1866.
The three main aims are to quantify the amount of Opuatia remaining in Ngāti Tiipa ownership at the end of each decade, identifying critical moments in time, and highlighting the processes through which Opuatia was alienated and fragmented. These questions are addressed through a bespoke method that was developed to link data from several sources. These include (but are not limited to) historic records of land alienation, held by the Māori Land Court, and geospatial information available through Land Information New Zealand.
The key findings show that approximately 94% of the original Opuatia has been alienated, with only small parcles of land remaining in Ngāti Tiipa ownership. The late 1890s and early 1900s were a criticial period where over 80% of alienations were carried out. The results inidcate that the Crown was a key driver of this process, directly alienating more than 18,000 acres from Opuatia, much of which was taken on a single day in 1896. Individual settlers were responsible for most other alienations, and some of the same names appear several times in the historical record as settler families alienated clusters of land to build up significant stakes in the area. Finally, another result of this report is the method itself, which outlines an approach for tracing a defined block of land through the Native Land Court and linking this information to geospatial datasets.
The limitations of this report include the poor interoperability of key data sources, and the barriers that this presents to other hapū or organisations who may want to replicate this work. A more detailed investigation of archival records is required to examine the specific reasons behind why each parent block, and the subdivisions with them, was alienated from Ngāti Tiipa ownership.

text: The alienation of the Opuatia block: A GIS case study report written for Counting our Tūpuna This report provides an analysis and visualisation of the fragmentation and alienation of the Opuatia block (Opuatia hereafter), as well as changes in its ownership and geographic structure since 1866.
The three main aims are to quantify the amount of Opuatia remaining in Ngāti Tiipa ownership at the end of each decade, identifying critical moments in time, and highlighting the processes through which Opuatia was alienated and fragmented. These questions are addressed through a bespoke method that was developed to link data from several sources. These include (but are not limited to) historic records of land alienation, held by the Māori Land Court, and geospatial information available through Land Information New Zealand.
The key findings show that approximately 94% of the original Opuatia has been alienated, with only small parcles of land remaining in Ngāti Tiipa ownership. The late 1890s and early 1900s were a criticial period where over 80% of alienations were carried out. The results inidcate that the Crown was a key driver of this process, directly alienating more than 18,000 acres from Opuatia, much of which was taken on a single day in 1896. Individual settlers were responsible for most other alienations, and some of the same names appear several times in the historical record as settler families alienated clusters of land to build up significant stakes in the area. Finally, another result of this report is the method itself, which outlines an approach for tracing a defined block of land through the Native Land Court and linking this information to geospatial datasets.
The limitations of this report include the poor interoperability of key data sources, and the barriers that this presents to other hapū or organisations who may want to replicate this work. A more detailed investigation of archival records is required to examine the specific reasons behind why each parent block, and the subdivisions with them, was alienated from Ngāti Tiipa ownership.

year: 2021