title: An empirical study of moment estimators for quantile approximation

authors: Mitchell, Rory

subjects: computer science

abstract: We empirically evaluate lightweight moment estimators for the single-pass quantile approximation problem, including maximum entropy methods and orthogonal series with Fourier, Cosine, Legendre, Chebyshev and Hermite basis functions. We show how to apply stable summation formulas to offset numerical precision issues for higher-order moments, leading to reliable single-pass moment estimators up to order 15. Additionally, we provide an algorithm for GPU-accelerated quantile approximation based on parallel tree reduction. Experiments evaluate the accuracy and runtime of moment estimators against the state-of-the-art KLL quantile estimator on 14,072 real-world datasets drawn from the OpenML database. Our analysis highlights the effectiveness of variants of moment-based quantile approximation for highly space efficient summaries: their average performance using as few as five sample moments can approach the performance of a KLL sketch containing 500 elements. Experiments also illustrate the difficulty of applying the method reliably and showcases which moment-based approximations can be expected to fail or perform poorly.

text: An empirical study of moment estimators for quantile approximation We empirically evaluate lightweight moment estimators for the single-pass quantile approximation problem, including maximum entropy methods and orthogonal series with Fourier, Cosine, Legendre, Chebyshev and Hermite basis functions. We show how to apply stable summation formulas to offset numerical precision issues for higher-order moments, leading to reliable single-pass moment estimators up to order 15. Additionally, we provide an algorithm for GPU-accelerated quantile approximation based on parallel tree reduction. Experiments evaluate the accuracy and runtime of moment estimators against the state-of-the-art KLL quantile estimator on 14,072 real-world datasets drawn from the OpenML database. Our analysis highlights the effectiveness of variants of moment-based quantile approximation for highly space efficient summaries: their average performance using as few as five sample moments can approach the performance of a KLL sketch containing 500 elements. Experiments also illustrate the difficulty of applying the method reliably and showcases which moment-based approximations can be expected to fail or perform poorly.

year: 2021

title: A lower bound for the size of the smallest critical set in the back circulant latin square

authors: Cavenagh, Nicholas J.

subjects: mathematics

abstract: The back circulant latin square of order n is the latin square based on the addition table for the integers modulo n. A critical set is a partial latin square that has a unique completion to a latin square, and is minimal with respect to this property. In this note we show that the size of a critical set in the back circulant latin square of order n is at least n ⁴/³/2 - n - n²/³/2 + 2n¹/³ - 1.

text: A lower bound for the size of the smallest critical set in the back circulant latin square The back circulant latin square of order n is the latin square based on the addition table for the integers modulo n. A critical set is a partial latin square that has a unique completion to a latin square, and is minimal with respect to this property. In this note we show that the size of a critical set in the back circulant latin square of order n is at least n ⁴/³/2 - n - n²/³/2 + 2n¹/³ - 1.

year: 2006

title: Maori and Pakeha at Te Aroha: the context: 2: Maori in Hauraki in the nineteenth century

authors: Hart, Philip

abstract: After the arrival of Europeans, the Maori population of Hauraki suffered a rapid decline. Some rangatira opposed Pakeha ways, whereas others adopted these for their personal benefit. Keeping ‘the peace of Hauraki’ required government agents to intervene in various disputes between hapu (Ngati Hako in particular causing concern in the 1870s and early 1880s). Although rangatira had links to both Queen Victoria and King Tawhiao, the government was relieved that most remained ‘loyal’ to the new order, and only an intransigent minority opposed the spread of ‘civilisation’ through its roads, telegraph, and the snagging of the Waihou River. A liking for Pakeha goods encouraged collaboration, with Maori joining the cash economy through their involvement in road making, gum digging, and European agriculture to raise money for, in part, traditional gatherings that for a while were more lavish than earlier possible.
Maori of all ranks were quick to stand up for their rights by using the court system, reminding Pakeha of the Treaty of Waitangi, and, in some cases, violence. Tensions were eased by Maori socializing with Pakeha in sport, horse racing, and even the Volunteers, but drinking together in hotels could result in fights, and the lure of alcohol had to be countered by temperance movements. A few Maori children attended school, with Pakeha, and for a time the government provided a (free) doctor and vaccinated them against smallpox (though some preferred traditional ‘cures’ for other ailments). For most, living conditions remained poor. Criminal behaviour was of a minor nature. Christianity had to compete with old beliefs (notably in maketu), newer ones such as ‘Hauhauism’, and by the later years of the century the popularity of the Mormons.
Examples are included of intermarriage, ‘half-castes’, and Pakeha Maori, all being notable features of the time. In a variety of ways, Maori society was sufficiently resilient to adapt and thereby to survive the impact of Pakeha settlement, which produced massive changes and dominated the region well before the end of the century.

text: Maori and Pakeha at Te Aroha: the context: 2: Maori in Hauraki in the nineteenth century After the arrival of Europeans, the Maori population of Hauraki suffered a rapid decline. Some rangatira opposed Pakeha ways, whereas others adopted these for their personal benefit. Keeping ‘the peace of Hauraki’ required government agents to intervene in various disputes between hapu (Ngati Hako in particular causing concern in the 1870s and early 1880s). Although rangatira had links to both Queen Victoria and King Tawhiao, the government was relieved that most remained ‘loyal’ to the new order, and only an intransigent minority opposed the spread of ‘civilisation’ through its roads, telegraph, and the snagging of the Waihou River. A liking for Pakeha goods encouraged collaboration, with Maori joining the cash economy through their involvement in road making, gum digging, and European agriculture to raise money for, in part, traditional gatherings that for a while were more lavish than earlier possible.
Maori of all ranks were quick to stand up for their rights by using the court system, reminding Pakeha of the Treaty of Waitangi, and, in some cases, violence. Tensions were eased by Maori socializing with Pakeha in sport, horse racing, and even the Volunteers, but drinking together in hotels could result in fights, and the lure of alcohol had to be countered by temperance movements. A few Maori children attended school, with Pakeha, and for a time the government provided a (free) doctor and vaccinated them against smallpox (though some preferred traditional ‘cures’ for other ailments). For most, living conditions remained poor. Criminal behaviour was of a minor nature. Christianity had to compete with old beliefs (notably in maketu), newer ones such as ‘Hauhauism’, and by the later years of the century the popularity of the Mormons.
Examples are included of intermarriage, ‘half-castes’, and Pakeha Maori, all being notable features of the time. In a variety of ways, Maori society was sufficiently resilient to adapt and thereby to survive the impact of Pakeha settlement, which produced massive changes and dominated the region well before the end of the century.

year: 2016