Reference point hyperplane trees

Richard Connor*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Citation (Scopus)

Abstract

Our context of interest is tree-structured exact search in metric spaces. We make the simple observation that, the deeper a data item is within the tree, the higher the probability of that item being excluded from a search. Assuming a fixed and independent probability p of any subtree being excluded at query time, the probability of an individual data item being accessed is (1 − p)d for a node at depth d. In a balanced binary tree half of the data will be at the maximum depth of the tree so this effect should be significant and observable. We test this hypothesis with two experiments on partition trees. First, we force a balance by adjusting the partition/exclusion criteria, and compare this with unbalanced trees where the mean data depth is greater. Second, we compare a generic hyperplane tree with a monotone hyperplane tree, where also the mean depth is greater. In both cases the tree with the greater mean data depth performs better in high-dimensional spaces. We then experiment with increasing the mean depth of nodes by using a small, fixed set of reference points to make exclusion decisions over the whole tree, so that almost all of the data resides at the maximum depth. Again this can be seen to reduce the overall cost of indexing. Furthermore, we observe that having already calculated reference point distances for all data, a final filtering can be applied if the distance table is retained. This reduces further the number of distance calculations required, whilst retaining scalability. The final structure can in fact be viewed as a hybrid between a generic hyperplane tree and a LAESA search structure.

Original languageEnglish
Title of host publicationSimilarity Search and Applications - 9th International Conference, SISAP 2016, Proceedings
EditorsErich Schubert, Michael E. Houle, Laurent Amsaleg
PublisherSpringer-Verlag
Pages65-78
Number of pages14
ISBN (Print)9783319467580
DOIs
Publication statusPublished - 1 Jan 2016
Event9th International Conference on Similarity Search and Applications, SISAP 2016 - Tokyo, Japan
Duration: 24 Oct 201626 Oct 2016

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9939 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference9th International Conference on Similarity Search and Applications, SISAP 2016
Country/TerritoryJapan
CityTokyo
Period24/10/1626/10/16

Fingerprint

Dive into the research topics of 'Reference point hyperplane trees'. Together they form a unique fingerprint.

Cite this